論文の概要: Online Budgeted Matching with General Bids

• arxiv url: http://arxiv.org/abs/2411.04204v2
• Date: Thu, 14 Nov 2024 04:14:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-15 15:21:25.789078
• Title: Online Budgeted Matching with General Bids
• Title（参考訳）: オンライン予算マッチングとジェネラルバイド
• Authors: Jianyi Yang, Pengfei Li, Adam Wierman, Shaolei Ren,
• Abstract要約: 我々は,オンライン予算マッチング(OBM)の問題に一般入札で対処する。 まず、決定論的オンラインアルゴリズムの競合比を1-kappaの上限とする。 そこで我々はMetaAdと呼ばれる新しいメタアルゴリズムを提案し、最初に証明可能な競合比で異なるアルゴリズムに還元する。
• 参考スコア（独自算出の注目度）: 40.142341503145275
• License:
• Abstract: Online Budgeted Matching (OBM) is a classic problem with important applications in online advertising, online service matching, revenue management, and beyond. Traditional online algorithms typically assume a small bid setting, where the maximum bid-to-budget ratio (\kappa) is infinitesimally small. While recent algorithms have tried to address scenarios with non-small or general bids, they often rely on the Fractional Last Matching (FLM) assumption, which allows for accepting partial bids when the remaining budget is insufficient. This assumption, however, does not hold for many applications with indivisible bids. In this paper, we remove the FLM assumption and tackle the open problem of OBM with general bids. We first establish an upper bound of 1-\kappa on the competitive ratio for any deterministic online algorithm. We then propose a novel meta algorithm, called MetaAd, which reduces to different algorithms with first known provable competitive ratios parameterized by the maximum bid-to-budget ratio \kappa \in [0, 1]. As a by-product, we extend MetaAd to the FLM setting and get provable competitive algorithms. Finally, we apply our competitive analysis to the design learning-augmented algorithms.
• Abstract（参考訳）: Online Budgeted Matching (OBM) は、オンライン広告、オンラインサービスマッチング、収益管理などの重要なアプリケーションにおいて、古典的な問題である。 伝統的なオンラインアルゴリズムは、通常、最小入札率(\kappa)が無限小である小さな入札設定を仮定する。 近年のアルゴリズムは、非小規模または一般入札のシナリオに対処しようとするが、しばしばフラクショナルラストマッチング(FLM)の仮定に頼り、残りの予算が不十分な場合に部分入札を受け入れることができる。 しかし、この仮定は、不可分な入札を持つ多くのアプリケーションには当てはまらない。 本稿では、FLM仮定を除去し、一般入札によるOBMのオープン問題に取り組む。 まず、決定論的オンラインアルゴリズムの競合比を1-\kappaの上限とする。 そこで我々はMetaAdと呼ばれる新しいメタアルゴリズムを提案し,最大入札率 \kappa \in [0, 1] でパラメータ化された最初の証明可能な競合比を持つアルゴリズムに還元する。 副産物として、私たちはMetaAdをFLM設定に拡張し、証明可能な競合アルゴリズムを得る。 最後に、設計学習強化アルゴリズムに競合分析を適用した。

関連論文リスト

• 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)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。 本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T21:59:30Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Online Bidding Algorithms for Return-on-Spend Constrained Advertisers [10.500109788348732]
  この研究は、人気が高まっている制約の下で、単一の価値を最大化する広告主のための効率的なオンラインアルゴリズムを探索する。 我々は,指定したRoS制約を常に尊重しながら,期待のほぼ最適に後悔する簡単なオンラインアルゴリズムに貢献する。
  論文  参考訳（メタデータ） (2022-08-29T16:49:24Z)
• Improved Bounds for Online Facility Location with Predictions [14.973636284231047]
  学習強化オンラインアルゴリズムの枠組みとして,オンライン施設配置を考える。 OFLでは、要求はメートル法空間で1つずつ到着し、到着時にオープンな施設に割り当てられなければならない。 最適施設の位置の予測に不完全な可能性を生かしたOFLのオンラインアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-17T16:44:27Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。 性能は不特定な事前条件で優雅に低下することを示す。
  論文  参考訳（メタデータ） (2021-07-03T23:17:26Z)
• Online Adversarial Attacks [57.448101834579624]
  我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。 まず、オンライン脅威モデルの決定論的変種を厳格に分析する。 このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
  論文  参考訳（メタデータ） (2021-03-02T20:36:04Z)
• Necessarily Optimal One-Sided Matchings [49.0517583218216]
  我々は、$n$エージェントと$n$オブジェクトとをマッチングする古典的な問題について研究する。 エージェントに完全な選好を報告させる代わりに、私たちのゴールは部分的な選好から望ましいマッチングを学ぶことです。 我々は,与えられたマッチングが NPO か NRM かを確認し,そのようなマッチングが与えられたトップ$k$ の部分的選好が存在するかどうかを確認するために,効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-07-17T16:01:34Z)
• 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)

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

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