Computational Complexity of Proper Equilibrium
| Autor: | Kristoffer Arnsfelt Hansen, Troels Bjerre Lund |
|---|---|
| Přispěvatelé: | Tardos, Éva, Elkind, Edith, Vohra, Rakesh |
| Rok vydání: | 2018 |
| Předmět: |
TheoryofComputation_MISCELLANEOUS
Computer Science::Computer Science and Game Theory Mathematical optimization Computational complexity theory Computer science Proper equilibrium ComputingMilieux_PERSONALCOMPUTING TheoryofComputation_GENERAL 0102 computer and information sciences 02 engineering and technology 01 natural sciences Task (project management) symbols.namesake 010201 computation theory & mathematics Nash equilibrium 0202 electrical engineering electronic engineering information engineering symbols 020201 artificial intelligence & image processing |
| Zdroj: | EC Hansen, K A & Lund, T B 2018, Computational Complexity of Proper Equilibrium . in Proceedings of the 2018 ACM Conference on Economics and Computation : EC '18 . Association for Computing Machinery, pp. 113-130 . https://doi.org/10.1145/3219166.3219199 Hansen, K A & Lund, T B 2018, Computational Complexity of Proper Equilibrium . in É Tardos, E Elkind & R Vohra (eds), Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018 . Association for Computing Machinery, New York, NY, USA, pp. 113-130, The nineteenth ACM conference on Economics and Computation (ACM EC’18), Ithaca, United States, 18/06/2018 . https://doi.org/10.1145/3219166.3219199 |
| DOI: | 10.1145/3219166.3219199 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|