Regret Minimization in Behaviorally-Constrained Zero-Sum Games
This work addresses a scalability issue in game theory for practitioners by providing efficient algorithms for computing equilibrium refinements, which are incremental improvements over existing methods.
The paper tackles the problem of computing Nash equilibrium refinements in extensive-form games, which address deficiencies in standard Nash equilibria by providing guarantees on off-equilibrium play. The authors develop a method based on counterfactual regret minimization that finds solutions with substantially better refinement properties while maintaining a convergence rate comparable to state-of-the-art Nash equilibrium algorithms.
No-regret learning has emerged as a powerful tool for solving extensive-form games. This was facilitated by the counterfactual-regret minimization (CFR) framework, which relies on the instantiation of regret minimizers for simplexes at each information set of the game. We use an instantiation of the CFR framework to develop algorithms for solving behaviorally-constrained (and, as a special case, perturbed in the Selten sense) extensive-form games, which allows us to compute approximate Nash equilibrium refinements. Nash equilibrium refinements are motivated by a major deficiency in Nash equilibrium: it provides virtually no guarantees on how it will play in parts of the game tree that are reached with zero probability. Refinements can mend this issue, but have not been adopted in practice, mostly due to a lack of scalable algorithms. We show that, compared to standard algorithms, our method finds solutions that have substantially better refinement properties, while enjoying a convergence rate that is comparable to that of state-of-the-art algorithms for Nash equilibrium computation both in theory and practice.