コア(ゲーム理論)

同義語:core (game theory)

概要

コア(ゲーム理論)(core)とは、提携形ゲーム $(N,v)$ で、全体の価値 $v(N)$ を分ける配分 $x$ のうち、すべての提携 $S$ が $x(S)\ge v(S)$ を満たすものの全体である。どの提携も抜け出す理由を持たない配分の集合で、有限個の 1 次不等式の定める多面体である。コアが空でないことは、すべての均衡な重みで $\sum_S\lambda_Sv(S)\le v(N)$ となることと同値である(Bondareva–Shapley の定理)。優モジュラな凸ゲームではコアは限界ベクトルの凸包で、Shapley 値を含むが、多数決のように空になるゲームもある。

$$\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}} $$

前提知識: 線形計画法, ゲーム理論

協力ゲームのコア(core)は、全員で得た価値の分け方のうち、どの提携も「自分たちだけで組んだ方が得だ」と抜け出す理由を持たないものの全体である。有限個の 1 次不等式で定まる多面体なので、空かどうかは線形計画の問題になる。空でないための必要十分条件が Bondareva–Shapley の定理で、線形計画の双対から直接証明できる。多数決のように空になるゲームがある一方、凸ゲームでは空にならず、頂点が加入順の限界貢献で与えられ、Shapley値もコアに入る。ここではこれらを証明し、割当ゲームなどの計算例を示す。

定義と使える条件

提携形ゲームとコア

$N=\{1,\dots,n\}$ をプレイヤーの集合、$v\colon2^N\to\mathbb{R}$ を $v(\emptyset)=0$ となる関数とする。組 $(N,v)$ を 提携形ゲーム、$S\subset N$ を 提携、$v(S)$ を提携 $S$ が自力で得られる価値という。$x\in\mathbb{R}^n$ と $S\subset N$ に対し $x(S):=\sum_{i\in S}x_i$ とする。$x$ が

  • 効率性:$x(N)=v(N)$
  • 提携合理性:すべての $S\subset N$ で $x(S)\ge v(S)$
    を満たすとき、$x$ はコアに属するという。その全体をコアといい、$C(v)$ と書く。

$x(S)< v(S)$ となる提携 $S$ があれば、$S$ は全員の配分を拒んで自分たちだけで組み、余りを分けて全員が得をする。コアはそのような拒否の起きない配分の集合である。KP17 は $v$ の単調性を仮定して話を進めるが、以下の結果に単調性は要らない。

均衡な重み

$N$ の空でない部分集合 $S$ で添字付けた $\lambda=(\lambda_S)$ で、$\lambda_S\ge0$ かつ、すべての $i\in N$ について
$$\sum_{S\ni i}\lambda_S=1$$
となるものを 均衡な重み という。各プレイヤーが持ち時間 $1$ を提携に配分し、提携 $S$ の全員が時間 $\lambda_S$ を出すと見れば、$\sum_S\lambda_Sv(S)$ は提携を時間で混ぜて得られる価値である。$N$ の分割は重みが $0,1$ の均衡な重みである。

限界ベクトル、Shapley 値、凸ゲーム

プレイヤーの並べ方 $\pi=(\pi_1,\dots,\pi_n)$ に対し $P_k:=\{\pi_1,\dots,\pi_k\}$($P_0=\emptyset$)とし、
$$\varphi^{\pi}_{\pi_k}:=v(P_k)-v(P_{k-1})$$
で定まるベクトル $\varphi^{\pi}$ を 限界ベクトル という。全 $n!$ 個の並べ方についての平均を Shapley 値 というKP17。すべての $S,T\subset N$ で
$$v(S)+v(T)\le v(S\cup T)+v(S\cap T)$$
が成り立つゲームを 凸ゲーム という。

公式の表

量式根拠条件
コアが空でない条件均衡な $\lambda$ すべてで $\sum_S\lambda_Sv(S)\le v(N)$thm-core-bondareva-shapley有限ゲーム
被覆の値$\min\{x(N):x(S)\ge v(S)\}=\max_{\lambda}\sum_S\lambda_Sv(S)$cor-core-duality有限ゲーム
3 人の判定$v(N)\ge v_1+v_2+v_3$、$v(N)\ge v_{ij}+v_k$、$v(N)\ge\frac12(v_{12}+v_{13}+v_{23})$cor-core-three$n=3$、$v_i:=v(\{i\})$、$v_{ij}:=v(\{i,j\})$
単純ゲームコアは拒否権者の $e_i$ の凸包prop-core-simple$v\in\{0,1\}$、$v(N)=1$
凸ゲーム$C(v)=\mathrm{conv}\{\varphi^{\pi}\}$thm-core-convex凸
Shapley 値$\frac1{n!}\sum_{\pi}\varphi^{\pi}\in C(v)$thm-core-convex凸
割当ゲーム成分が $0$ 以上の最適双対解 $(a,b)\in C(v)$prop-core-assignment$w_{ij}\ge0$

主定理と証明

Bondareva–Shapley の定理

提携形ゲーム $(N,v)$ のコアが空でないことと、すべての均衡な重み $\lambda$ で
$$\sum_{\emptyset\ne S\subset N}\lambda_Sv(S)\le v(N)$$
となることは同値である。

択一定理を当てる

必要性。 $x\in C(v)$ と均衡な $\lambda$ に対し
$$\sum_S\lambda_Sv(S)\le\sum_S\lambda_Sx(S)=\sum_ix_i\sum_{S\ni i}\lambda_S=x(N)=v(N)$$
である。
十分性。 コアが空とする。コアの条件は、未知数 $x$ についての 1 次不等式系
$$-x(S)\le-v(S)\quad(\emptyset\ne S\subset N),\qquad x(N)\le v(N)$$
と同じである($S=N$ の不等式と合わせて等式になる)。解がないから、線形計画法 の定理「1 次不等式系の択一定理」より、$y_S\ge0$ と $y_0\ge0$ があって
$$-\sum_{S\ni i}y_S+y_0=0\quad(i\in N),\qquad-\sum_Sy_Sv(S)+y_0v(N)< 0$$
となる。$y_0=0$ なら 1 つ目の式からすべての $y_S=0$ となり、2 つ目の式に反する。よって $y_0>0$ で、$\lambda_S:=y_S/y_0$ は均衡な重みであり、$\sum_S\lambda_Sv(S)>v(N)$ を満たす。$\square$

定理は Bondareva と ShapleySha67 にさかのぼる。重みを分割に限った条件は「全体を分割しても得をしない」というもので、優加法性(交わらない $S,T$ で $v(S\cup T)\ge v(S)+v(T)$)から従う。コアが空でないためにはそれでは足りず、重なりのある提携の混ぜ方も考える必要がある。

被覆の値と双対

次の 2 つの線形計画の値は等しい。
$$\min\{x(N):x(S)\ge v(S)\ (\emptyset\ne S\subset N)\}=\max\Bigl\{\sum_S\lambda_Sv(S):\lambda\ \text{は均衡な重み}\Bigr\}$$
右辺は $\lambda_N=1$ を取れば $v(N)$ 以上である。コアが空でないことは、この共通の値が $v(N)$ に等しいことと同値である。

双対定理の形に揃える

$M$ を $(i,S)$ 成分が $i\in S$ のとき $1$、それ以外で $0$ の行列とする。右辺は $\max\{v\cdot\lambda:M\lambda\le\mathbf{1},\ -M\lambda\le-\mathbf{1},\ \lambda\ge0\}$ で、線形計画法 の定義「双対問題」による双対は $\min\{\mathbf{1}\cdot(p-q):M^{\top}(p-q)\ge v,\ p,q\ge0\}$ である。$x:=p-q$ とおくと左辺になる。$\lambda$ は $\lambda_{\{i\}}=1$ で実行可能、$x$ は成分を大きく取れば実行可能だから、定理「線形計画法の双対定理」より値は等しい。$x(S)\ge v(S)$ を満たす $x$ で $x(N)=v(N)$ となるものはコアの点そのものなので、後半を得る。$\square$

3 人のゲームの判定式

$n=3$ のとき、均衡な重みの多面体の頂点は次の 6 個である:$\{N\}$;$\{1\},\{2\},\{3\}$;$\{i,j\},\{k\}$(3 通り);$\{1,2\},\{1,3\},\{2,3\}$ に各 $\frac12$。したがってコアが空でないことは
$$v(N)\ge v(\{1\})+v(\{2\})+v(\{3\}),\quad v(N)\ge v(\{i,j\})+v(\{k\}),\quad v(N)\ge\frac12\bigl(v(\{1,2\})+v(\{1,3\})+v(\{2,3\})\bigr)$$
($N$ 自身の式は自明)と同値である。

頂点を調べる

均衡な重みは $0\le\lambda_S\le1$ を満たすので多面体は有界で、線形の目的関数の最大は頂点で達成される(線形計画法 の定理「最適解は頂点でとれる」と同じ理由)。頂点は 3 本の等式の基底解なので、$\{1,2\},\{1,3\},\{2,3\},\{1\},\{2\},\{3\},N$ の 7 個の提携から 3 個を選んで解を調べると上の 6 個になる。$\square$

単純ゲームのコアと拒否権者

$v(S)\in\{0,1\}$、$v(N)=1$ とする。すべての $v(S)=1$ の提携に属するプレイヤーを 拒否権者 という。コアは拒否権者の $e_i$ の凸包に等しい。特にコアが空でないことと拒否権者がいることは同値である。

勝つ提携の外には配れない

$x\in C(v)$ なら $x_i\ge v(\{i\})\ge0$ である。$v(S)=1$ なら $x(S)\ge1=x(N)$ より $S$ の外で $x_i=0$ となる。よって $x$ の台は拒否権者の集合に含まれ、$x$ は $e_i$ の凸結合である。逆に拒否権者の $e_i$ の凸結合 $x$ は、$v(S)=1$ なら $x(S)=1$、$v(S)=0$ なら $x(S)\ge0$ でコアに属する。$\square$

次は、凸ゲームのコアが完全に記述できるという定理である。

凸ゲームのコアと限界ベクトル

提携形ゲーム $(N,v)$ について、$v$ が凸であることと、すべての限界ベクトルがコアに属することは同値である。このとき
$$C(v)=\mathrm{conv}\{\varphi^{\pi}:\pi\text{ は並べ方}\}$$
であり、Shapley 値はコアに属する。

差分の比較と貪欲法

$\varphi^{\pi}(P_k)=v(P_k)$ は和が畳み込まれることから分かる。特に効率性は常に成り立つ。
凸なら限界ベクトルはコアに属する。 空でない $S$ の要素を $\pi$ の順に $s_1,\dots,s_m$ と並べ、$S_l:=\{s_1,\dots,s_l\}$ とする。$s_l=\pi_k$ のとき、凸性を $S_l$ と $P_{k-1}$ に当てる。$S_l\cup P_{k-1}=P_k$、$S_l\cap P_{k-1}=S_{l-1}$ だから
$$\varphi^{\pi}_{s_l}=v(P_k)-v(P_{k-1})\ge v(S_l)-v(S_{l-1})$$
である。$l$ で足して $\varphi^{\pi}(S)\ge v(S)$ を得る。
限界ベクトルがコアに属すれば凸である。 $S,T$ に対し、$S\cap T$、$S\setminus T$、$T\setminus S$、残りの順に並ぶ $\pi$ を取り、$x:=\varphi^{\pi}$ とする。$x(S\cap T)=v(S\cap T)$、$x(S)=v(S)$、$x(S\cup T)=v(S\cup T)$ であり、$x\in C(v)$ から
$$v(T)\le x(T)=x(S\cup T)-x(S)+x(S\cap T)=v(S\cup T)-v(S)+v(S\cap T)$$
である。
頂点の記述。 $C(v)$ は凸で限界ベクトルを含むから、$\mathrm{conv}\{\varphi^{\pi}\}\subset C(v)$ である。$y\in C(v)$ と $c\in\mathbb{R}^n$ を任意に取る。$c_{\pi_1}\ge\dots\ge c_{\pi_n}$ となる $\pi$ を選ぶと、Abel 変形により
$$c\cdot y=\sum_{k< n}(c_{\pi_k}-c_{\pi_{k+1}})y(P_k)+c_{\pi_n}y(N)\ge\sum_{k< n}(c_{\pi_k}-c_{\pi_{k+1}})v(P_k)+c_{\pi_n}v(N)=c\cdot\varphi^{\pi}$$
である。$y\notin\mathrm{conv}\{\varphi^{\pi}\}$ なら、有限個の点の凸包と点を分離する $c$ で $c\cdot y< \min_{\pi}c\cdot\varphi^{\pi}$ となるものがあり、矛盾する。Shapley 値は限界ベクトルの平均だから凸包に入る。$\square$

前半と頂点の記述は ShapleySha71、逆向きは IchiishiIch81 による。

割当ゲームのコア

買い手 $1,\dots,m$ と売り手 $1,\dots,m$、取引の価値 $w_{ij}\ge0$ に対し、$v(S)$ を $S$ の中の買い手と売り手のマッチングの重みの最大値とする。この Shapley–Shubik の割当ゲームのコアは空でなく、最大重みマッチングの双対問題($a_i+b_j\ge w_{ij}$ のもとで $\sum_ia_i+\sum_jb_j$ を最小にする問題)の最適解で成分が $0$ 以上のものがあり、それはコアの点であるKP17。

割当問題の双対を平行移動する

割当問題 の系「有理数と実数の費用」を費用 $-w_{ij}$ に当てて符号を替えると、$a_i+b_j\ge w_{ij}$ のもとでの $\sum_ia_i+\sum_jb_j$ の最小値は完全マッチングの重みの最大値に等しい。$w_{ij}\ge0$ より、部分的なマッチングは完全なものに広げても重みが減らないので、これは $v(N)$ である。最小解を取り、$\alpha:=\min_ia_i$、$\beta:=\min_jb_j$ とおくと $\alpha+\beta\ge0$ である($w_{ij}\ge0$ から)。$a_i\mapsto a_i-\alpha$、$b_j\mapsto b_j+\alpha$ と置き直すと、制約の左辺も合計も変わらず(買い手と売り手が同数なので)、成分はすべて $0$ 以上になる。$S$ の中の最大重みマッチングでは、組ごとに $w_{ij}\le a_i+b_j$ で、余る者の取り分も $0$ 以上だから $v(S)\le x(S)$ である。$\square$

計算の手順

  1. すべての提携 $S$ について $v(S)$ を表にする($2^n-1$ 個)。
  2. 線形計画 $\min\{x(N):x(S)\ge v(S)\}$ を解く。値が $v(N)$ なら解はコアの点で、$v(N)$ より大きければコアは空である。
  3. 空のとき、双対解 $\lambda$ を読むと、$\sum_S\lambda_Sv(S)>v(N)$ となる提携の混ぜ方が空である証拠になる。
  4. 凸性を調べる。$v(S\cup\{i\})-v(S)$ が $S$ について単調増加なら凸である。凸なら限界ベクトル $n!$ 個の凸包がコアである。
  5. Shapley 値を限界ベクトルの平均として計算し、コアに入るかを調べる。凸でないゲームでは入るとは限らない。
    図: 効率性の平面を三角座標で描いたもの。左は v(S) = |S|^2 のコアで、限界ベクトル 6 個を頂点とする正六角形の中心が Shapley 値である。右は滑走路の費用分担のゲームのコアで、限界ベクトル 4 個を頂点とする台形である 図: 効率性の平面を三角座標で描いたもの。左は v(S) = |S|^2 のコアで、限界ベクトル 6 個を頂点とする正六角形の中心が Shapley 値である。右は滑走路の費用分担のゲームのコアで、限界ベクトル 4 個を頂点とする台形である

例題

手袋市場

プレイヤー $1$ が左の手袋を、$2,3$ が右の手袋を 1 枚ずつ持つ。両手がそろう提携の価値を $1$、それ以外を $0$ とするKP17。

  • 使う公式:コアの定義、Shapley 値の定義。
  • 答え:$C(v)=\{(1,0,0)\}$、Shapley 値は $(\frac23,\frac16,\frac16)$ でコアに入らない。
  • 代表点:$x=(\frac23,\frac16,\frac16)$ では提携 $\{1,2\}$ の取り分が $\frac56< 1$ である。
    コアの計算

    $x_1+x_2\ge1$ と $x(N)=1$ から $x_3\le0$、同様に $x_2\le0$ で、単独の条件 $x_i\ge0$ から $x_2=x_3=0$ である。Shapley 値は、$1$ が 2 番目か 3 番目に来る確率が $\frac23$ であることから得る。

3 人の多数決と 4 人の株主

3 人の多数決。 $|S|\ge2$ で $v(S)=1$、それ以外で $0$ とする(2 人いれば全部取れるゲーム)。使う公式は thm-core-bondareva-shapley である。答えはコアが空で、代表点は $\{1,2\},\{1,3\},\{2,3\}$ に $\frac12$ を置く均衡な重みの値 $\frac32>1$ である。コアになるには全員に $\frac12$ ずつ必要で、合計 $\frac32$ を要する(cor-core-duality)。
4 人の株主。 持ち株が $1,2,3,4$ で、過半数の $6$ 株以上で $v=1$ とするKP17。使う公式は prop-core-simple である。$\{2,4\}$ と $\{1,2,3\}$ と $\{1,3,4\}$ はどれも勝つ提携で、3 つに共通する者はいないのでコアは空である。代表点は 3 つに $\frac12$ を置く均衡な重みの値 $\frac32>1$ である。

提携の大きさの 2 乗のゲーム

$n=3$、$v(S)=|S|^2$ とする。

  • 使う公式:thm-core-convex。
  • 答え:$v(S\cup\{i\})-v(S)=2|S|+1$ は $|S|$ について増加するので凸である。限界ベクトルは $(1,3,5)$ の順列 6 個で、コアは $1\le x_i\le5$、$x(N)=9$ の正六角形である。
  • 代表点:Shapley 値は $(3,3,3)$ である。
滑走路の費用分担

機種ごとに必要な滑走路の費用が $c=(1,2,3)$ で、提携は最も長いものを 1 本作ればよい。節約額のゲーム $v(S):=\sum_{i\in S}c_i-\max_{i\in S}c_i$ を考える。

  • 使う公式:thm-core-convex。
  • 答え:$v(\{1,2\})=1$、$v(\{1,3\})=1$、$v(\{2,3\})=2$、$v(N)=3$ で凸である。限界ベクトルは $(0,1,2),(0,2,1),(1,0,2),(1,2,0)$ の 4 個で、コアはそれらを頂点とする台形である。
  • 代表点:Shapley 値は $(\frac23,\frac76,\frac76)$ である。費用の負担 $c_i-x_i$ は $(\frac13,\frac56,\frac{11}6)$ で、合計は $3$ となる。区間 $[0,1]$ を 3 機で、$[1,2]$ を 2 機で、$[2,3]$ を 1 機で等分した値に一致する。
割当ゲーム

買い手 $2$ 人と売り手 $2$ 人で $(w_{ij})=\begin{pmatrix}5&2\\4&3\end{pmatrix}$ とする。

  • 使う公式:prop-core-assignment。
  • 答え:最大重みマッチングは対角の $5+3=8$ で、$v(N)=8$ である。$a=(3,2)$、$b=(2,1)$ はコアの点である。
  • 代表点:$a_1+b_1=5$、$a_1+b_2=4\ge2$、$a_2+b_1=4$、$a_2+b_2=3$、合計 $8$ である。

使える条件と反例

外す条件反例成り立たなくなること
凸性手袋市場限界ベクトルと Shapley 値がコアに入ること
均衡(優加法性だけにする)3 人の多数決コアが空でないこと
均衡の等号($\ge1$ に緩める)$n=2$、$v(\{i\})=1$、$v(N)=2$thm-core-bondareva-shapley の必要性
3 人の判定の $\frac12$ の式3 人の多数決cor-core-three の十分性
効率性3 人の多数決thm-core-bondareva-shapley の同値
反例の確かめ

凸性。 手袋市場で $S=\{1,2\}$、$T=\{1,3\}$ とすると $v(S)+v(T)=2>1=v(N)+v(\{1\})$ で凸でない。順 $(1,2,3)$ の限界ベクトルは $(0,1,0)$ で、提携 $\{1,3\}$ の取り分が $0< 1$ となる。コアは空でないが、thm-core-convex の結論は破れる。
優加法性。 3 人の多数決は、交わらない $S,T$ で $v(S\cup T)\ge v(S)+v(T)$ を満たすが、コアは空である。
均衡の等号。 $n=2$、$v(\{1\})=v(\{2\})=1$、$v(N)=2$ のコアは $\{(1,1)\}$ である。$\lambda_{\{1\}}=2$、$\lambda_{\{2\}}=1$ は $\sum_{S\ni i}\lambda_S\ge1$ を満たすが値は $3>2$ で、等号を緩めた条件は成り立たない。
$\frac12$ の式。 3 人の多数決では $v(N)=1$ で、他の 4 つの式 $1\ge0$、$1\ge1+0$ はすべて成り立つ。破れるのは $1\ge\frac32$ だけである。
効率性。 提携合理性だけなら、多数決でも $x=(1,1,1)$ が条件を満たす。均衡の不等式が破れているのに点があるので、同値は成り立たない。全体で $v(N)$ しかないという制約があってはじめて空になる。

よくある誤り

誤り正しくは
Shapley 値は常にコアに入る凸ゲームなどに限る。ex-core-glove で外れる
優加法ならコアは空でない重なりのある提携の混ぜ方で破れる。ex-core-majority を見よ
コアは 1 点である一般に多面体で、空にも 1 点にもなる
単独の条件 $x_i\ge v(\{i\})$ だけ確かめればよいすべての提携を確かめる。3 人の多数決の $(\frac13,\frac13,\frac13)$ は単独の条件を満たすが、2 人の提携が破る
コアは Nash均衡 と同じであるNash 均衡は 1 人ずつの逸脱を調べる非協力の概念で、コアは提携の逸脱を調べる配分の集合である
費用のゲームにそのまま当てる費用 $c(S)$ なら不等号は $x(S)\le c(S)$ に逆転する。節約額のゲームに直せば同じである

補足

マッチングとの関係。 安定結婚問題 の安定性は「ブロックするペアがない」という条件で、コアの提携合理性と同じ発想である。割当ゲームは、お金のやり取りができる場合の対応物にあたるKP17。
凸ゲームの意味。 凸性は、限界貢献 $v(S\cup\{i\})-v(S)$ が提携の拡大とともに増えることと同値である($S\subset T\not\ni i$ で $S\cup\{i\}$ と $T$ に凸性を当てれば増加が分かり、逆は $T\setminus S$ の要素を 1 つずつ足して差を足し合わせればよい)。集合関数の優モジュラ性にあたり、最適化の貪欲法が正しく働く条件と同じ構造で、thm-core-convex の Abel 変形はその計算である。
他の解との関係。 コアが配分の集合なのに対し、Shapley 値はゲームごとに 1 点を選ぶ規則である。コアが空のとき、cor-core-duality の値と $v(N)$ の差は、全員を満足させるのに外から足すべき最小額を表す。

関連項目

参考文献

[1]
Anna R. Karlin, Yuval Peres, Game Theory, Alive, American Mathematical Society, 2017, 著者公開版(2016 年 12 月 13 日)の番号:§12.1–12.3(pp. 204–209、Example 12.2.1、Example 12.3.3、Exercise 12.a、Theorem 12.3.5)、第 17 章 Notes(p. 309)
[2]
Lloyd S. Shapley, On balanced sets and cores, Naval Research Logistics Quarterly, 1967, pp. 453–460
[3]
Lloyd S. Shapley, Cores of convex games, International Journal of Game Theory, 1971, pp. 11–26
[4]
Tatsuro Ichiishi, Super-modularity: Applications to convex games and to the greedy algorithm for LP, Journal of Economic Theory, 1981, pp. 283–286

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