Computational Complexity of Proper Equilibrium

Kristoffer Arnsfelt Hansen, Troels Bjerre Lund

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
TitelProceedings of the 2018 ACM Conference on Economics and Computation : EC '18
ForlagAssociation for Computing Machinery
Publikationsdato2018
Sider113-130
ISBN (Trykt)978-1-4503-5829-3
DOI
StatusUdgivet - 2018
BegivenhedThe nineteenth ACM conference on Economics and Computation (ACM EC’18) - Cornell University, Ithaca, USA
Varighed: 18 jun. 201822 jun. 2018
Konferencens nummer: 19
http://www.sigecom.org/ec18/

Konference

KonferenceThe nineteenth ACM conference on Economics and Computation (ACM EC’18)
Nummer19
LokationCornell University
Land/OmrådeUSA
ByIthaca
Periode18/06/201822/06/2018
Internetadresse

Fingeraftryk

Dyk ned i forskningsemnerne om 'Computational Complexity of Proper Equilibrium'. Sammen danner de et unikt fingeraftryk.

Citationsformater