論文の概要: An $α$-regret analysis of Adversarial Bilateral Trade
- arxiv url: http://arxiv.org/abs/2210.06846v2
- Date: Thu, 10 Oct 2024 15:27:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-11 14:27:40.310407
- Title: An $α$-regret analysis of Adversarial Bilateral Trade
- Title（参考訳）: 対外貿易のα$-regret分析
- Authors: Yossi Azar, Amos Fiat, Federico Fusco,
- Abstract要約: 我々は、売り手と買い手のバリュエーションが完全に任意であるシーケンシャルな二国間取引を調査する。
我々は、社会福祉よりも近づきにくい貿易からの利益を考えます。
- 参考スコア（独自算出の注目度）: 10.275531964940425
- License:
- Abstract: We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary (i.e., determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade which is harder to approximate than social welfare. We consider a variety of feedback scenarios and distinguish the cases where the mechanism posts one price and when it can post different prices for buyer and seller. We show several surprising results about the separation between the different scenarios. In particular we show that (a) it is impossible to achieve sublinear $\alpha$-regret for any $\alpha<2$, (b) but with full feedback sublinear $2$-regret is achievable (c) with a single price and partial feedback one cannot get sublinear $\alpha$ regret for any constant $\alpha$ (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear $2$-regret, and (e) there is a provable separation in the $2$-regret bounds between full and partial feedback.
- Abstract（参考訳）: 我々は、売り手と買い手のバリュエーションが完全に任意である(すなわち、敵によって決定される)連続的な二国間貿易について研究する。
売り手と買い手は、利益のためのプライベートな評価額を持つ戦略的エージェントであり、目標は、インセンティブに適合し、個々に合理的で、予算のバランスを保ちながら、効率を最大化(または貿易から利益を得る)するメカニズムを設計することである。
本稿では,社会福祉よりも貿易から得られる利益を概観する。
我々は、さまざまなフィードバックシナリオを検討し、そのメカニズムが1つの価格を投稿し、買い手と売り手に対して異なる価格を投稿できるケースを区別する。
異なるシナリオの分離について、いくつかの驚くべき結果を示す。
特に私たちが示すのは
(a)任意の$\alpha<2$に対してsublinear $\alpha$-regretを達成することは不可能である。
(b)しかし、完全なフィードバックサブリニアである$2-regretは達成可能である
(c) 1 つの価格と部分的なフィードバックで、任意の定数 $\alpha$ に対して sublinear $\alpha$ regret を得ることはできない。
(d)それでも、1ビットフィードバックでも2つの価格を投稿すると、サブリニアな$2-regretが得られます。
(e) 完全なフィードバックと部分的なフィードバックの2ドルのバウンダリに、証明可能な分離がある。
関連論文リスト
- 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) - 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) - 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) - Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T21:59:30Z) - A Reinforcement Learning Approach in Multi-Phase Second-Price Auction
Design [158.0041488194202]
多相第2価格オークションにおけるリザーブ価格の最適化について検討する。
売り手の視点からは、潜在的に非現実的な入札者の存在下で、環境を効率的に探索する必要がある。
第三に、売り手のステップごとの収益は未知であり、非線形であり、環境から直接観察することさえできない。
論文 参考訳（メタデータ） (2022-10-19T03:49:05Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳（メタデータ） (2022-08-22T17:24:55Z) - Bilateral Trade: A Regret Minimization Perspective [5.031063690574698]
我々は、この二国間貿易問題を、売り手/買い手の相互作用のラウンドでT$以上の最小化フレームワークに配置した。
我々の主な貢献は、異なるフィードバックモデルとプライベートバリュエーションを持つ固定価格機構に対する後悔の体制の完全な評価である。
論文 参考訳（メタデータ） (2021-09-08T22:11:48Z) - A Regret Analysis of Bilateral Trade [5.031063690574698]
我々は、売り手/買い手の相互作用のラウンド上の後悔最小化フレームワークに二国間貿易問題で初めてキャストしました。
私達の主な貢献は異なったモデルのフィードバックおよび私用評価の固定価格のメカニズムのための後悔の体制の完全な特徴付けです。
論文 参考訳（メタデータ） (2021-02-16T08:53:17Z) - Dropout as a Regularizer of Interaction Effects [76.84531978621143]
ドロップアウトは高次相互作用に対する正則化器である。
我々はこの視点を分析的かつ実証的に証明する。
また、高次相互作用に対して同じ選択的な圧力を得ることも困難である。
論文 参考訳（メタデータ） (2020-07-02T01:11:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。