論文の概要: Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
- arxiv url: http://arxiv.org/abs/2301.13306v3
- Date: Wed, 12 Jun 2024 02:18:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-14 01:52:33.877183
- Title: Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
- Title(参考訳): 予算とROI制約を伴う自動車:効率性、レグレト、そしてパッシングダイナミクス
- Authors: Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, Mengxiao Zhang,
- Abstract要約: オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 53.62091043347035
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a game between autobidding algorithms that compete in an online advertising platform. Each autobidder is tasked with maximizing its advertiser's total value over multiple rounds of a repeated auction, subject to budget and return-on-investment constraints. We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret. Our algorithm uses only bandit feedback and can be used with the first- or second-price auction, as well as with any "intermediate" auction format. Our main result is that when these autobidders play against each other, the resulting expected liquid welfare over all rounds is at least half of the expected optimal liquid welfare achieved by any allocation. This holds whether or not the bidding dynamics converges to an equilibrium.
- Abstract(参考訳): オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
各オートバイダは、予算と投資の帰結の制約の下で、繰り返しのオークションの複数のラウンドで広告主の総価値を最大化する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
提案アルゴリズムは,帯域幅フィードバックのみを使用し,第1または第2価格のオークションや,任意の"中間"オークションフォーマットで使用することができる。
我々の主な成果は、これらの自走車同士が互いに対戦するとき、全てのラウンドで得られる液体の福祉は、任意のアロケーションによって達成される最適液体の福祉の少なくとも半分であるということである。
これは、入札力学が平衡に収束するか否かを保っている。
関連論文リスト
- Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
競売業者が各ラウンドで2つのグループに分けない商品を、合計で$T$のラウンドで販売する問題を考える。
競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
論文 参考訳(メタデータ) (2024-05-31T19:26:05Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳(メタデータ) (2024-04-16T17:59:55Z) - No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints [0.9694940903078658]
本稿では、ROIと予算制約の対象となる価値を最適化するために、オンラインオートバイディングアルゴリズムを設計する問題について検討する。
我々の主な結果は、最高のリプシッツ関数に関して、ほぼ最適の$tilde O(sqrt T)$の後悔を保証する完全な情報フィードバックを持つアルゴリズムである。
論文 参考訳(メタデータ) (2024-04-15T14:31:53Z) - Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions [11.988955088595858]
ゲーム理論と機械学習のインターフェースにおいて,プライスオークションを繰り返し競うことの学習は基本的な問題である。
本稿では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセント・アルゴリズムの解析に利用した。
論文 参考訳(メタデータ) (2024-02-12T01:33:33Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。
学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
論文 参考訳(メタデータ) (2023-10-08T07:04:22Z) - Learning in Repeated Multi-Unit Pay-As-Bid Auctions [3.6294895527930504]
複数単位のペイ・アズ・バイドオークションの入札方法を学ぶことの問題点を考察する。
バイド・バイド・オークションの入札方法を学ぶという問題は、アクション・スペースの性質によって困難である。
時間動的計画法を用いて,オフライン問題に対する最適解が得られることを示す。
論文 参考訳(メタデータ) (2023-07-27T20:49:28Z) - Learning and Collusion in Multi-unit Auctions [17.727436775513368]
均一な価格で複数ユニットのオークションを繰り返し検討する。
このオークションの特性をオフラインとオンラインの両方で分析する。
ここでは、$(K+1)$-stの価格形式が入札者間の共謀の影響を受けやすいことを示す。
論文 参考訳(メタデータ) (2023-05-27T08:00:49Z) - No-regret Learning in Repeated First-Price Auctions with Budget
Constraints [5.834615090865286]
定常競争下での最適非予測戦略に対して,RLに基づく入札アルゴリズムを提案する。
提案アルゴリズムは,各ラウンドの最後にすべての入札が明らかになった場合,$widetilde O(sqrt T)$-regretを求める。
論文 参考訳(メタデータ) (2022-05-29T04:32:05Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳(メタデータ) (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。