# Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 64 references that are in the map.
- First posted on arXiv 24 Jan 2023.

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

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [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)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [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)
- [Convergence of Learning Dynamics in Stackelberg Games](https://mlsanity.com/paper/1906.01217/) (2019)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [Regret, stability & fairness in matching markets with bandit learners](https://mlsanity.com/paper/2102.06246/) (2021)
- [Competition, Alignment, and Equilibria in Digital Marketplaces](https://mlsanity.com/paper/2208.14423/) (2022)
- [Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets](https://mlsanity.com/paper/2203.03684/) (2022)
- [Learning Strategies in Decentralized Matching Markets under Uncertain Preferences](https://mlsanity.com/paper/2011.00159/) (2020)
- [Learning in Multi-Stage Decentralized Matching Markets](https://mlsanity.com/paper/2102.06988/) (2021)
- [Thompson Sampling for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2204.12048/) (2022)
- [Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents](https://mlsanity.com/paper/1812.02783/) (2018)
- [Incentive-Aware Recommender Systems in Two-Sided Markets](https://mlsanity.com/paper/2211.15381/) (2022)
- [A Multi-Agent Reinforcement Learning Framework for Off-Policy Evaluation in Two-sided Markets](https://mlsanity.com/paper/2202.10574/) (2022)
- [Designing Approximately Optimal Search on Matching Platforms](https://mlsanity.com/paper/2102.09017/) (2021)
- [A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper Quotas](https://mlsanity.com/paper/2009.14171/) (2020)

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

- [Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning](https://mlsanity.com/paper/2410.04376/) (2024)
- [Advancing Retail Data Science: Comprehensive Evaluation of Synthetic Data](https://mlsanity.com/paper/2406.13130/) (2024)
- [Incentivized Exploration with Stochastic Covariates: A Two-Stage Mechanism Design for Recommender System](https://mlsanity.com/paper/2406.04374/) (2024)
- [Competing Bandits in Decentralized Contextual Matching Markets](https://mlsanity.com/paper/2411.11794/) (2024)
- [An ODE Model for Dynamic Matching in Heterogeneous Networks](https://mlsanity.com/paper/2302.09757/) (2023)

## Abstract (arXiv)

In this paper, we propose a new recommendation algorithm for addressing the problem of two-sided online matching markets with complementary preferences and quota constraints, where agents' preferences are unknown a priori and must be learned from data. The presence of mixed quota and complementary preferences constraints can lead to instability in the matching process, making this problem challenging to solve. To overcome this challenge, we formulate the problem as a bandit learning framework and propose the Multi-agent Multi-type Thompson Sampling (MMTS) algorithm. The algorithm combines the strengths of Thompson Sampling for exploration with a new double matching technique to provide a stable matching outcome. Our theoretical analysis demonstrates the effectiveness of MMTS as it can achieve stability and has a total widetildeO(Q√KmaxT)-Bayesian regret with high probability, which exhibits linearity with respect to the total firm's quota Q, the square root of the maximum size of available type workers √Kmax and time horizon T. In addition, simulation studies also demonstrate MMTS's effectiveness in various settings. We provide code used in our experiments urlhttps://github.com/Likelyt/Double-Matching.