論文の概要: Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism
- arxiv url: http://arxiv.org/abs/2611.08173v1
- Date: Thu, 05 Nov 2026 15:30:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-07 04:55:13.563365
- Title: Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism
- Title（参考訳）: 両国間貿易における利益最大化のためのレグレト・バウンド--ベスト・ポスト・プライス・メカニズムの学習
- Abstract要約: バイラテラル取引は、売り手と買い手という2つの戦略エージェントの仲介を行うタスクをモデル化する。
我々は,この問題を,後悔の最小化フレームワークにおける利益最大化ブローカーの観点から検討する。
逆算アルゴリズムは,局所的な推定手順と情報に基づくミニマックス構成を組み合わせる。
- 参考スコア（独自算出の注目度）: 9.429817463400644
- 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 profit-maximizing broker in a regret minimization framework. At each time step, a new seller and buyer arrive and the broker proposes a trading price to each agent. The trade happens if both agents accept, and the profit of the broker is the difference between the price received from the buyer and the one paid to the seller. At the end of each interaction, the learner only observes whether the trade occurred, and its goal is to achieve sublinear regret relative to the best fixed pair of prices in hindsight. We start by investigating the adversarial version of the problem, where buyer and seller valuations are generated by an adversary. In this setting, we construct a polynomial-time learning algorithm with a $\tilde O(T^{\frac 23})$ regret rate, which is nearly tight even if the valuations are drawn i.i.d. from independent distributions, thus matching the rate for one-sided pricing. Our adversarial algorithm combines a localized estimation procedure with an information-based minimax construction. We then consider valuations drawn i.i.d. from independent distributions satisfying the monotone-hazard-rate (MHR) property and provide a learning algorithm with nearly tight $\tilde{O}(\sqrt{T})$ regret. The algorithm combines localized estimation with a stochastic convex bandit routine applied to the negative logarithm of expected profit. Finally, we complement this result by showing a separation between MHR and regular distributions, proving that the minimax regret rate in the latter setting is $\tilde Θ(T^{\frac 35})$. This last result contrasts with the $\tilde{O}(\sqrt{T})$ regret bound that can be obtained for one-sided pricing with regular distributions.
- Abstract（参考訳）: バイラテラル取引は、売り手と買い手という2つの戦略エージェントの仲介を行うタスクをモデル化する。
我々は,この問題を,後悔の最小化フレームワークにおける利益最大化ブローカーの観点から検討する。
各ステップで、新しい売り手と買い手が到着し、ブローカーは各エージェントに取引価格を提案する。
取引は、双方のエージェントが受け入れた場合に行われ、ブローカーの利益は、買い手から受け取った価格と売り手に支払われた価格との差である。
各相互作用の最後には、学習者は、取引が起こったかどうかのみを観察し、その目標は、後見の最高の固定された価格に対して、サブリニアな後悔を達成することである。
まず、買い手と売り手のバリュエーションが相手によって生成される問題の逆バージョンを調査することから始める。
この設定では、多項式時間学習アルゴリズムを$\tilde O(T^{\frac 23})$ regret rateで構築する。
逆算アルゴリズムは,局所的な推定手順と情報に基づくミニマックス構成を組み合わせる。
次に、単調ハザードレート(MHR)特性を満たす独立分布から引き出された評価を考察し、ほぼ厳密な$\tilde{O}(\sqrt{T})の学習アルゴリズムを提供する。
このアルゴリズムは局所推定と確率的凸バンディットルーチンを結合し、期待される利益の負の対数に適用する。
最後に、この結果を MHR と正規分布の分離を示し、後者の設定におけるミニマックス後悔率が$\tilde >(T^{\frac 35})$であることを証明することで補完する。
この最後の結果は、正規分布を持つ一方の価格で得られる$\tilde{O}(\sqrt{T})$ regret boundとは対照的である。
関連論文リスト
- Contextual Online Bilateral Trade [18.8734045754182]
我々は、貿易と利益の2つの目的について研究する。
我々は、取引の利益のために$O(dlog d)$後悔するアルゴリズムを設計し、利益のために$O(dlog T + dlog d)$後悔するアルゴリズムを設計する。
論文 参考訳（メタデータ） (2026-02-13T13:03:10Z) - Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。
本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
論文 参考訳（メタデータ） (2025-10-20T02:28:08Z) - A Parametric Contextual Online Learning Theory of Brokerage [8.049531918823758]
トレーダー間のブローカーのオンライン学習問題における文脈情報の役割について検討する。
このシーケンシャルな問題では、各ステップで、2人のトレーダーが取引したい資産に関する秘密のバリュエーションを持って到着します。
学習者(ブローカー)は、資産と市場条件に関するコンテキストデータに基づくトレーディング(またはブローカー)価格を提案する。
そして、トレーダーは、彼らの評価額がブローカー価格よりも高いか低いかに基づいて、購入または販売する意思を明らかにします。
論文 参考訳（メタデータ） (2024-05-22T18:38:05Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - No-Regret Learning in Bilateral Trade via Global Budget Balance [29.514323697659613]
我々は、様々なフィードバックモデルの下で、敵対的二元貿易のための最初のノンレグレットアルゴリズムを提供する。
フルフィードバックモデルでは、学習者は後見の最高の固定価格に対して$tilde O(sqrtT)$ regretを保証できる。
また,1ビットフィードバックを伴って,$tilde O(T3/4)$ regret upper boundを保証した学習アルゴリズムも提供する。
論文 参考訳（メタデータ） (2023-10-18T22:34:32Z) - An Online Learning Theory of Brokerage [3.8059763597999012]
オンライン学習の観点からトレーダー間のブローカーについて検討する。
既に研究されている他の二国間貿易問題とは異なり、指定された買い手や売り手の役割が存在しない場合に焦点を当てる。
第1の場合、最適率は$sqrtT$に低下し、第2の場合、問題は解けなくなる。
論文 参考訳（メタデータ） (2023-10-18T17:01:32Z) - Repeated Bilateral Trade Against a Smoothed Adversary [5.939280057673226]
我々は、アダプティブ$sigma$-smooth敵が売り手と買い手のバリュエーションを生成する二国間取引について検討する。
本研究では、異なるフィードバックモデルの下での固定価格機構に対する後悔状態の完全な特徴付けを行う。
論文 参考訳（メタデータ） (2023-02-21T16:30:10Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - A Reinforcement Learning Approach in Multi-Phase Second-Price Auction
Design [158.0041488194202]
多相第2価格オークションにおけるリザーブ価格の最適化について検討する。
売り手の視点からは、潜在的に非現実的な入札者の存在下で、環境を効率的に探索する必要がある。
第三に、売り手のステップごとの収益は未知であり、非線形であり、環境から直接観察することさえできない。
論文 参考訳（メタデータ） (2022-10-19T03:49:05Z) - Robust Learning of Optimal Auctions [84.13356290199603]
本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。
我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-07-13T17:37:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。