# Competing Bandits in Matching Markets via Super Stability

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 19 Jun 2025.

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

- [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)
- [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)
- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Matching while Learning](https://mlsanity.com/paper/1603.04549/) (2016)
- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets](https://mlsanity.com/paper/2206.02344/) (2022)
- [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)
- [Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets](https://mlsanity.com/paper/2408.08690/) (2024)
- [Converging to Stability in Two-Sided Bandits: The Case of Unknown Preferences on Both Sides of a Matching Market](https://mlsanity.com/paper/2302.06176/) (2023)
- [Stable Matching with Ties: Approximation Ratios and Learning](https://mlsanity.com/paper/2411.03270/) (2024)

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

- [Probably Correct Optimal Stable Matching under Two-Sided Uncertainty](https://mlsanity.com/paper/2607.04824/) (2026)
- [MenuNet: A Strategy-Proof Mechanism for Matching Markets](https://mlsanity.com/paper/2605.03216/) (2026)
- [Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits](https://mlsanity.com/paper/2609.19963/) (2026)
- [DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback](https://mlsanity.com/paper/2610.12960/) (2026)

## Abstract (arXiv)

We study bandit learning in matching markets with two-sided reward uncertainty, extending prior research primarily focused on single-sided uncertainty. Leveraging the concept of `super-stability' from Irving (1994), we demonstrate the advantage of the Extended Gale-Shapley (GS) algorithm over the standard GS algorithm in achieving true stable matchings under incomplete information. By employing the Extended GS algorithm, our centralized algorithm attains a logarithmic pessimal stable regret dependent on an instance-dependent admissible gap parameter. This algorithm is further adapted to a decentralized setting with a constant regret increase. Finally, we establish a novel centralized instance-dependent lower bound for binary stable regret, elucidating the roles of the admissible gap and super-stable matching in characterizing the complexity of stable matching with bandit feedback.