Metraipolis › archive › dc_fcd8ecbf640e

Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games — arXiv:2611.07089

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.07089
License (as archived): CC0-1.0
Archived: 2026-11-06T14:41:24.988Z
SHA-256 of the archived text: a6e36c02ad675de02a04fd6e37784d6c5b291381c4b8d34b524f8bd58cfd3264
Stable URL of this page: https://metraipolis.com/documento/dc_fcd8ecbf640e

How to cite

Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games — arXiv:2611.07089 — arXiv (en), https://arxiv.org/abs/2611.07089 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fcd8ecbf640e (Metraipolis archive dc_fcd8ecbf640e, sha256 a6e36c02ad675de02a04fd6e37784d6c5b291381c4b8d34b524f8bd58cfd3264)

BibTeX

@misc{dcfcd8ecbf640e,
  title = {Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games — arXiv:2611.07089},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.07089},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fcd8ecbf640e; sha256 a6e36c02ad675de02a04fd6e37784d6c5b291381c4b8d34b524f8bd58cfd3264},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07089. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.MA, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Artificial Intelligence (cs.AI); Multiagent Systems (cs.MA); Theoretical Economics (econ.TH).
Pagina del lavoro: https://arxiv.org/abs/2611.07089 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:18:27.666Z dalla pagina https://arxiv.org/list/cs.MA/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).