Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty
This work addresses a foundational challenge in online matching platforms, such as dating or job markets, by providing efficient methods to learn optimal stable matchings under uncertainty, though it appears incremental as it builds on existing stable marriage and bandit frameworks.
The paper tackles the problem of identifying the left-side optimal stable matching in two-sided markets under uncertainty, where preferences are unknown and learned through noisy evaluations, and presents bandit algorithms with theoretical sample complexity results and experimental validation on synthetic data.
We consider a learning problem for the stable marriage model under unknown preferences for the left side of the market. We focus on the centralized case, where at each time step, an online platform matches the agents, and obtains a noisy evaluation reflecting their preferences. Our aim is to quickly identify the stable matching that is left-side optimal, rendering this a pure exploration problem with bandit feedback. We specifically aim to find Probably Correct Optimal Stable Matchings and present several bandit algorithms to do so. Our findings provide a foundational understanding of how to efficiently gather and utilize preference information to identify the optimal stable matching in two-sided markets under uncertainty. An experimental analysis on synthetic data complements theoretical results on sample complexities for the proposed methods.