Fugu-MT 論文翻訳(概要): Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games

論文の概要: Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games

arxiv url: http://arxiv.org/abs/2610.25524v1
Date: Sun, 18 Oct 2026 20:37:56 GMT
ステータス: 情報取得中
システム内更新日: 2026-10-20 22:34:31.668243
Title: Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games
Title（参考訳）: シンメトリクスゲームにおける近似ナッシュ平衡の1/3バリアの破壊
Abstract要約: 対称ビマトリクスゲームにおいて、1/3$の近似障壁を破る最初の非条件のファミリ・オブ・タイムアルゴリズムを与える。固定された$>0$に対して、このファミリーのアルゴリズムは対称な$(1-1/sqrt2+)$-approx Nashimate平衡を計算する。
参考スコア（独自算出の注目度）: 46.31158375592562
License:
Abstract: We give the first unconditional family of polynomial-time algorithms that breaks the $1/3$ approximation barrier for symmetric bimatrix games. For every fixed $δ>0$, an algorithm in this family computes a symmetric $(1-1/\sqrt{2}+δ)$-approximate Nash equilibrium, improving on the previous best guarantee of $(1/3+δ)$ due to Kontogiannis and Spirakis [2011].
Abstract（参考訳）: 対称二行列ゲームに対する$1/3$近似障壁を破る多項式時間アルゴリズムの最初の無条件族を与える。すべての固定された$δ>0$に対して、このファミリーのアルゴリズムは対称な$(1-1/\sqrt{2}+δ)$-approximate Nash平衡を計算し、Kontogiannis と Spirakis [2011] による以前の最高保証である$(1/3+δ)$を改善する。

関連論文リスト

Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
論文参考訳（メタデータ） (2026-09-30T18:26:29Z)
Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games [2.7340036787711646]
量子ゼロサムゲームにおける$$$-approximate Nashlibriaを$O(1/varepsilon)$ average-iterate guaranteeで調べる。最大混合初期状態を含む一様平均出力に対して、$ (1/varepsilon)$低い境界を証明します。分離された固定ゲームは、初期状態の族間での定数係数による初期誤差を減少させるのに、任意に長い遅延を示す。
論文参考訳（メタデータ） (2026-09-30T02:54:14Z)
On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling [6.908972852063454]
相関クラスタリング(CC)は基本的な教師なし学習プリミティブである。 LPベースの保証を維持するためには,どの程度のエッジ情報が必要であるかを検討する。ヤオのミニマックス原理を通して、擬距離構造がなければ、任意のアルゴリズムが$o(n)$一様ランダムエッジを観測すると近似比が生じることを示す。
論文参考訳（メタデータ） (2026-02-14T09:12:15Z)
Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文参考訳（メタデータ） (2025-02-25T19:08:26Z)
The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria [37.300102993926046]
我々は、$max_mathbfwinmathcalWmin_mathbfpinDeltamathbfptopAmathbfw$という形式の行列ゲームを解く問題を研究する。この問題は、線形セパレータの発見やゼロサムゲームにおけるナッシュ平衡の計算といった標準的なタスクをカプセル化する。
論文参考訳（メタデータ） (2024-12-09T20:58:26Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [71.73971094342349]
本稿では,Regret$+$ (RM$+$) に基づく2プレーヤゼロサムゲーム解決アルゴリズムの終点収束特性について検討する。我々の分析は、アルゴリズムの極限点の幾何学的構造を新たに解析し、最終点収束に関する文献の大半から大きく離れていることを示す。
論文参考訳（メタデータ） (2023-11-01T17:34:58Z)
Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices [0.5439020425819]
2つのプレイヤーゼロサム微分可能なゲームに対する勾配法の局所的ナッシュ平衡の収束について検討する。偏曲のおかげで、円錐粒子法 -- 重みを最適化し、混合戦略をサポートする -- は、固定支持法よりも一般的に収束する。
論文参考訳（メタデータ） (2023-05-26T21:43:56Z)

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