戦略（ゲーム理論）

ゲーム理論では、動き、行動、またはプレイとは、最適な結果が自分の行動だけでなく他の人の行動によって決まる状況でプレイヤーが選択できるオプションのいずれかです。 ^[1]この分野は主に、ゲーム内のプレイヤーの行動が他のプレイヤーの行動や行動に影響を与えることに関するものです。「ゲーム」の例には、チェス、ブリッジ、ポーカー、モノポリー、外交、戦艦などがあります。^[2]

戦略という用語は通常、ゲームをプレイするための完全なアルゴリズムを意味し、あらゆる状況でプレイヤーに何をすべきかを伝えます。プレイヤーの戦略は、ゲームのどの段階でもプレイヤーが取る行動を決定します。ただし、ほとんどのゲームでは動きと純粋な戦略が対応しているため、戦略の概念は動きやアクションの概念と混同または統合されることがよくあります。つまり、任意の動きXに対して、「常に動きXをする」は有効な戦略の例であり、結果としてすべての動きも戦略であると考えられます。他の著者は、戦略をアクションとは異なる種類のものとして扱い、したがって区別しています。

「戦略」を指示のリストとして考え、「動き」を指示のリスト自体の 1 ターンとして考えると役に立ちます。この戦略は、各アクションの報酬または結果に基づいています。各エージェントの目標は、競合他社のアクションに基づいて報酬を検討することです。たとえば、競合他社 A は、競合他社 B が市場に参入すると想定できます。そこから、競合他社 A は、参入した場合と参入しない場合の報酬を比較します。次のステップは、競合他社 B が参入しないと想定し、競合他社 A が参入するかしないかに基づいて、どちらの報酬がより良いかを検討することです。この手法により、プレーヤーが競合他社が報酬を最大化するために何をしようとも実行できるアクションを特定できる、支配的な戦略を特定できます。

戦略プロファイル(戦略の組み合わせと呼ばれることもあります) は、ゲーム内のすべてのアクションを完全に指定する、すべてのプレーヤーの戦略のセットです。戦略プロファイルには、プレーヤーごとに 1 つの戦略のみを含める必要があります。

プレイヤーの戦略セットは、プレイできる戦略を定義します。

プレイヤーが利用できる個別の戦略が複数ある場合、そのプレイヤーは有限の戦略セットを持ちます。たとえば、じゃんけんのゲームは各プレイヤーによる 1 つの動きで構成され、各プレイヤーの動きは応答としてではなく、他のプレイヤーの動きを知らずに行われるため、各プレイヤーは有限の戦略セット {じゃんけん} を持ちます。

それ以外の場合、戦略セットは無限です。たとえば、ケーキカットゲームでは、戦略セット {ケーキの 0 パーセントから 100 パーセントの間でカットする} 内に戦略の制限された連続体が存在します。

動的ゲーム、つまり一定期間にわたってプレイされるゲームでは、戦略セットは、プレイヤーがロボットやエージェントにゲームのプレイ方法について与えることができる可能性のあるルールで構成されます。たとえば、最後通牒ゲームでは、2 番目のプレイヤーの戦略セットは、どのオファーを受け入れ、どのオファーを拒否するかに関する可能性のあるすべてのルールで構成されます。

ベイジアン ゲーム、つまりプレイヤーが互いについて不完全な情報しか持たないゲームで は、戦略セットは動的ゲームの戦略セットに似ています。戦略セットは、あらゆる可能性のある秘密情報に対してどのようなアクションを取るかというルールで構成されます。

応用ゲーム理論では、戦略セットの定義は、ゲームを解決可能かつ有意義なものにする技術の重要な部分です。ゲーム理論家は、全体的な問題、つまり 2 人以上のプレイヤー間の摩擦に関する知識を使用して、戦略空間を制限し、解決を容易にすることができます。

たとえば、厳密に言えば、アルティメイタム ゲームでは、プレーヤーは次のような戦略を取ることができます。($1、$3、$5、...、$19) のオファーを拒否し、($0、$2、$4、...、$20) のオファーを受け入れる。このような戦略をすべて含めると、戦略空間が非常に大きくなり、問題が多少難しくなります。ゲーム理論家は、代わりに戦略セットを次のように制限できると考えるかもしれません。{ x ≤ のすべてのオファーを拒否し、 x > のすべてのオファーを受け入れる。xは($0、$1、$2、...、$20) の範囲内}。

純粋戦略は、プレイヤーがゲームをどのようにプレイするかを完全に定義します。純粋戦略は、プレイ中にプレイヤーが行った観察に基づく単一の具体的な計画と考えることができます。特に、プレイヤーが直面する可能性のあるあらゆる状況に対してプレイヤーが取る動きを決定します。プレイヤーの戦略セットは、そのプレイヤーが利用できる純粋戦略のセットです。

混合戦略とは、各純粋戦略に確率を割り当てることです。混合戦略を採用する理由は、多くの場合、ゲームがゲームの純粋戦略を指定するための合理的な説明を許可していないためです。これにより、プレーヤーは純粋戦略をランダムに選択できます。(次のセクションの図を参照してください。) 確率は連続的であるため、プレーヤーが使用できる混合戦略は無限にあります。特定のシナリオのペイオフについて議論する場合、特定のプレーヤーの戦略に確率が割り当てられるため、ペイオフは「期待ペイオフ」と呼ばれる必要があります。

もちろん、純粋戦略は混合戦略の退化したケースと見なすこともできます。その場合、特定の純粋戦略は確率1で選択され、他のすべての戦略は確率0で選択されます。

完全混合戦略とは、プレイヤーがすべての純粋戦略に厳密に正の確率を割り当てる混合戦略です。(完全混合戦略は、震える手の完全均衡などの均衡の改良に重要です。)

サッカーのペナルティ キックでは、キッカーはゴールの右側に蹴るか左側に蹴るかを選択し、同時にゴールキーパーはどちらにブロックするかを決定する必要があります。また、キッカーには最も得意な方向があり、右利きの場合は左です。サッカー ゲームのマトリックスは、Chiappori、Levitt、および Groseclose (2002) によって研究されたゲームの簡略化された形式でこの状況を示しています。^[3]このマトリックスでは、ゴールキーパーが正しく推測した場合、キックはブロックされ、両方のプレーヤーの基本ペイオフが 0 に設定されていると想定しています。ゴールキーパーが間違った推測をした場合、キックが左側に蹴られた場合 (キッカーのペイオフ +2、ゴールキーパーのペイオフ -2) の方が、右側に蹴られた場合 (キッカーのペイオフ +1、ゴールキーパーのペイオフ -1 と低くなります) よりもキックが入る可能性が高くなります。

このゲームには、純粋戦略の均衡はありません。なぜなら、どちらかのプレイヤーが戦略のプロファイルから逸脱するからです。たとえば、(左、左) は均衡ではありません。キッカーが右に逸脱して、報酬を 0 から 1 に増やすからです。

キッカーの混合戦略均衡は、左キックと右キックの利得が正確に等しくない限り、ランダム化から逸脱するという事実から求められます。ゴールキーパーが確率 g で左に傾く場合、キッカーの左キック​​からの期待利得は g(0) + (1-g)(2) で、右キックからの期待利得は g(1) + (1-g)(0) です。これらを等しくすると、g = 2/3 になります。同様に、ゴールキーパーがランダム化を希望するのは、キッカーが混合戦略確率 k を選択し、左に傾いた場合の利得 k(0) + (1-k)(-1) が右に傾いた場合の利得 k(-2) + (1-k)(0) に等しくなる場合、つまり k = 1/3 の場合のみです。したがって、混合戦略均衡は (Prob(Kick Left) = 1/3、Prob(Lean Left) = 2/3) です。

均衡状態では、キッカーは 1/3 の確率でのみ、最も有利なサイドにキックします。これは、ゴールキーパーがそのサイドをより多く守っているためです。また、均衡状態では、キッカーはどちらの方向にキックするかは関係ありませんが、均衡状態であるためには、正確に 1/3 の確率を選択する必要があります。

キアポリ、レビット、グロースクローズは、キッカーが自分の好きなサイドにキックしたり、センターキックを追加したりすることがどれほど重要かを測定し、プロの選手が実際にどのように行動するかを調べようとしました。彼らは、ランダム化が行われていることを発見し、キッカーが自分の好きなサイドにキックする割合は 45%、ゴールキーパーが 57% の割合でそのサイドに傾いていることを発見しました。彼らの論文は、現実世界で人々が混合戦略を使用する例としてよく知られています。

ジョン・フォーブス・ナッシュは有名な論文で、すべての有限ゲームには均衡が存在することを証明しました。ナッシュ均衡は 2 種類に分けられます。純粋戦略ナッシュ均衡は、すべてのプレイヤーが純粋戦略でプレイしているナッシュ均衡です。混合戦略ナッシュ均衡は、少なくとも 1 人のプレイヤーが混合戦略でプレイしている均衡です。ナッシュはすべての有限ゲームにナッシュ均衡が存在することを証明しましたが、すべてのゲームに純粋戦略ナッシュ均衡が存在するわけではありません。純粋戦略でナッシュ均衡が存在しないゲームの例は、「Matching pennies」を参照してください。ただし、多くのゲームには純粋戦略ナッシュ均衡が存在します (例:コーディネーション ゲーム、囚人のジレンマ、鹿狩り)。さらに、ゲームには純粋戦略均衡と混合戦略均衡の両方が存在する場合があります。簡単な例としては、純粋調整ゲームがあります。純粋戦略 (A,A) と (B,B) に加えて、両方のプレイヤーがいずれかの戦略を 1/2 の確率で実行する混合均衡が存在します。

1980 年代、混合戦略の概念は「直感的に問題がある」として激しい批判にさらされた。なぜなら、混合戦略は弱いナッシュ均衡であり、プレイヤーは均​​衡戦略確率に従うか、他の確率に逸脱するかについて無関心だからである。^{[4] [5]}ゲーム理論家Ariel Rubinstein は、この概念を理解する別の方法を説明している。最初の解釈は、Harsanyi (1973) ^[6]によるもので、純粋化と呼ばれ、混合戦略の解釈は、プレイヤーの情報と意思決定プロセスに関する知識の欠如を反映しているに過ぎないと想定している。明らかに、ランダムな選択は、指定されていない、報酬とは無関係な外生的要因の結果と見なされる。^[5] 2 番目の解釈は、ゲーム プレイヤーがエージェントの大規模な集団を代表していると想定している。各エージェントは純粋戦略を選択し、報酬は各戦略を選択するエージェントの割合によって決まる。したがって、混合戦略は、各集団によって選択された純粋戦略の分布を表す。しかし、これは、プレイヤーが個々のエージェントである場合の正当性を提供しない。

その後、オーマンとブランデンブルガー（1995）^[7]は、ナッシュ均衡を行動ではなく信念の均衡として再解釈した。例えば、じゃんけんでは、信念の均衡では、各プレイヤーは相手がそれぞれの戦略を取る可能性が等しいと信じているだろう。しかし、この解釈はナッシュ均衡の記述力を弱める。なぜなら、そのような均衡では、時間の経過とともに確率が混合戦略の確率になるにもかかわらず、各プレイヤーがゲームの各プレイで実際に純粋な石の戦略を取ることが可能であるからである。

混合戦略は純粋戦略に確率分布を割り当てるのに対し、行動戦略は各情報セットに可能なアクションの集合に確率分布を割り当てます。これら 2 つの概念は、通常形式のゲームのコンテキストでは非常に密接に関連していますが、展開形式ゲームでは非常に異なる意味を持ちます。大まかに言えば、混合戦略はゲーム ツリーを通る決定論的なパスをランダムに選択しますが、行動戦略は確率論的なパスと見なすことができます。混合戦略と行動戦略の関係は、従来のゲーム理論的仮説に対する行動的見解であるクーンの定理の対象です。その結果、完全な想起を伴う有限展開形式ゲームでは、任意のプレーヤーと任意の混合戦略に対して、すべての戦略プロファイル (他のプレーヤーの) に対して、混合戦略と同じ分布をターミナル ノードに誘導する行動戦略が存在することが確立されます。逆もまた真です。

同等性を証明するために完全な想起が必要である理由の有名な例は、Piccione と Rubinstein (1997) ^{[全文引用が必要]}によるAbsent-Minded Driverゲームです。

結果の等価性は、プレイヤー i の混合戦略と行動戦略を、プレイヤー i の対戦相手の純粋戦略と関連させて組み合わせたものである。結果の等価性は、プレイヤー i が取る混合戦略と行動戦略が、プレイヤー i の対戦相手の純粋戦略に対応して、混合戦略と行動戦略の結果分布が等しくなければならない状況として定義される。この等価性は、次の式で記述できる: (Q^(U(i), S(-i)))(z) = (Q^(β(i), S(-i)))(z)、ここで U(i) はプレイヤー i の混合戦略、β(i) はプレイヤー i の行動戦略、S(-i) は対戦相手の戦略である。^[8]

完全な想起は、ゲーム内のすべてのプレイヤーがゲーム内での過去の行動をすべて記憶し、思い出す能力と定義されます。不完全な想起を伴う有限ゲームでは、同等の行動戦略が存在しないプレイヤー I の混合戦略が存在するため、同等性には完全な想起が必要です。これは、Piccione と Rubinstein によって定式化されたAbsent-Minded Driverゲームで完全に説明されています。つまり、このゲームは、家に着くために高速道路の 2 番目の出口を利用する必要があるが、そこに到着したときにどの交差点にいるかを覚えていない、不完全な想起を伴うドライバーの意思決定に基づいています。図 [2] はこのゲームを示しています。

完全情報（つまり不完全情報）がない場合、プレイヤーは各決定ノードで、それ以前の決定を知らずに選択を行う。したがって、プレイヤーの混合戦略は、その行動戦略では得られない結果を生み出す可能性があり、その逆もまた同様である。これは、ぼんやりしたドライバーゲームで実証されている。完全な想起と情報がある場合、ドライバーは、到着したときにどの交差点（または決定ノード）にいるかを認識しているため、純粋な戦略は [続行、終了] のみである。一方、計画最適段階のみを見ると、最大の利益は両方の交差点で続行することで達成され、p = 2/3 で最大化される（参照）。この単純な 1 人用ゲームは、結果の同等性に対する完全な想起の重要性と、それが通常形式および拡張形式のゲームに与える影響を示している。^[9]

• ナッシュ均衡
• ヘイブン（グラフ理論）
• 進化的に安定した戦略