摂動完全均衡

摂動完全均衡 (せつどうかんぜんきんこう，英: trembling hand perfect equilibrium, 独: trembling-hand-perfektes Gleichgewicht) とは，ナッシュ均衡の精緻化のひとつ．1975 年に International Journal of Game Theory 誌に掲載された論文において，“A Model of Slight Mistakes” (軽微な誤りのモデル) の名前で，ラインハルト・ゼルテンによってこの概念が発見された．ここでの狙いは，均衡はプレーヤーたちの誤りによってどの程度影響されるかを決定することである．ゼルテンによれば，プレーヤーたちが完全に合理的に行動するならば，誤りは起こらない．しかし現実では，人びとは相手のプレーヤーの誤った決定を計算に入れねばならない．この点をゲーム理論的に表現するために，摂動完全均衡が生みだされた． 簡単な表現で摂動完全均衡のアイデアを説明しよう．プレーヤー A が，プレーヤー B はかならず戦略 b1 をとってくると考えているとして，その b1 へのプレーヤー A の最適反応は戦略 a1 であるとしよう．戦略 a1 をプレーすることは，もしプレーヤー B が小さな誤り確率 ε で b2 をプレーしてくるとしても，なお最適な選択でありつづけるだろうか．そのような条件でもなお a1 がプレーヤー A の最適戦略であるならば，これは摂動完全均衡戦略であるという． 右の利得行列をもつ正規形ゲームによって，摂動完全均衡のアプローチが非常に簡単に説明できる． この例における 2 つのナッシュ均衡は (a1, b1) と (a2, b2) である．このどちらが (あるいは両方が) 摂動完全均衡であるかを検討しよう．プレーヤー A は戦略 a1 をプレーしたいと思い，かつプレーヤー B は戦略 b1 をプレーするとすると，両者は 3 の利得を得ることになる．しかしプレーヤー A が，プレーヤー B は小さな誤り確率で戦略 b2 をプレーしてこないともかぎらないというふうに不確かに思う．a1 が，このプレーヤー 2 の誤り確率があってもなおプレーヤー 1 の最適な選択であり，したがって摂動完全である，ということを確かめるには，次のことを確認しなければならない：プレーヤー 1 が a1 を選んだときの期待利得が，a2 を選んだときの期待利得以上である． ε をプレーヤー B の誤り確率とし，これは非常に小さいものと仮定する．すなわち，その余事象の確率 (正しくプレーする確率) が 1 − ε である．ここで 0 < ε < 1 とする． すると，a1 を選んだときのプレーヤー 1 の期待利得は， E [ u ( a 1 ) ] = ( 1 − ε ) u ( a 1 , b 1 ) + ε u ( a 1 , b 2 ) = ( 1 − ε ) ⋅ 3 + ε ⋅ 5 {\displaystyle {\begin{aligned}\mathrm {E} [u(a_{1})]&=(1-\varepsilon )u(a_{1},b_{1})+\varepsilon u(a_{1},b_{2})\\&=(1-\varepsilon )\cdot 3+\varepsilon \cdot 5\end{aligned}}} であり，反対に，戦略 a2 からの期待利得は， E [ u ( a 2 ) ] = ( 1 − ε ) u ( a 2 , b 1 ) + ε u ( a 2 , b 2 ) = ( 1 − ε ) ⋅ ( − 2 ) + ε ⋅ 5 {\displaystyle {\begin{aligned}\mathrm {E} [u(a_{2})]&=(1-\varepsilon )u(a_{2},b_{1})+\varepsilon u(a_{2},b_{2})\\&=(1-\varepsilon )\cdot (-2)+\varepsilon \cdot 5\end{aligned}}} である．次のことが簡単にわかる： ( 1 − ε ) ⋅ 3 + ε ⋅ 5 > ( 1 − ε ) ⋅ ( − 2 ) + ε ⋅ 5 {\displaystyle (1-\varepsilon )\cdot 3+\varepsilon \cdot 5>(1-\varepsilon )\cdot (-2)+\varepsilon \cdot 5} . また，プレーヤー B が小さな誤り確率で b2 をプレーするならば，プレーヤー 1 にとって a1 は最適な選択である．したがって，戦略 a1 は摂動完全である．しかし，摂動完全均衡は 2 つの摂動完全な戦略の組みあわせからなるものである．したがって，戦略プロファイル (a1, b1) が摂動完全均衡であることを示すには，プレーヤー 2 の b1 についても確かめなければならない．戦略 a1 のときと同様に，次のことが示される． b1 を選んだときのプレーヤー 2 の期待利得は， E [ u ( b 1 ) ] = ( 1 − ε ) u ( a 1 , b 1 ) + ε u ( a 2 , b 1 ) = ( 1 − ε ) ⋅ 3 + ε ⋅ ( − 2 ) {\displaystyle {\begin{aligned}\mathrm {E} [u(b_{1})]&=(1-\varepsilon )u(a_{1},b_{1})+\varepsilon u(a_{2},b_{1})\\&=(1-\varepsilon )\cdot 3+\varepsilon \cdot (-2)\end{aligned}}} であり，反対に，戦略 b2 からの期待利得は， E [ u ( b 2 ) ] = ( 1 − ε ) u ( a 1 , b 2 ) + ε u ( a 2 , b 2 ) = ( 1 − ε ) ⋅ 0 + ε ⋅ 0 {\displaystyle {\begin{aligned}\mathrm {E} [u(b_{2})]&=(1-\varepsilon )u(a_{1},b_{2})+\varepsilon u(a_{2},b_{2})\\&=(1-\varepsilon )\cdot 0+\varepsilon \cdot 0\end{aligned}}} である．ふたたび，明らかに， 0 < ( 1 − ε ) ⋅ 3 + ϵ ⋅ ( − 2 ) = 3 − 5 ⋅ ε {\displaystyle 0<(1-\varepsilon )\cdot 3+\epsilon \cdot (-2)=3-5\cdot \varepsilon } . したがって戦略 b1 も摂動完全であり，ナッシュ均衡 (a1, b1) は摂動完全均衡である． 変動ゲーム (perturbed game, perturbiertes Spiel) とは，もとになるゲームのコピーであって，どのプレーヤーもすべての純粋戦略を正の確率でプレーしなければならないという制限を加えたものである．すなわち，ふつうのゲームではプレーヤー A は自分の戦略を 0 ≤ ε ≤ 1 でプレーすることができるところ，変動ゲームでは ε > 0 でなければならない． 次の戦略形ゲームから始める： G = ⟨ I , ( M i ) i ∈ I , ( P i ) i ∈ I ⟩ {\displaystyle G=\langle I,(M_{i})_{i\in I},(P_{i})_{i\in I}\rangle } . ここで I はプレーヤーの集合を表し，Mi は純粋戦略 Si 上の確率分布からなる混合戦略の集合，そして Pi はプレーヤー i の期待利得関数である． プレーヤーの起こしうる誤りを描くための中心的なアイデアは，どの純粋戦略も 0 でない確率でプレーされうる，と仮定することである．そのような変動ゲームでは，ni 個の純粋戦略をもった各プレーヤー i ∈ I について， ε i = ( ε i 1 , ε i 2 , . . . , ε i n i ) {\displaystyle \varepsilon _{i}=(\varepsilon _{i}^{1},\varepsilon _{i}^{2},...,\varepsilon _{i}^{n_{i}})} を，正の確率の集合であって次をみたすものとする： ε i ≫ 0 , ∑ j = 1 n i ε i j < 1 {\displaystyle \varepsilon _{i}\gg 0,\;\sum _{j=1}^{n_{i}}\varepsilon _{i}^{j}<1} . したがって，変動ゲームにおける混合戦略の集合は， M i ε = { m i ∈ M i ∣ m i k ≥ ε i k , k = 1 , … , n i } {\displaystyle M_{i}^{\varepsilon }=\{m_{i}\in M_{i}\mid m_{i}^{k}\geq \varepsilon _{i}^{k},k=1,\ldots ,n_{i}\}} , すなわち，プレーヤー i ∈ I はその k 番めの戦略について，少なくとも ε i k {\displaystyle \varepsilon _{i}^{k}} の確率でプレーしなければならないようなものである．以上から，変動ゲームは， G ( ε ) = ⟨ I , ( M i ε ) i ∈ I , ( P i ) i ∈ I ⟩ {\displaystyle G(\varepsilon )=\langle I,(M_{i}^{\varepsilon })_{i\in I},(P_{i})_{i\in I}\rangle } となる． 変動ゲームにおけるナッシュ均衡を m* (ε) とし，極限ゲームでのナッシュ均衡を m* とする．変動ゲームにおける誤り確率 ε を 0 に近づけていき，それによって変動ゲームにおける均衡がもとの正規形ゲームにおけるものに一致するならば，これを摂動完全均衡であるという．形式的に表現すると， lim ε → 0 m ∗ ( ε ) = m ∗ {\displaystyle \lim _{\varepsilon \to 0}m^{*}(\varepsilon )=m^{*}} であるとき，摂動完全均衡であるという． はじめのゲームとして，右の利得行列をもつ正規形ゲームを考える． 正規形ゲームでは 2 つのナッシュ均衡戦略プロファイル，(a1, b1), (a2, b2) がある．ここでは両プレーヤーにとって，それぞれの相手のプレーヤーの選ぶ戦略に対して相互に最適になっている． 変動ゲームにおいてはそれは成りたたない．プレーヤー B が戦略 b1 を選ぶ確率が0より大ならば，プレーヤー A にとっての最適反応は確率 a1 = 1 でプレーすることである．変動ゲームでは定義によってこの確率は存在するので，プレーヤー A はかならず a1 = 1 をプレーすることになる．しかしプレーヤー A も変動ゲームでは戦略 a2 を正の確率でプレーしなければならない．したがってプレーヤー A の最適反応は，混合戦略 a 2 = a 2 m i n {\displaystyle a_{2}=a_{2}^{\rm {min}}} , すなわち a2 を最小限の確率でプレーすることである． ゲームの対称性から，プレーヤー B にとっての最適戦略は，同様に b 2 = b 2 m i n {\displaystyle b_{2}=b_{2}^{\rm {min}}} となる． したがって，変動ゲームにおける均衡は， ( 1 − a 2 m i n , a 2 m i n ) , ( 1 − b 2 m i n , b 2 m i n ) {\displaystyle (1-a_{2}^{\rm {min}},a_{2}^{\rm {min}}),(1-b_{2}^{\rm {min}},b_{2}^{\rm {min}})} . いま， a 2 m i n {\displaystyle a_{2}^{\rm {min}}} と b 2 m i n {\displaystyle b_{2}^{\rm {min}}} を 0 に近づけたならば，変動ゲームから得られるのはふたたびもとのゲームにほかならない： lim a 2 m i n , b 2 m i n → 0 ( ( 1 − a 2 m i n , a 2 m i n ) , ( 1 − b 2 m i n , b 2 m i n ) ) = ( ( 1 , 0 ) , ( 1 , 0 ) ) = ( a 1 , b 1 ) {\displaystyle \lim _{a_{2}^{\rm {min}},b_{2}^{\rm {min}}\to 0}\left((1-a_{2}^{\rm {min}},a_{2}^{\rm {min}}),(1-b_{2}^{\rm {min}},b_{2}^{\rm {min}})\right)=((1,0),(1,0))=(a_{1},b_{1})} 誤り確率を 0 に近づけ，変動ゲームの均衡がもとのゲームのナッシュ均衡に近づくならば，この均衡は摂動完全均衡である． この例では，変動ゲームは均衡 (a1, b1) に向かい，したがってこれは摂動完全均衡である． 逐次手番ゲームに対しても，摂動完全均衡の概念を応用できる．正規形ゲームの場合と同じようにこの場合も，部分ゲーム完全均衡からのふるいわけには，小さな誤り確率があっても残るものを探しだすことが有用である． 右のものには 4 つの部分ゲーム完全均衡がある．(A, (X, X)), すなわち，プレーヤー 1 は戦略 A をプレーし，プレーヤー 2 は，プレーヤー 1 が A を選んだならば X を，プレーヤー 1 が B を選んだときにも X を選ぶようなものである．ほかの 3 つの部分ゲーム完全均衡は，(A, (Y, X)), (B, (X, X)), (B, (Y, X)). このうち，プレーヤー 1 が戦略 A を選んでいるような 2 つの均衡だけが摂動完全である．プレーヤー 2 が戦略 Y をプレーする確率は十分小さいのだとしても，プレーヤー 1 にとってはやはり A をプレーすることがよりよい．というのもそうすればかならず 2 の利得が得られ，戦略 B を選んだ場合には戦略 A による場合よりも決してよい結果にはならないからである． したがって，摂動完全均衡は (A, (X, X)) と (A, (Y, X)) の 2 つになる． ゲーム理論家エロン・コールベルグによるもので，ここでわずかな修正を施した Dalekspiel が，摂動完全均衡のさらなる応用の例になる．展開形ゲームを正規形ゲームに還元するさいに起こる情報の減少を補うため，1953 年の論文でハロルド・クーンはエージェント標準形 (Agentennormalform) を用いた．右に示した Dalekspiel において，プレーヤー 1 は，それぞれの決定節で相関のない意思決定をするよう数学的に記述するために，2 人のエージェントに分割される． 正規形では，純粋戦略の範囲で (gl, R), (gr, R), (ul, L) という 3 つのナッシュ均衡があることが簡単にわかる．いまこれらの均衡が摂動完全であるかを確かめるためには，プレーヤー 1 の 2 つの決定節における誤り確率が相互に相関していないことを保証せねばならない．すなわち，最初の決定節における誤りが，第 2 の決定節における確率を高めたり低めたりしてはならない．このことを保証するため，プレーヤー 1 は，右に示したように，独立して決定を行う 2 人のエージェントに分割されている． ここで，次のように仮定する： 第 1 のエージェント (Sp1A) は，小さな誤り確率 ε で，g でなく u をプレーしてしまう． 同様に，第 2 のエージェント (Sp1B) は，小さな誤り確率 δ で，r でなく l をプレーしてしまう． 最後に，プレーヤー 2 は，小さな誤り確率 λ で，R でなく L をプレーしてしまう． このように定められた確率のもとで，前記の正規形は右のようになる (周辺に確率を付記した第 2 の表)． いまや，小さな λ に対して，プレーヤー 1 には戦略 gr および gl が摂動完全戦略であることが簡単に見てとれる．したがってプレーヤー 1 は，プレーヤー 2 がどのように意思決定したとしても等しい，2 の安全な利得を得る．ul を選ぶことによって得られる唯一のよい利得は 4 だが，確率にもとづいて，期待値で得られる利得は， E [ u ( u l ) ] = ( 1 − λ ) ⋅ 0 + λ ⋅ 4 {\displaystyle \mathrm {E} [u(ul)]=(1-\lambda )\cdot 0+\lambda \cdot 4} となる．そして λ < 0.5 のときこの期待値は gr および gl が与えるものよりも悪い． プレーヤー 2 にとっても戦略 R は摂動完全である．なぜならば，プレーヤー 2 が R を選ぶよりも L を選ぶほうが利得が大きくなるような唯一の戦略の組みあわせは (ul, R) に比べたときの (ul, L) だけであって，ところが ul が実現するのは，プレーヤー 1 の両方のエージェントが誤りを犯した場合であり，その ul の確率は最小の εδ だからである． したがって 2 つの均衡 (gr, R), (gl, R) は摂動完全均衡である．いま見たように戦略 ul は摂動完全戦略ではなかったので，(ナッシュ) 均衡 (ul, L) は摂動完全均衡ではない． ラインハルト・ゼルテン ゲーム理論 ナッシュ均衡 部分ゲーム完全均衡 展開形ゲーム 標準形ゲーム Reinhard Selten (1975). “A reexamination of the perfectness concept for equilibrium points in extensive games”. International Journal of Game Theorie (Vienna: Physica-Verlag): 25 - 55.  Harold William Kuhn (1953). “Extensive Games and the Problem of Informations”. Contribution to the Theorie of Games, Vol. 2 (Princeton: Princeton Univ. Press): 193 - 216.  Elon Kohlberg, Jean-Francois Mertens (1986). On the Strategic Stability of Equilibria. Econometrica. pp. 1003 - 1037  Robert Gibbons (1992). A Primer in Game Theory. Harlow: Financial Times  Thomas Riechmann (2010). Spieltheorie (3 ed.). München: Vahlen  Christian Rieck (2008). Spieltheorie (8 ed.). Eschborn: Rieck  Alexander Mehlmann (2007). Strategische Spiele für Einsteiger. Wiesbaden: Friedr. Vieweg & Sohn Verlag  Ken Binmore (1992). Fun and Games (1 ed.). Lexington: Heath  Jürgen Eichberger (2007). Game Theorie for Economists (1 ed.). Bingley: Emerald  LMU ミュンヘンのプロジェクトであるゲーム理論百科事典