Computational Complexity of Proper Equilibrium

Kristoffer Arnsfelt Hansen; Troels Bjerre Lund

doi:10.1145/3219166.3219199

Computational Complexity of Proper Equilibrium

Kristoffer Arnsfelt Hansen, Troels Bjerre Lund

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

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	https://doi.org/10.1145/3219166.3219199
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	http://www.sigecom.org/ec18/

Adgang til dokumentet

10.1145/3219166.3219199

p113-hansenForlagets udgivne version, 1,3 MB

Citationsformater

@inproceedings{bbfe694248544afa86e6c8743128eda4,

title = "Computational Complexity of Proper Equilibrium",

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.",

keywords = "Computational Complexity, Proper Equilibrium, Finite Games, NP-Complete, PPAD-Complete",

author = "Hansen, {Kristoffer Arnsfelt} and Lund, {Troels Bjerre}",

year = "2018",

doi = "10.1145/3219166.3219199",

language = "English",

isbn = "978-1-4503-5829-3",

pages = "113--130",

booktitle = "Proceedings of the 2018 ACM Conference on Economics and Computation",

publisher = "Association for Computing Machinery",

address = "United States",

note = "The nineteenth ACM conference on Economics and Computation (ACM EC{\textquoteright}18), ACM EC'18 ; Conference date: 18-06-2018 Through 22-06-2018",

url = "http://www.sigecom.org/ec18/",

}

TY - GEN

T1 - Computational Complexity of Proper Equilibrium

AU - Hansen, Kristoffer Arnsfelt

AU - Lund, Troels Bjerre

N1 - Conference code: 19

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Computational Complexity

KW - Proper Equilibrium

KW - Finite Games

KW - NP-Complete

KW - PPAD-Complete

U2 - 10.1145/3219166.3219199

DO - 10.1145/3219166.3219199

M3 - Article in proceedings

SN - 978-1-4503-5829-3

SP - 113

EP - 130

BT - Proceedings of the 2018 ACM Conference on Economics and Computation

PB - Association for Computing Machinery

T2 - The nineteenth ACM conference on Economics and Computation (ACM EC’18)

Y2 - 18 June 2018 through 22 June 2018

ER -

Computational Complexity of Proper Equilibrium

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater