# Bandit Learning in Decentralized Matching Markets

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2020.

## Built on by (most cited first, 30 of 46)

- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Regret, stability & fairness in matching markets with bandit learners](https://mlsanity.com/paper/2102.06246/) (2021)
- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)
- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets](https://mlsanity.com/paper/2203.03684/) (2022)
- [Deep Learning for Two-Sided Matching](https://mlsanity.com/paper/2107.03427/) (2021)
- [Learning in Multi-Stage Decentralized Matching Markets](https://mlsanity.com/paper/2102.06988/) (2021)
- [Auditing for Human Expertise](https://mlsanity.com/paper/2306.01646/) (2023)
- [Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets](https://mlsanity.com/paper/2206.02344/) (2022)
- [Thompson Sampling for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2204.12048/) (2022)
- [Decentralized Learning in Online Queuing Systems](https://mlsanity.com/paper/2106.04228/) (2021)
- [Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility](https://mlsanity.com/paper/2401.01528/) (2024)
- [Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning](https://mlsanity.com/paper/2410.04376/) (2024)
- [An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit](https://mlsanity.com/paper/2111.04873/) (2021)
- [Competing for Shareable Arms in Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2305.19158/) (2023)
- [Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets](https://mlsanity.com/paper/2408.08690/) (2024)
- [Decentralized Competing Bandits in Non-Stationary Matching Markets](https://mlsanity.com/paper/2206.00120/) (2022)
- [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)
- [Cooperative Online Learning with Feedback Graphs](https://mlsanity.com/paper/2106.04982/) (2021)
- [Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning](https://mlsanity.com/paper/2205.02450/) (2022)
- [Competing Bandits in Matching Markets via Super Stability](https://mlsanity.com/paper/2506.15926/) (2025)
- [Competing Bandits in Time Varying Matching Markets](https://mlsanity.com/paper/2210.11692/) (2022)
- [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)
- [Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach](https://mlsanity.com/paper/2407.21294/) (2024)
- [Stable Matching with Ties: Approximation Ratios and Learning](https://mlsanity.com/paper/2411.03270/) (2024)
- [Bandit Learning in Matching Markets: Utilitarian and Rawlsian Perspectives](https://mlsanity.com/paper/2412.00301/) (2024)

## Abstract (arXiv)

We study two-sided matching markets in which one side of the market (the players) does not have a priori knowledge about its preferences for the other side (the arms) and is required to learn its preferences from experience. Also, we assume the players have no direct means of communication. This model extends the standard stochastic multi-armed bandit framework to a decentralized multiple player setting with competition. We introduce a new algorithm for this setting that, over a time horizon T, attains O(log(T)) stable regret when preferences of the arms over players are shared, and O(log(T)2) regret when there are no assumptions on the preferences on either side. Moreover, in the setting where a single player may deviate, we show that the algorithm is incentive compatible whenever the arms' preferences are shared, but not necessarily so when preferences are fully general.