Monotonic Solutions of Cooperative Games

---

이번 포스팅에서는 Shapley Value에 대한 Young의 논문 "Monotonic Solutions of Cooperative Games"을 읽고 정리해보았다.

---

   요약

1. Introduction

"단조성(Monotonicity)"는 문제의 데이터가 변하면 그 답도 비슷한 방식으로 변한다는 것으로 공정 배분의 일반적인 원리를 나타낸다. 

 

여기서는 협력 게임(Cooperative Game)을 위한 단조성 원리를 알아보고자 한다. 

 

2. Monotonicity

2.1 Cooperative Games

$n$명의 플레이어($\{1, 2, \ldots, n \}=N$)로 이루어진  협력 게임(Cooperative Game - CG) $v$는 $N$의 모든 부분 집합$S$에 대하여 실수값으로 정의된 $v(\phi) =0$을 만족하는 함수이다. 이때 $v(S)$를 $S$의 가치(Value)라 한다.

 

때때로 $v$에 대하여 다음을 가정한다.

$$v(S \cap T) \geq v(S)+v(T) \;\;\text{for all disjoint }\; S, T \subset N$$

같이 협력 했을 때 시너지 효과가 나는 성질이라고 보면 되겠다.

 

2.2 Allocation Procedure

Allocation Procedure(AP)는 $N$상에서 정의된 모든 CG $v$에 대하여 $n$명의 플레이어에게 $\sum_{i=1}^nx_i = v(N)$을 만족하는 할당 $(x_1, x_2, \ldots, x_n)$를 생성하는 함수 $\varphi$이다. 즉,

$$\varphi(v) = (x_1, x_2, \ldots, x_n) \;\; \text{with }\;\; \sum_{i=1}^nx_i=V(N)$$

이때 합 조건을 효율성(efficiency)라 한다. 

2.3 Aggregate Monotonicity

자주 보게되는 단조성 형태는 Aggregate Monotonicity(AM)이다. 이는 부분 연합의 가치를 고정시켜 놓고  전체 연합의 가치가 증가하면 각 플레이어의 할당량은 줄어들지 않는다는 것이다. 이를 수식으로 표현하면 다음과 같다.

 

$$v(N) \geq w(N), v(S) = w(S) \;\; \text{for all }\;\; S \subset N \\ \Rightarrow \varphi_i(v) \geq \varphi_i(w) \;\;\text{for all} \;\;i$$

2.4 Example of AP

평등 규칙(Egalitarian Rule)은 총 가치(전체 연합의 가치)($=v(N)$)를 플레이어게 평등하게 나누어 주는 할당을 말한다. 즉,

$$\varphi_i(v) = v(N)/|N|\;\; \forall i$$

평등 규칙은 AM을 만족하는 것을 쉽게 보일 수 있다.

$$v(N)\geq w(N) \Rightarrow v(N)/|N| \geq w(N)/|N|$$

 

다음으로 AM을 만족하는 것이 Shapley Value이며 그 정의는 다음과 같다.

$$\varphi_i(v) = \sum_{S : i \in S}\frac{(|S|-1)!|N-S|!}{|N|!}v^i(S)$$

여기서 $v^i(S)$는 다음과 같이 정의된다.

$$v^i(S) = \begin{cases} v(S)-v(S-i) & \;\;\text{if }\;\; i \in S \\ v(S+i)-v(S) & \;\;\text{if } \;\; i \notin S \end{cases}$$

Shapley Value 역시 AM을 만족한다. 먼저 AM 조건을 가정하자. 즉, 

$$v(N) \geq w(N), v(S) = w(S) \;\; \text{for all }\;\; S \subset N$$

을 가정하자는 것이다.

$$\begin{align} \varphi_i(v) - \varphi_i(w) &= \sum_{S : i \in S}\frac{(|S|-1)!|N-S|!}{|N|!}( v^i(S) - w^i(S)) \\ &= \frac{(|N|-1)!|0|!}{|N|!}(v^i(N)-w^i(N)) \geq 0 \end{align}$$

 

그렇다면 AM을 만족하지 않는 AP가 아닌 것들도 있을까?

있다~!!

Separable Costs Remaining Benefits(SCRB)와 Neclelous of Schmeidler AP는 AM을 만족하지 않는다고 한다.

2.5 Coalitional Monotonicity

AP $\varphi$가 다음을 만족할 때 $\varphi$는 Coalitional Monotonicity(CM) 성질을 만족한다고 한다.

$$v(T) \geq w(T) \;\;\text{for some} \;\; T, v(S) = w(S) \;\; \text{for all }\;\; S\neq T \\ \Rightarrow \varphi_i(v) \geq \varphi_i(w) \;\;\text{for all} \;\;i\in T$$

2.6 Strong Monotonicity and Symmetric AP

AP $\varphi$가 다음을 만족할 때 $\varphi$는 Strong Monotonicity(SM) 성질을 만족한다고 한다. 

$$v^i(S) \geq w^i(S) \;\;\text{for all} \;\; S \\ \Rightarrow \varphi_i(v) \geq \varphi_i(w) \;\;\text{for all} \;\;i$$

 

또한  AP $\varphi$가모든 $N$의 순열 $\pi$에 대하여 다음을 만족할 때 Symmetric 하다고 한다.

$$\varphi_{\pi i}(v) = \varphi_i(v), \;\;\text{ where }\;\; \pi v(S) = v(\pi S) \;\;\text{for all}\;\;S$$

 

정리 2. Shapley Value는 SM을 만족하는 유일한 Symmetric AP이다.

 

 

---