Research map / Probabilistic and scientific modeling / Bayesian optimization
Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MMTS, a Thompson Sampling bandit algorithm with a two-stage "double matching" (type-quota DA then unrestricted DA) for many-to-one matching with complementary preferences and quota constraints, proving stability and a Bayesian regret bound.
Problem
Two-sided online matching markets where firms have type-specific minimum quotas and total quotas (complementary preferences), and firms' preferences over workers are unknown and must be learned from bandit feedback while keeping matchings stable.
Approach
Combine Thompson Sampling for exploration with a double matching procedure: first a type-specific firm-proposing deferred acceptance to meet minimum type quotas, then a standard DA without type restriction to fill leftover quota, yielding stable matchings and a Bayesian regret bound scaling with the square root of the maximum type size.
Key results
- MMTS achieves Bayesian regret bound of 8Q log(QT) sqrt(K_max T) + NK/Q with probability 1-1/QT, linear in total quota Q and square root in K_max.
- In a 3-firm simulation with M=1, Q=1, N=3, K=3, centralized UCB shows linear regret for firms 1 and 2 and a matching rate of 0.031, while MMTS achieves sublinear regret and a matching rate of 0.741.
- In Example 1 (N=2, M=2, K=5 per type, T=2000), MMTS recovers the firm-optimal stable matching with sublinear regret; firm 1 can achieve negative regret for a type due to non-optimal estimated rankings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace centralized UCB with MMTS Thompson sampling | Centralized matching in the insufficient-exploration simulation · Insufficient-exploration simulation (M=1, Q=1, N=3, K=3) | matching rate: 0.031 -> 0.741 | Helped |
| Replace centralized UCB with MMTS Thompson sampling | Centralized matching in the insufficient-exploration simulation · Insufficient-exploration simulation (M=1, Q=1, N=3, K=3) | firm-optimal stable regret | Helped |
Surprising findings
- Firms can obtain negative regret (matching better-than-optimal workers) in multi-agent settings due to estimation errors, unlike single-agent bandits.
- Centralized UCB can suffer linear firm-optimal stable regret in a simple three-firm example, while Thompson Sampling avoids this.
Limitations
- Assumes unique stable matching / no indifferences for the incentive-compatibility result.
- Stability relies on marginalized (responsive) complementary preferences; couples preferences may yield empty stable set.
- Experiments are small simulations with synthetic data only.
Experimental setup
Metrics: firm-optimal stable regret matching rate Bayesian regret bound
Baselines: centralized UCB
Builds on: Thompson Sampling deferred acceptance centralized UCB matching bandits eluder dimension
Closest papers by meaning
- Improved Analysis for Bandit Learning in Matching Markets (NeurIPS 2024 · similarity 0.90)
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.89)
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.89)
- Competing Bandits in Matching Markets via Super Stability (ICML 2025 · similarity 0.88)
- Stable Matching with Ties: Approximation Ratios and Learning (NeurIPS 2025 · similarity 0.87)
- Stochastic Matching Bandits with Rare Optimization Updates (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.