シャープレイ値 （シャープレイち、英 : Shapley value ）とは、ゲーム理論において協力 によって得られた利得を各プレイヤー へ公正に[1] 1953年 にこの値を導入したロイド・シャープレー を記念して命名された。
シャープレイ値が想定する状況 [ 編集 ] 協力ゲームの理論では、プレイヤーが提携 し、その提携によって獲得された報酬を分配するような状況を考える。
このときプレイヤー間で提携への貢献度が異なるとしたら、
どのように報酬を分配することが公正な分配であるといえるか、
各プレイヤーは作業全体に対してどれほど重要であり、
その重要度に応じた合理的な報酬を期待できるか、という問題が生じる。
シャープレイ値はこのような状況における公正な報酬計算方法の一つである。
形式的な定義 [ 編集 ] 状況を定式化するために、特性関数型ゲーム の概念を導入する。
プレイヤーの集合
N
{\displaystyle N}
関数 を
v
:
P
(
N
)
→
ℜ
{\displaystyle v\;:\;{\mathcal {P}}(N)\;\to \Re }
部分集合 から実数 への関数（特性関数という）は以下の性質をもつ。
v
(
∅
)
=
0
{\displaystyle v(\varnothing )=0}
v
(
S
∪
T
)
≥
v
(
S
)
+
v
(
T
)
{\displaystyle v(S\cup T)\geq v(S)+v(T)}
ここで
S
{\displaystyle S}
T
{\displaystyle T}
N
{\displaystyle N}
空集合 の）部分集合である。
関数
v
{\displaystyle v}
S
{\displaystyle S}
v
(
S
)
{\displaystyle v(S)}
v
(
S
)
{\displaystyle v(S)}
S
{\displaystyle S}
不等式で示される第二の条件
v
{\displaystyle v}
優加法性 とは、
二つのグループ（単独でもよい）が協働することで
報酬の総和が増えることはあっても減ることはないという性質を表す。
プレイヤーのシャープレイ値 [ 編集 ] シャープレイ値は，全員が協働するとしたときに，総報酬をプレイヤーに分配する方法の一つである。
この分配は，以下に示す条件を満足する唯一の分配案であるという意味で「公正な」分配である。
プレイヤー
i
{\displaystyle i}
v
{\displaystyle v}
ϕ
i
(
v
)
=
∑
S
⊆
N
∖
{
i
}
|
S
|
!
(
n
−
|
S
|
−
1
)
!
n
!
(
v
(
S
∪
{
i
}
)
−
v
(
S
)
)
{\displaystyle \phi _{i}(v)=\sum _{S\subseteq N\setminus \{i\}}{\frac {|S|!\;(n-|S|-1)!}{n!}}(v(S\cup \{i\})-v(S))}
という配分 を得る。
ここで、
n
{\displaystyle n}
N
{\displaystyle N}
S
{\displaystyle S}
i
{\displaystyle i}
v
(
S
∪
{
i
}
)
−
v
(
S
)
{\displaystyle v(S\cup \{i\})-v(S)}
i
{\displaystyle i}
順列 について考え、平均したものである。
シャープレイベクトル [ 編集 ] シャープレイベクトル (Shapley vector) は全プレーヤーのシャープレイ値を要素とするベクトル であり、
ϕ
(
v
)
=
(
ϕ
1
(
v
)
,
ϕ
2
(
v
)
,
.
.
.
,
ϕ
n
(
v
)
)
{\displaystyle \phi (v)=(\phi _{1}(v),\phi _{2}(v),...,\phi _{n}(v))}
と表される。
シャープレイ値は以下のような好ましい性質を持つ。[2]
1. 個人合理性: 個人合理性 とは，全てのプレイヤーに1人で提携を作る時の利得
v
(
{
i
}
)
{\displaystyle v(\{i\})}
N
{\displaystyle N}
i
{\displaystyle i}
ϕ
i
(
v
)
≧
v
(
{
i
}
)
{\displaystyle \phi _{i}(v)\geqq v(\{i\})}
が成り立つ。
2. 全体合理性:
N
{\displaystyle N}
∑
i
∈
N
ϕ
i
(
v
)
=
v
(
N
)
{\displaystyle \sum _{i\in N}\phi _{i}(v)=v(N)}
3. 対称性: プレイヤー
i
{\displaystyle i}
j
{\displaystyle j}
v
(
S
∪
{
i
}
)
=
v
(
S
∪
{
j
}
)
{\displaystyle v(S\cup \{i\})=v(S\cup \{j\})}
N
{\displaystyle N}
i
{\displaystyle i}
j
{\displaystyle j}
S
{\displaystyle S}
ϕ
i
(
v
)
=
ϕ
j
(
v
)
{\displaystyle \phi _{i}(v)=\phi _{j}(v)}
である。
4. 加法性: 2つの特性関数
v
{\displaystyle v}
w
{\displaystyle w}
v
+
w
{\displaystyle v+w}
ϕ
i
(
v
+
w
)
=
ϕ
i
(
v
)
+
ϕ
i
(
w
)
{\displaystyle \phi _{i}(v+w)=\phi _{i}(v)+\phi _{i}(w)}
これが
N
{\displaystyle N}
5. ナルプレイヤーに関する性質: ナルプレイヤー i に対して報酬を与えない。
ここで、プレイヤー
i
{\displaystyle i}
i
{\displaystyle i}
N
{\displaystyle N}
i
{\displaystyle i}
S
{\displaystyle S}
v
(
S
∪
{
i
}
)
=
v
(
S
)
{\displaystyle v(S\cup \{i\})=v(S)}
実際のところ,プレイヤー集合
N
{\displaystyle N}
v
(
S
)
{\displaystyle v(S)}
シャープレイ値の計算例 [ 編集 ] グローブゲーム [ 編集 ] グローブゲーム(glove game)は、プレイヤーが左手用または右手用のグローブを持っていて、左手用と右手用のグローブのペアを作ろうとする提携ゲームである。
ここでは例としてプレイヤーを3人としてその集合
N
{\displaystyle N}
N
=
{
1
,
2
,
3
}
{\displaystyle N=\{1,2,3\}\,\!}
ここでプレイヤー1とプレイヤー2が右手のグローブを、プレイヤー3が左手のグローブを持っているとする。この提携ゲームの特性関数は以下のように書ける。
v
(
S
)
=
{
1
,
if
S
∈
{
{
1
,
3
}
,
{
2
,
3
}
,
{
1
,
2
,
3
}
}
0
,
otherwise
{\displaystyle v(S)={\begin{cases}1,&{\text{if }}S\in \left\{\{1,3\},\{2,3\},\{1,2,3\}\right\}\\0,&{\text{otherwise}}\\\end{cases}}}
ここで、シャープレイ値は以下のように計算できる。
ϕ
i
(
v
)
=
1
|
N
|
!
∑
R
[
v
(
P
i
R
∪
{
i
}
)
−
v
(
P
i
R
)
]
{\displaystyle \phi _{i}(v)={\frac {1}{|N|!}}\sum _{R}\left[v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})\right]\,\!}
R
{\displaystyle R\,\!}
P
i
R
{\displaystyle P_{i}^{R}\,\!}
R
{\displaystyle R\,\!}
i
{\displaystyle i\,\!}
N
{\displaystyle N\,\!}
ここで、下表にプレイヤー1が配列に参加することによる寄与分を示す。
配列
R
{\displaystyle R\,\!}
プレイヤー1の寄与分
1
,
2
,
3
{\displaystyle {1,2,3}\,\!}
v
(
{
1
}
)
−
v
(
∅
)
=
0
−
0
=
0
{\displaystyle v(\{1\})-v(\varnothing )=0-0=0\,\!}
1
,
3
,
2
{\displaystyle {1,3,2}\,\!}
v
(
{
1
}
)
−
v
(
∅
)
=
0
−
0
=
0
{\displaystyle v(\{1\})-v(\varnothing )=0-0=0\,\!}
2
,
1
,
3
{\displaystyle {2,1,3}\,\!}
v
(
{
1
,
2
}
)
−
v
(
{
2
}
)
=
0
−
0
=
0
{\displaystyle v(\{1,2\})-v(\{2\})=0-0=0\,\!}
2
,
3
,
1
{\displaystyle {2,3,1}\,\!}
v
(
{
1
,
2
,
3
}
)
−
v
(
{
2
,
3
}
)
=
1
−
1
=
0
{\displaystyle v(\{1,2,3\})-v(\{2,3\})=1-1=0\,\!}
3
,
1
,
2
{\displaystyle {3,1,2}\,\!}
v
(
{
1
,
3
}
)
−
v
(
{
3
}
)
=
1
−
0
=
1
{\displaystyle v(\{1,3\})-v(\{3\})=1-0=1\,\!}
3
,
2
,
1
{\displaystyle {3,2,1}\,\!}
v
(
{
1
,
2
,
3
}
)
−
v
(
{
2
,
3
}
)
=
1
−
1
=
0
{\displaystyle v(\{1,2,3\})-v(\{2,3\})=1-1=0\,\!}
よって、
ϕ
1
(
v
)
=
1
3
!
⋅
1
=
1
6
{\displaystyle \phi _{1}(v)={\frac {1}{3!}}\cdot 1={\frac {1}{6}}\,\!}
が得られる。対称性の議論によって、プレイヤー2はプレイヤー1と対称なプレイヤー(同様の寄与をもたらすプレイヤー)であるから、
ϕ
2
(
v
)
=
ϕ
1
(
v
)
=
1
6
{\displaystyle \phi _{2}(v)=\phi _{1}(v)={\frac {1}{6}}\,\!}
である。シャープレイ値は全体合理性を満たし、全てのプレイヤーのシャープレイ値の総和は1になるので、
ϕ
3
(
v
)
=
1
−
ϕ
1
(
v
)
−
ϕ
2
(
v
)
=
4
6
=
2
3
{\displaystyle \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. [:en] 16:08, 27 October 2007
からの抄訳に基づいて作成された。
特性およびグローブゲームの項はウィキペディア英語版記事
Shapley value. Wikipedia: Free Encyclopedia. [1] 15:49, 30 April 2011
からの抄訳に基づいて作成された。
![\phi _{i}(v)={\frac {1}{|N|!}}\sum _{R}\left[v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})\right]\,\!](https://wikimedia.org/api/rest_v1/media/math/render/svg/85e460793bcb11fd5e40d519f501f500bd704e38)
