Accomplice Manipulation of the Deferred Acceptance Algorithm

1 Introduction

The deferred acceptance (DA) algorithm [Gale and Shapley, 1962] is a crowning achievement of the theory of twosided matching [Manlove, 2013], and forms the backbone of a wide array of real-world matching markets such as entry-level labor markets [Roth, 1984; Roth and Peranson, 1999] and school choice [Abdulkadiro˘glu et al., 2005b; Abdulkadiro˘glu et al., 2005a]. Under this algorithm, one side of the market (colloquially, the men) makes proposals to the other side (the women) subject to either immediate rejection or tentative acceptance. A key property of the DA algorithm is stability which says that no pair of unmatched agents should prefer each other over their assigned partners. This property has played a significant role in the long-term success of several real-world matching markets [Roth, 1991; Roth, 2002].

The attractive stability guarantee of the DA algorithm, however, comes at the cost of incentives, as any stable matching procedure is known to be vulnerable to strategic misreporting of preferences [Roth, 1982]. The special proposal-rejection structure of the DA algorithm makes truth-telling a dominant strategy for the proposing side, i.e., the men [Dubins and Freedman, 1981; Roth, 1982], implying that any strategic behavior must occur on the proposed-to side, i.e., the women. This model of strategic behavior by a woman-which we call self manipulation-has been the subject of extensive study in economics and computer science [Dubins and Freedman, 1981; Gale and Sotomayor, 1985b; Demange et al., 1987; Teo et al., 2001; Kobayashi and Matsui, 2009; Kobayashi and Matsui, 2010; Vaish and Garg, 2017; Deng et al., 2018].

Our interest in this work is in studying a different model of strategic behavior under the DA algorithm called manipulation through an accomplice [Bendlin and Hosseini, 2019]. Under this model, a woman reports her preferences truthfully, but asks an agent on the proposing side (a.k.a. an accomplice) to manipulate the outcome on her behalf, possibly worsening his match in the process.

Such a strategic alliance can naturally arise in the assignment of students to schools under a school-proposing setup, where a "well-connected" student could have a school administrator manipulate on his/her behalf, possibly at a small loss to the school. Similarly, in a student-proposing setting, schools can strategize by making themselves appear less attractive to students from low-income backgrounds, thus forcing a change in the students' preferences [Hatfield et al., 2016]. Accomplice manipulation can also be seen as a control problem, wherein a woman can bribe a man to lie on her behalf. Bribery has been extensively studied in computational social choice in the context of voting, and our work can be seen as investigating this phenomenon in the two-sided matching framework.

At first glance, manipulation through an accomplice might not seem any more powerful than self manipulation, as the latter provides direct control over the preferences of the manipulator. Interestingly, there exist instances where this intuition turns out to be wrong.

Example 1 (Accomplice vs. self). Consider the following preference profile where the DA outcome is underlined. The notation "m1 : w3 w2 w1 w4" denotes that for man m1, the first choice woman is w3, the second choice is w2, and so on.

Suppose w1 seeks to improve her match via manipulation. The optimal self manipulation strategy for w1 is truth-telling, as m2 is the only man who proposes to her under the DA algorithm. On the other hand, w1 can improve her outcome by asking m1 to misreport on her behalf. Indeed, if m1 misreports by declaring ≻′m1 := w1 ≻ w3 ≻ w2 ≻ w4, then w1's match improves from m2 to m3 (the new DA matching is marked by ∗). Notice that the accomplice m1 preserves his initial match, meaning he does not incur any 'regret'.

The above example highlights that accomplice manipulation could, in principle, have an advantage over self manipulation. However, it is not apriori clear how frequent such an advantage might be in a typical matching scenario. To investigate the latter question, we take a quick experimental detour.

Accomplice manipulation is a viable strategic behavior. We simulate a two-sided matching scenario for an increasingly larger set of agents (specifically, n ∈ {3, . . . , 40}, where n is the number of men/women) and for each setting, generate 1000 preference profiles uniformly at random. For each profile, we compute the optimal self manipulation under the DA algorithm for a fixed woman [Teo et al., 2001], and the optimal accomplice manipulation by any man (we allow any man to be chosen as an accomplice as long as he is not worse off, i.e., a no-regret accomplice manipulation). Figure 1 illustrates the fraction of instances where accomplice and self manipulation are strictly more beneficial than truthful reporting, and how they compare against each other. Example 1 and Figure 1 suggest that the incentive for manipulation through an accomplice is not only present but actually more prevalent than self manipulation. Additionally, as we discuss later in our experimental results, women are expected to receive better matches when manipulating through an accomplice (Figure 2). These promising observations call for a systematic study of the structural and computational aspects of the accomplice manipulation problem, which is the focus of our work.

Our contributions. We consider two models of strategic behavior- no-regret manipulation (wherein the accomplice's own match doesn't worsen upon misreporting) and withregret manipulation (where the accomplice could get a worse match)-and make the following contributions:

• No-regret manipulation: Our main theoretical result (Theorem 2) is that any optimal no-regret accomplice manipulation can be simulated by promoting exactly one

woman in the true preference list of the accomplice; in other words, the manipulation is inconspicuous [Vaish and Garg, 2017]. This structural finding immediately gives a polynomial-time algorithm for computing an optimal manipulation (Corollary 2). We also show that the inconspicuous no-regret strategy results in a matching that is stable with respect to the true preferences (Corollary 3).

• With-regret manipulation: For the more permissible strategy space that allows the accomplice to incur regret, the optimal manipulation strategy once again turns out be inconspicuous (Theorem 3). However, in contrast to the no-regret case, the inconspicuous with-regret strategy is no longer guaranteed to be stability-preserving (Example 3). Nevertheless, any blocking pair can be shown to necessarily involve the accomplice (Proposition 2). This property justifies the use of an accomplice who can be encouraged to tolerate some regret to benefit a woman.
• Experiments: On the experimental front, we work with preferences generated uniformly at random, and find that accomplice manipulation outperforms self manipulation with respect to the frequency of occurrence, the quality of matched partners, and the fraction of women who can improve their matches (Section 6).

2 RelatedWork

Much of the early work on strategic aspects of stable matchings focused on truncation manipulation [Gale and Sotomayor, 1985a; Roth and Rothblum, 1999; Coles and Shorrer, 2014; Jaramillo et al., 2014], where the misreported preference list is required to be a prefix of the true list.

The literature on self manipulation via permutation is more recent and has focused on computational aspects. Teo et al. [2001] provided a polynomial-time algorithm for computing the optimal permutation manipulation by a woman under the men-proposing DA algorithm. Deng et al. [2018] studied stability-preserving permutation manipulation by a coalition of women and showed that such manipulations are inconspicuous. Vaish and Garg [2017] showed that an optimal permutation manipulation by a single agent is inconspicuous even without the stability-preserving requirement. They also studied conditions under which the manipulated outcome is stable with respect to the true preferences.

Huang [2006] studied (weakly) Pareto improving permutation manipulation by a coalition of men, revisiting the result of Dubins and Freedman [1981] on the impossibility of manipulations that are strictly improving for every member of the coalition.

The accomplice manipulation model was proposed by Bendlin and Hosseini [2019], who noted that manipulation through an accomplice can be strictly more preferable for the woman than optimal self manipulation. However, they left the structural and computational questions open.

Balinski and S¨onmez [1999] studied a closely related problem in school choice wherein the students have an incentive to make themselves appear less preferable to colleges (by performing badly on tests) under the college-optimal algorithm. Hatfield et al. [2016] similarly showed that in a student-optimal mechanism, schools have the incentive to deliberately make themselves look less attractive to "undesirable" students. For example, a private school that is legally required to cap its tuition fee for low-income students could make itself less attractive by increasing the rent in dormitories or requiring the students to purchase expensive uniforms.

3 Preliminaries

3.1 Stable Matching Problem

Problem setup. An instance of the stable marriage problem [Gale and Shapley, 1962] is specified by the tuple 〈M,W,≻〉, where M is a set of n men, W is a set of n women, and ≻ is a preference profile which consists of the preference lists of all agents. The preference list of any man m ∈ M, denoted by ≻m, is a strict total order over all women in W (for any w ∈ W, the list ≻w is defined analogously). We use w1 ⪰m w2 to denote 'either w1 ≻m w2 or w1 =m w2' (the latter denotes that man m is indifferent between w1 and w2), and write ≻-m to denote the preference lists of all men and women except man m; thus, ≻= {≻-m, ≻m}.

Stable matchings. Amatching is a function µ : M∪W → M ∪W such that µ(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 the preference profile ≻ if there is a man-woman pair (m,w) who prefer each other over their assigned partners under µ, i.e., w ≻m µ(m) and m ≻w µ(w). A stable matching is one that does not admit any blocking pair. We will write S≻ to denote the set of all matchings that are stable with respect to ≻. In addition, for any pair of matchings µ, µ′ , we will write µ ⪰M µ′ to denote µ(m) ⪰m µ′ (m) for all m ∈ M (and µ ⪰W µ′ for the women).

Deferred acceptance algorithm. Given a preference profile ≻, the Deferred Acceptance (DA) algorithm of Gale and Shapley [1962] proceeds in rounds. In each round, it consists of a proposal phase, where each man who is currently unmatched proposes to his favorite woman from among those who have not rejected him yet, followed by a rejection phase where each woman tentatively accepts her favorite proposal and rejects the rest. The algorithm terminates when no further proposals can be made. Gale and Shapley [1962] showed that given any profile ≻ as input, the DA algorithm always returns a stable matching as output; we denote this matching by DA(≻). They observed that this matching is men-optimal, i.e., it assigns each man his favorite stable partner among all stable matchings in S≻. McVitie and Wilson [1971] subsequently showed that this matching is also women-pessimal.

Proposition 1 ([Gale and Shapley, 1962; McVitie and Wilson, 1971]). Let ≻ be a preference profile and let µ := DA(≻). Then, µ ∈ S≻. Furthermore, for any µ′ ∈ S≻, µ ⪰M µ′ and µ′ ⪰W µ.

Accomplice manipulation. Under this model of strategic behavior, a woman w, instead of misreporting herself, has a man m provide a manipulated preference list, say ≻′m, in order to improve her match. Given a preference profile ≻, we say that w can manipulate through accomplice m if

µ′ (w) ≻w µ(w), where µ := DA(≻), ≻′ := {≻-m,≻′m}, and µ′ := DA(≻′ ). We will often refer to (m,w) as the manipulating pair (not to be confused with a blocking pair). Throughout this paper, any manipulation will be assumed to be optimal unless stated otherwise. That is, there exists no other list ≻′′m for the accomplice m such that µ′′ (w) ≻w µ′ (w), where ≻′′ := {≻-m,≻′′m}, and µ′′ := DA(≻′′ ). Note that we assume that the manipulator has full information about the preferences of other agents. Extending our results to incomplete or uncertain information settings is an interesting direction for future research.

No-regret and with-regret manipulation. We say that the accomplice m incurs regret if his match worsens upon misreporting, i.e., µ(m) ≻m µ′ (m). It is known that the DA algorithm is strategyproof for the proposing side [Dubins and Freedman, 1981], which means that no man can improve his match by unilaterally misreporting his preferences. Therefore, for any man m ∈ M and for any misreport ≻′m, we have that µ(m) ⪰m µ′ (m). Thus, equivalently, we say that man m incurs regret if µ(m) ̸= µ′ (m). We will consider two models of accomplice manipulation in this paper: no-regret manipulation wherein only those misreports ≻′m are allowed under which µ(m) = µ′ (m), and with-regret manipulation, where the accomplice is allowed (but not required) to incur regret. Thus, any no-regret strategy is also a with-regret strategy. Recall that the misreport in Example 1 was a no-regret manipulation.

Stability relaxations. For any preference profile ≻ and a fixed man m ∈ M, we say that a matching µ is mstable [Bendlin and Hosseini, 2019] with respect to ≻ if any blocking pair (if one exists) in µ involves the man m. That is, for any pair (m′ , w′ ) that blocks µ under ≻, we have m′ = m. Clearly, a stable matching is also m-stable. Under accomplice manipulation, it can be shown that any matching µ′ that is stable with respect to the manipulated profile (in particular, when µ′ = DA(≻′ )) is m-stable with respect to the true profile ≻ (Proposition 2). We note that Proposition 2 strengthens a result of Bendlin and Hosseini [2019] who proved a similar statement only for a DA matching. The proof of this result, along with all other omitted proofs, can be found in the full version of the paper [Hosseini et al., 2020].

Proposition 2. Let ≻ denote the true preference profile. For any man m, let ≻′ := {≻-m,≻′m}, and let µ′ ∈ S≻′ be any matching that is stable with respect to ≻′ . Then, µ′ is mstable with respect to ≻.

3.2 Structural Observations

Push up/push down operations. Note that given a profile ≻, the preference list of any man m can be written as ≻m= (≻Lm, µ(m), ≻Rm), where µ = DA(≻) and ≻Lm (respectively, ≻Rm) is the set of women that m prefers to (respectively, finds less preferable than) µ(m). Interestingly, the DA outcome does not change even if each man m arbitrarily permutes the parts of his list above and below his DA-partner µ(m). This result, due to Huang [2006], is recalled below.

Proposition 3 ([Huang, 2006]). Let ≻ be a preference profile and let µ := DA(≻). For any man m ∈ M, let

≻′m:= (πL(≻Lm), µ(m), πR(≻Rm)), where πL and πR are arbitrary permutations of ≻Lm and ≻Rm, respectively. Let ≻′ := {≻-m,≻′m}, and let µ′ := DA(≻′ ). Then, µ′ = µ.

Proposition 3 considerably simplifies the structure of accomplice manipulations that we need to consider. Indeed, we can assume that any manipulated list ≻′m is such that the relative ordering of agents in the parts above and below µ′ (m) is the same as under the true list ≻m, where µ′ := DA(≻′ ) and ≻′ := {≻-m,≻′m} are the post-manipulation DA outcome and preference profile, respectively.

This observation implies that, without loss of generality, any manipulated list ≻′m can be obtained from the true list ≻m by only push up and push down operations, wherein a set of women is pushed up above the true match µ(m), and another disjoint set is pushed below µ(m). Importantly, no permutation or shuffling operation is required as part of the manipulation. Formally, starting with the true list ≻m= (≻Lm, µ(m),≻Rm), we say that man m performs a push up operation for a set X ⊆ W if the new list is ≻X↑ m := (≻Lm ∪X, µ(m),≻Rm \X). Likewise, a push down operation of a set Y ⊆ W results in ≻Y ↓ m := (≻Lm \Y, µ(m), ≻Rm ∪Y ).

For manipulation via push down operations only, Huang [2006] has shown that the resulting matching is weakly improving for all men. Together, with the fact that the DA algorithm is strategyproof for the proposing side (in our case the men) [Dubins and Freedman, 1981], we get that the DA partner of the accomplice remains unchanged after a push down operation.

Proposition 4 ([Dubins and Freedman, 1981; Huang, 2006]). Let ≻ be the true preference profile and let µ := DA(≻). For any subset of women X ⊆ W and any fixed accomplice m ∈ M, let ≻′ := {≻-m,≻X↓ m } and µ′ := DA(≻′ ). Then, µ′ ⪰M µ and µ′ (m) = µ(m).

The effect of push down operations for the proposed-to side is the exact opposite, as the resulting matching makes all women weakly worse off.

Lemma 1. Let ≻ be the true preference profile and let µ := DA(≻). For any subset of women X ⊆ W, let ≻′ := {≻-m, ≻X↓ m } and µ′ := DA(≻′ ). Then, µ ⪰W µ′ .

Lemma 1 shows that in order to improve the partner of the woman w, the use of push up operations (by the accomplice) is necessary. However, it is not obvious upfront whether push up alone suffices; indeed, it is possible that the optimal strategy involves some combination of push up and push down operations. To this end, our theoretical results will show that, somewhat surprisingly, pushing up at most one woman achieves the desired optimal manipulation (Theorems 2 and 3). This strategy is known in the literature as inconspicuous manipulation, which we define next.

Inconspicuous manipulation. Given a profile ≻ of true preferences and any fixed accomplice m, the manipulated list ≻′m is said to be an inconspicuous manipulation if the list ≻′m can be derived from the true preference list ≻m by promoting exactly one woman and making no other changes. The notion of inconspicuous manipulation has been previously studied in the context of self manipulation (where w misreports herself), where it was shown that an optimal self manipulation is, without loss of generality, inconspicuous [Vaish and Garg, 2017; Deng et al., 2018].

4 No-Regret Accomplice Manipulation

Let us start by observing that the DA matching after an arbitrary (i.e., not necessarily push up) no-regret accomplice manipulation may not be stable with respect to the true preferences.

m1 : w∗ 2 w† 1 w3 w4 w5 w1 : m†1 m3 m∗2 m4 m5 m2 : w∗ 1 w† 2 w3 w4 w5 w2 : m†2 m∗1 m3 m4 m5 m3 :w1 w∗,† 3 w4 w2 w5 w3 : m∗,† 3 m1 m2 m4 m5 m4 : w4 w∗,† 5 w1 w2 w3 w4 : m∗,† 5 m3 m1 m2 m4 m5 : w5 w∗,† 4 w1 w2 w3 w5 : m∗,† 4 m1 m2 m3 m5

Suppose the manipulating pair is (m3,w4). The DA matches after the accomplice m3 submits the manipulated list ≻′m3 := w4 ≻ w3 ≻ w1 ≻ w2 ≻ w5 are marked by ∗. The manipulation results in w4 being matched with her top choice m5 (i.e., ≻′m3 is an optimal manipulation), an improvement over her true match m4. Although m3 does not incur regret, the manipulated matching admits a blocking pair (m3,w1) with respect to the true preferences.

Notice that if instead m3 were to submit ≻′′m3 := w4 ≻ w1 ≻ w3 ≻ w2 ≻ w5 as his preference list in Example 2, then the resulting DA matching (indicated by †) would be stable with respect to the true preferences while still allowing w4 to match with m5 (i.e., ≻′′m3 is also optimal). The manipulated list ≻′′m3 is derived from the true list ≻m3 through a no-regret push up operation. Our first main result of this section (Theorem 1) shows that this is not a coincidence: The set of all stable matchings with respect to a profile after a noregret push up operation is always contained within the stable set of the true preference profile.

Theorem 1 (No-regret push up is stability preserving). Let ≻ be a preference profile, and let µ := DA(≻). For any subset of women X ⊆ W and any man m, let ≻′ := {≻-m, ≻X↑ m }, and µ′ := DA(≻′ ). If m does not incur regret, then S≻′ ⊆ S≻.

A primary consequence of Theorem 1 is that the DA matching after a no-regret accomplice manipulation is weakly preferred over the true DA outcome by all women, while the opposite is true for the men.

Corollary 1. Let ≻ be a preference profile and let µ := DA(≻). For any man m, let ≻′ := {≻-m,≻X↑ m } and µ′ := DA(≻′ ). If m does not incur regret, then µ′ ⪰W µ and µ ⪰M µ′ .

As observed in Section 3.2, any manipulation by the accomplice can be, without loss of generality, assumed to comprise only of push up and push down operations. We will now show that combining these operations is not necessary. That is, any manipulation that is achieved by a combination of push up and push down operations can be weakly improved by a push up operation alone (Lemma 2). We note that this result does not require the no-regret assumption, and applies to the with-regret setting as well.

Lemma 2. Let (m,w) be a manipulating pair and let ≻ be a preference profile. For any subsets of women X ⊆ W and Y ⊆ W, let ≻′ := {≻-m,≻X↑ m } denote the preference profile after pushing up the set X, and ≻′′ := {≻-m,≻X↑,Y ↓ m } denote the profile after pushing up X and pushing down Y in the true preference list ≻m of man m. Let µ := DA(≻), µ′ := DA(≻′ ), and µ′′ := DA(≻′′ ). Then, µ′ (w) ⪰w µ′′ (w).

Having narrowed down the strategy space to push up operations alone, we will now turn our attention to inconspicuous manipulations (recall that such a manipulation involves promoting exactly one woman in the accomplice's true preference list to a higher position). We will show that any match for the manipulating woman w that can be obtained by pushing up a set of women can also be achieved by promoting exactly one woman in that set (Lemma 3). In other words, any no-regret push up operation is, without loss of generality, inconspicuous. We note that although Lemma 3 assumes no regret for the accomplice, the corresponding implication actually holds even in the with-regret setting (see Lemma 4).

Lemma 3. Let (m,w) be a manipulating pair, and let X ⊆W be an arbitrary set of women that m can push up without incurring regret. Then, the match for w that is obtained by pushing up all women in X can also be obtained by pushing up exactly one woman in X.

We will now use the foregoing observations to prove our main result (Theorem 2).

Theorem 2. If there is an optimal no-regret accomplice manipulation, then there is an optimal inconspicuous no-regret accomplice manipulation.

Proof. From Proposition 3 (and subsequent remarks), we know that any accomplice manipulation can be simulated via push up and push down operations. Lemma 2 shows that any beneficial manipulation that is achieved by some combination of pushing up a set X ⊆ W and pushing down Y ⊆ W can be weakly improved by only pushing up X. Finally, from Lemma 3, we know that any match for the manipulating woman w that is achieved by pushing up X ⊆ W is also achieved by pushing up exactly one woman in X, thus establishing the desired inconspicuousness property.

Theorem 2 has some interesting computational and structural implications. First, the inconspicuousness property implies a straightforward polynomial-time algorithm for computing an optimal no-regret accomplice manipulation (Corollary 2). Second, the DA matching resulting from an inconspicuous no-regret manipulation is stable with respect to the true preferences (Corollary 3). Together, these results reconcile the seemingly conflicting interests of the manipulator (who wants to compute optimal manipulation efficiently) and the central planner (who wants the resulting matching to be stable with respect to the true preferences).

Corollary 2. An optimal no-regret accomplice manipulation strategy can be computed in O(n3 ) time.

Corollary 3. The DA outcome from an inconspicuous noregret accomplice manipulation is stable with respect to the true preferences.

In summary, recall from Example 2 that an arbitrary optimal no-regret strategy may not be stability-preserving. Nevertheless, any optimal no-regret strategy admits an equivalent inconspicuous strategy (Theorem 2) which indeed preserves stability (Corollary 3).

5 With-Regret Accomplice Manipulation

No-regret manipulations come at no cost for the accomplice and thus are a viable strategic behavior (as shown in Figure 1). Yet, a more permissive strategy space may allow for the accomplice to incur some regret. Such with-regret manipulations may be justifiable in practice: An accomplice's idiosyncratic preference may be tolerant to a small loss in exchange of gain for the partnering woman, or a woman may persuade a man to withstand some regret by providing side-payments.

We will start by illustrating that a with-regret accomplice manipulation can be strictly more beneficial compared to its no-regret and self manipulation counterparts.

Suppose the manipulating pair is (m1, w1). The DA matching after m1 submits the optimal no-regret 1 manipulated list ≻′m1 := w2 ≻ w4 ≻ w1 ≻ w5 ≻ w3 and the optimal withregret manipulated list ≻′′m1 := w1 ≻ w4 ≻ w2 ≻ w5 ≻ w3 are marked by ∗ and †, respectively. Both manipulation strategies improve w1's matching compared to truthful reporting, but w1 strictly prefers the with-regret outcome.

Example 3 highlights two key differences between optimal no-regret and with-regret manipulations. First, the matching after the inconspicuous with-regret manipulation (marked by †) admits a blocking pair (m1,w4) with respect to the true profile ≻. This is in contrast to the no-regret case which is stability preserving (Theorem 1). Second, in contrast to Corollary 1, an optimal with-regret manipulation is not guaranteed to weakly improve or worsen the matching for all agents on one side; indeed the women w3 and w5 are strictly worse off while w1 is strictly better off. Similarly, the man m1 is strictly worse off while m4 and m5 strictly improve.

The primary distinction between no-regret and with-regret manipulation lies in the push up operations. If pushing up a set of women does not cause regret for the accomplice, then pushing up any subset thereof does not either. By contrast, if by pushing up a set of women the accomplice incurs regret, then there exists exactly one woman in that set who causes the same level of regret when pushed up individually. As previously mentioned, with-regret push up operations do not uniformly affect all men and all women (in contrast to Corollary 1). Moreover, the set of attained matchings after a withregret manipulation are no longer stable with respect to true preferences (in contrast to Theorem 1), which makes the analysis challenging.

1 To see why ≻′m1 is an optimal no-regret manipulation, note that the woman-optimal stable matching (with respect to ≻) matches w1 with m2. From Theorem 2 and Corollary 3, an optimal no-regret manipulation is, without loss of generality, stability preserving, and from Proposition 1, m2 is the best stable partner for w2.

Despite these structural differences, we are able to prove an analogue of Lemma 3 for with-regret push up operations (Lemma 4). Our proof of this result relies on the fact that all proposals that occur when the accomplice pushes up a set of women are contained in the union of sets of proposals that occur when pushing up individual women in that set. This is relatively easy to prove for the no-regret case, since the DA matchings after these push up operations are all stable with respect to true preferences (Theorem 1). Although we cannot rely on the same stability result for the with-regret case, we circumvent the issue by reasoning about the sets of proposals in greater detail.

Lemma 4. Let (m,w) be a manipulating pair, and let X ⊆W be an arbitrary set of women that m can push up (while incurring regret). Then, the match for w that is obtained by pushing up all women in X can also be obtained by pushing up exactly one woman in X.

Subsequently, an optimal with-regret manipulation is, without loss of generality, inconspicuous. The proof is similar to that of the no-regret case (Theorem 2) with the only difference being the use of Lemma 4 in place of Lemma 3.

Theorem3. If there is an optimal with-regret accomplicemanipulation, then there is an optimal inconspicuous with-regret accomplice manipulation.

Theorem 3 immediately implies a polynomial-time algorithm for computing an optimal with-regret accomplice manipulation. Moreover, the DA outcome from any inconspicuous with-regret accomplice manipulation is m-stable with respect to the true preferences (Proposition 2).

Corollary 4. An optimal with-regret accomplice manipulation strategy can be computed in O(n3 ) time.

6 Experimental Results

In addition to the experiments described in Section 1, we performed a series of simulations to analyze the performance of accomplice manipulation. As for the previous experimental setup, we generated 1000 profiles uniformly at random for each value of n ∈ {3, . . . , 40} (where n is the number of men/women) and allowed any man to be chosen as an accomplice for each experiment unless stated otherwise.

Comparing the Quality of Partners. We first compare the quality of partners that a fixed strategic woman w is matched with through no-regret accomplice and self manipulation. Figure 2 illustrates the distributions of improvement (in terms of rank difference) out of only those instances where w is strictly better off through the two strategies individually. In other words, the self (respectively, accomplice) manipulation boxplots only reflect the data for when self (respectively, accomplice) manipulation is successful. It is evident that, in expectation, w is matched with better partners through no-regret accomplice manipulation.

The Fraction of Women Who Improve. We additionally compare the fraction of women who are able to improve through no-regret accomplice and self manipulation individually. Teo et al. [2001] reported that 5.06% of women were able to improve using self manipulation when n = 8. In our experiment, this value is similarly 4.18%. However, 9.99% of women are able to improve through no-regret accomplice manipulation. As illustrated in Figure 3, the fraction of women who benefit from no-regret accomplice manipulation is consistently more than double that of self manipulation.

7 Concluding Remarks

We showed that accomplice manipulation is a viable strategic behavior that only requires inconspicuous misreporting of preferences and is frequently more beneficial than the classical self-manipulation strategy. A natural avenue for future research is to investigate a setting with multiple accomplices working together to manipulate the outcome for the strategic woman, or one where the accomplice and the manipulating woman can misreport their preference lists simultaneously. Analyzing the benefits of such coalitional manipulation strategies-with or without regret-on one or both sides, and studying their structural and algorithmic properties are intriguing directions for future work.

Acknowledgements

HH acknowledges support from NSF grant #1850076. RV acknowledges support fromONR#N00014-171-2621, project no. RTI4001 of the Department of Atomic Energy, Government of India, and Prof. R Narasimhan postdoctoral award.