Competing Bandits in Matching Markets via Super Stability
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 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
| Algorithm | Two sided | Market Assumptions | Upper Bound and Metric |
| C-UCB [ 2 ] | NO | Centralized | Pessimal |
| UCB-D3 [ 3 ] | NO | Serial Dictatorship | Unique |
| CA-UCB [ 5 ] | NO | (user, arm) broadcast | Pessimal |
| UCB-D4 [ 4 ] | NO | uniqueness consistency | Unique |
| UCB-DMA [ 21 ] | NO | -reducible | Unique |
| ETGS [ 20 ] | NO | (user, arm) broadcast | Optimal |
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Multi-Armed Bandits
Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.
See all 375 papers