We study the computational complexity of proper equilibrium in finite games and prove the following results. First, for two-player games in strategic form we show that the task of simply verifying the proper equilibrium conditions of a given pure Nash equilibrium is NP-complete. Next, for n -player games in strategic form we show that the task of computing an approximation of a proper equilibrium is FIXPa-complete. Finally, for n -player polymatrix games we show that the task of computing a symbolic proper equilibrium is PPAD-complete.
Title of host publication
Proceedings of the 2018 ACM Conference on Economics and Computation : EC '18
The nineteenth ACM conference on Economics and Computation (ACM EC’18) - Cornell University, Ithaca, United States Duration: 18 Jun 2018 → 22 Jun 2018 Conference number: 19 http://www.sigecom.org/ec18/
The nineteenth ACM conference on Economics and Computation (ACM EC’18)
This page is printed from https://en.itu.dk/research/portalplaceholder?layoutfraction=breadcrumb&langRef=https://pure.itu.dk/portal/da/organisations-research/business-it(c6fa53f2-e82c-42c0-ac6f-86f0828b563d)/publications.html?filter=research&ordering=researchOutputOrderByPublicationYearAndAuthor&page=20&descending=false