論文の概要: Impossibility of No-Regret in Multi-Agent Bidding
- arxiv url: http://arxiv.org/abs/2610.36666v1
- Date: Tue, 27 Oct 2026 05:37:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-28 21:04:31.489005
- Title: Impossibility of No-Regret in Multi-Agent Bidding
- Title（参考訳）: マルチエージェントバイディングにおけるno-regretの不可能性
- Abstract要約: 我々は,全ての入札者が同時にノンレグレットを達成することは,計算的に不可能であることを示した。
オンライン入札システムにおける高いばらつきが後悔を招く決定論的関係を確立する。
- 参考スコア（独自算出の注目度）: 29.8171362564092
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider $T$ repeated second-price auctions across $n$ pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve no-regret simultaneously while satisfying their respective budget or return-on-investment constraints. Therefore, in the prominent internet auction systems where buyers simultaneously deploy pacing algorithms or automated bidding agents, we cannot hope to achieve joint no-regret guarantees in general. We establish a deterministic relationship that high variance in online bidding systems implies high regret. By showing that one can extract a pacing equilibrium from a low-variance system, we prove PPAD-hardness of attaining joint no-regret. For several widely used bidding algorithms, we also show evidence from dynamical systems and numerical simulations that they can indeed display high-variance behavior through cycling, even on simple market instances.
- Abstract（参考訳）: 我々は、$T$の繰り返し第2価格オークションを$n$のペイシング入札者に対して、すなわちアイテムの到着とともに検討し、各入札者がそれぞれの予算や投資の帰結の制約を満たしつつ、同時にノンレグレットを達成することは、計算的に不可能であることを示す。
したがって、自動入札エージェントや自動入札エージェントを同時に導入する著名なインターネットオークションシステムでは、一般に共同保証が達成されることは期待できない。
オンライン入札システムにおける高いばらつきが後悔を招く決定論的関係を確立する。
低分散系からペーシング平衡を抽出できることを示せば, PPAD硬さを証明できる。
いくつかの広く使われている入札アルゴリズムでは、単純なマーケットインスタンスでもサイクリングによる高分散挙動を実際に表示できるという、力学系や数値シミュレーションの証拠も示している。
関連論文リスト
- Learning to Coordinate Bidders in Non-Truthful Auctions [9.642382646285805]
非実効オークションにおけるベイズ相関均衡の複雑さについて検討する。
我々は、戦略形式のBCEの集合が、入札者の値のサンプルの$$$$ $tilde O(fracnvarepsilon2)で学習できることを証明した。
提案手法は,全ての単調入札戦略のクラスにおける擬似次元の分析と合わせて,入札者の期待する効用をサンプルから推定する問題への還元である。
論文 参考訳（メタデータ） (2025-07-03T17:03:14Z) - Selling Joint Ads: A Regret Minimization Perspective [7.288063443108292]
オンライン小売によるモチベーションにより、一品(広告スロットなど)を2つの非排除購入者(商店、ブランド等)に販売する問題を考える。
この問題は、例えば、マーチャントとブランドが商品を宣伝するために競売に協力して入札する状況と、表示されている広告の恩恵を捉えている。
メカニズムは2つの入札を収集し、どちらを割り当てるか、どの支払いを行うかを決定する。
論文 参考訳（メタデータ） (2024-09-12T07:59:10Z) - Learning in Repeated Multi-Unit Pay-As-Bid Auctions [3.6294895527930504]
本研究では,単一入札者の視点から,ペイ・アズ・バイド(PAB)オークションにおける入札戦略の問題点を考察する。
提案手法は,競合する入札が事前に知られている場合のオフライン問題を,時間アルゴリズムで解くことができることを示す。
また,PAB平衡のキャラクタリゼーションについても検討した。
論文 参考訳（メタデータ） (2023-07-27T20:49:28Z) - Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。
このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。
上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
論文 参考訳（メタデータ） (2023-02-02T16:30:33Z) - Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T21:59:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。