論文の概要: Procurement Auctions via Approximately Optimal Submodular Optimization

• arxiv url: http://arxiv.org/abs/2411.13513v1
• Date: Wed, 20 Nov 2024 18:06:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-21 16:11:29.393684
• Title: Procurement Auctions via Approximately Optimal Submodular Optimization
• Title（参考訳）: ほぼ最適部分モジュラ最適化による調達オークション
• Authors: Yuan Deng, Amin Karbasi, Vahab Mirrokni, Renato Paes Leme, Grigoris Velegkas, Song Zuo,
• Abstract要約: 競売業者がプライベートコストで戦略的売り手からサービスを取得しようとする競売について検討する。 我々の目標は、取得したサービスの品質と販売者の総コストとの差を最大化する計算効率の良いオークションを設計することである。
• 参考スコア（独自算出の注目度）: 53.93943270902349
• License:
• Abstract: We study procurement auctions, where an auctioneer seeks to acquire services from strategic sellers with private costs. The quality of services is measured by a submodular function known to the auctioneer. Our goal is to design computationally efficient procurement auctions that (approximately) maximize the difference between the quality of the acquired services and the total cost of the sellers, while ensuring incentive compatibility (IC), individual rationality (IR) for sellers, and non-negative surplus (NAS) for the auctioneer. Our contributions are twofold: (i) we provide an improved analysis of existing algorithms for non-positive submodular function maximization, and (ii) we design efficient frameworks that transform submodular optimization algorithms into mechanisms that are IC, IR, NAS, and approximation-preserving. These frameworks apply to both the offline setting, where all sellers' bids and services are available simultaneously, and the online setting, where sellers arrive in an adversarial order, requiring the auctioneer to make irrevocable decisions. We also explore whether state-of-the-art submodular optimization algorithms can be converted into descending auctions in adversarial settings, where the schedule of descending prices is determined by an adversary. We show that a submodular optimization algorithm satisfying bi-criteria $(1/2, 1)$-approximation in welfare can be effectively adapted to a descending auction. Additionally, we establish a connection between descending auctions and online submodular optimization. Finally, we demonstrate the practical applications of our frameworks by instantiating them with state-of-the-art submodular optimization algorithms and empirically comparing their welfare performance on publicly available datasets with thousands of sellers.
• Abstract（参考訳）: 競売業者がプライベートコストで戦略的売り手からサービスを取得しようとする競売について検討する。 サービスの質は、競売業者に知られているサブモジュラー関数によって測定される。 我々のゴールは、購入したサービスの品質と販売者の総コストの差を最大化しつつ、販売者に対するインセンティブ互換性(IC)、個人合理性(IR)、オークション業者に対する非負の余剰(NAS)を確保できる計算効率の良い調達オークションを設計することである。 私たちの貢献は2つあります。 (i)非正の部分モジュラー関数最大化のための既存のアルゴリズムの改良分析を行い、 (II)サブモジュール最適化アルゴリズムをIC,IR,NAS,近似保存といった機構に変換する効率的なフレームワークを設計する。 これらのフレームワークは、すべての販売者の入札とサービスが同時に利用可能となるオフライン設定と、販売者が反対の順序で到着するオンライン設定の両方に適用される。 また、現在最先端のサブモジュラー最適化アルゴリズムが、逆条件下での下降オークションに変換可能かどうかについても検討し、下降価格の日程を逆条件で決定する。 両基準$(1/2, 1)$-approximationを満足する部分モジュラ最適化アルゴリズムは,下降オークションに効果的に適応できることを示す。 さらに,下降オークションとオンラインサブモジュール最適化の関連性を確立する。 最後に、我々のフレームワークの実践的応用を、最先端のサブモジュール最適化アルゴリズムでインスタンス化し、公開データセット上での福祉性能と数千の売り手とを実証的に比較することによって実証する。

関連論文リスト

• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。 競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
  論文  参考訳（メタデータ） (2024-05-31T19:26:05Z)
• Coordinated Dynamic Bidding in Repeated Second-Price Auctions with Budgets [17.937079224726073]
  予算を伴う第2価格の繰り返しオークションにおける協調オンライン入札アルゴリズムについて検討した。 我々は、すべてのクライアントに対して、独立入札で得られる最高のものよりも高いユーティリティを保証するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-13T11:55:04Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。 本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T21:59:30Z)
• A Modular Framework for Reinforcement Learning Optimal Execution [68.8204255655161]
  我々は、最適貿易実行問題への強化学習の適用のためのモジュラーフレームワークを開発する。 このフレームワークは、異なるシミュレーション設定の実装を容易にするために、柔軟性を念頭に設計されている。
  論文  参考訳（メタデータ） (2022-08-11T09:40:42Z)
• Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertising [42.7415188090209]
  我々は,オークションからコンテキストを効率的に抽出する深層モデルを開発し,オークションデザインのための豊富な特徴を提供する。 タオバオのEコマース広告システムにDNAが配備されている。
  論文  参考訳（メタデータ） (2021-06-07T13:20:40Z)
• Optimizing Multiple Performance Metrics with Deep GSP Auctions for E-commerce Advertising [28.343122250701498]
  eコマース広告では、広告プラットフォームは通常、ユーザーエクスペリエンス、広告主ユーティリティ、プラットフォーム収益など、さまざまなパフォーマンス指標を最適化するためのオークションメカニズムに依存している。 本稿では,Deep GSPオークション(Deep GSP auction)と呼ばれる新しいメカニズムを提案する。
  論文  参考訳（メタデータ） (2020-12-05T02:51:11Z)
• Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
  我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。 この問題に対する最初のパラメトリック下界を提供する。 本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
  論文  参考訳（メタデータ） (2020-11-10T12:45:02Z)
• 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)
• Dynamic Knapsack Optimization Towards Efficient Multi-Channel Sequential Advertising [52.3825928886714]
  我々は、動的knapsack問題として、シーケンシャルな広告戦略最適化を定式化する。 理論的に保証された二段階最適化フレームワークを提案し、元の最適化空間の解空間を大幅に削減する。 強化学習の探索効率を向上させるため,効果的な行動空間削減手法も考案した。
  論文  参考訳（メタデータ） (2020-06-29T18:50:35Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。 まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。 当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
  論文  参考訳（メタデータ） (2020-04-19T18:00:58Z)

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

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