Gale and Sotomayor (1985) have shown that in the Gale-Shapley matching algorithm (1962), the proposed-to side W (referred to as women there) can strategically force the W-optimal stable matching as the M-optimal one by truncating their preference lists, each woman possibly blacklisting all but one man. As Gusfield and Irving have already noted in 1989, no results are known regarding achieving this feat by means other than such preference-list truncation, i.e. by also permuting preference lists. We answer Gusfield and Irving's open question by providing tight upper bounds on the amount of blacklists and their combined size, that are required by the women to force a given matching as the M-optimal stable matching, or, more generally, as the unique stable matching. Our results show that the coalition of all women can strategically force any matching as the unique stable matching, using preference lists in which at most half of the women have nonempty blacklists, and in which the average blacklist size is less than 1. This allows the women to manipulate the market in a manner that is far more inconspicuous, in a sense, than previously realized. When there are less women than men, we show that in the absence of blacklists for men, the women can force any matching as the unique stable matching without blacklisting anyone, while when there are more women than men, each to-be-unmatched woman may have to blacklist as many as all men. Together, these results shed light on the question of how much, if at all, do given preferences for one side a priori impose limitations on the set of stable matchings under various conditions. All of the results in this paper are constructive, providing efficient algorithms for calculating the desired strategies.
In 2003 there were 8,665 transplants of deceased donor kidneys for the approximately 60,000 patients waiting for such transplants in the United States. While waiting, 3,436 patients died. There were also 6,464 kidney transplants from living donors (Scientific Registry of Transplant Recipients web site). Live donation is an option for kidneys, since healthy people have two and can remain healthy with one. While it is illegal to buy or sell organs, there have started to be kidney exchanges involving two donor–patient pairs such that each (living) donor cannot give a kidney to the intended recipient because of blood type or immunological incompatibility, but each patient can receive a kidney from the other donor. So far these have been rare: as of December 2004, only five exchanges had been performed in the 14 transplant centers in New England. One reason there have been so few kidney exchanges is that there have not been databases of incompatible patient–donor pairs. Incompatible donors were simply sent home. (Databases are now being assembled not only in New England, but also in Ohio and Baltimore.) Lainie Friedman (1997) discussed the possibility of exchange between incompatible patient–donor pairs. Not only have a few such two-way exchanges been performed, but two three-way exchanges (in which the donor kidney from one pair is transplanted into the patient in a second pair, whose donor kidney goes to a third pair, whose donor kidney goes to the first pair) have been performed at Johns Hopkins. There have also been a number of “list exchanges” in which an incompatible patient– donor pair makes a donation to someone on the waiting list for a cadaver kidney, in return for the patient in the pair receiving high priority for a cadaver kidney when one becomes available. Lying in order to manipulate the Gale-Shapley matching algorithm has been studied by Dubins and Freedman (1981) and by Gale and Sotomayor (1985), and was shown to be generally more appealing to the proposed-to side (denoted as the women in Gale and Shapley's seminal paper (1962)) 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.