Algorithm computes exact proper equilibria in two-player games
Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games
Computer Science and Game TheoryArtificial IntelligenceMultiagent Systems
Summary
Finding a balanced way for two players to make choices where neither can gain by changing their strategy is important for game theory. The authors provide a method to compute a specific balanced solution called an extensive-form proper equilibrium efficiently and exactly, even in complex games with many possible moves. This method deals with how to assign probabilities to moves carefully, ensuring the solution is mathematically stable and precise without relying on approximate guesses. Their approach advances the ability to analyze such strategic games with guaranteed exactness and manageable calculation time.
What this means in practice
- •For game theory software developers: Build software tools to compute exact proper equilibria in two-player zero-sum games efficiently for strategic analysis.
- •For strategic decision makers: Use exact equilibrium computations to better predict outcomes in competitive settings such as auctions or security scenarios with perfect recall.
Authors
Sam Ganzfried
Abstract
We give a deterministic polynomial-time algorithm for computing an exact extensive-form proper equilibrium in a finite two-player zero-sum extensive-form game with perfect recall and rational data. Properness is understood in the agent normal form: an action at an information set is penalized relative to a better action while all other local behavioral choices, including the player's own future actions, remain fixed. Our algorithm assigns each information set a geometric permutahedron of allowable action probabilities. A scaled doubly stochastic representation embeds these restrictions in a polynomial-size sequence-form polytope; a saddle point then satisfies the local $\varepsilon$-properness inequalities. To obtain an exact equilibrium rather than a solution at an arbitrarily small numerical perturbation, we establish sign stability of a parametric linear system, construct a persistent feasible basis, and extract the limits of behavioral ratios. The resulting probabilities are rational and have polynomial encoding length, including at information sets whose realization probabilities vanish.