The Complexity of Proper Equilibrium in Extensive-Form and Polytope Games

Brian Hu Zhang, Ioannis Anagnostides, Kiriaki Fragkia, Maria-Florina Balcan, Tuomas Sandholm

TL;DR

This paper resolves a 20-year-old open problem by proving that computing a "proper equilibrium"—a gold-standard refinement of the Nash equilibrium—in extensive-form games is no harder than finding a standard Nash equilibrium. Surprisingly, the authors also demonstrate that for a broader class called "polytope games," finding this same equilibrium is NP-hard, marking the first known case where an equilibrium refinement is strictly harder to compute than the base Nash equilibrium.

What Problem Does This Paper Address?

In game theory, the Nash equilibrium is the foundational solution concept, but it has a famous flaw: it can sometimes prescribe "unreasonable" strategies, such as non-credible threats. To fix this, researchers developed refinements. Myerson’s proper equilibrium (1978) is often called the "mother of all refinements" because it assumes that while players might make mistakes ("trembles"), they are significantly less likely to make "costly" mistakes than "cheap" ones.

While we’ve known the computational complexity of finding proper equilibria in simple "normal-form" (table-based) games for years, the complexity for Extensive-Form Games (EFGs)—which model sequential moves and hidden information—remained a major open question since 2008. The challenge is that EFGs have a number of pure strategies that grows exponentially with the size of the game tree, making traditional "sorting-based" approaches to perturbations computationally impossible.

Methods

The authors tackle the problem by breaking a long-standing "permutahedron barrier."

  1. Hardness of the Classic Approach: They first prove that the standard method for defining proper equilibria (the Kohlberg-Mertens perturbation) is #P-hard to compute. This explains why previous researchers struggled to find efficient algorithms.
  2. Sequentially Proper Best Responses: To bypass the #P-hardness, the authors introduce a new technique. Instead of trying to sort an exponential number of strategies, they develop a way to compute a "perturbed best response" that works at the level of individual sequences in the game tree.
  3. Arithmetic Circuits and CLF Gates: They use a framework of Conditional Linear Feasibility (CLF) gates within arithmetic circuits. This allows them to express the equilibrium conditions as a fixed-point problem, proving that the problem belongs to the complexity classes PPAD (for 2-player games) and FIXP$_a$ (for multi-player games).

Datasets

This is a theoretical paper focused on computational complexity and algorithmic proofs; therefore, no empirical datasets or benchmarks were used for training or evaluation.

Key Insights and Ideas

  • The Structure Matters: The most profound insight is the divergence between EFGs and polytope games. In most game theory research, if you can solve a problem for an EFG, you can solve it for a polytope game (a game where strategies are defined by general linear constraints). This paper shows that for proper equilibria, the specific tree structure of an EFG allows for an "algorithmic shortcut" that general polytopes do not possess.
  • Refinements Aren't Always "Free": Usually, the complexity of a refined equilibrium "collapses" to the complexity of the Nash equilibrium. This paper provides the first natural example where this collapse does not happen (in polytope games), showing that refinements can be fundamentally more difficult to find.
  • Coordinate-Level Perturbation: The authors show that you don't need to perturb every possible strategy to achieve "properness." Perturbing at the level of coordinates (sequences) is sufficient and much more efficient.

Key Results

  • EFG Completeness: The paper proves that finding a normal-form proper equilibrium in an EFG is PPAD-complete for two players and FIXP$_a$-complete for three or more players. This effectively means it is no harder than finding a standard Nash equilibrium.
  • Polytope Game Hardness: In a "stark contrast," they prove that finding a proper equilibrium in a polytope game is NP-hard. This is a significant result because Nash equilibria in these games are still in PPAD/FIXP.
  • KM Best Response: They formally show that computing a Kohlberg-Mertens best response is #P-hard even in Bayesian games, justifying the need for their new "sequential" approach.

Limitations and Future Work

  • Exact Polytope Complexity: While the authors proved NP-hardness for polytope games, they haven't yet pinpointed the exact complexity class (e.g., is it in $\Sigma_2^P$?).
  • Broader Classes: The authors suggest looking for other classes of games (between EFGs and general polytope games) where proper equilibria might still be efficiently computable.
  • Extended Proper Equilibrium: A newer, even stricter refinement called "extended proper equilibrium" was recently proposed. The authors leave it as an open question whether their techniques can be adapted to this even more complex concept.

Summary updated

Abstract

The proper equilibrium, introduced by Myerson (1978), is a classic refinement of the Nash equilibrium that has been referred to as the "mother of all refinements." For normal-form games, computing a proper equilibrium is known to be PPAD-complete for two-player games and FIXP$_a$-complete for games with at least three players. However, the complexity beyond normal-form games -- in particular, for extensive-form games (EFGs) -- was a long-standing open problem first highlighted by Miltersen and Sørensen (SODA '08). In this paper, we resolve this problem by establishing PPAD- and FIXP$_a$-membership (and hence completeness) of normal-form proper equilibria in two-player and multi-player EFGs respectively. Our main ingredient is a technique for computing a perturbed (proper) best response that can be computed efficiently in EFGs. This is despite the fact that, as we show, computing a best response using the classic perturbation of Kohlberg and Mertens based on the permutahedron is #P-hard even in Bayesian games. In stark contrast, we show that computing a proper equilibrium in polytope games is NP-hard. This marks the first natural class in which the complexity of computing equilibrium refinements does not collapse to that of Nash equilibria, and the first problem in which equilibrium computation in polytope games is strictly harder -- unless there is a collapse in the complexity hierarchy -- relative to extensive-form games.
BibTeX
@misc{zhang2026complexity,
  author = {Brian Hu Zhang and Ioannis Anagnostides and Kiriaki Fragkia and Maria-Florina Balcan and Tuomas Sandholm},
  title = {{The Complexity of Proper Equilibrium in Extensive-Form and Polytope Games}},
  year = {2026},
  eprint = {2602.10096},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.10096},
}

Loading related content...

Figure