論文の概要: 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.
関連論文リスト
- No-Regret Learning in Bilateral Trade via Global Budget Balance [32.24227834513534]
問題のオンライン版を調査し、各段階で新しい売り手と買い手が到着する。
学習者の仕事は、各エージェントの価格を設定することであり、その評価について何の知識も持たない。
グローバルな予算バランスを必要とすることにより、二国間貿易のための最初の非レグレットアルゴリズムを提供する。
論文 参考訳(メタデータ) (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) - A Reinforcement Learning Approach in Multi-Phase Second-Price Auction
Design [158.0041488194202]
多相第2価格オークションにおけるリザーブ価格の最適化について検討する。
売り手の視点からは、潜在的に非現実的な入札者の存在下で、環境を効率的に探索する必要がある。
第三に、売り手のステップごとの収益は未知であり、非線形であり、環境から直接観察することさえできない。
論文 参考訳(メタデータ) (2022-10-19T03:49:05Z) - An $\alpha$-regret analysis of Adversarial Bilateral Trade [4.244584441909098]
我々は、売り手と買い手のバリュエーションが完全に任意であるシーケンシャルな二国間取引を調査する。
我々は、社会福祉よりも近づきにくい貿易からの利益を考えます。
論文 参考訳(メタデータ) (2022-10-13T08:57:30Z) - Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
競売人の収益を最大化しつつ、競売人の過去の後悔を最小限にする競売メカニズムは、経済学において重要であるが複雑な問題である。
ニューラルネットワークによる最適なオークションメカニズムの学習を通じて、注目すべき進歩が達成されている。
論文 参考訳(メタデータ) (2022-10-11T16:13:25Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with
Probabilistically Triggered Arms or Independent Arms [53.89752069984382]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-08-31T13:09:39Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。