论文库

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. Following the recent agenda of Amanatidis et al. (2021), we seek to find the best possible tradeoffs between the distortion of an algorithm and the amount of information elicited via means of cardinal value queries. As a warm-up, we show that purely ordinal algorithms (i.e., algorithms that only use the preference rankings of the agents but no value queries), including the classic Deferred Acceptance (DA) algorithm of Gale and Shapley (1962), have unlimited distortion. Despite this strong impossibility, we observe that a simple randomized version of the DA algorithm achieves a distortion of $2$, and show that this is in fact optimal among all randomized stable matching algorithms. We then consider algorithms that also use value queries on top of the ordinal ranking information. Again, it is easy to see that the same bound of $2$ can be achieved with only $1$ value query per agent, and thus we focus on the question of improving upon this bound. To this end, we provide two strong lower bounds, namely that any stable matching algorithm requires $Ω(n)$ non-adaptive value queries or $Ω(\log n)$ adaptive value queries per agent to achieve a distortion smaller than $2$, where $n$ is the number of agents. Finally, we show an asymptotically tight bound of $Θ(\log (1+n\varepsilon)/\varepsilon)$ on the number of queries that are necessary and sufficient to achieve near-optimal distortion, i.e., a distortion of $1+\varepsilon$, for any $\varepsilon >0$.