# Regret, stability & fairness in matching markets with bandit learners

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 53 references that are in the map.
- First posted on arXiv 11 Feb 2021.

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

- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [Robust Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.03812/) (2020)
- [Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without](https://mlsanity.com/paper/1904.12233/) (2019)
- [Selfish Robustness and Equilibria in Multi-Player Bandits](https://mlsanity.com/paper/2002.01197/) (2020)
- [Competing Bandits: Learning under Competition](https://mlsanity.com/paper/1702.08533/) (2017)
- [Multi-user Communication Networks: A Coordinated Multi-armed Bandit Approach](https://mlsanity.com/paper/1808.04875/) (2018)
- [Dominate or Delete: Decentralized Competing Bandits in Serial Dictatorship](https://mlsanity.com/paper/2006.15166/) (2020)
- [Stable Matching Mechanisms are Not Obviously Strategy-Proof](https://mlsanity.com/paper/1511.00452/) (2015)

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

- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets](https://mlsanity.com/paper/2203.03684/) (2022)
- [Auditing for Human Expertise](https://mlsanity.com/paper/2306.01646/) (2023)
- [Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints](https://mlsanity.com/paper/2301.10230/) (2023)
- [Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty](https://mlsanity.com/paper/2501.03018/) (2025)
- [Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning](https://mlsanity.com/paper/2205.02450/) (2022)
- [Subgroup Fairness in Two-Sided Markets](https://mlsanity.com/paper/2106.02702/) (2021)
- [Competing Bandits in Time Varying Matching Markets](https://mlsanity.com/paper/2210.11692/) (2022)
- [Active Learning for Fair and Stable Online Allocations](https://mlsanity.com/paper/2406.14784/) (2024)
- [Multiplayer Information Asymmetric Bandits in Metric Spaces](https://mlsanity.com/paper/2503.08004/) (2025)
- [Multiplayer Information Asymmetric Contextual Bandits](https://mlsanity.com/paper/2503.08961/) (2025)
- [Bandit Learning in Matching Markets: Utilitarian and Rawlsian Perspectives](https://mlsanity.com/paper/2412.00301/) (2024)
- [Probably Correct Optimal Stable Matching under Two-Sided Uncertainty](https://mlsanity.com/paper/2607.04824/) (2026)
- [Decentralized Online Learning in Task Assignment Games for Mobile Crowdsensing](https://mlsanity.com/paper/2309.10594/) (2023)
- [Optimal Analysis for Bandit Learning in Matching Markets with Serial Dictatorship](https://mlsanity.com/paper/2512.06758/) (2025)
- [Double Auctions with Two-sided Bandit Feedback](https://mlsanity.com/paper/2208.06536/) (2022)
- [A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming](https://mlsanity.com/paper/2606.29221/) (2026)
- [Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits](https://mlsanity.com/paper/2609.19963/) (2026)
- [From Preference to Reciprocity: Decentralized Matching with Empirically Grounded LLM-agent Based Modeling](https://mlsanity.com/paper/2609.34679/) (2026)

## Abstract (arXiv)

Making an informed decision -- for example, when choosing a career or housing -- requires knowledge about the available options. Such knowledge is generally acquired through costly trial and error, but this learning process can be disrupted by competition. In this work, we study how competition affects the long-term outcomes of individuals as they learn. We build on a line of work that models this setting as a two-sided matching market with bandit learners. A recent result in this area states that it is impossible to simultaneously guarantee two natural desiderata: stability and low optimal regret for all agents. Resource-allocating platforms can point to this result as a justification for assigning good long-term outcomes to some agents and poor ones to others. We show that this impossibility need not hold true. In particular, by modeling two additional components of competition -- namely, costs and transfers -- we prove that it is possible to simultaneously guarantee four desiderata: stability, low optimal regret, fairness in the distribution of regret, and high social welfare.