ITU

Computational Complexity of Proper Equilibrium

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

View graph of relations

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.
Original languageEnglish
Title of host publicationProceedings of the 2018 ACM Conference on Economics and Computation : EC '18
PublisherAssociation for Computing Machinery
Publication date2018
Pages113-130
ISBN (Print)978-1-4503-5829-3
DOIs
Publication statusPublished - 2018
EventThe nineteenth ACM conference on Economics and Computation (ACM EC’18) - Cornell University, Ithaca, United States
Duration: 18 Jun 201822 Jun 2018
Conference number: 19
http://www.sigecom.org/ec18/

Conference

ConferenceThe nineteenth ACM conference on Economics and Computation (ACM EC’18)
Nummer19
LocationCornell University
LandUnited States
ByIthaca
Periode18/06/201822/06/2018
Internetadresse

Downloads

No data available

ID: 83587086