The computational complexity of trembling hand perfection and other equilibrium refinements

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Department of Computer Science
The king of refinements of Nash equilibrium is trembling hand perfection. We show that it is NP-hard and Sqrt-Sum-hard to decide if a given pure strategy Nash equilibrium of a given three-player game in strategic form with integer payoffs is trembling hand perfect. Analogous results are shown for a number of other solution concepts, including proper equilibrium, (the strategy part of) sequential equilibrium, quasi-perfect equilibrium and CURB.
The proofs all use a reduction from the problem of comparing the minmax value of a three-player game in strategic form to a given rational number. This problem was previously shown to be NP-hard by Borgs et al., while a Sqrt-Sum hardness result is given in this paper. The latter proof yields bounds on the algebraic degree of the minmax value of a three-player game that may be of independent interest.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume6386
Pages (from-to)198-209
Number of pages12
ISSN0302-9743
DOIs
Publication statusPublished - 2010
EventAlgorithmic Game Theory, Third International Symposium - Athen, Greece
Duration: 18 Oct 201020 Oct 2010
Conference number: 3

Conference

ConferenceAlgorithmic Game Theory, Third International Symposium
Number3
CountryGreece
CityAthen
Period18/10/201020/10/2010

Bibliographical note

Title of the vol.: Algorithmic Game Theory, international Symposium, SAGT. Proceedings. / Spyros Kontogiannis, Elias Koutsoupias and Paul G. Spirakis (eds.)
ISBN: 978-3-642-16169-8

See relations at Aarhus University Citationformats

ID: 32837275