フォーク定理

同義語:folk theoremFolk定理

概要

フォーク定理(folk theorem)とは、同じゲームを無限に繰り返し、参加者が将来を十分重く見るとき、実行可能で各参加者の最小最大値を上回る利得の組が均衡で実現できる、という一群の定理である。割引のある繰り返しでは、均衡の利得は必ず実行可能で最小最大値以上である。純粋行動の組の利得で最小最大値を上回るものは、割引因子が 1 に近ければ Nash 均衡で、1 回のゲームの Nash 均衡の利得を上回るものは部分ゲーム完全均衡で実現できる(Friedman)。2 人なら純粋最小最大値を上回るものが部分ゲーム完全均衡で実現できる(Fudenberg–Maskin)が、3 人以上では最小最大値を上回る利得でも実現できない例がある。

$$\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均衡, 部分ゲーム完全均衡, 凸包

フォーク定理(folk theorem)は、同じゲームを無限に繰り返すとき、参加者が将来を十分重く見るなら、実行可能で、各参加者が最低限確保できる値(最小最大値)を上回る利得の組は、ほぼすべて均衡で実現できる、という一群の定理である。1 回だけのゲームでは協調が均衡にならない ゲーム理論 の例「均衡が全員にとって最善でない例」(囚人のジレンマ)でも、繰り返せば「裏切ったら以後は罰する」という約束で協調が均衡になる。学術誌に現れる前からゲーム理論の研究者の間で知られていた(KP17 p. 135 の注)。
均衡の種類と仮定によって、いくつもの版がある。この記事では割引のある無限回の繰り返しについて、次を示す。

  • 均衡の利得は必ず実行可能で、最小最大値以上である(prop-ft-necessary)。
  • 純粋行動の組の利得で最小最大値を上回るものは、割引因子が 1 に近ければ Nash 均衡で実現できる(thm-ft-nash)。
  • そのうち 1 回のゲームの Nash 均衡の利得を上回るものは、部分ゲーム完全均衡で実現できる(Friedman、thm-ft-friedman)。
  • 2 人なら、そのうち純粋最小最大値を上回るものが部分ゲーム完全均衡で実現できる(Fudenberg–Maskin、thm-ft-fm-two)。
  • 3 人以上では、最小最大値を上回る利得でも実現できない例がある(prop-ft-three)。

定義

割引のある繰り返しゲーム

$k\ge2$ とし、段階ゲーム $G$ を、参加者 $i=1,\dots,k$ の有限な行動の集合 $A_i$ と利得 $u_i\colon A\to\mathbb R$($A:=A_1\times\dots\times A_k$)で与える。$0<\delta<1$ とする。

  1. $t=0,1,2,\dots$ の各期に全員が同時に行動を選び、期の終わりに全員の行動 $a^t\in A$ が全員に知らされる。長さ $t$ の 履歴 は $h=(a^0,\dots,a^{t-1})\in A^t$ で、$H:=\bigcup_{t\ge0}A^t$ とおく($A^0$ は空の履歴 $\emptyset$ だけ)。
  2. 参加者 $i$ の 戦略 $\sigma_i$ は、各履歴 $h\in H$ に $A_i$ 上の確率分布 $\sigma_i(h)$ を対応させる写像である。各期の行動は、履歴が与えられたとき参加者の間で独立に選ばれる。
  3. 戦略の組 $\sigma$ と履歴 $h$ に対し、$h$ の後のプレイの分布のもとでの
    $$ U_i(\sigma\mid h):=(1-\delta)\,\mathbb E\Bigl[\sum_{t\ge0}\delta^tu_i(a^{\lvert h\rvert+t})\Bigr] $$
    を、$h$ からの 継続利得 という。$U_i(\sigma):=U_i(\sigma\mid\emptyset)$ とし、これを (正規化した)割引利得 という。係数 $1-\delta$ により、毎期 $c$ を得ると利得は $c$ になる。
  4. すべての $i$ と $i$ のすべての戦略 $\sigma_i'$ について $U_i(\sigma_i',\sigma_{-i})\le U_i(\sigma)$ なら $\sigma$ を Nash 均衡、すべての履歴 $h$ について $U_i(\sigma_i',\sigma_{-i}\mid h)\le U_i(\sigma\mid h)$ なら 部分ゲーム完全均衡 という。
    この無限回の繰り返しゲームを $G^\infty(\delta)$ と書く。

$\delta$ は、次の期もゲームが続く確率、あるいは利子による将来の利得の割引と読める(KP17 p. 129)。履歴 $h$ から先のゲームは $G^\infty(\delta)$ と同じ形なので、部分ゲーム完全均衡 $\sigma$ の $h$ からの続き $\sigma\vert_h$($\sigma\vert_h(h'):=\sigma(hh')$)は、また $G^\infty(\delta)$ の部分ゲーム完全均衡である。

実行可能な利得と最小最大値

段階ゲーム $G$ について、

  1. $u(A)=\{(u_1(a),\dots,u_k(a))\mid a\in A\}$ の凸包 $V$ を 実行可能な利得の集合 という(KP17 Definition 6.4.7、pp. 131–132)。
  2. 参加者 $i$ の 最小最大値 を
    $$ \underline v_i:=\min_{\alpha_{-i}}\max_{a_i\in A_i}u_i(a_i,\alpha_{-i}) $$
    とする。$\alpha_{-i}$ は $i$ 以外の参加者の独立な混合行動の組全体を動き、$u_i(a_i,\alpha_{-i})$ は期待値である(KP17 Definition 6.4.8、p. 132)。最小値は、混合行動の組の集合がコンパクトで、$\max_{a_i}$ が連続関数なので存在する。最小値を与える $\alpha_{-i}$ を $i$ を罰する行動 という。
  3. $\alpha_{-i}$ を純粋行動の組 $a_{-i}$ に限ったものを $\hat v_i:=\min_{a_{-i}}\max_{a_i}u_i(a_i,a_{-i})$ とし、純粋最小最大値 という。$\underline v_i\le\hat v_i$ である。
  4. $v\in V$ で、すべての $i$ について $v_i>\underline v_i$ のとき、$v$ は 狭義に個人合理的 という。

定理の表

版均衡実現できる利得 $v$条件根拠
必要条件Nash$v\in V$、$v_i\ge\underline v_i$すべての $\delta$prop-ft-necessary
Nash 版Nash$v=u(a^\ast)$、$v_i>\underline v_i$$\delta\ge\max_i\frac{d_i-v_i}{d_i-\underline v_i}$thm-ft-nash
Friedman部分ゲーム完全$v=u(a^\ast)$、$v_i>e_i$($e$ は段階ゲームの Nash 均衡の利得)$\delta\ge\max_i\frac{d_i-v_i}{d_i-e_i}$thm-ft-friedman
Fudenberg–Maskin部分ゲーム完全$v=u(a^\ast)$、$v_i>\hat v_i$$k=2$、$\delta$ が 1 に近いthm-ft-fm-two
平均利得Nash$v\in V$、$v_i\ge\underline v_i$ のすべて割引でなく長期平均rem-ft-average
3 人の反例部分ゲーム完全狭義に個人合理的でも実現できない $v$ がある$k=3$、$\dim V=1$prop-ft-three

$d_i:=\max_{a_i\in A_i}u_i(a_i,a^\ast_{-i})$ は、他の全員が $a^\ast$ に従うときに $i$ が 1 期で得られる最大の利得である。

主定理と証明

必要条件

均衡の利得の必要条件

$G^\infty(\delta)$ のどの Nash 均衡 $\sigma$ についても、$U(\sigma)=(U_1(\sigma),\dots,U_k(\sigma))\in V$ であり、すべての $i$ で $U_i(\sigma)\ge\underline v_i$ である。

期ごとの最適反応で最小最大値を確保する

要点:各期の期待利得は $V$ の点で、割引利得はその凸結合の極限である。各期に相手の行動への最適反応をとれば、毎期 $\underline v_i$ 以上を得る。

詳しい証明を開く

実行可能性。 各期 $t$ の期待利得 $\mathbb E[u(a^t)]=\sum_{a\in A}P(a^t=a)\,u(a)$ は $u(A)$ の点の凸結合なので $V$ に属する。$U(\sigma)=\sum_{t\ge0}(1-\delta)\delta^t\,\mathbb E[u(a^t)]$ は、和が $1$ の正の重みによる $V$ の点の和である。有限和までの部分は $V$ の点の凸結合に $(1-\delta^{T})$ を掛けたものと見て、$T\to\infty$ とすると、$V$ が有界閉集合(有限集合の凸包)なので $U(\sigma)\in V$ である。 個人合理性。 参加者 $i$ の戦略 $\sigma_i'$ を、各履歴 $h$ で $\max_{a_i}u_i(a_i,\sigma_{-i}(h))$ を与える純粋行動を 1 つ選ぶものとする。ここで $\sigma_{-i}(h)$ は他の参加者の独立な混合行動の組なので、その最大値は $\underline v_i$ 以上である。$(\sigma_i',\sigma_{-i})$ のもとで、各期の $i$ の期待利得は、その期の履歴で条件を付けると $\underline v_i$ 以上なので、期待値をとっても $\underline v_i$ 以上で、$U_i(\sigma_i',\sigma_{-i})\ge\underline v_i$ である。$\sigma$ は Nash 均衡なので $U_i(\sigma)\ge U_i(\sigma_i',\sigma_{-i})\ge\underline v_i$ である。$\square$

KP17 Theorem 6.4.10(p. 133)の (1) は、平均利得についての同じ主張である。

一段逸脱原理

$\sigma$、履歴 $h$、$a_i\in A_i$ に対し、「$h$ で $a_i$ を選び、それ以外の履歴では $\sigma_i$ に従う」戦略を $\sigma_i^{h\to a_i}$ と書き、$h$ での 一段逸脱 という。

繰り返しゲームの一段逸脱原理

$G^\infty(\delta)$ の戦略の組 $\sigma$ について、次は同値である。

  1. $\sigma$ は部分ゲーム完全均衡である。
  2. すべての履歴 $h$、すべての $i$、すべての $a_i\in A_i$ について $U_i(\sigma_i^{h\to a_i},\sigma_{-i}\mid h)\le U_i(\sigma\mid h)$。

有限の木の場合は 部分ゲーム完全均衡 の定理「一段逸脱原理」にある。無限に続くゲームでは、割引によって遠い将来の影響が小さいことを使う。遠い将来の影響が小さくならない利得では、無限に続くゲームで成り立たないことがある(部分ゲーム完全均衡 の反例の表の 3 行目)。

有限回の逸脱に切り詰めて後ろから戻す

1 ⇒ 2 は定義から明らかである。2 を仮定し、ある履歴 $h$、参加者 $i$、戦略 $\sigma_i'$ について $U_i(\sigma_i',\sigma_{-i}\mid h)>U_i(\sigma\mid h)+\varepsilon$($\varepsilon>0$)となったとして矛盾を導く。$M:=\max_{a}\lvert u_i(a)\rvert$ とする。
切り詰め。 $\delta^T\cdot2M<\varepsilon/2$ となる $T$ をとる。$\sigma_i''$ を、$h$ の後 $T$ 期未満の履歴($hh'$ で $\lvert h'\rvert< T$)では $\sigma_i'$、それ以外では $\sigma_i$ と定める。$(\sigma_i',\sigma_{-i})$ と $(\sigma_i'',\sigma_{-i})$ は $h$ から $T$ 期の間は同じ分布のプレイを生むので、$h$ からの継続利得の差は $T$ 期以降の分だけで、$(1-\delta)\sum_{t\ge T}\delta^t\cdot2M=2M\delta^T<\varepsilon/2$ である。よって $U_i(\sigma_i'',\sigma_{-i}\mid h)>U_i(\sigma\mid h)+\varepsilon/2$ である。
後ろから戻す。 $m=T,T-1,\dots,1$ について、$\sigma_i^{(m)}$ を「$h$ の後 $m$ 期未満の履歴では $\sigma_i''$、それ以外では $\sigma_i$」とする。$\sigma_i^{(T)}=\sigma_i''$ である。$U_i(\sigma_i^{(m-1)},\sigma_{-i}\mid h)\ge U_i(\sigma_i^{(m)},\sigma_{-i}\mid h)$ を示す($\sigma_i^{(0)}:=\sigma_i$)。
2 つの戦略は、$h$ の後 $m-1$ 期未満の履歴では一致するので、$h$ から $m-1$ 期の間のプレイの分布は同じで、その間の利得も同じである。長さ $\lvert h\rvert+m-1$ の各履歴 $g$ で、$\sigma_i^{(m)}$ は $g$ で $\sigma_i''(g)$ を選び、その後は $\sigma_i$ に従う。$\sigma_i''(g)$ は $A_i$ 上の分布で、$g$ からの継続利得は $a_i$ ごとの一段逸脱の継続利得をその分布で平均したものである。2 よりそれぞれ $U_i(\sigma\mid g)$ 以下なので、
$$ U_i(\sigma_i^{(m)},\sigma_{-i}\mid g)\le U_i(\sigma\mid g)=U_i(\sigma_i^{(m-1)},\sigma_{-i}\mid g) $$
である(右の等号は、$\sigma_i^{(m-1)}$ が $g$ 以後 $\sigma_i$ に一致することによる)。$h$ からの継続利得は、$m-1$ 期の間の利得と、$g$ の分布についての $\delta^{m-1}U_i(\cdot\mid g)$ の期待値の和なので、主張が従う。
これを $m=T,\dots,1$ と続けると $U_i(\sigma\mid h)\ge U_i(\sigma_i'',\sigma_{-i}\mid h)>U_i(\sigma\mid h)+\varepsilon/2$ となり、矛盾である。$\square$

Nash 均衡の版

割引のある Nash 均衡のフォーク定理

$a^\ast\in A$、$v:=u(a^\ast)$ がすべての $i$ で $v_i>\underline v_i$ を満たすとし、$d_i:=\max_{a_i}u_i(a_i,a^\ast_{-i})$ とする。各 $i$ について、$i$ を罰する行動 $\alpha^{(i)}_{-i}$ を 1 つ固定する。戦略の組 $\sigma$ を次で定める:誰も $a^\ast$ から外れていない間は $a^\ast$ を選ぶ。ある期に初めて、ちょうど 1 人の参加者 $i$ だけが $a^\ast_i$ と異なる行動をとったら、以後 $i$ 以外は永久に $\alpha^{(i)}_{-i}$ をとり、$i$ は任意の決まった行動をとる(2 人以上が同時に外れた場合は、何も起きなかったものとして続ける)。このとき
$$ \delta\ge\max_i\frac{d_i-v_i}{d_i-\underline v_i} $$
なら $\sigma$ は Nash 均衡で、$U(\sigma)=v$ である($d_i=v_i$ の $i$ は条件に含めない)。

外れた後の利得の上限を不動点で押さえる

要点:罰の期に入った後の継続利得は $\underline v_i$ 以下である。まだ誰も外れていない履歴での継続利得の上限 $S$ は、$S\le\max\{(1-\delta)v_i+\delta S,\ (1-\delta)d_i+\delta\underline v_i\}$ を満たし、$\delta$ の条件から $S\le v_i$ が従う。

詳しい証明を開く

全員が $\sigma$ に従えば毎期 $a^\ast$ が選ばれ、$U(\sigma)=v$ である。参加者 $i$ と任意の戦略 $\sigma_i'$ をとる。 罰の期に入った後($i$ が外れた後)の履歴 $g$ では、他の参加者は以後の履歴によらず毎期 $\alpha^{(i)}_{-i}$ を選ぶので、$i$ の各期の期待利得は $\max_{a_i}u_i(a_i,\alpha^{(i)}_{-i})=\underline v_i$ 以下で、$U_i(\sigma_i',\sigma_{-i}\mid g)\le\underline v_i$ である。 まだ誰も外れていない履歴全体での継続利得の上限を $S:=\sup_g U_i(\sigma_i',\sigma_{-i}\mid g)$ とする($\lvert u_i\rvert$ の最大値で有界)。そのような履歴 $g$ で $i$ が $a_i$ を選ぶとき、$a_i=a^\ast_i$ なら次の期も誰も外れていない履歴で、継続利得は $(1-\delta)v_i+\delta S$ 以下である。$a_i\ne a^\ast_i$ なら罰の期に入り、$(1-\delta)d_i+\delta\underline v_i$ 以下である。$\sigma_i'(g)$ はこの 2 つの平均なので$$S\le\max\{(1-\delta)v_i+\delta S,\ (1-\delta)d_i+\delta\underline v_i\}.$$ ここで $\delta$ の条件は $(1-\delta)d_i+\delta\underline v_i\le v_i$ と同値である。$S>v_i$ と仮定すると $(1-\delta)v_i+\delta S< S$ なので、右辺の最大は第 2 項で $S\le v_i$ となり矛盾する。よって $S\le v_i$ で、とくに $U_i(\sigma_i',\sigma_{-i})\le v_i=U_i(\sigma)$ である。$\square$

この $\sigma$ は一般に部分ゲーム完全均衡ではない。罰する側が $\alpha^{(i)}_{-i}$ をとり続けることが、罰する側にとって損になりうるからである(ex-ft-asym)。

凸結合と平均利得

$v\in V$ が $u(A)$ の点の有理数の重みの凸結合なら、重みに比例した回数だけ純粋行動の組を並べた周期で回すと、$\delta\to1$ で割引利得は $v$ に近づく。割引利得でちょうど $v$ を実現する構成には、全員が見る共通のくじ(公開の乱数)を使うものが多い。共通のくじを使わずに済ませる結果に FM91 がある。割引の代わりに長期平均 $\lim_{T\to\infty}\frac1T\sum_{t< T}u_i(a^t)$ を利得とすると、$V$ の点で $v_i\ge\underline v_i$ を満たすものはすべて Nash 均衡の平均利得になり、逆も成り立つ(KP17 Theorem 6.4.10、p. 133)。

部分ゲーム完全均衡の版

thm-ft-nash の罰は、罰する側にも損をさせることがあり、部分ゲームでの最適性を欠く。罰の期にも全員が最適に行動するように罰を作り直す。最も簡単なのは、段階ゲームの Nash 均衡を罰に使う方法である。

Friedman の定理(Nash 均衡に戻す罰)

$\alpha^e$ を段階ゲーム $G$ の(混合戦略の)Nash 均衡、$e_i:=u_i(\alpha^e)$ とする。$a^\ast\in A$、$v:=u(a^\ast)$ がすべての $i$ で $v_i>e_i$ を満たすとし、$d_i:=\max_{a_i}u_i(a_i,a^\ast_{-i})$ とする。戦略の組 $\sigma$ を「これまで毎期 $a^\ast$ が選ばれていれば $a^\ast$ を、そうでなければ $\alpha^e$ を選ぶ」と定める。このとき
$$ \sigma\text{ が部分ゲーム完全均衡}\iff\delta\ge\max_i\frac{d_i-v_i}{d_i-e_i} $$
である($d_i=v_i$ の $i$ は右辺に含めない)。$U(\sigma)=v$ である。

この罰の作り方は Friedman(Fri71)に帰せられる(FM86 のワーキングペーパー版の Theorem C、p. 11)。

一段逸脱を 2 種類の履歴で調べる

thm-ft-one-shot により、すべての履歴で一段逸脱が得にならないことを調べればよい。履歴は 2 種類ある。
罰の期の履歴(どこかで $a^\ast$ 以外が選ばれた後)。 この後 $\sigma$ は履歴によらず毎期 $\alpha^e$ を選ぶので、従えば継続利得は $e_i$ である。$a_i$ に一段逸脱しても、翌期以降はやはり $\alpha^e$ が選ばれ、継続利得は $(1-\delta)u_i(a_i,\alpha^e_{-i})+\delta e_i$ である。$\alpha^e$ は Nash 均衡なので $u_i(a_i,\alpha^e_{-i})\le e_i$ で、これは $e_i$ 以下である。
協調の期の履歴(これまで毎期 $a^\ast$)。 従えば継続利得は $v_i$ である。$a_i\ne a^\ast_i$ に一段逸脱すると、翌期から罰の期になり、継続利得は $(1-\delta)u_i(a_i,a^\ast_{-i})+\delta e_i$ である。その最大は $(1-\delta)d_i+\delta e_i$ で、
$$ (1-\delta)d_i+\delta e_i\le v_i\iff(d_i-e_i)\,\delta\ge d_i-v_i $$
である。$d_i\ge v_i>e_i$ なので、$d_i>v_i$ の $i$ ではこれは $\delta\ge\frac{d_i-v_i}{d_i-e_i}$ と同値で、$d_i=v_i$ の $i$ ではつねに成り立つ。
よって、$\delta$ が条件を満たせばどの一段逸脱も得にならず、$\sigma$ は部分ゲーム完全均衡である。逆に条件が満たされない $i$ があれば、空の履歴での最大を与える一段逸脱が得になるので、$\sigma$ は部分ゲーム完全均衡でない。$\square$

$v_i\le e_i$ の参加者がいる $v$ には、この罰は使えない。2 人の場合は、互いに相手を罰する期間を有限にし、罰の期に外れたら罰をやり直すことで、最小最大値を上回る利得まで広げられる。

Fudenberg–Maskin の定理(2 人、純粋行動の罰)

$k=2$ とする。$a^\ast\in A$、$v:=u(a^\ast)$ が $v_1>\hat v_1$、$v_2>\hat v_2$ を満たすとし、$d_i:=\max_{a_i}u_i(a_i,a^\ast_{-i})$ とする。$m_1\in A_1$ を $\max_{a_2}u_2(m_1,a_2)=\hat v_2$ となるように、$m_2\in A_2$ を $\max_{a_1}u_1(a_1,m_2)=\hat v_1$ となるようにとり、$m:=(m_1,m_2)$、$w:=u(m)$ とおく。整数 $L\ge1$ を
$$ L\,(v_i-w_i)>d_i-v_i\qquad(i=1,2) $$
となるようにとる。戦略の組 $\sigma$ を、状態 $\mathrm A$(協調)と $\mathrm B_r$(残り $r$ 期の罰、$r=1,\dots,L$)で定める。初めは $\mathrm A$ である。

  • 状態 $\mathrm A$ では $a^\ast$ を選ぶ。選ばれた組が $a^\ast$ なら $\mathrm A$ に留まり、そうでなければ $\mathrm B_L$ に移る。
  • 状態 $\mathrm B_r$ では $m$ を選ぶ。選ばれた組が $m$ なら $\mathrm B_{r-1}$($r=1$ なら $\mathrm A$)に移り、そうでなければ $\mathrm B_L$ に移る。
    このとき、$i=1,2$ について
    $$ \text{(a)}\ \ (\delta+\delta^2+\dots+\delta^L)(v_i-w_i)\ge d_i-v_i,\qquad \text{(b)}\ \ \delta^L(v_i-w_i)\ge\hat v_i-w_i $$
    を満たす $\delta$ では、$\sigma$ は部分ゲーム完全均衡で $U(\sigma)=v$ である。(a)(b) は $\delta$ が 1 に十分近ければ成り立つ。

$w_i\le\hat v_i< v_i$ である($m_j$ は $i$ を罰するので $w_i=u_i(m_i,m_j)\le\max_{a_i}u_i(a_i,m_j)=\hat v_i$)。$\delta\to1$ で (a) の左辺は $L(v_i-w_i)>d_i-v_i$ に、(b) の左辺は $v_i-w_i>\hat v_i-w_i$ に近づくので、最後の主張が従う。この罰の作り方(互いに罰し合い、罰の期の逸脱で罰をやり直す)は Fudenberg と Maskin(FM86)による。

2 種類の状態で一段逸脱を比べる

thm-ft-one-shot により、各状態で一段逸脱が得にならないことを示せばよい。$\sigma$ は純粋戦略なので、状態 $\mathrm B_r$ の履歴から従えば、$r$ 期は $w$、以後は $v$ が続き、継続利得は $(1-\delta^r)w_i+\delta^rv_i$ である。罰が始まる直前の時点から見た「$L$ 期の罰の後に協調」の継続利得は $(1-\delta^L)w_i+\delta^Lv_i$ である。
状態 $\mathrm A$。 $a_i\ne a^\ast_i$ に一段逸脱すると、その期の利得は $d_i$ 以下で、翌期から $\mathrm B_L$ に入る。継続利得の差は
$$ v_i-\bigl[(1-\delta)d_i+\delta(1-\delta^L)w_i+\delta^{L+1}v_i\bigr] =(1-\delta)(v_i-d_i)+(\delta-\delta^{L+1})(v_i-w_i) $$
である。$\delta-\delta^{L+1}=(1-\delta)(\delta+\dots+\delta^L)$ なので、これは $(1-\delta)\bigl[(\delta+\dots+\delta^L)(v_i-w_i)-(d_i-v_i)\bigr]$ に等しく、(a) より $0$ 以上である。
状態 $\mathrm B_r$($1\le r\le L$)。 相手 $j$ は $m_j$ を選ぶので、$i$ がどの $a_i$ に一段逸脱しても、その期の利得は $\max_{a_i}u_i(a_i,m_j)=\hat v_i$ 以下である。$a_i\ne m_i$ なら翌期から $\mathrm B_L$ に入り直すので、継続利得は $(1-\delta)\hat v_i+\delta(1-\delta^L)w_i+\delta^{L+1}v_i$ 以下である。従ったときとの差は
$$ (1-\delta^r)w_i+\delta^rv_i-(1-\delta)\hat v_i-(\delta-\delta^{L+1})w_i-\delta^{L+1}v_i =(1-\delta)(w_i-\hat v_i)+(\delta^r-\delta^{L+1})(v_i-w_i) $$
である($w_i$ の係数 $1-\delta^r-\delta+\delta^{L+1}$ を $(1-\delta)-(\delta^r-\delta^{L+1})$ と書き直した)。$r\le L$ なので $\delta^r-\delta^{L+1}\ge\delta^L-\delta^{L+1}=\delta^L(1-\delta)$、また $v_i-w_i>0$ だから、差は
$$ (1-\delta)\bigl[\delta^L(v_i-w_i)-(\hat v_i-w_i)\bigr] $$
以上で、(b) より $0$ 以上である。
どの状態でも一段逸脱は得にならないので、$\sigma$ は部分ゲーム完全均衡である。初めの状態は $\mathrm A$ なので $U(\sigma)=v$ である。$\square$

罰の期の議論の要点は、罰を受ける側はどう外れてもその期に $\hat v_i$ 以下しか得られず罰が延びるだけであり、罰する側の損($w_i$)は、罰を終えて協調に戻る価値 $v_i$ で償われる、ということである。

一般の形とワーキングペーパー版の番号

FM86 のワーキングペーパー版(MIT 経済学部、1984 年)は、各参加者が相手の過去の混合行動を観測でき、全員が見る共通のくじを使えると仮定して(§II)、次を述べる。

  • 2 人なら、$V$ の点で $v_i>\underline v_i$(混合行動での最小最大値)を満たすものは、$\delta$ が 1 に十分近ければ部分ゲーム完全均衡の利得になる(Theorem 1、p. 15)。
  • $k$ 人で、$\{v\in V\mid v_i>\underline v_i\ \forall i\}$ の次元が $k$ なら同じことが成り立つ(Theorem 2、p. 18)。
  • Theorem 2 は、混合行動でなく実際の行動だけが観測される場合にも成り立つ(Theorem 6、p. 33)。
    thm-ft-fm-two は、罰する行動を純粋行動に限ることで観測の問題を避け、共通のくじを使わずに純粋行動の組の利得だけを扱った特別な場合である。

3 人以上での反例

次元の条件が欠けた 3 人の例

$k=3$、$A_i=\{0,1\}$ とし、全員が同じ行動を選んだときは全員の利得が $1$、そうでなければ全員の利得が $0$ とする。このとき $\underline v_i=0$、$V=\{(x,x,x)\mid0\le x\le1\}$ で、$0< x<\frac14$ の $(x,x,x)$ は狭義に個人合理的である。しかし、どの $\delta\in(0,1)$ についても、$G^\infty(\delta)$ のすべての部分ゲーム完全均衡で各参加者の利得は $\frac14$ 以上である(FM86 のワーキングペーパー版の例、pp. 17–18)。

最も悪い均衡を下から押さえる

要点:部分ゲーム完全均衡の利得の下限を $\beta$ とする。最初の期に、ある参加者は期待利得 $\frac14$ 以上の行動をもち、続きの利得は $\beta$ 以上なので $\beta\ge(1-\delta)\frac14+\delta\beta$、すなわち $\beta\ge\frac14$ である。

詳しい証明を開く

他の 2 人が異なる行動を選べば参加者 $i$ の利得はどの行動でも $0$ なので $\underline v_i=0$ である。利得の組は $(0,0,0)$ か $(1,1,1)$ なので $V$ は線分である。 全員が履歴によらず毎期 $0$ を選ぶ組は、一段逸脱で利得が $1$ から $0$ に下がるだけなので(thm-ft-one-shot)、部分ゲーム完全均衡である。よって部分ゲーム完全均衡の全体は空でなく、全員の利得はつねに等しいので、$\beta:=\inf_\sigma U_1(\sigma)\in[0,1]$(下限は部分ゲーム完全均衡 $\sigma$ 全体)が定まる。 部分ゲーム完全均衡 $\sigma$ をとり、空の履歴で参加者 $j$ が $0$ を選ぶ確率を $p_j$ とする。3 つの数 $p_1,p_2,p_3$ のうち 2 つは、ともに $\frac12$ 以上か、ともに $\frac12$ 以下である。その 2 人を $j,l$、残りを $i$ とする。$p_j,p_l\ge\frac12$ なら、$i$ が $0$ を選ぶとその期の期待利得は $p_jp_l\ge\frac14$ である。$p_j,p_l\le\frac12$ なら、$i$ が $1$ を選ぶと $(1-p_j)(1-p_l)\ge\frac14$ である。 この行動 $a_i$ への空の履歴での一段逸脱を考える。翌期以降の続きは、1 期目の行動の組 $a$ を履歴とする $\sigma\vert_{(a)}$ で、これは部分ゲーム完全均衡なので継続利得は $\beta$ 以上である。よって一段逸脱の利得は $(1-\delta)\frac14+\delta\beta$ 以上で、$\sigma$ が部分ゲーム完全均衡であることから$$U_1(\sigma)=U_i(\sigma)\ge(1-\delta)\tfrac14+\delta\beta$$である。$\sigma$ について下限をとると $\beta\ge(1-\delta)\frac14+\delta\beta$、すなわち $\beta\ge\frac14$ である。$\square$

この例では、ある参加者を罰すると他の 2 人も同じだけ損をするので、罰する側を罰の期の後に報いて償うことができない。$V$ が線分で、rem-ft-fm-general の次元の条件を満たさないことがその表れである。

例題

囚人のジレンマ

ゲーム理論 の例「均衡が全員にとって最善でない例」の利得($(\mathrm C,\mathrm C)=(3,3)$、$(\mathrm C,\mathrm D)=(0,5)$、$(\mathrm D,\mathrm C)=(5,0)$、$(\mathrm D,\mathrm D)=(1,1)$)を段階ゲームとする。
答え:$\underline v=\hat v=(1,1)$、段階ゲームの Nash 均衡は $(\mathrm D,\mathrm D)$ だけで $e=(1,1)$ である。「誰かが裏切るまで協調し、以後ずっと裏切る」組(thm-ft-friedman で $a^\ast=(\mathrm C,\mathrm C)$)は、$\delta\ge\frac{5-3}{5-1}=\frac12$ のとき、かつそのときに限り部分ゲーム完全均衡で、利得は $(3,3)$ である。

途中の計算を開く

相手が C を確率 $q$ で選ぶとき、C の利得は $3q$、D の利得は $5q+(1-q)=4q+1$ で、D の方がつねに大きい。最大値 $4q+1$ は $q=0$ で最小値 $1$ をとるので $\underline v_i=1$、純粋行動に限っても $1$ である。$d_i=\max\{u_i(\mathrm C,\mathrm C),u_i(\mathrm D,\mathrm C)\}=5$、$v_i=3$、$e_i=1$ を thm-ft-friedman の式に入れる。最小最大値と段階ゲームの均衡の利得が一致するので、この例では thm-ft-nash と thm-ft-friedman の範囲は同じである。

段階ゲームの均衡より低い利得

2 人のゲームで、参加者 1 の行動を $\mathrm T,\mathrm B$、参加者 2 の行動を $\mathrm L,\mathrm R$ とし、利得を $(\mathrm T,\mathrm L)=(0,0)$、$(\mathrm T,\mathrm R)=(3,1)$、$(\mathrm B,\mathrm L)=(0,0)$、$(\mathrm B,\mathrm R)=(1,3)$ とする。$a^\ast=(\mathrm B,\mathrm R)$、$v=(1,3)$ を実現したい。
答え:段階ゲームの Nash 均衡は $(\mathrm T,\mathrm R)$ だけで $e=(3,1)$ なので $v_1< e_1$ で、thm-ft-friedman は使えない。thm-ft-nash の組も部分ゲーム完全均衡でない。一方 $\hat v=\underline v=(0,1)$ で、thm-ft-fm-two は $m=(\mathrm T,\mathrm L)$、$L=3$ で使え、$\delta\ge\delta_0\approx0.8105$($\delta_0$ は $\delta+\delta^2+\delta^3=2$ の正の解)なら $v=(1,3)$ が部分ゲーム完全均衡の利得になる。

途中の計算を開く

参加者 2 にとって R は L より真に良い($1>0$、$3>0$)ので、どの均衡でも R を選び、それに対する参加者 1 の最適反応は T である。最小最大値:参加者 2 が L を選べば参加者 1 の利得は $0$ で、利得はすべて $0$ 以上なので $\underline v_1=\hat v_1=0$($m_2=\mathrm L$)。参加者 1 が T を確率 $p$ で選ぶとき参加者 2 の最大の利得は $\max\{0,\,p+3(1-p)\}=3-2p\ge1$ で、$p=1$ で $1$ になるので $\underline v_2=\hat v_2=1$($m_1=\mathrm T$)。$w=u(\mathrm T,\mathrm L)=(0,0)$、$d=(3,3)$。$L(v_1-w_1)>d_1-v_1$ は $L>2$ で $L=3$。(a) は参加者 1 で $\delta+\delta^2+\delta^3\ge2$、参加者 2 では $d_2-v_2=0$ で自明。(b) は参加者 1 で $\delta^3\ge0$、参加者 2 で $\delta^3\ge\frac13$($\delta\ge0.6934$)。thm-ft-nash の組では、参加者 1 が外れた後、参加者 2 は毎期 L を選んで利得 $0$ を得るが、その期だけ R に替えると利得が $1$ 以上になり以後は変わらないので、一段逸脱が得になる。

使える条件と反例

外す条件反例成り立たなくなる結論
$\delta$ が 1 に十分近いことex-ft-pd で $\delta<\frac12$$(3,3)$ が均衡の利得になること(thm-ft-nash、thm-ft-friedman)
無限に繰り返すことex-ft-pd を $T$ 回だけ繰り返す$(3,3)$ が部分ゲーム完全均衡の利得になること
個人合理性 $v_i>\underline v_i$ex-ft-pd の $v=(0,5)=u(\mathrm C,\mathrm D)$$v$ が均衡の利得になること
2 人であること(rem-ft-fm-general の Theorem 1)prop-ft-three狭義に個人合理的な $v$ が部分ゲーム完全均衡の利得になること
表の反例の確かめ

1 行目は Nash 均衡にもならず、2 行目は部分ゲーム完全均衡では毎期 $(\mathrm D,\mathrm D)$ になる。

確認を開く

1 行目:毎期 $(\mathrm C,\mathrm C)$ でない期が正の確率であると、2 人の利得の和は $6$ 未満になるので、利得 $(3,3)$ の均衡では毎期確率 $1$ で $(\mathrm C,\mathrm C)$ が選ばれる。参加者 1 が最初から毎期 D を選ぶ戦略に替えると、1 期目は $5$、以後は相手の行動によらず毎期 $1$ 以上を得るので、利得は $5(1-\delta)+\delta=5-4\delta$ 以上で、$\delta< \frac12$ では $3$ を超える。よって $(3,3)$ は Nash 均衡の利得にもならない。2 行目:最後の期では、履歴によらず D が真に良いので、部分ゲーム完全均衡では最後の期に両者が D を選ぶ。すると最後から 2 番目の期の選択は最後の期の結果を変えないので、そこでも D が真に良い。これを逆にたどると、どの期にも両者が D を選び、利得は $(1,1)$ になる(KP17 p. 129 にも同じ議論がある)。3 行目:$v_1=0< 1=\underline v_1$ なので、prop-ft-necessary により、どの $\delta$ でも Nash 均衡の利得にならない。4 行目:prop-ft-three で $0< x< \frac14$ の $(x,x,x)$ をとる。これは $V$ の点だが純粋行動の組の利得ではない。

よくある誤り

誤り正しくはなぜ
繰り返せば協調が唯一の均衡になる協調は多数の均衡の 1 つにすぎず、毎期裏切る組も部分ゲーム完全均衡である段階ゲームの Nash 均衡を履歴によらず繰り返す組は部分ゲーム完全均衡
永久に最小最大で罰する組は部分ゲーム完全均衡罰する側が損をして外れたがることがあるex-ft-asym
何回でも、有限回繰り返せば協調できる段階ゲームの Nash 均衡が 1 つなら、有限回では協調できない反例の表の 2 行目
何人でも最小最大値を上回る利得は実現できる3 人以上では次元の条件などが要るprop-ft-three
$\delta$ の大きさは問題にならない割引が強いと協調は均衡にならない反例の表の 1 行目

補足

名前と歴史

フォーク定理は学術誌に現れる前から研究者の間で知られていた(KP17 p. 135 の注)。割引のない場合の部分ゲーム完全均衡の版は Aumann–Shapley と Rubinstein に、段階ゲームの Nash 均衡に戻す罰の版は Friedman(Fri71)に帰せられる(FM86 のワーキングペーパー版の Theorem B、Theorem C、pp. 10–11)。割引のある部分ゲーム完全均衡の一般の版は Fudenberg と Maskin(FM86)による。

関連項目

参考文献

[1]
Anna R. Karlin, Yuval Peres, Game Theory, Alive, American Mathematical Society, 2017, 著者公開版(2016 年 12 月 13 日)の番号:§6.4(p. 129、有限回の囚人のジレンマと割引の解釈)、Definition 6.4.7(pp. 131–132)、Definition 6.4.8(p. 132)、Theorem 6.4.10(p. 133)、第 6 章の注(p. 135)

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