Interactive Learning with Pricing for Optimal and Stable Allocations in Markets

• URL: http://arxiv.org/abs/2212.06891v1
• Date: Tue, 13 Dec 2022 20:33:54 GMT
• Title: Interactive Learning with Pricing for Optimal and Stable Allocations in Markets
• Authors: Yigit Efe Erginbas, Soham Phade, Kannan Ramchandran
• Abstract summary: 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.
• Score: 12.580391999838128
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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. As a principled way of incorporating market constraints and user incentives in the design, we consider our objectives to be two-fold: maximal social welfare with minimal instability. To maximize social welfare, our proposed 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. Though it is known that these equilibria yield stable prices for markets with known user preferences, our approach accounts for the inherent uncertainty in the preferences and further ensures that the users accept their recommendations under offered prices. To the best of our knowledge, our approach is the first to integrate techniques from combinatorial bandits, optimal resource allocation, and collaborative filtering to obtain an algorithm that achieves sub-linear social welfare regret as well as sub-linear instability. Empirical studies on synthetic and real-world data also demonstrate the efficacy of our strategy compared to approaches that do not fully incorporate all these aspects.

Related papers

• Fair and Welfare-Efficient Constrained Multi-matchings under Uncertainty [17.364297444721057]
  We study fair allocation of constrained resources, where a market designer optimize overall welfare while maintaining group fairness. In many large-scale settings, utilities are not known in advance, but are instead observed after realizing the allocation. We discuss these trade-offs under two paradigms for preference modeling.
  arXiv  Detail & Related papers  (2024-11-04T22:42:34Z)
• Quantifying User Coherence: A Unified Framework for Cross-Domain Recommendation Analysis [69.37718774071793]
  This paper introduces novel information-theoretic measures for understanding recommender systems. We evaluate 7 recommendation algorithms across 9 datasets, revealing the relationships between our measures and standard performance metrics.
  arXiv  Detail & Related papers  (2024-10-03T13:02:07Z)
• OptiGrad: A Fair and more Efficient Price Elasticity Optimization via a Gradient Based Learning [7.145413681946911]
  This paper presents a novel approach to optimizing profit margins in non-life insurance markets through a gradient descent-based method. It targets three key objectives: 1) maximizing profit margins, 2) ensuring conversion rates, and 3) enforcing fairness criteria such as demographic parity (DP)
  arXiv  Detail & Related papers  (2024-04-16T04:21:59Z)
• Insurance pricing on price comparison websites via reinforcement learning [7.023335262537794]
  This paper introduces reinforcement learning framework that learns optimal pricing policy by integrating model-based and model-free methods. The paper also highlights the importance of evaluating pricing policies using an offline dataset in a consistent fashion.
  arXiv  Detail & Related papers  (2023-08-14T04:44:56Z)
• Incentive-Aware Recommender Systems in Two-Sided Markets [49.692453629365204]
  We propose a novel recommender system that aligns with agents' incentives while achieving myopically optimal performance. Our framework models this incentive-aware system as a multi-agent bandit problem in two-sided markets. Both algorithms satisfy an ex-post fairness criterion, which protects agents from over-exploitation.
  arXiv  Detail & Related papers  (2022-11-23T22:20:12Z)
• Interactive Recommendations for Optimal Allocations in Markets with Constraints [12.580391999838128]
  We propose an interactive framework where the system provider can enhance the quality of recommendations to the users. We employ an integrated approach using techniques from collaborative filtering, bandits, and optimal resource allocation. Empirical studies on synthetic matrix and real-world data also demonstrate the effectiveness and performance of our approach.
  arXiv  Detail & Related papers  (2022-07-08T22:16:51Z)
• Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements [3.2732273647357437]
  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.
  arXiv  Detail & Related papers  (2022-04-27T05:03:45Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  We casting online learning problems in which a decision maker wants to maximize their expected reward without violating a finite set of $m$m resource constraints. Our framework allows the decision maker to handle its evidence flexibility and costoretic functions.
  arXiv  Detail & Related papers  (2022-02-28T12:10:48Z)
• Policy Gradient Bayesian Robust Optimization for Imitation Learning [49.881386773269746]
  We derive a novel policy gradient-style robust optimization approach, PG-BROIL, to balance expected performance and risk. Results suggest PG-BROIL can produce a family of behaviors ranging from risk-neutral to risk-averse.
  arXiv  Detail & Related papers  (2021-06-11T16:49:15Z)
• 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)
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences [91.3755431537592]
  We study the problem of decision-making in the setting of a scarcity of shared resources when the preferences of agents are unknown a priori. Our approach is based on the representation of preferences in a reproducing kernel Hilbert space. We derive optimal strategies that maximize agents' expected payoffs.
  arXiv  Detail & Related papers  (2020-10-29T03:08:22Z)

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.