Abstract
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.
| Originalsprog | Engelsk |
|---|---|
| Titel | Proceedings of the 2018 ACM Conference on Economics and Computation : EC '18 |
| Forlag | Association for Computing Machinery |
| Publikationsdato | 2018 |
| Sider | 113-130 |
| ISBN (Trykt) | 978-1-4503-5829-3 |
| DOI | |
| Status | Udgivet - 2018 |
| Begivenhed | The nineteenth ACM conference on Economics and Computation (ACM EC’18) - Cornell University, Ithaca, USA Varighed: 18 jun. 2018 → 22 jun. 2018 Konferencens nummer: 19 http://www.sigecom.org/ec18/ |
Konference
| Konference | The nineteenth ACM conference on Economics and Computation (ACM EC’18) |
|---|---|
| Nummer | 19 |
| Lokation | Cornell University |
| Land/Område | USA |
| By | Ithaca |
| Periode | 18/06/2018 → 22/06/2018 |
| Internetadresse |
Emneord
- Computational Complexity
- Proper Equilibrium
- Finite Games
- NP-Complete
- PPAD-Complete