Sisterhood in the Gale-Shapley matching algorithm (Q1953489)

Summary: Lying in order to manipulate the Gale-Shapley matching algorithm has been studied by have an algorithm for finding a stable marriage in a system of preferences. Recently, \textit{L. E. Dubins} and \textit{D. A. Freedman} [Am. Math. Mon. 88, 485--494 (1981; Zbl 0449.92024)] and by \textit{D. Gale} and \textit{M. Sotomayor} [Am. Math. Mon. 92, 261--268 (1985; Zbl 0595.90004)], and was shown to be generally more appealing to the proposed-to side (denoted as the women in \textit{D. Gale} and \textit{L. S. Shapley}'s seminal paper [Am. Math. Mon. 69, 9--15 (1962; Zbl 0109.24403)] than to the proposing side (denoted as men there). It can also be shown that in the case of lying women, for every woman who is better off due to lying, there exists a man who is worse off. In this paper, we show that an even stronger dichotomy between the goals of the sexes holds, namely, if no woman is worse off then no man is better off, while a form of sisterhood between the lying and the ``innocent'' women also holds, namely, if none of the former is worse off, then neither is any of the latter. These results are robust: they generalize to the one-to-many variants of the algorithm and do not require the resulting matching to be stable (i.e. they hold even in out-of-equilibria situations). The machinery we develop in our proofs sheds new light on the structure of lying by women in the Gale-Shapley matching algorithm. This paper is based upon an undergraduate thesis (2007) by the first author.