サブゲーム完全均衡

ゲーム理論において、サブゲーム完全均衡（またはサブゲーム完全ナッシュ均衡）は、動的ゲームで使用されるナッシュ均衡の改良版である。戦略プロファイルは、元のゲームのすべてのサブゲームのナッシュ均衡を表す場合、サブゲーム完全均衡である。非公式には、これは、ゲームのどの時点でも、その時点以降のプレイヤーの行動は、それ以前に何が起こったかに関係なく、継続ゲーム（つまりサブゲーム）のナッシュ均衡を表すはずであることを意味する。完全想起を持つすべての有限拡張ゲームには、サブゲーム完全均衡がある。^[1]完全想起は、1953年にハロルド・W・クーンが導入した用語であり、 「各プレイヤーは、ゲームのルールによって、以前の動きで知っていたことすべてと、それらの動きでのすべての選択を記憶することが許可されているという主張と同等である」。^[2]

有限ゲームの場合にサブゲーム完全均衡を決定する一般的な方法は、後方帰納法である。ここでは、まずゲームの最後の行動を考慮し、最終動者がそれぞれの可能な状況で自分の効用を最大化するためにどの行動を取るべきかを決定する。次に、最後の行為者がこれらの行動を取ると仮定し、最後から2番目の行動を考慮し、再びその行為者の効用を最大化する行動を選択する。このプロセスは、ゲームの最初の動きに到達するまで続行される。残った戦略は、完全情報の有限時間拡大型ゲームのすべてのサブゲーム完全均衡の集合である。^[1]しかし、後方帰納法は、非シングルトン情報セットのカットスルーを伴うため、不完全情報または不完全情報 のゲームには適用できない。

サブゲーム完全均衡は必然的にワンショット偏差原理を満たします。

特定のゲームの部分ゲーム完全均衡の集合は、常にそのゲームのナッシュ均衡の集合のサブセットです。場合によっては、集合が同一になることもあります。

最後通牒ゲームは、ナッシュ均衡よりもサブゲーム完全均衡が少ないゲームの直感的な例を提供します。

後方帰納法を使用してサブゲームの完全均衡を決定する方法は、以下の図 1 に示されています。プレーヤー 1 の戦略は {Up、Uq、Dp、Dq} で与えられ、プレーヤー 2 の戦略は {TL、TR、BL、BR} の間です。この例には 4 つのサブゲームがあり、そのうち 3 つが適切なサブゲームです。

後方誘導を使用して、プレイヤーは各サブゲームで次のアクションを実行します。

• アクション p と q のサブゲーム: プレイヤー 1 は、自分の利益を最大化するために、利益 (3, 3) でアクション p を実行します。そのため、アクション L の利益は (3,3) になります。
• アクション L と R のサブゲーム: プレイヤー 2 は 3 > 2 でアクション L を実行するため、アクション D の報酬は (3, 3) になります。
• アクション T と B のサブゲーム: プレイヤー 2 は、プレイヤー 2 の利益を最大化するためにアクション T を実行するため、アクション U の利益は (1, 4) になります。
• アクション U と D のサブゲーム: プレイヤー 1 は、プレイヤー 1 の利益を最大化するためにアクション D を実行します。

したがって、サブゲームの完全均衡は{Dp, TL}であり、その利得は(3, 3)である。

不完全な情報を持つ拡張形式のゲームを、下の図 2 に示します。アクション A と B、およびそれに続くすべてのアクションを実行するプレイヤー 1 のノードはサブゲームであることに注意してください。プレイヤー 2 のノードは同じ情報セットの一部であるため、サブゲームではありません。

最初の正規形ゲームは、全体の拡張形式ゲームの正規形表現です。提供された情報に基づくと、(UA, X)、(DA, Y)、(DB, Y) はすべてゲーム全体のナッシュ均衡です。

2 番目の正規形ゲームは、アクション A と B を持つプレーヤー 1 の 2 番目のノードから始まるサブゲームの正規形表現です。2 番目の正規形ゲームの場合、サブゲームのナッシュ均衡は (A、X) です。

ゲーム全体では、ナッシュ均衡 (DA, Y) と (DB, Y) はサブゲーム完全均衡ではない。なぜなら、プレイヤー 2 の動きがナッシュ均衡を構成しないからである。ナッシュ均衡 (UA, X) は、サブゲームナッシュ均衡 (A, X) を戦略の一部として組み込んでいるため、サブゲーム完全である。^[3]

このゲームを解くには、まずサブゲーム1の相互最善の応答によるナッシュ均衡を見つけます。次に、逆帰納法を使用して(A,X) → (3,4)を代入し、(3,4)がサブゲーム2のペイオフになるようにします。^[3]

破線は、同時ゲームでプレイヤー 2 がプレイヤー 1 が A と B のどちらをプレイするかを知らないことを示しています。

プレイヤー1は、自分の利得が3 > 2であるため、DではなくUを選択します。結果として得られる均衡は(A, X) → (3,4)です。

したがって、後方誘導によるサブゲーム完全均衡は(UA, X)であり、その利得は(3, 4)である。

有限反復ゲームでは、ステージ ゲームに一意のナッシュ均衡が 1 つしかない場合、サブゲームの完全均衡は、過去の行動を考慮せずにプレイし、現在のサブゲームをワンショット ゲームとして扱うことです。この例として、有限反復囚人のジレンマゲームがあります。囚人のジレンマは、2 人の有罪の犯人がいる状況からその名前が付けられています。尋問されると、2 人には黙秘するか裏切るかの選択肢があります。2 人とも黙秘すれば、2 人とも短い刑期になります。2 人とも裏切る場合は、2 人とも中程度の刑期になります。反対の選択肢を選んだ場合は、裏切った犯人は自由になり、黙秘した犯人は長い刑期になります。最終的に、後方帰納法を使用すると、有限反復囚人のジレンマの最後のサブゲームでは、プレイヤーは一意のナッシュ均衡 (両方のプレイヤーが裏切る) をプレイする必要があります。このため、最後のサブゲームより前のすべてのゲームでも、単一期間の利得を最大化するためにナッシュ均衡が実行される。^[4] 有限反復ゲームのステージゲームに複数のナッシュ均衡がある場合、「アメとムチ」構造を通じて、非ステージゲームナッシュ均衡アクションを実行するサブゲーム完全均衡を構築できる。一方のプレイヤーは、1つのステージゲームのナッシュ均衡を使用して、非ナッシュ均衡アクションを実行するよう奨励し、他方のプレイヤーが裏切ることを選択した場合は、そのプレイヤーへの利得が低いステージゲームのナッシュ均衡を使用できる。^[5]

ラインハルト・ゼルテンは、メインゲームで利用可能なすべての選択肢のサブセットを含む「サブゲーム」に分割できるゲームは、サブゲーム完全ナッシュ均衡戦略（おそらく非決定論的なサブゲームの決定を与える混合戦略として）を持つことを証明しました。サブゲーム完全性は、完全情報のゲームでのみ使用されます。サブゲーム完全性は、完全だが不完全な情報の拡張形式ゲームで使用できます。

サブゲーム完全ナッシュ均衡は通常、ゲームのさまざまな最終結果から「後方帰納法」によって演繹され、そのノードからどのプレイヤーも信頼できない（最適ではないため）動きをすることになる分岐を排除する。後方帰納法の解法がよく知られているゲームの 1 つは三目並べだが、理論的には囲碁にもすべてのプレイヤーにとって最適な戦略がある。サブゲーム完全性と後方帰納法の関係の問題は、Kaminski (2019) によって解決され、彼は、後方帰納法の一般化された手順により、無限の長さ、各情報セットとしての無限のアクション、および最終サポートの条件が満たされる場合は不完全な情報を持つ可能性のあるゲームのすべてのサブゲーム完全均衡が生成されることを証明した。

前の段落の「信頼できる」という言葉の興味深い側面は、全体として（サブゲームに到達することの不可逆性を無視して）サブゲーム完全戦略よりも優れているが、それを実行するという脅しが脅しをしているプレイヤーに損害を与え、その戦略の組み合わせを妨げるという意味では信頼できるわけではない戦略が存在することです。たとえば、「チキン」ゲームで、プレイヤーの 1 人が車のハンドルを引きちぎるという選択肢を持っている場合、そのプレイヤーは常にそれを選ぶべきです。なぜなら、それは「サブゲーム」につながるため、合理的な相手が同じことを行う（そして 2 人とも殺す）のを防ぐことができるからです。ハンドルを引きちぎるプレイヤーは常にゲームに勝ちます（相手をそらす）。そして、自殺行為でそれに倣うという相手の脅しは信頼できるものではありません。

• ムカデゲーム
• 動的不整合
• ゲーム理論の用語集
• ミニマックス定理
• 逆行分析
• ソリューションコンセプト
• ベルマンの最適性原理

• セルテン、R. (1965)。理論理論は、非常に複雑なモデルを扱います。Zeitschrift für die gesamte Staatswissenschaft/Journal of Institutional and Theoretical Economy、(H. 2)、301-324、667-689。 [ドイツ語 - パート 1、パート 2]
• 不完全情報による拡張形式ゲームの例
• gametheory.net の拡張形式ゲームのサブゲーム完全ナッシュ均衡ソリューションを見つける Java アプレット。
• gametheory.net の拡張形式ゲームのサブゲーム完全ナッシュ均衡ソリューションを見つける Java アプレット。
• Kaminski, MM 一般化後方帰納法: フォークアルゴリズムの正当化。Games 2019、10、34。