Competing Bandits in Matching Markets via Super Stability
This work addresses matching market efficiency under uncertainty, providing theoretical guarantees for both centralized and decentralized settings, though it is incremental as it builds on prior concepts like super-stability.
The paper tackles the problem of bandit learning in two-sided matching markets with reward uncertainty, showing that the Extended Gale-Shapley algorithm achieves logarithmic pessimal stable regret dependent on an instance-specific gap parameter.
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 `super-stability' 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 instance-dependent 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.