論文の概要: A Regret Analysis of Bilateral Trade
- arxiv url: http://arxiv.org/abs/2102.08754v1
- Date: Tue, 16 Feb 2021 08:53:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-18 14:41:19.243229
- Title: A Regret Analysis of Bilateral Trade
- Title（参考訳）: 二国間貿易の残余分析
- Authors: Nicol\`o Cesa-Bianchi, Tommaso Cesari (TSE), Roberto Colomboni (IIT),
Federico Fusco, Stefano Leonardi
- Abstract要約: 我々は、売り手/買い手の相互作用のラウンド上の後悔最小化フレームワークに二国間貿易問題で初めてキャストしました。
私達の主な貢献は異なったモデルのフィードバックおよび私用評価の固定価格のメカニズムのための後悔の体制の完全な特徴付けです。
- 参考スコア（独自算出の注目度）: 5.031063690574698
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilateral trade, a fundamental topic in economics, models the problem of
intermediating between two strategic agents, a seller and a buyer, willing to
trade a good for which they hold private valuations. Despite the simplicity of
this problem, a classical result by Myerson and Satterthwaite (1983) affirms
the impossibility of designing a mechanism which is simultaneously efficient,
incentive compatible, individually rational, and budget balanced. This
impossibility result fostered an intense investigation of meaningful trade-offs
between these desired properties. Much work has focused on approximately
efficient fixed-price mechanisms, i.e., Blumrosen and Dobzinski (2014; 2016),
Colini-Baldeschi et al. (2016), which have been shown to fully characterize
strong budget balanced and ex-post individually rational direct revelation
mechanisms. All these results, however, either assume some knowledge on the
priors of the seller/buyer valuations, or a black box access to some samples of
the distributions, as in D{\"u}tting et al. (2021). In this paper, we cast for
the first time the bilateral trade problem in a regret minimization framework
over rounds of seller/buyer interactions, with no prior knowledge on the
private seller/buyer valuations. Our main contribution is a complete
characterization of the regret regimes for fixed-price mechanisms with
different models of feedback and private valuations, using as benchmark the
best fixed price in hindsight. More precisely, we prove the following bounds on
the regret:
$\bullet$ $\widetilde{\Theta}(\sqrt{T})$ for full-feedback (i.e., direct
revelation mechanisms);
$\bullet$ $\widetilde{\Theta}(T^{2/3})$ for realistic feedback (i.e.,
posted-price mechanisms) and independent seller/buyer valuations with bounded
densities;
$\bullet$ $\Theta(T)$ for realistic feedback and seller/buyer valuations with
bounded densities;
$\bullet$ $\Theta(T)$ for realistic feedback and independent seller/buyer
valuations;
$\bullet$ $\Theta(T)$ for the adversarial setting.
- Abstract（参考訳）: 経済の基本的なトピックである二国間貿易は、売り手と買い手の2つの戦略的代理人の間で仲介する問題をモデル化し、彼らが私的な評価を保持するために良いものを取引しようとします。
この問題の単純さにもかかわらず、Myerson and Satterthwaite (1983) による古典的な結果は、同時に効率的でインセンティブに適合し、個々に合理的で予算バランスの取れたメカニズムを設計できないことを裏付けている。
この不可能性の結果は、これらの望ましい特性間の有意義なトレードオフの激しい調査を促した。
多くの研究は、Blumrosen と Dobzinski (2014; 2016), Colini-Baldeschi et al など、およそ効率的な固定価格機構に焦点を当てている。
(2016)は、バランスの取れた強い予算と、個別に合理的な直接啓示メカニズムを完全に特徴付けることが示されている。
しかしながら、これらの結果のすべては、売り手/買い手の評価の事前知識を仮定するか、d{\"u}tting et alのように、分布のいくつかのサンプルにアクセスするブラックボックスのいずれかである。
(2021).
本稿では,二国間貿易問題が初めて,個人販売者/購入者評価の知識がなく,販売者/購入者間インタラクションのラウンドに対する後悔の最小化枠組みに突き当たった。
私たちの主な貢献は、フィードバックとプライベート評価の異なるモデルを備えた固定価格メカニズムの後悔体制の完全な評価であり、後見で最高の固定価格のベンチマークとして使用します。
More precisely, we prove the following bounds on the regret: $\bullet$ $\widetilde{\Theta}(\sqrt{T})$ for full-feedback (i.e., direct revelation mechanisms); $\bullet$ $\widetilde{\Theta}(T^{2/3})$ for realistic feedback (i.e., posted-price mechanisms) and independent seller/buyer valuations with bounded densities; $\bullet$ $\Theta(T)$ for realistic feedback and seller/buyer valuations with bounded densities; $\bullet$ $\Theta(T)$ for realistic feedback and independent seller/buyer valuations; $\bullet$ $\Theta(T)$ for the adversarial setting.
関連論文リスト
- Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。
適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
論文 参考訳（メタデータ） (2024-05-24T11:22:19Z) - Fair Online Bilateral Trade [20.243000364933472]
各取引が終わった後、プラットフォームは各トレーダーが現在の価格を受け入れたかどうかのみを学習するときに、取引から公平に利益を得るための後悔の完全な特徴を提示する。
それぞれのインタラクションの後に、プラットフォームが真のトレーダーのバリュエーションを観察できることを許す。
論文 参考訳（メタデータ） (2024-05-22T18:49:11Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (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) - Repeated Bilateral Trade Against a Smoothed Adversary [5.939280057673226]
我々は、アダプティブ$sigma$-smooth敵が売り手と買い手のバリュエーションを生成する二国間取引について検討する。
本研究では、異なるフィードバックモデルの下での固定価格機構に対する後悔状態の完全な特徴付けを行う。
論文 参考訳（メタデータ） (2023-02-21T16:30:10Z) - A Reinforcement Learning Approach in Multi-Phase Second-Price Auction
Design [158.0041488194202]
多相第2価格オークションにおけるリザーブ価格の最適化について検討する。
売り手の視点からは、潜在的に非現実的な入札者の存在下で、環境を効率的に探索する必要がある。
第三に、売り手のステップごとの収益は未知であり、非線形であり、環境から直接観察することさえできない。
論文 参考訳（メタデータ） (2022-10-19T03:49:05Z) - An $α$-regret analysis of Adversarial Bilateral Trade [10.275531964940425]
我々は、売り手と買い手のバリュエーションが完全に任意であるシーケンシャルな二国間取引を調査する。
我々は、社会福祉よりも近づきにくい貿易からの利益を考えます。
論文 参考訳（メタデータ） (2022-10-13T08:57:30Z) - Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
我々は、効率よく非結合な学習力学を確立し、各プレイヤーのトリガー後悔は、プレイの繰り返しの後に$O(log T)$として成長する。
これにより、これまでよく知られていた$O(T1/4)$よりも指数関数的に改善される。
論文 参考訳（メタデータ） (2022-08-20T20:48:58Z) - Bilateral Trade: A Regret Minimization Perspective [5.031063690574698]
我々は、この二国間貿易問題を、売り手/買い手の相互作用のラウンドでT$以上の最小化フレームワークに配置した。
我々の主な貢献は、異なるフィードバックモデルとプライベートバリュエーションを持つ固定価格機構に対する後悔の体制の完全な評価である。
論文 参考訳（メタデータ） (2021-09-08T22:11:48Z) - Certifying Strategyproof Auction Networks [53.37051312298459]
我々は、任意の数のアイテムと参加者でオークションを表現できるRegretNetアーキテクチャに焦点を当てる。
本稿では,ニューラルネットワーク検証文献から得られた手法を用いて,特定の評価プロファイルの下で戦略の安全性を明示的に検証する方法を提案する。
論文 参考訳（メタデータ） (2020-06-15T20:22:48Z) - VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit
Feedback [104.06766271716774]
本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。
まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。
当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
論文 参考訳（メタデータ） (2020-04-19T18:00:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。