Shapley値(Shapley value)とは、提携形ゲーム $(N,v)$ の全体の価値 $v(N)$ を、プレイヤーが無作為な順に到着するときの限界貢献の期待値に従って分ける配分である。効率性・対称性・ダミー・加法性の 4 つの公理を満たす規則はこれただ 1 つである。部分集合の和の式や配当の和の式で計算でき、投票の力の指数、費用の分担、機械学習の予測の寄与の分解に使われる。凸ゲームではコアに属するが、一般のゲームではコアに入るとは限らない。
協力して得た価値を、貢献に応じてどう分けるか。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$ 次元の実ベクトル空間である。
プレイヤーの並べ方 $\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。
写像 $\psi\colon\mathcal{G}_N\to\mathbb{R}^n$(ゲームに配分を対応させる規則)に対し、次の 4 つの条件を考える。
公理は $\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$ |
効率性・対称性・ダミー・加法性を満たす写像 $\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)。
加法性は「限界貢献が同じなら取り分も同じ」という条件に取り替えることもできる。
$\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 による。ダミーの条件も加法性も仮定していない。
コア(ゲーム理論) は「どの提携も抜け出す理由を持たない配分」の集合で、Shapley 値は 1 点を選ぶ規則である。両者は別の問いへの答えなので、一般には一致しない。凸ゲームでは、同記事の定理「凸ゲームのコアと限界ベクトル」により、すべての限界ベクトルがコアに属し、その平均である Shapley 値もコアに属する。ここで新しく必要な証明はない。
凸でないゲームでは、次の 3 通りのどれも起こる。
図: 左は重み 1,2,3,4、基準 6 の多数決での、重みの割合と Shapley 値の比較。重み 2 と 3 の者の Shapley 値が等しい。右は同じゲームで並べ方を抽出したときの誤差の平均を両対数で描いたもので、抽出数の平方根に反比例して減る
$v(\{1\})=1$、$v(\{2\})=0$、$v(\{3\})=2$、$v(\{1,2\})=4$、$v(\{1,3\})=3$、$v(\{2,3\})=5$、$v(N)=9$ とする。
$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$、買い手にとっての価値が $10$ の品物を考える。$v(\{1\})=2$、$v(\{2\})=0$、$v(N)=10$ とするKP17。
プレイヤー $1$ が左の手袋を、$2,3$ が右の手袋を持ち、両手がそろう提携の価値を $1$ とする(コア(ゲーム理論) の例「手袋市場」と同じゲーム)。
持ち株 $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 と呼ばれる。
15 人の委員会で、$1,\dots,5$ 番の全員を含み合計 $9$ 人以上の提携だけが勝つとする(国連安全保障理事会の表決の形)。
拒否権のない者 $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=\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 値は配分の規則であって、どれも別の問いに答える。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する