Competing Bandits in Matching Markets via Super Stability
Abstract
We study bandit learning in matching markets with two-sided reward uncertainty, extending prior research primarily focused on single-sided uncertainty. Leveraging the concept of 'superstability' from Irving (1994), we demonstrate the advantage of the Extended Gale-Shapley (GS) algorithm over the standard GS algorithm in achieving true stable matchings under incomplete information. By employing the Extended GS algorithm, our centralized algorithm attains a logarithmic pessimal stable regret dependent on an instance-dependent admissible gap parameter. This algorithm is further adapted to a decentralized setting with a constant regret increase. Finally, we establish a novel centralized instancedependent lower bound for binary stable regret, elucidating the roles of the admissible gap and super-stable matching in characterizing the complexity of stable matching with bandit feedback.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Decentralized Bandits without Global Clock for Dynamic Matching Market cites Beyond log2(T) regret for decentralized bandits in matching markets
- Decentralized Bandits without Global Clock for Dynamic Matching Market cites Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility cites Beyond log2(T) regret for decentralized bandits in matching markets
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility cites Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
- Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets cites Learning Equilibria in Matching Markets from Bandit Feedback
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning cites Beyond log2(T) regret for decentralized bandits in matching markets
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning cites Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning cites Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning cites Learning Equilibria in Matching Markets from Bandit Feedback
- Learning Equilibria in Matching Markets from Bandit Feedback cites Beyond log2(T) regret for decentralized bandits in matching markets
Cited by top-tier papers1
Builds on8
- Learning Equilibria in Matching Markets from Bandit FeedbackMeena Jagadeesan, Alexander Wei, Yixin Wang, Michael I. Jordan et al.NeurIPS 2021 · 52 citations
- Beyond log2(T) regret for decentralized bandits in matching marketsSoumya Basu, Karthik Abinav Sankararaman, Abishek SankararamanICML 2021 · 45 citations
- Decentralized, Communication- and Coordination-free Learning in Structured Matching MarketsChinmay Maheshwari, Shankar Sastry, Eric MazumdarNeurIPS 2022 · 22 citations
- Putting Gale & Shapley to Work: Guaranteeing Stability Through LearningHadi Hosseini, Sanjukta Roy, Duohan ZhangNeurIPS 2024 · 14 citations
- Improved Bandits in Many-to-One Matching Markets with Incentive CompatibilityFang Kong, Shuai LiAAAI 2024 · 10 citations
Related papers
- Bandit Learning in Matching Markets Robust to Adversarial CorruptionsZheshun Wu, Jinhang Zuo, Zenglin Xu, Fang KongICLR 2026
- Improved Analysis for Bandit Learning in Matching MarketsFang Kong, Zilong Wang, Shuai LiNeurIPS 2024 · 8 citations
- Adaptive Bandit Algorithms for Contextual Matching MarketsShiyun Lin, Simon Mauras, Vianney Perchet, Nadav MerlisICML 2026
- Bandit Learning in Matching Markets with IndifferenceFang Kong, Jingqi Tang, Mingzhu Li, Pinyan Lu et al.ICLR 2025
- Stable Matching with Ties: Approximation Ratios and LearningShiyun Lin, Simon Mauras, Nadav Merlis, Vianney PerchetNeurIPS 2025 · 4 citations
