論文の概要: No-Regret Learning in Bilateral Trade via Global Budget Balance
- arxiv url: http://arxiv.org/abs/2310.12370v1
- Date: Wed, 18 Oct 2023 22:34:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-20 17:36:20.827215
- Title: No-Regret Learning in Bilateral Trade via Global Budget Balance
- Title(参考訳): グローバル予算均衡による二国間貿易におけるノンレグレット学習
- Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Federico Fusco
- Abstract要約: 問題のオンライン版を調査し、各段階で新しい売り手と買い手が到着する。
学習者の仕事は、各エージェントの価格を設定することであり、その評価について何の知識も持たない。
グローバルな予算バランスを必要とすることにより、二国間貿易のための最初の非レグレットアルゴリズムを提供する。
- 参考スコア(独自算出の注目度): 32.24227834513534
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilateral trade revolves around the challenge of facilitating transactions
between two strategic agents -- a seller and a buyer -- both of whom have a
private valuations for the item. We study the online version of the problem, in
which at each time step a new seller and buyer arrive. The learner's task is to
set a price for each agent, without any knowledge about their valuations. The
sequence of sellers and buyers is chosen by an oblivious adversary. In this
setting, known negative results rule out the possibility of designing
algorithms with sublinear regret when the learner has to guarantee budget
balance for each iteration. In this paper, we introduce the notion of global
budget balance, which requires the agent to be budget balance only over the
entire time horizon. By requiring global budget balance, we provide the first
no-regret algorithms for bilateral trade with adversarial inputs under various
feedback models. First, we show that in the full-feedback model the learner can
guarantee $\tilde{O}(\sqrt{T})$ regret against the best fixed prices in
hindsight, which is order-wise optimal. Then, in the case of partial feedback
models, we provide an algorithm guaranteeing a $\tilde{O}(T^{3/4})$ regret
upper bound with one-bit feedback, which we complement with a nearly-matching
lower bound. Finally, we investigate how these results vary when measuring
regret using an alternative benchmark.
- Abstract(参考訳): 二国間貿易は、2つの戦略エージェント(売り手と買い手)の取引を促進するという課題を中心に展開している。
我々は、問題のオンラインバージョンを調査し、各段階で新しい売り手と買い手が到着する。
学習者の仕事は、各エージェントの価格を設定することであり、その評価について何の知識も持たない。
売り手と買い手の連続は、不可解な敵によって選択される。
この設定では、既知の負の結果は、学習者が反復ごとに予算バランスを保証しなければならない場合に、サブ線形後悔を伴うアルゴリズムを設計する可能性を排除している。
本稿では,グローバルな予算バランスの概念を紹介する。これは,時間的地平線全体を通してのみ,エージェントが予算バランスを取ることを必要とする。
グローバル予算均衡を求めることにより,様々なフィードバックモデルにおいて,対向入力との双方向取引のための最初のno-regretアルゴリズムを提供する。
まず、フルフィードバックモデルにおいて学習者は、従順に最適である最高の固定価格に対して$\tilde{o}(\sqrt{t})$ regretを保証できることを示す。
そして、部分フィードバックモデルの場合、1ビットフィードバックで$\tilde{O}(T^{3/4})$残念な上限を保証し、ほぼ一致する下限を補完するアルゴリズムを提供する。
最後に,代替ベンチマークを用いて後悔度を測定する際に,これらの結果がどのように変化するかを検討する。
関連論文リスト
- An Online Learning Theory of Brokerage [3.8059763597999012]
オンライン学習の観点からトレーダー間のブローカーについて検討する。
既に研究されている他の二国間貿易問題とは異なり、指定された買い手や売り手の役割が存在しない場合に焦点を当てる。
第1の場合、最適率は$sqrtT$に低下し、第2の場合、問題は解けなくなる。
論文 参考訳(メタデータ) (2023-10-18T17:01:32Z) - Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。
学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
論文 参考訳(メタデータ) (2023-10-08T07:04:22Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳(メタデータ) (2023-03-15T17:59:27Z) - Learning to Incentivize Information Acquisition: Proper Scoring Rules
Meet Principal-Agent Model [64.94131130042275]
インセンティブ付き情報取得問題について検討し、主治官がエージェントを雇って代理情報を収集する。
UCBアルゴリズムをモデルに適合させる,実証可能なサンプル効率の良いアルゴリズムを設計する。
本アルゴリズムは,主役の最適利益に対する微妙な推定手順と,所望のエージェントの行動にインセンティブを与える保守的な補正手法を特徴とする。
論文 参考訳(メタデータ) (2023-03-15T13:40:16Z) - 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 [77.67037372500495]
オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T21:59:30Z) - An $\alpha$-regret analysis of Adversarial Bilateral Trade [4.244584441909098]
我々は、売り手と買い手のバリュエーションが完全に任意であるシーケンシャルな二国間取引を調査する。
我々は、社会福祉よりも近づきにくい貿易からの利益を考えます。
論文 参考訳(メタデータ) (2022-10-13T08:57:30Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳(メタデータ) (2022-03-03T02:55: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。