The Distortion of Stable Matching
2026-02-16 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how to find stable matchings—like pairing students and schools—that are also high quality according to some score, but without knowing exact preferences. They show that traditional methods using only order of preferences can be very bad at this. By either using randomness or asking agents for a small number of exact value queries, they can guarantee much better outcomes. They also explore how many questions need to be asked for near-perfect results and test their ideas on average cases from random preferences.
Stable MatchingDeferred Acceptance AlgorithmCardinal PreferencesOrdinal PreferencesDistortionRandomized AlgorithmsSocial WelfareValue QueriesApproximationAlgorithmic Game Theory
Authors
Aris Filos-Ratsikas, Georgios Kalantzis
Abstract
We initiate the study of distortion in stable matching. Concretely, we aim to design algorithms that have limited access to the agents' cardinal preferences and compute stable matchings of high quality with respect to some aggregate objective, e.g., the social welfare. Our first result is a strong impossibility: the classic Deferred Acceptance (DA) algorithm of Gale and Shapley [1962], as well as any deterministic algorithm that relies solely on ordinal information about the agents' preferences, has unbounded distortion. To circumvent this impossibility, we consider algorithms that either (a) use randomization or (b) perform a small number of value queries to the agents' cardinal preferences. In the former case, we prove that a simple randomized version of the DA algorithm achieves a distortion of $2$, and that this is optimal among all randomized stable matching algorithms. For the latter case, we prove that the same bound of $2$ can be achieved with only $1$ query per agent, and improving upon this bound requires $Ω(\log n)$ queries per agent. We further show that this query bound is asymptotically optimal for any constant approximation: for any $\varepsilon >0$, there exists an algorithm which uses $O(\log n /\varepsilon^2)$ queries, and achieves a distortion of $1+\varepsilon$. Moreover, under natural structural restrictions on the instances of the problem, we provide improved upper bounds on the number of queries required for a $(1+\varepsilon)$-approximation. We complement our main findings above with theoretical and empirical results on the average-case performance of stable matching algorithms, when the preferences of the agents are drawn i.i.d. from a given distribution.