들어가며

최근 Coursera의 Game Theory Course를 수강 중이다. 꽤 만족도가 높아서, Game Theory 2: Advanced Application course까지 이어서 수강할 계획을 세우고 있다. 두 번째 course가 9월 12일부터 시작하기 때문에 첫 번째 course를 9월 첫주까지 끝낼 생각으로 수강 중이다. 아무래도 공부를 하고 나서 블로그에 정리 글을 올리지 않으면 공부를 끝마친 기분이 들지 않아서, 이번 course도 블로그에 계속 요약글을 올릴까한다. Geoffrey Hinton 교수가 2012년 Coursera에서 강의 한 Neural Networks for Machine Learning 이후로 Coursera에 처음 들어가봤는데, 예전이랑 많이 바뀐 것 같다. 진짜 MOOC에 집중해서 ‘수강’이라는 개념을 좀 더 강화한듯. 예전에 조금 보다 말았던 Probabilistic Graphical Model이나 위에 링크한 Neural Network course도 전부 예전 자료에 access가 되지 않는다. 음.. 다시 듣고 싶었는데 또 enrollment하라고 해서 둘 다 일단 enroll해둔 상태. 이래저래 Coursera는 내 취향에 안맞는다.

다시 본문으로 돌아와서, 이 글은 Coursera의 Game Theory course의 첫 주차 강의를 요약한 글이다. 대부분의 course의 첫 주가 그러하듯, 이 lecture 역시 Game Theory에 대한 introduction과 몇 가지 기본적인 definition에 대해 설명한다.

What is “Game”?

제목이 ‘Game Theory’ 인 만큼, game이 무엇인지부터 정의하고 넘어갈 필요가 있다. 우리가 게임이라고 부르는 것들에는 무엇이 포함될까? 먼저 대표적인 게임인 가위바위보를 생각해보자. 이 게임을 구성하기 위해서는 먼저 두 명의 player가 있으야 하며, 각 player들이 할 수 있는 action (가위, 바위, 보)가 있어야하며, 마지막으로 게임이 끝날 때 마다 정해지는 payoff (승/패)가 있어야한다.

Game을 나타내는 standard한 방법으로는 크게 두 가지가 있다. 하나는 Normal form (a.k.a. Matrix form, strategic form)이고, 또 하나는 Extensive form이다. Normal form은 player들의 action에 따른 각각의 player들의 payoff를 표현한 방법으로, player가 두 명이라면 2차원 matrix로 표현이 가능하기 때문에 matrix form이라고도 부른다. Normal form은 player들이 지금 당장 action을 취했을 때 나타나는 payoff를 나타내는데, 예를 들어 체스같은 게임은 sequential한 movement를 포함하기 때문에 normal form으로 나타내기 쉽지 않다. (처음부터 게임이 끝날 때 까지 모든 가능한 경우의 수를 action으로 나타내면 가능할 수도 있지만 space가 너무 넓기 때문에 사실상 표현이 불가능하다.) Extensive form은 그런 sequential한 movement를 포함하는 form으로, tree형태로 표현이 된다고 한다. 보다 자세한 얘기는 course의 뒷 부분에서 다룬다고 하니, 여기에서는 우선 넘어가자.

Definition of Game: The Normal Form

이제 game을 normal form을 정의해보자. Finite, n-person normal form game: <N, A, u>는 다음과 같이 정의된다.

• Players: $N = {1, \ldots, n}$ is a finite set of n, indexes by i
• Action set for player i $A_i$

  • $a = (a_1, \ldots, a_n) \in A$, where $A = A_1 \times \ldots \times A_n$ 을 action profile이라 부른다.

• Utility function or Payoff function for player i: $u_i: A \to \mathbb R$
  • $u = (u_1, \ldots, u_n)$을 utility function의 profile이라 부른다.

이제 두 명이 진행하는 가위바위보를 normal form, 정확히는 matrix 형태로 적어보자.

• Player는 1과 2 두 명이 존재한다.

• Row는 player 1의 action $a_1 \in A_1$에 대응하고, column은 player 2의 action $a_2 \in A_2$에 대응한다.

• Matrix의 각각의 cell은 각 player들의 payoff value에 해당한다. (a, b)라고 표현되며, 여기에서 a는 1번의 payoff, b는 2번의 payoff이다.

	Rock	Paper	Scissors
Rock	0, 0	-1, 1	1, -1
Paper	1, -1	0, 0	-1, 1
Scissors	-1, 1	1, -1	0, 0

비슷한 방식으로 훨씬 더 큰 게임도 기술할 수 있다.

Examples

Matching Pennies

두 player가 동전의 면을 고르는데, 한 명은 둘이 같은 선택을 해야, 한 명은 둘이 다른 선택을 해야 이기는 게임

	Head	Tails
Head	1, -1	-1, 1
Tails	-1, 1	1, -1

Rock-Paper-Scissors

우리가 아는 바로 그 가위바위보는 아래와 같이 쓸 수 있다. (위에서 이미 언급했었다)

	Rock	Paper	Scissors
Rock	0, 0	-1, 1	1, -1
Paper	1, -1	0, 0	-1, 1
Scissors	-1, 1	1, -1	0, 0

Matching Pennies와 Rock-Paper-Scissors는 서로 정확히 반대의 payoff를 가지는 게임인데, 이런 게임을 ‘games of pure competition’이라고 부른다.

Prisoner’s Dilemma

그 유명한 죄수의 딜레마¹도 아래와 같이 표현할 수 있다.

	C	D
C	a, a	b, c
D	c, b	d, d

이때 c > a > d > b 라는 관계가 성립하면 ‘죄수의 딜레마’가 발생한다.

Battle of the Sexes

어느 커플이 영화관에 영화를 보러갔는데, 남자와 여자가 선호하는 영화가 조금씩 달랐다고 가정해보자. 남자는 어벤져스를 (액션을) 더 좋아하고, 여자는 러브 엑츄얼리를 (로맨틱 코미디를) 더 좋아한다고 생각해보자. 하지만 둘 다 서로 떨어져서 영화를 보는건 원하지 않는다. 즉, 둘 다 같은 영화를 봐야지만 payoff가 발생하는데, 이렇게 둘 다 같은 interest를 가진 게임을 cooperation game이라고 한다. 그런데 지금처럼 각자 서로 조금씩 interest가 달라서 경쟁하는 경우에는 cooperation과 competition의 특징을 둘 다 가지게 된다. Normal form으로는 아래와 같이 표현할 수 있다.

	B	F
B	2, 1	0, 0
F	0, 0	1, 2

Best Response and Nash Equilibrium

이제 게임이 무엇인지 정의하였으니 Game Theory의 핵심이라 할 수 있는 Nash Equilibrium에 대해 알아보자. Nash Equilibrium (NE)를 한 마디로 정의하자면, 게임에 참여하는 모든 agent들이 현재 선택한 action이 선택할 수 있는 모든 action들보다 더 좋거나 같은 상황이 유지되는 상황이다. 죄수의 딜레마를 예로 들어보자. 위의 게임에서 둘 다 (D, D)를 고르는 경우, 죄수 1은 협조하는 것이 협조하지 않는 것 보다 좋고, 죄수 2역시 마찬가지이므로 둘 다 협조하는 것이 NE에 해당한다. 이를 좀 더 정확한 formula로 정의해보자.

먼저 Best response $a_i^*$를 다음과 같이 정의하자

$$a_i^* \in \mbox{BR}(a_{-i}) ~\mbox{iff}~ \forall a_i \in A_i, u(a_i^*, a_{-i}) \geq u_i(a_i, a_{-i}), ~\mbox{where}~ a_{-i} = (a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n)$$

즉, best response란 나를 제외한 모든 player들이 어떻게 행동하는지 알고 있을 때 내가 선택할 수 있는 가장 optimal한 action이 best response(BR)이다. 이때 유의할 점은, BR은 하나만 존재하는 것이 아니라 동시에 여러 개 존재할 수도 있기 때문에 위의 정의에서 $a_i^*$가 set $\mbox{BR}(a_{-i})$에 포함되게 되는 것이다.

이제 BR을 정의했으니 NE를 정의할 차례이다. 앞에서 설명한대로 NE는 모든 agent들이 stable한 action을 가지는 상태를 말하며, 모든 player들이 optimal하다면 항상 BR을 고를 것이다. 즉, NE는 모든 player들이 BR을 선택했을 경우가 NE로 정의되게 된다. 보다 엄밀한 Nash Equilibrium의 정의는 다음과 같다.

$$a = (a_1, \ldots, a_n) ~\mbox{is a "pure strategy" Nash Equilibrium iff}~ \forall i, a_i \in BR(a_{-i}).$$

이제 실제 예시들에서 (pure strategy) Nash Equilibrium을 찾아보자. 먼저 죄수의 딜레마는 앞에서 설명한 것 처럼, 어떤 상황에서도 둘 다 협조를 하는 것이 더 나은 선택이므로, 둘 다 협조하는 쪽이 NE가 된다. Battle of the Sexes에서는 남자가 액션영화를 골랐을 때, 여자가 로코를 고르면 payoff가 0이므로 반드시 액션을 고르게 된다. 반대로 남자가 로코를 골랐다면 여자는 반드시 로코를 고르게 된다. 남자에게도 같은 방식이 적용되므로, 이 게임의 NE는 둘 다 같은 영화를 고르는 두 점이 된다.

마지막으로 Matching Pennies를 살펴보자. 시작하기 전에 Pure strategy NE는 서로 상대가 고른 전략을 정확하게 알고 있다고 가정한다는 점에 유의하자. 만약 player 2가 head를 골랐다면 player 1은 head를 고르는 것이 optimal solution이다. (1은 서로 같은 면을 골라야, 2는 서로 다른 면을 골라야 이긴다) 그런데 이렇게 되면 player 2가 player 1이 head를 골랐다는 것을 알기 때문에 player 2는 tail을 고르는 것이 optimum이다. 다시 player 1은 tail을 고르게 되고, player 2는 head를 고르게 된다. 이제 player 1은 다시 head를 고르게 되는데, 이 결과는 우리가 가장 먼저 살펴봤던 결과와 같다. 즉, Matching Pennies는 cycle이 생기기 때문에 pure strategy Nash Equilibrium이 존재하지 않는다는 사실을 알 수 있다.

	Head	Tails
Head	1, -1	-1, 1
Tails	-1, 1	1, -1

Dominant Strategies

이제 Game Theory에서 중요한 개념 중 하나인 dominant strategy에 대해 살펴보자. Strategy를 아직 엄밀하게 정의한 상태는 아니기 때문에 단순히 ‘어떤 action을 고르는 행위’ 정도로 이해하자. (Reinforcement learning에서 나오는 policy와 동일한 개념이다.) 이때, (strictly/weakly) dominant라는 것은 다음과 같이 정의할 수 있다.

$$s_i ~\mbox{strictly dominates}~ s_i^\prime ~\mbox{if}~ \forall s_{-i} \in S_{-i}, u_i(s_i, s_{-i}) > u_i(s_i^\prime, s_{-i}).$$ $$s_i ~\mbox{weakly dominates}~ s_i^\prime ~\mbox{if}~ \forall s_{-i} \in S_{-i}, u_i(s_i, s_{-i}) \geq u_i(s_i^\prime, s_{-i}).$$

만약 어떤 strategy가 모든 다른 strategy에 대해 dominate하다면 우리는 그런 strategy를 dominant하다고 부른다. 정의에 따라 dominant strategy가 성립하는 경우, Nash equilibrium이 성립하며, 만약 strictly dominant한 strategy라면, Nash equilibrium은 그 점에서만 unique하다.

Pareto Optimality

마지막으로 Pareto optimality에 대해 다루면 week1은 끝이 난다. 지금까지 우리는 각각의 player의 입장에서 game과 strategy, equilibrium 등을 정의했다. 그런데 만약에 게임에 참여하는 player가 아니라 게임에 참여하지 않는 누군가의 관점에서 게임을 결정하게 된다면 어떻게 될까? 예를 들어 죄수의 딜레마에서 바깥에 있는 우리는 둘 모두가 협조하지 않는 것이 optimal이라는 것을 알고 있는데, 이런 것들을 게임에 반영할 수는 없을까? 즉, 게임을 참여하는 입장이 아닌 상태에서 ‘최종 outcome’이 게임 참여자들에게 어떤 결과를 주는지를 바탕으로 action을 결정하는 것이다. 그렇다면 이것을 어떻게 엄밀하게 정의할 수 있을까?

아이디어는 이렇다. 하나의 outcome $o$가 또 다른 outcome $o^\prime$ 보다 모든 다른 agent들에게 좋고, 만약 $o^\prime$을 $o$보다 strictly prefer하는 agent가 존재한다면, $o^\prime$을 고르는 것이 $o$를 고르는 것 보다 나을 것이라고 생각하는 것이다. 또한 이런 경우 우리는 ‘$o$ Pareto-dominates $o^\prime$’ 라고 정의한다. 이렇게 정의할 경우, Pareto-optimal은 다음과 같이 정의된다.

An outcome $o^*$ is Pareto-optimal if there is no other outcome that Pareto-dominates it.

물론 2주차에서 다루듯, Pareto optimal이 존재하는지 확인하는 문제는 NP-complete이기 때문에 풀기 매우 어려운 문제이긴 하지만, 이런 개념을 통해 조금 더 ‘공익적인’ 게임을 설계할 수도 있다.

정리

가장 간단한 개념을 다루는 첫 주차인 만큼, 전반적으로 ‘개념’들에 초점이 맞춰져 있다. 가장 기본적이라고 할 수 있는 ‘game’의 정의와 Nash Equilibrium, dominat strategy와 Pareto optimality까지, 전체적으로 간단한 개념들을 훑어가는 주라고 생각하면 될 것 같다.

References

1. Coursera Game Theory Course

변경 이력

• 2016년 8월 21일: 글 등록

---

Game Theory 스터디의 다른 글들

Game Theory

• Week 1: Introduction and Overview
• Week 2: Mixed-Strategy Nash Equilibrium
• Week 3: Alternate Solution Concepts
• Week 4: Extensive-Form Games
• Week 5: Repeated Games
• Week 6: Bayesian Games
• Week 7: Coalitional Games

Game Theory 2: Advanced Application

• Week 1: Social Choice
• Week 2: Mechanism Design
• Week 3: Efficient Mechanisms
• Week 4: Auctions