Poster
Practical exact algorithm for trembling-hand equilibrium refinements in games
Gabriele Farina · Nicola Gatti · Tuomas Sandholm

Wed Dec 5th 10:45 AM -- 12:45 PM @ Room 210 #78
in Wed Poster Session A »

Nash equilibrium strategies have the known weakness that they do not prescribe rational play in situations that are reached with zero probability according to the strategies themselves, for example, if players have made mistakes. Trembling-hand refinements---such as extensive-form perfect equilibria and quasi-perfect equilibria---remedy this problem in sound ways. Despite their appeal, they have not received attention in practice since no known algorithm for computing them scales beyond toy instances. In this paper, we design an exact polynomial-time algorithm for finding trembling-hand equilibria in zero-sum extensive-form games. It is several orders of magnitude faster than the best prior ones, numerically stable, and quickly solves game instances with tens of thousands of nodes in the game tree. It enables, for the first time, the use of trembling-hand refinements in practice.

Keywords: Game Theory and Computational Economics

Author Information

Gabriele Farina (Carnegie Mellon University)
Nicola Gatti (Politecnico di Milano)
Tuomas Sandholm (Carnegie Mellon University)

More from the Same Authors