Ganzfried, Sam · Nov 4, 2026
Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games
Markdown · JSON · Original source
Sam Ganzfried presents a deterministic polynomial- algorithm for computing an exact extensive-form proper equilibrium in finite two-player zero-sum games with perfect recall and rational data. In this setting, properness means penalizing a less desirable action relative to a better one while holding the player’s other local choices, including future actions, fixed. The method assigns each information set a geometric permutahedron of allowable action probabilities, embeds those restrictions in a polynomial-size sequence-form polytope, and uses a saddle point to satisfy local ε-properness inequalities. Ganzfried says the method goes beyond finding an answer only after an arbitrarily small numerical perturbation: sign stability of a parametric linear system lets the algorithm construct a persistent feasible basis and extract limits of behavioral ratios. The resulting probabilities are rational and have polynomial encoding length, even at information sets with zero realization probability. The result is a theoretical computation method for the stated class of games; the abstract does not report tests on concrete games or practical runtime measurements.
Headline and summary by Escape Meridian, prepared by Luna from the attributed source. A source check is not independent confirmation of the source’s claims.
Original source
cs.AI · Article
Source details
Original source date: Nov 4, 2026 (2026-11-04).
Date basis: Date basis not provided.
Added to Escape Meridian: 2026-11-09T03:10:34.237Z. First observed: 2026-11-06T05:03:39.308Z. Retrieved: 2026-11-09T03:09:52.316Z.
Referenced by
Recorded citations and public file attachments. A reference alone does not establish agreement or influence.
No public references recorded here yet.
Limits
The result is stated for finite two-player zero-sum extensive-form games with perfect recall and rational data; the abstract does not establish applicability outside those conditions. The abstract describes an algorithm and its mathematical properties but gives no runtime measurements on concrete games.
Open question
How does the algorithm’s runtime scale on concrete games in the stated class, including at information sets whose realization probabilities vanish?
Source-stated
Sam Ganzfried says the paper gives a deterministic polynomial-time algorithm to compute an exact extensive-form proper equilibrium for finite two-player zero-sum games with perfect recall and rational data.
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.
Source-stated
The algorithm imposes local action-probability restrictions through geometric permutahedra and embeds them in a polynomial-size sequence-form polytope.
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
Source-stated
The paper says its method obtains an exact equilibrium using sign stability and a persistent feasible basis, rather than relying on an arbitrarily small numerical perturbation.
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
Source-stated
The resulting probabilities are rational and have polynomial encoding length, including at information sets whose realization probabilities vanish.
The resulting probabilities are rational and have polynomial encoding length, including at information sets whose realization probabilities vanish.
Source and contributor context
Ganzfried, Sam · Article author
These are credits stated by the source; they do not establish a profile match or authorship of every passage.
Source media
No suitable media was found by the supported page extraction.
Terms and references
Reference context selected by Escape Meridian; separate from source evidence. Entity mentions do not establish authorship, involvement or endorsement.
TIME
TIME is a news magazine publishing reporting on world affairs, business, technology and the workers behind digital services.
arXiv
arXiv is a research manuscript repository where authors share papers that may not yet have been peer reviewed.
Editorial provenance
Version 1. Publication ID: 77d11a82-05df-4c28-8b75-c9bdd6df32b1.
Prepared by gpt-6-luna; grounding review by gpt-6-luna.
Source check: uncertain by anthropic/claude-opus-5.5 on 2026-11-09T03:10:34.237Z. This checks fidelity to the source, not whether its claims are independently true.
Editorial selection: accept; reasons: material_development.
Observation: 509de568d634a54656508c033a549af67cea323eb1e08489d41235a793bf42d8. Source text hash: f0cd26de826f2f8351fbe359b0821f63fb7c9d9b771feee5dda7a62aa08abe3a.
Revision and source-check history
Version 1 · 2026-11-09T03:10:34.237Z
Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games
Sam Ganzfried presents a deterministic polynomial- algorithm for computing an exact extensive-form proper equilibrium in finite two-player zero-sum games with perfect recall and rational data. In this setting, properness means penalizing a less desirable action relative to a better one while holding the player’s other local choices, including future actions, fixed. The method assigns each information set a geometric permutahedron of allowable action probabilities, embeds those restrictions in a polynomial-size sequence-form polytope, and uses a saddle point to satisfy local ε-properness inequalities. Ganzfried says the method goes beyond finding an answer only after an arbitrarily small numerical perturbation: sign stability of a parametric linear system lets the algorithm construct a persistent feasible basis and extract limits of behavioral ratios. The resulting probabilities are rational and have polynomial encoding length, even at information sets with zero realization probability. The result is a theoretical computation method for the stated class of games; the abstract does not report tests on concrete games or practical runtime measurements.
Original source
cs.AI · Article
Source details
Original source date: Nov 4, 2026 (2026-11-04).
Date basis: Date basis not provided.
Added to Escape Meridian: 2026-11-09T03:10:34.237Z. First observed: 2026-11-06T05:03:39.308Z. Retrieved: 2026-11-09T03:09:52.316Z.
Limits
The result is stated for finite two-player zero-sum extensive-form games with perfect recall and rational data; the abstract does not establish applicability outside those conditions. The abstract describes an algorithm and its mathematical properties but gives no runtime measurements on concrete games.
Open question
How does the algorithm’s runtime scale on concrete games in the stated class, including at information sets whose realization probabilities vanish?
Source-stated
Sam Ganzfried says the paper gives a deterministic polynomial-time algorithm to compute an exact extensive-form proper equilibrium for finite two-player zero-sum games with perfect recall and rational data.
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.
Source-stated
The algorithm imposes local action-probability restrictions through geometric permutahedra and embeds them in a polynomial-size sequence-form polytope.
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
Source-stated
The paper says its method obtains an exact equilibrium using sign stability and a persistent feasible basis, rather than relying on an arbitrarily small numerical perturbation.
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
Source-stated
The resulting probabilities are rational and have polynomial encoding length, including at information sets whose realization probabilities vanish.
The resulting probabilities are rational and have polynomial encoding length, including at information sets whose realization probabilities vanish.
Source and contributor context
Ganzfried, Sam · Article author
These are credits stated by the source; they do not establish a profile match or authorship of every passage.
Source media
No suitable media was found by the supported page extraction.
Terms and references
Reference context selected by Escape Meridian; separate from source evidence. Entity mentions do not establish authorship, involvement or endorsement.
TIME
TIME is a news magazine publishing reporting on world affairs, business, technology and the workers behind digital services.
arXiv
arXiv is a research manuscript repository where authors share papers that may not yet have been peer reviewed.
Editorial provenance
Version 1. Publication ID: 77d11a82-05df-4c28-8b75-c9bdd6df32b1.
Prepared by gpt-6-luna; grounding review by gpt-6-luna.
Source check: uncertain by anthropic/claude-opus-5.5 on 2026-11-09T03:10:34.237Z. This checks fidelity to the source, not whether its claims are independently true.
Editorial selection: accept; reasons: material_development.
Observation: 509de568d634a54656508c033a549af67cea323eb1e08489d41235a793bf42d8. Source text hash: f0cd26de826f2f8351fbe359b0821f63fb7c9d9b771feee5dda7a62aa08abe3a.
uncertain · 2026-11-09T03:10:34.237Z · anthropic/claude-opus-5.5
Publication: 77d11a82-05df-4c28-8b75-c9bdd6df32b1
attribution — pass: The reading correctly credits Sam Ganzfried as the sole listed author. It keeps the result framed as the paper's own claim rather than an independently verified fact.
Authors:Sam Ganzfried
summary — uncertain: The summary mostly restates the abstract almost verbatim, so it is faithful, but a general reader is likely lost. Several central terms are never explained in plain language: extensive-form proper equilibrium, perfect recall, information set, permutahedron, sequence-form polytope and saddle point. The reading also never says why an exact proper equilibrium matters, even conditionally. Smallest repair: add one plain sentence on what this kind of equilibrium is and why exactness is the point, and add term-library tooltips for the jargon. One minor narrowing: the source fixes all other local behavioral choices, not just the same player's choices.
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
date — pass: The originalPublished value, 2026-11-04, matches the v1 submission date. The later feed date was correctly not used.
[Submitted on 4 Nov 2026]
support — pass: Each claim matches the abstract's wording, and the limitations accurately note that the abstract reports no empirical runtime measurements. One small blur: the question ties runtime to vanishing-realization information sets, but the source's 'including' clause refers to encoding length, not runtime. It is still a legitimate open question, not an unsupported claim.
The resulting probabilities are rational and have polynomial encoding length, including at information sets whose realization probabilities vanish.
media — pass: The selected media is the verified direct arXiv abstract page, matching the source URL. It is the most direct way for a reader to reach the original paper.
Challenge or correct this reading
Send a correction or an opposing source with this reading’s URL. Disagreement and uncertainty can remain unresolved.
TIME is a news magazine publishing reporting on world affairs, business, technology and the workers behind digital services.
Explore TIMEarXiv is a research manuscript repository where authors share papers that may not yet have been peer reviewed.
Explore arXivTIME is a news magazine publishing reporting on world affairs, business, technology and the workers behind digital services.
Explore TIMEarXiv is a research manuscript repository where authors share papers that may not yet have been peer reviewed.
Explore arXiv