# coalition_manipulation_of_galeshapley_algorithm__8909bbee.pdf

Coalition Manipulation of Gale-Shapley Algorithm

Yuan Deng Department of Computer Science Duke University Durham, NC 27708, USA ericdy@cs.duke.edu

It is well-known that the Gale-Shapley algorithm is not truthful for all agents. Previous studies in this category concentrate on manipulations using incomplete preference lists by a single woman and by the set of all women. Little is known about manipulations by a subset of women. In this paper, we consider manipulations by any subset of women with arbitrary preferences. We show that a strong Nash equilibrium of the induced manipulation game always exists among the manipulators and the equilibrium outcome is unique and Pareto-dominant. In addition, the set of matchings achievable by manipulations has a lattice structure. We also examine the super-strong Nash equilibrium in the end.

Introduction The stable matching theory was introduced by Gale and Shapley (1962). Since then, stability has been a central concept in matching market design. The area has attracted intensive research attention, putting theory into practice through a large amount of important applications, such as college admissions and school matchings (Abdulkadiroglu and S onmez 2003; Abdulkadiro glu, Pathak, and Roth 2005; Gale and Shapley 1962), hospitals-residents matchings (Irving and Manlove 2009; Irving, Manlove, and Scott 2000; Roth 1996), kidney exchange programs (Abraham, Blum, and Sandholm 2007; Roth, S onmez, and Unver 2004; 2005; Liu, Tang, and Fang 2014), and water right trading (Liu et al. 2016; Zhan et al. 2017). We study the standard stable matching model, where two set of agents, namely men and women, have preferences over each other. A matching is a one-to-one correspondence between the two sets. A pair of a man and a woman, who are not matched together, but prefer each other to their designated partner, is said to be a blocking pair. A matching is called stable if there exists no blocking pair. The Gale-Shapley algorithm, which was ﬁrst proposed by Gale and Shapley (1962), takes as input the preference lists of all agents, and computes a stable matching in O(n2) time. The algorithm simulates the procedure of men proposing to

This work was supported in part by the National Natural Science Foundation of China Grant 61561146398 and a China Youth 1000-talent program. Copyright c 2018, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

women. At each round of the procedure, each man proposes to his favorite woman among those who have not rejected him yet. Then each woman rejects all men but her favorite one. The algorithm terminates when no man can make any proposal. It is shown that the matching computed by the Gale Shapley algorithm is stable and the algorithm is guaranteed to terminate for each legal input, which immediately implies that every instance of the stable matching problem has a stable matching. There are many interesting structural results in the literature of stable matching theory. For example, among all stable matchings, the matching computed by the Gale Shapley algorithm is preferred by all men to other matchings, and thus is called the M-optimal (W-pessimal) matching. Similarly, the W-optimal (M-pessimal) matching can be found by switching the roles of men and women. In fact, all men and women have opposite preferences over the set of stable matchings, i.e., for every two stable matchings μ1 and μ2, all men prefer μ1 to μ2, if and only if all women prefer μ2 to μ1. Moreover, the set of all stable matchings forms a lattice structure.

Incentive Issue

However, the Gale-Shapley algorithm suffers from the incentive issue, i.e., some agents have incentive to misreport their preference lists. Although it is shown that the Gale Shapley algorithm is group strategy-proof for all men (Dubins and Freedman 1981)1, when the algorithm is adopted, the women may have incentives to misreport their preferences. Moreover, a well-known impossibility result by Roth (1982) states that no stable matching algorithm is truthful for all agents. Gale and Sotomayor (1985) shows that if all women truncate their preference lists properly, the Gale-Shapley algorithm will output a matching that matches each of them to their partner in the W-optimal matching. Teo, Sethuraman, and Tan (2001) provide a polynomial time algorithm to ﬁnd the optimal single-agent truncation manipulation. However,

1Precisely, group strategy-proof means no coalition manipulation can make all men in the coalition strictly better off, in this context. If considering the case where no man is worse off and at least one man is strictly better off, the Gale-Shapley algorithm is not group strategy-proof (Huang 2006).

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

Weiran Shen, Pingzhong Tang Institute for Interdisciplinary Information Sciences Tsinghua University Beijing, China {emersonswr,kenshinping}@gmail.com

little is known when only a subset of players can misreport their preference lists. This paper is directly motivated by the recent reform of the college admissions process in China. In China, all students are required to take the National College Entrance Exam before applying to the universities. The applications are settled by the Ministry of Education using the Gale Shapley algorithm. However, besides the entrance exam, the Ministry also has the independent admission program (aka the university initiative admission plan). This program allows the universities to conduct independent exams to determine their own ordering of the students. Starting from 2010, these universities began to form leagues and determine their orderings together. Such leagues are widely believed to be beneﬁcial to their members, since they can cooperatively manipulate the admission results. However, these universities are also faced with the problem of competition, since they target for a similar set of students. Such leagues are urged to dissolve by the Ministry for the belief of unfairness.

Our Results

We analyze the manipulation problem in the stable matching problem, where agents can report a preference list over any subset of the other sex. Contrary to most existing works, we allow any subset of women to be the manipulators. We show that a strong Nash equilibrium (i.e., no subset of manipulators can deviate and get strictly better off) always exists for any subset of women. Moreover, in the strong Nash equilibrium, each manipulator removes every man below her Woptimal partner on her list and in the induced matching, all manipulators can be matched to their W-optimal partners. This result generalizes the results by Teo, Sethuraman, and Tan (2001) and Gale and Sotomayor (1985), which consider manipulations by a single woman and the set of all women, respectively. Moreover, the equilibrium outcome is unique and Pareto-dominant for all manipulators, i.e., all manipulators reach a consensus on a single manipulation proﬁle. Furthermore, the set of all stable matchings attainable from general manipulations forms a join-semilattice. Finally, we show how to check whether such an unique strong Nash equilibrium is a super-strong Nash equilibrium.

Related Works

Knuth, Motwani, and Pittel (1990) show that the number of different partner that a woman can have in all stable matchings is between 1

2 ϵ ln n and (1 + ϵ) ln n, where n is the number of men and ϵ is a positive constant. Jaramillo, Kayı, and Klijn (2014) study possible manipulations by the women in a many-to-many setting. They consider the socalled dropping strategies, where women are allowed to strategically remove some men in their true preference lists but cannot shufﬂe their lists. They give an exhaustiveness of this kind of strategies, i.e., for any given stable matching, there exists some dropping strategy that can replicate or improve the matching. Gonczarowski (2014) study group manipulations by all women when the Gale-Shapley algorithm is applied. They also consider dropping strategies and give a tight upper bound on the number of men that must be

removed in order for the W-optimal matching to be the ﬁnal output. Dworczak (2016) put forward a new matching algorithm to ﬁnd stable matchings, where all agents are allowed to make proposals. Their algorithm is a natural generalization of the Gale-Shapley algorithm and they also characterize the set of stable matchings by showing that a matching is stable if and only if it is a possible output of their algorithm. Teo, Sethuraman, and Tan (2001) study a different type of manipulation, where a woman can only permute her true preference list2. This is a natural constraint when all agents are only allowed to report a complete preference list. They focus on the case where there is only a single manipulator and give an algorithm to ﬁnd the optimal manipulation that runs in polynomial time. Gupta et al. (2015) extends the algorithm to the so-called P-stable (stable w.r.t preferences P) Nash equilibrium setting. With the impossibility result by Roth, it is clear that there always exist some agents who have the incentive to manipulate the matching result, no matter what stable matching algorithm is applied. Nevertheless, Pini et al. (2009) design a stable matching mechanism and prove that it is computationally hard to ﬁnd a manipulation, even for a single manipulator.

Preliminaries

In the standard stable matching problem, there are two sets of agents: the men (denoted by M) and the women (denoted by W). A preference proﬁle P is the collection of the preference lists of all agents. The preference list P(m) of a man m M is a strict total order m over a subset of W, where w1 m w2 denotes that m prefers w1 to w2. Similarly, the preference list P(w) of a woman w W is a strict total order w over a subset of M. We will use P m and P w to explicitly refer to the preference lists of m and w in proﬁle P, if multiple preference proﬁles are considered. However, for simplicity, we always use m and m to denote the true preferences of m and w. We slightly abuse notation and use P(X) to denote the preference proﬁle for a set of agents X M W. A matching between men and women is a function μ : M W M W, that maps each agent to his or her partner in the matching. For example, μ(m) = w means that m is matched to w. Thus μ(m) = w if and only if μ(w) = m. In any matching, a man should be matched with a woman and vice versa. However, we also write μ(m) = m or μ(w) = w if m or w is unmatched in μ. We say μ1 W μ2, if for all w W, μ1(w) w μ2(w). A matching is individually rational if no one is matched to someone who is absent from his or her preference list. A pair of man and woman (m, w) is said to block a matching μ, if they are not matched together, yet prefer each other to their partners in μ. Such a pair is also called a blocking pair. A matching is stable if it is individually rational and has no blocking pairs.

2This type of manipulations is widely studied in the social choice domain, e.g. (Gibbard 1973).

Recall that the Gale-Shapley algorithm is not truthful for the women (Dubins and Freedman 1981). Let L W be the set of manipulators and N = W \ L be the set of nonmanipulators. We deﬁne a manipulation game between the manipulators. Deﬁnition 1 (Manipulation game). Given the true preference proﬁle of all agents, and a set L W of manipulators, a manipulation game is a tuple (L, AL), where: 1. L W is the set of manipulators; 2. AL = i L Ai is the set of all possible reported preference proﬁles. Remark 1. Note that in the above deﬁnition, all agents in M N are not players. Thus their preference proﬁle is always their true preference proﬁle. The set of all possible preferences Ai depends on different manipulation types which will be deﬁned later, and we only consider the case where all manipulators use the same type of manipulations. The outcome of the manipulation game (also called induced matching in this paper) is the matching resulted from the Gale-Shapley algorithm with respect to the reported preference proﬁles. A manipulator s preference over all possible outcomes of this game is naturally her true preference in P. We now deﬁne two types of manipulations, which determines the elements in AL. Deﬁnition 2 (General manipulation). Let Ob be the set of strict total orders over all possible subsets of M. The manipulators use general manipulations if Ai = Ob, i L. Deﬁnition 3 (Truncation manipulation). Let (m1, m2, . . . , mk) be a woman i s true preference list. In truncation manipulations, Ai = {(m1, m2, . . . , mj) | j k}, i L. It is clear that the truncation manipulation is a special case of the general manipulation. The overall preference proﬁle that is taken as input in the Gale-Shapley algorithm is P = (P(M), P(N), P(L)). Denote by S(P) the set of all stable matchings under proﬁle P. Moreover, let SA(P(M), P(W)) denote the set of all achievable stable matchings, i.e., stable matchings (with respect to the true preference proﬁle) that can be manipulated to by the manipulators. We sometimes write SA for short when (P(M), P(W)) is clear from the context. Deﬁnition 4 (Nash equilibrium). A preference proﬁle P (L) of a manipulation game is a Nash equilibrium if w L, reporting P(w) results in the best partner for w while assuming the other women reports P (L) \ {P(w)}. In other words, in a Nash equilibrium, any w L cannot be matched with a better partner in any stable matching she can manipulate to. We are also interested in the strong notions of Nash equilibrium. Deﬁnition 5 (Strong Nash equilibrium & Super-strong Nash equilibrium). A Nash equilibrium is strong, if no subset of manipulators can jointly manipulate to a matching that is strictly better off for all of them. A Nash equilibrium is superstrong, if no subset of manipulators can jointly manipulate to a matching that is weakly better off for all and strictly better off for at least one of them.

Equivalence between General Manipulation and Truncation Manipulation Gale and Sotomayor (1985) prove that a strong Nash equilibrium always exists if all women are manipulators and use truncation manipulations. They construct explicitly such a strong equilibrium by letting each woman use a truncation manipulation that removes all men ranked below her Woptimal partner. Ma (2010) also studies truncation manipulations in the same setting and shows that there is only one Nash equilibrium. In addition, the equilibrium proﬁle admits a unique stable matching, namely, the W-optimal matching. Teo, Sethuraman, and Tan (2001) provide a polynomial time algorithm to ﬁnd the optimal single-agent manipulation. We extend these results to coalition manipulations and consider any subset L W as manipulators.

Lemma 1. Let P = (P(M), P(W)) be the true preference proﬁle for all agents. Every matching in SA(P) induced by a general manipulation can be induced by a truncation manipulation.

To prove this lemma, we need another useful result from (Gonczarowski and Friedgut 2013):

Theorem 1. Given agents strict preferences over agents of the other sex, and a set of manipulators L W are allowed to use general manipulations, if no lying woman is worse off, then (1) No woman is worse off; (2) No man is better off.

Proof of Lemma 1. Let μ be any matching in SA and P (L) be the corresponding reported preference proﬁle by the manipulators in a Nash equilibrium of general manipulation. Therefore, μ is the M-optimal matching of P = (P(M), P(N), P (L)). We construct a truncated preference proﬁle Pt(L) for the manipulators where for each manipulator w, μ(w) is the last in her preference lists. (If w is single in μ, her preference list remains the same as her true preference list). Note that μ is stable under the true preference proﬁle. We show that under Pt = (P(M), P(N), Pt(L)), μ is also stable. Clearly, μ is individually rational. Assume on the contrary that a pair (m, w) blocks μ under Pt. It follows that m Pt w μ(w) and w Pt m μ(m). Then we know that m P w μ(w) is also true w W from the construction of Pt. Also, w P m μ(m) is true since no man s preference list is changed. Thus, (m, w) is a blocking pair under P, which contradicts to the stability of μ. We claim that μ is the W-pessimal matching under Pt. Suppose not and μ is the W-pessimal matching and μ = μ . Then we let the manipulators manipulate again from P to Pt and apply Theorem 1 (notice that when applying the theorem, the term worse off is with respect to P ). The resulting matching is μ . Clearly, no lying woman is worse off according to P . Thus no woman is worse off. So for any non-manipulator w, we have that μ (w) P w μ(w). It follows that μ (w) Pt w μ(w), since w is not a manipulator, which contradicts to the assumption that μ is the Wpessimal matching under Pt and μ is not equal to μ.

Remark 2. Note that this result is different from the exhaustiveness result in (Jaramillo, Kayı, and Klijn 2014), since ex-

haustiveness only requires that μ SA(P), there exists a truncation manipulation such that the induced matching is weakly preferred by the manipulators.

According to Lemma 1, it is therefore without loss of generality to focus on truncation manipulations. In the remainder of this paper, unless explicitly speciﬁed, we say a partner or a matching is W-optimal or W-pessimal for a woman if it is so under the true preference proﬁle.

Strong Nash Equilibria

It is well-known that any unmatched woman in a stable matching remains unmatched in all stable matchings.

Theorem 2. (Roth 1986) Given P(M) and P(W), the set of unmatched agents is the same among all stable matchings.

Recall that a Nash equilibrium induces a stable matching under true preferences (Gale and Sotomayor 1985). Any unmatched woman in the W-optimal matching has no incentive to misreport since she will always be unmatched. Thus, we only need to consider the case where no manipulator is unmatched in the W-optimal matching.

Lemma 2. Let (P(M), P(W)) be the true preference proﬁle and P (L) be the reported proﬁle by the manipulators. If for each manipulator w, her W-optimal partner is not removed from her list in truncation manipulation, then S(P(M), P(N), P (L)) S(P(M), P(W)).

Proof. Suppose not and there exists a matching μ which is in S(P(M), P(N), P (L)) but not in S(P(M), P(W)). Then, there exists a blocking pair (m, w) in μ under true preference lists. For m, since his preference list is not modiﬁed, he prefers w to μ(m) in true preference lists and the lists after truncation. If w is not single in μ, then m is still in her preference list after truncation manipulation since m w μ(w), which forms a blocking pair in μ with respect to the truncated preference lists. Otherwise, if w is single in μ, notice that, since the order of each man and each woman s preference list is not changed, the W-optimal matching is in S(P(M), P(N), P (L)). Thus, w is single in the W-optimal matching and according to the assumption, she is not a manipulator.

Theorem 3. In truncation manipulations, it is a strong Nash equilibrium that each manipulator removes every man below her W-optimal partner on her list. Furthermore, in the induced matching, all manipulators can be matched to their W-optimal partners.

Our proof is based on the following theorem.

Theorem 4 (Limits on successful manipulation, (Demange, Gale, and Sotomayor 1987)). Let P be the true preferences (not necessarily strict) of the agents, and let P differ from P in that some coalition C of men and women mis-state their preferences. Then there is no matching μ, stable for P , which is strictly preferred to every stable matching under the true preferences P by all members of C.

Proof of Theorem 3. We ﬁrst prove that each manipulator is matched to her W-optimal partner if they report P (L). According to Lemma 2, the induced matching μ must be in S(P(M), P(W)). Notice that the W-optimal matching is still in S(P(M), P(N), P (L)). Thus, according to Theorem 2, each manipulator is not single after manipulation, and she cannot be matched with a man worse than her W-optimal partner since she already removed him. Also, each woman cannot get a partner better than her W-optimal partner. Thus, all manipulators must be matched with their W-optimal partner. Next we show that it is a strong Nash equilibrium for all manipulators to do so. Note that for all stable matchings in S(P(M), P(N), P (L)), each manipulators are matched with their W-optimal partner. Applying Theorem 4 with C L, we can conclude that there is no matching in S(P(M), P(N), P (L \ C), P (C)) is strictly preferred to every stable matching in S(P(M), P(N), P (L)) for all members of C. Therefore, the constructed strategy proﬁle is a strong Nash equilibrium.

This result generalizes the result by (Gale and Sotomayor 1985) and (Teo, Sethuraman, and Tan 2001), which only considers manipulations by the set of all women. If the set of manipulators contains only one woman, the problem becomes a single-agent manipulation and Theorem 3 can also be applied. Thus, in coalition manipulations, every manipulator is matched with the same man as in her best singleagent manipulation. As Theorem 3 states, there is no conﬂict between different manipulators in the general manipulation. In fact, each woman can individually perform their optimal singleton manipulation, which provides her W-optimal partner. When combining together, all of them can still be matched to their W-optimal partners.

Lattice Structure

A lattice is mathematical structure containing a set where any two elements have a unique supremum. Formally,

Deﬁnition 6 (Join and Meet). Let be a partial order deﬁned over a set L for any subset S of L. Let e be an upper bound of S if e s, s S. e is a join of S if e is an upper bound of S and for any upper bound e of S, e e. Similarly, let e be an lower bound of S if e s, s S. e is a meet of S if e is an lower bound of S and for any lower bound e of S, e e.

Deﬁnition 7 (Lattice). L is a join-semilattice if every twoelement subset {e1, e2} L has a join. L is a meetsemilattice if every two-element subset {e1, e2} L has a meet. A lattice is both a join-semilattice and a meetsemilattice.

Now we deﬁne two notations that will be useful for later arguments.

Deﬁnition 8. Given two matchings μ and μ , deﬁne μ = μ μ to be the matching that matches each man to his more preferred partner and each woman to her less preferred partner in μ and μ . Similarly, we can deﬁne μ = μ μ ,

which matches each man to his less preferred partner and each woman to her more preferred partner.

The following theorem states that μ and μ are not only well-deﬁned matchings, but also essential to the lattice structure of the set of all stable matchings.

Theorem 5 (Conway s Lattice theorem; (Knuth 1976)). When all preferences are strict, if μ and μ are stable matchings under preference proﬁle P, then μ = μ μ and μ = μ μ are both matchings. Furthermore, they are both stable under P.

Therefore, the set of all stable matchings is a lattice with M and W . Let μL be a partial matching obtained by restricting the corresponding full matching μ to the set of manipulators and moreover, we call μ an extension of μL. Let SL A be the set of partial matchings obtained by restricting all matchings in SA to the set of manipulators L. Before we discuss the lattice structure of the set of SA, we ﬁrst prove a lemma about the relation between the length of the preference lists and the induced matching. We say a preference proﬁle P1 = (P(M), P(N), P1(L)) is shorter than another P2 = (P(M), P(N), P2(L)) if for each w L, |P1(w)| |P2(w)|. In other words, P1 is shorter than P2 if all manipulators remove no less men in P1 than in P2.

Lemma 3. Let P1 and P2 be two preference proﬁles and μ1 and μ2 be the two corresponding M-optimal matchings. If for each manipulator, her W-optimal partner is in both P1 and P2 and P1 is shorter than P2, then μ1 W μ2.

Proof. The lemma is a corollary of Lemma 2. Since P1 is shorter than P2, P1 can be viewed as a manipulation starting from P2. By Lemma 2, the set of stable matchings under P1 is a subset of that under P2. Moreover, the Gale-Shapley outputs the W-pessimal matching and thus, μ1 W μ2.

Lemma 4. Given two truncated preference proﬁles P1 and P2 from (P(M), P(W)), and two corresponding Moptimal matchings by μ1 and μ2. Let P = P1 P2 = (P(M), P(N), P (L)) such that

P (w) = P1(w) if |P1(w)| |P2(w)| P2(w) otherwise

for all w L. Then the M-optimal matching μ under P is exactly μ = μ1 μ2.

Proof. It is easy to check that P (L) is a legal proﬁle for the manipulators, i.e., the preference list for each manipulator w can be obtained by truncating her true preference list. According to Lemma 3, we have μ W μ1 and μ W μ2, so that from the deﬁnition of μ , we have μ W μ . To show that μ is identical to μ , we only need to show that μ W μ . We claim that μ is a stable matching under P , and thus μ W μ because μ is the W-pessimal matching under P . For each w, μ (w) w μ1(w), so μ (w) is in P1(w). Similarly μ (w) is also in P2(w). Therefore μ (w) is individually rational under P . Assume that μ is not stable under P . Then there must be a blocking pair (m, w) and m w μ (w) and w m μ (m) under P . However, the

two inequalities also hold in both P1(w) and P2(w). Notice that m and w are unmatched in at least one of the two matchings μ1 and μ2, otherwise μ (w) = m. Thus, (m, w) blocks either μ1 or μ2, which produces a contradiction.

Lemma 4 indicates that SA is a join-semilattice. However, it is not a meet-semilattice, i.e., there exists a subset in SA that does not have a meet. Consider the counter-example shown in Table 1 and 2.

m1 w1 w3 w5 m2 w2 w3 w6 m3 w3 w4 m4 w4 w3 m5 w5 w1 m6 w6 w2

Table 1: Men s preference lists

w1 m5 m1 w2 m6 m2 w3 m4 m2 m1 m3 w4 m3 m4 w5 m1 m5 w6 m2 m6

Table 2: Women s preference lists

μ1 μ2 μ m1 w5 m1 w1 m1 w1 m2 w2 m2 w6 m2 w2 m3 w4 m3 w4 m3 w4 m4 w3 m4 w3 m4 w3 m5 w1 m5 w5 m5 w5 m6 w6 m6 w2 m6 w6

Table 3: Matching results

Suppose L = {w1, w2}. If w1 alone lies and cuts her list to the one containing only m5, the induced matching is μ1 in Table 3. If w2 alone lies and lists only m6, we will get μ2. But the meet of the these two matchings μ cannot be induced by only truncating the preference lists of w1 and w2. Nevertheless, we prove that the set of partial matchings SL A is a lattice. Lemma 5. Given P1 = (P(M), P(N), P1(L)) and P2 = (P(M), P(N), P2(L)), suppose μ1 and μ2 are the two corresponding M-optimal matchings. Let μ = μ1 μ2. Then μL is in SL A.

Proof. We construct a preference proﬁle P as follows. For each w L, she removes all men ranked below μ (w) in her true preference list. We prove that the corresponding Moptimal matching μ is an extension of μL , i.e., μL = μL . Using similar techniques as in the proof of Lemma 4, we conclude that μ is a stable matching with respect to preference proﬁle P . For each w L, since μ (w) is the last one

in her preference list and they must be matched to their Wpessimal partner under P , μ (w) must be equal to μ (w) and μL = μL .

Lemma 4 is true when restricted to manipulators. Combining the above two lemmas together, we immediately get:

Theorem 6. Given the set of manipulators L and the true preference proﬁles (P(M), P(W)), the set of stable matchings that can be induced by general manipulations, SA(P(M), P(W)), is a join-semilattice, and the set of partial matchings SL A(P(M), P(W)) is a lattice.

In a ﬁnite join-semilattice, every two distinct matchings have a join and every woman is weakly better off in the join than any of the two matchings. Thus, if there exist two distinct matchings resulting from strong Nash equilibria, at least one matching can be improved from the perspective of women. Thus, the matching induced from the strong Nash equilibria is unique and Pareto-dominant.

Super-strong Nash Equilibrium However, a super-strong Nash equilibrium does not always exist.

Example 1. Consider the following preference lists (see Table 4 and 5).

m1 w1 w3 w2 m2 w2 w1 m3 w3

Table 4: Men s preference lists

w1 m2 m1 w2 m1 m2 w3 m1 m3

Table 5: Women s preference lists

The only stable matching under true preference lists is {(m1, w1), (m2, w2), (m3, w3)}. Therefore, this matching is the only possible outcome of a super-strong Nash equilibrium. However, consider the following manipulation:

w1 m2 w2 m1 w3 m3

Table 6: Women s new preference lists

After using the manipulation, the only stable matching is {(m1, w2), (m2, w1), (m3, w3)}, in which w1 and w2 are strictly better off while w3 remains the same.

The intuition behind the construction is that we consider one manipulator w who keeps her W-pessimal partner m and rejects any better proposals. Therefore, it is equivalent to a manipulation game by removing w from W, m from M and it is possible that in the remaining manipulation game, the

W-optimal matching is weakly better off than the W-optimal matching in the original game, though it is unstable with respect to true preference lists. Thus, with the help of manipulator w, a coalition can have a further manipulation to make everyone weakly better off and at least one strictly better off.

But notice that a super-strong Nash equilibrium must also be a strong Nash equilibrium. Since there exists a unique strong Nash equilibrium, one can check the existence and compute a super-strong Nash equilibrium by simply checking whether there exists a deviation to an unstable matching from the unique strong Nash equilibrium outcome. Given true preference lists P = (P(M), P(N), P(L)), a strong Nash equilibrium P (L), and its induced matching μ, if there exists a way to deviate to an unstable matching μ such that all manipulators are weakly better off and at least one manipulator w with μ (w ) = m w μ(w ) is strictly better off. Consider the modiﬁed preference lists P w ,m (L) from P (L): (1) w removes all men ranked below m in her true preference lists; (2) w L with w m w , removes m . Since no manipulators accept more men in P w ,m (L) than in P (L), either all of them are weakly better off or some of them become unmatched.

Theorem 7. Let P = (P(M), P(N), P(L)) be the true preference proﬁle. Let P (L) be a strong Nash equilibrium, and μ be the induced matching by (P(M), P(N), P (L)). P (L) is a super-strong Nash equilibrium if and only if for all w L and m P(w) with m w μ(w), there exists one manipulator w L such that w becomes unmatched under preference lists (P(M), P(N), P w,m(L)).

Proof. By Lemma 1, it is without loss of generality to assume that all manipulators only use truncation manipulations. only if direction: Suppose not and for the sake of contradiction, suppose that there exists w L and m P(w ) with m w μ(w) such that under preference lists (P(M), P(N), P w ,m (L)), no w L becomes unmatched. Note that no manipulators accept more men in P w ,m (L) than in P (L). Therefore, all manipulators are weakly better off since all of them are still matched after deviation. Moreover, w can only be matched to a man m w m w μ(w ) and thus w is strictly better off. Thus, we obtain a deviation such that all manipulators are weakly better off and at least one manipulator is strictly better off, implying that P (L) is not a super-strong Nash equilibrium. if direction: Suppose not and for the sake of contradiction, assume there still exists a deviation to P (L) with induced matching μ such that all manipulators are weakly better off and at least one manipulator w is strictly better off. Note that it is without loss of generality to assume that each manipulator w removes every man other than μ (w) in her lists since it does not change the induced matching. Therefore, no manipulators accepts more men in P (L) than in

P w ,μ (w )(L). However, we know there exists one manipulator w L such that w becomes unmatched under preference lists (P(M), P(N), P w ,m (L)). By removing more men from manipulators preference lists can only cause more manipulators become unmatched. Therefore, P (L) cannot be a deviation such that all manipulators are weakly better off and at least one manipulator w is strictly better off.

By Theorem 7, we can design an algorithm to compute a super-strong Nash equilibrium by ﬁrst computing the unique strong Nash equilibrium P (L) according to Theorem 3. After that, check whether P (L) is a super-strong Nash equilibrium by enumerating all possible pair of (w, m) with w L, m P(w), and m w μ(w). If assume |M| = |W| = n. then the total time complexity is O(n4): there are O(n2) possible pairs of (w, m) to enumerate and we need O(n2) time for running Gale-Shapley algorithm on the (P(M), P(N), P w,m(L)).

Future Research We show that Gale-Shapley algorithm is vulnerable to manipulation when women are allowed to report arbitrary preference lists. But is there any practical matching mechanism that is hard to manipulate? Though all matching mechanism can be manipulated due to the impossibility result Roth (1982), we can still hope for a practical mechanism that is computationally hard to manipulate. It is also interesting to investigate other types of manipulations, e.g. permutation manipulations.

References Abdulkadiroglu, A., and S onmez, T. 2003. School choice: A mechanism design approach. The American Economic Review 93(3):729 747. Abdulkadiro glu, A.; Pathak, P. A.; and Roth, A. E. 2005. The new york city high school match. American Economic Review 364 367. Abraham, D. J.; Blum, A.; and Sandholm, T. 2007. Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In Proceedings of the 8th ACM conference on Electronic commerce, 295 304. ACM. Demange, G.; Gale, D.; and Sotomayor, M. 1987. A further note on the stable matching problem. Discrete Applied Mathematics 16(3):217 222. Dubins, L. E., and Freedman, D. A. 1981. Machiavelli and the Gale-Shapley algorithm. American mathematical monthly 485 494. Dworczak, P. 2016. Deferred acceptance with compensation chains. In Proceedings of the 2016 ACM Conference on Economics and Computation, 65 66. ACM. Gale, D., and Shapley, L. S. 1962. College admissions and the stability of marriage. The American Mathematical Monthly 69(1):9 15. Gale, D., and Sotomayor, M. 1985. Ms. machiavelli and the stable matching problem. American Mathematical Monthly 261 268.

Gibbard, A. 1973. Manipulation of voting schemes: a general result. Econometrica: journal of the Econometric Society 587 601. Gonczarowski, Y. A., and Friedgut, E. 2013. Sisterhood in the Gale-Shapley matching algorithm. The Electronic Journal of Combinatorics 20(2):P12. Gonczarowski, Y. A. 2014. Manipulation of stable matchings using minimal blacklists. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC 14, 449 449. New York, NY, USA: ACM. Gupta, S.; Iwama, K.; and Miyazaki, S. 2015. Stable Nash equilibria in the Gale-Shapley matching game. ar Xiv preprint ar Xiv:1509.04344. Huang, C.-C. 2006. Cheating by men in the Gale Shapley stable matching algorithm. In Algorithms ESA 2006. Springer. 418 431. Irving, R. W., and Manlove, D. F. 2009. Finding large stable matchings. Journal of Experimental Algorithmics (JEA) 14:2. Irving, R. W.; Manlove, D. F.; and Scott, S. 2000. The hospitals/residents problem with ties. In Algorithm Theory SWAT 2000. Springer. 259 271. Jaramillo, P.; Kayı, C .; and Klijn, F. 2014. On the exhaustiveness of truncation and dropping strategies in manyto-many matching markets. Social Choice and Welfare 42(4):793 811. Knuth, D. E.; Motwani, R.; and Pittel, B. 1990. Stable husbands. In Proceedings of the ﬁrst annual ACM-SIAM symposium on Discrete algorithms, 397 404. Society for Industrial and Applied Mathematics. Knuth, D. E. 1976. Mariages Stables. Les Presses de I Universite de Montreal. Liu, Y.; Tang, P.; Xu, T.; and Zheng, H. 2016. Optimizing trading assignments in water right markets. In Proceedings of the Thirtieth AAAI Conference on Artiﬁcial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA., 551 557. Liu, Y.; Tang, P.; and Fang, W. 2014. Internally stable matchings and exchanges. In Proceedings of the Twenty Eighth AAAI Conference on Artiﬁcial Intelligence, July 27 -31, 2014, Qu ebec City, Qu ebec, Canada., 1433 1439. Ma, J. 2010. The singleton core in the college admissions problem and its application to the national resident matching program (nrmp). Games and Economic Behavior 69(1):150 164. Pini, M. S.; Rossi, F.; Venable, K. B.; and Walsh, T. 2009. Manipulation and gender neutrality in stable marriage procedures. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 1, 665 672. International Foundation for Autonomous Agents and Multiagent Systems. Roth, A. E.; S onmez, T.; and Unver, M. 2004. Kidney exchange. The Quarterly Journal of Economics 119(2):457 488. Roth, A. E.; S onmez, T.; and Unver, M. U. 2005. A kidney exchange clearinghouse in new england. American Economic Review 376 380.

Roth, A. E. 1982. The economics of matching: Stability and incentives. Mathematics of operations research 7(4):617 628. Roth, A. E. 1986. On the allocation of residents to rural hospitals: a general property of two-sided matching markets. Econometrica: Journal of the Econometric Society 425 427. Roth, A. E. 1996. The national residency matching program as a labor market. Journal of the American Medical Association 275(13):1054 1056. Teo, C.-P.; Sethuraman, J.; and Tan, W.-P. 2001. Gale Shapley stable marriage problem revisited: Strategic issues and applications. Management Science 47(9):1252 1267. Zhan, W.; Li, Z.; Tang, P.; Liu, Y.; and Xu, T. 2017. Stability of generalized two-sided markets with transaction thresholds. In Proceedings of the AAMAS.