Two for One & One for All: Two-Sided Manipulation in Matching Markets

1 Introduction

The deferred acceptance algorithm [Gale and Shapley, 1962] is one of the biggest success stories of matching theory and market design. It has profoundly impacted numerous practical applications including school choice [Abdulkadiro˘glu et al., 2005a; Abdulkadiro˘glu et al., 2005b] and entrylevel labor markets [Roth and Peranson, 1999] and has inspired a long line of work in economics and computer science [Gusfield and Irving, 1989; Roth and Sotomayor, 1992; Roth, 2008; Manlove, 2013].

The success of the deferred acceptance (or DA) algorithm has been driven by its stability property, which prevents pairs of agents from preferring each other over their assigned partners. Stability eliminates the incentives for agents to participate in secondary markets or 'scrambles' [Kojima et al.,

2013], and has been a key predictor of the long-term sustenance of many real-world matching markets [Roth, 2002].

Unfortunately, any stable matching algorithm is known to be vulnerable to strategic misreporting of preferences by the agents [Roth, 1982]. For the DA algorithm, in particular, it is known that truth-telling is a dominant strategy for the proposing side-colloquially, the men-implying that any strategic behavior is confined to the proposed-to side-the women [Dubins and Freedman, 1981; Roth, 1982].

One-sided vs. two-sided manipulation. Given the strong practical appeal of DA algorithm, significant research effort has been devoted towards understanding its incentive properties. Much of this work has focused on "one-sided" manipulation wherein the agent who misreports is also the intended beneficiary; that is, the misreporting agent and the beneficiary are on the same side. For this self manipulation problem, the structural and computational questions have been extensively studied [Dubins and Freedman, 1981; Gale and Sotomayor, 1985a; Gale and Sotomayor, 1985b; Teo et al., 2001; Vaish and Garg, 2017]. By contrast, there are many real-world settings that, in essence, resemble "twosided" manipulations where the misreporting agent and the beneficiary are on different sides. For example, in the studentproposing school choice, schools could influence the preferences of students they find "undesirable" (such as those from low-income backgrounds) by using indirect measures such as fee hike [Hatfield et al., 2016]. In ridesharing platforms, a driver may influence the preferences of certain riders by strategically moving to a farther distance. Similarly, in a gig economy, freelancers' preferences over tasks may be affected by an employer's restrictive requirements.

Motivated by these examples, recent works have studied the accomplice manipulation model wherein a man misreports his preferences in order to help a specific woman [Bendlin and Hosseini, 2019; Hosseini et al., 2021]. It has been shown via simulations that accomplice manipulation strategies are more frequently available than self manipulation and result in better matches for the woman. Further, an optimal misreport for the accomplice is known to be inconspicuous (i.e., the manipulated list can be derived from his true list by promoting exactly one woman), efficiently computable, and stability-preserving (i.e., the manipulated DA matching is stable with respect to the true preferences).

Towards coalitional two-sided manipulation. The aforementioned advantages of two-sided manipulation call for a deeper investigation into the topic. Our work takes a step in this direction by focusing on coalitional aspects of the two-sided manipulation problem. Our starting point is the accomplice manipulation model [Hosseini et al., 2021], which involves one misreporting agent and one beneficiary (i.e., a one for one setting). We consider two coalitional generalizations of this model: (i) The two for one model, with a coalition of two misreporting agents (a man and a woman) and a single beneficiary (the woman), and (ii) the one for all model, with one misreporting agent (man) and a coalition of beneficiaries (all women). Coalitional manipulation of the DA algorithm has received considerable theoretical interest over the years [Dubins and Freedman, 1981; Gale and Sotomayor, 1985a; Gale and Sotomayor, 1985b; Demange et al., 1987; Kobayashi and Matsui, 2010], and recently its practical relevance has also been discussed. Indeed, in college admissions in China, universities have been known to form "leagues" for conducting independent recruitment exams allowing them to jointly manipulate admission results [Shen et al., 2021]. Prior work on coalitional manipulation has focused exclusively on one-sided manipulation.

Our contributions. We study two coalitional generalizations of accomplice manipulation and make the following theoretical and experimental contributions (see Table 1):

• Two for one: We show that when the accomplice and the beneficiary can jointly misreport, an optimal pair manipulation strategy can be strictly better for the beneficiary than either of the optimal individual (i.e., self or accomplice) manipulation strategies (Example 1). In contrast to self and accomplice manipulation, an optimal pair manipulation may not be stability-preserving (Remark 1) and it is unclear whether it is inconspicuous. Nevertheless, we provide a polynomial-time algorithm for computing an optimal pair manipulation (Theorem 1).
• One for all: We observe that optimal manipulation by the accomplice for helping all women could fail to be inconspicuous (Example 2). By contrast, when helping a single woman, an optimal strategy for the accomplice is known to be inconspicuous [Hosseini et al., 2021].

Despite losing this structural benefit, we develop a polynomial-time algorithm for computing an optimal one-for-all strategy (Corollary 1), and show that such a strategy is stability-preserving (Corollary 3 in [Hosseini et al., 2022]). In fact, we show that a minimum optimal misreport (i.e., one that pushes up as few women as possible) can be efficiently computed and provide tight bounds on size of promoted set [Hosseini et al., 2022].

• Experiments: Our simulations on uniformly random preferences show that two-sided strategies are more frequently available (Figure 2) and result in better matches than one-sided strategies [Hosseini et al., 2022].

Related Work. The literature on strategic aspects of stable matching procedures has classically focused on truncation strategies where the misreported list is a prefix of the true list [Dubins and Freedman, 1981; Roth, 1982; Roth and Rothblum, 1999]. Our work, on the other hand, focuses on permutation manipulation where the manipulated list is a reordering of the true list. Teo et al. [2001] initiated the study of permutation manipulation by a single woman and provided a polynomial-time algorithm for finding an optimal misreport. Vaish and Garg [2017] showed that an optimal strategy for the woman is inconspicuous and stability-preserving. Permutation manipulation by a group of agents has been studied for a coalition of men [Huang, 2006; Huang, 2007] and for a coalition of women [Kobayashi and Matsui, 2010; Shen et al., 2021]. In particular, Shen et al. [2021] provided an algorithm for finding a strategy for a coalition of women that is Pareto optimal among all stability-preserving strategies, and showed that such a strategy is inconspicuous. In the two-sided setting, Bendlin and Hosseini [2019] introduced the accomplice manipulation model and observed that it can be more beneficial for a woman than optimal self manipulation. Subsequently, Hosseini et al. [2021] studied with-regret and no-regret accomplice manipulation, depending on whether the accomplice's match worsens or stays the same. They showed that an optimal no-regret manipulation is stability-preserving while its with-regret counterpart is not, and that optimal strategies under both models are inconspicuous and therefore efficiently computable. Our work will focus exclusively on no-regret strategies.

2 Preliminaries

Problem instance. An instance of the stable marriage problem [Gale and Shapley, 1962] is given by a tuple 〈M,W,≻〉, where M is a set of n men, W is a set of n women, and ≻ is a preference profile which specifies the preference lists of the agents. The preference list of a man m ∈ M, denoted by ≻m, is a strict total order over all women in W. The list ≻w of a woman w ∈ W is defined analogously. We will write w1 ⪰m w2 to denote "either w1 ≻m w2 or w1 = w2", and write ≻-m to denote the profile without the list of man m; thus, ≻= {≻-m, ≻m}.

Stable matching. A matching 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. Given a matching µ, a blocking pair with respect to the preference profile ≻ is a man-woman pair (m, w) who prefer each other over their assigned partners, i.e., w ≻m µ(m) and m ≻w µ(w). A matching is said to be stable if it does not have any blocking pair. We will write S≻ to denote the set of all stable matchings with respect to ≻. Note that in the worst case, the size of S≻ can be exponential in n [Knuth, 1997].

For any pair of matchings µ, µ′ , we will write µ ⪰M µ′ to denote that all men weakly prefer µ over µ′ , i.e., µ(m) ⪰m µ′ (m) for all m ∈ M (analogously µ ⪰W µ′ for women).

Deferred acceptance algorithm. The deferred acceptance (DA) algorithm is a well-known procedure for finding stable matchings [Gale and Shapley, 1962]. Given as input a preference profile, the algorithm alternates between a proposal phase, where each currently unmatched man proposes to his favorite woman among those who haven't rejected him yet, and 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 preference profile ≻ as input, the matching computed by the DA algorithm, which we will denote by DA(≻), is stable. Furthermore, this matching is men-optimal as it assigns to each man his favorite partner among all stable matchings in S≻. Subsequently, it was observed that the same matching is also women-pessimal [McVitie andWilson, 1971].

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

Self manipulation. Given a profile ≻ and the matching µ := DA(≻), we say that woman w can self manipulate if there exists a list ≻′w (which is a permutation of w's true list ≻w) such that µ′ (w) ≻w µ(w), where µ′ := DA(≻-w,≻′w ). An optimal self manipulation ≻′w (with respect to the profile ≻) is one for which there is no other list ≻′′w such that µ′′ (w) ≻w µ′ (w), where µ′′ := DA(≻-w,≻′′w ).

Accomplice manipulation. A different model of strategic behavior is accomplice manipulation [Bendlin and Hosseini, 2019; Hosseini et al., 2021], wherein a woman w, instead of misreporting herself, asks a man m to misreport his preference in order to improve w's match. Formally, given a profile ≻ and a fixed man m, we say that woman w can manipulate via accomplice m if there exists a list ≻′m for man m (which is a permutation of his true list ≻m) such that µ′ (w) ≻w µ(w), where µ := DA(≻) and µ′ := DA(≻-m ,≻′m). An optimal accomplice manipulation ≻′m (with respect to ≻) is one for which there is no other list ≻′′m such that µ′′ (w) ≻w µ′ (w), where µ′′ := DA(≻-m,≻′′m). We will call woman w a 'beneficiary' and man m an 'accomplice'.

No-regret assumption. In this paper, we will consider two generalizations of accomplice manipulation: (a) the "two for one" problem with two misreporting agents (man m and woman w) and a single beneficiary (woman w), and (b) the "one for all" problem with a single misreporting agent (man m) and a coalition of beneficiaries (all women). In both cases, we will assume no-regret manipulation for the man which means that m's match does not worsen upon misreporting, i.e., µ′ (m) ⪰m µ(m).

Interestingly, for both generalizations mentioned above, the no-regret assumption implies that the accomplice's match stays the same, i.e., µ(m) = µ′ (m). Indeed, in the one-for-all problem, it follows from the strategyproofness of the DA algorithm for the proposing side that µ(m) ⪰m µ′ (m). Along with the no-regret assumption, this implies µ(m) = µ′ (m). For the two-for-one problem where both man m and woman w can misreport, it is known that m cannot be strictly better off unless w is strictly worse off [Huang, 2007, Corollary 4]. To prevent the beneficiary w from being worse off, we must ensure that man m's match does not improve, implying once again that µ(m) = µ′ (m).

Inconspicuous manipulation. Amisreported list (or strategy) ≻′m for an accomplice m is said to be inconspicuous if it can be derived from his true list ≻m by promoting at most one woman and making no other changes. Similarly, when the misreporting agent is a woman w, inconspicuousness involves promoting at most one man in her true list ≻w.

Push up and push down operations. For any man m ∈ M, let ≻Lm and ≻Rm denote the parts of m's list above and below his DA partner, respectively. That is, ≻m= (≻Lm , µ(m),≻Rm). We say that man m pushes up a set X ⊆ W if the new list is ≻X↑ m := (≻Lm ∪X, µ(m),≻Rm \X). Similarly, pushing down a set Y ⊆ W results in ≻Y ↓ m := (≻Lm \Y, µ(m),≻Rm ∪Y ). The exact positions at which agents in X (or Y ) are placed above (or below) µ(m) is not important, as long as the sets are appropriately pushed above (or below) µ(m). Huang [2006] has shown that the DA outcome remains unchanged if each man m arbitrarily permutes the part of his list above and below his DA-partner µ(m).

Proposition 2 ([Huang, 2006]). Let ≻ be a profile and let µ := DA(≻). For any man m ∈ M with true list ≻m= (≻Lm , µ(m),≻Rm), let ≻′m:= (πL(≻Lm), µ(m), πR(≻Rm)), where πL and πR are arbitrary permutations. Let µ′ := DA(≻-m ,≻′m). Then, µ′ = µ.

3 Two for One: Helping a SingleWoman Through Pair Manipulation

In this section, we will consider the "two for one" generalization of accomplice manipulation where the accomplice and the strategic woman can jointly misreport in order to benefit the latter. To see how such a generalization can be useful, let us start with an example showing that pair manipulation can be strictly more beneficial for the woman compared to either self or accomplice manipulation (Example 1).

Example 1 (Pair manipulation can be strictly better than accomplice or self manipulation). Consider the following preference profile where the DA outcome is underlined. The notation "m1 : w5 w3 w4 w2 w1" denotes that m1's top choice is w5, second choice is w3, and so on.

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

Suppose the manipulating pair is (m1,w1). Since m4 is the only man who proposes to w1 during the execution of DA

Figure 1: Preference profiles under pair manipulation.

algorithm on this profile, it follows that there is no beneficial self manipulation strategy for w1.

To find an optimal accomplice manipulation for m1, it suffices to focus on inconspicuous strategies [Hosseini et al., 2021]. It is straightforward to verify that promoting any woman below w3 in m1's list does not result in a better match for w1. In fact, none of the other men can give w1 a better partner via no-regret manipulation.

The DA matching when m1 and w1 jointly misreport with ≻′m1 := w1 ≻ w5 ≻ w3 ≻ w4 ≻ w2 and ≻′w1 := m3 ≻ m5 ≻ m1 ≻ m4 ≻ m2 is marked by "∗". Note that the strategic woman w1 is now able to match with her top choice without worsening the match of the accomplice m1.

Since pair manipulation can be strictly more beneficial than either self or accomplice manipulation, it is natural to ask whether an optimal pair manipulation can be efficiently computed. Our main result in this section is that an optimal pair manipulation can be computed in polynomial time.

3.1 Computing an Optimal Joint Strategy

A natural approach for finding an optimal joint strategy is to combine (or "concatenate") an optimal self manipulation for the woman and an optimal accomplice manipulation for the man. However, as we saw in Example 1, an optimal pair manipulation may exist despite there being no beneficial accomplice nor self manipulations. Further, Example 3 in the full version of the paper [Hosseini et al., 2022] shows that the woman's match could actually worsen by naively combining the respective individual strategies. Thus, pair manipulation appears to be "more than just the sum of its parts".

Another natural approach is to combine inconspicuous (but not necessarily individually optimal) strategies of the accomplice and the strategic woman. However, as we discuss in the appendix of [Hosseini et al., 2022], there are some subtleties that arise from this approach that become difficult to resolve. We leave the question of determining whether optimal pair manipulation is inconspicuous as an open problem.

Nevertheless, the idea of looking for structure in the individual strategies turns out to be useful. To see why, consider a manipulating pair (m,w). Let ≻∗m and ≻∗w denote the respective lists of m and w under an optimal pair manipulation, and let ≻∗ := {≻-{m,w}, ≻∗m, ≻∗w } denote the corresponding preference profile.

Since it is easier to think about single-agent misreports, let us break down the transition from the true profile ≻ to the pair manipulation profile ≻∗ in two steps: First, swap w's list in ≻ to obtain the intermediate profile ≻w := {≻-w,≻∗w }, and then swap m's list in ≻w to get ≻∗ ; see Figure 1. We will show that this two-step approach allows us to impose additional structure on the individual strategies ≻∗m and ≻∗w .

Let us start by analyzing woman w's strategy ≻∗w . Consider the transition ≻→≻w in Figure 1, where w is the only misreporting agent. Let Rw denote the set of preference Algorithm 1 Computing an optimal pair manipulation Input: Profile ≻, accomplice m, beneficiary w

Output: Optimal pair manipulations ≻∗m and ≻∗w 1: Initialize (µ∗ ,≻∗m,≻∗w) ← (µ := DA(≻),≻m,≻w) 2: Compute Rw 3: for each ≻′w∈ Rw do 4: Compute Rm 5: for each ≻′m∈ Rm do 6: µ′ ← DA(≻-{m,w}, ≻′m, ≻′w) 7: if µ′ (w) ≻w µ∗ (w) and µ′ (m) = µ(m) then 8: Update (µ∗ , ≻∗m, ≻∗w) ← (µ′ , ≻′m, ≻′w) 9: return ≻∗m and ≻∗w

lists that can be obtained from w's true list ≻w by moving some pair of men to the top two positions, i.e., Rw := {(mi, mj, ≻w \{mi,mj}) : mi,mj ∈ M}. In Lemma 1, we show that for an arbitrary misreport by w, there exists a list in Rw that creates the same matching for all agents. Thus, it follows that ≻∗w ∈ Rw. Observe that the set Rw is of polynomial size O(n2 ) and can be efficiently enumerated.

Lemma 1. Let ≻ be a profile and let ≻′w be any misreport for a fixed woman w. Then, there exists a list ≻′′w ∈ Rw that achieves the same matching, i.e., µ′′ = µ′ , where µ′ := DA(≻-w,≻′w ) and µ′′ := DA(≻-w,≻′′w ).

Next consider the transition ≻w→≻∗ in Figure 1. For this step, man m is the only misreporting agent. We define ̂≻m as the list obtained by promoting m's original match, namely µ(m), to the top of his original list ≻m, and define Rm := {̂≻m} ∪ {̂≻w′ ↑ m : w′ ̸= µ(m)} as the set consisting of the list ̂≻m as well as all preference lists that are obtained by individually pushing up each woman other than µ(m) to the top position in the list ̂≻m. Further, we say that an arbitrary misreport ≻′m is feasible if m matches with µ(m) under ≻′ := {≻-{m,w},≻′m,≻∗w }. In Lemma 2, we show that for an arbitrary feasible misreport by the accomplice, there exists another feasible list in Rm that results in the same partner for w. Thus, we can assume that ≻∗m ∈ Rm. Again, observe that the set Rm is of polynomial size O(n).

Lemma 2. Let ≻ be a profile and let ≻′w and ≻′m be any misreports for a fixed pair (m, w) such that µ′ (m) = µ(m), where µ := DA(≻) and µ′ := DA(≻-{m,w},≻′m,≻′w ). Then, there exists a list ≻′′m ∈ Rm such that µ′′ (m) = µ(m) and µ′′ (w) = µ′ (w), where µ′′ := DA(≻-{m,w},≻′′m,≻′w ).

Although the lists in sets Rm and Rw are not necessarily inconspicuous versions of the true lists ≻m and ≻w, respectively, we have been able to identify nominally-sized sets of misreports Rm and Rw that are sufficient to check, leading to a simple algorithm for finding an optimal pair manipulation strategy: Enumerate the sets Rm and Rw, evaluate the DA outcome for each possible ≻′m∈ Rm, ≻′w ∈ Rw pair, and return the strategy that gives the best match for the woman w without regret for the accomplice m; see Algorithm 1.

Theorem 1. An optimal pair manipulation can be computed in O(n5 ) time.

Remark 1. In Example 5 in [Hosseini et al., 2022], we show that optimal pair manipulation could fail to be stabilitypreserving. Thus, an unrestricted pair manipulation (i.e., when the manipulated matching is not required to be stable with respect to true preferences) can be strictly better than an optimal stability-preserving pair manipulation.

4 One for All: Helping All Women Through a Single Accomplice

Let us now consider a different generalization of accomplice manipulation which we call "one for all" manipulation where a single accomplice (man m) misreports in order to improve the outcome for all women in W. Recall that due to the noregret assumption, the manipulated match of the accomplice m is the same as his true match. As we are interested in improving a group of agents, it will be helpful to define the notions of Pareto improvement and Pareto optimal strategies.

Pareto optimal and optimal strategies. Let ≻ be the true preference profile and let µ := DA(≻). We say that a strategy ≻′m of the accomplice Pareto improves another strategy ≻′′m if µ′ ⪰W µ′′ and µ′ (w) ≻w µ′′ (w) for some w ∈ W, where µ′ := DA(≻-m,≻′m) and µ′′ := DA(≻-m,≻′′m). A strategy ≻′m is Pareto optimal if µ′ ⪰W µ and there is no other strategy ≻′′m that Pareto improves ≻′m. Further, a strategy ≻′m is optimal if µ′ ⪰W µ and for any other strategy ≻′′m, we have µ′ ⪰W µ′′ . Thus, given a Pareto optimal strategy, any other strategy that improves some woman must make some other woman worse off, while the outcome under an optimal strategy simply cannot be improved for any woman. Similarly, we say that a matching µ′ := DA(≻-m,≻′m) is "Pareto optimal" (respectively, "optimal") if the corresponding strategy ≻′m is Pareto optimal (respectively, optimal). Note that an optimal strategy is also Pareto optimal. The finiteness of the strategy space implies that a Pareto optimal strategy is guaranteed to exist. Whether an optimal strategy also always exists is not immediately clear; however, if an optimal strategy exists, then the set of Pareto optimal matchings-the Pareto frontier-must be a singleton, consisting only of the optimal matching. There can be multiple optimal strategies, but all such strategies must induce the same optimal matching.

Let us now proceed to analyzing the structure of (Pareto) optimal strategies. When an accomplice manipulates on behalf of a single beneficiary woman (i.e., "one for one"), it is known that there always exists an optimal strategy that is inconspicuous [Hosseini et al., 2021]. By contrast, when an accomplice misreports on behalf of multiple women (i.e., "one for all"), an inconspicuous strategy may no longer be optimal (Example 2).

Example 2 (Inconspicuous strategy can be suboptimal).

Consider the following preference profile where the DA outcome is underlined.

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

Suppose the accomplice is m1 and all women are beneficiaries. The DA matching after m1 submits the optimal noregret manipulated list ≻′m1 := w2 ≻ w4 ≻ w1 ≻ w3 ≻ w5 is marked by "∗". Notice that ≻′m1 is derived from ≻m1

by pushing up w2 and w4 and therefore is not inconspicuous. The manipulation results in the women-optimal matching, where all women are matched with their top choices.

There is no inconspicuous strategy that m1 (or any other man for that matter) can report to produce the same matching; indeed, if m1 were to push up only w2, then only w2 and w3 would improve, and if he were to push up only w4, then only w4 and w5 would improve. This observation highlights the conflict between optimality and inconspicuousness when the set of beneficiaries consists of all women.

Our main result in this section is that an optimal strategy for the accomplice is guaranteed to exist and computable in polynomial time (Theorem 2). In the full version [Hosseini et al., 2022], we prove a stronger result: Among all optimal strategies, we can efficiently compute one that promotes the smallest number of women in accomplice's list.

4.1 Computing an Optimal Strategy

Recall from Proposition 2 that even if each man m arbitrarily permutes the part of his list above and below his DA-partner µ(m), the DA outcome remains unchanged. This result shows that any strategy of the accomplice m, without loss of generality, can be expressed in terms of only push up and push down operations, where a set of women is pushed above the DA partner µ(m), and another disjoint set of women is pushed below µ(m). We will now provide a structural simplification: Any matching obtained by a combination of push up and push down operations in the accomplice's list can be weakly improved for all women by the push up operation alone.

Proposition 3. Let ≻ be a profile. For any fixed man m and any subsets X ⊆ W and Y ⊆ W of women who are ranked below and above µ(m), respectively, let ≻′ := {≻-m,≻X↑ m } denote the profile after pushing up the set X and let ≻′′ := {≻-m, ≻X↑,Y ↓ m } denote the profile after pushing up X and pushing down Y in the true preference list ≻m of man m. Then, µ′ ⪰W µ′′ , where µ′ := DA(≻′ ) and µ′′ := DA(≻′′ ).

Having established that push up operations suffice, let us now examine which subset of women the accomplice should push up. Given a profile ≻ and an accomplice m, define the no-regret set W NR := {w ∈ W :≻′ := {≻-m,≻w↑ m } is a no-regret profile} as the set of all women who do not cause m to incur regret when pushed up individually, and its complement with-regret set W R :=W \W NR .

We will first show that pushing up any subset of no-regret women does not cause regret for the accomplice (Lemma 3).

Lemma 3. Let ≻ be a profile and let µ := DA(≻). For any subset Y ⊆W NR , let ≻Y := {≻-m,≻Y ↑ m } denote the preference profile after pushing up the set Y in the true preference list ≻m of man m, and let µY := DA(≻Y ). Then, m does not incur regret under ≻Y , i.e., µY (m) = µ(m).

In contrast to Lemma 3, any subset Y ⊆ W that contains at least one woman from the with-regret set (i.e., Y ∩W R ̸= ∅) causes regret for the man m (Lemma 4).

Lemma 4. Let w′ ∈ W R and let Y ⊆ W be such that w′ ∈ Y . Then, m incurs regret under ≻Y := {≻-m,≻Y ↑ m }, i.e., µ(m) ≻m µY (m), where µY := DA(≻Y ).

Together, Lemmas 3 and 4 imply that a push up operation is no-regret if and only if the pushed-up set is a subset of W NR . Thus, an optimal (or Pareto optimal) strategy should promote some subset of W NR . This observation, however, does not automatically provide an efficient algorithm for computing the desired strategy because brute force enumeration of subsets of W NR could take exponential time. Also, in case an optimal strategy does not exist, the Pareto frontier of strategies can be exponential in size, again ruling out exhaustive search.

Our main result of this section (Theorem 2) alleviates both of the above concerns. We show that not only does an optimal strategy always exist, but also that pushing up the entire noregret set W NR achieves such an outcome.

Theorem 2. An optimal one-for-all strategy for the accomplice is to push up the no-regret set W NR in his true list.

Our proof of Theorem 2 leverages the following known result which says that the matching resulting from a no-regret push up operation is weakly preferred by all women.

Proposition 4 ([Hosseini et al., 2021]). 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 µ′ ∈ S≻ and thus µ′ ⪰W µ and µ ⪰M µ′ .

Proof. (of Theorem2) FromProposition 2, we know that any accomplice manipulation can be simulated via push up and push down operations. Proposition 3 shows that any combination of push up and push down operations can be weakly improved for all women by push up only. From Lemma 4, we know that the desired push up set, say Y ⊆ W, should not contain any woman from the with-regret set W R. Therefore, Y ⊆ W NR . From Lemma 3, we know that pushing up Y satisfies no-regret assumption. If Y ̸= W NR (thus, Y ⊂ W NR ), then Proposition 4 shows that ≻Y := {≻-m,≻Y ↑ m } can be weakly improved for all women by additionally pushing up the women in W NR \Y . Thus, pushing up all women in W NR gives an optimal no-regret accomplice manipulation strategy for helping all women, as desired.

Theorem 2 readily gives a polynomial-time algorithm for computing an optimal strategy (Corollary 1).

Corollary 1. An optimal one-for-all strategy for the accomplice can be computed in O(n3 ) time.

Although pushing up the entire no-regret set W NR is optimal (Theorem 2), the accomplice may want to displace as few women as possible in order to remain close to his true preference list. In the full version [Hosseini et al., 2022], we provide a polynomial-time algorithm for computing a minimum optimal strategy (i.e., one that promotes the smallest number of women). We also show that the size of the promoted set is at most ⌊ n-1 2 ⌋ and that this bound is tight.

5 Experimental Results

Let us now experimentally compare the two-sided and onesided models in terms of the fraction of instances where each model improves upon truthful reporting. In our experimental setup, the preferences of n men and n women are drawn Number of men/women (n)

uniformly at random. 1 For each value of n ∈ {4, 6, . . . , 20}, we independently sample 1000 preference profiles. For the two-for-one part, we compute the fraction of instances where some man m can jointly misreport with a fixed woman w to improve her match, and compare it with the analogous fraction where only one of m (accomplice) or w (self) can misreport; see Figure 2 (left). Similarly, for the one-for-all part, we compute the fraction of instances where some man can misreport to help all women (i.e., weakly improve all and strictly improve some compared to their true matches), and compare it with the analogous fraction where a woman helps all women; see Figure 2 (right). Figure 2 shows that twosided strategies are more frequently available than one-sided; in roughly 2% more instances under the two-for-one setting and roughly 10%more instances under the one-for-all. In the full version [Hosseini et al., 2022], we show that two-sided manipulation outperforms one-sided in terms of the extent of improvement for the beneficiary/beneficiaries, i.e., the difference between the ranks of old and new matched partner(s).

6 Concluding Remarks

We studied two coalitional generalizations of two-sided manipulation of the DA algorithm. Moving from single-agent to coalitional manipulation impacted the structure of optimal strategies in the form of loss of inconspicuousness, but we showed that efficient computation can still be achieved. Going forward, it will be interesting to consider manipulation by arbitrary coalitions of men and women. Another relevant direction could be to interpret two-sided manipulation as a bribery problem [Faliszewski et al., 2009; Boehmer et al., 2021] wherein there is a cost associated with each pairwise swap in an agent's true list. Finally, extensions of our work to more general preference models (e.g., partial orders), as well as experimental evaluation on non-uniform distributions or real-world data, will also be of interest.

Acknowledgments

We thank the anonymous reviewers for helpful comments. HH acknowledges support from NSF IIS grants #2144413, #2052488, and #2107173. RV acknowledges support from DST INSPIRE grant no. DST/INSPIRE/04/2020/000107.

1 The assumption about uniformly random preferences is quite common in the literature on strategic aspects of stable matchings; see, for example, [Teo et al., 2001; Kojima et al., 2013; Immorlica and Mahdian, 2015; Aziz et al., 2015; Ashlagi et al., 2017].