Practical Exact Algorithm For Trembling-hand Equilibrium Refinements In Games

Authors:
Gabriele Farina Carnegie Mellon University
Nicola Gatti Politecnico di Milano
Tuomas Sandholm Carnegie Mellon University

Introduction:

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.In this paper, the authors design an exact polynomial-time algorithm for finding trembling-hand equilibria in zero-sum extensive-form games.

Abstract:

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.

You may want to know: