論文の概要: Bayes correlated equilibria and no-regret dynamics
- arxiv url: http://arxiv.org/abs/2304.05005v1
- Date: Tue, 11 Apr 2023 06:22:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-12 15:57:55.475182
- Title: Bayes correlated equilibria and no-regret dynamics
- Title（参考訳）: ベイズ相関平衡と非回帰力学
- Authors: Kaito Fujii
- Abstract要約: 本稿では,不完全情報を持つゲームの基本モデルであるベイズゲームに対する平衡概念について検討する。
我々は,各プレイヤーのプライベート情報を収集し,関連するレコメンデーションをプレイヤーに送信する仲介者によって実現可能なコミュニケーション均衡に焦点を当てる。
本稿では,非直交スワップ後悔を線形上界で最小化するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 9.89901717499058
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper explores equilibrium concepts for Bayesian games, which are
fundamental models of games with incomplete information. We aim at three
desirable properties of equilibria. First, equilibria can be naturally realized
by introducing a mediator into games. Second, an equilibrium can be computed
efficiently in a distributed fashion. Third, any equilibrium in that class
approximately maximizes social welfare, as measured by the price of anarchy,
for a broad class of games. These three properties allow players to compute an
equilibrium and realize it via a mediator, thereby settling into a stable state
with approximately optimal social welfare. Our main result is the existence of
an equilibrium concept that satisfies these three properties.
Toward this goal, we characterize various (non-equivalent) extensions of
correlated equilibria, collectively known as Bayes correlated equilibria. In
particular, we focus on communication equilibria (also known as coordination
mechanisms), which can be realized by a mediator who gathers each player's
private information and then sends correlated recommendations to the players.
We show that if each player minimizes a variant of regret called untruthful
swap regret in repeated play of Bayesian games, the empirical distribution of
these dynamics converges to a communication equilibrium. We present an
efficient algorithm for minimizing untruthful swap regret with a sublinear
upper bound, which we prove to be tight up to a multiplicative constant. As a
result, by simulating the dynamics with our algorithm, we can efficiently
compute an approximate communication equilibrium. 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（参考訳）: 本稿では,不完全情報を持つゲームの基本モデルであるベイズゲームに対する平衡概念について考察する。
平衡の3つの望ましい性質を目指しています。
まず、ゲームにメディエータを導入することで、平衡を自然に実現できる。
第二に、平衡は分散的に効率的に計算できる。
第3に、このクラスのいかなる均衡も、アナキシーの価格によって測定されるように、幅広い種類のゲームに対する社会福祉をほぼ最大化する。
これら3つの性質により、プレイヤーは平衡を計算し、仲介者を通してそれを実現することができ、それによってほぼ最適な社会福祉を持つ安定した状態に定着する。
私たちの主な結果は、これら3つの性質を満たす平衡概念の存在です。
この目的に向けて、同値平衡の様々な(非等価な)拡張を特徴づけ、まとめてベイズ同値平衡(Bayes equilibria)と呼ぶ。
特に,コミュニケーション均衡(コーディネーション機構とも呼ばれる)に着目し,各プレイヤーのプライベート情報を収集し,関連するレコメンデーションをプレイヤーに送信する仲介者によって実現される。
ベイズゲームの繰り返しプレイにおいて、各プレイヤーが不完全スワップ後悔と呼ばれる後悔の変種を最小化すれば、これらのダイナミクスの実験的分布はコミュニケーション均衡に収束する。
そこで本研究では,不真理なスワップ後悔を部分線形上界で最小化する効率的なアルゴリズムを提案する。
その結果、我々のアルゴリズムで力学をシミュレートすることで、近似通信平衡を効率的に計算することができる。
さらに,提案手法により得られた不定値に対する既定下限をベイズナッシュ平衡から平衡までスムース性議論に基づいて拡張する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。