1. 개요
Cooperative Game Theory or Coalitional Game Theory필요에 따라 다른 플레이어들과 협력(cooperation)을 할 수 있는[1] 게임을 연구하는 분야이다.
다른 말로, 플레이어들끼리 파벌(coalition)을 이룰 수 있다고 해서 Coalitional Game Theory라고도 한다.[2]
어떤 게임을 하기 전에 플레이어들끼리 자유롭게 대화하며 한번 사인하고 나면 나중에 강제적으로 지킬 수밖에 없는 계약(commitment)을 마음대로 할 수 있다고 가정한다.[3] 여기에서 포인트는 이 '계약'이라는 것이 한번 이루어지면 모두가 그 계약의 내용대로 행동할 것이 보장된다는 것이다. 이러한 보장이 없어서 나중에 어떤 플레이어가 계약을 어기게 된다면 이 계약은 아무런 의미가 없다. 이러한 영단어 commitment의 뉘앙스를 한국어로 살리기는 힘든데, 저서에 따라서는 '맹약'이라고 번역되기도 한다.
파벌이 실질적으로 특수 목적을 위해 만들어진 사람들의 모임인 만큼 정당 및 시민단체의 형성, 대선후보 단일화, 기업 인수합병, 직원들의 이직 등의 모델링에 쓰일 수 있으므로 특히 정치학이나 경제학에서 중요하다.
2. 내용
죄수의 딜레마 게임을 기억해보면 다음과 같은 Payoff로 표현 가능하다.| 상대의 협력 | 상대의 배신 | |
| 나의 협력 | 2, 2 | 0, 3 |
| 나의 배신 | 3, 0 | 1, 1 |
위의 숫자는 해당 행동을 했을 때 (나, 상대)의 대략적 이득을 가장 간단한 숫자로 표현한 것이다.
당연히 내시 균형은 서로 (배신, 배신)을 하는 것이다.
하지만 여기서 두 사람이 게임을 하기전에 자유롭게 대화하고 나중에 뒷통수 치거나 합의를 함부로 깨지 못하게 계약을 체결 할 수 있다면 두 사람이 협력하여 (2, 2)를 얻는 것이 서로 협력하지 않아서 배신하여 같이 손해보는 것보다 무조건 이득일 것이다.
이렇게 두 사람이 협력하여 한 집단이 되는 것을 coalition이라 한다.
이 coalition은 한 사람처럼 행동할 수도, 구성원 간의 갈등으로 와해될 수도 있지만 coalition의 모든 멤버들이 집단 밖으로 나오는 것보다 집단에 있어서 분배받는 것이 더 좋다면 파벌은 한 몸처럼 매우 효율적으로 행동하는 것으로[4] 가정할 수 있다. 그럼 2인 죄수의 딜레마 게임은 1인 2차원 행동 최적화 문제로 collapse 될 수 있다. 이와 비슷하게 3인 이상의 멀티플레이어 게임에 대해서도 각 파벌 조합에 대해 파벌을 유지하는 것이 가능한지, 만약 유지된다면 해당 파벌은 어떤 행동을 할지 원래 게임을 다음과 같이 쪼개서 생각할 수 있다.
- 파벌자체를 하나의 플레이어로 생각한 비협조적 게임 (non-cooperative game)
- 한 파벌 안에서 멤버끼리 이득을 분배하는 Subgame인 협상 게임 (bargaining game)
1950년대 이후로 주요한 접근 방식은[5] , 파벌이 일단 구성되었을 때 이는 결국 non-cooperative game으로 collapse할 수 있는데, 수학적 편의상, 그 비협조적 게임의 equilibrium이 unique하게 well-defined되었다고 가정한다.[6]
결국 파벌이 일단 구성되었다몀 equilibrium의 행동밖에 하지 않을 것이므로 파벌의 action은 고려하지 않아도 되고 그저 최종 action과 그에 따른 payoff만 주어진다고 생각할 수 있거.[7] 그리고 이 파벌이 구성되었을 때 받는 payoff 함수가 주어졌을 때 어떻게 게임의 균형이 나타날 것인가를 연구하는 것이 협력적 게임 이론의 기본적은 접근 방법이다.
이론적 간편함을 위해 (for simplicity), 효용은 돈처럼 주거나 받거나가 가능하다고 가정한다 (transferrable utility).[8]
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 혼자 보물 상자를 다 가지는 것이다. 즉 payoff가 (0, 0, 1)이 되도록 하는 것.
왜냐하면, 만약 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이 줄어들거나 같아서 새로 파벌을 만들 수 없다.[9]"
"대연합에 들어와 [math(\mathbf{v}^*)]에 해당하는 만큼 돈을 받고 있다면, 대연합에서 나와 새로 파벌 [math(S)]을 새로 만들려 해도, 가만히 있는 것보다 무조건 파벌 S가 얻는 total benefit이 줄어들거나 같아서 새로 파벌을 만들 수 없다.[9]"
을 만족하는 가능한 [math(\mathbf{v}^*)]의 집합이 core이다.
위의 보물상자 예시에서 대연합은 1,2,3 모두가 연합하는 것이고, 코어 분배 [math(\mathbf{v}^*)]는 (0,0,1)이다. 이 상태에서 어느 누구라도 따로 나와서 파벌을 만들려고 해도 지금 상태보다 나아지는 경우의 수가 존재하지 않는다.[10]
다만 core가 없는 경우도 있는데, 다음과 같은 게임에서는 core가 없다.
짝짓기 게임
3명이 플레이하는데, 2명 이상 팀을 만들어 오면 보물을 준다.
즉, 이미 2명이 짝 지어져 각각 얼마만큼 배분할지 정해졌을 때, 다른 한 사람이 (물론 그 사람은 지금 아무것도 못 얻고 있다) 둘 중 한명에게 다가가 "만약 나랑 팀하면, 너가 지금 받는 것보다 더 많이 줄게"하면 무조건 옮기게 되어 있다. 그런데 이는 offer를 받지 못하고 남는 사람도 똑같이 할 수 있으므로 이게 계속 반복이 되어 경쟁 게임에서의 best response가
사이클 도는 것처럼 되어 균형이 존재하지 않는다.3명이 플레이하는데, 2명 이상 팀을 만들어 오면 보물을 준다.
이처럼 문제가 조금만 복잡해져도 파벌안에 있는 모든 사람이 다른 파벌로 갈 요인을 아예 없애게 하는게 은근 어려워서 core가 존재하지 않는 경우가 굉장히 많다. 그 이유는 core의 정의가 옮기는 사람만 대우를 잘해주면 되는게 아니라, 기존에 있던 사람들도 다 안 나가게 잘해줘야하기 때문이다.[11]
3.1.1. Bondareva–Shapley theorem
코어가 존재하기 위한 필요충분 조건을 찾은 정리이다.Balanced Game이면 core를 갖고, core를 가졌으면 balanced game이다. 이는 linear programming의 duality로부터 바로 나온다. 참조
Convex Game이면 core를 갖지만, core를 가졌다고 convex game인 것은 아니다.
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 | [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\})] |
다만, 섀플리 값은 그저 "공정"한 분배일 뿐이기에, 진짜 저만큼만 이익을 준다고 하면 코어와는 달리 다른 파벌에 붙을 유인이 존재한다. 위의 보물상자 열기 예에서 섀플리 분배는 (1/6, 1/6, 4/6)으로 플레이어 1과 2 둘 중 하나가 플레이어 3하고만 파벌 따로 만들어 나올 유인이 존재한다. 이러한 점에서 정의론 혹은 전략적 선택까지 고려한 진짜 "공정"한 분배라기엔 애매하고, 그냥 수학적으로 유용한 공리적 성질들 (linearity, symmetry, efficiency) 등을 만족하는 수학적 해 + 직관적으로도 각 파벌에 추가되었을 때 추가되는 additional utility의 평균이라는 직관과 합치되는 간단하면서도 굉장히 유용한 척도 정도로 생각할 수 있다.
하지만 Convex 게임이면 섀플리 값은 core의 convex combination이기에 역시 core solution이다. 물론 위의 보물상자 게임은 convex game이 아니다.
증명과 관련해서, 참고로 efficiency는 모델 구조상 대연합 형성을 가정한 상태로 논리를 전개한 것이므로 사실상 normalization이나 다름 없는 것이고, symmetry 역시, 이상한 배분 방식(완전 동등한 대상인데도 불구하고 다른 배분을 해주는 것)이 아닌 이상에야 여간하면 만족되는 성질. 메인은 분배가 오직 worth function에만 depend한다는 가정 + linearity에만 있다고 봐도 무방한데, 이것이 worth function이 실질적으로 다른 파벌에 depend 되지 않아서 암묵적 independence를 가정해서 발생한다. 증명을 보면 알겠지만 linearity + worth function dependency 덕에 allocation vector [math(\mathbf{\phi} \in \mathbb{R}^n)]는 worth vector [math(\mathbf{v} \in \mathbb{R}^{2^n})]의 linear function이기에 [math(\mathbf{\phi} = \mathbf{A}\mathbf{v})]가 성립하는데, 여기서 [math(n\times 2^n)] 차원 행렬 [math(\mathbf{A})]는 symmetry에 의해 각 row는 coalition size에만 depend하고, dummy player의 allocation은 0으로 두는 조건을 추가하면, [math(v(S \cup \{i\}) - v(S))]로 묶이게 된다. 마지막으로 coefficient는 allocation의 sum이 grand coaliated allocation을 만족한다는 조건 [math(\mathbf{\phi}^\top \mathbf{1} = v(N))]에 의해 자유 변수인 [math(\mathbf{v})]의 자유도를 주기위해 무조건 [math(\mathbf{A})]는 [math(|S|!(n-|S|-1)!/n!)]을 만족할 수 밖에 없다. 참고
섀플리 값은 기계학습에서 각 feature가 예측 성능을 높이는데 얼마나 중요한지 나타내는 feature importance 계산할 때, 혹은 인공신경망에서 각 뉴런이 예측하는데 얼마나 중요한지 계산하는데 자주 사용된다.
3.3. 권력 지수 (Power Index)
* Banzhaf power index
* Penrose method
4. 한계점
위에도 써놨지만 대부분의 협력 게임 이론은 플레이어 액션들을 축약해놓는 worth function만 가지고 이론을 전개한다. 하지만 이는 본질적으로 coalition의 payoff가 coalition 밖의 플레이어와 아무상관 없다는 것을 가정하므로 실제 경제 혹은 정치 모델에 사용할 때 치명적인 문제가 된다. 참조이를 고려한 게임을 partition function game 이라 한다
5. 여담
6. 관련 문서
[1]
좋게 말하면 협력이지만, 전략적인 목적을 달성하기 위해 임시로 서로 돕는 정도의 느낌일 뿐이다.
[2]
여기서 일반적으로 많이 쓰이는 연합(Alliance)가 아니라 파벌이라고 번역한 이유는 연합은 좀 더 장기적이고 지속적인 끈끈한 결합이라는 뉘앙스가 있지만 파벌에는 전략적이고 임시적 동맹 느낌이 강하기에 게임이론의 맥락 상 후자가 더 적합하다고 생각해서이다. 다만 섀플리 값의 수학적 이론 전개에서는 일단 파벌이 형성되고 나면, 해체되지 않고, 다른 파벌을 공격하거나 해체시켜러는 상황을 고려하지 않으므로 그 때에는 연합이 맥락상 더 어울릴 수도 있다.
[3]
보통은 연합하여 수익을 얻은 후 이를 어떻게 분배하겠다가 계약이 된다.
[4]
해당 파벌의 효용함수를 따로 worth function이라고 한다
[5]
Shapley 등
[6]
물론 mixed strategy를 allow할 경우 Nash equilibrium이 존재는 하지만 그게 여러개일 수도 있다. 하지만 그거까지 고려하면 너무 복잡해지므로 일단 하나만 딱 있다고 가정한다.
[7]
이를 worth function 혹은 (optimization 관점에서) value function이라고 한다. 이는 superadditive한
내측도로 주어진다.
[8]
즉, 비교도 가능하고 모두 더하여 전체의 효용을 계산할 수도 있다.
[9]
새로 파벌 [math(S)]를 만들려면 그 안에 있는 모든 사람이 동의해야하는데 나와가지고 얻는 total benefit이 줄어들면 비둘기집의 원리에 따라 누구 하나는 손해를 봐야하므로, 그 손해보는 사람이 파벌만드는 것을 거절할 것이다.
[10]
플레이어 1과 플레이어 2는 같이 나와봤자 어차피 보물상자 못 열어서 얻는 이득은 0이고, 플레이어 3도 마찬가지로 1이나 2나 누구랑 같이 나와도 얻는 이득은 변함이 없다.
[11]
마치 유능한 직원들 모두를 다 만족시키면서 회사 내에 붙잡기 힘든 것 처럼.