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

• arxiv url: http://arxiv.org/abs/2110.03906v5
• Date: Tue, 19 Aug 2025 19:30:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-21 16:52:41.015839
• Title: Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions
• Title（参考訳）: 第一価格オークションにおける平均学習アルゴリズムのナッシュ収束
• Authors: Xiaotie Deng, Xinyan Hu, Tao Lin, Weiqiang Zheng,
• Abstract要約: この研究は、固定値の入札者が平均ベースのアルゴリズムを用いて入札を学習する、繰り返し最初の価格オークションに焦点を当てる。 我々は平均的アルゴリズムの学習力学を完全に特徴付けている。
• 参考スコア（独自算出の注目度）: 13.524376512653658
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The convergence properties of learning dynamics in repeated auctions is a timely and important question, with numerous applications in, e.g., online advertising markets. This work focuses on repeated first-price auctions where bidders with fixed values learn to bid using mean-based algorithms -- a large class of online learning algorithms that include popular no-regret algorithms such as Multiplicative Weights Update and Follow the Perturbed Leader. We completely characterize the learning dynamics of mean-based algorithms, under two notions of convergence: (1) time-average: the fraction of rounds where bidders play a Nash equilibrium converges to 1; (2) last-iterate: the mixed strategy profile of bidders converges to a Nash equilibrium. Specifically, the results depend on the number of bidders with the highest value: - If the number is at least three, the dynamics almost surely converges to a Nash equilibrium of the auction, in both time-average and last-iterate. - If the number is two, the dynamics almost surely converges to a Nash equilibrium in time-average but not necessarily last-iterate. - If the number is one, the dynamics may not converge to a Nash equilibrium in time-average or last-iterate. Our discovery opens up new possibilities in the study of the convergence of learning dynamics.
• Abstract（参考訳）: 繰り返しオークションにおける学習力学の収束性は、タイムリーで重要な問題であり、オンライン広告市場など多くの応用がある。 この研究は、固定価値の入札者が平均ベースのアルゴリズムを使って入札を学習する、繰り返し最初の価格オークションに焦点を当てている。 平均的アルゴリズムの学習力学は, 平均値: 平均値: 入札者がナッシュ均衡を演じるラウンドの分数: 1 に収束する; 2) 最終項目: 入札者の混合戦略プロファイルはナッシュ均衡に収束する。 具体的には、最高値の入札者数に依存する: - 数値が少なくとも3である場合、ダイナミクスはほぼ確実に、平均値と最終値の両方でオークションのナッシュ均衡に収束する。 - 数値が 2 であれば、ダイナミクスはほぼ確実に時間平均のナッシュ平衡に収束するが、必ずしも最終点ではない。 - 数値が 1 であれば、力学は時間平均や最終定位においてナッシュ平衡に収束しない。 我々の発見は、学習力学の収束の研究における新たな可能性を開く。

関連論文リスト

• Accelerating Nash Learning from Human Feedback via Mirror Prox [36.04055906691423]
  オンラインNLHFアルゴリズムであるNash Mirror Prox(mathtNash-MP$)を導入する。 我々の理論的解析により、ナッシュ-MPは、$beta$-regularized Nash平衡に対して、最終点の線形収束を示すことが証明された。 また,Nash-MPは,利用可能性ギャップと対数確率の半ノルムの均一性に対して,最終等級の線形収束を示すことを示した。
  論文  参考訳（メタデータ） (2025-05-26T09:17:32Z)
• On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games [71.73971094342349]
  ゲームにおける学習力学の非エルゴード収束は、理論と実践の両方において重要であるため、広く研究されている。 近年の研究では、最適乗算重み更新を含む学習力学の幅広いクラスが、任意に遅い最終項目収束を示すことが示されている。 OMWUは、同じクラスのゲームにおいて、その遅い最終点収束とは対照的に、$O(T-1/6)$est-iterate convergence rateを達成することを示す。
  論文  参考訳（メタデータ） (2025-03-04T17:49:24Z)
• 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 [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (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)
• Forward Looking Best-Response Multiplicative Weights Update Methods [14.519198115835966]
  エンフェルティプリケートウェイト更新法の新しい変種は、独自のエンフェルティプリケート平衡を持つエンフェルティプリケートサムゲームに対する最終点収束を保証する 以上の結果から,本アルゴリズムは従来手法と比較して,収束率と収縮領域の両方において有意な利得が得られることが明らかとなった。
  論文  参考訳（メタデータ） (2021-06-07T13:03:33Z)
• 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)

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

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