論文の概要: Online Learning in Fisher Markets with Unknown Agent Preferences
- arxiv url: http://arxiv.org/abs/2205.00825v1
- Date: Wed, 27 Apr 2022 05:03:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-09 00:45:47.713479
- Title: Online Learning in Fisher Markets with Unknown Agent Preferences
- Title(参考訳): 未知のエージェント選好による漁業市場のオンライン学習
- Authors: Devansh Jalota and Yinyu Ye
- Abstract要約: フィッシャー市場では、エージェント(利用者)は、公共事業を最大化する商品を購入するために(人工的な)通貨の予算を使う。
我々は,ユーザのプライバシを保ちながら,後悔とキャパシティ違反を犯すような,シンプルで効果的なアルゴリズムを開発した。
- 参考スコア(独自算出の注目度): 12.06012129084933
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In a Fisher market, agents (users) spend a budget of (artificial) currency to
buy goods that maximize their utilities, and producers set prices on
capacity-constrained goods such that the market clears. The equilibrium prices
in such a market are typically computed through the solution of a convex
program, e.g., the Eisenberg-Gale program, that aggregates users' preferences
into a centralized social welfare objective. However, the computation of
equilibrium prices using convex programs assumes that all transactions happen
in a static market wherein all users are present simultaneously and relies on
complete information on each user's budget and utility function.
Since, in practice, information on users' utilities and budgets is unknown
and users tend to arrive over time in the market, we study an online variant of
Fisher markets, wherein users enter the market sequentially. We focus on the
setting where users have linear utilities with privately known utility and
budget parameters drawn i.i.d. from a distribution $\mathcal{D}$. In this
setting, we develop a simple yet effective algorithm to set prices that
preserves user privacy while achieving a regret and capacity violation of
$O(\sqrt{n})$, where $n$ is the number of arriving users and the capacities of
the goods scale as $O(n)$. Here, our regret measure represents the optimality
gap in the objective of the Eisenberg-Gale program between the online
allocation policy and that of an offline oracle with complete information on
users' budgets and utilities. To establish the efficacy of our approach, we
show that even an algorithm that sets expected equilibrium prices with perfect
information on the distribution $\mathcal{D}$ cannot achieve both a regret and
constraint violation of better than $\Omega(\sqrt{n})$. Finally, we present
numerical experiments to demonstrate the performance of our approach relative
to several benchmarks.
- Abstract(参考訳): フィッシャー市場では、エージェント(利用者)は公共事業を最大化する商品を購入するために(人工的な)通貨の予算を使い、生産者は市場がクリアするような容量制限のある商品に価格を設定する。
そのような市場の均衡価格は通常、ユーザの好みを中央集権的な社会福祉目標に集約する凸プログラム(例えばアイゼンバーグ=ゲールプログラム)の解によって計算される。
しかしながら、凸プログラムを用いた平衡価格の計算は、全てのユーザが同時に存在し、各ユーザの予算とユーティリティ機能に関する完全な情報に依存する静的市場において、すべてのトランザクションが発生することを前提としている。
実際に,利用者のユーティリティや予算に関する情報が不明であり,市場投入の時間が経つにつれて利用者が到着する傾向にあるため,利用者が順次市場に参入するフィッシャー市場のオンライン版について検討する。
我々は、ユーザがプライベートに知られているユーティリティと予算パラメータを持つ線形ユーティリティを分散$\mathcal{d}$から描画する設定にフォーカスする。
この設定では,ユーザプライバシを保ちつつ,o(\sqrt{n})$の後悔とキャパシティ違反を実現した,シンプルかつ効果的な価格設定アルゴリズムを開発し,そこでは,n$は到着するユーザ数と商品の容量をo(n)$とする。
ここでは,オンラインアロケーションポリシとオフライン託宣の目標であるEisenberg-Galeプログラムの最適性ギャップを,ユーザの予算とユーティリティに関する完全な情報で表現する。
提案手法の有効性を確立するために,期待均衡価格を分布上の完全情報で設定したアルゴリズムでさえ,$\Omega(\sqrt{n})$よりもよい後悔と制約違反を達成できないことを示す。
最後に,いくつかのベンチマークに対して,提案手法の性能を示す数値実験を行った。
関連論文リスト
- Facility Location Games with Scaling Effects [69.28397508730046]
古典的な施設配置問題を考慮し、各エージェントの個々のコスト関数が、スケーリング係数によって乗算された施設からの距離と等しくなる変動を考察する。
戦略と匿名のメカニズムによって達成できる総コストと最大コストの近似比について結果が得られた。
論文 参考訳(メタデータ) (2024-02-29T07:08:18Z) - A Marketplace Price Anomaly Detection System at Scale [3.8632181427836945]
MoatPlusは、成長するマーケットプレースプラットフォームのためのスケーラブルな価格異常検出フレームワークである。
価格に基づく機能の不規則を検出するために、モデルのアンサンブルを構築します。
提案手法は, 高精度アンカーカバレッジを最大46.6%向上させる。
論文 参考訳(メタデータ) (2023-10-06T16:41:51Z) - Online Learning for Equilibrium Pricing in Markets under Incomplete
Information [5.092028049119383]
不完全な情報設定における均衡価格設定の問題を考える。
我々は3つのパフォーマンス指標、すなわち不需要、コストの後悔、支払いの後悔を共同で最適化する。
この拡張環境では,サブ線形後悔を伴うアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-21T00:53:37Z) - Personalized Pricing with Invalid Instrumental Variables:
Identification, Estimation, and Policy Learning [5.372349090093469]
本研究は,インストゥルメンタル変数アプローチを用いて,内在性の下でのオフラインパーソナライズド価格について検討する。
Invalid iNsTrumental変数を用いたパーソナライズされたプライシングのための新しいポリシー学習手法を提案する。
論文 参考訳(メタデータ) (2023-02-24T14:50:47Z) - Interactive Learning with Pricing for Optimal and Stable Allocations in
Markets [12.580391999838128]
大規模オンラインレコメンデーションシステムは、ユーザのフィードバックから好みを学習しながら、競合するユーザ間で限られた数のアイテムの割り当てを容易にする必要がある。
我々のフレームワークは、報酬を楽観的に最大化するアロケーションを探索することで、レコメンデーションの品質を高める。
不安定性を最小限に抑えるため、推薦されたアロケーションから逸脱するユーザのインセンティブを測定するため、アルゴリズムはWalrasian equilibriaから派生したスキームに基づいてアイテムを価格設定する。
本手法は, 帯域幅, 最適資源配分, 協調フィルタリングの手法を統合し, サブリニアな社会福祉の後悔と, サブリニアな不安定性を実現するアルゴリズムを得るための最初の手法である。
論文 参考訳(メタデータ) (2022-12-13T20:33:54Z) - 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) - Quantum computational finance: martingale asset pricing for incomplete
markets [69.73491758935712]
金融の価格問題に様々な量子技術を適用することができることを示す。
従来の研究と異なる3つの方法について議論する。
論文 参考訳(メタデータ) (2022-09-19T09:22:01Z) - Linear Speedup in Personalized Collaborative Learning [69.45124829480106]
フェデレート学習におけるパーソナライゼーションは、モデルのバイアスをトレーディングすることで、モデルの精度を向上させることができる。
ユーザの目的の最適化として、パーソナライズされた協調学習問題を定式化する。
分散の低減のためにバイアスを最適にトレードオフできる条件について検討する。
論文 参考訳(メタデータ) (2021-11-10T22:12:52Z) - Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions [74.00030431081751]
本稿では,ユーザ固有のコスト関数の概念を定式化し,ユーザのための行動可能なリコースを識別する新しい手法を提案する。
本手法は,強いベースライン法に比べて最大25.89パーセントのユーザを満足させる。
論文 参考訳(メタデータ) (2021-11-01T19:49:35Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳(メタデータ) (2021-02-23T18:25:13Z) - Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。
意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。
この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
論文 参考訳(メタデータ) (2020-12-13T04:47:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。