論文の概要: Nash Convergence of Mean-Based Learning Algorithms in First Price Auctions

• arxiv url: http://arxiv.org/abs/2110.03906v1
• Date: Fri, 8 Oct 2021 06:01:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-11 14:35:11.151611
• Title: Nash Convergence of Mean-Based Learning Algorithms in First Price Auctions
• Title（参考訳）: 初値オークションにおける平均学習アルゴリズムのnash収束
• Authors: Xiaotie Deng, Xinyan Hu, Tao Lin, Weiqiang Zheng
• Abstract要約: 我々は,決定論的型を持つ入札者が平均的学習アルゴリズムを用いて入札を学習する,価格オークションを繰り返し検討する。 2つの意味での入札力学のナッシュ収束特性を完全に特徴づける。
• 参考スコア（独自算出の注目度）: 13.340033859941094
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider repeated first price auctions where each bidder, having a deterministic type, learns to bid using a mean-based learning algorithm. We completely characterize the Nash convergence property of the bidding dynamics in two senses: (1) time-average: the fraction of rounds where bidders play a Nash equilibrium approaches to 1 in the limit; (2) last-iterate: the mixed strategy profile of bidders approaches to a Nash equilibrium in the limit. Specifically, the results depend on the number of bidders with the highest value: - If the number is at least three, the bidding dynamics almost surely converges to a Nash equilibrium of the auction, both in time-average and in last-iterate. - If the number is two, the bidding dynamics almost surely converges to a Nash equilibrium in time-average but not necessarily in last-iterate. - If the number is one, the bidding dynamics may not converge to a Nash equilibrium in time-average nor in last-iterate. Our discovery opens up new possibilities in the study of convergence dynamics of learning algorithms.
• Abstract（参考訳）: 我々は,決定論的型を持つ入札者が平均学習アルゴリズムを用いて入札を学習する,価格オークションを繰り返し検討する。 1) 入札ダイナミクスのnash収束特性を,(1) 時間平均: 入札者が限界で1に近づくラウンドの分数,(2) 最終文: 入札者の混合戦略プロファイルが限界におけるnash平衡に近づく,という2つの感覚で完全に特徴づける。 具体的には、最も高い値の入札者数に依存する: - 数値が少なくとも3である場合、入札ダイナミクスは、時間平均とラストイテレートの両方において、オークションのnash平衡にほぼ確実に収束する。 - 数値が 2 であれば、入札力学はほぼ確実に時間平均のナッシュ平衡に収束するが、必ずしも最終点に収束しない。 -数を1とした場合、入札ダイナミクスは時間平均でもラスト・イテレートでもナッシュ平衡に収束しない。 我々の発見は、学習アルゴリズムの収束力学の研究における新たな可能性を開く。

関連論文リスト

• Games played by Exponential Weights Algorithms [0.0]
  各プレイヤーは、初期混合動作と固定学習率を特徴とする指数重み付けアルゴリズムを使用する。 厳密なナッシュ均衡が存在するときは常に、次の段階で厳密なナッシュ均衡を行う確率は、ほぼ確実に0または1に収束することを示す。
  論文  参考訳（メタデータ） (2024-07-09T08:49:51Z)
• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。 競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
  論文  参考訳（メタデータ） (2024-05-31T19:26:05Z)
• Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability [11.793922711718645]
  我々は,ゼロサムゲームにおいて,プレイヤーが情報のみを閲覧し,相手の行動や支払いを行うような分散学習を検討する。 従来の研究は、強い到達可能性仮定の下で二重時間スケールのアルゴリズムを用いて、この設定でナッシュ均衡に収束することを示した。 我々の貢献は合理的で収束したアルゴリズムであり、Tsallis-Entropy regularization を値イテレーションに基づくアルゴリズムで利用している。
  論文  参考訳（メタデータ） (2023-12-13T09:31:30Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [62.51015395213579]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 提案アルゴリズムは粒子の動きを利用して$ilon$-mixed Nash平衡のランダム戦略の更新を表現する。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。 本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T21:59:30Z)
• Game-Theoretical Perspectives on Active Equilibria: A Preferred Solution Concept over Nash Equilibria [61.093297204685264]
  マルチエージェント強化学習における効果的なアプローチは,エージェントの学習プロセスを検討し,今後の政策に影響を与えることである。 この新たな解の概念は、ナッシュ均衡のような標準解の概念が活性平衡の特別な場合である、という一般的なものである。 我々は,ゲーム理論の観点から,ナッシュ平衡が知られている実例を綿密に研究することにより,アクティブ平衡を解析する。
  論文  参考訳（メタデータ） (2022-10-28T14:45:39Z)
• Approximate Nash Equilibrium Learning for n-Player Markov Games in Dynamic Pricing [0.0]
  競技マルコフゲーム(MG)環境におけるナッシュ均衡学習について検討する。 我々は、近似的なナッシュ平衡を求めるための新しいモデルフリー手法を開発した。 我々は、特に動的価格領域において、近似的なナッシュ均衡を学習できることを実証する。
  論文  参考訳（メタデータ） (2022-07-13T19:27:07Z)
• Fast Rate Learning in Stochastic First Price Bidding [0.0]
  ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。 対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。 我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
  論文  参考訳（メタデータ） (2021-07-05T07:48:52Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
  論文  参考訳（メタデータ） (2021-02-23T05:11:07Z)
• Learning Nash Equilibria in Zero-Sum Stochastic Games via Entropy-Regularized Policy Approximation [18.35524179586723]
  ゼロサムゲームにおけるナッシュ均衡学習の計算コストを削減するためのポリシー近似の利用について検討する。 我々は,Nashポリシーを近似するために,エントロピー規則化されたソフトポリシーのシーケンスを利用する新しいQ-ラーニング型アルゴリズムを提案する。 一定の条件下では、正規化されたQ-関数を更新することにより、アルゴリズムはナッシュ平衡に収束する。
  論文  参考訳（メタデータ） (2020-09-01T01:03:44Z)
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
  我々は,$lambda$-cocoerciveゲーム上での連立OGD学習における有限時間最終点収束率を特徴付ける。 新たなダブルストッピング時間法により, この適応アルゴリズムは, 非適応的手法と同じ有限時間終点収束率が得られることを示す。
  論文  参考訳（メタデータ） (2020-02-23T01:46:34Z)

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

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