二人零和博弈中扩展式恰当均衡的多项式时间计算方法
Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games
AI 导读
研究者为完美回忆且数据有理的有限二人零和扩展式博弈提出一种确定性多项式时间算法，可计算精确的扩展式恰当均衡。算法为每个信息集分配几何 permutahedron 约束，通过缩放双随机表示嵌入多项式规模的序列形式多面体，再由鞍点满足局部 ε-properness 不等式，并借助参数线性系统的符号稳定性提取精确解。所得均衡概率为有理数且编码长度为多项式级。
正文 · 原文
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.
| Subjects: | Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Multiagent Systems (cs.MA); Theoretical Economics (econ.TH) |
| Cite as: | arXiv:2611.07089 [cs.GT] |
| (or arXiv:2611.07089v1 [cs.GT] for this version) | |
| https://doi.org/10.48550/arXiv.2611.07089 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Sam Ganzfried [view email]
[v1]
Wed, 4 Nov 2026 19:52:21 UTC (15 KB)
来源：arXiv cs.AI · arxiv.org