ポテンシャルゲーム(potential game)とは、どの参加者が自分の戦略だけを替えても、その人の利得の変化が参加者によらない 1 つの関数(ポテンシャル)の変化に等しくなるゲームである。戦略が有限ならポテンシャルの最大点が純粋 Nash 均衡で、1 人ずつ利得を改善する手順は必ず止まり、この性質(有限改善性)は一般化順序ポテンシャルの存在と同値である。ポテンシャルの存在は 2 人が 1 回ずつ戦略を替える 4 点の閉路の条件だけで判定できる。資源の費用が利用者数だけで決まる混雑ゲームはポテンシャルゲームで、逆に有限のポテンシャルゲームは混雑ゲームと同型である。
ポテンシャルゲーム(potential game)とは、どの参加者が自分の戦略だけを替えても、その参加者の利得の変化が、参加者によらない 1 つの関数(ポテンシャル)の変化に等しくなるゲームである。全員の利害が 1 つの関数にまとまっているので、各人が自分の利得を上げようと 1 人ずつ戦略を替えると、ポテンシャルが上がり続ける。このため有限のポテンシャルゲームには純粋戦略の Nash 均衡があり、1 人ずつ改善する手順は必ず止まる。この部分は Nash均衡 の節「潜在関数をもつゲーム」(そこでの「潜在ゲーム」はこの記事のポテンシャルゲームと同じもの)で示されている。
代表例は、道路や回線などの資源を共有し、資源の費用が使う人数だけで決まる 混雑ゲーム である。混雑ゲームは R. W. Rosenthal が導入して改善の手順を調べ(Ros73)、一般のポテンシャルゲームは D. Monderer と L. S. Shapley が調べた(MS96。帰属は KP17 第 4 章の注、p. 93 による)。この記事では、ポテンシャルの変種(重み付き・順序)、改善の手順が止まるための必要十分条件、完全なポテンシャルが存在するための 4 点の閉路による判定、混雑ゲームとポテンシャルゲームが同型の意味で同じものであること、ポテンシャルを使った均衡の効率の評価を証明する。
$N$ 人の参加者 $i=1,\dots,N$ が空でない集合 $S_i$ から戦略を選び、$S:=S_1\times\cdots\times S_N$、利得を $u_i\colon S\to\mathbb R$ とする。断らない限り $S_i$ は有限集合とする。$s\in S$ の第 $i$ 成分を $t_i\in S_i$ に替えた組を $(t_i,s_{-i})$ と書く。
関数 $P\colon S\to\mathbb R$ を考える。すべての $i$、$s\in S$、$t_i\in S_i$ について次が成り立つとき、$P$ をそれぞれ次のように呼ぶ。
1⇒2⇒3⇒4 である。1 は KP17 の式 (4.9)(p. 87)、3 は同 Remark 4.4.8 の式 (4.11)(p. 89。そこでは generalized potential function と呼ばれている)にあたる。1 は「$u_i-P$ が $s_i$ によらない」と言い換えられる(同 式 (4.8))。すなわち、ポテンシャルゲームの利得は
$$
u_i(s)=P(s)+D_i(s_{-i})
$$
の形に書ける。全員が共通の利得 $P$ をもつゲーム(協調ゲーム)と、自分の利得が自分の戦略によらないゲームの和である。
組の列 $s^0,s^1,s^2,\dots$(有限でも無限でもよい)が 改善の列 であるとは、各 $k\ge1$ について、ある参加者 $i_k$ だけが戦略を替えて $s^{k}=(t,s^{k-1}_{-i_k})$ となり、$u_{i_k}(s^k)>u_{i_k}(s^{k-1})$ となることをいう。どの改善の列も有限であるとき、ゲームは 有限改善性 をもつという。
$S$ を有限とする。ゲームが有限改善性をもつことと、一般化順序ポテンシャルをもつことは同値である。このとき純粋 Nash 均衡が存在し、それ以上延ばせない改善の列は純粋 Nash 均衡で終わる。
一般化順序ポテンシャル $P$ があるとき、改善の列に沿って $P$ は真に増えるので、列に同じ組は 2 度現れない。$S$ は有限なので、列の長さは $\lvert S\rvert-1$ 以下である。
逆に有限改善性があるとする。$s$ から長さ $1$ 以上の改善の列でたどり着ける組の集合を $R(s)$ とし、$P(s):=-\lvert R(s)\rvert$ とおく。$s\to s'$ が改善の 1 歩なら、$s'$ からたどり着ける組は $s$ からもたどり着けるので $R(s')\subseteq R(s)$ であり、$s'\in R(s)$ である。もし $s'\in R(s')$ なら、$s'$ から $s'$ に戻る改善の列を繰り返して無限の改善の列が作れ、有限改善性に反する。よって $s'\notin R(s')$ で、$R(s')\subsetneq R(s)$、$P(s')>P(s)$ である。$P$ は一般化順序ポテンシャルである。
最後の主張:任意の組から始めて延ばせる限り改善の列を延ばすと、有限改善性により有限回で止まる。止まった組では誰も 1 人で利得を上げられないので、純粋 Nash 均衡である。$\square$
完全ポテンシャルの場合は Nash均衡 の命題「潜在ゲームの純粋均衡」と同じで、KP17 Claim 4.4.3、Proposition 4.4.6(pp. 87–88)にある。同書の Remark 4.4.8(p. 89)は、順序ポテンシャルがあれば改善の列が純粋 Nash 均衡で止まることを注意している。
$P,P'$ が同じゲームの完全ポテンシャルなら、$P-P'$ は定数である。
$Q:=P-P'$ とおくと、定義の等式の差から $Q(t_i,s_{-i})=Q(s)$ がすべての $i,s,t_i$ で成り立つ。任意の $s,s'\in S$ は、成分を 1 つずつ $s_1\to s'_1$、…、$s_N\to s'_N$ と替えて結べるので、$Q(s)=Q(s')$ である。$\square$
完全ポテンシャルの存在は、2 人が 1 回ずつ戦略を替える 4 点の閉路だけを見れば判定できる。$i\ne j$、$s\in S$、$t_i\in S_i$、$t_j\in S_j$ について、$s^i:=(t_i,s_{-i})$、$s^j:=(t_j,s_{-j})$、$s^{ij}$ を $s$ の第 $i$ 成分を $t_i$、第 $j$ 成分を $t_j$ に替えた組とし
$$
\kappa:=\Bigl[u_i(s^i)-u_i(s)\Bigr]+\Bigl[u_j(s^{ij})-u_j(s^i)\Bigr]-\Bigl[u_j(s^j)-u_j(s)\Bigr]-\Bigl[u_i(s^{ij})-u_i(s^j)\Bigr]
$$
とおく。$\kappa$ は、$s$ から $s^{ij}$ へ「$i$ が先」に動く道と「$j$ が先」に動く道で、動いた人の利得の変化の和の差である。
($S_i$ は無限集合でもよい。)ゲームが完全ポテンシャルをもつための必要十分条件は、すべての $i\ne j$、$s$、$t_i$、$t_j$ について $\kappa=0$ となることである。
必要性:完全ポテンシャル $P$ があれば、$\kappa$ の 4 つの括弧はそれぞれ $P(s^i)-P(s)$、$P(s^{ij})-P(s^i)$、$P(s^j)-P(s)$、$P(s^{ij})-P(s^j)$ に等しく、$\kappa=0$ である。
十分性:組の列 $\gamma=(x^0,x^1,\dots,x^m)$ で、隣り合う組が高々 1 つの成分で異なるものを 道 といい、$x^{k-1}$ から $x^k$ で替わる成分の参加者を $i_k$ として(替わらない歩は差が $0$ なので誰でもよい)
$$
I(\gamma):=\sum_{k=1}^m\Bigl[u_{i_k}(x^k)-u_{i_k}(x^{k-1})\Bigr]
$$
とおく。$I$ は次の 2 つの操作で変わらない。
$\kappa$ は各 2 人とほかの人の戦略を固定した $2\times2$ の部分だけで決まるので、戦略の集合が有限なら判定は有限の計算になる。この判定を使うと、ある組合せの利得がポテンシャルゲームになるかどうかを、ポテンシャルを推測せずに確かめられる。
2 人が協力 $\mathrm C$ か裏切り $\mathrm D$ を選び、利得が $(\mathrm C,\mathrm C)\mapsto(-1,-1)$、$(\mathrm C,\mathrm D)\mapsto(-3,0)$、$(\mathrm D,\mathrm C)\mapsto(0,-3)$、$(\mathrm D,\mathrm D)\mapsto(-2,-2)$ であるとする。$P(\mathrm C,\mathrm C)=0$、$P(\mathrm C,\mathrm D)=P(\mathrm D,\mathrm C)=1$、$P(\mathrm D,\mathrm D)=2$ は完全ポテンシャルである(どちらの参加者も、$\mathrm C\to\mathrm D$ で利得が $1$ 増え、$P$ も $1$ 増える)。$P$ の最大点 $(\mathrm D,\mathrm D)$ が唯一の純粋 Nash 均衡で、利得の和を最大にする $(\mathrm C,\mathrm C)$ とは異なる。ポテンシャルは利得の和ではない。
無向グラフの各頂点 $i$ が参加者で、$b_i\in\{0,1\}$ を選び、費用 $D_i(b):=\sum_{j}w_{ij}\lvert b_i-b_j\rvert$($j$ は $i$ の隣接頂点、$w_{ij}>0$)を小さくしたいとする(KP17 Example 4.4.7、Exercises 4.20・4.21、pp. 88・97–98)。
$w_{ij}=w_{ji}$ なら、意見の違う辺の重みの和 $\Phi(b):=\sum_{\{i,j\}}w_{ij}\lvert b_i-b_j\rvert$ が費用のポテンシャルである。$i$ が $b_i$ を替えて変わるのは $i$ を含む辺の項だけで、その和は $D_i$ だからである。
ある辺で $w_{ij}\ne w_{ji}$ なら、完全ポテンシャルはない。$i,j$ 以外を固定し、$s=(b_i,b_j)=(0,0)$、$t_i=t_j=1$ とする。$D_i=w_{ij}\lvert b_i-b_j\rvert+g_i(b_i)$、$D_j=w_{ji}\lvert b_i-b_j\rvert+g_j(b_j)$($g_i,g_j$ はほかの辺の分)と書けるので、利得 $-D_i,-D_j$ についての $\kappa$ は
$$
\kappa=\bigl(-w_{ij}\bigr)+w_{ji}-\bigl(-w_{ji}\bigr)-w_{ij}=2(w_{ji}-w_{ij})\ne0
$$
である($g_i,g_j$ の寄与は打ち消し合う)。thm-pg-cycle により、ポテンシャルゲームではない。
参加者 1 の戦略を $x_1,x_2$、参加者 2 の戦略を $y_1,y_2$ とし、利得を
$$
u_1=\begin{pmatrix}3&0\\0&1\end{pmatrix},\qquad u_2=\begin{pmatrix}1&0\\0&1\end{pmatrix}
$$
(行が $x_k$、列が $y_l$)とする。$s=(x_1,y_1)$、$t_1=x_2$、$t_2=y_2$ で $\kappa=(0-3)+(1-0)-(0-1)-(1-0)=-2$ なので、完全ポテンシャルはない。一方 $P=\begin{pmatrix}2&0\\0&1\end{pmatrix}$ は順序ポテンシャルで、$(x_1,y_1)$ と $(x_2,y_2)$ が純粋 Nash 均衡である。このゲームは重み $w=(2,1)$ の重み付きポテンシャル $P'=\begin{pmatrix}0&-1\\-3/2&-1/2\end{pmatrix}$ をもつ。
有限集合 $R$(資源)と、各 $r\in R$ の 費用の関数 $c_r\colon\{1,\dots,N\}\to\mathbb R$ が与えられているとする。参加者 $i$ の戦略の集合 $\Sigma_i$ は $R$ の部分集合からなる空でない族で、組 $A=(A_1,\dots,A_N)\in\Sigma_1\times\cdots\times\Sigma_N$ について、$n_r(A):=\#\{i\mid r\in A_i\}$ を資源 $r$ の利用者数とし、参加者 $i$ の費用を
$$
C_i(A):=\sum_{r\in A_i}c_r\bigl(n_r(A)\bigr)
$$
とする。これを 混雑ゲーム という(利得は $u_i=-C_i$)。
経路選択では、資源は辺、戦略は自分の出発点から到着点への路(辺の集合)である。費用の関数は人数の関数で、誰が使うかによらないことが本質である(下の反例の表)。費用は負でもよく、単調でなくてもよい。
2 つのゲーム $(S_i,u_i)_i$ と $(S'_i,u'_i)_i$(参加者は同じ)が 同型 であるとは、全単射 $\varphi_i\colon S_i\to S'_i$ があって、すべての $s$ で $u'_i\bigl(\varphi_1(s_1),\dots,\varphi_N(s_N)\bigr)=u_i(s)$ となることをいう。
1:参加者 $i$ が $A_i$ を $B_i$ に替えると、$r\in B_i\setminus A_i$ の利用者数は $1$ 増え、$r\in A_i\setminus B_i$ の利用者数は $1$ 減り、ほかは変わらない。$n_r:=n_r(A)$ とすると、$\Phi$ の変化は
$$
\sum_{r\in B_i\setminus A_i}c_r(n_r+1)-\sum_{r\in A_i\setminus B_i}c_r(n_r)
$$
である。$C_i$ は、$A_i\cap B_i$ の資源の項 $c_r(n_r)$ が共通で、$A_i\setminus B_i$ の項 $c_r(n_r)$ が消え、$B_i\setminus A_i$ の項 $c_r(n_r+1)$ が加わるので、変化は同じである。
2:完全ポテンシャル $P$ をもつ有限のゲーム $(S_i,u_i)$ をとり、$D_i:=u_i-P$ とおく。$D_i(s)$ は $s_{-i}$ だけで決まるので $D_i(s_{-i})$ と書く。資源の集合を、組 $z\in S$ ごとの資源 $\rho_z$ と、参加者 $k$ と $y\in S_{-k}:=\prod_{l\ne k}S_l$ ごとの資源 $\sigma_{k,y}$ の全体とする。参加者 $i$ の戦略 $s_i\in S_i$ に、資源の集合
$$
\varphi_i(s_i):=\{\rho_z\mid z_i=s_i\}\cup\{\sigma_{i,y}\mid y\in S_{-i}\}\cup\{\sigma_{k,y}\mid k\ne i,\ y_i\ne s_i\}
$$
を対応させる($y_i$ は $y\in S_{-k}$ の第 $i$ 成分)。第 1 の部分が $s_i$ ごとに異なるので $\varphi_i$ は単射であり、その像を $\Sigma_i$ とする。費用の関数を
$$
c_{\rho_z}(m):=\begin{cases}-P(z)&(m=N)\\0&(m< N)\end{cases},\qquad c_{\sigma_{k,y}}(m):=\begin{cases}-D_k(y)&(m=1)\\0&(m\ge2)\end{cases}
$$
とする。組 $s$ に対応する組 $A=(\varphi_i(s_i))_i$ での利用者数を数える。$\rho_z$ を使うのは $z_i=s_i$ となる $i$ なので、$n_{\rho_z}=N$ となるのは $z=s$ のときだけである。$\sigma_{k,y}$ は $k$ がつねに使い、$i\ne k$ は $y_i\ne s_i$ のときに使うので、$n_{\sigma_{k,y}}=1$ となるのは $y=s_{-k}$ のときだけである。よって参加者 $i$ の費用は、$\rho_s$ の項 $-P(s)$、$\sigma_{i,s_{-i}}$ の項 $-D_i(s_{-i})$ と、$k\ne i$ の $\sigma_{k,y}$ の項($k$ と $i$ が使うので利用者数は $2$ 以上で、$0$)の和で、$C_i(A)=-P(s)-D_i(s_{-i})=-u_i(s)$ である。$\square$
1 は KP17 Example 4.4.1・Corollary 4.4.2(pp. 85–86)で、Nash均衡 の節「潜在関数をもつゲーム」の混雑ゲームの段落にも同じ計算がある。$\Phi$ は、参加者を 1 人ずつ加えて、加えた時点のその人の費用を足していったものである(KP17 p. 86)。$\Phi$ は費用の和 $\sum_iC_i$ とは異なる。2 の意味での逆は Monderer–Shapley による(MS96)。2 の構成は資源の数が組の数ほどになり大きいが、ポテンシャルゲームという性質が「資源の費用が人数だけで決まる」という形に必ず書けることを示している。
利用者が連続量の経路選択(Braessのパラドックス)では、和 $\sum_{m=1}^{n}c_r(m)$ が積分 $\int_0^{F_e}\ell_e$ に替わり、Beckmann のポテンシャルになる(KP17 Remark 8.1.12 と Lemma 8.1.11 の証明、pp. 153–154)。
費用が整数値の混雑ゲームでは、改善の 1 歩ごとに $\Phi$ が $1$ 以上減るので、改善の列の歩数は $\Phi(A^0)-\min\Phi$ 以下である。ただしこれは資源や人数について指数的になりうる。Fabrikant–Papadimitriou–Talwar(2004 年)は、最適反応は効率よく計算できるのに、純粋 Nash 均衡に着くまでの改善の歩数の最小値が、参加者と資源の数の和について指数的になる混雑ゲームがあることを示した(KP17 第 4 章の注、p. 93)。
ポテンシャルの最小点は均衡なので、ポテンシャルと社会費用が近ければ、良い均衡があることが分かる。社会費用を $\mathrm{SC}:=\sum_iC_i$ とする。
戦略の集合が有限の費用のゲームが費用のポテンシャル $\Phi$ をもち、ある $B\ge1$ についてすべての組で $\Phi\le\mathrm{SC}\le B\,\Phi$ が成り立つとする。このとき、社会費用が $\min\mathrm{SC}$ の $B$ 倍以下の純粋 Nash 均衡がある。とくに、費用の関数が $c_r(m)=p_rm+q_r$($p_r,q_r\ge0$)の混雑ゲームでは $B=2$ にとれる。
$\Phi$ の最小点 $\bar A$ は純粋 Nash 均衡である(1 人で費用を下げると $\Phi$ も同じだけ下がるので)。$A^*$ を $\mathrm{SC}$ の最小点とすると $\mathrm{SC}(\bar A)\le B\Phi(\bar A)\le B\Phi(A^*)\le B\,\mathrm{SC}(A^*)$ である。
1 次の費用では、資源 $r$ ごとに $n:=n_r(A)$ として、$\Phi$ の項は $p_r\frac{n(n+1)}2+q_rn$、$\mathrm{SC}$ の項は $n(p_rn+q_r)$ である($\mathrm{SC}=\sum_iC_i=\sum_rn_rc_r(n_r)$)。$n\ge0$ の整数で $\frac{n(n+1)}2\le n^2\le n(n+1)$ なので、項ごとに $\Phi\le\mathrm{SC}\le2\Phi$ である。$\square$
これは「最良の均衡」の評価(アナーキーの代償 の記事の安定性の代償)である。同じ 1 次の費用の経路選択でも、最悪の均衡の比は $\frac52$ まで悪くなりうる(アナーキーの代償 の例「比 5/2 に達する例」)。
完全ポテンシャルの定義は、戦略の集合が無限でもそのまま意味をもち(KP17 Exercise 4.23、p. 98)、thm-pg-cycle もその証明のとおり無限の場合に成り立つ。定義から、純粋 Nash 均衡は $P$ を各成分ごとに最大にする組であり、$P$ の最大点は純粋 Nash 均衡である。
$N$ 社が生産量 $q_i\ge0$ を選び、価格が $a-bQ$($Q:=\sum_iq_i$、$a,b>0$)、限界費用が $c$($0\le c< a$)のとき、利得を $u_i(q):=q_i(a-bQ)-cq_i$ とする。
$$
P(q):=(a-c)\sum_iq_i-b\sum_iq_i^2-b\sum_{i< j}q_iq_j
$$
とおくと、$u_i-P$ の $q_i$ を含む項は $(a-c)q_i-bq_i^2-bq_i\sum_{j\ne i}q_j$ で打ち消し合うので、$u_i-P$ は $q_i$ によらず、$P$ は完全ポテンシャルである。$P$ のヘッセ行列は $-b(I+J)$($J$ は成分がすべて $1$ の行列)で負定値なので $P$ は狭義凹であり、$\partial P/\partial q_i=a-c-bq_i-bQ=0$ を解いた $q_i=\frac{a-c}{(N+1)b}>0$ が $[0,\infty)^N$ での最大点である。よってこれは純粋 Nash 均衡である。$N=2$、$a=10$、$b=1$、$c=1$ なら $q=(3,3)$ である。
| 外した仮定 | 例 | 成り立たなくなる結論 |
|---|---|---|
| 戦略の集合が有限(prop-pg-fip) | 1 人のゲーム、$S_1=\{0,1,2,\dots\}$、$u_1(n)=n$ | 改善の列 $0,1,2,\dots$ が止まらず、純粋 Nash 均衡もない($P=u_1$ は完全ポテンシャル) |
| 一般化順序ポテンシャルをもつ(prop-pg-fip) | 下の $3\times3$ のゲーム | 純粋 Nash 均衡はあるが、無限の改善の列があり有限改善性がない |
| 費用の関数が参加者によらない(thm-pg-congestion の 1) | 2 人・資源 $x,y$、戦略は $\{x\}$ か $\{y\}$、参加者 1 の費用 $c(m)=m$、参加者 2 の費用 $c(m)=2m$ | $\lvert\kappa\rvert=2$ で完全ポテンシャルがない |
| 1 人ずつ改善する(prop-pg-fip) | 1 本の辺の合意ゲーム(ex-pg-consensus、$w_{12}=w_{21}=1$)で、改善できる人が同時に替える | $(0,1)\to(1,0)\to(0,1)\to\cdots$ と止まらない |
無限の戦略:$P=u_1$ は定義の 1 を満たす。$n\to n+1$ はつねに改善で、どの $n$ も最適反応でない。
$3\times3$ のゲーム:参加者 1 の戦略を $x_1,x_2,x_3$、参加者 2 の戦略を $y_1,y_2,y_3$ とし、利得の組を
$$
\begin{pmatrix}(1,-1)&(-1,1)&(-2,-2)\\(-1,1)&(1,-1)&(-2,-2)\\(-2,-2)&(-2,-2)&(1,1)\end{pmatrix}
$$
とする。$(x_3,y_3)$ では、どちらが替えても利得が $1$ から $-2$ に下がるので純粋 Nash 均衡である。一方、左上の $2\times2$ はコイン合わせで、$(x_1,y_1)\to(x_1,y_2)\to(x_2,y_2)\to(x_2,y_1)\to(x_1,y_1)$ の各歩で動いた人の利得が $-1$ から $1$ に上がるので、これを繰り返す無限の改善の列がある。prop-pg-fip により一般化順序ポテンシャルはない。
参加者ごとの費用:$s=(\{x\},\{x\})$、$t_1=\{y\}$、$t_2=\{y\}$ とする。費用は $C_1(s)=2$、$C_1(s^1)=1$、$C_1(s^2)=1$、$C_1(s^{12})=2$、$C_2(s)=4$、$C_2(s^1)=2$、$C_2(s^2)=2$、$C_2(s^{12})=4$ で、利得 $-C_i$ についての $\kappa$ は $-(1-2)-(4-2)+(2-4)+(2-1)=-2$ である。参加者 2 の費用を $\frac12$ 倍すれば普通の混雑ゲームになるので、このゲームは重み $(1,2)$ の重み付きポテンシャルをもつ。
同時の改善:$(0,1)$ では 2 人とも費用 $1$ で、替えれば $0$ になるので、2 人とも替えると $(1,0)$ になり、同じことが繰り返される。1 人ずつなら 1 歩で $(1,1)$ か $(0,0)$ に着いて止まる(KP17 Example 4.4.7、pp. 88–89 は一般のグラフで、同時に替える手順が周期 2 以下の繰り返しに落ち着くことを示している)。
| 誤り | 正しくは | なぜ |
|---|---|---|
| ポテンシャルは利得の和(または費用の和)である | 一般に異なる | ex-pg-prisoner、混雑ゲームの $\Phi$ と $\sum_iC_i$ |
| ポテンシャルの最大点だけが純粋 Nash 均衡である | 均衡は $P$ を各成分ごとに最大にする組で、局所的な最大点も均衡になる | ex-pg-ordinal の $(x_2,y_2)$ は $P$ の最大点でないが均衡 |
| 純粋 Nash 均衡があれば改善の手順は止まる | 止まらないことがある | ex-pg-counterexamples の $3\times3$ のゲーム |
| 改善の手順は速く止まる | 歩数が指数的になる混雑ゲームがある | Fabrikant–Papadimitriou–Talwar の結果 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する