∃R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games

被引：9
|
作者：
Bilo, Vittorio [1 ]
Mavronicolas, Marios [2 ]
机构：
[1] Univ Salento, Dept Math & Phys, Lecce, Italy
[2] Univ Cyprus, Dept Comp Sci, Nicosia, Cyprus
来源：
34TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2017) | 2017年 / 66卷
关键词：
Nash equilibrium; complexity of equilibria; there exists R-completeness; APPROXIMATE;
D O I：
10.4230/LIPIcs.STACS.2017.13
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We study the complexity of decision problems about symmetric Nash equilibria for symmetric multi-player games. These decision problems concern the existence of a symmetric Nash equilibrium with certain natural properties. We show that a handful of such decision problems are there exists R-complete; that is, they are exactly as hard as deciding the Existential Theory of the Reals.
引用
收藏
页数：14
相关论文
共 19 条
12