論文の概要: 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})$よりもよい後悔と制約違反を達成できないことを示す。
最後に,いくつかのベンチマークに対して,提案手法の性能を示す数値実験を行った。
関連論文リスト
- A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraints [54.46126953873298]
顧客に対して順次表示される補完アイテムの動的価格設定の問題に対処する。
各項目の価格を個別に最適化するのは効果がないため、補完項目のコヒーレントな価格ポリシーが不可欠である。
実世界のデータからランダムに生成した合成設定を用いて,我々のアプローチを実証的に評価し,制約違反や後悔の観点からその性能を比較した。
論文 参考訳（メタデータ） (2024-07-08T09:55:31Z) - A novel decision fusion approach for sale price prediction using Elastic Net and MOPSO [0.0]
価格予測アルゴリズムは、市場動向、予測された需要、その他の特性に応じて、すべての製品またはサービスの価格を提案する。
価格予測における依存変数として、いくつかの独立変数および相関変数に影響される。
本研究では,価格予測において情報変数を選択するための新たな意思決定レベル融合手法を提案する。
論文 参考訳（メタデータ） (2024-03-29T07:59:33Z) - Structured Dynamic Pricing: Optimal Regret in a Global Shrinkage Model [50.06663781566795]
消費者の嗜好と価格感が時間とともに変化する動的モデルを考える。
我々は,モデルパラメータの順序を事前に把握している透視者と比較して,収益損失が予想される,後悔による動的価格政策の性能を計測する。
提案した政策の最適性を示すだけでなく,政策立案のためには,利用可能な構造情報を組み込むことが不可欠であることを示す。
論文 参考訳（メタデータ） (2023-03-28T00:23:23Z) - Personalized Pricing with Invalid Instrumental Variables:
Identification, Estimation, and Policy Learning [5.372349090093469]
本研究は,インストゥルメンタル変数アプローチを用いて,内在性の下でのオフラインパーソナライズド価格について検討する。
Invalid iNsTrumental変数を用いたパーソナライズされたプライシングのための新しいポリシー学習手法を提案する。
論文 参考訳（メタデータ） (2023-02-24T14:50:47Z) - Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。
このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。
上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
論文 参考訳（メタデータ） (2023-02-02T16:30:33Z) - Interactive Learning with Pricing for Optimal and Stable Allocations in
Markets [12.580391999838128]
大規模オンラインレコメンデーションシステムは、ユーザのフィードバックから好みを学習しながら、競合するユーザ間で限られた数のアイテムの割り当てを容易にする必要がある。
我々のフレームワークは、報酬を楽観的に最大化するアロケーションを探索することで、レコメンデーションの品質を高める。
不安定性を最小限に抑えるため、推薦されたアロケーションから逸脱するユーザのインセンティブを測定するため、アルゴリズムはWalrasian equilibriaから派生したスキームに基づいてアイテムを価格設定する。
本手法は, 帯域幅, 最適資源配分, 協調フィルタリングの手法を統合し, サブリニアな社会福祉の後悔と, サブリニアな不安定性を実現するアルゴリズムを得るための最初の手法である。
論文 参考訳（メタデータ） (2022-12-13T20:33:54Z) - 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) - Fairness, Welfare, and Equity in Personalized Pricing [88.9134799076718]
顧客特性に基づくパーソナライズ価格における公平性、福祉、株式の配慮の相互作用について検討する。
選択ワクチンの価格補助金と、マイクロクレジットの下流結果に対するパーソナライズされた利率の影響の2つの設定において、パーソナライズされた価格の潜在的利点を示す。
論文 参考訳（メタデータ） (2020-12-21T01:01:56Z) - Online Regularization towards Always-Valid High-Dimensional Dynamic
Pricing [19.11333865618553]
本稿では,動的価格ポリシーに基づくオンライン統計学習を理論的保証付きで設計するための新しい手法を提案する。
提案手法は,提案する楽観的オンライン定期化最大価格(OORMLP)に3つの大きな利点がある。
理論的には,提案したOORMLPアルゴリズムは高次元モデルの空間構造を利用し,決定の地平線における対数的後悔を保証する。
論文 参考訳（メタデータ） (2020-07-05T23:52:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。