論文の概要: Profit Maximization in Bilateral Trade against a Smooth Adversary
- arxiv url: http://arxiv.org/abs/2605.12664v1
- Date: Tue, 12 May 2026 19:12:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-14 23:30:27.633935
- Title: Profit Maximization in Bilateral Trade against a Smooth Adversary
- Title（参考訳）: Smooth Adversary に対するバイラテラル取引における利益の最大化
- Authors: Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn,
- Abstract要約: バイラテラル取引は、商品の取引を希望する売り手と買い手という2つの戦略エージェントの仲介業務をモデル化する。
本研究では,オンライン学習フレームワークにおける収益最大化ブローカーの観点から,エージェントのバリュエーションがスムーズな相手によって生成される問題について検討する。
我々は,時間的地平線に強い$tildeO(sqrtT)$ regret boundを保証できる学習アルゴリズムを考案した。
- 参考スコア（独自算出の注目度）: 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, who wish to trade a good. We study this problem from the perspective of a profit-maximizing broker within an online learning framework, where the agents' valuations are generated by a smooth adversary. We devise a learning algorithm that guarantees a $\tilde{O}(\sqrt{T})$ regret bound, which is tight in the time horizon $T$ up to poly-logarithmic factors. This matches the minimax rate for the stochastic i.i.d. case, and is also well separated from the adversarial setting, where sublinear-regret is unattainable. By extending the strong regret guarantees from the i.i.d. case to the smooth adversary, we significantly broaden the scope of settings where such fast rate is achievable, while closing an important gap in the regret landscape of this fundamental economic problem. To overcome the challenges posed by this adversary, we leverage a continuity property of smooth instances and combines this with a hierarchical net-construction of the broker's action space, which is analyzed via algorithmic chaining. We showcase the applicability of these techniques by deriving a similarly tight $\tilde{O}(\sqrt{T})$ regret bound for a related mechanism design model: the joint ads problem.
- Abstract（参考訳）: バイラテラル取引は、商品の取引を希望する売り手と買い手という2つの戦略エージェントの仲介業務をモデル化する。
本研究では,オンライン学習フレームワークにおける収益最大化ブローカーの観点から,エージェントのバリュエーションがスムーズな相手によって生成される問題について検討する。
学習アルゴリズムを考案し,多元対数因子までの時間的地平線において厳密な$T$である$\tilde{O}(\sqrt{T})$ regret boundを保証した。
これは確率的 i.d. の場合の minimax レートと一致し、また、サブリニア・レグレットが到達不可能な逆数の設定とよく分離される。
本論では、この場合の強い後悔の保証をスムーズな敵に広げることで、このような速さが達成可能な設定の範囲を大きく広げるとともに、この根本的な経済問題における後悔の背景における重要なギャップを埋める。
この逆転によって引き起こされる課題を克服するため、スムーズなインスタンスの連続性を利用し、アルゴリズムチェインを用いて解析されたブローカーのアクション空間の階層的ネット構成と組み合わせる。
これらの手法の適用性を示すために、同様の厳密な$\tilde{O}(\sqrt{T})$ regret bound for a related mechanism design model: the joint ads problem。
関連論文リスト
- Regret Minimization in Bilateral Trade With Perturbed Markets [25.375074054942434]
我々は、世界財政収支の制約を受ける買い手・売り手取引所における取引所(GFT)からの利得の最大化の問題に対処する。
対向的な環境は、最高の固定価格メカニズムに対する非回帰学習を可能にする。
提案アルゴリズムは, 予算バランスの悪いベースラインに対して, 最悪値である$tildemathcalO(T3/4)$ regret を維持できる。
論文 参考訳（メタデータ） (2026-05-11T12:37:53Z) - Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade [14.182863671689836]
バイラテラル取引は、売り手と買い手という2つの戦略エージェントの仲介を行うタスクをモデル化する。
我々は,この問題をブローカーの観点から,後悔の最小化フレームワークを用いて検討する。
本稿では,売り手と評価を引いた場合,約$tildeO(sqrtT)=後悔を保証できる学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-09-26T16:42:05Z) - Competing Bandits in Decentralized Contextual Matching Markets [13.313881962771777]
我々は、需要側(プレイヤーまたはエージェント)が供給側(腕)と競合する二面的マッチング市場における分散学習を研究する。
それぞれのエージェントに対して、腕平均は既知の特徴ベクトルと未知の(エージェント固有の)パラメータの線形関数で表されると仮定する。
そこで我々は,潜伏環境を特定し,同時に安定したマッチングを得る学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-18T18:08:05Z) - 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) - Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。
このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。
上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
論文 参考訳（メタデータ） (2023-02-02T16:30:33Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Collaborative Linear Bandits with Adversarial Agents: Near-Optimal
Regret Bounds [31.5504566292927]
我々は, 後悔を最小限に抑えるために, 中央サーバを介して協調できる$M$エージェントを含む線形帯域幅問題を考える。
これらのエージェントのわずか$alpha$は敵対的であり、任意に作用し、次の緊張に繋がる。
我々は、厳密な信頼区間を慎重に構築し、探索と探索のトレードオフをバランスさせる新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2022-06-06T18:16:34Z) - Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。
当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
論文 参考訳（メタデータ） (2022-02-28T12:10:48Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。