Probably Correct Optimal Stable Matching under Two-Sided Uncertainty
2026-07-06 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how to find the best stable matchings in markets where both sides (like buyers and sellers) have unknown preferences. They design algorithms that learn these preferences over time by matching pairs and getting noisy feedback about how well they match. Their methods focus on exploring efficiently to identify the best stable matchings with high confidence, even when preferences are partially known or uncertain on both sides. They also extend their approach to reduce regret, meaning they try to minimize bad matches over time, without relying on the smallest difference in match quality.
stable matchingtwo-sided marketspreference learningsemi-bandit feedbackpure explorationpervasive stable matchingsample complexityregret minimizationoptimal matchingelimination algorithms
Authors
Andreas Athanasopoulos, Anne-Marie George, Christos Dimitrakakis
Abstract
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}$.