Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements

• URL: http://arxiv.org/abs/2205.00825v4
• Date: Fri, 31 May 2024 17:07:04 GMT
• Title: Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements
• Authors: Devansh Jalota, Yinyu Ye,
• Abstract summary: We study an online variant of Fisher markets, wherein users with privately known utility and budget parameters arrive sequentially. In this setting, we first study the limitations of static pricing algorithms, which set uniform prices for all users. We design adaptive posted-pricing algorithms, one with knowledge of the distribution of users' budget and utility parameters and another that adjusts prices solely based on past observations of user consumption.
• Score: 3.2732273647357437
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fisher markets are one of the most fundamental models for resource allocation. However, the problem of computing equilibrium prices in Fisher markets typically relies on complete knowledge of users' budgets and utility functions and requires transactions to happen in a static market where all users are present simultaneously. Motivated by these practical considerations, we study an online variant of Fisher markets, wherein users with privately known utility and budget parameters, drawn i.i.d. from a distribution, arrive sequentially. In this setting, we first study the limitations of static pricing algorithms, which set uniform prices for all users, along two performance metrics: (i) regret, i.e., the optimality gap in the objective of the Eisenberg-Gale program between an online algorithm and an oracle with complete information, and (ii) capacity violations, i.e., the over-consumption of goods relative to their capacities. Given the limitations of static pricing, we design adaptive posted-pricing algorithms, one with knowledge of the distribution of users' budget and utility parameters and another that adjusts prices solely based on past observations of user consumption, i.e., revealed preference feedback, with improved performance guarantees. Finally, we present numerical experiments to compare our revealed preference algorithm's performance to several benchmarks.

Related papers

• A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraints [54.46126953873298]
  We address the problem of dynamically pricing complementary items that are sequentially displayed to customers. Coherent pricing policies for complementary items are essential because optimizing the pricing of each item individually is ineffective. We empirically evaluate our approach using synthetic settings randomly generated from real-world data, and compare its performance in terms of constraints violation and regret.
  arXiv  Detail & Related papers  (2024-07-08T09:55:31Z)
• A novel decision fusion approach for sale price prediction using Elastic Net and MOPSO [0.0]
  Price prediction algorithms propose prices for every product or service according to market trends, projected demand, and other characteristics. As the dependent variable in price prediction, it is affected by several independent and correlated variables. This study introduces a novel decision level fusion approach to select informative variables in price prediction.
  arXiv  Detail & Related papers  (2024-03-29T07:59:33Z)
• Structured Dynamic Pricing: Optimal Regret in a Global Shrinkage Model [50.06663781566795]
  We consider a dynamic model with the consumers' preferences as well as price sensitivity varying over time. We measure the performance of a dynamic pricing policy via regret, which is the expected revenue loss compared to a clairvoyant that knows the sequence of model parameters in advance. Our regret analysis results not only demonstrate optimality of the proposed policy but also show that for policy planning it is essential to incorporate available structural information.
  arXiv  Detail & Related papers  (2023-03-28T00:23:23Z)
• Personalized Pricing with Invalid Instrumental Variables: Identification, Estimation, and Policy Learning [5.372349090093469]
  This work studies offline personalized pricing under endogeneity using an instrumental variable approach. We propose a new policy learning method for Personalized pRicing using Invalid iNsTrumental variables.
  arXiv  Detail & Related papers  (2023-02-24T14:50:47Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions. We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
  arXiv  Detail & Related papers  (2023-02-02T16:30:33Z)
• Interactive Learning with Pricing for Optimal and Stable Allocations in Markets [12.580391999838128]
  Large-scale online recommendation systems must facilitate the allocation of a limited number of items among competing users while learning their preferences from user feedback. Our framework enhances the quality of recommendations by exploring allocations that optimistically maximize the rewards. To minimize instability, a measure of users' incentives to deviate from recommended allocations, the algorithm prices the items based on a scheme derived from the Walrasian equilibria. Our approach is the first to integrate techniques from bandits, optimal resource allocation, and collaborative filtering to obtain an algorithm that achieves sub-linear social welfare regret as well as sub-linear instability.
  arXiv  Detail & Related papers  (2022-12-13T20:33:54Z)
• Linear Speedup in Personalized Collaborative Learning [69.45124829480106]
  Personalization in federated learning can improve the accuracy of a model for a user by trading off the model's bias. We formalize the personalized collaborative learning problem as optimization of a user's objective. We explore conditions under which we can optimally trade-off their bias for a reduction in variance.
  arXiv  Detail & Related papers  (2021-11-10T22:12:52Z)
• Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions [74.00030431081751]
  We formalize the notion of user-specific cost functions and introduce a new method for identifying actionable recourses for users. Our method satisfies up to 25.89 percentage points more users compared to strong baseline methods.
  arXiv  Detail & Related papers  (2021-11-01T19:49:35Z)
• Fairness, Welfare, and Equity in Personalized Pricing [88.9134799076718]
  We study the interplay of fairness, welfare, and equity considerations in personalized pricing based on customer features. We show the potential benefits of personalized pricing in two settings: pricing subsidies for an elective vaccine, and the effects of personalized interest rates on downstream outcomes in microcredit.
  arXiv  Detail & Related papers  (2020-12-21T01:01:56Z)
• Online Regularization towards Always-Valid High-Dimensional Dynamic Pricing [19.11333865618553]
  We propose a novel approach for designing dynamic pricing policy based regularized online statistical learning with theoretical guarantees. Our proposed online regularization scheme equips the proposed optimistic online regularized maximum likelihood pricing (OORMLP) pricing policy with three major advantages. In theory, the proposed OORMLP algorithm exploits the sparsity structure of high-dimensional models and secures a logarithmic regret in a decision horizon.
  arXiv  Detail & Related papers  (2020-07-05T23:52:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.