論文の概要: No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints

• arxiv url: http://arxiv.org/abs/2404.09832v1
• Date: Mon, 15 Apr 2024 14:31:53 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-17 21:57:24.060441
• Title: No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints
• Title（参考訳）: 予算・ROI制約をもつ非実効オークションにおける非実効アルゴリズム
• Authors: Gagan Aggarwal, Giannis Fikioris, Mingfei Zhao,
• Abstract要約: 本稿では、ROIと予算制約の対象となる価値を最適化するために、オンラインオートバイディングアルゴリズムを設計する問題について検討する。 我々の主な結果は、最高のリプシッツ関数に関して、ほぼ最適の$tilde O(sqrt T)$の後悔を保証する完全な情報フィードバックを持つアルゴリズムである。
• 参考スコア（独自算出の注目度）: 0.9694940903078658
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Advertisers increasingly use automated bidding to optimize their ad campaigns on online advertising platforms. Autobidding optimizes an advertiser's objective subject to various constraints, e.g. average ROI and budget constraints. In this paper, we study the problem of designing online autobidding algorithms to optimize value subject to ROI and budget constraints when the platform is running any mixture of first and second price auction. We consider the following stochastic setting: There is an item for sale in each of $T$ rounds. In each round, buyers submit bids and an auction is run to sell the item. We focus on one buyer, possibly with budget and ROI constraints. We assume that the buyer's value and the highest competing bid are drawn i.i.d. from some unknown (joint) distribution in each round. We design a low-regret bidding algorithm that satisfies the buyer's constraints. Our benchmark is the objective value achievable by the best possible Lipschitz function that maps values to bids, which is rich enough to best respond to many different correlation structures between value and highest competing bid. Our main result is an algorithm with full information feedback that guarantees a near-optimal $\tilde O(\sqrt T)$ regret with respect to the best Lipschitz function. Our result applies to a wide range of auctions, most notably any mixture of first and second price auctions (price is a convex combination of the first and second price). In addition, our result holds for both value-maximizing buyers and quasi-linear utility-maximizing buyers. We also study the bandit setting, where we show an $\Omega(T^{2/3})$ lower bound on the regret for first-price auctions, showing a large disparity between the full information and bandit settings. We also design an algorithm with $\tilde O(T^{3/4})$ regret, when the value distribution is known and is independent of the highest competing bid.
• Abstract（参考訳）: 広告主はオンライン広告プラットフォーム上での広告キャンペーンを最適化するために自動入札を利用することが増えている。 自動化は広告主の目的を様々な制約、例えば平均ROIと予算制約に最適化する。 本稿では,プラットフォームが第1価格と第2価格のオークションを混在している場合に,ROIと予算制約に課される価値を最適化するオンライン自動入札アルゴリズムを設計する際の課題について検討する。 以下の確率的設定について考察する: それぞれのラウンドで販売されるアイテムがあります。 各ラウンドでは、購入者が入札を提出し、その商品を売るためにオークションが実施される。 おそらく予算とROIの制約によって、私たちは1人の買い手に焦点を当てています。 各ラウンドにおける未知の(結合した)分布から、買い手の価値と最も高い競争入札が引き出されると仮定する。 我々は,買い手の制約を満たす低信頼入札アルゴリズムを設計する。 我々のベンチマークは、値を入札にマップする最も可能なリプシッツ関数によって達成可能な客観的値である。 我々の主な結果は、最適なリプシッツ関数に関して、ほぼ最適の$\tilde O(\sqrt T)$後悔を保証する完全な情報フィードバックを持つアルゴリズムである。 我々の結果は幅広いオークションに当てはまり、特に第1と第2の価格のオークション(価格が第1と第2の価格の凸組合せである)の混合が顕著である。 さらに、当社の結果は、価値最大化バイヤーと準線形ユーティリティ最大化バイヤーの両方に当てはまる。 また,Bandit設定についても検討し,第1価格オークションの後悔点を$\Omega(T^{2/3})$以下で示し,全情報とBandit設定との間に大きな相違点を示す。 我々はまた、値分布が知られ、最も競争の激しい入札とは無関係であるときに、$\tilde O(T^{3/4})$ regret のアルゴリズムを設計する。

関連論文リスト

• Procurement Auctions via Approximately Optimal Submodular Optimization [53.93943270902349]
  競売業者がプライベートコストで戦略的売り手からサービスを取得しようとする競売について検討する。 我々の目標は、取得したサービスの品質と販売者の総コストとの差を最大化する計算効率の良いオークションを設計することである。
  論文  参考訳（メタデータ） (2024-11-20T18:06:55Z)
• 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 and Collusion in Multi-unit Auctions [17.727436775513368]
  均一な価格で複数ユニットのオークションを繰り返し検討する。 このオークションの特性をオフラインとオンラインの両方で分析する。 ここでは、$(K+1)$-stの価格形式が入札者間の共謀の影響を受けやすいことを示す。
  論文  参考訳（メタデータ） (2023-05-27T08:00:49Z)
• Dynamic Pricing and Learning with Bayesian Persuasion [18.59029578133633]
  我々は,商品の価格設定に加えて,販売者が「広告計画」にコミットする,新たな動的価格設定と学習環境を考える。 我々は、バイエルンの一般的な説得フレームワークを使用して、これらのシグナルが購入者の評価と購入反応に与える影響をモデル化する。 我々は、過去の購入応答を利用して最適な価格と広告戦略を適応的に学習できるオンラインアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-04-27T17:52:06Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。 本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T21:59:30Z)
• A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design [158.0041488194202]
  多相第2価格オークションにおけるリザーブ価格の最適化について検討する。 売り手の視点からは、潜在的に非現実的な入札者の存在下で、環境を効率的に探索する必要がある。 第三に、売り手のステップごとの収益は未知であり、非線形であり、環境から直接観察することさえできない。
  論文  参考訳（メタデータ） (2022-10-19T03:49:05Z)
• Fast Rate Learning in Stochastic First Price Bidding [0.0]
  ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。 対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。 我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
  論文  参考訳（メタデータ） (2021-07-05T07:48:52Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions [40.30925727499806]
  我々は,$widetildeO(sqrtT)$ regretを達成する,最初のミニマックス最適オンライン入札アルゴリズムを開発した。 Verizon Mediaから得られた3つの実世界の1価オークションデータセットを用いて,本アルゴリズムを検証した。
  論文  参考訳（メタデータ） (2020-07-09T05:40:39Z)
• Optimal No-regret Learning in Repeated First-price Auctions [38.908235632001116]
  オンライン学習を反復した初価オークションで研究する。 我々は,ほぼ最適の$widetildeO(sqrtT)$ regret boundを達成するための最初の学習アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-03-22T03:32:09Z)

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

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