Shapley値

同義語:シャープレイ値Shapley value

概要

Shapley値(Shapley value)とは、提携形ゲーム $(N,v)$ の全体の価値 $v(N)$ を、プレイヤーが無作為な順に到着するときの限界貢献の期待値に従って分ける配分である。効率性・対称性・ダミー・加法性の 4 つの公理を満たす規則はこれただ 1 つである。部分集合の和の式や配当の和の式で計算でき、投票の力の指数、費用の分担、機械学習の予測の寄与の分解に使われる。凸ゲームではコアに属するが、一般のゲームではコアに入るとは限らない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: ゲーム理論, コア(ゲーム理論)

協力して得た価値を、貢献に応じてどう分けるか。3 人で組むと $9$、組み合わせごとの価値が分かっているとき、各人の取り分はいくらが「公平」か。Shapley 値(Shapley value)は、この問いに公理で答える。全員に配り切ること、同じ働きの者を同じに扱うこと、何も足さない者には配らないこと、2 つのゲームの取り分は足し算になること。この 4 つを満たす配分の規則はただ 1 つであり、しかも「プレイヤーが無作為な順に到着するときの限界貢献の期待値」という具体的な式で書ける。
同じ式は投票の力の指数として使われ、費用の分担や、機械学習の予測への寄与の分解にも使われている。ここでは一意性と存在の定理を証明し、配当による計算法、公理の独立性、コア(ゲーム理論) との関係、計算の手順と数値例を示す。

定義と使える条件

記号は コア(ゲーム理論) と同じにする。$N=\{1,\dots,n\}$ をプレイヤーの集合、$v\colon2^N\to\mathbb{R}$ を $v(\emptyset)=0$ となる関数とし、組 $(N,v)$ を提携形ゲームという。$N$ を固定したゲームの全体を $\mathcal{G}_N$ と書く。成分ごとの和とスカラー倍で $2^n-1$ 次元の実ベクトル空間である。

限界ベクトルと Shapley 値

プレイヤーの並べ方 $\pi=(\pi_1,\dots,\pi_n)$ に対し $P_k:=\{\pi_1,\dots,\pi_k\}$($P_0=\emptyset$)とし、
$$\varphi^{\pi}_{\pi_k}(v):=v(P_k)-v(P_{k-1})$$
で定まるベクトル $\varphi^{\pi}(v)\in\mathbb{R}^n$ を 限界ベクトル という。全 $n!$ 個の並べ方についての平均
$$\mathrm{Sh}(v):=\frac1{n!}\sum_{\pi}\varphi^{\pi}(v)$$
をゲーム $v$ の Shapley 値 という。

$\varphi^{\pi}_i(v)$ は、並べ方 $\pi$ で $i$ より前に来る者の集合 $S$ だけで決まり、$v(S\cup\{i\})-v(S)$ に等しい。与えられた $S\subset N\setminus\{i\}$ が $i$ の直前までの集合になる並べ方は $|S|!\,(n-|S|-1)!$ 個あるので
$$\mathrm{Sh}_i(v)=\sum_{S\subset N\setminus\{i\}}\frac{|S|!\,(n-|S|-1)!}{n!}\bigl(v(S\cup\{i\})-v(S)\bigr)\qquad(1)$$
であるKP17。

Shapley の公理

写像 $\psi\colon\mathcal{G}_N\to\mathbb{R}^n$(ゲームに配分を対応させる規則)に対し、次の 4 つの条件を考える。

  • 効率性:すべての $v$ で $\sum_{i\in N}\psi_i(v)=v(N)$。
  • 対称性:$i\ne j$ が、$i,j\notin S$ となるすべての $S$ で $v(S\cup\{i\})=v(S\cup\{j\})$ を満たすなら $\psi_i(v)=\psi_j(v)$。
  • ダミー:$i$ が、すべての $S$ で $v(S\cup\{i\})=v(S)$ を満たすなら $\psi_i(v)=0$。このような $i$ をダミー(プレイヤー)という。
  • 加法性:すべての $v,u$ で $\psi(v+u)=\psi(v)+\psi(u)$。

公理は $\mathcal{G}_N$ の全体で定義された規則についての条件である。1 つのゲームだけを見れば、効率性・対称性・ダミーを満たす配分はふつう無数にある。加法性が別のゲームとの関係を規定することで、はじめて値が決まる。
文献によっては上のダミーを null player と呼び、ダミーの語を $v(S\cup\{i\})=v(S)+v(\{i\})$ が常に成り立つ者に使う。その場合の条件は $\psi_i(v)=v(\{i\})$ である。式 (1) の右辺は $\sum_S\frac{|S|!(n-|S|-1)!}{n!}v(\{i\})=v(\{i\})$ となるので、Shapley 値はどちらの形も満たす。

公式の表

ゲーム $v$ の 配当(Harsanyi の配当)$c_S(v)$ を $c_S(v):=\sum_{T\subset S}(-1)^{|S|-|T|}v(T)$($S\ne\emptyset$)で定める。全員一致ゲーム $w_S$ を、$S\subset T$ のとき $w_S(T)=1$、それ以外で $w_S(T)=0$ として定める。

量式根拠条件
到着順の平均$\frac1{n!}\sum_\pi\varphi^{\pi}_i(v)$def-shv-value定義
部分集合の和式 (1)def-shv-value の直後$2^{n-1}$ 項
配当の和$\sum_{S\ni i}c_S(v)/\lvert S\rvert$thm-shv-mainすべての $v$
全員一致ゲーム$\mathrm{Sh}_i(cw_S)=c/\lvert S\rvert$($i\in S$)、$0$($i\notin S$)lem-shv-unanimity$c\in\mathbb{R}$
2 人$\mathrm{Sh}_1=v(\{1\})+\frac12\bigl(v(N)-v(\{1\})-v(\{2\})\bigr)$式 (1)$n=2$
多重線形拡張$\int_0^1\partial_if(t,\dots,t)\,dt$prop-shv-more$f=\sum_Sc_S\prod_{j\in S}x_j$
差の形$P(N)-P(N\setminus\{i\})$prop-shv-more$P(T)=\sum_{\emptyset\ne S\subset T}c_S/\lvert S\rvert$
滑走路のゲーム$\sum_{l\le i}\frac{c_l-c_{l-1}}{n-l+1}$ex-shv-airport$0=c_0\le c_1\le\dots\le c_n$

主定理と証明

全員一致ゲームの基底と配当
  1. $\{w_S\}_{\emptyset\ne S\subset N}$ は $\mathcal{G}_N$ の基底であり、$v=\sum_{S\ne\emptyset}c_S(v)\,w_S$ である。
  2. 効率性・対称性・ダミーを満たす $\psi$ は、$c\in\mathbb{R}$ について $\psi_i(cw_S)=c/|S|$($i\in S$)、$\psi_i(cw_S)=0$($i\notin S$)を満たす。
包除の計算と 3 つの公理
  1. 個数が $2^n-1=\dim\mathcal{G}_N$ なので、$v$ の表示を示せば基底であることも従う。$T\ne\emptyset$ について
    $$\sum_{\emptyset\ne S\subset T}c_S(v)=\sum_{R\subset T}v(R)\sum_{R\subset S\subset T}(-1)^{|S|-|R|}=v(T)$$
    である。内側の和は $(1-1)^{|T\setminus R|}$ で、$R=T$ のときだけ $1$ となる($R=\emptyset$ の項は $v(\emptyset)=0$ で消え、$S=\emptyset$ を含めても差は出ない)。左辺は $\bigl(\sum_Sc_S(v)w_S\bigr)(T)$ に等しい。
  2. $i\notin S$ なら $i$ は $cw_S$ のダミーなので $0$ である。$i,j\in S$ なら、$i,j\notin T$ で $cw_S(T\cup\{i\})=cw_S(T\cup\{j\})=0$ なので対称性より等しい。効率性から $S$ の $|S|$ 人の取り分の和は $cw_S(N)=c$ で、各人 $c/|S|$ となる。$c$ の符号は使っていない。$\square$
Shapley の定理

効率性・対称性・ダミー・加法性を満たす写像 $\psi\colon\mathcal{G}_N\to\mathbb{R}^n$ はただ 1 つ存在し、$\psi=\mathrm{Sh}$ である。さらに
$$\mathrm{Sh}_i(v)=\sum_{S\ni i}\frac{c_S(v)}{|S|}$$
である。

一意性は基底で、存在は到着順の平均で

一意性。 $\psi$ が 4 つの公理を満たすとする。lem-shv-unanimity (1) で $v$ を有限和 $\sum_Sc_S(v)w_S$ に書き、加法性と (2) を使うと
$$\psi_i(v)=\sum_{S\ne\emptyset}\psi_i\bigl(c_S(v)w_S\bigr)=\sum_{S\ni i}\frac{c_S(v)}{|S|}$$
となる。右辺は $v$ だけで決まる。
存在。 $\mathrm{Sh}$ が公理を満たすことを示す。各 $\pi$ について、和が畳み込まれるので $\sum_i\varphi^{\pi}_i(v)=v(N)$ で、平均しても効率性が成り立つ。$\varphi^{\pi}_i(v+u)=\varphi^{\pi}_i(v)+\varphi^{\pi}_i(u)$ から加法性が、ダミーの $i$ では $\varphi^{\pi}_i(v)=0$ からダミーの条件が従う。
対称性を示す。$i,j$ が対称とする。$\pi$ の $i,j$ の位置を入れ替えた並べ方を $\pi^*$ とする。$\pi$ で $i$ が $j$ より前なら、$i$ の前の集合 $T$ は $i,j$ を含まず、$\pi^*$ で $j$ の前の集合も $T$ なので
$$\varphi^{\pi}_i(v)=v(T\cup\{i\})-v(T)=v(T\cup\{j\})-v(T)=\varphi^{\pi^*}_j(v)$$
である。$\pi$ で $j$ が $i$ より前なら、$i,j$ を含まない $T$ で $i$ の前の集合が $T\cup\{j\}$、$\pi^*$ で $j$ の前の集合が $T\cup\{i\}$ と書けるので
$$\varphi^{\pi}_i(v)=v(T\cup\{i,j\})-v(T\cup\{j\})=v(T\cup\{i,j\})-v(T\cup\{i\})=\varphi^{\pi^*}_j(v)$$
である。$\pi\mapsto\pi^*$ は全単射なので、平均して $\mathrm{Sh}_i(v)=\mathrm{Sh}_j(v)$ を得る。$\square$

定理は ShapleySha53 による。上の組み立ては KP17 Theorem 12.3.5(pp. 208–209)に沿う。同書の Example 12.3.1 は $c\ge0$ の場合だけを述べているが、配当 $c_S(v)$ は負にもなるので、(2) は負の $c$ でも必要である。$c$ の符号によらないことは上の証明のとおりである。
4 つの公理はどれも外せない。各公理について、残りの 3 つを満たして $\mathrm{Sh}$ と異なる規則がある(ex-shv-independent)。
加法性は「限界貢献が同じなら取り分も同じ」という条件に取り替えることもできる。

Young の特徴づけ

$\psi\colon\mathcal{G}_N\to\mathbb{R}^n$ が効率性と対称性を満たし、さらに次の 限界性 を満たすとする:$i$ と $v,u$ について、$i\notin S$ となるすべての $S$ で $v(S\cup\{i\})-v(S)=u(S\cup\{i\})-u(S)$ なら $\psi_i(v)=\psi_i(u)$。このとき $\psi=\mathrm{Sh}$ である。

配当の個数についての帰納法

$\mathrm{Sh}$ が限界性を満たすことは式 (1) から分かる。配当が $0$ でない $S$ の個数 $m$ についての帰納法で $\psi(v)=\mathrm{Sh}(v)$ を示す。
$m=0$ なら $v=0$ で、全員が対称だから $\psi_i(v)$ はすべて等しく、効率性より $0$ である。
$m\ge1$ とし、$c_S(v)\ne0$ となる $S$ 全部の共通部分を $I$ とする。$i\notin I$ なら、$c_S(v)\ne0$、$i\notin S$ となる $S$ がある。$u:=v-c_S(v)w_S$ の配当の個数は $m-1$ である。$i\notin S$ なので $w_S(T\cup\{i\})=w_S(T)$ であり、$i$ の限界貢献は $v$ と $u$ で同じである。限界性と帰納法の仮定から $\psi_i(v)=\psi_i(u)=\mathrm{Sh}_i(u)=\mathrm{Sh}_i(v)$ となる。
$i\ne j$ が $I$ に属するとする。$T\not\ni i,j$ のとき、配当が $0$ でない $S$ はどれも $i,j$ の両方を含むので $T\cup\{i\}$ にも $T\cup\{j\}$ にも含まれない。よって $v(T\cup\{i\})=\sum_{S\subset T\cup\{i\}}c_S(v)=0=v(T\cup\{j\})$ で、$i,j$ は対称である。したがって $\psi$ も $\mathrm{Sh}$ も $I$ の上で定数である。効率性から $\sum_{i\in I}\psi_i(v)=v(N)-\sum_{i\notin I}\psi_i(v)$ が $\mathrm{Sh}$ の同じ和と等しいので、$I$ の上でも一致する。$\square$

定理は YoungYou85 による。ダミーの条件も加法性も仮定していない。

配当から分かること
  1. (多重線形拡張)$f(x):=\sum_{S\ne\emptyset}c_S(v)\prod_{j\in S}x_j$ とおくと $\mathrm{Sh}_i(v)=\int_0^1\partial_if(t,\dots,t)\,dt$ である。
  2. (差の形)$P(T):=\sum_{\emptyset\ne S\subset T}c_S(v)/|S|$ とおくと $\mathrm{Sh}_i(v)=P(N)-P(N\setminus\{i\})$ である。
  3. すべての $S$ で $c_S(v)\ge0$ なら $v$ は凸ゲームで、$\mathrm{Sh}(v)$ は直接の計算でコアに属する。
  4. $v$ が優加法的(交わらない $S,T$ で $v(S\cup T)\ge v(S)+v(T)$)なら $\mathrm{Sh}_i(v)\ge v(\{i\})$ である。
項ごとの計算
  1. $\partial_if(t,\dots,t)=\sum_{S\ni i}c_St^{|S|-1}$ で、積分は $\sum_{S\ni i}c_S/|S|$ である。
  2. $P(N)-P(N\setminus\{i\})$ に残るのは $i$ を含む $S$ の項である。
  3. $w_S$ は凸で($w_S(A)+w_S(B)\le w_S(A\cup B)+w_S(A\cap B)$ は、$A,B$ がともに $S$ を含むか否かで調べればよい)、非負結合も凸である。また $x:=\mathrm{Sh}(v)$ と $T\subset N$ について
    $$x(T)=\sum_{S}c_S\frac{|S\cap T|}{|S|}\ge\sum_{S\subset T}c_S=v(T)$$
    である。
  4. 優加法性から式 (1) の各項の差が $v(\{i\})$ 以上で、係数の和は $1$ である。$\square$

コアとの関係

コア(ゲーム理論) は「どの提携も抜け出す理由を持たない配分」の集合で、Shapley 値は 1 点を選ぶ規則である。両者は別の問いへの答えなので、一般には一致しない。凸ゲームでは、同記事の定理「凸ゲームのコアと限界ベクトル」により、すべての限界ベクトルがコアに属し、その平均である Shapley 値もコアに属する。ここで新しく必要な証明はない。
凸でないゲームでは、次の 3 通りのどれも起こる。

  • コアが空でないのに Shapley 値が入らない:ex-shv-glove の手袋市場。
  • コアが空なのに Shapley 値はある:ex-shv-stock の株主。Shapley 値は常に存在するので、配分の規則としては空のときにも使える。
  • 凸でないのに Shapley 値がコアに入る:ex-shv-counter の第 2 の例。凸性は十分条件であって必要条件ではない。

計算の手順

  1. すべての提携 $S$ について $v(S)$ を表にする($2^n-1$ 個)。
  2. $n$ が小さければ式 (1) で計算する。$v$ が少数の全員一致ゲームの和で書けるなら、配当の和の式の方が速い。
  3. 対称なプレイヤーをまとめる。対称なプレイヤーの取り分は等しいので、1 人ずつ計算する必要はなく、最後に効率性で検算する。
  4. 重み付き多数決 $[q;w_1,\dots,w_n]$($\sum_{i\in S}w_i\ge q$ で $v(S)=1$、$w_i,q$ は非負整数)では、$i$ を除く者について「大きさ $s$ で重みの和が $t$ の部分集合の個数」$a_{s,t}$ を動的計画法で求めれば、$\mathrm{Sh}_i=\sum_s\sum_{q-w_i\le t< q}a_{s,t}\frac{s!(n-s-1)!}{n!}$ となる。計算量は $n$ と重みの総和の多項式である。
  5. $n$ が大きければ並べ方を抽出する。独立に一様な並べ方 $\pi^{(1)},\dots,\pi^{(T)}$ を取り、$\widehat{\mathrm{Sh}}_i:=\frac1T\sum_t\varphi^{\pi^{(t)}}_i(v)$ とする。限界貢献が区間 $[a,b]$ に入るなら、Hoeffdingの不等式 より $P(|\widehat{\mathrm{Sh}}_i-\mathrm{Sh}_i|\ge\varepsilon)\le2\exp\bigl(-2T\varepsilon^2/(b-a)^2\bigr)$ である。推定量は不偏である。この方法の解析は Castro–Gómez–TejadaCGT09 にある。
    図: 左は重み 1,2,3,4、基準 6 の多数決での、重みの割合と Shapley 値の比較。重み 2 と 3 の者の Shapley 値が等しい。右は同じゲームで並べ方を抽出したときの誤差の平均を両対数で描いたもので、抽出数の平方根に反比例して減る 図: 左は重み 1,2,3,4、基準 6 の多数決での、重みの割合と Shapley 値の比較。重み 2 と 3 の者の Shapley 値が等しい。右は同じゲームで並べ方を抽出したときの誤差の平均を両対数で描いたもので、抽出数の平方根に反比例して減る

例題

3 人の数値例

$v(\{1\})=1$、$v(\{2\})=0$、$v(\{3\})=2$、$v(\{1,2\})=4$、$v(\{1,3\})=3$、$v(\{2,3\})=5$、$v(N)=9$ とする。

  • 使う公式:配当の和の式。
  • 答え:$0$ でない配当は $c_{\{1\}}=1$、$c_{\{3\}}=2$、$c_{\{1,2\}}=3$、$c_{\{2,3\}}=3$ で、$\mathrm{Sh}(v)=(\frac52,3,\frac72)$ である。
  • 代表点:$\frac52+3+\frac72=9=v(N)$。配当が非負なので prop-shv-more (3) よりコアに入る。たとえば $x(\{2,3\})=6.5\ge5$ である。
    配当の計算を開く

    $c_{\{1,2\}}=4-1-0=3$、$c_{\{1,3\}}=3-1-2=0$、$c_{\{2,3\}}=5-0-2=3$、$c_N=9-(4+3+5)+(1+0+2)=0$ である。$\mathrm{Sh}_1=1+\frac32=\frac52$、$\mathrm{Sh}_2=\frac32+\frac32=3$、$\mathrm{Sh}_3=2+\frac32=\frac72$ となる。

売り手と買い手(2 人)

売り手にとっての価値が $2$、買い手にとっての価値が $10$ の品物を考える。$v(\{1\})=2$、$v(\{2\})=0$、$v(N)=10$ とするKP17。

  • 使う公式:2 人の式。
  • 答え:$\mathrm{Sh}(v)=(6,4)$ で、余剰 $8$ を等分して単独の値に足した形である。
  • 代表点:売り手の取り分 $6$ は価格 $6$ に相当する。コアは $2\le x_1\le10$、$x_2=10-x_1$ の線分で、その中点が Shapley 値である。
手袋市場

プレイヤー $1$ が左の手袋を、$2,3$ が右の手袋を持ち、両手がそろう提携の価値を $1$ とする(コア(ゲーム理論) の例「手袋市場」と同じゲーム)。

  • 使う公式:配当の和の式。$v=w_{\{1,2\}}+w_{\{1,3\}}-w_{N}$ であるKP17。
  • 答え:$\mathrm{Sh}(v)=(\frac23,\frac16,\frac16)$ である。
  • 代表点:$\mathrm{Sh}_1=\frac12+\frac12-\frac13=\frac23$、$\mathrm{Sh}_2=\frac12-\frac13=\frac16$。提携 $\{1,2\}$ の取り分は $\frac56< 1$ で、コア $\{(1,0,0)\}$ には入らない。
4 人の株主と Shapley–Shubik 指数

持ち株 $1,2,3,4$、過半数 $6$ 株で可決のゲーム $[6;1,2,3,4]$ を考える。$v$ が単調($S\subset T$ なら $v(S)\le v(T)$)で $0,1$ の値を取るとき、$\mathrm{Sh}_i(v)$ は無作為な到着順で $i$ が負けの提携を勝ちに変える確率で、Shapley–Shubik の力の指数SS54 と呼ばれる。

  • 使う公式:$v=w_{\{2,4\}}+w_{\{3,4\}}+w_{\{1,2,3\}}-w_{\{2,3,4\}}-w_N$(KP17 Example 12.3.3)。
  • 答え:$\mathrm{Sh}(v)=(\frac1{12},\frac14,\frac14,\frac5{12})$ である。
  • 代表点:持ち株 $2$ と $3$ の者は株数が違うのに力が等しい。株数の割合 $(0.1,0.2,0.3,0.4)$ と力は一致しない。このゲームのコアは空である。
拒否権つきの委員会

15 人の委員会で、$1,\dots,5$ 番の全員を含み合計 $9$ 人以上の提携だけが勝つとする(国連安全保障理事会の表決の形)。

  • 使う公式:式 (1) と効率性。
  • 答え:拒否権のない 1 人の値は $\binom93\frac{8!\,6!}{15!}=\frac4{2145}\approx0.00186$、拒否権のある 1 人の値は $\frac{421}{2145}\approx0.19627$ である。
  • 代表点:拒否権のある者 1 人は、ない者 1 人の約 $105$ 倍の力を持つ。$5\cdot\frac{421}{2145}+10\cdot\frac4{2145}=1$ である。
    式の立て方を開く

    拒否権のない者 $i$ が勝ちに変えるのは、前の集合 $S$ が拒否権のある 5 人全員と、ない者のうち他の 9 人から選ばれた 3 人からなるときに限る。$|S|=8$ なので、係数は $\frac{8!\,6!}{15!}$、$S$ の個数は $\binom93=84$ である。残りは対称性と効率性で決まる。

滑走路のゲーム

機種 $1,\dots,n$ に必要な滑走路の費用が $0=c_0\le c_1\le\dots\le c_n$ で、提携は最も長い 1 本を作るとする。費用のゲーム $c(S):=\max_{i\in S}c_i$ の Shapley 値は
$$\mathrm{Sh}_i(c)=\sum_{l=1}^i\frac{c_l-c_{l-1}}{n-l+1}$$
である(Littlechild–OwenLO73)。

  • 使う公式:加法性とダミー・対称性・効率性。
  • 答え:$c=(2,5,9,10)$ で $\mathrm{Sh}(c)=(\frac12,\frac32,\frac72,\frac92)$ である。
  • 代表点:和は $10=c(N)$ である。$c=(1,2,3)$ では $(\frac13,\frac56,\frac{11}6)$ で、コア(ゲーム理論) の例「滑走路の費用分担」の費用の負担と一致する。
    公式の証明を開く

    $c=\sum_{l=1}^n(c_l-c_{l-1})u_l$ と分ける。ここで $u_l(S)$ は $S$ が $\{l,\dots,n\}$ と交わるとき $1$、それ以外で $0$ である。$u_l$ では $l$ 未満の者がダミーで、$l$ 以上の $n-l+1$ 人は対称だから、値は $1/(n-l+1)$ ずつである。加法性(と同じ論法のスカラー倍)で足せば式を得る。$\square$

使える条件と反例

外す条件反例(残りの公理は満たす)成り立たなくなること
効率性$\psi=2\,\mathrm{Sh}$thm-shv-main の一意性
対称性固定した $\pi$ の $\varphi^{\pi}$thm-shv-main の一意性
ダミー等分 $\psi_i(v)=v(N)/n$thm-shv-main の一意性
加法性ダミーでない者で等分する規則thm-shv-main の一意性
凸性手袋市場Shapley 値がコアに入ること
凸性(必要条件ではない)下の $0.6$ のゲーム「コアに入るなら凸」という逆
定義域が $\mathcal{G}_N$ の全体1 つのゲームだけの規則値の一意性
反例の確かめ

公理の独立性。 上の 4 行は ex-shv-independent で確かめる。
凸でなくコアに入る例。 $n=3$、$v(\{i\})=0$、$v(\{i,j\})=0.6$、$v(N)=1$ とする。$S=\{1,2\}$、$T=\{1,3\}$ で $v(S)+v(T)=1.2>1=v(N)+v(\{1\})$ なので凸でない。対称性から $\mathrm{Sh}(v)=(\frac13,\frac13,\frac13)$ であり、2 人の取り分は $\frac23\ge0.6$ なのでコアに入る。
定義域。 $n=2$ で $v(\{1\})=v(\{2\})=0$、$v(N)=1$ の 1 つのゲームだけを考えると、効率性・対称性・ダミーの条件からは $(\frac12,\frac12)$ に決まる。しかし $v(\{1\})=1$、$v(\{2\})=0$、$v(N)=2$ のゲームでは、誰も対称でもダミーでもないので、$x_1+x_2=2$ の点はどれも 3 つの条件を満たす。値を決めているのは、他のゲームとの加法性である。

公理の独立性

効率性だけを破る。 $\psi=2\,\mathrm{Sh}$ は対称性・ダミー・加法性を満たすが、和は $2v(N)$ である。
対称性だけを破る。 1 つ固定した $\pi$ の限界ベクトル $\varphi^{\pi}$ は効率性・ダミー・加法性を満たす。$n=2$、$v=w_N$ で $\pi=(1,2)$ とすると $\varphi^{\pi}=(0,1)$ で、対称な 2 人の値が違う。
ダミーだけを破る。 $\psi_i(v)=v(N)/n$ は効率性・対称性・加法性を満たす。$n=2$、$v=w_{\{1\}}$ では、ダミーの $2$ が $\frac12$ を受け取る。
加法性だけを破る。 ダミーでない者の集合を $D(v)$ とし、$D(v)\ne\emptyset$ なら $i\in D(v)$ に $v(N)/|D(v)|$、他に $0$ を配る。$D(v)=\emptyset$ なら $v=0$ なので全員 $0$ とする。効率性とダミーの条件は明らかである。$i,j$ が対称で $i$ がダミーなら $j$ もダミーである($T\not\ni i,j$ で $v(T\cup\{j\})=v(T\cup\{i\})=v(T)$、また $v(T\cup\{i,j\})=v(T\cup\{j\})=v(T\cup\{i\})$ から $T\cup\{i\}$ への $j$ の追加も値を変えない)ので、対称性も成り立つ。しかし $n=2$ で $v=w_{\{1\}}$、$u=w_N$ に対し $\psi(v)=(1,0)$、$\psi(u)=(\frac12,\frac12)$ で、$v+u$ はダミーがなく $(v+u)(N)=2$ より $\psi(v+u)=(1,1)$ となる。$\psi(v)+\psi(u)=(\frac32,\frac12)$ と異なる。

よくある誤り

誤り正しくは
投票の力は持ち株の割合に比例するex-shv-stock のように一致しない
Shapley 値は常にコアに入る凸ゲームなどに限る。手袋市場で外れる
式 (1) の係数は $1/2^{n-1}$$\lvert S\rvert!(n-\lvert S\rvert-1)!/n!$ である。一様な重みは Banzhaf 指数と呼ばれる別の量で、効率性を満たさない
個人の取り分 $v(\{i\})$ 以上がいつも保証される優加法的なときの性質である。一般には破れる
順序の平均だから順番が意味を持つ実際の到着順を仮定しているのではない。配分の式を与える計算上の見方である
費用のゲームでも不等号はそのままShapley 値の式はそのまま使えるが、コアの不等号は逆向きになる

補足

機械学習での使い方。 予測モデル $f$ の入力 $x$ について、$v(S):=E[f(z)\mid z_S=x_S]-E[f(z)]$ というゲームの Shapley 値を各特徴量の寄与とする方法を SHAP というLL17。効率性は「寄与の和が $f(x)-E[f(z)]$ に等しい」ことに当たる。特徴量の個数が多いと式 (1) の計算は重く、上の手順 5 のような近似を使う。ゲームの定め方(条件付き期待値か周辺の期待値か)で値が変わるので、公理の一意性は「ゲームを決めたあとの配分」についての主張である。
別の特徴づけ。 prop-shv-more (2) の $P$ はポテンシャルと呼ばれ、限界貢献を 1 つの関数の差として書く。公理の組は他にも知られており、thm-shv-young はその一例である。
他の解との比較。 Nash均衡 は非協力ゲームの解、コアは配分の集合、Shapley 値は配分の規則であって、どれも別の問いに答える。

関連項目

参考文献

[1]
Anna R. Karlin, Yuval Peres, Game Theory, Alive, American Mathematical Society, 2017, 著者公開版(2016 年 12 月 13 日)の番号:§12.3(pp. 206–210、Example 12.3.1、Lemma 12.3.2、Example 12.3.3、Theorem 12.3.5、Remark 12.3.6、Example 12.3.7)
[2]
L. S. Shapley, A value for n-person games, Contributions to the Theory of Games II (Annals of Mathematics Studies 28), 1953, pp. 307–317
[3]
L. S. Shapley, Martin Shubik, A method for evaluating the distribution of power in a committee system, American Political Science Review, 1954, pp. 787–792
[4]
H. P. Young, Monotonic solutions of cooperative games, International Journal of Game Theory, 1985, pp. 65–72
[5]
S. C. Littlechild, G. Owen, A simple expression for the Shapley value in a special case, Management Science, 1973, pp. 370–372
[6]
Javier Castro, Daniel Gómez, Juan Tejada, Polynomial calculation of the Shapley value based on sampling, Computers & Operations Research, 2009, pp. 1726–1730
[7]
Scott M. Lundberg, Su-In Lee, A unified approach to interpreting model predictions, Advances in Neural Information Processing Systems 30 (NIPS 2017), 2017, §3–§4、Theorem 1 と式 (8)、(9)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する