Abstract
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.
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 language | English |
|---|---|
| Book series | Lecture Notes in Computer Science |
| Volume | 6386 |
| Pages (from-to) | 198-209 |
| Number of pages | 12 |
| ISSN | 0302-9743 |
| DOIs | |
| Publication status | Published - 2010 |
| Event | Algorithmic Game Theory, Third International Symposium - Athen, Greece Duration: 18 Oct 2010 → 20 Oct 2010 Conference number: 3 |
Conference
| Conference | Algorithmic Game Theory, Third International Symposium |
|---|---|
| Number | 3 |
| Country/Territory | Greece |
| City | Athen |
| Period | 18/10/2010 → 20/10/2010 |