強いナッシュ均衡

ゲーム理論において、強いナッシュ均衡 (SNE)とは、異なるプレイヤーの行動の組み合わせであり、他のプレイヤーの行動が固定されている限り、どのプレイヤー連合もメンバー全員に厳密に利益をもたらすような方法で協力的に逸脱することはできない。これは、個々のプレイヤーの逸脱のみを考慮する単純なナッシュ均衡とは対照的である。この概念は、1959 年にイスラエル・オーマンによって導入された。 ^{[1] SNE は、}投票システムの研究などの分野で特に有用である。投票システムでは、通常、考えられる結果よりもプレイヤーの数の方がはるかに多く、単純なナッシュ均衡があまりにも多く存在する。^[2]

ネッサとティアン^[3]は、以下の条件が満たされる場合にSNEが存在することを証明している。

• 各プレイヤーの戦略空間はコンパクトかつ凸状である。
• 各プレイヤーの報酬関数は凹型かつ連続型である。
• 連合一貫性プロパティ: 重みベクトルタプルwが存在し、重みベクトルw _Sを各可能な連合Sに割り当てるため、各戦略プロファイルxに対して、 x _{- S}が与えられた場合に、z _{S が}Sのメンバーに対する重み付けされた ( w _Sによる) 社会的福祉を最大化する戦略プロファイルz が存在します。
  • x自体が SNE である場合、z はxと等しいとみなされることに注意してください。xが SNE でない場合、条件では、すべての連合に対して同時に社会的福祉の最善の対応となる別の戦略プロファイルに移行できることが要求されます。

たとえば、2 人のプレイヤーがいるゲームを考えてみましょう。戦略空間は [1/3, 2] と [3/4, 2] で、明らかにコンパクトで凸です。効用関数は次のようになります。

• u1(x) = - x1 ² + x2 + 1
• u2(x) = x1 - x2 ² + 1

これらは連続かつ凸です。残っているのは連合の一貫性をチェックすることです。すべての戦略タプル x について、各連合の重み付けされた最良応答をチェックします。

• 連合{1}の場合、すべてのx2に対して、最大値_y1（-y1 ² + x2 + 1）を見つける必要があります。最大値は戦略空間の最小点、つまりy1 = 1/3で達成されることは明らかです。
• 連合{2}についても同様に、すべてのx1に対して、最大の利益は最小の点、y2=3/4で達成されることがわかります。
• 重みがw1、w2である連合{1,2}の場合、最大値_y1、y2（w1*(-y1 ² + y2 + 1)+w2*(y1 - y2 ² + 1)）を見つける必要があります。微分テストを使用すると、最大点はy1=w2/(2*w1)およびy2=w1/(2*w2)であることがわかります。w1=0.6、w2=0.4とすると、y1=1/3およびy2=3/4になります。

したがって、w1=0.6、w2=0.4 の場合、ポイント (1/3,3/4) は、すべての連合にとって同時に一貫した社会福祉の最善の対応です。したがって、同じポイント (1/3,3/4) に SNE が存在します。

これは、連合一貫性が失敗し、実際にSNEが存在しない例です。^{[3] : 例3.1}戦略空間[0,1]を持つ2人のプレーヤーがいます。彼らの効用関数は次のとおりです。

• u1(x) = -x1 + 2*x2;
• u2(x) = 2*x1 - x2 です。

(0,0) に、利得ベクトル (0,0) を持つ唯一のナッシュ均衡があります。しかし、連合 {1,2} は利得ベクトル (1,1) を持つ (1,1) に逸脱する可能性があるため、これは SNE ではありません。実際、連合一貫性はx =(0,0) で破られています。連合 {1,2} の場合、任意の重みベクトルw _Sに対して、社会福祉最善の応答は、直線 (1,0)--(1,1) 上または直線 (0,1)--(1,1) 上にあります。しかし、そのような点は、1 をプレイするプレイヤーにとって最善の応答ではありません。

NessahとTian ^[3]は、 SNEが存在するための必要十分条件と、SNEが存在する場合にのみSNEを見つけるアルゴリズムも提示しています。

すべての SNE はナッシュ均衡です。これは、 n 個のシングルトン連合の偏差を考慮することで確認できます。

すべての SNE は弱いパレート効率的です。これは、大連合 (すべてのプレーヤーの連合) の偏差を考慮することで確認できます。

すべてのSNEは弱いアルファコアと弱いベータコアにあります。^[3]

強いナッシュ概念は、環境が無制限のプライベート通信を可能にするという点で「強すぎる」と批判されています。これらの要件の結果として、強いナッシュは、研究に値するほど興味深いゲームではほとんど存在しません。ただし、複数の強いナッシュ均衡が存在する可能性があります。たとえば、承認投票では、存在するコンドルセ勝者に対して常に強いナッシュ均衡が存在します。ただし、これは、過半数のコンドルセ勝者がいる場合にのみ一意です (重要でない変更は別として)。

比較的弱いが洗練されたナッシュ安定性の概念は、連立耐性ナッシュ均衡（CPNE）^[2]と呼ばれ、均衡は自己強制的な多国間偏差の影響を受けません。反復厳密優位性によってサポートされ、パレート境界上にあるすべての相関戦略はCPNEです。^{[4]さらに、指定されたサイズ}k 未満の連立に対して耐性のあるナッシュ均衡をゲームが持つことも可能です 。CPNEはコア理論に関連しています。

紛らわしいことに、強いナッシュ均衡の概念は弱いナッシュ均衡の概念とは無関係です。つまり、ナッシュ均衡は、強いと弱いの両方になることもあれば、どちらか一方になることもあれば、どちらでもないこともあります。