Search papers, labs, and topics across Lattice.
This paper addresses the challenge of finding optimal stable matchings in two-sided markets where preferences are initially unknown and subject to uncertainty. By employing a pure exploration framework, the authors develop elimination-based algorithms that leverage partial preference information to efficiently identify the optimal stable matching with high probability. The study introduces the concept of pervasive stable matching and provides a refined sample-complexity analysis, extending the approach to include regret minimization without relying on the minimum reward gap.
Identifying optimal stable matchings under two-sided uncertainty can be achieved with high probability using innovative elimination-based algorithms that exploit partial preferences.
We study a sequential learning problem for stable matchings in two-sided markets where preferences on both sides are initially unknown. We focus on a centralized setting where an algorithm matches agents at each time step and receives noisy rewards that reflect the preferences of the matched agents, following a semi-bandit feedback structure. We adopt a pure exploration perspective, aiming to efficiently identify the optimal stable matching with high probability. Our work extends prior results by handling \emph{two-sided uncertainty} and by exploiting \emph{partial preference} information. A central ingredient is the notion of \textbf{pervasive stable matching}, which enables the identification of optimal stable matchings under partial preferences. We propose elimination-based algorithms whose stopping criteria exploit the structure of the learned partial preferences, and provide a refined sample-complexity analysis. Beyond pure exploration, we extend our approach to regret minimization and establish regret bounds with respect to the \emph{optimal} stable matching that avoid dependence on the minimum reward gap $螖_{\min}$.
