シャープレイ値

シャープレイ値（シャープレイち、Shapley value）とは、ゲーム理論において協力によって得られた利得を各プレイヤーへ公正に 分配する方法の一案である。1953年にこの値を導入したロイド・シャープレーを記念して命名された。

シャープレイ値が想定する状況

協力ゲームの理論では、プレイヤーが提携し、その提携によって獲得された報酬を分配するような状況を考える。 このときプレイヤー間で提携への貢献度が異なるとしたら、 どのように報酬を分配することが公正な分配であるといえるか、 各プレイヤーは作業全体に対してどれほど重要であり、 その重要度に応じた合理的な報酬を期待できるか、という問題が生じる。 シャープレイ値はこのような状況における公正な報酬計算方法の一つである。

形式的な定義

状況を定式化するために、特性関数型ゲームの概念を導入する。 プレイヤーの集合 $N$ および関数を $v \; : \; \mathcal{P}(N) \; \to \Re$ へ定義する。 こうしてプレイヤーの部分集合から実数への関数（特性関数という）は以下の性質をもつ。

1. $v(\varnothing) = 0$
2. $v(S\cup T) \ge v(S) + v(T)$

ここで$S$ と $T$ は $N$ の任意の非交の（交わりが空集合の）部分集合である。

関数 $v$ の性質は以下のとおりである。 もしも $S$ がプレイヤーの提携で、協力に合意している場合、$v(S)$ は その提携からの総報酬の期待値を示す。 このときの $v(S)$ の値は $S$ 以外のプレイヤーの行動とは独立に決まる。

不等式で示される第二の条件 $v$ の優加法性とは、 二つのグループ（単独でもよい）が協働することで 報酬の総和が増えることはあっても減ることはないという性質を表す。

プレイヤーのシャープレイ値

シャープレイ値は，全員が協働するとしたときに，総報酬をプレイヤーに分配する方法の一つである。 この分配は，以下に示す条件を満足する唯一の分配案であるという意味で「公正な」分配である。 プレイヤー $i$ は上記の定義に基づく特性関数 $v$ のもとで、

$\phi_i(v)=\sum_{S \subseteq N \setminus \{i\}} \frac{|S|!\; (n-|S|-1)!}{n!}(v(S\cup\{i\})-v(S))$

という配分を得る。 ここで、$n$ はプレイヤーの総数であり、 足し合わせの範囲は $N$ の部分集合 $S$ のうち プレイヤー $i$ を含まないものすべてである。 本式は、プレイヤーがひとりずつ提携に加わり、その寄与分 $v(S\cup\{i\}) - v(S)$ を公正な報酬として要求するときの プレイヤー $i$ の取り分を、 提携に参加する順序を変えたすべての順列について考え、平均したものである。

シャープレイベクトル

シャープレイベクトル (Shapley vector) は全プレーヤーのシャープレイ値を要素とするベクトルであり、

$\phi(v)=(\phi_1(v),\phi_2(v),...,\phi_n(v))$

と表される。

性質

シャープレイ値は以下のような好ましい性質を持つ。

1. 個人合理性: 個人合理性とは，全てのプレイヤーに1人で提携を作る時の利得$v(\{i\})$以上の利得を与える性質である。すなわち$N$の全てのプレイヤー $i$ に対して、

$\phi_i(v) \geqq v(\{i\})$

が成り立つ。

2. 全体合理性: $N$ 全体の提携値は各プレイヤーの利得の総和である。

$\sum_{i\in N}\phi_i(v) = v(N)$

3. 対称性: プレイヤー $i$ とプレイヤー $j$ 同様の意味を持つ、つまり、 $v(S\cup\{i\}) = v(S\cup\{j\})$ が $N$ の $i$ も $j$ も含まない全ての部分集合 $S$ に成り立つ場合、

$\phi_i (v) = \phi_j (v)$

である。

4. 加法性: 2つの特性関数 $v$ と $w$ によって作った提携ゲームの和 $v+w$ において，各プレイヤーの報酬はそれぞれの提携ゲームで得られる報酬の和と一致する。

$\phi_i(v+w) = \phi_i(v) + \phi_i(w)$

これが $N$ の全てのプレイヤーについてそれぞれ成り立つ。

5. ナルプレイヤーに関する性質: ナルプレイヤー i に対して報酬を与えない。 ここで、プレイヤー $i$ がナルプレイヤーであるとは、 $i$ が $N$ の $i$ を含まない全ての部分集合 $S$ について、 $v(S\cup \{i\}) = v(S)$ を満たすことを言う。

実際のところ,プレイヤー集合 $N$と 各提携に対する利得の値 $v(S)$ を決める特性関数が与えられたとき, シャープレイ値ベクトルは、全ての優加法的なゲーム(superadditive games)のクラスにおいて、上に挙げた特性2,3,4,5の4つの全ての特性を満たす唯一のベクトルである。

シャープレイ値の計算例

グローブゲーム

グローブゲーム(glove game)は、プレイヤーが左手用または右手用のグローブを持っていて、左手用と右手用のグローブのペアを作ろうとする提携ゲームである。 ここでは例としてプレイヤーを3人としてその集合$N$を次のように定める。

$N = \{1, 2, 3\}\,\!$

ここでプレイヤー1とプレイヤー2が右手のグローブを、プレイヤー3が左手のグローブを持っているとする。この提携ゲームの特性関数は以下のように書ける。

$v(S) = \begin{cases} 1, & \text{if }S \in \left\{ \{1,3\},\{2,3\},\{1,2,3\} \right\}\\ 0, & \text{otherwise}\\ \end{cases}$

ここで、シャープレイ値は以下のように計算できる。

$\phi_i(v)= \frac{1}{|N|!}\sum_R\left [ v(P_i^R \cup \left \{ i \right \}) - v(P_i^R) \right ]\,\!$

$R\,\!$とはプレイヤーの配列である。$P_i^R\,\!$ は、配列$R\,\!$でプレイヤー$i\,\!$の前に並んでいる$N\,\!$のプレイヤーの集合である。

ここで、下表にプレイヤー1が配列に参加することによる寄与分を示す。

配列 $R\,\!$	プレイヤー1の寄与分
${1,2,3}\,\!$	$v(\{1\}) - v(\varnothing) = 0 - 0 = 0\,\!$
${1,3,2}\,\!$	$v(\{1\}) - v(\varnothing) = 0 - 0 = 0\,\!$
${2,1,3}\,\!$	$v(\{1,2\}) - v(\{2\}) = 0 - 0 = 0\,\!$
${2,3,1}\,\!$	$v(\{1,2,3\}) - v(\{2,3\}) = 1 - 1 = 0\,\!$
${3,1,2}\,\!$	$v(\{1,3\}) - v(\{3\}) = 1 - 0 =1\,\!$
${3,2,1}\,\!$	$v(\{1,2,3\}) - v(\{2,3\}) = 1 - 1 = 0\,\!$

よって、

$\phi_1(v)=\frac{1}{3!} \cdot 1=\frac{1}{6}\,\!$

が得られる。対称性の議論によって、プレイヤー2はプレイヤー1と対称なプレイヤー(同様の寄与をもたらすプレイヤー)であるから、

$\phi_2(v)=\phi_1(v)=\frac{1}{6}\,\!$

である。シャープレイ値は全体合理性を満たし、全てのプレイヤーのシャープレイ値の総和は1になるので、

$\phi_3(v) =1-\phi_1(v)-\phi_2(v)= \frac{4}{6} = \frac{2}{3}\,$

が得られる。

関連項目

• 協力ゲーム
• シャープレイ＝シュービック投票力指数

参考文献

• Lloyd S. Shapley. A Value for n-person Games. In Contributions to the Theory of Games, volume II, by H.W. Kuhn and A.W. Tucker, editors. Annals of Mathematical Studies v. 28, pp. 307-317. Princeton University Press.
• Eric Rasmusen. Games & Information 3rd Edition, Blackwell Publishers, 2001.
• 鈴木光男 武藤滋夫 著,『協力ゲームの理論』,東京大学出版会
• 中山幹夫 他著,『協力ゲーム理論』,勁草書房
• 船木由喜彦 著,『エコノミックゲームセオリー』,サイエンス社

翻訳元

本記事はウィキペディア英語版記事

• Shapley value. Wikipedia: Free Encyclopedia. [1]

16:08, 27 October 2007 からの抄訳に基づいて作成された。

特性およびグローブゲームの項はウィキペディア英語版記事

• Shapley value. Wikipedia: Free Encyclopedia. [2]

15:49, 30 April 2011 からの抄訳に基づいて作成された。