# Interactive Learning with Pricing for Optimal and Stable Allocations in Markets

arXiv: https://arxiv.org/abs/2212.06891 · HTML: https://mlsanity.com/paper/2212.06891/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 13 Dec 2022.

## Builds on (most cited first, 13 of 13)

- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits](https://mlsanity.com/paper/1504.06937/) (2015)
- [Matching while Learning](https://mlsanity.com/paper/1603.04549/) (2016)
- [Online Interactive Collaborative Filtering Using Multi-Armed Bandit with Dependent Arms](https://mlsanity.com/paper/1708.03058/) (2017)
- [Competing Bandits: The Perils of Exploration Under Competition](https://mlsanity.com/paper/2007.10144/) (2020)
- [Structured Stochastic Linear Bandits](https://mlsanity.com/paper/1606.05693/) (2016)
- [Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation](https://mlsanity.com/paper/2004.01136/) (2020)

## Built on by (most cited first, 1 of 1)

- [A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming](https://mlsanity.com/paper/2606.29221/) (2026)

## Abstract (arXiv)

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.