--- title: "Manipulating Gale-Shapley Algorithm: Preserving Stability and Remaining Inconspicuous" authors: - "Rohit Vaish" - "Dinesh Garg" doi: "10.24963/ijcai.2017/62" url: "https://ijcai.org/proceedings/2017/62" pdf: "https://ijcai.org/proceedings/2017/0062.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "437-443" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Economic paradigms, auctions and market-based systems" - "Agent-based and Multi-agent Systems: Social Choice Theory" --- # Manipulating Gale-Shapley Algorithm: Preserving Stability and Remaining Inconspicuous Rohit Vaish, Dinesh Garg *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 437-443. DOI: [10.24963/ijcai.2017/62](https://doi.org/10.24963/ijcai.2017/62) ## Abstract We study the problem of manipulation of the men-proposing Gale-Shapley algorithm by a single woman via permutation of her true preference list. Our contribution is threefold: First, we show that the matching induced by an optimal manipulation is stable with respect to the true preferences. Second, we identify a class of optimal manipulations called inconspicuous manipulations which, in addition to preserving stability, are also nearly identical to the true preference list of the manipulator (making the manipulation hard to be detected). Third, for optimal inconspicuous manipulations, we strengthen the stability result by showing that the entire stable lattice of the manipulated instance is contained inside the original lattice.​ ## Full text ## 1 Introduction The theory of two-sided matching has been a cornerstone of market design, inspiring a wide array of applications such as school choice [Abdulkadiro˘glu et al., 2005a; Abdulkadiro˘glu et al., 2005b], entry-level labor markets [Roth and Peranson, 1999], and kidney exchange [Roth et al., 2004]. All of these markets are built around a centralized matching procedure, which solicits the preferences of the participating agents (typically in the form of rank ordered lists) and selects a matching outcome based on these preferences (i.e., decides who gets matched to whom). Arguably the most famous of such procedures is the GaleShapley algorithm [Gale and Shapley, 1962], which takes as input the preferences of two sets of agents over each other (commonly referred to as men and women), and after a sequence of proposal and rejection steps, outputs a matching that is stable in the sense that no pair of agents prefer each other over their assigned partners. Over the years, the notion of stability has emerged as the most significant predictor of a market's long term success-while markets with stable matching procedures have successfully persisted, the unstable ones have failed and are out of use [Roth, 2002]. A frequent concern in such markets, however, is that of strategic behavior by individual agents. Indeed, Roth [1982] has shown that no stable matching mechanism makes it a ## Dinesh Garg IIT Gandhinagar, India dgarg@iitgn.ac.in dominant strategy for every agent to announce their true preferences. This, in particular, means that the Gale-Shapley algorithm is also vulnerable to manipulation. Our interest in this paper is to study the conditions under which the Gale-Shapley matching for the manipulated instance remains stable with respect to the true preferences. It is known from the results of Dubins and Freedman [1981] and Roth [1982] that the proposing side (say, the men) in the algorithm has no incentive to manipulate. Therefore, any strategic behavior must occur on the proposed-to side (i.e., the women). Our starting point, therefore, is the following natural question: Suppose a woman can manipulate by permuting her true preference list while everyone else is truthful. Then, is the resulting Gale-Shapley matching stable with respect to the true preferences? Our first result (Theorem 3) shows that the answer to the above question is YES if the manipulation is optimal. That is, if, by misreporting, the manipulator secures the best possible partner (according to her true preferences), then the resulting Gale-Shapley matching is stable with respect to the true preferences of the agents. This is an encouraging result for both the market designer (who cares about stability with respect to the true preferences) and the manipulator (who cares about finding the optimal partner). We complement this result by showing that sub-optimal manipulations can sometimes lead to instability (Example 1). Besides optimality, the manipulator might also want to avoid being suspected of strategic behavior. Indeed, it is reasonable to expect that the market designer has a coarse idea of the true preferences of the agents, say from past runs of the algorithm or from survey data. In such a setting, strategic misreporting can be easily detected if the announced list of an agent looks significantly different from the market designer's estimate. Our second result (Theorem 4) shows that this is an avoidable concern for the manipulator: For any optimal manipulation, there exists an equivalent inconspicuous manipulation which results in the same matched partner, and can be derived from the true list by promoting only one man (and making no other changes). In other words, an optimal manipulation is nearly indistinguishable from the true list. Our third result (Theorem 5) strengthens the stability implication of Theorem 3 for inconspicuous optimal manipulations. Specifically, we show that every matching (including the Gale-Shapley matching) that is stable with respect to the manipulated instance is also stable with respect to the true preferences. We complement this result by giving an example of a non-inconspicuous optimal manipulation, where a matching that is stable with respect to the manipulated instance is not stable with respect to the true preferences (Example 2). Why study permutation manipulations? By far, the most commonly studied model of manipulation in the stable matching literature has been that of truncation [Gale and Sotomayor, 1985; Roth and Rothblum, 1999; Coles and Shorrer, 2014; Jaramillo et al., 2014]. This model allows the manipulator to remove a tail of her true preference list and report the rest of the list unshuffled. An especially attractive feature of truncation-based manipulations is exhaustiveness, which means that any possible misrepresentation can be replicated or improved by a truncation strategy [Roth and Vate, 1991; Jaramillo et al., 2014]. However, an optimal truncation manipulation by an agent can look very different from her true preference list. In fact, Coles and Shorrer [2014] have shown that when the true preferences of all the other agents are generated uniformly at random, the optimal truncation strategy for the manipulator involves the removal of a large fraction of her true list. This phenomenon is particularly severe for large markets, where the ratio of the length of the reported list to that of the true list goes to zero as the size of the market grows. By contrast, as our results show, an optimal permutation manipulation can be nearly identical to the true list of the manipulator. We consider this feature of permutation manipulations to be an important one, both from a theoretical and a practical standpoint. ## 2 RelatedWork The literature on permutation manipulations of Gale-Shapley algorithm has focused primarily on computational questions [Teo et al., 2001; Kobayashi and Matsui, 2009; Kobayashi and Matsui, 2010; Deng et al., 2015; Gupta et al., 2016]. The earliest result in this direction is by Teo et al. [2001], who gave an O(n3 ) algorithm for computing an optimal permutation manipulation of Gale-Shapley algorithm by a single manipulator. In conjunction with our result (Theorem 3), this means that not only are optimal manipulations stabilitypreserving, but are also efficiently computable. The work of Teo et al. [2001] was generalized to the coalitional manipulation setting by Deng et al. [2015]. For permutation manipulations, they provide an O(n6 ) algorithm for computing a pareto-optimal manipulation for any fixed coalition. Additionally, they show that any such manipulation can be made inconspicuous. There are two important ways in which the work of Deng et al. [2015] differs from ours: First, their model only allows for manipulations that are stabilitypreserving in the first place. On the other hand, we allow the manipulator to pick any permutation (not just a stabilitypreserving one), and identify a class of manipulations that induce stability. Second, their result on the inconspicuousness of coalitional manipulation involves a reduction to the stable roommates problem [Irving, 1985], and uses sophisticated combinatorial structures like rotations and suitor graphs [Kobayashi and Matsui, 2010]. Our proof, on the other hand, is direct and much simpler, which we consider an important contribution of this work. Another set of relevant works is by Kobayashi and Matsui [2009; 2010], who study the following extension version of the manipulation problem: Suppose we are given the preference lists of all men, and a complete/partial matching. The goal is to compute a set (if it exists) of the preference lists of all women such that the men-proposing Gale-Shapley matching contains the given matching. They show that this problem is NP-complete in general (when the given matching is partial), but polynomial time solvable if the given matching is complete. Finally, the recent work of Gupta et al. [2016] studies the question of total stability of a manipulation strategy when all women are strategic individuals and all men are truthful. A manipulation strategy is totally stable if (i) it is stabilitypreserving, and (ii) it constitutes a stable Nash equilibrium, meaning that any unilateral deviation from the strategy is either non-improving or induces instability. It is shown that checking a given strategy for total stability can be done in polynomial time. ## 3 Preliminaries Problem setup An instance 〈M,W,≻〉 of the stable marriage problem consists of a set M of n men, a set W of n women, and a preference profile ≻ = {≻m1 , . . . ,≻mn ,≻w1 , . . . ,≻wn } consisting of the preference lists of all men and women. The preference list of each man m ∈ M, denoted by ≻m, is a strict total order over the set of all women (the preference lists of women are defined analogously). We will use the shorthand w1 ⪰m w2 to denote 'either w1 ≻m w2 or w1 = w2'. We let ≻-w denote the preference lists of all men and women except woman w. Thus, ≻ = {≻-w, ≻w}. Stable matchings A matching refers to a function µ : M ∪W →M ∪W, where µ(m) ∈ W for all m ∈ M, µ(w) ∈ M for all w ∈ W, and µ(m) = w if and only if µ(w) = m. A matching µ admits a blocking pair with respect to ≻ if there is a pair of agents (m, w) such that w≻m µ(m) and m≻w µ(w). A matching µ is stable if it admits no blocking pair with respect to ≻. We let S≻ denote the set of all matchings that are stable with respect to ≻. Gale-Shapley algorithm A matching algorithm takes as input a preference profile and outputs a matching. In this paper, we study the well-known deferred acceptance algorithm [Gale and Shapley, 1962], also known as Gale-Shapley algorithm. In particular, we will focus on the men-proposing version of this algorithm, abbreviated as GS algorithm. We let µ = GS(≻) denote the matching output by the menproposing Gale-Shapley algorithm for the input profile ≻. Briefly, GS algorithm proceeds in rounds, and each round consists of two phases: (i) a proposal phase, where each single man proposes to his favorite woman from among those who haven't rejected him yet, and (ii) a rejection phase, where each woman with multiple proposals in hand rejects all proposals except the one that she likes best. The algorithm terminates when no single agents remain. Gale and Shapley [1962] showed that GS algorithm always terminates with a stable matching. Moreover, this matching is simultaneously the best for all men from among all stable matchings (and, as McVitie and Wilson [1971] later observed, the worst for all women). Theorem 1 recalls these results. Theorem 1 (Men-optimality of GS). Let ≻ be a preference profile, and let µ = GS(≻). Then, µ ∈ S≻. Moreover, for any µ′ ∈ S≻, µ(m) ⪰m µ′ (m) for all m ∈ M and µ′ (w) ⪰w µ(w) for all w ∈W. We let Prop(w,≻) denote the set of all men who propose to w during the run of GS algorithm on ≻. Further, we let Prop(w,≻, i) denote the ith favorite man of w (according to ≻w) in the set Prop(w,≻). Thus, Prop(w,≻, 1) = µ(w) for µ = GS(≻). Stable lattice Given a preference profile ≻ and two matchings µ and µ′ , define the join function µ∨ = µ∨µ′ as follows: for each m ∈ M and w ∈ W , Similarly, define the meet function µ∧ = µ ∧ µ′ for all m ∈ M and w ∈ W as: The following result from [Knuth, 1997], attributed to John Conway, shows that the join and meet of any pair of stable matchings are also stable. Theorem 2 (Lattice of stable matchings). Let ≻ be a preference profile and let µ, µ′ ∈ S≻. Then, µ∨, µ∧ ∈ S≻. Manipulation A matching algorithm is said to be manipulable by an agent w if there exists a pair of preference profiles ≻ and ≻′ , differing only in the preferences of w, such that µ′ (w)≻w µ(w), where µ and µ′ are the matchings before and after the manipulation respectively. The agent w is referred to as the manipulator. In this study, we only consider permutation manipulations, i.e., ≻′w is a permutation of ≻w. Besides, we focus only on the manipulation of GS algorithm, and the manipulator is assumed to be a woman, who knows the preferences of all the other agents. We will often use ≻′ = (≻-w,≻′w ) and µ′ = GS(≻′ ) to denote the manipulated profile (with respect to ≻) and the resulting GS matching respectively. The matching µ′ and the set S≻′ will be referred to as the induced matching and the induced lattice respectively. The set S≻ will be referred to as the original lattice. We will say that a manipulation ≻′w with respect to ≻ is stability-preserving if µ′ ∈ S≻. Optimal manipulation Given a preference profile ≻, an optimal manipulation of GS algorithm by an agent w with respect to a profile ≻ refers to a preference list ≻′w such that (i) µ′ (w)≻w µ(w), and (ii) µ′ (w) ⪰w µ′′ (w) for any other preference list ≻′′w , where µ′ = GS(≻-w,≻′w ) and µ′′ = GS(≻-w, ≻′′w ). Inconspicuous equivalent of a manipulation Given a preference profile ≻, we call ≻′′w an inconspicuous equivalent of a manipulation ≻′w (of GS algorithm by woman w) if (i) ≻′′w can be derived from the true preference list ≻w by moving at most one man, and (ii) µ′′ (w) = µ′ (w), where µ′ = GS(≻′ ) and µ′′ = GS(≻′′ ). ## 4 Main Results Our first result (Theorem 3) shows that optimal manipulation of GS algorithm by a single woman preserves stability. Theorem 3 (Optimal manipulation is stability-preserving). Let ≻′w be an optimal manipulation with respect to ≻ for woman w and let µ′ = GS(≻′ ). Then, µ′ ∈ S≻. This is a positive result, since the stability of the resulting matching is not affected by optimal strategic behaviour of a single agent. Example 1 complements this result by showing that sub-optimal strategic behavior can lead to instability. Example 1. (Sub-optimal manipulation can be unstable) Consider the stable marriage instance shown below. | True preferences of men m1: 2 1 3 4 m2: 3 1 2 4 m3: 1 2 3 4 | True preferences of women w1: 1 2 3 4 w2: 3 1 2 4 w3: 1 2 3 4 w4: 1 2 3 4 | |---------------------------------------------------------------|-----------------------------------------------------------------------------| | w1 manipulates sub-optimally (≻′ ) | w1 manipulates optimally (≻′′ ) | | w1: 2 4 3 1 w2: 3 1 2 4 | | | m4: 1 4 2 3 | | | | w1: 1 4 3 2 | | | w2: 3 1 2 4 | | w3: 1 2 3 4 | w3: 1 2 3 4 | | 1 2 3 | w4: 1 2 3 4 | | w4: 4 | | The top row shows the true preferences of the agents, and the bottom row shows two different manipulations by w1 with respect to ≻. The underlined numbers denote the matched partners of the women under the men-proposing Gale-Shapley algorithm. Notice that the manipulation under ≻′ is sub-optimal for w1 because she matches to a strictly better partner (according to her true preference list ≻w1 ) under ≻′′ . Besides, the matching induced under ≻′ is not stable with respect to the true preferences ≻ since (m1, w1) is a blocking pair. On the other hand, the manipulation under ≻′′ is optimal, and the induced matching is stable with respect to the true preferences. As mentioned earlier in Section 1, it is still possible that the list reported by the manipulator (as part of optimal manipulation) might look very different from her true list. Indeed, for the stable marriage instance in Example 1, notice that except for the most preferred man (namely m1), the optimal manipulation ≻′′w1 by w1 is a complete reversal of her true preference list ≻w. Theorem 4 addresses this concern by showing that any optimal manipulation has an inconspicuous equivalent which results in the same matched partner for the manipulator (thus maintaining optimality) while differing from the true list in the positioning of only one man (thus making the manipulation hard to be detected). Theorem 4 (Inconspicuous equivalent of optimal manipulation). Let ≻′w be an optimal manipulation with respect to ≻ for woman w. Let ≻′′w be another preference list derived from her true list ≻w by promoting the man Prop(w,≻′ , 2) to the position right after Prop(w,≻′ , 1) while making no other changes. Then, ≻′′w is the inconspicuous equivalent of ≻′w , i.e., µ′′ (w) = µ′ (w), where µ′ = GS(≻′ ) and µ′′ = GS(≻′′ ). Going back to Example 1, it can be observed that w1 can achieve her optimal partner (i.e., m1) by reporting the list m1 ≻m4 ≻m2 ≻m3, derived from her true list ≻w by promoting the man m4 and making no other changes. Our final result strengthens the stability implication of Theorem 3 for inconspicuous optimal manipulations. Recall from Theorem 3 that the men-proposing Gale-Shapley matching for the optimally manipulated instance is stable with respect to the true preferences. This result can be alternatively interpreted in the lattice terminology as follows: Theorem 3 shows that the "men-optimal extreme" of the lattice S≻′ always lies inside the original lattice S≻. One might wonder whether the same holds for the rest of the manipulation lattice as well. Theorem 5 shows that this is indeed the case for inconspicuous optimal manipulations. Theorem 5 (Lattice containment result). Let ≻′w be an optimal manipulation with respect to ≻ for woman w, and let ≻′′w be its inconspicuous equivalent (as described in Theorem 4). Then, S≻′′ ⊆ S≻. Example 2 complements Theorem 5 by showing that the implication does not extend to non-inconspicuous optimal manipulations. Example 2. Consider the following stable marriage instance | True preferences of men m1: 2 1 3 4 5 m2: 4 1 5 3 2 m3: 3 1 4 5 2 m4: 1 3 4 5 2 m5: 1 5 4 3 2 | True preferences of women w1: 1 2 3 4 5 w2: 3 2 4 5 1 w3: 4 2 1 5 3 w4: 5 1 4 3 2 w5: 1 2 3 4 5 | |------------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------| | Opt + Non-Inconsp manipulation (≻′ ) w1: 2 5 4 3 1 w2: 3 2 4 5 1 w3: 4 2 1 5 3 w4: 5 1 4 3 2 w5: 1 2 3 4 5 | Opt + Inconsp manipulation (≻′′ ) w1: 1 2 5 3 4 w2: 3 2 4 5 1 w3: 4 2 1 5 3 w4: 5 1 4 3 2 w5: 1 2 3 4 5 | The top row shows the true preferences of the agents, while the bottom row shows two different optimal manipulations ≻′ and ≻′′ for the manipulator w1. The underlined numbers denote the matched partners of the women under the menproposing Gale-Shapley algorithm. First, we briefly describe why ≻′ and ≻′′ are both optimal. Observe that during the run of GS algorithm on the true profile ≻, w1 receives proposals only from m4 and m5. Therefore, any manipulation by w1 must involve swapping the relative ordering of m4 and m5. By rejecting m4 in favor of m5, w1 forces m4 to propose to w3, thereby displacing m3. As a result, m3 is forced to propose to w1. This already is an improvement for w1 over her original partner m4. However, w1 can do even better by pretending to prefer m5 over m3 in the manipulated list. This forces m3 to propose to w4, thereby displacing m2, who in turn is forced to propose to w1, giving her a more preferred match. Notice that w1 can do no better, since rejecting m2 in favor of m5 will not displace m1 in the preference list of w2. Thus, m2 is the optimal partner for w1. Let us now consider the matching φ defined as φ = (m1,w5), (m2,w1), (m3,w2), (m4,w3), (m5,w4). It is easy to verify that φ ∈ S≻′ but φ /∈ S≻′′ and φ /∈ S≻ since (m1, w1) constitutes a blocking pair in each case. Therefore, the stable lattice induced by an optimal manipulation (in this case ≻′ ) need not be completely contained inside the original lattice. ## 5 Proofs of Main Results ## 5.1 Proof of Stability of Optimal Manipulation (Theorem 3) We start by stating a lemma (Lemma 6) that will be useful in the proof of Theorem 3. The lemma states that if a fixed man m proposes to a fixed woman w during the run of GS algorithm, then the same holds when w moves that man up/down in her list while making no other changes. The proof is omitted due to space constraints. (Notice that the lemma applies only to the fixed man m who was moved in the preference list of w, and not to any other man who proposed to w but was not moved.) Lemma 6. Let ≻ and ≻′ be two preference profiles that are completely identical except for the preferences of a fixed woman w. Let ≻′w be derived from ≻w by moving a fixed man m and making no other changes. Then, m ∈ Prop(w, ≻) ⇒ m ∈ Prop(w, ≻′ ). We now provide the proof of Theorem 3. Proof. (of Theorem 3) Suppose, for contradiction, that µ′ /∈ S≻. Then, there must exist a pair (m′ , w′ ) that blocks µ′ with respect to ≻. That is, w′ ≻m′ µ′ (m′ ) and m′ ≻w′ µ′ (w′ ). We first claim that w′ = w. Indeed, by the stability of GS algorithm, we have µ′ ∈ S≻′ . Hence, either µ′ (m′ )≻′m′ w′ or µ′ (w′ )≻′w′ m′ or both. If w′ ̸= w, then by construction ≻′w′ = ≻w′ . Similarly, ≻′m′ = ≻m′ . Therefore, we have that either µ′ (m′ )≻m′ w′ or µ′ (w′ )≻w′ m′ or both, which contradicts the blocking pair condition. Hence, w′ = w. Next, consider a preference list ≻′′w for w derived from ≻′w by promoting the man m′ to the top position and making no other changes. Let ≻′′ = (≻-w,≻′′w ) and µ′′ = GS(≻′′ ). Since w′ = w, we have that m′ ≻w µ′ (w) and w ≻m′ µ′ (m′ ). Moreover, since ≻′m′ = ≻m′ , we have that w≻′m′ µ′ (m′ ). Therefore, during the run of GS algorithm on ≻′ , it must be that m′ proposes to and is rejected by w before he is matched to µ′ (m′ ). That is, m′ ∈ Prop(w, ≻′ ). By applying Lemma 6 with ≻′ and ≻′′ as the old and the new profiles respectively, we get that m′ ∈ Prop(w, ≻′′ ). Since m′ is at the top position in ≻′′w , we must have µ′′ (w) = m′ . This, however, contradicts the optimality of ≻′w , since m′ ≻w µ′ (w) according to the blocking pair condition. ## 5.2 Proof of Inconspicuous Equivalent of Optimal Manipulation (Theorem 4) Our proof of Theorem 4 crucially relies on the swapping lemma (Lemma 7). This lemma provides a complete description of the matched partners that the manipulator can secure by swapping any pair of adjacent men in her preference list. We state the lemma below and omit its proof due to space constraints. It will be convenient to denote the set of non-proposing men by Non-Prop(w,≻). Thus, Non-Prop(w, ≻) = M \ Prop(w, ≻). Lemma 7 (Swapping lemma). Let ≻ and ≻′ be two preference profiles differing only in the preferences of a fixed woman w, and let µ = GS(≻) and µ′ = GS(≻′ ). Let ≻′w be derived from ≻w by swapping the positions of an adjacent pair of men (mi, mj) and making no other changes. Then, - (1) if mi ∈ Non-Prop(w,≻) or mj ∈ Non-Prop(w,≻), then µ′ (w) = µ(w). - (2) if mi,mj /∈ {Prop(w,≻, 1), Prop(w,≻, 2)}, then µ′ (w) = µ(w). - (3) if mi = Prop(w,≻, 2) and mj = Prop(w,≻, 3), then µ′ (w) ∈ {µ(w), mj}. - (4) if mi = Prop(w,≻, 1) and mj = Prop(w,≻, 2), then Prop(w, ≻′ , 2) ∈ {mi, mj}. In words, case (1) shows that swapping two non-proposers or a proposer and a non-proposer cannot give a different matched partner. Case (2) shows the same result for swapping a pair of proposers outside the first and the second best. Case (3) shows that the matched partner either stays the same or becomes worse (according to the true preference list) if the second and third-best proposers are swapped. Finally, case (4) shows that swapping the first and the second-best proposers can lead to at most one new proposal that is better than the old partner (according to the true preference list). Proof. (of Theorem 4) We construct the preference list ≻′′w by starting from ≻′w and performing a sequence of massaging operations on it in order to make it resemble the original preference list ≻w, except for the placement of the man Prop(w, ≻′ , 2). Each such operation involves swapping a pair of adjacent men in the current list. By repeatedly invoking swapping lemma (Lemma 7), we will argue that w continues to receive a proposal from µ′ (w) at each intermediate step, giving us the desired result. We start by describing the construction of the list ≻′′w followed by arguing the correctness of this construction. For notational convenience, we will use p = Prop(w, ≻′ , 1) and q = Prop(w, ≻′ , 2). - (1) Constructing ≻′′w : Starting from ≻′w , we construct a sequence of preference lists ≻(1) w ,≻(2) w , . . . culminating in ≻′′w as follows (refer Figure 1): 2. (a) Promoting q: The list ≻(1) w is obtained from ≻′w by promoting q to the position right after p. Since any men between p and q in the list ≻′w can only be non-proposers, it follows from case (1) of swapping lemma (Lemma 7) that the run of the algorithm on the profile ≻(1) = (≻-w,≻(1) w ) is identical to that on ≻′ . Thus, Prop(w,≻(1) , 1) = p and Prop(w, ≻(1) , 2) = q. Notice that any man above p in the list ≻(1) w must be a non-proposer. 3. (b) Fixing the part of the list above p: Our goal in this step will be to make the part of the list ≻(1) w above and including p resemble that in the list ≻w. We achieve this by replacing the set of non-proposers above p in ≻(1) w with the set of men above p in the true list ≻w. It is easy to see that no man in the latter set can be a proposer to w at any stage, or else the optimality of the manipulation is violated. Thus, our task involves shuffling around a set of non-proposers in the list ≻(1) w , which, by case (1) of swapping lemma (Lemma 7), does not affect the run of GS algorithm. We call the resulting preference list ≻(2) w . It is easy to verify that after this step, the new list ≻(2) w resembles the true preference list ≻w for all positions above and including p, and that Prop(w,≻(2) , 1) = p and Prop(w,≻(2) , 2) = q, where ≻(2) = (≻-w, ≻(2) w ). - (c) Fixing the part of the list below q: The final step in our construction involves a sequence of preference lists {≻(3) w ,≻(4) w , . . . }. The list ≻(k+1) w is derived from ≻(k) w by swapping a pair of adjacent men (mi,mj) in ≻(k) w such that (i) Prop(w,≻(k) , 2)≻(k) w mi and Prop(w, ≻(k) , 2) ≻(k) w mj, and (ii) mi ≻wmj and mj ≻(k) w mi. In words, each new list in the sequence is derived from the previous list by swapping a pair of adjacent men that are (i) both positioned below the second-favorite proposer according to the previous list, and (ii) are incorrectly ordered with respect to the true preference list ≻w. No other changes are made. Notice that this sequence of preference lists must be finite since there can only be a finite number of pairs of men that are incorrectly ordered with respect to the true list. Let ≻(ℓ) w be the final list in this sequence, and let ≻(k) = (≻-w, ≻(k) w ) and µ(k) = GS(≻(k) ) denote the preference profile and the corresponding GS matching at each step. This finishes the construction of the sequence of preference lists. - (2) Correctness: We will now show that Theorem 4 holds for Figure 1: The sequence of preference lists constructed in the proof of Theorem 4. Here, p = Prop(w, ≻′ , 1) = µ′ (w) and q = Prop(w, ≻′ , 2). ![Image](https://ijcai.org/proceedings/2017/fulltext/62/image_000000_fc975777b74d2d51c09cab2cd973a0ed40fbe333c3dc68dbe7702ea11431b654.png) ≻′′w = ≻(ℓ) . That is, we will show that: - (a) The list ≻(ℓ) w can be obtained from the true list ≻w by promoting q to the position right after p while making no other changes, and Case (a) follows easily from the above construction. Indeed, the steps (1a) and (1b) ensure that ≻(ℓ) w resembles ≻w for all positions above and including p, while step (1c) incrementally corrects for pairs that are out of order with respect to ≻w, thus eventually terminating with a list ≻(ℓ) w that is identical to ≻w except for the positioning of the man q. We prove case (b) by induction. The base case consists of showing that µ(3) (w) = p. Indeed, let (mi,mj) be the pair of adjacent men in ≻(2) w that are swapped in ≻(3) w . By construction, we know that mi,mj /∈ {Prop(w,≻(2) , 1), Prop(w,≻(2) , 2)}. Therefore, from cases (1) and (2) of swapping lemma (Lemma 7), we have that µ(3) (w) = p. We now proceed to the induction hypothesis. That is, we now assume that µ(k) (w) = p for all 3 < k ≤ K, and show that µ(K+1) (w) = p. As before, let (mi,mj) be the pair of adjacent men that are swapped in ≻(K) w to obtain ≻(K+1) w . By construction, we have that mi,mj /∈ {Prop(w,≻(K) , 1), Prop(w,≻(K) , 2)}. Therefore, from cases (1) and (2) of swapping lemma (Lemma 7), we have that µ(K+1) (w) = µ(K) (w). Finally, using the induction hypothesis, we get that µ(K+1) (w) = p. Hence, by induction, we have that µ(ℓ) (w) = p. This finishes the proof of case (b) and, as a result, of Theorem 4. ## 5.3 Proof of Lattice Containment (Theorem 5) Proof. (of Theorem 5) Let us assume, for contradiction, that there exists a matching φ such that φ ∈ S≻′′ \ S≻. Then, there must exist a pair (m, w) that blocks φ with respect to ≻ (it follows from the argument in the proof of Theorem 3 that one of the blocking agents must be the manipulator w). Thus, m≻w φ(w) and w ≻m φ(m). Consider the set S≻′′ . Since φ ∈ S≻′′ , it follows from Theorem 2 that φ(w) ⪰′′w µ′′ (w), where µ′′ = GS(≻′′ ). Moreover, from Theorem 4, we know that µ′ (w) = µ′′ (w) for µ′ = GS(≻′ ). Therefore, we also have that φ(w) ⪰′′w µ′ (w). By inconspicuousness of ≻′′w , we have that φ(w) ⪰w µ′ (w). Combining this with the blocking pair condition above, we get that m≻w φ(w) ⪰w µ′ (w). Once again, by inconspicuousness of ≻′′w , we have that m≻′′w φ(w). We also know that ≻m = ≻′′m by construction. Therefore, from the blocking pair condition, we have that w≻′′m φ(m). Combining this with the condition m≻′′w φ(w), we get that the pair (m,w) blocks φ with respect to ≻′′ , which contradicts the assumption φ ∈ S≻′′ . Therefore, S≻′′ ⊆ S≻. ## 6 Concluding Remarks We studied the problem of manipulation of Gale-Shapley algorithm by a single agent, and identified a class of manipulations called inconspicuous manipulations which are optimal, stability-preserving, and nearly identical to the manipulator's true preference list. Our work motivates several directions for future work. First, extensions of the current model to a setting with several self-interested manipulators (seeking an equilibrium strategy) will be interesting to study. It will also be interesting to find out if our techniques-in particular, swapping lemma-can lead to faster algorithms for optimal manipulation by a single agent or a coalition of agents; the current best algorithms for these problems are O(n3 ) [Teo et al., 2001] and O(n6 ) [Deng et al., 2015] respectively. Finally, it would be of interest to conduct a similar analysis for other stable matching algorithms, such as ones that compute minimum regret [Knuth, 1997; Gusfield, 1987], egalitarian [Irving et al., 1987; Teo and Sethuraman, 1998] or median [Teo and Sethuraman, 1998] stable matchings. ## Acknowledgements We thank the anonymous reviewers for their helpful comments. Part of this work was done at IBM Research, Bangalore, India. RV thanks Microsoft Research for a travel grant to present this work at IJCAI 2017. ## References 1. [Abdulkadiroglu et al., 2005a] Atila Abdulkadiroglu, Parag A Pathak, and Alvin E Roth. The New York City High School Match. American Economic Review, pages 364-367, 2005. 2. [Abdulkadiroglu et al., 2005b] Atila Abdulkadiroglu, Parag A Pathak, Alvin E Roth, and Tayfun Sönmez. The Boston Public School Match. American Economic Review, pages 368-371, 2005. 3. [Coles and Shorrer, 2014] Peter Coles and Ran Shorrer. Op- timal Truncation in Matching Markets. Games and Eco- nomic Behavior, 87:591-615, 2014. 4. [Deng et al., 2015] Yuan Deng, Weiran Shen, and Pingzhong Tang. Coalition Manipulations of the Gale-Shapley Algo- rithm. arXiv preprint arXiv:1502.07823, 2015. 5. [Dubins and Freedman, 1981] Lester E Dubins and David A Freedman. Machiavelli and the Gale-Shapley Algo- rithm. The American Mathematical Monthly, 88(7):485- 494, 1981. 6. [Gale and Shapley, 1962] David Gale and Lloyd S Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1):9-15, 1962. 7. [Gale and Sotomayor, 1985] David Gale and Marilda So- tomayor. Ms. Machiavelli and the Stable Matching Prob- lem. The American Mathematical Monthly, 92(4):261- 268, 1985. 8. [Gupta et al., 2016] Sushmita Gupta, Kazuo Iwama, and Shuichi Miyazaki. Total Stability in Stable Matching Games. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), pages 23:1-23:12, 2016. 9. [Gusfield, 1987] Dan Gusfield. Three Fast Algorithms for Four Problems in Stable Marriage. SIAM Journal on Com- puting, 16(1):111-128, 1987. 10. [Irving et al., 1987] Robert W Irving, Paul Leather, and Dan Gusfield. An Efficient Algorithm for the "Optimal" Stable Marriage. Journal of the ACM (JACM), 34(3):532-543, 1987. 11. [Irving, 1985] Robert W Irving. An Efficient Algorithm for the "Stable Roommates" Problem. Journal of Algorithms, 6(4):577-595, 1985. 12. [Jaramillo et al., 2014] Paula Jaramillo, C ¸aǧatay Kayı, and Flip Klijn. On the Exhaustiveness of Truncation and Drop- ping Strategies in Many-to-Many Matching Markets. So- cial Choice and Welfare, 42(4):793-811, 2014. 13. [Knuth, 1997] Donald Ervin Knuth. Stable Marriage and Its Relation to Other Combinatorial Problems: An Intro- duction to the Mathematical Analysis of Algorithms, vol- ume 10. American Mathematical Soc., 1997. 14. [Kobayashi and Matsui, 2009] Hirotatsu Kobayashi and To- momi Matsui. Successful Manipulation in Stable Marriage Model with Complete Preference Lists. IEICE TRANSAC- TIONS on Information and Systems, 92(2):116-119, 2009. 15. [Kobayashi and Matsui, 2010] Hirotatsu Kobayashi and To- momi Matsui. Cheating Strategies for the Gale-Shapley Algorithm with Complete Preference Lists. Algorithmica, 58(1):151-169, 2010. 16. [McVitie and Wilson, 1971] David G McVitie and Leslie B Wilson. The Stable Marriage Problem. Communications of the ACM, 14(7):486-490, 1971. 17. [Roth and Peranson, 1999] Alvin E Roth and Elliott Peran- son. The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic De- sign. American Economic Review, 89(4):748-780, 1999. 18. [Roth and Rothblum, 1999] Alvin E Roth and Uriel G Roth- blum. Truncation Strategies in Matching Markets- In Search of Advice for Participants. Econometrica, 67(1):21-43, 1999. 19. [Roth and Vate, 1991] Alvin E Roth and John H Vande Vate. Incentives in Two-Sided Matching with Random Stable Mechanisms. Economic theory, 1(1):31-44, 1991. 20. [Roth et al., 2004] Alvin E Roth, Tayfun Sönmez, and M Utku Ünver. Kidney Exchange. The Quarterly Jour- nal of Economics, 119(2):457-488, 2004. 21. [Roth, 1982] Alvin E Roth. The Economics of Matching: Stability and Incentives. Mathematics of operations re- search, 7(4):617-628, 1982. 22. [Roth, 2002] Alvin E Roth. The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics. Econometrica, 70(4):1341- 1378, 2002. 23. [Teo and Sethuraman, 1998] Chung-Piaw Teo and Jay Sethuraman. The Geometry of Fractional Stable Match- ings and its Applications. Mathematics of Operations Research, 23(4):874-891, 1998. 24. [Teo et al., 2001] Chung-Piaw Teo, Jay Sethuraman, and Wee-Peng Tan. Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications. Management Science, 47(9):1252-1267, 2001.