A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.

摘要: [Schaefer and Stefankovic, Theory of Computing Systems, 2015] provided an explicit formulation EXISTS-R as the class capturing complexity deciding Existential Reals, established that deciding, given a 3-player game, whether or not it has Nash equilibrium with no probability exceeding rational is EXISTS-R-complete. Four more decision problems about equilibria for games were very recently shown EXISTS-R-complete via chain individual, problem-specific reductions in [Garg et al., Proceedings ICALP 2015]; determining such was posed there open problem. In this work, we deliver extensive catalog games, thus resolving completely problem from 2015]. Towards end, present single simple, unifying reduction to (almost) all before NP-complete 2-player [Bilo Mavronicolas, SAGT 2012; Conitzer Sandholm, Games Economic Behavior, 2008; Gilboa Zemel, 1989]. Encompassed are four