論文の概要: Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy
- arxiv url: http://arxiv.org/abs/2304.05005v2
- Date: Sun, 29 Jun 2025 13:53:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-01 21:27:53.269524
- Title: Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy
- Title（参考訳）: ベイズ相関平衡、ベイズゲームにおける非回帰力学、およびアナーキーの価格
- Authors: Kaito Fujii,
- Abstract要約: 本稿では,非直交スワップ後悔を線形上界で最小化するための効率的なアルゴリズムを提案する。
我々は、ベイズ-ナッシュ均衡から平衡への滑らかさの議論に基づいて、アナーキーの価格に関する既存の下限を拡大する。
- 参考スコア（独自算出の注目度）: 8.430481660019451
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper investigates equilibrium computation and the price of anarchy for Bayesian games, which are the fundamental models of games with incomplete information. In normal-form games with complete information, it is known that efficiently computable no-regret dynamics converge to correlated equilibria, and the price of anarchy for correlated equilibria can be bounded for a broad class of games called smooth games. However, in Bayesian games, as surveyed by Forges (1993), several non-equivalent extensions of correlated equilibria exist, and it remains unclear whether they can be efficiently computed or whether their price of anarchy can be bounded. In this paper, we identify a natural extension of correlated equilibria that can be computed efficiently and is guaranteed to have bounds on the price of anarchy in various games. First, we propose a variant of regret called untruthful swap regret. If each player minimizes it in repeated play of Bayesian games, the empirical distribution of these dynamics is guaranteed to converge to communication equilibria, which is one of the extensions of correlated equilibria proposed by Myerson (1982). We present an efficient algorithm for minimizing untruthful swap regret with a sublinear upper bound, which we prove to be tight in terms of the number of types. As a result, by simulating the dynamics with our algorithm, we can approximately compute a communication equilibrium in polynomial time. Furthermore, we extend existing lower bounds on the price of anarchy based on the smoothness arguments from Bayes--Nash equilibria to equilibria obtained by the proposed dynamics.
- Abstract（参考訳）: 本稿では,不完全情報を持つゲームの基本モデルであるベイズゲームにおける平衡計算とアナーキーの価格について検討する。
完全情報を持つ正規形式ゲームでは、効率的に計算可能な非回帰力学が相関平衡に収束することが知られ、同値平衡のアナーキーの価格は、スムーズゲームと呼ばれる幅広い種類のゲームに対してバウンドすることができる。
しかし、 Forges (1993) が調査したベイズゲームでは、相関平衡の非等価な拡張がいくつか存在し、それらが効率的に計算できるのか、それらのアナーキーの値が有界なのかは不明である。
本稿では,様々なゲームにおいて,アナーキーの価格に制約が生じることを保証し,効率よく計算できる相関平衡の自然な拡張を同定する。
まず,不本意な言い換え後悔(unruthful swap regret)と呼ばれる後悔の変種を提案する。
各プレイヤーがベイズゲームの繰り返しプレイでそれを最小化すれば、これらの力学の経験的分布は通信平衡に収束することが保証される。
本稿では,非直交スワップ後悔を線形上界で最小化するアルゴリズムを提案する。
その結果、我々のアルゴリズムで力学をシミュレートすることで、多項式時間でおよそ通信平衡を計算することができる。
さらに、ベイズ-ナッシュ均衡から提案された力学によって得られる平衡への滑らかさの議論に基づいて、アナーキーの価格に関する既存の下限を拡張する。
関連論文リスト
- On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
非凹面ゲームはゲーム理論と最適化に重大な課題をもたらす。
Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
また,オンライングラディエントDescentは,非自明な状況下で効率よく$Phi$-equilibriaを近似できることを示した。
論文 参考訳（メタデータ） (2024-03-13T01:51:30Z) - Soft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and
Inverse Learning [37.176741793213694]
我々は、アフィン・マルコフゲームと呼ばれるマルコフゲームのクラスを定式化し、アフィン報酬関数はプレイヤーの行動と一致する。
我々は,各プレイヤーが有理的に有理であり,ソフト・ベルマンポリシーを選択するような,新しい解の概念,ソフト・ベルマン均衡を導入する。
そこで我々は,プロジェクテッド・グラディエント・アルゴリズムを用いて,観測された状態-行動軌跡からプレイヤーの報酬パラメータを推定する逆ゲーム問題を解く。
論文 参考訳（メタデータ） (2023-03-31T22:50:47Z) - Are Equivariant Equilibrium Approximators Beneficial? [3.947165805405381]
等変平衡近似器の利点と限界を理論的に特徴づける。
この利点のために、一般的なものよりもより優れた一般化性を示し、ペイオフ分布が置換不変である場合により良い近似を達成できることを示す。
限界については、均衡選択と社会福祉の観点から、それらの欠点について論じる。
論文 参考訳（メタデータ） (2023-01-27T01:11:41Z) - Observable Perfect Equilibrium [0.4895118383237099]
我々は、可観測完全均衡(observable perfect equilibrium)と呼ばれる拡張形式のゲームに対して、新しい平衡改善の概念を定義する。
我々は、観測可能な完全平衡は常に存在することを保証している。
我々は、観測可能な完全均衡が、人工知能に関心を持つ多くの重要な不完全な情報ゲームをモデル化する上で有用な平衡改善概念になることを期待する。
論文 参考訳（メタデータ） (2022-10-29T06:07:29Z) - Game-Theoretical Perspectives on Active Equilibria: A Preferred Solution
Concept over Nash Equilibria [61.093297204685264]
マルチエージェント強化学習における効果的なアプローチは,エージェントの学習プロセスを検討し,今後の政策に影響を与えることである。
この新たな解の概念は、ナッシュ均衡のような標準解の概念が活性平衡の特別な場合である、という一般的なものである。
我々は,ゲーム理論の観点から,ナッシュ平衡が知られている実例を綿密に研究することにより,アクティブ平衡を解析する。
論文 参考訳（メタデータ） (2022-10-28T14:45:39Z) - How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in
Urban Driving Games [64.71476526716668]
我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。
我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。
提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
論文 参考訳（メタデータ） (2022-10-24T09:32:40Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。
本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
論文 参考訳（メタデータ） (2021-02-23T05:11:07Z) - Game-theoretic Models of Moral and Other-Regarding Agents [0.0]
我々は、計算の難易度、高い調整コスト、一般的な正規形式ゲームへの高価でプロブレマ的な拡張など、そのような平衡性に関する多くの問題を強調する。
そこで本研究では,カンチアン平衡に関連する一般的,直感的,計算的,他的に考慮可能な平衡と,純粋に自己完結的行動とカンチアン行動とを補間する行動コースのクラスを提案する。
論文 参考訳（メタデータ） (2020-12-17T17:16:50Z) - Polynomial-Time Computation of Optimal Correlated Equilibria in
Two-Player Extensive-Form Games with Public Chance Moves and Beyond [107.14897720357631]
本研究では,公的なチャンス移動を伴う2人プレイヤゲームにおいて,最適相関平衡が時間内に計算可能であることを示す。
この結果、10年以上にわたる広範な形式の相関を取り巻く最大の正の複雑性結果が得られた。
論文 参考訳（メタデータ） (2020-09-09T14:51:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。