# Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 40 references that are in the map.
- First posted on arXiv 6 Jun 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [Improved Path-length Regret Bounds for Bandits](https://mlsanity.com/paper/1901.10604/) (2019)
- [Multiplayer bandits without observing collision information](https://mlsanity.com/paper/1808.08416/) (2018)
- [Matching while Learning](https://mlsanity.com/paper/1603.04549/) (2016)
- [Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions](https://mlsanity.com/paper/2011.03896/) (2020)
- [Thompson Sampling for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2204.12048/) (2022)
- [Competing Bandits: Learning under Competition](https://mlsanity.com/paper/1702.08533/) (2017)

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

- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [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)
- [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)
- [Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach](https://mlsanity.com/paper/2407.21294/) (2024)
- [Bandit Learning in Matching Markets: Utilitarian and Rawlsian Perspectives](https://mlsanity.com/paper/2412.00301/) (2024)
- [Competing Bandits in Decentralized Contextual Matching Markets](https://mlsanity.com/paper/2411.11794/) (2024)
- [Optimal Analysis for Bandit Learning in Matching Markets with Serial Dictatorship](https://mlsanity.com/paper/2512.06758/) (2025)
- [Regret Analysis of Sleeping Competing Bandits](https://mlsanity.com/paper/2603.19700/) (2026)

## Abstract (arXiv)

We study the problem of online learning in competitive settings in the context of two-sided matching markets. In particular, one side of the market, the agents, must learn about their preferences over the other side, the firms, through repeated interaction while competing with other agents for successful matches. We propose a class of decentralized, communication- and coordination-free algorithms that agents can use to reach to their stable match in structured matching markets. In contrast to prior works, the proposed algorithms make decisions based solely on an agent's own history of play and requires no foreknowledge of the firms' preferences. Our algorithms are constructed by splitting up the statistical problem of learning one's preferences, from noisy observations, from the problem of competing for firms. We show that under realistic structural assumptions on the underlying preferences of the agents and firms, the proposed algorithms incur a regret which grows at most logarithmically in the time horizon. Our results show that, in the case of matching markets, competition need not drastically affect the performance of decentralized, communication and coordination free online learning algorithms.