ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
复制标题
ETR-多人（对称）纳什均衡决策版本的完整性
DOI：
10.1007/978-3-662-47672-7_45
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Sadra Yazdanbod
中科院分区：
文献类型：
--
作者：
J. Garg;R. Mehta;V. Vazirani;Sadra Yazdanbod
由于一些重要工作 [4,5,6,10,15]，现在已经很好地理解了 2 人纳什均衡的复杂性，即使当需要具有特殊属性的均衡并且博弈是对称时也是如此。然而，对于多人游戏，当需要具有特殊属性的平衡时，唯一已知的结果来自 Schaefer 和 Stefankovic [18]：检查 3 人 NE (3-Nash) 实例在 \(l_{\infty }\)-范数中半径一半的球中是否具有平衡是 ETR 完全的，其中 ETR 是实数的存在理论。
As a result of some important works [4, 5, 6, 10, 15], the complexity of 2-player Nash equilibrium is by now well understood, even when equilibria with special properties are desired and when the game is symmetric. However, for multi-player games, when equilibria with special properties are desired, the only result known is due to Schaefer and Stefankovic [18]: that checking whether a 3-player NE (3-Nash) instance has an equilibrium in a ball of radius half in \(l_{\infty }\)-norm is ETR-complete, where ETR is the class Existential Theory of Reals.