論文の概要: Dynamic Budget Throttling in Repeated Second-Price Auctions
- arxiv url: http://arxiv.org/abs/2207.04690v2
- Date: Tue, 12 Jul 2022 08:46:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-13 11:03:53.306732
- Title: Dynamic Budget Throttling in Repeated Second-Price Auctions
- Title（参考訳）: 繰り返し2次オークションにおける動的予算変動
- Authors: Zhaohua Chen, Chang Wang, Qian Wang, Yuqi Pan, Zhuming Shi, Chuyue
Tang, Zheng Cai, Yukun Ren, Zhihua Zhu, Xiaotie Deng
- Abstract要約: Throttlingは、今日のオンライン広告市場で最も人気のある予算管理手法の1つである。
本稿では,第2価格の繰り返しオークションにおける動的予算縮小過程を理論的観点から考察する。
- 参考スコア（独自算出の注目度）: 10.906824638992154
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Throttling is one of the most popular budget control methods in today's
online advertising markets. When a budget-constrained advertiser employs
throttling, she can choose whether or not to participate in an auction after
the advertising platform recommends a bid. This paper focuses on the dynamic
budget throttling process in repeated second-price auctions from a theoretical
view. An essential feature of the underlying problem is that the advertiser
does not know the distribution of the highest competing bid upon entering the
market. To model the difficulty of eliminating such uncertainty, we consider
two different information structures. The advertiser could obtain the highest
competing bid in each round with full-information feedback. Meanwhile, with
partial information feedback, the advertiser could only have access to the
highest competing bid in the auctions she participates in. We propose the
OGD-CB algorithm, which involves simultaneous distribution learning and revenue
optimization. In both settings, we demonstrate that this algorithm guarantees
an $O(\sqrt{T\log T})$ regret with probability $1 - O(1/T)$ relative to the
fluid adaptive throttling benchmark. By proving a lower bound of
$\Omega(\sqrt{T})$ on the minimal regret for even the hindsight optimum, we
establish the near optimality of our algorithm. Finally, we compare the fluid
optimum of throttling to that of pacing, another widely adopted budget control
method. The numerical relationship of these benchmarks sheds new light on the
understanding of different online algorithms for revenue maximization under
budget constraints.
- Abstract（参考訳）: Throttlingは、今日のオンライン広告市場で最も人気のある予算管理手法の1つである。
予算制約のある広告主がスロットリングを採用すると、広告プラットフォームが入札を推奨した後、オークションに参加するかどうかを選択できる。
本稿では,2次オークションを繰り返す場合の動的予算削減過程を理論的に考察する。
根本的な問題の本質的な特徴は、広告主が市場参入時に最も高い入札者の分布を知らないことである。
このような不確実性を取り除くことの難しさをモデル化するため、2つの異なる情報構造を考える。
広告主は、全情報フィードバックで各ラウンドで最高の競争入札を得ることができた。
一方、部分的な情報フィードバックによって、広告主は、彼女が参加するオークションで最も高い競争入札にしかアクセスできない。
分配学習と収益最適化を同時に行うOGD-CBアルゴリズムを提案する。
どちらの設定でも、このアルゴリズムは流体適応スロットリングベンチマークと比較して1-O(1/T)$の確率で$O(\sqrt{T\log T})$後悔を保証する。
隠れた最適化でさえも最小限の後悔に対して$\Omega(\sqrt{T})$の低い境界を証明することにより、アルゴリズムのほぼ最適性を確立する。
最後に, スロットリングの最適流体と, 予算管理法として広く採用されているペーシングの流体を比較した。
これらのベンチマークの数値関係は、予算制約下での収益最大化のための異なるオンラインアルゴリズムの理解に新たな光を当てている。
関連論文リスト
- Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。
競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
論文 参考訳（メタデータ） (2024-05-31T19:26:05Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - 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) - Multi-Platform Budget Management in Ad Markets with Non-IC Auctions [6.037383467521294]
オンライン広告市場では、予算に制約のある広告主は、様々なプラットフォームでのオークションで繰り返し入札することで、広告の配置を取得する。
予算制約がある場合、インセンティブに適合するかもしれない、あるいはそうでないかもしれない一連のオークションにおいて、入札を最適に行う戦略を提案する。
当社の戦略は、広告主が期待する予算制約を満たしつつ、オークション全体で期待される全ユーティリティを最大化する。
論文 参考訳（メタデータ） (2023-06-12T18:21:10Z) - Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T21:59:30Z) - Fast Rate Learning in Stochastic First Price Bidding [0.0]
ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。
対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。
我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
論文 参考訳（メタデータ） (2021-07-05T07:48:52Z) - Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。
この問題に対する最初のパラメトリック下界を提供する。
本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
論文 参考訳（メタデータ） (2020-11-10T12:45:02Z) - VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit
Feedback [104.06766271716774]
本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。
まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。
当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
論文 参考訳（メタデータ） (2020-04-19T18:00:58Z) - Optimal Bidding Strategy without Exploration in Real-time Bidding [14.035270361462576]
予算制約によるユーティリティの最大化は、リアルタイム入札(RTB)システムにおける広告主の主要な目標である。
それまでの作品は、検閲された国家の困難を和らげるために競売に敗れたことを無視していた。
本稿では,リアルタイムトラフィックで観測される真の分布の挙動を模倣するために,最大エントロピー原理を用いた新しい実用的枠組みを提案する。
論文 参考訳（メタデータ） (2020-03-31T20:43:28Z) - Adversarial Attacks on Linear Contextual Bandits [87.08004581867537]
悪意のあるエージェントは、望ましい行動を実行するためにバンディットアルゴリズムを攻撃するインセンティブを持つ可能性がある。
悪意のあるエージェントは、線形コンテキストのバンドイットアルゴリズムに任意のアーム$T - o(T)$倍を$T$ステップで引き出すように強制することができる。
また,悪意のあるエージェントが単一コンテキストにおける帯域幅アルゴリズムの動作に影響を与えることに関心がある場合についても検討する。
論文 参考訳（メタデータ） (2020-02-10T15:04:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。