最大支配戦略

ゲーム理論では、最大支配戦略とは、他のプレイヤーのどの戦略プロファイルに対しても最善の対応ではない戦略です。これは、同様に最大支配である 厳密な支配戦略の概念の拡張です。

プレーヤー の戦略が最大支配的であるとは、他のプレーヤー のすべての戦略プロファイル に対してとなる戦略が存在する場合です。この定義は、 がどの戦略プロファイルに対しても最善の応答ではないことを意味します。なぜなら、そのようなすべての戦略プロファイルに対して、プレーヤーよりも高い効用をもたらす別の戦略が存在するからです。 ${\displaystyle s_{i}\in S_{i}}$${\displaystyle i}$${\displaystyle s_{-i}\in S_{-i}}$${\displaystyle s_{i}^{\prime }\in S_{i}}$${\displaystyle u_{i}(s_{i}^{\prime },s_{-i})>u_{i}(s_{i},s_{-i})}$${\displaystyle s_{i}}$ ${\displaystyle s_{-i}}$${\displaystyle s_{i}^{\prime}}$${\displaystyle s_{i}}$${\displaystyle i}$

ある戦略が戦略 によって厳密に支配されている場合、その戦略は最大支配でもあります。これは、他のプレイヤーのすべての戦略プロファイルに対して、が となる戦略であるためです。 ${\displaystyle s_{i}\in S_{i}}$${\displaystyle s_{i}^{\prime }\in S_{i}}$${\displaystyle s_{-i}\in S_{-i}}$${\displaystyle s_{i}^{\prime}}$${\displaystyle u_{i}(s_{i}^{\prime },s_{-i})>u_{i}(s_{i},s_{-i})}$

が混合戦略によって厳密に支配されている場合でも、最大支配でもあります。 ${\displaystyle s_{i}}$

プレーヤー の戦略は、他のプレーヤー のすべての戦略プロファイルに対してとなる戦略が存在する場合、弱最大優位です。この定義は、 がどの戦略プロファイルに対しても最善の応答ではないか、唯一の最善の応答ではないことを意味します。なぜなら、そのようなすべての戦略プロファイルに対して、プレーヤーと少なくとも同じ効用を与える別の戦略が存在するからです。 ${\displaystyle s_{i}\in S_{i}}$${\displaystyle i}$${\displaystyle s_{-i}\in S_{-i}}$${\displaystyle s_{i}^{\prime }\in S_{i}}$${\displaystyle u_{i}(s_{i}^{\prime },s_{-i})\geq u_{i}(s_{i},s_{-i})}$${\displaystyle s_{i}}$ ${\displaystyle s_{-i}}$${\displaystyle s_{i}^{\prime}}$${\displaystyle s_{i}}$${\displaystyle i}$

ある戦略が戦略 によって弱支配されている場合、その戦略は弱最大支配でもあります。これは、他のプレイヤーのすべての戦略プロファイルに対して、が となる戦略であるためです。 ${\displaystyle s_{i}\in S_{i}}$${\displaystyle s_{i}^{\prime }\in S_{i}}$${\displaystyle s_{-i}\in S_{-i}}$${\displaystyle s_{i}^{\prime}}$${\displaystyle u_{i}(s_{i}^{\prime },s_{-i})\geq u_{i}(s_{i},s_{-i})}$

が混合戦略によって弱支配されている場合でも、それは弱最大支配でもあります。 ${\displaystyle s_{i}}$

最大支配戦略を繰り返し排除することによって、最後に 1 つの戦略プロファイルだけが残る 場合、ゲームは最大解決可能であると言われます。${\displaystyle G}$

より正式には、次のようなゲームのシーケンスが存在する場合、それは最大解決可能であると言います。 ${\displaystyle G}$${\displaystyle G_{0},...,G_{r}}$

• ${\displaystyle G_{0}=G}$
• ${\displaystyle G_{k+1}}$は、単一のプレイヤーの戦略空間から単一の最大支配戦略を削除することによって得られます。${\displaystyle G_{k}}$
• 残っている戦略プロファイルは 1 つだけです。${\displaystyle G_{r}}$

明らかに、すべての最大解決可能ゲームには、残された戦略プロファイルである一意の純粋ナッシュ均衡があります。 ${\displaystyle G_{r}}$

前回と同様に、それぞれ弱最大解決可能ゲームの概念を定義できます。これは、弱最大優位戦略を排除することで、単一の戦略プロファイルを持つゲームに到達できるゲームです。主な違いは、弱最大優位ゲームには複数の純粋なナッシュ均衡がある場合があり、排除の順序によって異なるナッシュ均衡が生じる可能性があることです。

囚人のジレンマは、最大解決可能なゲームの例です (支配解決可能でもあるため)。協力戦略は、どちらのプレイヤーにとっても、不正戦略によって最大支配されます。これは、他のプレイヤーが何をプレイしても、不正をプレイすると常にプレイヤーの効用が高くなるためです。これを確認するには、行のプレイヤーが協力をプレイする場合、列のプレイヤーは、協力をプレイして 1 年間刑務所に入るよりも、不正をプレイして自由になることを好むことに注意してください。行のプレイヤーが不正をプレイする場合、列のプレイヤーは、協力をプレイして 5 年間刑務所に入るよりも、不正をプレイして 3 年間刑務所に入ることを好むでしょう。

任意の最大解決可能ゲームでは、最善の応答ダイナミクスは最終的にゲームの唯一の純粋ナッシュ均衡につながります。これを確認するには、 がゲームの排除シーケンスである場合（つまり、最初にが最大支配であるため、あるプレーヤーの戦略スペースから排除され、次にが排除され、以下同様に続く）、最善応答ダイナミクスでは は最善の応答の 1 回の反復後にプレーヤーによってプレイされることはなく、 は最善の応答の 2 回の反復後にプレーヤーによってプレイされることはなく、以下同様に続くことに気付くだけです。これは、 が他のプレーヤーのどの戦略プロファイルに対しても最善の応答ではないため、最善の応答の 1 回の反復後にプレーヤーは別の戦略を選択したに違いないからです。最善の応答のどの反復でも に戻ることはないとわかっているので、最善の応答の 1 回の反復後にゲームを がゲームから排除されたものとして扱い、帰納法によって証明を完了することができます。 ${\displaystyle s_{1},s_{2},s_{3},...,s_{k}}$${\displaystyle s_{1}}$${\displaystyle s_{2}}$${\displaystyle s_{1}}$${\displaystyle s_{2}}$${\displaystyle s_{1}}$${\displaystyle s_{-i}}$${\displaystyle s_{1}}$${\displaystyle s_{1}}$

すると、右のゲームに見られるように、最良応答ダイナミクス を使用すると、弱最大解決可能ゲームが必ずしも純粋なナッシュ均衡に収束するわけではないことに驚かれるかもしれません。 ゲームがマトリックスの左下のセルから開始する場合、次のような最善の再生ダイナミクスが可能です。行のプレーヤーは 1 行上へ移動して中央の行に移動し、列のプレーヤーは右の列に移動し、行のプレーヤーは一番下の行に戻り、列のプレーヤーは左の列に戻り、これを繰り返します。 これは明らかに、ゲームの唯一の純粋ナッシュ均衡 (ペイオフ マトリックスの左上のセル) に収束することはありません。

優位性（ゲーム理論）

• Nisan, Noam; Schapira, Michael; Zohar, Aviv (2009)、非同期ベストリプライダイナミクス、ベルリン: Springer-Verlag、2003-04-17 にオリジナルからアーカイブ非同期ベストリプライダイナミクス[1]。