cs.LGJun 19, 2025

Competing Bandits in Matching Markets via Super Stability

Authors: Soumya Basu

Organizations: Google, New York

Abstract

We study bandit learning in matching markets with two-sided reward uncertainty, extending prior research primarily focused on single-sided uncertainty. Building on Irving's (1994) concept of super-stability and the partial-order proposal algorithm of Cseh and Juhos (2021), we use a simultaneous Extended Gale-Shapley procedure to certify stable matchings from incomplete preference information. By employing this procedure, our centralized algorithm attains logarithmic pessimal stable regret dependent on an instance-dependent admissible gap parameter. This algorithm is further adapted to a decentralized setting with a time-independent additive O(N3K)O(N^3K) regret increase under the stated shared-flag communication model. Finally, we establish a centralized instance-dependent lower bound for binary stable regret on strict interior Bernoulli instances, elucidating the roles of admissible partial ranks and super-stable matching in characterizing the complexity of stable matching with bandit feedback.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Probably Correct Optimal Stable Matching under Two-Sided Uncertainty

    Jul 6, 2026Andreas Athanasopoulos, Anne-Marie George, Christos DimitrakakisMulti-Armed BanditsPreference Learning

  2. Adaptive Bandit Algorithms for Contextual Matching Markets

    May 27, 2026Shiyun Lin, Simon Mauras, Vianney Perchet +1Multi-Armed BanditsContextual Bandits

  3. Learn to Match: Two-Sided Matching with Temporally Extended Feedback

    Jun 4, 2026Haijing Zong, Yancheng Liang, Boyang Zhou +1Multi-Agent Reinforcement Learning