論文の概要: Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade

• arxiv url: http://arxiv.org/abs/2509.22563v1
• Date: Fri, 26 Sep 2025 16:42:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:54.59115
• Title: Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade
• Title（参考訳）: バイラテラル取引における利益最大化のためのほぼ28のリフレクト境界
• Authors: Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn,
• Abstract要約: バイラテラル取引は、売り手と買い手という2つの戦略エージェントの仲介を行うタスクをモデル化する。 我々は,この問題をブローカーの観点から,後悔の最小化フレームワークを用いて検討する。 本稿では,売り手と評価を引いた場合,約$tildeO(sqrtT)=後悔を保証できる学習アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 14.182863671689836
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We study this problem from the perspective of a broker, in a regret minimization framework. At each time step, a new seller and buyer arrive, and the broker has to propose a mechanism that is incentive-compatible and individually rational, with the goal of maximizing profit. We propose a learning algorithm that guarantees a nearly tight $\tilde{O}(\sqrt{T})$ regret in the stochastic setting when seller and buyer valuations are drawn i.i.d. from a fixed and possibly correlated unknown distribution. We further show that it is impossible to achieve sublinear regret in the non-stationary scenario where valuations are generated upfront by an adversary. Our ambitious benchmark for these results is the best incentive-compatible and individually rational mechanism. This separates us from previous works on efficiency maximization in bilateral trade, where the benchmark is a single number: the best fixed price in hindsight. A particular challenge we face is that uniform convergence for all mechanisms' profits is impossible. We overcome this difficulty via a careful chaining analysis that proves convergence for a provably near-optimal mechanism at (essentially) optimal rate. We further showcase the broader applicability of our techniques by providing nearly optimal results for the joint ads problem.
• Abstract（参考訳）: バイラテラル取引は、売り手と買い手という2つの戦略エージェントの仲介を行うタスクをモデル化する。 我々は,この問題をブローカーの観点から,後悔の最小化フレームワークを用いて検討する。 それぞれの段階において、新たな売り手と買い手が到着し、ブローカーは利益の最大化を目標として、インセンティブ互換で個々に合理的なメカニズムを提案する必要がある。 本稿では,不確実な分布から売り手と買い手の評価値を引き出す場合の確率的条件において,ほぼ厳密な$\tilde{O}(\sqrt{T})$後悔を保証する学習アルゴリズムを提案する。 さらに,非定常シナリオにおいて,相手が事前評価を発生させるようなサブ線形後悔を実現することは不可能であることを示す。 これらの結果に対する私たちの野心的なベンチマークは、インセンティブと互換性があり、個々に合理的なメカニズムです。 これは、ベンチマークが単一数である二国間貿易における効率の最大化に関する以前の研究とは別のものだ。 特に直面する課題は、すべてのメカニズムの利益に対する一様収束は不可能であるということです。 この難しさを、(必然的に)最適速度で証明可能な準最適機構の収束を証明する、慎重な連鎖解析によって克服する。 さらに,共同広告問題に対して,ほぼ最適な結果を提供することにより,我々の技術の適用性を示す。

関連論文リスト

• Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search [20.536739487240318]
  ワンマックス検索はオンライン意思決定における古典的な問題である。 学習強化環境における1マックス探索の解析に得られる滑らかさの活用法を示す。
  論文  参考訳（メタデータ） (2025-02-08T23:25:52Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• Selling Joint Ads: A Regret Minimization Perspective [7.288063443108292]
  オンライン小売によるモチベーションにより、一品(広告スロットなど)を2つの非排除購入者(商店、ブランド等)に販売する問題を考える。 この問題は、例えば、マーチャントとブランドが商品を宣伝するために競売に協力して入札する状況と、表示されている広告の恩恵を捉えている。 メカニズムは2つの入札を収集し、どちらを割り当てるか、どの支払いを行うかを決定する。
  論文  参考訳（メタデータ） (2024-09-12T07:59:10Z)
• 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)
• Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents [52.75161794035767]
  性能インセンティブとロバストネスの2つの目的を同時に満たすバンディットアルゴリズムのクラスを導入する。 そこで本研究では,第2価格オークションのアイデアをアルゴリズムと組み合わせることで,プリンシパルが腕の性能特性に関する情報を持たないような設定が可能であることを示す。
  論文  参考訳（メタデータ） (2023-12-13T06:54:49Z)
• An $α$-regret analysis of Adversarial Bilateral Trade [10.275531964940425]
  我々は、売り手と買い手のバリュエーションが完全に任意であるシーケンシャルな二国間取引を調査する。 我々は、社会福祉よりも近づきにくい貿易からの利益を考えます。
  論文  参考訳（メタデータ） (2022-10-13T08:57:30Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。 まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。 当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
  論文  参考訳（メタデータ） (2020-04-19T18:00:58Z)

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

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