繰り返しゲーム

ゲーム理論では、反復ゲーム(または反復ゲーム) は、ある基本ゲーム (ステージゲームと呼ばれる)の多数の繰り返しで構成される拡張形式のゲームです。ステージゲームは通常、よく研究されている2 人用ゲームの 1 つです。反復ゲームは、プレーヤーが現在のアクションが他のプレーヤーの将来のアクションに与える影響を考慮しなければならないという考えに基づいています。この影響は、評判と呼ばれることもあります。 シングルステージゲームまたはシングルショットゲームは、反復されないゲームの名前です。

反復ゲームの例として、隣接する2 つのガソリンスタンドを考えてみましょう。これらのスタンドは価格を公開して競争しており、限界費用 c (ガソリンの卸売価格) は同じで一定です。両方のスタンドが p = 10 を請求すると、共同利益が最大化され、全員の利益が大きくなると仮定します。これがスタンドにとって最善の結果であるにもかかわらず、スタンドには逸脱する動機があります。価格を適度に下げることで、どちらも競合他社の顧客をすべて奪い、収益をほぼ 2 倍にすることができます。利益がゼロになる p = c は、この利益逸脱のない唯一の価格です。言い換えると、価格競争ゲームでは、両方のスタンドが p = c を請求する唯一のナッシュ均衡が非効率的です (ガソリンスタンドの場合)。これは例外というよりはルールです。段階的なゲームでは、ナッシュ均衡はエージェントが相互作用で一貫して獲得できる唯一の結果であり、通常は非効率的です。これは、エージェントが自分の個人的な利益だけを気にしており、自分の行動が競争相手にもたらす利益やコストを気にしていないためです。一方、ガソリンスタンドは、隣に別のガソリンスタンドがあっても利益を上げます。最も重要な理由の 1 つは、それらの相互作用が 1 回限りではないことです。この状態は、2 つのガソリンスタンドが不定の時間範囲 t = 0、1、2、... にわたって価格設定を競う繰り返しゲーム (ステージゲーム) によって表されます。

有限繰り返しゲームと無限繰り返しゲーム

繰り返しゲームは、ゲームのプレイ時間の長さに応じて、有限と無限の 2 つのクラスに大まかに分けられます。

有限ゲームとは、両方のプレイヤーが、ゲームが特定の（有限の）ラウンド数プレイされていること、およびそのラウンド数がプレイされた後にゲームが確実に終了することを知っているゲームです。一般に、有限ゲームは後方帰納法によって解くことができます。
無限ゲームとは、ゲームが無限回プレイされるゲームです。ラウンド数が無限のゲームは、(プレイ戦略の観点から) ゲームのプレイヤーがゲームが何ラウンドプレイされるか分からないゲームと同等です。無限ゲーム (または不明な回数繰り返されるゲーム) は、逆方向帰納法で解くことはできません。逆方向帰納法を開始する「最後のラウンド」がないためです。

各ラウンドでプレイされるゲームが同一であっても、そのゲームを有限回または無限回繰り返すと、一般的に、非常に異なる結果 (均衡) と非常に異なる最適戦略につながる可能性があります。

無限に繰り返されるゲーム

最も広く研究されている反復ゲームは、無限回繰り返されるゲームです。反復囚人のジレンマゲームでは、好ましい戦略はステージゲームのナッシュ戦略を実行することではなく、協力して社会的に最適な戦略を実行することであることがわかっています。無限反復ゲームにおける戦略の重要な部分は、この協力戦略から逸脱するプレーヤーを罰することです。罰は、ゲームの残りの間両方のプレーヤーの報酬が減少する戦略を実行することです (トリガー戦略と呼ばれる)。プレーヤーは通常、社会的に最適な戦略を実行するのではなく、自分の報酬を増やすために利己的に行動することを選択します。ただし、他のプレーヤーがトリガー戦略に従っていることがわかっている場合、プレーヤーはこの段階で逸脱すると将来的に報酬が減少することを予期します。効果的なトリガー戦略により、今利己的に行動して将来的に他のプレーヤーの罰に直面するよりも、協力する方がプレーヤーにとって有用であることが保証されます。

反復ゲームで社会的に最適な均衡を達成し維持する方法を扱う定理には、多くの結果があります。これらの結果は、まとめて「フォーク定理」と呼ばれます。反復ゲームの重要な特徴は、プレーヤーの好みをモデル化する方法です。無限に反復されるゲームで好みの関係をモデル化する方法は多数ありますが、重要な 2 つは次のとおりです。

手段の限界- ゲームの結果が結果のパスになり、プレイヤーi が基本ゲーム効用関数を持つ場合、プレイヤーiの効用は次のようになります。 $x_{t}$ $u_{i}$

U_{i}=\lim _{T\to \infty }\inf {\frac {1}{T}}\sum _{t=0}^{T}u_{i}(x_{t})

割引- プレイヤー i のゲームに対する評価が割引率に応じて時間とともに減少する場合、プレイヤーi の効用は次のようになります。 $\delta <1$

U_{i}=\sum _{t}\geq 0}\delta ^{t}u_{i}(x_{t})

十分に忍耐強いプレイヤー（たとえば、の値が十分に高いプレイヤー）の場合、最小最大ペイオフよりも大きいペイオフを持つすべての戦略がナッシュ均衡（非常に大きな戦略セット）になり得ることが証明できます。 $\delta$

有限反復ゲーム

繰り返しゲームは、即時の利益と長期的なインセンティブの相互作用を研究することを可能にします。有限繰り返しゲームとは、同じワンショットステージゲームがいくつかの離散的な期間、またはラウンドにわたって繰り返しプレイされるゲームです。各期間は 0 < t ≤ T でインデックス付けされ、T は期間の総数です。プレイヤーの最終的な報酬は、各ラウンドの報酬の合計です。^[1]

固定かつ既知の期間数を持つ反復ゲームの場合、ステージゲームに一意のナッシュ均衡がある場合、反復ゲームには、各ラウンドでステージゲーム均衡をプレイする一意のサブゲーム完全ナッシュ均衡戦略プロファイルがあります。これは、後方帰納法によって演繹できます。一意のステージゲームナッシュ均衡は、以前のラウンドで何が起こったかに関係なく、最後のラウンドでプレイする必要があります。これを知っていると、プレーヤーは最後から2番目のラウンドで一意のステージゲームナッシュ均衡から逸脱するインセンティブがないため、このロジックはゲームの最初のラウンドに適用されます。^{[2]このゲームのエンドポイントからの「解きほぐれ」は}、チェーンストアパラドックスで観察できます。

ステージゲームに複数のナッシュ均衡がある場合、繰り返しゲームには複数のサブゲーム完全ナッシュ均衡が存在する可能性があります。ナッシュ均衡は最終ラウンドでプレイされる必要がありますが、複数の均衡が存在すると、報酬と罰の戦略が可能になり、それを使用してステージゲームのナッシュ均衡からの逸脱を初期のラウンドでサポートできるようになります。^[2]

一方、期間の数が未知または不確定である有限反復ゲームは、無限反復ゲームであるかのようにみなされます。これらのゲームに逆方向帰納法を適用することはできません。

有限反復ゲームにおける協力の例

例 1: 複数のナッシュ均衡を持つ 2 段階繰り返しゲーム

例 1 は、複数の純粋戦略ナッシュ均衡を持つ 2 段階の繰り返しゲームを示しています。これらの均衡はプレイヤー 2 の報酬の点で著しく異なるため、プレイヤー 1 は、プレイヤー 2 に対する罰則または報酬の可能性を組み込んだ、ゲームの複数の段階にわたる戦略を提案できます。たとえば、プレイヤー 1 は、最初のラウンドで (A, X) をプレイすることを提案する場合があります。プレイヤー 2 がラウンド 1 で従う場合、プレイヤー 1 はラウンド 2 で均衡 (A, Z) をプレイすることで報酬を与え、2 ラウンドで合計報酬が (7, 9) になります。

プレイヤー 2 が第 1 ラウンドで合意済みの (A, X) をプレイする代わりに (A, Z) に逸脱した場合、プレイヤー 1 は第 2 ラウンドで (B, Y) 均衡をプレイすることで罰を与えると脅すことができます。この後者の状況では、報酬は (5, 7) となり、両方のプレイヤーが不利になります。

このように、将来のラウンドで罰を受けるという脅威は、最初のラウンドで協力的で非均衡な戦略をとる動機となります。有限反復ゲームの最終ラウンドでは、その性質上、将来の罰を受けるという脅威がなくなるため、最終ラウンドの最適戦略は常にゲームの均衡点の 1 つになります。例 1 で示したゲーム内の均衡点間の利得差が、罰/報酬戦略を実行可能にします (罰と報酬がゲーム戦略に与える影響の詳細については、「罰と報酬のある公共財ゲーム」を参照してください)。

例 2: 一意のナッシュ均衡を持つ 2 段階繰り返しゲーム

例 2 は、一意のナッシュ均衡を持つ 2 段階の繰り返しゲームを示しています。ここでは均衡が 1 つしかないため、どちらのプレイヤーもゲームの 2 ラウンド目で罰を脅かしたり報酬を約束したりするメカニズムはありません。したがって、サブゲーム完全ナッシュ均衡としてサポートできる唯一の戦略は、ゲームの一意のナッシュ均衡戦略 (D, N) を毎ラウンド実行するというものです。この場合、各ステージで (D, N) を 2 ステージ (n=2) 実行することを意味しますが、これは任意の有限数のステージnに対して当てはまります。^[3]解釈すると、この結果は、既知の有限の時間範囲が存在すること自体が、ゲームのすべてのラウンドで協力を妨害することを意味しています。反復ゲームでの協力は、ラウンド数が無限または未知の場合にのみ可能です。