ポテンシャルゲーム

同義語:潜在ゲームpotential game

概要

ポテンシャルゲーム(potential game)とは、どの参加者が自分の戦略だけを替えても、その人の利得の変化が参加者によらない 1 つの関数(ポテンシャル)の変化に等しくなるゲームである。戦略が有限ならポテンシャルの最大点が純粋 Nash 均衡で、1 人ずつ利得を改善する手順は必ず止まり、この性質(有限改善性)は一般化順序ポテンシャルの存在と同値である。ポテンシャルの存在は 2 人が 1 回ずつ戦略を替える 4 点の閉路の条件だけで判定できる。資源の費用が利用者数だけで決まる混雑ゲームはポテンシャルゲームで、逆に有限のポテンシャルゲームは混雑ゲームと同型である。

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

前提知識: Nash均衡, ゲーム理論

ポテンシャルゲーム(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})$ と書く。

ポテンシャルの 4 つの型

関数 $P\colon S\to\mathbb R$ を考える。すべての $i$、$s\in S$、$t_i\in S_i$ について次が成り立つとき、$P$ をそれぞれ次のように呼ぶ。

  1. 完全ポテンシャル:$u_i(t_i,s_{-i})-u_i(s)=P(t_i,s_{-i})-P(s)$。
  2. 重み付きポテンシャル(重み $w_i>0$):$u_i(t_i,s_{-i})-u_i(s)=w_i\bigl(P(t_i,s_{-i})-P(s)\bigr)$。
  3. 順序ポテンシャル:$u_i(t_i,s_{-i})-u_i(s)$ と $P(t_i,s_{-i})-P(s)$ の符号が等しい。
  4. 一般化順序ポテンシャル:$u_i(t_i,s_{-i})>u_i(s)$ ならば $P(t_i,s_{-i})>P(s)$。
    完全ポテンシャルをもつゲームを ポテンシャルゲーム という。参加者が費用 $C_i$ を小さくしたいゲームでは、$u_i=-C_i$ とし、$\Phi:=-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$ が先」に動く道で、動いた人の利得の変化の和の差である。

4 点の閉路による判定

($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 つの操作で変わらない。

  • 入れ替え:道の中の連続する 2 歩 $x\to y\to w$ で、最初の歩で参加者 $j$ が、次の歩で参加者 $i\ne j$ が替えるとき、中間の組 $y$ を、先に $i$ の成分だけを $w_i$ に替えた組 $(w_i,x_{-i})$ に置き換える。差はちょうど $s=x$、$t_i=w_i$、$t_j=y_j$ とした $\kappa$ であり、仮定により $0$ である。
  • 併合:同じ参加者 $i$ が続けて替える 2 歩 $x\to y\to w$ を 1 歩 $x\to w$ にする。$[u_i(y)-u_i(x)]+[u_i(w)-u_i(y)]=u_i(w)-u_i(x)$ である。
    $z\in S$ を 1 つ固定し、$s\in S$ に対して、$z$ から成分を $1,2,\dots,N$ の順に $z_k\to s_k$ と替える道を $\gamma_s$ とし、$P(s):=I(\gamma_s)$ と定める。$i$、$s$、$t_i$ を与え、$\gamma_s$ の後に 1 歩 $s\to(t_i,s_{-i})$ を付けた道を $\gamma'$ とする。$I(\gamma')=P(s)+u_i(t_i,s_{-i})-u_i(s)$ である。
    $\gamma'$ の最後の歩(参加者 $i$ が $s_i\to t_i$)を、その直前の参加者 $N,N-1,\dots,i+1$ の歩と順に入れ替えて前に移すと、参加者 $i$ の歩 $z_i\to s_i$ の直後に来る。この 2 歩を併合すると $z_i\to t_i$ の 1 歩になる。できた道は、$z$ から成分を $1,\dots,N$ の順に $(t_i,s_{-i})$ の成分へ替える道、すなわち $\gamma_{(t_i,s_{-i})}$ そのものである。2 つの操作は $I$ を変えないので
    $$ P(t_i,s_{-i})=I\bigl(\gamma_{(t_i,s_{-i})}\bigr)=I(\gamma')=P(s)+u_i(t_i,s_{-i})-u_i(s) $$
    であり、$P$ は完全ポテンシャルである。$\square$

$\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. 混雑ゲームでは
    $$ \Phi(A):=\sum_{r\in R}\sum_{m=1}^{n_r(A)}c_r(m) $$
    が費用のポテンシャルである:$C_i(B_i,A_{-i})-C_i(A)=\Phi(B_i,A_{-i})-\Phi(A)$。とくに混雑ゲームはポテンシャルゲームである。
  2. 逆に、有限のポテンシャルゲームは混雑ゲームと同型である。
1 は人数の増減を数え、2 は資源を組ごとに用意する

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 均衡である。

Cournot の寡占

$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 の結果

関連項目

参考文献

[1]
Anna R. Karlin, Yuval Peres, Game Theory, Alive, American Mathematical Society, 2017, 著者公開版(2016 年 12 月 13 日)の番号:Example 4.4.1・Corollary 4.4.2(pp. 85–86)、§4.4.1・式 (4.8)・(4.9)・Claim 4.4.3(p. 87)、Proposition 4.4.6(pp. 87–88)、Example 4.4.7(pp. 88–89)、Remark 4.4.8・式 (4.11)(p. 89)、第 4 章の注(p. 93)、Exercises 4.20・4.21(pp. 97–98)、Exercise 4.23(p. 98)、Remark 8.1.12(p. 153)、Lemma 8.1.11 の証明(p. 154)
[2]
Dov Monderer, Lloyd S. Shapley, Potential games, Games and Economic Behavior 14 (1996), no. 1, 124–143, 1996
[3]
Robert W. Rosenthal, A class of games possessing pure-strategy Nash equilibria, International Journal of Game Theory 2 (1973), 65–67, 1973

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