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

Aarhus University

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › 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.

Original language	English
Title of host publication	Proceedings of the 2018 ACM Conference on Economics and Computation : EC '18
Publisher	Association for Computing Machinery
Publication date	2018
Pages	113-130
ISBN (Print)	978-1-4503-5829-3
DOIs	https://doi.org/10.1145/3219166.3219199
Publication status	Published - 2018
Event	The nineteenth ACM conference on Economics and Computation (ACM EC’18) - Cornell University, Ithaca, United States Duration: 18 Jun 2018 → 22 Jun 2018 Conference number: 19 http://www.sigecom.org/ec18/

Conference

Conference	The nineteenth ACM conference on Economics and Computation (ACM EC’18)
Number	19
Location	Cornell University
Country/Territory	United States
City	Ithaca
Period	18/06/2018 → 22/06/2018
Internet address	http://www.sigecom.org/ec18/

Keywords

Computational Complexity
Proper Equilibrium
Finite Games
NP-Complete
PPAD-Complete

Access to Document

10.1145/3219166.3219199

p113-hansenFinal published version, 1.3 MB

Cite this

@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, 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

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

Conference

Keywords

Access to Document

Fingerprint

Cite this