---
title: "Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.07089v1"
permalink: "https://feed.astralor.com/items/itm_5003203f00b18e882104ca55"
published: "2026-11-04T19:52:21.000Z"
score: 56
channel: "ai"
tags: ["AI Agent","Polynomial-Time Computation","Extensive-Form Proper Equilibria","Two-Player Zero-Sum Games","Properness","Our"]
---

# Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games

## 速览

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 underst…

## 关键点

- 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 fix…
- Our algorithm assigns each information set a geometric permutahedron of allowable action probabilities.

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_5003203f00b18e882104ca55