論文の概要: Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
- arxiv url: http://arxiv.org/abs/2510.16782v1
- Date: Sun, 19 Oct 2025 10:14:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-25 00:56:39.142119
- Title: Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
- Title（参考訳）: 一般サムゲームにおける計算(粗い)関連平衡に対する近似量子アルゴリズム
- Authors: Tongyang Li, Xinzhao Wang, Yexin Zhang,
- Abstract要約: 一般ゲームの場合、ナッシュ平衡の計算はPPADハードであり、相関平衡の計算はゲーム理論において広く研究されている。
マルチプレイヤーの正規形式ゲームにおいて,$varepsilon$-approximate correlation equilibria (CE) と粗相関平衡 (CCE) を計算するための量子アルゴリズムについて検討した。
- 参考スコア（独自算出の注目度）: 14.684351170028853
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is PPAD-hard and the computing of a more general concept called correlated equilibria has been widely explored in game theory. In this paper, we initiate the study of quantum algorithms for computing $\varepsilon$-approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player normal-form games. Our approach utilizes quantum improvements to the multi-scale Multiplicative Weight Update (MWU) method for CE calculations, achieving a query complexity of $\tilde{O}(m\sqrt{n})$ for fixed $\varepsilon$. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity $\tilde{O}(m\sqrt{n}/\varepsilon^{2.5})$. Both algorithms demonstrate a near-optimal scaling in the number of players $m$ and actions $n$, as confirmed by our quantum query lower bounds.
- Abstract（参考訳）: 古典的および量子的設定におけるゼロサムゲームのナッシュ平衡を計算する。
一般ゲームの場合、ナッシュ平衡の計算はPPADハードであり、より一般的な概念である相関平衡の計算はゲーム理論において広く研究されている。
本稿では,マルチプレイヤの正規形式ゲームにおいて,$\varepsilon$-approximate equilibria (CE) と coarse equilibria (CCE) の量子アルゴリズムの研究を開始する。
提案手法は,CE計算におけるマルチスケール乗算重み更新法(MWU)の量子的改善を利用して,$\tilde{O}(m\sqrt{n})$ for fixed $\varepsilon$のクエリ複雑性を実現する。
CCEでは、ゼロサムゲームのための量子アルゴリズムからマルチプレイヤー設定まで、クエリ複雑性を$\tilde{O}(m\sqrt{n}/\varepsilon^{2.5})$に拡張する。
どちらのアルゴリズムも、量子クエリの低いバウンダリで確認されているように、プレイヤー数$m$とアクション$n$のほぼ最適スケーリングを示している。
関連論文リスト
- Quantum EigenGame for excited state calculation [8.957579200590988]
我々は、$0textth$-orderアプローチと量子コンピュータのためのEigenGameアルゴリズムを拡張した。
その結果、量子固有Gameを使うことで、デフレステップを必要とせずに、与えられたハミルトンの励起状態に収束できることを示した。
論文 参考訳（メタデータ） (2025-03-17T18:48:40Z) - Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
そこで我々は,Stackelbergの大規模相関平衡の計算アルゴリズムを提案する。
また,大域的相関平衡を近似計算するアルゴリズムも提案する。
ほぼ最適なEFCEのアルゴリズムは、私たちの知る限り、3つのデシラタを同時に達成した最初のアルゴリズムである。
論文 参考訳（メタデータ） (2024-12-22T09:12:05Z) - Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。
結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
論文 参考訳（メタデータ） (2024-11-04T00:39:52Z) - Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。
特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
論文 参考訳（メタデータ） (2024-11-04T00:34:56Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。
この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
論文 参考訳（メタデータ） (2023-11-17T20:38:38Z) - Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [10.79781442303645]
ゼロサムゲームを解くための最初のオンライン量子アルゴリズムを提案する。
我々のアルゴリズムは簡潔な記述を伴う古典的な出力を生成する。
我々のアルゴリズムの核心は、ギブスサンプリング問題に対する高速な量子マルチサンプリング手法である。
論文 参考訳（メタデータ） (2023-04-27T14:02:54Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。