Equilibrium Refinement for the Age of Machines: The One-Sided Quasi-Perfect Equilibrium

Gabriele Farina, Tuomas SandholmNeurIPS 2021 · OpenReview

Introduction

In two-player zero-sum games, the Nash equilibrium (NE) is widely considered the gold standard for optimal play. However, standard Nash equilibrium strategies often fail in the real world because they assume opponents are perfectly rational and will not make mistakes. When an opponent does make an error, moving the game into an unexpected state (an off-equilibrium path), a standard NE strategy might suddenly behave irrationally or fail to capitalize on the mistake.

To address this, game theorists use "refinements" like trembling-hand perfection, which assume players have "shaky hands" and might accidentally choose any sub-optimal move with some tiny probability $\epsilon$. This forces the strategy to remain rational everywhere in the game tree. Unfortunately, existing refinements are "two-sided"—they assume both players make mistakes. This makes them computationally brutal and numerically unstable, preventing their use in large-scale, real-world games like professional poker.

This paper introduces one-sided quasi-perfect equilibrium (QPE), a novel refinement tailored for the "Age of Machines." It assumes a "machine" player is perfectly rational while its opponent remains prone to errors. This asymmetric approach is 4–5x faster to compute than previous methods and is the first to scale to massive real-world poker endgames.

Methods: The One-Sided QPE Approach

The core innovation of one-sided QPE is its asymmetric assumption: the AI (the machine) is perfectly rational and never makes mistakes, while only the imperfect player (the human or opponent) "trembles."

An example game tree illustrating trembling-hand probabilities, where actions are taken with a small probability $\epsilon$.

Technically, the authors formulate this as a trembling linear program. In traditional two-sided refinements, the error term $\epsilon$ appears in the constraints of the optimization problem. As $\epsilon$ approaches zero, this leads to massive numerical instability.

In one-sided QPE, the authors prove a crucial mathematical property: $\epsilon$ only needs to appear in the objective function. Because the constraints remain constant, they can use a modified version of the simplex algorithm with a "basis-stability oracle." The solver finds a solution for a small $\epsilon$ and then efficiently checks if that solution remains optimal as $\epsilon$ shrinks to zero. This allows them to "warm-start" the solver, drastically reducing the computational overhead at each step.

Experimental Validation

The authors evaluated one-sided QPE on several standard game theory benchmarks and one high-stakes real-world scenario:

  • Leduc Poker: Instances with 5, 9, and 13 ranks.
  • Goofspiel: A strategic card game (4 ranks).
  • Liar’s Dice: A classic bluffing game.
  • River Endgame: A specific "river" (final betting round) situation taken from the famous Libratus vs. human professionals match in Heads-Up No-Limit Texas Hold'em. This massive instance involved 21 million terminal states.

Key Insights and Results

  • Computational Speedup: One-sided QPE was consistently 4–5x faster to compute than traditional two-sided QPE across all benchmark games.
  • Scaling to the "River": This marks the first time a sequentially rational refinement has been computed for a real poker endgame of this magnitude. Traditional methods (like EFPE and two-sided QPE) failed entirely on this dataset due to numerical instability or crashing the solver.
  • Exploiting Imperfection: When tested against imperfect opponents generated by Counterfactual Regret Minimization (CFR), the one-sided QPE strategy achieved higher expected utility than standard Nash equilibrium strategies. It effectively "punished" the sub-optimal trembles of the CFR agents.
  • Sequential Rationality: The one-sided QPE maintains "sequential rationality," ensuring the machine plays optimally even in sub-parts of the game tree that should theoretically never be reached in perfect play.

Limitations and Future Work

While highly effective for zero-sum games, the authors caution that this one-sided approach does not translate well to general-sum games. In scenarios where players are not in total conflict, modeling your own potential mistakes is often necessary to avoid falling for "non-credible threats."

Furthermore, while one-sided QPE is 5x faster than other refinements, it remains 1–2 orders of magnitude slower than computing an unrefined Nash equilibrium using commercial solvers. Finally, while the AI successfully exploits algorithmic opponents, formal trials are still needed to see if one-sided QPE performs significantly better against actual human professionals compared to the baseline strategies used by milestone bots like Libratus.

Summary updated

Abstract

In two-player zero-sum extensive-form games, Nash equilibrium prescribes optimal strategies against perfectly rational opponents. However, it does not guarantee rational play in parts of the game tree that can only be reached by the players making mistakes. This can be problematic when operationalizing equilibria in the real world among imperfect players. Trembling-hand refinements are a sound remedy to this issue, and are subsets of Nash equilibria that are designed to handle the possibility that any of the players may make mistakes. In this paper, we initiate the study of equilibrium refinements for settings where one of the players is perfectly rational (the ``machine'') and the other may make mistakes. As we show, this endeavor has many pitfalls: many intuitively appealing approaches to refinement fail in various ways. On the positive side, we introduce a modification of the classical quasi-perfect equilibrium (QPE) refinement, which we call the one-sided quasi-perfect equilibrium. Unlike QPE, one-sided QPE only accounts for mistakes from one player and assumes that no mistakes will be made by the machine. We present experiments on standard benchmark games and an endgame from the famous man-machine match where the AI Libratus was the first to beat top human specialist professionals in heads-up no-limit Texas hold'em poker. We show that one-sided QPE can be computed more efficiently than all known prior refinements, paving the way to wider adoption of Nash equilibrium refinements in settings with perfectly rational machines (or humans perfectly actuating machine-generated strategies) that interact with players prone to mistakes. We also show that one-sided QPE tends to play better than a Nash equilibrium strategy against imperfect opponents.
BibTeX
@inproceedings{farina2021equilibrium,
  author = {Gabriele Farina and Tuomas Sandholm},
  title = {{Equilibrium Refinement for the Age of Machines: The One-Sided Quasi-Perfect Equilibrium}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=XsuEvfxv_C7},
}
Figure