論文の概要: Autobidders with Budget and ROI Constraints: Efficiency, Regret, and
Pacing Dynamics
- arxiv url: http://arxiv.org/abs/2301.13306v1
- Date: Mon, 30 Jan 2023 21:59:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-01 18:29:52.069636
- Title: Autobidders with Budget and ROI Constraints: Efficiency, Regret, and
Pacing Dynamics
- Title(参考訳): 予算とROI制約を伴う自動車:効率性、レグレト、そしてパッシングダイナミクス
- Authors: Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, Mengxiao Zhang
- Abstract要約: オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 77.67037372500495
- 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/or 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 and regardless of the correlation structure between advertiser
valuations.
- Abstract(参考訳): オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
各オートバイダは、予算および/または投資のリターンの制約の下で、繰り返しオークションの複数のラウンドで広告主の総価値を最大化する。
本稿では,全ての制約を満たすことを保証する勾配に基づく学習アルゴリズムを提案する。
本アルゴリズムはバンディットフィードバックのみを使用し,第1または第2価格オークション,および任意の「中間」オークション方式で使用できる。
我々の主な成果は、これらの自走車同士が互いに対戦するとき、全てのラウンドで得られる液体の福祉は、任意のアロケーションによって達成される最適液体の福祉の少なくとも半分であるということである。
これは、入札ダイナミクスが、広告主のバリュエーション間の相関構造によらず、均衡に収束するかどうかを議論する。
関連論文リスト
- Strategically-Robust Learning Algorithms for Bidding in First-Price
Auctions [13.474384048001259]
ゲーム理論と機械学習のインターフェースにおいて,プライスオークションを繰り返し競うことの学習は基本的な問題である。
本稿では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセント・アルゴリズムの解析に利用した。
論文 参考訳(メタデータ) (2024-02-12T01:33:33Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and
Exp-Concave Games with Gradient Feedback [84.61895643083226]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳(メタデータ) (2023-10-21T18:38:13Z) - 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 [6.370905925442655]
複数単位のペイ・アズ・バイドオークションの入札方法を学ぶことの問題点を考察する。
バイド・バイド・オークションの入札方法を学ぶという問題は、アクション・スペースの性質によって困難である。
時間動的計画法を用いて,オフライン問題に対する最適解が得られることを示す。
論文 参考訳(メタデータ) (2023-07-27T20:49:28Z) - Learning and Collusion in Multi-unit Auctions [17.727436775513368]
均一な価格で複数ユニットのオークションを繰り返し検討する。
このオークションの特性をオフラインとオンラインの両方で分析する。
ここでは、$(K+1)$-stの価格形式が入札者間の共謀の影響を受けやすいことを示す。
論文 参考訳(メタデータ) (2023-05-27T08:00:49Z) - Regret Minimization and Convergence to Equilibria in General-sum Markov
Games [57.568118148036376]
汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。
我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
論文 参考訳(メタデータ) (2022-07-28T16:27:59Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳(メタデータ) (2022-07-25T18:29:16Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。