論文の概要: Selling Joint Ads: A Regret Minimization Perspective

• arxiv url: http://arxiv.org/abs/2409.07819v1
• Date: Thu, 12 Sep 2024 07:59:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-13 17:27:45.985366
• Title: Selling Joint Ads: A Regret Minimization Perspective
• Title（参考訳）: ジョイント広告の販売:レグレットの最小化の視点
• Authors: Gagan Aggarwal, Ashwinkumar Badanidiyuru, Paul Dütting, Federico Fusco,
• Abstract要約: オンライン小売によるモチベーションにより、一品(広告スロットなど)を2つの非排除購入者(商店、ブランド等)に販売する問題を考える。 この問題は、例えば、マーチャントとブランドが商品を宣伝するために競売に協力して入札する状況と、表示されている広告の恩恵を捉えている。 メカニズムは2つの入札を収集し、どちらを割り当てるか、どの支払いを行うかを決定する。
• 参考スコア（独自算出の注目度）: 7.288063443108292
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by online retail, we consider the problem of selling one item (e.g., an ad slot) to two non-excludable buyers (say, a merchant and a brand). This problem captures, for example, situations where a merchant and a brand cooperatively bid in an auction to advertise a product, and both benefit from the ad being shown. A mechanism collects bids from the two and decides whether to allocate and which payments the two parties should make. This gives rise to intricate incentive compatibility constraints, e.g., on how to split payments between the two parties. We approach the problem of finding a revenue-maximizing incentive-compatible mechanism from an online learning perspective; this poses significant technical challenges. First, the action space (the class of all possible mechanisms) is huge; second, the function that maps mechanisms to revenue is highly irregular, ruling out standard discretization-based approaches. In the stochastic setting, we design an efficient learning algorithm achieving a regret bound of $O(T^{3/4})$. Our approach is based on an adaptive discretization scheme of the space of mechanisms, as any non-adaptive discretization fails to achieve sublinear regret. In the adversarial setting, we exploit the non-Lipschitzness of the problem to prove a strong negative result, namely that no learning algorithm can achieve more than half of the revenue of the best fixed mechanism in hindsight. We then consider the $\sigma$-smooth adversary; we construct an efficient learning algorithm that achieves a regret bound of $O(T^{2/3})$ and builds on a succinct encoding of exponentially many experts. Finally, we prove that no learning algorithm can achieve less than $\Omega(\sqrt T)$ regret in both the stochastic and the smooth setting, thus narrowing the range where the minimax regret rates for these two problems lie.
• Abstract（参考訳）: オンライン小売によって動機づけられた私たちは、一品(例:広告スロット)を2つの非排除購入者(例:商人とブランド)に販売する問題を考える。 この問題は、例えば、マーチャントとブランドが商品を宣伝するために競売に協力的に入札する状況と、表示されている広告の利益の両方を捉えている。 メカニズムは2つの入札を収集し、どちらを割り当てるか、どの支払いを行うかを決定する。 これにより、複雑なインセンティブの互換性の制約が生まれます。 我々は、オンライン学習の観点から、収益を最大化するインセンティブ互換メカニズムを見つけるという問題にアプローチする。 第一に、アクション空間(全ての可能なメカニズムのクラス)は巨大であり、第二に、メカニズムを収益にマッピングする関数は非常に不規則であり、標準的な離散化に基づくアプローチを除外する。 確率的条件下では,残差の$O(T^{3/4})$を達成できる効率的な学習アルゴリズムを設計する。 我々のアプローチは、非適応的な離散化がサブ線形後悔を達成できないため、メカニズム空間の適応的な離散化スキームに基づいている。 逆向きの設定では、問題の非Lipschitznessを利用して、強い負の結果を証明し、すなわち、学習アルゴリズムが後見で最高の固定機構の収益の半分以上を達成できない。 次に、$\sigma$-smoothの逆数を考える。我々は、$O(T^{2/3})の後悔境界を達成し、指数的に多くの専門家の簡潔な符号化の上に構築する効率的な学習アルゴリズムを構築する。 最後に、確率的および滑らかな設定の両方において、学習アルゴリズムが$\Omega(\sqrt T)以下の後悔を達成できないことを証明し、これらの2つの問題に対するミニマックスの後悔率が生じる範囲を狭める。

関連論文リスト

• Procurement Auctions via Approximately Optimal Submodular Optimization [53.93943270902349]
  競売業者がプライベートコストで戦略的売り手からサービスを取得しようとする競売について検討する。 我々の目標は、取得したサービスの品質と販売者の総コストとの差を最大化する計算効率の良いオークションを設計することである。
  論文  参考訳（メタデータ） (2024-11-20T18:06:55Z)
• Multi-Agent Imitation Learning: Value is Easy, Regret is Hard [52.31989962031179]
  我々は,エージェント群を協調させようとする学習者の視点で,マルチエージェント模倣学習(MAIL)問題を研究する。 MAILの以前の作業のほとんどは、基本的には、デモのサポート内で専門家の振る舞いにマッチする問題を減らすものです。 エージェントが戦略的でないという仮定の下で、学習者と専門家の間の価値ギャップをゼロにするのに十分であるが、戦略的エージェントによる逸脱を保証するものではない。
  論文  参考訳（メタデータ） (2024-06-06T16:18:20Z)
• Learning to Maximize Gains From Trade in Small Markets [6.204762177970342]
  両面市場(ダブルオークション)をインセンティブの整合性と予算バランスの制約の下で設計する問題について検討する。 この結果は,1つの売り手と2つの買い手の間でも相関した値の分布の場合の一般的な不可能性である。 2つ目は、独立分布の場合、1つの売り手と2つの買い手のための効率的な学習アルゴリズムです。
  論文  参考訳（メタデータ） (2024-01-21T20:57:12Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。 このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。 上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
  論文  参考訳（メタデータ） (2023-02-02T16:30:33Z)
• Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning [1.994307489466967]
  有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。 対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-02-02T10:33:09Z)
• 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)
• Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
  競売人の収益を最大化しつつ、競売人の過去の後悔を最小限にする競売メカニズムは、経済学において重要であるが複雑な問題である。 ニューラルネットワークによる最適なオークションメカニズムの学習を通じて、注目すべき進歩が達成されている。
  論文  参考訳（メタデータ） (2022-10-11T16:13:25Z)
• Online Bidding Algorithms for Return-on-Spend Constrained Advertisers [10.500109788348732]
  この研究は、人気が高まっている制約の下で、単一の価値を最大化する広告主のための効率的なオンラインアルゴリズムを探索する。 我々は,指定したRoS制約を常に尊重しながら,期待のほぼ最適に後悔する簡単なオンラインアルゴリズムに貢献する。
  論文  参考訳（メタデータ） (2022-08-29T16:49:24Z)
• Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
  我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。 この問題に対する最初のパラメトリック下界を提供する。 本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
  論文  参考訳（メタデータ） (2020-11-10T12:45:02Z)

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

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