1. 개요
Cooperative Game Theory or Coalitional Game Theory필요에 따라 다른 플레이어들과 협력(cooperation)을 할 수 있는[1] 게임을 연구하는 분야이다.
다른 말로, 플레이어들끼리 파벌(coalition)을 이룰 수 있다고 해서 Coalitional Game Theory라고도 한다.
어떤 게임을 하기 전에 플레이어들끼리 자유롭게 대화하며 한번 사인하고 나면 나중에 강제적으로 지킬 수밖에 없는 계약(commitment)을 마음대로 할 수 있다고 가정한다.[2] 여기에서 포인트는 이 '계약'이라는 것이 한번 이루어지면 모두가 그 계약의 내용대로 행동할 것이 보장된다는 것이다. 이러한 보장이 없어서 나중에 어떤 플레이어가 계약을 어기게 된다면 이 계약은 아무런 의미가 없다. 이러한 영단어 commitment의 뉘앙스를 한국어로 살리기는 힘든데, 저서에 따라서는 '맹약'이라고 번역되기도 한다.
파벌이 실질적으로 특수 목적을 위해 만들어진 사람들의 모임인 만큼 정당 및 시민단체의 형성, 대선후보 단일화, 기업 인수합병, 직원들의 이직 등의 모델링에 쓰일 수 있으므로 특히 정치학이나 경제학에서 중요하다.
2. 내용
죄수의 딜레마 게임을 기억해보면 다음과 같은 Payoff로 표현 가능하다.| 상대의 협력 | 상대의 배신 | |
| 나의 협력 | 2, 2 | 0, 3 |
| 나의 배신 | 3, 0 | 1, 1 |
위의 숫자는 해당 행동을 했을 때 (나, 상대)의 대략적 이득을 가장 간단한 숫자로 표현한 것이다.
당연히 내시 균형은 서로 (배신, 배신)을 하는 것이다.
하지만 여기서 두 사람이 서로 협력할 수 있다면[3] 두 사람이 협력하여 (2, 2)의 이득을 얻고 이를 (가능하다면) 똑같이 분배할 수도 있을 것이다.
이렇게 두 사람이 협력하여 한 집단이 되는 것을 coalition이라 한다.
이 coalition은 한 사람처럼 행동할 수도, 구성원 간의 갈등으로 와해될 수도 있지만 가장 간단하게는 파벌이 한 몸처럼 매우 효율적으로 행동하는 것으로[4] 가정할 수 있다. 그럼 2인 죄수의 딜레마 게임은 1인 2차원 행동 최적화 문제로 collapse 될 수 있다. 이와 비슷하게 3인 이상 멀티플레이어 게임에 대해서도 각 파벌 조합에 대해 각 파벌 갯수만큼 플레이어가 collapse되어 원래 게임을 다음 두 종류의 게임으로 쪼개서 풀 수 있다.
- 파벌을 각 플레이어로 생각한 비협조적 게임 (non-cooperative game)
- 한 파벌 안에서 멤버끼리 이득을 분배하는 Subgame인 협상 게임 (bargaining game)
여기서 파벌 구성 되었을 때 어떠한 의사결정으로 action이 선택될지는 고려하지 않고, 그저 최종 action과 그에 따른 payoff만 주어진다고 가정한다.[5] 그리고 이 파벌이 구성되었을 때 받는 payoff 함수가 주어졌을 때 어떻게 게임의 균형이 나타날 것인가를 연구하는 것이 협력적 게임 이론의 기본적은 접근 방법이다.
이론적 간편함을 위해 (for simlicity), 효용은 돈처럼 주거나 받거나가 가능하다고 가정한다 (transferrable utility).[6]
3. 해 (Solution)
3.1. 코어 (Core)
게임이론에서, 플레이어 모두가 한 마음 한 뜻으로 함께 움직인다면 당연히 가장 많은 output을 얻을 수 있을 것이다 (분배는 어떻게 할지는 모르겠지만). 그렇게 모든 플레이어가 연합한 것을 대연합(grand coalition)이라 한다.코어란, 협력적 게임의 내시 균형과 같은 것으로, 누구라도 대연합을 깨는 순간 (혼자 나오거나 자기들끼리 파벌에 붙더라도) 본인에게 손해가 되는 균형을 의미한다.
예를 들어, 다음과 같은 보물 상자가 있다고 해보자.
보물 상자
필요한 열쇠: a, b
이 보물 상자를 열기 위해선 두 개의 열쇠 a와 b가 필요하다.필요한 열쇠: a, b
이 보물 상자를 가지기 위해 3명의 사람이 눈치 게임을 한다. 각각 가지고 있는 열쇠는 다음과 같다.
플레이어
1: a 소유
2: a 소유
3: b 소유
즉, 보물 상자를 열기 위해서는 a, b 두개의 키가 필요하므로 3명 중 2명은 무조건 협력하여야 한다.1: a 소유
2: a 소유
3: b 소유
이 중 플레이어 3 혼자서만 b 키를 소유하고 있으므로 협력할 때에는 무조건 3이 있어야만 보물 상자를 열 수 있다. 모두가 연합하나 2명만 연합하나 플레이어 3만 있으면 보물 상자는 하나이므로 얻는 이득은 같다.
이 협력 게임의 균형, 즉 코어는 3이 (누구랑 연합할지는 모르겠으나) 아무나랑 협력해 3 혼자 보물 상자를 다 가지는 것이다.
왜냐하면, 만약 1과 3이 협력하여 2:8로 보물은 나누려고 하면, 2가 1:9로 제안하여 3이 넘어올 수 있고, 그럼 다시 1이 0.5:9.5를 제안하여 3을 다시 뺏을 수 있고, 이를 다시 2가 0.2:9.8을 제안하여 3을 뺏어오고, ..., 이를 반복하다보면 플레이어 3이 모든 보물을 갖는 것이 균형이다.
코어의 정의는 수학적으로 다음과 같다. n명의 플레이어가 있고 이 중 몇명이 S라는 연합을 만들어 얻을 수 있는 최대 이득이 [math(v(S))]라고 할 때, 코어 [math(\mathbf{v}^*)]는 각 n명의 플레이어가 얻는 이득 벡터들의 집합으로 (그 합은 대연합하였을 때 얻는 이득),
[math(\displaystyle \mathbf{v}^* \iff \forall{S}: v(S) \le v^*(S) := \sum_{i \in S} v_i^* )]
"대연합에 들어와 [math(\mathbf{v}^*)]에 해당하는 만큼 돈을 받고 있다면, 대연합에서 나와 새로 파벌 [math(S)]을 새로 만들려 해도, 가만히 있는 것보다 무조건 파벌 S가 얻는 total benefit이 줄어들거나 같아서 새로 파벌을 만들 수 없다.[7]"
"대연합에 들어와 [math(\mathbf{v}^*)]에 해당하는 만큼 돈을 받고 있다면, 대연합에서 나와 새로 파벌 [math(S)]을 새로 만들려 해도, 가만히 있는 것보다 무조건 파벌 S가 얻는 total benefit이 줄어들거나 같아서 새로 파벌을 만들 수 없다.[7]"
을 만족하는 가능한 [math(\mathbf{v}^*)]의 집합이 core이다.
다음과 같은 게임에서는 core가 없다.
짝짓기 게임
3명이 플레이하는데, 2명 이상 팀을 만들어 오면 보물을 준다.
즉, 이미 2명이 짝 지어져 각각 얼마만큼 배분할지 정해졌을 때, 다른 한 사람이 (물론 그 사람은 지금 아무것도 못 얻고 있다) 둘 중 한명에게 다가가 "만약 나랑 팀하면, 너가 지금 받는 것보다 더 많이 줄게"하면 무조건 옮기게 되어 있다. 그런데 이는 offer를 받지 못하고 남는 사람도 똑같이 할 수 있으므로 이게 계속 반복이 되어 경쟁 게임에서의 best response가 사이클 도는 것처럼 되어 균형이 존재하지 않는다.3명이 플레이하는데, 2명 이상 팀을 만들어 오면 보물을 준다.
이처럼 문제가 조금만 복잡해져도 파벌안에 있는 모든 사람이 다른 파벌로 갈 요인을 아예 없애게 하는게 은근 어려워서 core가 존재하지 않는 경우가 굉장히 많다. 그 이유는 core의 정의가 옮기는 사람만 대우를 잘해주면 되는게 아니라, 기존에 있던 사람들도 다 안 나가게 잘해줘야하기 때문이다.[8]
3.2. 섀플리 값 (Shapley Value)
섀플리는 협력적 게임에서 전략적 선택은 아예 무시하고, 모두가 일단 협력하여 대연합(grand coalition)을 일단 만들었다면 어떻게 분배해야 공정한지 연구하였는데, 나름의 기준(Efficiency, Linearity, Symmetry)을 만족하는 유일한 분배 방법이 바로 섀플리 값이다. 즉, 정의로운 "공정한 분배"를 어떻게할 것인가를 답한 것이 섀플리 값이라고 할 수 있겠다.섀플리 값이란 랜덤하게 파벌이 형성되었을 때 i번째 플레이어가 그 파벌에 낌으로 해서 얻을 수 있는 추가 이득의 평균이다.
수학적으로는 다음과 같다. n명의 플레이어가 협력 게임을 할 때, i번째 플레이어의 공정한 분배 값은
[math(\displaystyle \varphi_i = \mathbb{E} \big[ v(S \cup \{i\}) - v(S) \big])]
여기서 [math(S)]는 i가 없는 랜덤하게 형성된 파벌. 그 확률은 [math(\mathbb{P}(S) = |S|!(n-|S|-1)!/n!)]로 주어진다.
여기서 [math(S)]는 i가 없는 랜덤하게 형성된 파벌. 그 확률은 [math(\mathbb{P}(S) = |S|!(n-|S|-1)!/n!)]로 주어진다.
저 확률 분포는 랜덤하게 플레이어들을 줄 세운 후, 임의의 i번째 플레이어를 골라 i의 왼쪽은 전부 같은 파벌 S라고 했을 때 그 S의 확률 분포이다. 예를 들어 세 명의 플레이어 1,2,3이 있을 때, 세 명 모두를 랜덤하게 줄세우는 경우의 수는 [math(3 \times 2 \times 1 = 6)]가지이고, i를 예를 들어 2라고 정한다면 파벌 S의 조합은 (i의 왼쪽) 다음과 같다.
||<tablebgcolor=#fff,#2d2f34><rowbgcolor=#00a495><rowcolor=#fff> 나열 || S (2보다 왼쪽) ||
| 1 2 3 | [math(\{1\})] |
| 1 3 2 | [math(\{1,3\})] |
| 2 1 3 | [math(\emptyset)] |
| 2 3 1 | [math(\emptyset)] |
| 3 1 2 | [math(\{3,1\})] |
| 3 2 1 | [math(\{3\})] |
각 파벌이 나올 확률은 총 6개 중에 [math(\{1\})]은 1개 [math(\{1,3\})]은 2개 (순서 바꿔도 똑같으니), [math(\emptyset)]은 2개, [math(\{3\})]은 1개 이므로,
||<tablebgcolor=#fff,#2d2f34><rowbgcolor=#00a495><rowcolor=#fff> S (2보다 왼쪽) || [math(\mathbb{P}(S))] ||
| [math(\{1\})] | [math(\frac{1}{6})] |
| [math(\{1,3\})] | [math(\frac{2}{6})] |
| [math(\emptyset)] | [math(\frac{2}{6})] |
| [math(\{3\})] | [math(\frac{1}{6})] |
이 확률 분포를 사용하여 섀플리 값을 계산하면 된다.
모든 플레이어의 섀플리 값을 더하면 언제나 grand coalition일 때의 payoff [math(v(N))]과 동일하다. 왜냐하면 telescoping에 의해
||<tablebgcolor=#fff,#2d2f34><rowbgcolor=#00a495><rowcolor=#fff> 나열 || 플레이어 1 추가 || 플레이어 2 추가 || 플레이어 3 추가 || 최종 합 ||
| 1 2 3 | [math(v(\{1\}) - v(\emptyset))] | [math(v(\{1,2\}) - v(\{1\}))] | [math(v(\{1,2,3\}) - v(\{1,2\}))] | [math(v(\{1,2,3\})] |
| 1 3 2 | [math(v(\{1\}) - v(\emptyset))] | [math(v(\{1,3\}) - v(\{1\}))] | [math(v(\{1,3,2\}) - v(\{1,3\}))] | [math(v(\{1,2,3\})] |
| 2 1 3 | [math(v(\{2\}) - v(\emptyset))] | [math(v(\{2,1\}) - v(\{2\}))] | [math(v(\{2,1,3\}) - v(\{2,1\}))] | [math(v(\{1,2,3\})] |
| 2 3 1 | [math(v(\{2\}) - v(\emptyset))] | [math(v(\{2,3\}) - v(\{2\}))] | [math(v(\{2,3,1\}) - v(\{2,3\}))] | [math(v(\{1,2,3\})] |
| 3 1 2 | [math(v(\{3\}) - v(\emptyset))] | [math(v(\{3,1\}) - v(\{3\}))] | [math(v(\{3,1,2\}) - v(\{3,1\}))] | [math(v(\{1,2,3\})] |
| 3 2 1 | [math(v(\{3\}) - v(\emptyset))] | [math(v(\{3,2\}) - v(\{3\}))] | [math(v(\{3,2,1\}) - v(\{3,2\}))] | [math(v(\{1,2,3\})] |
다만, 섀플리 값은 그저 "공정"한 분배일 뿐이기에, 진짜 저만큼만 이익을 준다고 하면 코어와는 달리 다른 파벌에 붙을 유인이 존재한다.
섀플리 값은 기계학습에서 각 feature가 예측 성능을 높이는데 얼마나 중요한지 나타내는 feature importance 계산할 때, 혹은 인공신경망에서 각 뉴런이 예측하는데 얼마나 중요한지 계산하는데 자주 사용된다.
3.3. 권력 지수 (Power Index)
* Banzhaf power index
* Penrose method
4. 여담
5. 관련 문서
[1] 좋게 말하면 협력이지만, 전략적인 목적을 달성하기 위해 임시로 서로 돕는 정도의 느낌일 뿐이다.[2] 보통은 연합하여 수익을 얻은 후 이를 어떻게 분배하겠다가 계약이 된다.[3] 만약 어떤 가상의 계약을 체결할 수 있어서 완전 공정하게 이익을 서로 배분할 수 있고 이를 어길 수 없다면.[4] 해당 파벌의 효용함수를 따로 worth function이라고 한다[5] 이를 worth function 혹은 (optimization 관점에서) value function이라고 한다.[6] 즉, 비교도 가능하고 모두 더하여 전체의 효용을 계산할 수도 있다.[7] 새로 파벌 [math(S)]를 만들려면 그 안에 있는 모든 사람이 동의해야하는데 나와가지고 얻는 total benefit이 줄어들면 비둘기집의 원리에 따라 누구 하나는 손해를 봐야하므로, 그 손해보는 사람이 파벌만드는 것을 거절할 것이다.[8] 마치 유능한 직원들 모두를 다 만족시키면서 회사 내에 붙잡기 힘든 것 처럼.