Research map / Learning theory and algorithms / Submodular and game algorithms
Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning
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 arm-proposing deferred acceptance with arm-elimination sampling for bandit learning in two-sided matching markets, giving probability-of-instability and sample-complexity bounds for finding stable matchings.
Problem
Learning preferences in two-sided matching markets via bandit feedback typically optimizes regret but ignores stability of the final matching; the paper asks how to find stable matchings and how many samples are needed.
Approach
Exploit the structure of stable solutions by running the arm-proposing deferred acceptance (DA) algorithm on estimated preferences, and combine it with an action-elimination sampler that only samples arm pairs in the envy set; this improves the probability of stability and reduces sample complexity relative to uniform sampling and agent-proposing DA.
Key results
- Arm-proposing DA is provably at least as likely to be stable as agent-proposing DA under uniqueness consistency, for any sampling algorithm (Theorem on uniqueness consistency and corollary).
- Uniform arm-DA has instability probability O(|ES(m_underline)| exp(-Delta^2 T/(8K))) versus O(|ES(m_overline)| exp(-Delta^2 T/(8K))) for uniform agent-DA; AE arm-DA bound is O(|ES(m_underline)| exp(-Delta^2 T_min/8)).
- AE arm-DA sample complexity is tilde O(|ES(m_underline)| log(1/alpha)/Delta^2), versus tilde O(NK log(1/alpha)/Delta^2) for uniform sampling; experiments with N=K=20 show AE arm-DA improves stability over uniform and CA-UCB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use arm-proposing instead of agent-proposing DA with uniform sampling | Uniform DA · General preference profiles | probability of instability bound: O(|ES(\overline{m})| \gamma) -> O(|ES(\underline{m})|\gamma) | Helped |
| Use arm-proposing DA with Action Elimination instead of uniform sampling | Stable matching learning · General preference profiles | sample complexity: \tilde{O}(\frac{NK}{\Delta^2} \log(\alpha^{-1})) -> \tilde{O}(\frac{|ES(\underline{m})|}{\Delta^2} \log(\alpha^{-1})) | Helped |
| Use AE arm-DA rather than uniform sampling variants or CA-UCB | Stable matching learning · 200 randomized general preference profiles | stability | Helped |
| Use AE arm-DA rather than uniform algorithms | Stable matching learning · 200 randomized SPC preference profiles | regret convergence | Helped |
| Compare AE arm-DA with uniform arm-DA using agent-pessimal regret | Stable matching learning · 200 randomized general preference profiles | agent-pessimal regret convergence | Helped |
| Use arm-proposing DA instead of agent-proposing DA | DA with any sampling algorithm · Preference profiles satisfying uniqueness consistency | probability of stable matching | Helped |
Surprising findings
- Uniform arm-DA appears to outperform AE arm-DA in agent-optimal regret, but this is because AE arm-DA is not designed to reach the agent-optimal stable matching; under agent-pessimal regret AE arm-DA converges faster.
Limitations
- Analysis restricted to strict preferences without ties, incomplete preferences, or non-subgaussian rewards.
- Bounds depend on envy-set size, which can be as large as NK; the worst-case sample-complexity advantage is modest.
- Experiments limited to synthetic random preference profiles with N=K=20.
Experimental setup
Metrics: proportion of stable matchings agent-optimal regret agent-pessimal regret sample complexity
Baselines: uniform agent-DA uniform arm-DA CA-UCB
Builds on: Deferred Acceptance Action Elimination Conflict-Avoiding UCB Explore-then-commit
Closest papers by meaning
- Stable Matching with Ties: Approximation Ratios and Learning (NeurIPS 2025 · similarity 0.91)
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.90)
- Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach (AAAI 2025 · similarity 0.90)
- Competing Bandits in Matching Markets via Super Stability (ICML 2025 · similarity 0.89)
- Improved Analysis for Bandit Learning in Matching Markets (NeurIPS 2024 · similarity 0.89)
- Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints (ICML 2024 · similarity 0.89)
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.