論文の概要: Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2611.07089v1
• Date: Wed, 04 Nov 2026 19:52:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 21:50:50.44163
• Title: Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games
• Title（参考訳）: 2プレーヤゼロサムゲームにおける指数型固有平衡の多項式時間計算
• Abstract要約: 有限 2-player 0-sum wide-form game において,厳密なワイドフォーム固有平衡を計算するための決定論的時間アルゴリズムを提案する。 提案アルゴリズムは,各情報に許容可能な動作確率の幾何学的パームタを割り当てる。 結果として生じる確率は有理であり、実現が消える情報集合を含む符号化長を持つ。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.
• Abstract（参考訳）: 完全リコールおよび有理データを持つ有限2プレイヤーゼロサムワイドフォームゲームにおいて, 厳密なワイドフォーム固有平衡を計算するための決定論的多項式時間アルゴリズムを提案する。 情報セットでのアクションはより良いアクションに対して罰せられるが、プレイヤー自身の将来のアクションを含む他のすべてのローカルな行動選択は固定されている。 提案アルゴリズムは,各情報に許容可能な動作確率の幾何学的ペルムタヘドロンを割り当てる。 スケールされた二重確率表現は、これらの制限を多項式サイズのシーケンス形式のポリトープに埋め込む; サドル点は局所的な$\varepsilon$-propernessの不等式を満たす。 任意に小さな数値摂動で解よりも正確な平衡を得るため、パラメトリック線形系の符号安定性を確立し、持続可能な基礎を構築し、行動比の限界を抽出する。 結果として生じる確率は有理であり、実現確率がなくなる情報集合を含む多項式符号化長を持つ。

関連論文リスト

• A Compositional Theory of Causally Masked Transformers [50.88598486616582]
  モデルが実装した力学から直接表現性を導出する形式化を開発する。 各アテンションヘッドは、レイヤ内で独立して自身の状態を更新する。 修正されたソフトアテンションは、不可逆なチェックリストのような状態をサポートする。
  論文  参考訳（メタデータ） (2026-07-29T14:47:19Z)
• Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games [0.0]
  マルチプレイヤー不完全情報ゲームにおけるナッシュ均衡の近似手法を提案する。 非線形相補性定式化におけるスラック変数と乗算変数の有限境界を導出する。 提案した境界が3人プレイヤのクーンポーカーの正確なナッシュ平衡に与える影響を実証する。
  論文  参考訳（メタデータ） (2026-06-24T16:08:33Z)
• Asymmetric Nash Seeking via Best Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models [0.0]
  ナッシュ均衡(Nash equilibria)は、マルチエージェントの意思決定と制御における相互作用をモデル化するための原則的なフレームワークを提供する。 この手紙は、非対称情報 2-プレーヤ制約付きゲームのクラスを分離可能な集合で研究する。
  論文  参考訳（メタデータ） (2026-03-17T18:45:56Z)
• Going from a Representative Agent to Counterfactuals in Combinatorial Choice [1.7074019866492325]
  本稿では,二元多面体の集合からデータを抽出する意思決定問題について検討する。 本稿では,代表エージェントモデルに基づく非パラメトリックな非実例推論手法を提案する。
  論文  参考訳（メタデータ） (2025-05-29T15:24:23Z)
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。 正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
  論文  参考訳（メタデータ） (2021-05-27T06:10:24Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。