Research map / Bandits and online learning / Online convex optimization and games
Competing Bandits in Matching Markets via Super Stability
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 centralized and decentralized bandit algorithms for two-sided matching markets that use Extended Gale-Shapley to find super-stable matchings under UCB-LCB partial rankings, giving logarithmic pessimal stable regret, plus a binary stable regret lower bound.
Problem
Learning a stable matching in two-sided matching markets where both users and arms must learn their preferences from noisy bandit feedback, with regret measured against stable matchings.
Approach
Replace standard Gale-Shapley with Extended Gale-Shapley on UCB-LCB partial rankings: a super-stable matching under a partial rank is guaranteed stable under any compatible full rank, so when one is found it incurs no stable regret; otherwise explore round-robin. Introduces the admissible gap, which can be much larger than the minimum gap.
Key results
- Centralized algorithm achieves pessimal stable regret O(K log(T)/Δ_A^2) for each user and arm, improving on O(K log(T)/Δ_min^2) of ETGS-type methods since Δ_A ≥ Δ_min.
- Decentralized version using two shared binary flags incurs only an additional O(N^2) regret independent of T.
- In simulations with N=K=8, the Extended-GS algorithm outperforms centralized ETGS in cumulative pessimal stable regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Extended Gale-Shapley instead of Gale-Shapley in the centralized matching bandit | Centralized two-sided matching bandit · Random matching-market instances | pessimal stable regret | Helped |
Surprising findings
- The ratio Δ_A/Δ_min can be arbitrarily large (1/ε − 2), showing admissible gap can far exceed minimum gap.
Limitations
- Uses round-robin exploration which is suboptimal; tight regret bound remains open.
- Lower bound is not tight and the general-instance characterization is computationally hard to simplify.
- Decentralized algorithm relies on two shared flags, more restrictive than (user, arm) broadcast.
Experimental setup
Metrics: pessimal stable regret binary stable regret
Baselines: Centralized ETGS (Kong et al.)
Builds on: Gale-Shapley algorithm Extended Gale-Shapley (Irving 1994) ETGS (Kong et al.) OSSB
Closest papers by meaning
- Improved Analysis for Bandit Learning in Matching Markets (NeurIPS 2024 · similarity 0.93)
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.92)
- Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach (AAAI 2025 · similarity 0.90)
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.89)
- Stable Matching with Ties: Approximation Ratios and Learning (NeurIPS 2025 · similarity 0.89)
- Stochastic Matching Bandits with Rare Optimization Updates (NeurIPS 2026 · 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.