論文の概要: Last-Iterate Convergence of No-Regret Learning for Equilibria in Bargaining Games

• arxiv url: http://arxiv.org/abs/2507.03150v1
• Date: Thu, 03 Jul 2025 20:12:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-08 15:46:34.596086
• Title: Last-Iterate Convergence of No-Regret Learning for Equilibria in Bargaining Games
• Title（参考訳）: バーゲティングゲームにおける不等式学習における不等式収束
• Authors: Serafina Kamp, Reese Liebman, Benjamin Fish,
• Abstract要約: 正規化リーダをフォローするアルゴリズムは,様々なゲームにおいて最後にナッシュ平衡に収束することを示す。 この研究は、単純な学習アルゴリズムを用いて、複雑な経済行動がもたらす影響を実証する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Bargaining games, where agents attempt to agree on how to split utility, are an important class of games used to study economic behavior, which motivates a study of online learning algorithms in these games. In this work, we tackle when no-regret learning algorithms converge to Nash equilibria in bargaining games. Recent results have shown that online algorithms related to Follow the Regularized Leader (FTRL) converge to Nash equilibria (NE) in the last iterate in a wide variety of games, including zero-sum games. However, bargaining games do not have the properties used previously to established convergence guarantees, even in the simplest case of the ultimatum game, which features a single take-it-or-leave-it offer. Nonetheless, we establish that FTRL (without the modifications necessary for zero-sum games) achieves last-iterate convergence to an approximate NE in the ultimatum game along with a bound on convergence time under mild assumptions. Further, we provide experimental results to demonstrate that convergence to NE, including NE with asymmetric payoffs, occurs under a broad range of initial conditions, both in the ultimatum game and in bargaining games with multiple rounds. This work demonstrates how complex economic behavior (e.g. learning to use threats and the existence of many possible equilibrium outcomes) can result from using a simple learning algorithm, and that FTRL can converge to equilibria in a more diverse set of games than previously known.
• Abstract（参考訳）: エージェントがユーティリティを分割する方法に同意しようとするバーゲティングゲームは、経済行動を研究するために使用されるゲームの重要なクラスであり、これらのゲームにおけるオンライン学習アルゴリズムの研究を動機付けている。 本研究では,非回帰学習アルゴリズムがバゲティングゲームにおいてナッシュ均衡に収束する場合に対処する。 近年の研究では、FTRL(Follow the Regularized Leader)に関連するオンラインアルゴリズムが、ゼロサムゲームを含む様々なゲームにおいて、最終回においてナッシュ均衡(NE)に収束していることが示されている。 しかし、バーゲティングゲームは、コンバージェンス保証を確立するために以前に使用されていた特性を持っておらず、単一のテイク・イ・リーブ・イットのオファーを特徴とする最後通しゲームにおいて最も単純な場合であってもである。 それでも、FTRL(ゼロサムゲームに必要となる修正を伴わない)は、アルティマトゥムゲームにおける近似NEへの最終点収束と、軽度の仮定による収束時間の境界を達成できる。 さらに、非対称なペイオフを持つNEを含むNEへの収束は、最後通しゲームと複数のラウンドを持つバーゲティングゲームの両方において、幅広い初期条件下で発生することを示す実験結果を提供する。 この研究は、単純な学習アルゴリズムを用いて、複雑な経済行動(例えば、脅威を使うための学習と、多くの可能な平衡結果の存在)がどのようにして得られるかを示し、FTRLは以前よりも多様なゲームで平衡に収束できることを示した。

関連論文リスト

• No-regret learning in harmonic games: Extrapolation in the face of conflicting interests [45.94247914236653]
  学習は任意の初期状態からナッシュ均衡に収束し、すべてのプレイヤーは、ほとんどのO(1)後悔において保証される。 結果は、ハーモニックゲームにおける非回帰学習の深い理解を提供する。
  論文  参考訳（メタデータ） (2024-12-28T16:28:13Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  非コンケーブゲームにおいて、抽出可能な$Phi$-equilibriaについて検討する。 Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2024-03-13T01:51:30Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality [21.94743452608215]
  本研究では,ゲーム報酬と探索費用のバランスを捉えたプロトタイプ学習モデルであるスムーズQ-ラーニングについて検討する。 Q-ラーニングは常に、有界な有理性の下でのゲームに対する標準的な解概念である一意の量子-応答平衡(QRE)に収束することを示す。
  論文  参考訳（メタデータ） (2021-06-24T11:43:38Z)
• Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium [33.9962699667578]
  No-regretアルゴリズムはゲーム理論の保証の点で等しく作成されません。 楽観的なミラー降下に基づく非相対的ポリシーを提案する。
  論文  参考訳（メタデータ） (2021-04-26T17:52:29Z)

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

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