文章基本信息

标题：Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games
本地全文：下载
作者：Vittorio Bil{\`o ; Marios Mavronicolas
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：66
页码：13:1-13:14
DOI：10.4230/LIPIcs.STACS.2017.13
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 Existential-R-complete; that is, they are exactly as hard as deciding the Existential Theory of the Reals.
关键词：Nash equilibrium; complexity of equilibria; ExistentialR-completeness