## 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 |