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. 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(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.

Machine Learning (cs.LG); Information Theory (cs.IT)

arXiv:2506.15926 [cs.LG]

(or arXiv:2506.15926v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2506.15926 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.