On Existence and Computational Complexity of Quasi-strict Equilibria

概要

Quasi-strict Nash equilibrium, introduced by Harsanyi in 1973, is the Nash equilibrium refinement that requires every pure best response to be played with positive probability. Norde established that any bimatrix game admits a quasi-strict Nash equilibrium. We give a substantially simpler proof of this result that in particular avoids an intricate limit argument used in the final step of the proof by Norde. Our existence proof allows us to positively resolve the outstanding open question of PPAD membership of the problem of computing a quasi-strict Nash equilibrium, thereby settling its precise complexity. In games with three or more players, a quasi-strict Nash equilibrium is not guaranteed to exist, leading to the natural problem of deciding the existence of a quasi-strict Nash equilibrium in a given strategic form game. We show that this problem is $\exists\mathbb{R}$-complete, strengthening a previous NP-hardness result.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
On Existence and Computational Complexity of Quasi-strict Equilibria

# 概要
Quasi-strict Nash equilibrium, introduced by Harsanyi in 1973, is the Nash equilibrium refinement that requires every pure best response to be played with positive probability. Norde established that…

# 原典
https://arxiv.org/abs/2611.06350

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。