Download

PDF

Practical Exact Algorithm for Trembling-Hand Equilibrium Refinements in Games

Gabriele Farina, Nicola Gatti and Tuomas Sandholm

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.

Bibtex entry

@inproceedings{Farina18:Practical, title={Practical Exact Algorithm for Trembling-Hand Equilibrium Refinements in Games}, author={Farina, Gabriele and Gatti, Nicola and Sandholm, Tuomas}, booktitle={Conference on Neural Information Processing Systems (NIPS)}, year={2018} }