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

Hadi Hosseini  Pennsylvania State University
<EMAIL_ADDRESS>Fatima Umar  Rochester Institute of Technology
<EMAIL_ADDRESS>Rohit Vaish  Indian Institute of Technology Delhi
<EMAIL_ADDRESS>
###### Abstract

Strategic behavior in two-sided matching markets has been traditionally
studied in a “one-sided” manipulation setting where the agent who misreports
is also the intended beneficiary. Our work investigates “two-sided”
manipulation of the deferred acceptance algorithm where the misreporting agent
and the manipulator (or beneficiary) are on different sides. Specifically, we
generalize the recently proposed _accomplice manipulation_ model (where a man
misreports on behalf of a woman) along two complementary dimensions: (a) the
_two for one_ model, with a pair of misreporting agents (man and woman) and a
single beneficiary (the misreporting woman), and (b) the _one for all_ model,
with one misreporting agent (man) and a coalition of beneficiaries (all
women).

Our main contribution is to develop polynomial-time algorithms for finding an
optimal manipulation in both settings. We obtain these results despite the
fact that an optimal _one for all_ strategy fails to be _inconspicuous_ ,
while it is unclear whether an optimal _two for one_ strategy satisfies the
inconspicuousness property. We also study the conditions under which stability
of the resulting matching is preserved. Experimentally, we show that two-sided
manipulations are more frequently available and offer better quality matches
than their one-sided counterparts.

##  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ğlu et al., 2005a, b) and _entry-level 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, b; Teo et al., 2001; Vaish and
Garg, 2017).

By contrast, there are many real-world settings that, in essence, resemble
“two-sided” manipulations where the misreporting agent and the beneficiary are
on _different_ sides. For example, in the student-proposing 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 (Banerjee and
Johari, 2019), 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 (e.g., demanding additional IDs or enforcing zoning).

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, b; Demange et al., 1987; Kobayashi and Matsui, 2009, 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.

Who misreports? | Who benefits? | Results for optimal manipulation | Reference
---|---|---|---
Inconspicuous? | Poly-time? | Stability-preserving?
Woman $w$ |  Woman $w$ | ✓ | ✓ | ✓ | Vaish and Garg (2017)
Man $m$ |  Woman $w$ | ✓ | ✓ | ✓ | Hosseini et al. (2021)
Man $m$ and woman $w$ |  Woman $w$ | Open | ✓ | ✗ | This paper
Man $m$ | All women | ✗ | ✓ | ✓ | This paper
Table 1: Summary of previously known (top two rows) and new results (bottom
two rows).

#### 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 than
either of the optimal individual (i.e., self or accomplice) manipulation
strategies (1). In contrast to both 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 (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 fact, we show a
stronger result 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 the size of the promoted set (Section C.5).

  * •

Experiments: We show via simulations on uniformly random preferences that two-
sided strategies are more frequently available (Figure 2) and result in better
quality matches (Appendix D) than one-sided strategies.

#### 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, 2007)
and for a coalition of women (Kobayashi and Matsui, 2009, 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 $\langle M,W,\succ\rangle$, where $M$ is a set of $n$ men, $W$ is a
set of $n$ women, and $\succ$ is a preference profile which specifies the
preference lists of the agents. The preference list of a man $m\in M$, denoted
by $\succ_{m}$, is a strict total order over all women in $W$. The list
$\succ_{w}$ of a woman $w\in W$ is defined analogously. We will write
$w_{1}\succeq_{m}w_{2}$ to denote “either $w_{1}\succ_{m}w_{2}$ or
$w_{1}=w_{2}$”, and write $\succ_{-m}$ to denote the profile without the list
of man $m$; thus, $\succ=\\{\succ_{-m},\succ_{m}\\}$.

#### Stable matching.

A _matching_ is a function $\mu:M\cup W\rightarrow M\cup W$ such that
$\mu(m)\in W$ for all $m\in M$, $\mu(w)\in M$ for all $w\in W$, and $\mu(m)=w$
if and only if $\mu(w)=m$. Given a matching $\mu$, a _blocking pair_ with
respect to the preference profile $\succ$ is a man-woman pair $(m,w)$ who
prefer each other over their assigned partners, i.e., $w\succ_{m}\mu(m)$ and
$m\succ_{w}\mu(w)$. A matching is said to be _stable_ if it does not have any
blocking pair. We will write $S_{\succ}$ to denote the set of all stable
matchings with respect to $\succ$. Note that in the worst case, the size of
$S_{\succ}$ can be exponential in $n$ (Knuth, 1997).

For any pair of matchings $\mu,\mu^{\prime}$, we will write
$\mu\succeq_{M}\mu^{\prime}$ to denote that all men weakly prefer $\mu$ over
$\mu^{\prime}$, i.e., $\mu(m)\succeq_{m}\mu^{\prime}(m)$ for all $m\in M$
(analogously $\mu\succeq_{W}\mu^{\prime}$ 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 $\succ$ as
input, the matching computed by the DA algorithm, which we will denote by
$\texttt{DA}(\succ)$, is stable. Furthermore, this matching is _men-optimal_
as it assigns to each man his favorite partner among all stable matchings in
$S_{\succ}$. Subsequently, it was observed that the same matching is also
_women-pessimal_ (McVitie and Wilson, 1971).

######  Proposition 1 (Gale and Shapley, 1962; McVitie and Wilson, 1971).

Let $\succ$ be a profile and let ${\mu\coloneqq\texttt{DA}(\succ)}$. Then,
$\mu\in S_{\succ}$. Furthermore, for any $\mu^{\prime}\in S_{\succ}$,
$\mu\succeq_{M}\mu^{\prime}$ and $\mu^{\prime}\succeq_{W}\mu$.

#### Self manipulation.

Given a profile $\succ$ and the matching $\mu\coloneqq\texttt{DA}(\succ)$, we
say that woman $w$ can _self manipulate_ if there exists a list
$\succ^{\prime}_{w}$ (which is a _permutation_ of $w$’s true list $\succ_{w}$)
such that $\mu^{\prime}(w)\succ_{w}\mu(w)$, where
$\mu^{\prime}\coloneqq\texttt{DA}(\succ_{-w},\succ^{\prime}_{w})$. An
_optimal_ self manipulation $\succ^{\prime}_{w}$ is one for which there is no
other list $\succ^{\prime\prime}_{w}$ such that
$\mu^{\prime\prime}(w)\succ_{w}\mu^{\prime}(w)$, where
$\mu^{\prime\prime}\coloneqq\texttt{DA}(\succ_{-w},\succ^{\prime\prime}_{w})$.

#### Accomplice manipulation.

A different model of strategic behavior is _accomplice manipulation_ , wherein
a woman $w$, instead of misreporting herself, asks a man $m$ to misreport his
preference in order to improve $w$’s match (Bendlin and Hosseini, 2019;
Hosseini et al., 2021). Formally, given a profile $\succ$ and a fixed man $m$,
we say that woman $w$ can _manipulate via accomplice_ $m$ if there exists a
list $\succ^{\prime}_{m}$ for man $m$ (which is a permutation of his true list
$\succ_{m}$) such that $\mu^{\prime}(w)\succ_{w}\mu(w)$, where
$\mu\coloneqq\texttt{DA}(\succ)$ and
$\mu^{\prime}\coloneqq\texttt{DA}(\succ_{-m},\succ^{\prime}_{m})$. An
_optimal_ accomplice manipulation $\succ^{\prime}_{m}$ is one for which there
is no other list $\succ^{\prime\prime}_{m}$ such that
$\mu^{\prime\prime}(w)\succ_{w}\mu^{\prime}(w)$, where
$\mu^{\prime\prime}\coloneqq\texttt{DA}(\succ_{-m},\succ^{\prime\prime}_{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 (a) 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., $\mu^{\prime}(m)\succeq_{m}\mu(m)$.

Interestingly, for both generalizations mentioned above, the no-regret
assumption implies that the accomplice’s match stays the same, i.e.,
$\mu(m)=\mu^{\prime}(m)$. Indeed, in the one-for-all problem, it follows from
the strategyproofness of DA algorithm for the proposing side that
$\mu(m)\succeq_{m}\mu^{\prime}(m)$. Along with the no-regret assumption, this
implies $\mu(m)=\mu^{\prime}(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
$\mu(m)=\mu^{\prime}(m)$.

#### Inconspicuous manipulation.

A misreported list (or _strategy_) $\succ^{\prime}_{m}$ for an accomplice $m$
is said to be _inconspicuous_ if it can be derived from his true list
$\succ_{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 $\succ_{w}$.

#### Push up and push down operations

For any man $m\in M$, let $\succ^{L}_{m}$ and $\succ^{R}_{m}$ denote the parts
of $m$’s list above and below his DA partner, respectively. That is,
$\succ_{m}=(\succ^{L}_{m},\mu(m),\succ^{R}_{m})$. We say that man $m$ _pushes
up_ a set $X\subseteq W$ if the new list is
$\succ^{X\uparrow}_{m}\coloneqq(\succ^{L}_{m}\cup
X,\mu(m),\succ^{R}_{m}\setminus X)$. Similarly, _pushing down_ a set
$Y\subseteq W$ results in
$\succ^{Y\downarrow}_{m}\coloneqq(\succ^{L}_{m}\setminus
Y,\mu(m),\succ^{R}_{m}\cup Y)$. Note that the exact positions at which agents
in $X$ (or $Y$) are placed above (or below) $\mu(m)$ is not important, as long
as the sets are appropriately pushed above (or below) $\mu(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 $\mu(m)$.

######  Proposition 2 (Huang, 2006).

Let $\succ$ be a profile and let $\mu\coloneqq\texttt{DA}(\succ)$. For any man
$m\in M$ with true list $\succ_{m}=(\succ^{L}_{m},\mu(m),\succ^{R}_{m})$, let
${\succ^{\prime}_{m}\coloneqq(\pi^{L}(\succ^{L}_{m}),\mu(m),\pi^{R}(\succ^{R}_{m}))}$,
where $\pi^{L}$ and $\pi^{R}$ are arbitrary permutations. Let
$\mu^{\prime}\coloneqq\texttt{DA}(\succ_{-m},\succ^{\prime}_{m})$. Then,
$\mu^{\prime}=\mu$.

All omitted proofs are in the Appendix.

##  3 Two for One: Helping a Single Woman 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 (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 “${m_{1}}:w_{5}\ w_{3}\ w_{4}\ w_{2}$ $w_{1}$” denotes that
$m_{1}$’s top choice is $w_{5}$, second choice is $w_{3}$, and so on.

$\boldsymbol{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{m_{1}}}}\colon$ |  $w_{5}$ |  $\underline{w_{3}^{*}}$ |  $w_{4}$ |  $w_{2}$ |  $w_{1}$ |  |  $\boldsymbol{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{w_{1}}}}\colon$ |  $m_{3}^{*}$ |  $\underline{m_{4}}$ |  $m_{5}$ |  $m_{1}$ |  $m_{2}$
---|---|---|---|---|---|---|---|---|---|---|---|---
${m_{2}}\colon$ |  $\underline{w_{4}^{*}}$ |  $w_{1}$ |  $w_{5}$ |  $w_{3}$ |  $w_{2}$ |  |  ${w_{2}}\colon$ |  $m_{1}$ |  $\underline{m_{5}^{*}}$ |  $m_{3}$ |  $m_{2}$ |  $m_{4}$
${m_{3}}\colon$ |  $\underline{w_{5}}$ |  $w_{4}$ |  $w_{1}^{*}$ |  $w_{2}$ |  $w_{3}$ |  |  ${w_{3}}\colon$ |  $m_{5}$ |  $m_{4}$ |  $m_{3}$ |  $m_{2}$ |  $\underline{m_{1}^{*}}$
${m_{4}}\colon$ |  $\underline{w_{1}}$ |  $w_{4}$ |  $w_{5}^{*}$ |  $w_{2}$ |  $w_{3}$ |  |  ${w_{4}}\colon$ |  $\underline{m_{2}^{*}}$ |  $m_{5}$ |  $m_{3}$ |  $m_{1}$ |  $m_{4}$
${m_{5}}\colon$ |  $\underline{w_{2}^{*}}$ |  $w_{4}$ |  $w_{3}$ |  $w_{1}$ |  $w_{5}$ |  |  ${w_{5}}\colon$ |  $m_{5}$ |  $m_{2}$ |  $m_{4}^{*}$ |  $\underline{m_{3}}$ |  $m_{1}$

Suppose the manipulating pair is $(m_{1},w_{1})$. Since $m_{4}$ is the only
man who proposes to $w_{1}$ during the execution of DA algorithm on this
profile, it follows that there is no beneficial self manipulation strategy for
$w_{1}$.

To find an optimal accomplice manipulation for $m_{1}$, it suffices to focus
on inconspicuous strategies (Hosseini et al., 2021). It is straightforward to
verify that promoting any woman below $w_{3}$ in $m_{1}$’s list does not
result in a better match for $w_{1}$. In fact, none of the other men can give
$w_{1}$ a better partner via no-regret manipulation.

The DA matching when $m_{1}$ and $w_{1}$ jointly misreport with
$\succ^{\prime}_{m_{1}}\coloneqq w_{1}\succ w_{5}\succ w_{3}\succ w_{4}\succ
w_{2}$ and $\succ^{\prime}_{w_{1}}\coloneqq m_{3}\succ m_{5}\succ m_{1}\succ
m_{4}\succ m_{2}$ is marked by “$*$”. Note that the strategic woman $w_{1}$ is
now able to match with her top choice without worsening the match of the
accomplice $m_{1}$. ∎∎

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 1, an optimal pair
manipulation may exist despite there being no beneficial accomplice nor self
manipulations. Further, 3 in Section B.1 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 Section B.4 in the Appendix, 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
$\succ^{*}_{m}$ and $\succ^{*}_{w}$ denote the respective lists of $m$ and $w$
under an optimal pair manipulation, and let
$\succ^{*}\coloneqq(\succ_{-\\{m,w\\}},\succ^{*}_{m},\succ^{*}_{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 $\succ$ to the pair manipulation profile
$\succ^{*}$ in two steps: First, swap $w$’s list in $\succ$ to obtain the
intermediate profile $\succ^{w}\coloneqq\\{\succ_{-w},\succ^{*}_{w}\\}$, and
then swap $m$’s list in $\succ^{w}$ to get $\succ^{*}$; see Figure 1. We will
show that this two-step approach allows us to impose additional structure on
the individual strategies $\succ^{*}_{m}$ and $\succ^{*}_{w}$.

$\succ$$\succ^{*}$$\succ^{w}=\\{\succ_{-w},\succ^{*}_{w}\\}$$\succ_{w}\rightarrow\,\succ^{*}_{w}$$\succ_{m}\rightarrow\,\succ^{*}_{m}$
Figure 1: Preference profiles under pair manipulation.

Let us start by analyzing woman $w$’s strategy $\succ^{*}_{w}$. Consider the
transition $\succ\rightarrow\,\succ^{w}$ in Figure 1, where $w$ is the only
misreporting agent. Let $S_{w}$ denote the set of preference lists that can be
obtained from $w$’s true list $\succ_{w}$ by moving some pair of men to the
top two positions, i.e.,

$S_{w}\coloneqq\\{(m_{i},\,m_{j},\,{\succ_{w}\setminus\\{m_{i},m_{j}\\}}):m_{i},m_{j}\in
M\\}.$

In Lemma 1, we show that for an _arbitrary_ misreport by $w$, there exists a
list in $S_{w}$ that creates the same matching for _all_ agents. Thus, it
follows that $\succ^{*}_{w}\,\in S_{w}$. Observe that the set $S_{w}$ is of
polynomial size $\mathcal{O}(n^{2})$ and can be efficiently enumerated.

######  Lemma 1.

Let $\succ$ be a profile and let $\succ^{\prime}_{w}$ be any misreport for a
fixed woman $w$. Then, there exists a list ${\succ^{\prime\prime}_{w}\,\in
S_{w}}$ that achieves the same matching, i.e.,
$\mu^{\prime\prime}=\mu^{\prime}$, where
$\mu^{\prime}\coloneqq\texttt{DA}(\succ_{-w},\succ^{\prime}_{w})$ and
$\mu^{\prime\prime}\coloneqq\texttt{DA}(\succ_{-w},\succ^{\prime\prime}_{w})$.

Next consider the transition $\succ^{w}\rightarrow\,\succ^{*}$ in Figure 1.
For this step, man $m$ is the only misreporting agent. We define
$\widehat{\succ}_{m}$ as the list obtained by promoting $m$’s original match,
namely $\mu(m)$, to the top of his original list $\succ_{m}$, and define
$S_{m}\coloneqq\\{\widehat{\succ}_{m}\\}\cup\\{\widehat{\succ}_{m}^{w^{\prime}\uparrow}:w^{\prime}\neq\mu(m)\\}$
as the set consisting of the list $\widehat{\succ}_{m}$ as well as all
preference lists that are obtained by individually pushing up each woman other
than $\mu(m)$ to the top position in the list $\widehat{\succ}_{m}$. Further,
we say that an arbitrary misreport $\succ^{\prime}_{m}$ is _feasible_ if $m$
matches with $\mu(m)$ under
$\succ^{\prime}\coloneqq\\{\succ_{-\\{m,w\\}},\succ^{\prime}_{m},\succ^{*}_{w}\\}$.
In Lemma 2, we show that for an _arbitrary_ feasible misreport by the
accomplice, there exists another feasible list in $S_{m}$ that results in the
same partner for $w$. Thus, we can assume that $\succ^{*}_{m}\,\in S_{m}$.
Again, observe that the set $S_{m}$ is of polynomial size $\mathcal{O}(n)$.

######  Lemma 2.

Let $\succ$ be a profile and let $\succ^{\prime}_{w}$ and $\succ^{\prime}_{m}$
be any misreports for a fixed pair $(m,w)$ such that $\mu^{\prime}(m)=\mu(m)$,
where $\mu\coloneqq\texttt{DA}(\succ)$ and
$\mu^{\prime}\coloneqq(\succ_{-\\{m,w\\}},\succ^{\prime}_{m},\succ^{\prime}_{w})$.
Then, there exists a list $\succ^{\prime\prime}_{m}\ \in S_{m}$ such that
$\mu^{\prime\prime}(m)=\mu(m)$ and $\mu^{\prime\prime}(w)=\mu^{\prime}(w)$,
where
$\mu^{\prime\prime}\coloneqq\texttt{DA}(\succ_{-\\{m,w\\}},\succ^{\prime\prime}_{m},\succ^{\prime}_{w})$.

Although the lists in sets $S_{m}$ and $S_{w}$ are not necessarily
inconspicuous versions of the true lists $\succ_{m}$ and $\succ_{w}$,
respectively, we have been able to identify nominally-sized sets of misreports
$S_{m}$ and $S_{w}$ that are sufficient to check, leading to a simple
algorithm for finding an optimal pair manipulation strategy: Enumerate the
sets $S_{m}$ and $S_{w}$, evaluate the DA outcome for each possible
$\succ^{\prime}_{m}\in S_{m},\succ^{\prime}_{w}\in S_{w}$ pair, and return the
strategy that gives the best match for the woman $w$ without causing regret
for the accomplice $m$; see Algorithm 1.

Algorithm 1 Computing an optimal pair manipulation

1:Profile $\succ$, accomplice $m$, beneficiary $w$

2:Optimal pair manipulations $\succ^{*}_{m}$ and $\succ^{*}_{w}$

3:Initialize
$(\mu^{*},\succ^{*}_{m},\succ^{*}_{w})\leftarrow(\mu\coloneqq\texttt{DA}(\succ),\succ_{m},\succ_{w})$

4:Compute $S_{w}$

5:for each $\succ^{\prime}_{w}\in S_{w}$ do

6: Compute $S_{m}$

7: for each $\succ^{\prime}_{m}\in S_{m}$ do

8:
$\mu^{\prime}\leftarrow\texttt{DA}(\succ_{-\\{m,w\\}},\succ^{\prime}_{m},\succ^{\prime}_{w})$

9: if $\mu^{\prime}(w)\succ_{w}\mu^{*}(w)$ and $\mu^{\prime}(m)=\mu(m)$ then

10: Update
$(\mu^{*},\succ^{*}_{m},\succ^{*}_{w})\leftarrow(\mu^{\prime},\succ^{\prime}_{m},\succ^{\prime}_{w})$

11:return $\succ^{*}_{m}$ and $\succ^{*}_{w}$

######  Theorem 1.

An optimal pair manipulation can be computed in $\mathcal{O}(n^{5})$ time.

######  Remark 1.

In 5 in the Appendix, we show that optimal pair manipulation could fail to be
_stability-preserving_. 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 no-regret 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 $\succ$ be the true preference profile and let
$\mu\coloneqq\texttt{DA}(\succ)$. We say that a strategy $\succ^{\prime}_{m}$
of the accomplice _Pareto improves_ another strategy
$\succ^{\prime\prime}_{m}$ if $\mu^{\prime}\succeq_{W}\mu^{\prime\prime}$ and
$\mu^{\prime}(w)\succ_{w}\mu^{\prime\prime}(w)$ for some $w\in W$, where
$\mu^{\prime}\coloneqq\texttt{DA}(\succ_{-m},\succ^{\prime}_{m})$ and
$\mu^{\prime\prime}\coloneqq\texttt{DA}(\succ_{-m},\succ^{\prime\prime}_{m})$.
A strategy $\succ^{\prime}_{m}$ is _Pareto optimal_ if
$\mu^{\prime}\succeq_{W}\mu$ and there is no other strategy
$\succ^{\prime\prime}_{m}$ that Pareto improves $\succ^{\prime}_{m}$. Further,
a strategy $\succ^{\prime}_{m}$ is _optimal_ if $\mu^{\prime}\succeq_{W}\mu$
and for any other strategy $\succ^{\prime\prime}_{m}$, we have
$\mu^{\prime}\succeq_{W}\mu^{\prime\prime}$. 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
$\mu^{\prime}\coloneqq\texttt{DA}(\succ_{-m},\succ^{\prime}_{m})$ is “Pareto
optimal” (respectively, “optimal”) if the corresponding strategy
$\succ^{\prime}_{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 (2).

######  Example 2 (Inconspicuous strategy can be suboptimal).

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

$\boldsymbol{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{m_{1}}}}\colon$ |  $\underline{w_{1}^{*}}$ |  $w_{2}$ |  $w_{3}$ |  $w_{4}$ |  $w_{5}$ |  |  ${w_{1}}\colon$ |  $\underline{m_{1}^{*}}$ |  $m_{2}$ |  $m_{3}$ |  $m_{4}$ |  $m_{5}$
---|---|---|---|---|---|---|---|---|---|---|---|---
${m_{2}}\colon$ |  $\underline{w_{2}}$ |  $w_{3}^{*}$ |  $w_{4}$ |  $w_{5}$ |  $w_{1}$ |  |  ${w_{2}}\colon$ |  $m_{3}^{*}$ |  $m_{4}$ |  $m_{5}$ |  $m_{1}$ |  $\underline{m_{2}}$
${m_{3}}\colon$ |  $\underline{w_{3}}$ |  $w_{2}^{*}$ |  $w_{1}$ |  $w_{5}$ |  $w_{4}$ |  |  ${w_{3}}\colon$ |  $m_{2}^{*}$ |  $m_{5}$ |  $m_{4}$ |  $m_{1}$ |  $\underline{m_{3}}$
${m_{4}}\colon$ |  $\underline{w_{4}}$ |  $w_{5}^{*}$ |  $w_{1}$ |  $w_{2}$ |  $w_{3}$ |  |  ${w_{4}}\colon$ |  $m_{5}^{*}$ |  $m_{3}$ |  $m_{2}$ |  $m_{1}$ |  $\underline{m_{4}}$
${m_{5}}\colon$ |  $\underline{w_{5}}$ |  $w_{4}^{*}$ |  $w_{3}$ |  $w_{2}$ |  $w_{1}$ |  |  ${w_{5}}\colon$ |  $m_{4}^{*}$ |  $m_{2}$ |  $m_{3}$ |  $\underline{m_{5}}$ |  $m_{1}$

Suppose the accomplice is $m_{1}$ and all women are beneficiaries. The DA
matching after $m_{1}$ submits the optimal no-regret manipulated list
$\succ^{\prime}_{m_{1}}\coloneqq w_{2}\succ w_{4}\succ w_{1}\succ w_{3}\succ
w_{5}$ is marked by “$*$”. Notice that $\succ^{\prime}_{m_{1}}$ is derived
from $\succ_{m_{1}}$ by pushing up $w_{2}$ and $w_{4}$ 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 $m_{1}$ (or any other man for that
matter) can report to produce the same matching; indeed, if $m_{1}$ were to
push up only $w_{2}$, then only $w_{2}$ and $w_{3}$ would improve, and if he
were to push up only $w_{4}$, then only $w_{4}$ and $w_{5}$ 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 can be computed in polynomial time
(Theorem 2). In fact, we will show a stronger result: Among all optimal
strategies, we can efficiently compute one that promotes the _smallest_ number
of women in the accomplice’s list (Theorem 3 in Section C.5).

###  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 $\mu(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
$\mu(m)$, and another disjoint set of women is pushed below $\mu(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 $\succ$ be a profile. For any fixed man $m$ and any subsets $X\subseteq W$
and $Y\subseteq W$ of women who are ranked below and above $\mu(m)$,
respectively, let
$\succ^{\prime}\coloneqq\\{\succ_{-m},\succ_{m}^{X\uparrow}\\}$ denote the
profile after pushing up the set $X$ and let
$\succ^{\prime\prime}\coloneqq\\{\succ_{-m},\succ_{m}^{X\uparrow,Y\downarrow}\\}$
denote the profile after pushing up $X$ and pushing down $Y$ in the true
preference list $\succ_{m}$ of man $m$. Then,
$\mu^{\prime}\succeq_{W}\mu^{\prime\prime}$, where
$\mu^{\prime}\coloneqq\texttt{DA}(\succ^{\prime})$ and
$\mu^{\prime\prime}\coloneqq\texttt{DA}(\succ^{\prime\prime})$.

Having established that push up operations alone do not suffice, let us now
examine _which_ subset of women the accomplice should push up. Given a profile
$\succ$ and an accomplice $m$, define the _no-regret set_
$W^{\textsc{NR}}\coloneqq\\{w\in
W\,:\,\succ^{\prime}\coloneqq\\{\succ_{-m},\succ_{m}^{w\uparrow}\\}\text{ 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^{\textsc{R}}\coloneqq W\setminus W^{\textsc{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 $\succ$ be a profile and let $\mu\coloneqq\texttt{DA}(\succ)$. For any
subset $Y\subseteq W^{\textsc{NR}}$, let
$\succ^{Y}\coloneqq\\{\succ_{-m},\succ_{m}^{Y\uparrow}\\}$ denote the
preference profile after pushing up the set $Y$ in the true preference list
$\succ_{m}$ of man $m$, and let $\mu^{Y}\coloneqq\texttt{DA}(\succ^{Y})$.
Then, $m$ does not incur regret under $\succ^{Y}$, i.e., $\mu^{Y}(m)=\mu(m)$.

In contrast to Lemma 3, any subset $Y\subseteq W$ that contains at least one
woman from the with-regret set (i.e., $Y\cap W^{\textsc{R}}\neq\emptyset$)
causes regret for the man $m$ (Lemma 4).

######  Lemma 4.

Let $w^{\prime}\in W^{\textsc{R}}$ and let $Y\subseteq W$ be such that
$w^{\prime}\in Y$. Then, $m$ incurs regret under
$\succ^{Y}\coloneqq\\{\succ_{-m},\succ_{m}^{Y\uparrow}\\}$, i.e.,
$\mu(m)\succ_{m}\mu^{Y}(m)$, where $\mu^{Y}\coloneqq\texttt{DA}(\succ^{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^{\textsc{NR}}$. Thus, an optimal
(or Pareto optimal) strategy should promote some subset of $W^{\textsc{NR}}$.
This observation, however, does not automatically provide an efficient
algorithm for computing the desired strategy because brute force enumeration
of subsets of $W^{\textsc{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 no-regret set $W^{\textsc{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^{\textsc{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 $\succ$ be a preference profile and let
${\mu\coloneqq\texttt{DA}(\succ)}$. For any man $m$, let
$\succ^{\prime}\coloneqq\\{\succ_{-m},\succ_{m}^{X\uparrow}\\}$ and
$\mu^{\prime}\coloneqq\texttt{DA}(\succ^{\prime})$. If $m$ does not incur
regret, then $\mu^{\prime}\in S_{\succ}$ and thus $\mu^{\prime}\succeq_{W}\mu$
and $\mu\succeq_{M}\mu^{\prime}$.

###### Proof.

(of Theorem 2) From Proposition 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\subseteq W$, should not contain any woman from the with-
regret set $W^{R}$. Therefore, $Y\subseteq W^{\textsc{NR}}$. From Lemma 3, we
know that pushing up $Y$ satisfies no-regret assumption. If $Y\neq
W^{\textsc{NR}}$ (thus, $Y\subset W^{\textsc{NR}}$), then Proposition 4 shows
that $\succ^{Y}\coloneqq\\{\succ_{-m},\succ_{m}^{Y\uparrow}\\}$ can be weakly
improved for all women by additionally pushing up the women in
$W^{\textsc{NR}}\setminus Y$. Thus, pushing up all women in $W^{\textsc{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
$\mathcal{O}(n^{3})$ time.

Although pushing up the entire no-regret set $W^{\textsc{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 Section C.5, 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 $\lfloor\frac{n-1}{2}\rfloor$ and that this bound
is tight (Section C.11).

##  5 Experimental Results

Let us now experimentally compare the two-sided and one-sided models in terms
of the _fraction of instances_ where each model improves upon truthful
reporting. To this end, we will consider an experimental setup where the
preferences of $n$ men and $n$ women are drawn uniformly at random.111The
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). For each value of $n\in\\{4,6,\dots,20\\}$, we
independently sample $1\,000$ 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: Comparing one-sided and two-sided strategies for helping a _single_
woman (left) and for helping _all_ women (right) in terms of the fraction of
instances where a (Pareto) improvement is possible over truthful reporting.

Figure 2 shows that two-sided strategies are _more frequently available_ than
one-sided; specifically, in roughly $2\%$ more instances under the two-for-one
setting and roughly $10\%$ more instances under the one-for-all. In Appendix
D, 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 preference data, will also be of
interest.

## Acknowledgments

Hadi Hosseini acknowledges support from NSF IIS grants #2052488 and #2107173.

## References

  * Abdulkadiroğlu et al. (2005a) Atila Abdulkadiroğlu, Parag A Pathak, and Alvin E Roth.  The New York City High School Match.  American Economic Review, 95(2):364–367, 2005.
  * Abdulkadiroğlu et al. (2005b) Atila Abdulkadiroğlu, Parag A Pathak, Alvin E Roth, and Tayfun Sönmez.  The Boston Public School Match.  American Economic Review, 95(2):368–371, 2005.
  * Ashlagi et al. (2017) Itai Ashlagi, Yash Kanoria, and Jacob D Leshno.  Unbalanced Random Matching Markets: The Stark Effect of Competition.  Journal of Political Economy, 125(1):69–98, 2017.
  * Aziz et al. (2015) Haris Aziz, Hans Georg Seedig, and Jana Karina von Wedel.  On the Susceptibility of the Deferred Acceptance Algorithm.  In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, pages 939–947, 2015.
  * Banerjee and Johari (2019) Siddhartha Banerjee and Ramesh Johari.  Ride Sharing.  In Sharing Economy, pages 73–97. Springer, 2019.
  * Bendlin and Hosseini (2019) Theodora Bendlin and Hadi Hosseini.  Partners in Crime: Manipulating the Deferred Acceptance Algorithm through an Accomplice.  In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 9917–9918, 2019.
  * Boehmer et al. (2021) Niclas Boehmer, Robert Bredereck, Klaus Heeger, and Rolf Niedermeier.  Bribery and Control in Stable Marriage.  Journal of Artificial Intelligence Research, 71:993–1048, 2021\.
  * Demange et al. (1987) Gabrielle Demange, David Gale, and Marilda Sotomayor.  A Further Note on the Stable Matching Problem.  Discrete Applied Mathematics, 16(3):217–222, 1987.
  * Dubins and Freedman (1981) Lester E Dubins and David A Freedman.  Machiavelli and the Gale-Shapley Algorithm.  The American Mathematical Monthly, 88(7):485–494, 1981.
  * Faliszewski et al. (2009) Piotr Faliszewski, Edith Hemaspaandra, and Lane A Hemaspaandra.  How Hard is Bribery in Elections?  Journal of Artificial Intelligence Research, 35:485–532, 2009.
  * Gale and Shapley (1962) David Gale and Lloyd S Shapley.  College Admissions and the Stability of Marriage.  The American Mathematical Monthly, 69(1):9–15, 1962.
  * Gale and Sotomayor (1985a) David Gale and Marilda Sotomayor.  Ms. Machiavelli and the Stable Matching Problem.  The American Mathematical Monthly, 92(4):261–268, 1985.
  * Gale and Sotomayor (1985b) David Gale and Marilda Sotomayor.  Some Remarks on the Stable Matching Problem.  Discrete Applied Mathematics, 11(3):223–232, 1985.
  * Gonczarowski and Friedgut (2013) Yannai A Gonczarowski and Ehud Friedgut.  Sisterhood in the Gale-Shapley Matching Algorithm.  The Electronic Journal of Combinatorics, 20(2):P12, 2013.
  * Gusfield and Irving (1989) Dan Gusfield and Robert W Irving.  The Stable Marriage Problem: Structure and Algorithms.  MIT press, 1989.
  * Hatfield et al. (2016) John William Hatfield, Fuhito Kojima, and Yusuke Narita.  Improving Schools through School Choice: A Market Design Approach.  Journal of Economic Theory, 166:186–211, 2016.
  * Hosseini et al. (2021) Hadi Hosseini, Fatima Umar, and Rohit Vaish.  Accomplice Manipulation of the Deferred Acceptance Algorithm.  In Proceedings of the 30th International Joint Conference on Artificial Intelligence, pages 231–237, 2021.
  * Huang (2006) Chien-Chung Huang.  Cheating by Men in the Gale-Shapley Stable Matching Algorithm.  In Proceedings of the 14th Annual European Symposium on Algorithms, pages 418–431, 2006.
  * Huang (2007) Chien-Chung Huang.  Cheating to Get Better Roommates in a Random Stable Matching.  In Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science, pages 453–464, 2007.
  * Immorlica and Mahdian (2015) Nicole Immorlica and Mohammad Mahdian.  Incentives in Large Random Two-Sided Markets.  ACM Transactions on Economics and Computation (TEAC), 3(3):1–25, 2015.
  * Knuth (1997) Donald Knuth.  Stable Marriage and its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms, volume 10.  American Mathematical Society, 1997.
  * Kobayashi and Matsui (2009) Hirotatsu Kobayashi and Tomomi Matsui.  Successful Manipulation in Stable Marriage Model with Complete Preference Lists.  IEICE Transactions on Information and Systems, 92(2):116–119, 2009\.
  * Kobayashi and Matsui (2010) Hirotatsu Kobayashi and Tomomi Matsui.  Cheating Strategies for the Gale-Shapley Algorithm with Complete Preference Lists.  Algorithmica, 58(1):151–169, 2010.
  * Kojima et al. (2013) Fuhito Kojima, Parag A Pathak, and Alvin E Roth.  Matching with Couples: Stability and Incentives in Large Markets.  The Quarterly Journal of Economics, 128(4):1585–1632, 2013.
  * Manlove (2013) David Manlove.  Algorithmics of Matching under Preferences, volume 2.  World Scientific, 2013.
  * McVitie and Wilson (1971) David G McVitie and Leslie B Wilson.  The Stable Marriage Problem.  Communications of the ACM, 14(7):486–490, 1971.
  * Roth and Peranson (1999) Alvin E Roth and Elliott Peranson.  The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design.  American Economic Review, 89(4):748–780, 1999.
  * Roth and Rothblum (1999) Alvin E Roth and Uriel G Rothblum.  Truncation Strategies in Matching Markets—In Search of Advice for Participants.  Econometrica, 67(1):21–43, 1999.
  * Roth and Sotomayor (1992) Alvin E Roth and Marilda Sotomayor.  Two-Sided Matching.  Handbook of Game Theory with Economic Applications, 1:485–541, 1992\.
  * Roth (1982) Alvin E Roth.  The Economics of Matching: Stability and Incentives.  Mathematics of Operations Research, 7(4):617–628, 1982.
  * Roth (2002) Alvin E Roth.  The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics.  Econometrica, 70(4):1341–1378, 2002.
  * Roth (2008) Alvin E Roth.  Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions.  International Journal of Game Theory, 36(3):537–569, 2008.
  * Satterthwaite and Sonnenschein (1981) Mark A Satterthwaite and Hugo Sonnenschein.  Strategy-Proof Allocation Mechanisms at Differentiable Points.  The Review of Economic Studies, 48(4):587–597, 1981.
  * Shen et al. (2021) Weiran Shen, Yuan Deng, and Pingzhong Tang.  Coalitional Permutation Manipulations in the Gale-Shapley Algorithm.  Artificial Intelligence, 301:103577, 2021.
  * Teo et al. (2001) Chung-Piaw Teo, Jay Sethuraman, and Wee-Peng Tan.  Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications.  Management Science, 47(9):1252–1267, 2001.
  * Thomson (2016) William Thomson.  Non-Bossiness.  Social Choice and Welfare, 47(3):665–696, 2016.
  * Vaish and Garg (2017) Rohit Vaish and Dinesh Garg.  Manipulating Gale-Shapley Algorithm: Preserving Stability and Remaining Inconspicuous.  In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 437–443, 2017.

Appendix

##  Appendix A Useful Results from Prior Work

For ease of reference, we recall the notation of push up and push down
operations below.

#### Push up and push down operations

For any man $m\in M$, let $\succ^{L}_{m}$ and $\succ^{R}_{m}$ denote the parts
of $m$’s list above and below his DA partner, respectively. That is,
$\succ_{m}=(\succ^{L}_{m},\mu(m),\succ^{R}_{m})$. We say that man $m$ _pushes
up_ a set $X\subseteq W$ if the new list is
$\succ^{X\uparrow}_{m}\coloneqq(\succ^{L}_{m}\cup
X,\mu(m),\succ^{R}_{m}\setminus X)$. Similarly, _pushing down_ a set
$Y\subseteq W$ results in
$\succ^{Y\downarrow}_{m}\coloneqq(\succ^{L}_{m}\setminus
Y,\mu(m),\succ^{R}_{m}\cup Y)$. Note that the exact positions at which agents
in $X$ (or $Y$) are placed above (or below) $\mu(m)$ is not important, as long
as the sets are appropriately pushed above (or below) $\mu(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 $\mu(m)$
(Proposition 2).

We now present several useful known results.

######  Proposition 5 (Dubins and Freedman, 1981; Huang, 2006).

Let $\succ$ be a preference profile and let $\mu\coloneqq\texttt{DA}(\succ)$.
For any fixed man $m$ and any subset $X\subseteq W$ of women who are ranked
above $\mu(m)$ in $\succ_{m}$, let
${\succ^{\prime}\coloneqq\\{\succ_{-m},\succ_{m}^{X\downarrow}\\}}$ denote the
preference profile after pushing down the women in $X$ in the true preference
list $\succ_{m}$ of man $m$, and let
$\mu^{\prime}\coloneqq\texttt{DA}(\succ^{\prime})$. Then,
$\mu^{\prime}\succeq_{M}\mu$ and $\mu^{\prime}(m)=\mu(m)$.

######  Proposition 6 (Gonczarowski and Friedgut, 2013).

Let $W^{*}\subseteq W$ be a set of manipulating women. If no woman in $W^{*}$
is strictly worse off after the misreport, then all women (including those not
in $W^{*}$) are weakly better off and all men are weakly worse off after the
manipulation.

######  Proposition 7 (Hosseini et al., 2021).

Let $\succ$ be a preference profile and let $\mu\coloneqq\texttt{DA}(\succ)$.
For any fixed man $m$ and any subset $X\subseteq W$ of women who are ranked
above $\mu(m)$ in $\succ_{m}$, let
${\succ^{\prime}\coloneqq\\{\succ_{-m},\succ_{m}^{X\downarrow}\\}}$ denote the
preference profile after pushing down the women in $X$ in the true preference
list $\succ_{m}$ of man $m$, and let
$\mu^{\prime}\coloneqq\texttt{DA}(\succ^{\prime})$. Then,
$\mu\succeq_{W}\mu^{\prime}$.

######  Proposition 8 (Hosseini et al., 2021).

Let $\succ$ be a preference profile and let
${\mu\coloneqq\texttt{DA}(\succ)}$. For any fixed man $m$ and any subset
$X\subseteq W$ of women who are ranked below $\mu(m)$ in $\succ_{m}$, let
$\succ^{X}\coloneqq\\{\succ_{-m},\succ_{m}^{X\uparrow}\\}$ denote the
preference profile after pushing up the women in $X$ in the true preference
list $\succ_{m}$ of man $m$, and let
${\mu^{X}\coloneqq\texttt{DA}(\succ^{X})}$. If $m$ incurs regret (i.e., if
$\mu(m)\succ_{m}\mu^{X}(m)$), then $\mu^{X}(m)\in X$.

######  Proposition 9 (Hosseini et al., 2021).

Let $\succ$ be a preference profile and let $\mu\coloneqq\texttt{DA}(\succ)$.
For any fixed man $m$ and any subset $X\subseteq W$ of women who are ranked
below $\mu(m)$ in $\succ_{m}$, let
$\succ^{\prime}\coloneqq\\{\succ_{-m},\succ_{m}^{X\uparrow}\\}$ denote the
preference profile after pushing up the women in $X$ in the true preference
list $\succ_{m}$ of man $m$, and let
$\mu^{\prime}\coloneqq\texttt{DA}(\succ^{\prime})$. If $m$ does not incur
regret (i.e., if $\mu^{\prime}(m)=\mu(m)$), then for every $w_{x}\in X$, $m$
does not incur regret under the matching
$\mu^{x}\coloneqq\texttt{DA}(\succ^{x})$, where
$\succ^{x}\coloneqq\\{\succ_{-m},\succ_{m}^{w_{x}\uparrow}\\}$.

######  Proposition 10 (Hosseini et al., 2021).

Let $\succ$ be a preference profile and let $\mu\coloneqq\texttt{DA}(\succ)$.
For any fixed man $m$ and any subset $X\subseteq W$ of women who are ranked
below $\mu(m)$ in $\succ_{m}$, let
$\succ^{\prime}\coloneqq\\{\succ_{-m},\succ_{m}^{X\uparrow}\\}$ denote the
preference profile after pushing up the women in $X$ in the true preference
list $\succ_{m}$ of man $m$, and let
$\mu^{\prime}\coloneqq\texttt{DA}(\succ^{\prime})$. If $m$ does not incur
regret (i.e., if $\mu^{\prime}(m)=\mu(m)$) and
$\mu(w^{\prime})\succ_{w^{\prime}}m$ for all $w^{\prime}\in X$, where
$\mu^{\prime}\coloneqq\texttt{DA}(\succ^{\prime})$, then $\mu^{\prime}=\mu$.

######  Proposition 11 (Hosseini et al., 2021).

Let $\succ$ be a preference profile and let $\mu\coloneqq\texttt{DA}(\succ)$.
For any man $m$ and any subset $X\subseteq W$ of women who are ranked below
$\mu(m)$ in $\succ_{m}$, let
$\succ^{\prime}\coloneqq\\{\succ_{-m},\succ_{m}^{X\uparrow}\\}$ denote the
preference profile after pushing up the women in $X$ in the true preference
list $\succ_{m}$ of man $m$, and let
$\mu^{\prime}\coloneqq\texttt{DA}(\succ^{\prime})$. If $m$ does not incur
regret (i.e., if $\mu^{\prime}(m)=\mu(m)$) and $\mu^{\prime}\neq\mu$, then
there exist at least two distinct women $w^{\prime},w^{\prime\prime}\in W$
such that $\mu^{\prime}(w^{\prime})\succ_{w^{\prime}}\mu(w^{\prime})$ and
$\mu^{\prime}(w^{\prime\prime})\succ_{w^{\prime\prime}}\mu(w^{\prime\prime})$,
and at least two distinct men $m^{\prime},m^{\prime\prime}\in M$ such that
$\mu(m^{\prime})\succ_{m^{\prime}}\mu^{\prime}(m^{\prime})$ and
$\mu(m^{\prime\prime})\succ_{m^{\prime\prime}}\mu^{\prime}(m^{\prime\prime})$.

######  Proposition 12 (Hosseini et al., 2021).

Let $\succ$ be a preference profile and let
${\mu\coloneqq\texttt{DA}(\succ)}$. For any fixed man $m$ and any subset
$X\subseteq W$ of women who are ranked below $\mu(m)$ in $\succ_{m}$, let
$\succ^{\prime}\coloneqq\\{\succ_{-m},\succ_{m}^{X\uparrow}\\}$ denote the
preference profile after pushing up the women in $X$ in the true preference
list $\succ_{m}$ of man $m$, and let
$\mu^{\prime}\coloneqq\texttt{DA}(\succ^{\prime})$. If $m$ does not incur
regret (i.e., if $\mu^{\prime}(m)=\mu(m)$), then the set of proposals that
occur under $\succ$ is contained within the set of proposals that occur under
$\succ^{\prime}$.

######  Proposition 13 (Hosseini et al., 2021).

Let $X\coloneqq\\{w_{a},w_{b},w_{c},\dots\\}$ be an arbitrary finite set of
women that the accomplice $m$ can push up without incurring regret. Then, any
proposal that occurs under $\succ^{X}$ also occurs under at least one of the
profiles $\succ^{a},\succ^{b},\succ^{c},\dots$, where
$\succ^{x}\coloneqq\\{\succ_{-m},\succ^{w_{x}\uparrow}\\}$ denotes the
preference profile after pushing up $w_{x}$ in the true preference list
$\succ_{m}$ of man $m$ for every $w_{x}\in X$.

######  Proposition 14 (Hosseini et al., 2021).

For some fixed man $m$, let ${X\subseteq W}$ be a set of women that $m$ can
push up (with or without incurring regret). Then, the match for some fixed
woman $w$ that is obtained by pushing up all women in $X$ can also be obtained
by pushing up exactly one woman in $X$.

##  Appendix B Omitted Material from Section 3

###  B.1 Concatenating Optimal Self and Optimal Accomplice Strategies Can Be
Harmful

As discussed in Section 3.1, 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. Unfortunately, as we
show in 3 below, the woman’s match may _worsen_ by naively combining the
respective individual strategies.222Our example’s message of “coordination is
key” is reminiscent of a similar observation by Shen et al. (2021, Sec 3.1) in
the context of one-sided manipulation by a coalition of women. They showed
that naively combining optimal self-manipulation strategies for the
individuals may actually be detrimental for the coalition.

######  Example 3 (Optimal self + Optimal accomplice $\neq$ Optimal pair
manipulation).

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

$\boldsymbol{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{m_{1}}}}\colon$ |  $\underline{w_{4}^{a}}$ |  $w_{3}^{s}$ |  $w_{1}$ |  $w_{2}^{*}$ |  $w_{5}$ |  |  $\boldsymbol{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{w_{1}}}}\colon$ |  $m_{3}^{s}$ |  $m_{1}$ |  $m_{5}^{a}$ |  $\underline{m_{4}}$ |  $m_{2}^{*}$
---|---|---|---|---|---|---|---|---|---|---|---|---
${m_{2}}\colon$ |  $w_{1}^{*}$ |  $w_{3}$ |  $\underline{w_{2}^{s}}$ |  $w_{5}^{a}$ |  $w_{4}$ |  |  ${w_{2}}\colon$ |  $m_{4}^{a}$ |  $m_{3}$ |  $m_{1}^{*}$ |  $\underline{m_{2}^{s}}$ |  $m_{5}$
${m_{3}}\colon$ |  $\underline{w_{3}^{a}}^{,*}$ |  $w_{1}^{s}$ |  $w_{5}$ |  $w_{2}$ |  $w_{4}$ |  |  ${w_{3}}\colon$ |  $m_{1}^{s}$ |  $\underline{m_{3}^{a}}^{,*}$ |  $m_{2}$ |  $m_{4}$ |  $m_{5}$
${m_{4}}\colon$ |  $\underline{w_{1}}$ |  $w_{5}^{s,*}$ |  $w_{2}^{a}$ |  $w_{3}$ |  $w_{4}$ |  |  ${w_{4}}\colon$ |  $m_{2}$ |  $m_{5}^{s,*}$ |  $\underline{m_{1}^{a}}$ |  $m_{3}$ |  $m_{4}$
${m_{5}}\colon$ |  $w_{3}$ |  $\underline{w_{5}}$ |  $w_{1}^{a}$ |  $w_{4}^{s,*}$ |  $w_{2}$ |  |  ${w_{5}}\colon$ |  $m_{2}^{a}$ |  $m_{4}^{s,*}$ |  $\underline{m_{5}}$ |  $m_{1}$ |  $m_{3}$

Suppose the manipulating pair is $(m_{1},w_{1})$. The DA matching after
$m_{1}$ submits the optimal no-regret accomplice manipulated list
$\succ^{\prime}_{m_{1}}\coloneqq w_{2}\succ w_{4}\succ w_{3}\succ w_{1}\succ
w_{5}$ is marked by “$a$”, and the one where $w_{1}$ submits the optimal self
manipulated list $\succ^{\prime}_{w_{1}}\coloneqq m_{3}\succ m_{2}\succ
m_{1}\succ m_{5}\succ m_{4}$ is marked by “$s$”. Additionally, the DA matching
after both submit $\succ^{\prime}_{m_{1}}$ and $\succ^{\prime}_{w_{1}}$
simultaneously is marked by “$*$”.

Notice that the accomplice $m_{1}$ and the strategic woman $w_{1}$ are both
strictly worse off under joint manipulation, and truthful reporting by the
pair $(m_{1},w_{1})$ is strictly better for the woman compared to the
concatenation strategy.∎∎

###  B.2 Proof of Lemma 1

We will start by presenting a result that shows that any misreport by a woman
that leaves her matched with the same man as before has no effect on the final
matching (Lemma 5).

######  Lemma 5.

Let $\succ$ be a preference profile and let $\mu\coloneqq\texttt{DA}(\succ)$.
For any woman $w$, let
$\succ^{\prime}\coloneqq\\{\succ_{-w},\succ^{\prime}_{w}\\}$ denote the
preference profile after $w$ misreports her preferences and let
$\mu^{\prime}\coloneqq\texttt{DA}(\succ^{\prime})$. If
$\mu^{\prime}(w)=\mu(w)$, then $\mu^{\prime}=\mu$.

###### Proof.

Suppose, for contradiction, that $\mu^{\prime}(w)=\mu(w)$ and
$\mu^{\prime}(w^{\prime})\neq\mu(w^{\prime})$ for some $w^{\prime}\in
W\setminus\\{w\\}$. Since $w$’s partner does not change after misreporting, it
follows from Proposition 6 that
$\mu^{\prime}(w^{\prime})\succeq_{w^{\prime}}\mu(w^{\prime})$. Further, since
$\mu^{\prime}(w^{\prime})\neq\mu(w^{\prime})$ and the preferences are strict,
we have that $\mu^{\prime}(w^{\prime})\succ_{w^{\prime}}\mu(w^{\prime})$ for
some $w^{\prime}\in W\setminus\\{w\\}$. Since $w^{\prime}$ is truthful, she
must receive a proposal during the execution of DA algorithm on
$\succ^{\prime}$ that she does not under $\succ$; thus
$P_{\succ^{\prime}\setminus\succ}\neq\emptyset$. Without loss of generality,
suppose $(m^{\prime},w^{\prime})$ is the _first_ proposal in
$P_{\succ^{\prime}\setminus\succ}$ to occur during the DA execution on
$\succ^{\prime}$.

Since men propose in decreasing order of their preference and it is assumed
that $(m^{\prime},w^{\prime})\notin P_{\succ}$ and
$\succ^{\prime}_{m^{\prime}}=\ \succ_{m^{\prime}}$, it must be that
$m^{\prime}$ was rejected by $w^{\prime\prime}\coloneqq\mu(m^{\prime})$ under
$\succ^{\prime}$ before proposing to $w^{\prime}$. Then, $w^{\prime\prime}$
must have received a proposal from some man, say $m^{\prime\prime}$, such that
$m^{\prime\prime}\succ^{\prime}_{w^{\prime\prime}}m^{\prime}$. Since
$m^{\prime}$ is matched with $w^{\prime\prime}$ under $\mu$ but not under
$\mu^{\prime}$, we infer that $w^{\prime\prime}$ must be truthful; indeed, the
strategic woman retains her $\mu$-partner under $\mu^{\prime}$. Thus, in
particular,
$m^{\prime\prime}\succ^{\prime}_{w^{\prime\prime}}m^{\prime}\implies
m^{\prime\prime}\succ_{w^{\prime\prime}}m^{\prime}$.

We had assumed $(m^{\prime},w^{\prime})$ to be the first proposal during the
DA execution on $\succ^{\prime}$ to not belong to $P_{\succ}$. Since
$(m^{\prime\prime},w^{\prime\prime})$ occurs before $(m^{\prime},w^{\prime})$
under $\succ^{\prime}$, we must have that
$(m^{\prime\prime},w^{\prime\prime})$ also occurs under $\succ$. Thus, under
the execution of DA algorithm on $\succ$, $w^{\prime\prime}$ receives a better
proposal from $m^{\prime\prime}$ but ends up getting matched with
$m^{\prime}$. This contradicts the correctness of DA algorithm. Hence, we must
have that $\mu^{\prime}=\mu$. ∎

######  Remark 2 (Strategyproofness and non-bossiness).

In addition to its role in the proof of Lemma 1, we note that Lemma 5 offers
an important insight: The DA algorithm is _non-bossy_ for women. A mechanism
is said to be non-bossy if no agent can misreport in a way that changes the
allocation of other agents without changing his or her own match
(Satterthwaite and Sonnenschein, 1981; Thomson, 2016). In two-sided matching,
non-bossiness—similar to strategyproofness—can be defined for each side of the
market separately.

From Lemma 5, we know that a woman cannot influence the outcome of any other
agent without changing her own match. By contrast, a man can influence the
outcome of another agent (a woman) without changing his own match, as
evidenced by no-regret accomplice manipulation model (Bendlin and Hosseini,
2019; Hosseini et al., 2021). Combining these observations with the known
results for strategyproofness of the DA algorithm (Dubins and Freedman, 1981;
Roth, 1982), we obtain that:

  * •

For men, the DA algorithm is strategyproof but fails to be non-bossy, while

  * •

For women, the DA algorithm is not strategyproof but satisfies non-bossiness.∎

We now present Proposition 15—which is due to Vaish and Garg (2017)—that
outlines the effect that swapping any pair of adjacent men in a woman’s
preference list has on her final partner. It will be helpful to define the
notation $\textup{{Prop}}(w,\succ)$ that denotes the set of all men who
propose to $w$ during the run of DA algorithm on $\succ$. Further,
$\textup{{Prop}}(w,\succ,i)$ denotes the $i^{\text{th}}$ favorite man of $w$
(according to $w$’s list $\succ$, namely $\succ_{w}$) in the set
$\textup{{Prop}}(w,\succ)$. Thus, ${\textup{{Prop}}(w,\succ,1)=\mu(w)}$ where
${\mu\coloneqq\texttt{DA}(\succ)}$. The set of non-proposing men is denoted by
${\textup{{Non-Prop}}(w,\succ)}$, i.e., $\textup{{Non-Prop}}(w,\succ)\coloneqq
M\setminus\textup{{Prop}}(w,\succ)$.

######  Proposition 15 (Vaish and Garg, 2017).

Let $\succ$ and $\succ^{\prime}$ be two preference profiles differing only in
the preferences of a fixed woman $w$, and let $\mu=\texttt{DA}(\succ)$ and
$\mu^{\prime}=\texttt{DA}(\succ^{\prime})$. Let $\succ^{\prime}_{w}$ be
derived from $\succ_{w}$ by swapping the positions of an adjacent pair of men
$(m_{i},m_{j})$ and making no other changes. Then,

  1. 1.

if $m_{i}\in\textup{{Non-Prop}}(w,\succ)$ or $m_{j}\in\textup{{Non-
Prop}}(w,\succ)$, then $\mu^{\prime}(w)=\mu(w)$,

  2. 2.

if
$m_{i},m_{j}\notin\\{\textup{{Prop}}(w,\succ,1),\textup{{Prop}}(w,\succ,2)\\}$,
then $\mu^{\prime}(w)=\mu(w)$.

  3. 3.

if $m_{i}=\textup{{Prop}}(w,\succ,2)$ and $m_{j}=\textup{{Prop}}(w,\succ,3)$,
then $\mu^{\prime}(w)\in\\{\mu(w),m_{j}\\}$.

  4. 4.

if $m_{i}=\textup{{Prop}}(w,\succ,1)$ and $m_{j}=\textup{{Prop}}(w,\succ,2)$,
then $\textup{{Prop}}(w,\succ^{\prime},2)\in\\{m_{i},m_{j}\\}$.

In words, the matched partner remains the same when at least one of the
swapped agents is a non-proposer (case 1), or when neither of the swapped
agents is the first or the second-best proposer (case 2). When swapping the
second and third-best proposers, the matched partner can either stay the same
or worsen (with respect to true preferences). Further, when the first and the
second-best proposers are swapped, there can be at most one new proposal that
is better than the old partner (with respect to the true preference list).

######  Remark 3.

Note that whenever Proposition 15 guarantees that $\mu^{\prime}(w)=\mu(w)$
(e.g., in cases 1 and 2), then by Lemma 5, we can, in fact, infer that
$\mu^{\prime}=\mu$. Furthermore, since men’s preferences stay unchanged
between $\succ$ and $\succ^{\prime}$, the entire set of proposals during the
execution of DA algorithm also remains unchanged between $\succ$ and
$\succ^{\prime}$.

Before proving our next result (Lemma 1), we recall that the set $S_{w}$
denotes the set of preference lists that can be obtained from $w$’s true list
by moving exactly two men to the top. Although the lists in $S_{w}$ are _not
necessarily inconspicuous_ , we note that the proof of this result relies
heavily on that of Theorem 4 in Vaish and Garg (2017), which shows that the
partner a woman achieves via an _optimal_ misreport can also be achieved using
an inconspicuous list.

$\succ^{\prime}_{w}$$\vdots$$p$$\vdots$$q$$\vdots$$\vdots$$\succ^{(1)}_{w}$$\vdots$$p$$q$$\vdots$$\vdots$$\vdots$$\succ^{(2)}_{w}$$p$$q$$\vdots$$\vdots$$\vdots$$\vdots$$\succ^{(k)}_{w}$$p$$q$$\vdots$$\vdots$$m_{j}$$m_{i}$$\vdots$$\succ^{(k+1)}_{w}$$p$$q$$\vdots$$\vdots$$m_{i}$$m_{j}$$\vdots$$\succ^{(\ell)}_{w}=\succ^{\prime\prime}_{w}$$p$$q$$\vdots$$\vdots$$\vdots$$\vdots$
resembles $\succ_{w}$ except for $\\{p,q\\}$ ……
---
Figure 3: The sequence of preference lists constructed in the proof of Lemma 1
(based on a similar construction in Theorem 4 in Vaish and Garg (2017)). Here,
$p\coloneqq\textup{{Prop}}(w,\succ^{\prime},1)=\mu^{\prime}(w)$ and
$q\coloneqq\textup{{Prop}}(w,\succ^{\prime},2)$.

See 1

###### Proof.

Our proof of Lemma 1 closely follows that of Theorem 4 in Vaish and Garg
(2017), which showed that the partner a woman can achieve by an _optimal_
misreport can also be achieved using an inconspicuous list. For the sake of
completeness, we recall parts of their argument below with the necessary
modifications to establish Lemma 1.

Due to Lemma 5, it suffices to show that there exists some list
$\succ^{\prime\prime}_{w}\,\in S_{w}$ such that
$\mu^{\prime\prime}(w)=\mu^{\prime}(w)$, where
$\mu^{\prime\prime}\coloneqq\texttt{DA}(\succ_{-w},\succ^{\prime\prime}_{w})$.

For the profile $\succ^{\prime}\coloneqq\\{\succ_{-w},\succ^{\prime}_{w}\\}$,
let $p\coloneqq\textup{{Prop}}(w,\succ^{\prime},1)$ and
$q\coloneqq\textup{{Prop}}(w,\succ^{\prime},2)$ denote the favorite and
second-favorite proposers of $w$ (with respect to the list
$\succ^{\prime}_{w}$) during the execution of DA algorithm on
$\succ^{\prime}$. Thus, $p=\mu^{\prime}(w)$.

Starting from the true list $\succ_{w}$, let $\succ^{\prime\prime}_{w}$ be the
preference list obtained by promoting $p$ to the top and then placing the man
$q$ in the position immediately below $p$. Notice that
$\succ^{\prime\prime}_{w}\,\in S_{w}$.

In the remainder of the proof, we will show that the misreported list
$\succ^{\prime}_{w}$ can be transformed into $\succ^{\prime\prime}_{w}$ by a
sequence of _massaging_ operations (involving swaps of adjacent pairs of men)
such that the man $p=\mu^{\prime}(w)$ continues to propose to $w$ at each
intermediate step of the transformation. Further, we will argue that $p$ is
the _best_ proposal that $w$ receives with respect to each intermediate list
(which ensures that $p$ remains the DA partner of $w$ at each intermediate
step). Note that proving this would imply that
$\mu^{\prime\prime}(w)=\mu^{\prime}(w)$.

We will first describe the transformation of $\succ^{\prime}_{w}$ into
$\succ^{\prime\prime}_{w}$ followed by arguing that doing so maintains the
property that $p$ will propose to $w$, and importantly, that $p$ will continue
to be the DA partner of $w$ for each intermediate matching.

  1. 1.

_Constructing $\succ^{\prime\prime}_{w}$_: Starting with $\succ^{\prime}_{w}$,
we construct a sequence of preference lists
$\succ^{(1)}_{w},\succ^{(2)}_{w},\dots,\succ^{(\ell)}_{w}$ that terminates
with $\succ^{\prime\prime}_{w}$, i.e.,
$\succ^{\prime\prime}_{w}\,=\,\succ^{(\ell)}_{w}$ (see Figure 3):

    1. (a)

_Moving $q$ next to $p$_: We create the list $\succ^{(1)}_{w}$ from
$\succ^{\prime}_{w}$ by moving $q$ to the position right below $p$. Since all
men who are ranked between $p$ and $q$ in the list $\succ^{\prime}_{w}$ must
be non-proposers under $\succ^{\prime}$, it follows from case (1) of
Proposition 15 that $\mu^{\prime}(w)=\mu^{(1)}(w)$, where
$\mu^{(1)}\coloneqq\texttt{DA}(\succ_{-w},\succ^{(1)}_{w})$. Further, by
Remark 3, the set of proposals under the DA algorithm on the profiles $\succ$
and $\succ^{(1)}$ is exactly the same, implying that
$\textup{{Prop}}(w,\succ^{(1)},1)=p$ and
${\textup{{Prop}}(w,\succ^{(1)},2)=q}$. Note that any man above $p$ in the
list $\succ^{(1)}_{w}$ must still be a non-proposer.

    2. (b)

_Promoting $p$ and $q$_: In this step, starting from the list
$\succ^{(1)}_{w}$, we promote $p$ to the top rank position and $q$ to the
second rank position. Since $p$ is $w$’s favorite proposer according to
$\succ^{(1)}_{w}$, no man above $p$ could have proposed to her under
$\succ^{\prime}$ or $\succ^{(1)}$. Thus, we are only required to swap a
proposer with a non-proposer at each step, which, by case (1) of Proposition
15, does not affect $w$’s match, and thus, by Remark 3, also does not affect
the run of DA algorithm. We call the resulting preference list
$\succ^{(2)}_{w}$. Clearly, ${\textup{{Prop}}(w,\succ^{(2)},1)=p}$ and
${\textup{{Prop}}(w,\succ^{(2)},2)=q}$, where
${\succ^{(2)}\coloneqq\\{\succ_{-w},\succ^{(2)}_{w}\\}}$.

    3. (c)

_Fixing the part of the list below $q$_: The final step in our construction
involves a sequence of preference lists
$\\{\succ^{(3)}_{w},\succ^{(4)}_{w},\dots\\}$. The list $\succ^{(k+1)}_{w}$ is
derived from $\succ^{(k)}_{w}$ by _swapping_ a pair of adjacent men
$(m_{i},m_{j})$ in $\succ^{(k)}_{w}$ such that:

      1. (i)

$\textup{{Prop}}(w,\succ^{(k)},2)\succ^{(k)}_{w}m_{i}$ and
$\textup{{Prop}}(w,\succ^{(k)},2)\succ^{(k)}_{w}m_{j}$, and

      2. (ii)

$m_{i}\,\succ_{w}\,m_{j}$ and $m_{j}\,\succ^{(k)}_{w}\,m_{i}$.

That is, each new list in the sequence is derived from the previous list by
swapping a pair of adjacent men who are (i) both positioned below the second-
favorite proposer according to the previous list, and (ii) are incorrectly
ordered with respect to the true preference list $\succ_{w}$. No other changes
are made. Notice that this sequence of preference lists must be finite since
there can only be a finite number of pairs of men who are incorrectly ordered
with respect to the true list. Let $\succ^{(\ell)}_{w}$ be the final list in
this sequence, and let
${\succ^{(k)}\coloneqq\\{\succ_{-w},\succ^{(k)}_{w}\\}}$ and
${\mu^{(k)}=\texttt{DA}(\succ^{(k)})}$ denote the preference profile and the
corresponding DA matching at each step. This finishes the construction of the
sequence of preference lists.

  2. 2.

_Correctness_ : It follows from the above construction that the list
$\succ^{(\ell)}_{w}$ can be obtained from the true list $\succ_{w}$ by
promoting $p$ to the top and then placing $q$ to the position right below $p$,
while making no other changes. Indeed, steps 1(a) and 1(b) secure the
positions of $p$ and $q$ at the top of $\succ^{(\ell)}_{w}$, while step 1(c)
incrementally corrects for pairs that are out of order with respect to
$\succ_{w}$ and eventually terminates with a list $\succ^{(\ell)}_{w}$ that is
identical to $\succ_{w}$ with the exception of the positions of men $p$ and
$q$.

Now, we must show that
$\textup{{Prop}}(w,\succ^{(\ell)},1)=\mu^{(\ell)}(w)=p$. We do so using
induction. The base case consists of showing that $\mu^{(3)}(w)=p$. Let
$(m_{i},m_{j})$ be the pair of adjacent men in $\succ^{(2)}_{w}$ that are
swapped in $\succ^{(3)}_{w}$. By construction, we know that
$m_{i},m_{j}\notin\\{{\textup{{Prop}}(w,\succ^{(2)},1),}\,{\textup{{Prop}}(w,\succ^{(2)},2)}\\}$.
Therefore, from cases (1) and (2) of Proposition 15, we have that
$\mu^{(3)}(w)=p$. Additionally, from Remark 3, the set of proposals under the
DA algorithm remains unchanged.

Our induction hypothesis is that $\mu^{(k)}(w)=p$ for all $3<k\leq K$. Given
this, we show that $\mu^{(K+1)}(w)=p$.

As before, let $(m_{i},m_{j})$ be the pair of adjacent men that are swapped in
$\succ^{(K)}_{w}$ to obtain $\succ^{(K+1)}_{w}$. By construction, we again
have that
$m_{i},m_{j}\notin\\{{\textup{{Prop}}(w,\succ^{(K)},1),}\,{\textup{{Prop}}(w,\succ^{(K)},2)}\\}$.
Therefore, from cases (1) and (2) of Proposition 15, we have that
$\mu^{(K+1)}(w)=\mu^{(K)}(w)$. Finally, using the induction hypothesis, we get
that $\mu^{(K+1)}(w)=p$.

Hence, by induction, we have that $\mu^{(\ell)}(w)=p=\mu^{\prime}(w)$. Since
$\succ^{(\ell)}\,=\,\succ^{\prime\prime}_{w}$ by construction, and
$\succ^{\prime\prime}_{w}\,\in S_{w}$, we substantiate Lemma 1. ∎

######  Remark 4 (Key difference from the construction of Vaish and Garg
(2017)).

One might wonder why the proof of Lemma 1 does not follow the construction of
Vaish and Garg (2017) _exactly_. Specifically, one might ask why it is not
enough to simply promote $q$ to a position immediately below $p$ (as done by
Vaish and Garg (2017) in the context of self manipulation), without further
promoting these agents to the top two positions.

Note that Vaish and Garg (2017) invoke Proposition 15 in the context of an
_optimal_ self manipulation. This ensures that the agents above $p$ in the
true list are guaranteed to be non-proposers.

By contrast, our construction in Lemma 1 works for an _arbitrary_ misreport by
$w$. Thus, it is possible that there is a proposer $p^{\prime}$ that is below
$p$ in the misreported list $\succ^{\prime}_{w}$ but is above $p$ in the true
list $\succ_{w}$. If $p$ is not promoted to the top position, then in order to
ensure that the agents in $\succ^{\prime}_{w}\setminus\\{p,q\\}$ are ordered
exactly as in $\succ_{w}\setminus\\{p,q\\}$, we might need to exchange $p$ and
$p^{\prime}$. However, this could change the DA match of $w$ (case 4 of
Proposition 15). For this reason, we need to promote $p$ to the top position.

For a similar reason, we also need to promote $q$ to immediately after $p$,
thus preventing the swap of the second and third-best proposers and again
avoiding a change in the DA partner (case 3 of Proposition 15).

Vaish and Garg (2017) showed that optimal self manipulation is inconspicuous,
i.e., only one man’s position needs to be changed from the true list. One may
ask whether _any_ misreport—optimal, suboptimal, or with-regret—is also
inconspicuous. 4 gives a negative answer to this question. More specifically,
we show that a with-regret misreport by the woman is not guaranteed to be
inconspicuous. We leave the question of whether supoptimal manipulations by
women are inconspicuous as an open problem.

Our interest in with-regret misreports by women becomes apparent in the proof
of Theorem 1, where we discuss the problems that arise in establishing
inconspicuousness of pair manipulation.

######  Example 4 (With-regret misreport by a woman may not be inconspicuous).

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

$m_{1}\colon$ |  $\underline{w_{3}}$ |  $w_{1}$ |  $w_{2}^{*}$ |  $w_{4}$ |  $w_{5}$ |  |  $\boldsymbol{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{w_{1}}}}\colon$ |  $m_{1}$ |  $m_{2}$ |  $\underline{m_{3}}$ |  $m_{4}^{*}$ |  $m_{5}$
---|---|---|---|---|---|---|---|---|---|---|---|---
${m_{2}}\colon$ |  $\underline{w_{4}^{*}}$ |  $w_{5}$ |  $w_{3}$ |  $w_{1}$ |  $w_{2}$ |  |  ${w_{2}}\colon$ |  $m_{3}$ |  $m_{5}$ |  $m_{1}^{*}$ |  $m_{2}$ |  $\underline{m_{4}}$
${m_{3}}\colon$ |  $\underline{w_{1}}$ |  $w_{3}^{*}$ |  $w_{5}$ |  $w_{4}$ |  $w_{2}$ |  |  ${w_{3}}\colon$ |  $m_{5}$ |  $m_{2}$ |  $m_{3}^{*}$ |  $m_{4}$ |  $\underline{m_{1}}$
${m_{4}}\colon$ |  $\underline{w_{2}}$ |  $w_{1}^{*}$ |  $w_{3}$ |  $w_{4}$ |  $w_{5}$ |  |  ${w_{4}}\colon$ |  $\underline{m_{2}^{*}}$ |  $m_{3}$ |  $m_{1}$ |  $m_{5}$ |  $m_{4}$
${m_{5}}\colon$ |  $w_{1}$ |  $\underline{w_{5}^{*}}$ |  $w_{3}$ |  $w_{2}$ |  $w_{4}$ |  |  ${w_{5}}\colon$ |  $m_{1}$ |  $\underline{m_{5}^{*}}$ |  $m_{3}$ |  $m_{2}$ |  $m_{4}$

The DA matching after $w_{1}$ submits $\succ^{\prime}_{w_{1}}\coloneqq
m_{4}\succ m_{5}\succ m_{1}\succ m_{2}\succ m_{3}$ is marked by “$*$”. Notice
that the matching is with-regret for $w_{1}$ as she is assigned $m_{4}$, who
she prefers less than her DA match $m_{3}$. A polynomial number of checks can
be made to verify that there is no inconspicuous list that can achieve the
same matching.

Although $\succ^{\prime}_{w_{1}}$ is not an inconspicuous version of $w_{1}$’s
true list $\succ_{w_{1}}$, it can be created from $\succ_{w_{1}}$ just by
promoting $m_{4}\coloneqq\textup{{Prop}}(w,\succ^{\prime},1)$, where
$\succ^{\prime}\coloneqq\\{\succ_{-w_{1}},\succ^{\prime}_{w_{1}}\\}$, to the
topmost position and
$m_{5}\coloneqq\textup{{Prop}}(w,\succ^{\prime}\coloneqq\\{\succ_{-w_{1}},2)$
to the second-most position, which is the same construction that was described
in the proof of Lemma 1. ∎∎

###  B.3 Proof of Lemma 2

Recall that $\widehat{\succ}_{m}$ is the preference list obtained by promoting
man $m$’s original match $\mu(m)$ to the top of his original list $\succ_{m}$,
and
$S_{m}\coloneqq\\{\widehat{\succ}_{m}^{w^{\prime}\uparrow}:w^{\prime}\neq\mu(m)\\}\cup\\{\widehat{\succ}_{m}\\}$
is the set of preference lists obtained by individually pushing up each woman
other than $\mu(m)$ to the top of $\widehat{\succ}_{m}$ as well as the list
$\widehat{\succ}_{m}$ itself.

See 2

###### Proof.

To construct the desired list $\succ^{\prime\prime}_{m}$, we will make use of
the following three preference profiles:

  * •

$\succ^{w}\coloneqq\\{\succ_{-\\{m,w\\}},\succ^{\prime}_{w},\succ_{m}\\}$,

  * •

$\widehat{\succ}\coloneqq\\{\succ_{-\\{m,w\\}},\succ^{\prime}_{w},\widehat{\succ}_{m}\\}$,
and

  * •

$\succ^{\prime}\coloneqq\\{\succ_{-\\{m,w\\}},\succ^{\prime}_{w},\succ^{\prime}_{m}\\}$.

Notice that the three profiles differ only in the preferences of man $m$. We
will denote the corresponding DA matchings for these profiles by
$\mu^{w}\coloneqq\texttt{DA}(\succ^{w})$,
$\widehat{\mu}\coloneqq\texttt{DA}(\widehat{\succ})$ and
$\mu^{\prime}\coloneqq\texttt{DA}(\succ^{\prime})$.

We will start by observing that $\mu^{w}(m)\succeq_{m}\mu(m)$. Indeed, if
$\mu(m)\succ_{m}\mu^{w}(m)$, then man $m$ can switch from the profile
$\succ^{w}$ (where his list is the same as his true list $\succ_{m}$) to the
profile $\succ^{\prime}$ (where his list is $\succ^{\prime}_{m}$) and improve
his DA match with respect to $\succ^{w}$; recall that it is given that
$\mu^{\prime}(m)=\mu(m)$. This, however, contradicts the strategyproofness of
DA algorithm for the proposing side. Thus, we must have
$\mu^{w}(m)\succeq_{m}\mu(m)$.

The rest of the proof is divided into two cases, depending on whether
$\mu^{w}(m)$ is the same as $\mu(m)$.

Case I: When $\mu^{w}(m)\neq\mu(m)$.

Recall from Proposition 2 that any misreport by man $m$ can be simulated via
push up and push down operations in the true list. Therefore, we can assume
without loss of generality that the list $\succ^{\prime}_{m}$ is derived from
$\succ_{m}$ by pushing up a set $Y^{\prime}\subseteq W$ of women who are
ranked below $\mu^{w}(m)$ and pushing down a set $X\subseteq W$ of women who
are ranked above $\mu^{w}(m)$.

Further, let us write man $m$’s list under the profile $\succ^{w}$ as
$\succ_{m}\coloneqq(\succ^{L}_{m},\mu^{w}(m),\succ^{R}_{m})$ where
$\succ^{L}_{m}$ and $\succ^{R}_{m}$ denote the parts of $m$’s list $\succ_{m}$
above and below his DA partner $\mu^{w}(m)$, respectively. Based on this
notation, we let $\bar{X}\coloneqq\,{\succ^{L}_{m}\setminus X}$ denote the set
of women other than $X$ who are ranked above $\mu^{w}(m)$ in $\succ_{m}$, and
analogously write $\bar{Y}\coloneqq\,{\succ^{R}_{m}\setminus Y^{\prime}}$ for
the set of women other than $Y^{\prime}$ who are ranked below $\mu(m)$ in
$\succ_{m}$. By Proposition 2, permuting the order of agents above (or below)
the DA partner in man $m$’s list does not affect the DA matching. Therefore,
we can represent the lists $\succ_{m}$ and $\succ^{\prime}_{m}$ as follows:

$\succ_{m}:X\succ\bar{X}\succ\boxed{\mu^{w}(m)}\succ
Y^{\prime}\succ\bar{Y},\text{ and }$ $\succ^{\prime}_{m}:\bar{X}\succ
Y^{\prime}\succ\mu^{w}(m)\succ X\succ\bar{Y},$

where the boxed entry is the DA partner of $m$ under $\succ_{m}$.

By the assumption in Case I, we have $\mu^{w}(m)\succ_{m}\mu(m)$ and thus
$\mu(m)\in Y^{\prime}\cup\bar{Y}$. We are also given that
$\mu^{\prime}(m)=\mu(m)$. Therefore, the transition from the profile
$\succ^{w}$ to the profile $\succ^{\prime}$, where only $m$ misreports, must
be _with-regret_ for $m$.

Consider another profile $(\succ^{w})^{X\downarrow}$ obtained from $\succ^{w}$
by pushing down the set $X$ in man $m$’s list; that is,

$\succ_{m}^{X\downarrow}:\bar{X}\succ\boxed{\mu^{w}(m)}\succ X\succ
Y^{\prime}\succ\bar{Y}.$

Notice that by Proposition 5, man $m$ continues to be matched with
$\mu^{w}(m)$ under $(\succ^{w})^{X\downarrow}$ and therefore, by Proposition
2, we can assume that the sets $X$, $Y$, and $Y^{\prime}$ can be ordered as
shown above.

Observe that the list $\succ^{\prime}_{m}$ can be obtained from
$\succ_{m}^{X\downarrow}$ by pushing up the set $Y^{\prime}$. Since $\mu(m)\in
Y^{\prime}\cup\bar{Y}$, the transition
$(\succ^{w})^{X\downarrow}\rightarrow\,\succ^{\prime}$ constitutes a with-
regret push up operation for man $m$. Then, by Proposition 8, man $m$ must be
matched with some agent in $Y^{\prime}$ under $\succ^{\prime}$. We already
know that $\mu^{\prime}(m)=\mu(m)$, and therefore we have that $\mu(m)\in
Y^{\prime}$. Let $Y\coloneqq Y^{\prime}\setminus\\{\mu(m)\\}$. The preference
lists after this simplification are shown in Figure 4. Notice that due to
Proposition 2, we can assume that $\mu(m)$ is placed immediately below
$\mu^{w}(m)$ in $\succ_{m}$, and, as a result, immediately above it in
$\succ^{\prime}_{m}$.

${\succ_{m}:}$${X}$${\bar{X}}$${\boxed{\mu^{w}(m)}}$${\mu(m)}$${Y}$${\bar{Y}}$${\succ^{\prime}_{m}:}$${\bar{X}}$${Y}$${\boxed{\mu(m)}}$${\mu^{w}(m)}$${X}$${\bar{Y}}$${\succ^{\prime}_{m}(\text{eqv.}):}$${\bar{X}}$${Y}$${\boxed{\mu(m)}}$${X}$${\mu^{w}(m)}$${\bar{Y}}$${\widehat{\succ}_{m}:}$${\boxed{\mu(m)}}$${\mu^{w}(m)}$${X}$${\bar{X}}$${Y}$${\bar{Y}}$
Figure 4: An illustration of man $m$’s preference lists under the profiles
$\succ^{w}$, $\succ^{\prime}$, $\succ^{\prime}(\text{eqv.})$, and
$\widehat{\succ}$ in the proof of Lemma 2 for Case I (when
$\mu^{w}(m)\neq\mu(m)$). The boxed agents correspond to DA partners of man $m$
under the respective profiles. Recall that it follows from Proposition 2 that
the order of women below these partners is not crucial.

Let us now consider the list $\widehat{\succ}_{m}$ obtained by promoting man
$m$’s original match $\mu(m)$ to the top of his original list $\succ_{m}$,
i.e.,

$\widehat{\succ}_{m}:\mu(m)\succ X\succ\bar{X}\succ\mu^{w}(m)\succ
Y\succ\bar{Y}.$

Notice that $\widehat{\succ}_{m}\in S_{m}$. We will argue that $m$ matches
with $\mu(m)$ under $\widehat{\succ}_{m}$. Note that because of Proposition 2,
the list $\succ^{\prime}_{m}$ is equivalent to the following list:

$\succ^{\prime}_{m}(\text{eqv.}):\bar{X}\succ Y\succ\boxed{\mu(m)}\succ
X\succ\mu^{w}(m)\succ\bar{Y}.$

Then, the list $\widehat{\succ}_{m}$ can be obtained by pushing down the sets
$\bar{X}$ and $Y$ in the list $\succ^{\prime}_{m}(\text{eqv.})$ and placing
these sets between $X$ and $\bar{Y}$. Therefore, by Proposition 5, $m$ matches
with $\mu(m)$ under $\widehat{\succ}$ (see Figure 4).

Since $\widehat{\mu}(m)=\mu(m)$, the list $\succ^{\prime}_{m}(\text{eqv.})$
can be created from the list $\widehat{\succ}_{m}$ via a no-regret push up of
the set $\bar{X}\cup Y$. If $\bar{X}\cup Y=\emptyset$, then
$\widehat{\succ}_{m}\,=\,\succ^{\prime}_{m}$ and the choice
$\succ^{\prime\prime}_{m}\coloneqq\widehat{\succ}_{m}$ proves the lemma.
Otherwise, if $\bar{X}\cup Y\neq\emptyset$, then it follows from Proposition
14 that the same match for $w$ that is created by pushing up $\bar{X}\cup Y$
in $\widehat{\succ}_{m}$, namely $\mu^{\prime}(w)=\mu(w)$, can be created by
pushing up exactly one woman in $\bar{X}\cup Y$, say $w^{\prime}$.
Additionally, from Proposition 9, it follows that $m$ would still match with
$\widehat{\mu}_{m}$ (hence $\mu(m)$) after pushing up $w^{\prime}$ in
$\widehat{\succ}_{m}$. Since $\widehat{\succ}^{w^{\prime}\uparrow}_{m}\,\in
S_{m}$, we have that the choice
$\succ^{\prime\prime}_{m}\coloneqq\widehat{\succ}^{w^{\prime}\uparrow}_{m}$
proves the lemma.

Case II: When $\mu^{w}(m)=\mu(m)$.

Following a similar line of reasoning as in Case I, we can once again say that
the list $\succ^{\prime}_{m}$ is derived from $\succ_{m}$ by pushing up the
set $Y$ and pushing down the set $X$. Further, the list $\widehat{\succ}_{m}$,
which is obtained by pushing up $\mu(m)$ to the top position in $\succ_{m}$,
can be equivalently derived from $\succ^{\prime}_{m}$ by pushing down
$\bar{X}\cup Y$. Thus, by Proposition 5, we once again have that
$\widehat{\mu}(m)=\mu(m)$ (see Figure 5).

${\succ_{m}:}$${X}$${\bar{X}}$${\boxed{\mu(m)}}$${Y}$${\bar{Y}}$${\succ^{\prime}_{m}:}$${\bar{X}}$${Y}$${\boxed{\mu(m)}}$${X}$${\bar{Y}}$${\widehat{\succ}_{m}:}$${\boxed{\mu(m)}}$${X}$${\bar{X}}$${Y}$${\bar{Y}}$
Figure 5: An illustration of man $m$’s preference lists under the profiles
$\succ^{w}$, $\succ^{\prime}$, and $\widehat{\succ}$ in the proof of Lemma 2
for Case II (when $\mu^{w}(m)=\mu(m)$). The boxed agents correspond to DA
partners of man $m$ under the respective profiles. Recall that it follows from
Proposition 2 that the order of women below these partners is not crucial.

If $\bar{X}\cup Y=\emptyset$, then
$\widehat{\succ}_{m}\,=\,\succ^{\prime}_{m}$ and the choice
$\succ^{\prime\prime}_{m}\coloneqq\widehat{\succ}_{m}$ proves the lemma since
$\widehat{\succ}_{m}\in S_{m}$. Otherwise, if $\bar{X}\cup Y\neq\emptyset$,
then it follows from Proposition 14 that the same match for $w$ that is
created by pushing up $\bar{X}\cup Y$ in $\widehat{\succ}_{m}$ to obtain
$\succ^{\prime}_{,}$, namely $\mu^{\prime}(w)=\mu(w)$, can be created by
pushing up exactly one woman in $\bar{X}\cup Y$, say $w^{\prime}$.
Additionally, from Proposition 9, it follows that $m$ would still match with
$\widehat{\mu}_{m}$ (hence $\mu(m)$) after pushing up $w^{\prime}$ in
$\widehat{\succ}_{m}$. Since $\widehat{\succ}^{w^{\prime}\uparrow}_{m}\,\in
S_{m}$, we have that the choice
$\succ^{\prime\prime}_{m}\coloneqq\widehat{\succ}^{w^{\prime}\uparrow}_{m}$
proves the lemma. ∎

###  B.4 Proof of Theorem 1

#### Why inconspicuousness is not straightforward to establish.

Recall that optimal self manipulation and optimal accomplice manipulation are
both known to be _inconspicuous_ , i.e., very similar to the true list (Vaish
and Garg, 2017; Hosseini et al., 2021). Prompted by the failure of
individually optimal strategies in 3, we ask whether an inconspicuous strategy
for the man could be combined with an inconspicuous strategy for the woman to
yield an optimal pair manipulation.

More concretely, consider a manipulating pair $(m,w)$. Let $\succ^{*}_{m}$ and
$\succ^{*}_{w}$ denote the respective lists of $m$ and $w$ under an optimal
pair manipulation, and let
$\succ^{*}\coloneqq(\succ_{-\\{m,w\\}},\succ^{*}_{m},\succ^{*}_{w})$ denote
the corresponding preference profile.

$\succ$$\succ^{m}=\\{\succ_{-m},\succ^{*}_{m}\\}$$\succ^{*}$$\succ^{w}=\\{\succ_{-w},\succ^{*}_{w}\\}$$\succ_{m}\rightarrow\succ^{*}_{m}$$\succ_{w}\rightarrow\succ^{*}_{w}$$\succ_{w}\rightarrow\succ^{*}_{w}$$\succ_{m}\rightarrow\succ^{*}_{m}$
Figure 6: Preference profiles under pair manipulation.

Since it is easier to think about single-agent misreports, let us break down
the transition from the true profile $\succ$ to the pair manipulation profile
$\succ^{*}$ in two steps: First, swap $m$’s list in $\succ$ to obtain the
intermediate profile $\succ^{m}\coloneqq\\{\succ_{-m},\succ^{*}_{m}\\}$, and
then swap $w$’s list in $\succ^{m}$ to get $\succ^{*}$; see top path in Figure
6. Alternatively, by reversing the order of swaps and going via the profile
$\succ^{w}\coloneqq\\{\succ_{-w},\succ^{*}_{w}\\}$, we obtain the bottom path
in Figure 6.

Let us first consider the top path in Figure 6, and specifically the
transition $\succ^{m}\rightarrow\,\succ^{*}$ wherein woman $w$ is the only
misreporting agent. Thus, the optimal pair manipulation strategy must involve
$w$ performing an optimal self manipulation with respect to the profile
$\succ^{m}$ _subject to $m$ being matched with $\mu(m)$_. In other words, the
strategy $\succ^{*}_{w}$ is an optimal solution to a _constrained self
manipulation_ problem. While the unconstrained self manipulation problem has
been explored previously (Teo et al., 2001; Vaish and Garg, 2017), we are not
aware of results on the structure of optimal solution of the aforementioned
constrained problem.333The works of Kobayashi and Matsui (2009, 2010) are
relevant here. They study the computational complexity of determining whether,
given the preferences of men and non-strategic women as well as a partial
matching in which the strategic women are matched, there is a set of
misreports for the strategic women that could induce a DA matching that
extends the given partial matching. In particular, we do not know if the
optimal constrained self manipulation problem also admits an inconspicuous
solution. Recall that a with-regret misreport by a woman is not guaranteed to
be inconspicuous (see 4).

Now consider the transition $\succ^{w}\rightarrow\,\succ^{*}$ in the bottom
path in Figure 6. For this step, man $m$ is the only misreporting agent. Note
that $m$’s list under the profile $\succ^{w}$ is his true list $\succ_{m}$.
Further, under $\succ^{w}$, man $m$ must be matched with either $\mu(m)$ or
some agent he ranks above $\mu(m)$; note that $m$’s partner under $\succ^{w}$
cannot be someone he ranks below $\mu(m)$ since strategyproofness of DA for
proposing side would forbid $m$ from being matched with $\mu(m)$ under
$\succ^{*}$.

If the optimal pair strategy $\succ^{*}_{w}$ of woman $w$ is such that her
optimal partner under $\succ^{*}$, namely $\mu^{*}(w)$, is ranked above her
partner under $\succ^{w}$, namely $\mu^{w}(w)$, then the transition
$\succ^{w}\rightarrow\,\succ^{*}$ is an optimal no-regret accomplice
manipulation for man $m$, which is known to be inconspicuous (Hosseini et al.,
2021). On the other hand, if $\mu^{w}(m)\neq\mu(m)$, then the same transition
is an optimal solution to a _constrained with-regret manipulation problem_.
Whether such strategies are inconspicuous remains an open problem.

We will now present the proof of Theorem 1.

See 1

###### Proof.

(sketch) Algorithm 1 can be used to compute an optimal pair manipulation. The
_correctness_ of the algorithm follows from the discussion on how to compute
optimal joint strategies in the main text. Here, we will argue that Algorithm
1 runs in $\mathcal{O}(n^{5})$ time.

The sets $S_{m}$ and $S_{w}$ are of size $\mathcal{O}(n)$ and
$\mathcal{O}(n^{2})$, respectively. The algorithm checks all possible pairs
$(\succ^{\prime}_{m},\succ^{\prime}_{w})\in S_{m}\times S_{w}$. The total
number of checks is in $\mathcal{O}(n^{3})$, and for each check, running the
DA algorithm takes $\mathcal{O}(n^{2})$ time. ∎

###  B.5 Stability-Preserving Pair Manipulation is Suboptimal (Remark 1)

In 5, we show that the stability of the manipulated outcome (with respect to
true preferences) can be in conflict with optimality of manipulation.
Specifically, our example demonstrates that the matched partner of the woman
under _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 under optimal _stability-preserving_ pair manipulation.

######  Example 5 (Stable pair manipulation strategy is strictly suboptimal).

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

${m_{1}}\colon$ |  $\underline{w_{1}}$ |  $w_{4}^{*}$ |  $w_{5}$ |  $w_{3}$ |  $w_{2}$ |  |  $\boldsymbol{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{w_{1}}}}\colon$ |  $m_{2}^{*}$ |  $m_{4}$ |  $\underline{m_{1}}$ |  $m_{3}$ |  $m_{5}$
---|---|---|---|---|---|---|---|---|---|---|---|---
${m_{2}}\colon$ |  $\underline{w_{4}}$ |  $w_{3}$ |  $w_{1}^{*}$ |  $w_{5}$ |  $w_{2}$ |  |  ${w_{2}}\colon$ |  $\underline{m_{5}}$ |  $m_{2}$ |  $m_{4}$ |  $m_{3}^{*}$ |  $m_{1}$
${m_{3}}\colon$ |  $w_{1}$ |  $w_{2}^{*}$ |  $\underline{w_{5}}$ |  $w_{4}$ |  $w_{3}$ |  |  ${w_{3}}\colon$ |  $m_{5}$ |  $m_{1}$ |  $\underline{m_{4}^{*}}$ |  $m_{2}$ |  $m_{3}$
$\boldsymbol{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{m_{4}}}}\colon$ |  $w_{5}$ |  $\underline{w_{3}^{*}}$ |  $w_{4}$ |  $w_{1}$ |  $w_{2}$ |  |  ${w_{4}}\colon$ |  $m_{3}$ |  $m_{5}$ |  $m_{4}$ |  $m_{1}^{*}$ |  $\underline{m_{2}}$
${m_{5}}\colon$ |  $w_{5}^{*}$ |  $\underline{w_{2}}$ |  $w_{3}$ |  $w_{1}$ |  $w_{4}$ |  |  ${w_{5}}\colon$ |  $m_{1}$ |  $\underline{m_{3}}$ |  $m_{4}$ |  $m_{5}^{*}$ |  $m_{2}$

Suppose the manipulating pair is $(m_{4},w_{1})$. The DA matching after
$m_{4}$ and $w_{1}$ submit their respective optimal pair manipulated lists
$\succ^{\prime}_{m_{4}}\coloneqq w_{3}\succ w_{5}\succ w_{4}\succ w_{1}\succ
w_{2}$ and $\succ^{\prime}_{w_{1}}\coloneqq m_{4}\succ m_{2}\succ m_{3}\succ
m_{1}\succ m_{5}$ is marked by “$*$”. Notice that the beneficiary $w_{1}$ is
matched with her top choice partner $m_{2}$, which means that the pair
manipulation is indeed optimal.

Although $m_{4}$ does not incur regret, the manipulated matching admits a
blocking pair $(m_{4},w_{5})$ with respect to the true preferences. In this
instance, there is no stability-preserving pair manipulation that is strictly
better than truthful reporting.444This was checked using an exhaustive search
of all possible manipulations by $m_{4}$ and $w_{1}$.∎∎

Despite the negative result that we have just presented, we are able to show
that any pair that blocks a “two-for-one” manipulation must contain the
accomplice or the strategic woman (Lemma 6). This property is similar to the
concept of _$m$ -stable_ matchings (Bendlin and Hosseini, 2019; Hosseini et
al., 2021), which are defined as matchings such that any pair that blocks them
with respect to true preferences must contain the accomplice $m$.

######  Lemma 6.

Given a preference profile $\succ$ and a manipulating pair $(m,w)$, let
$\succ^{\prime}$ denote the profile after $m$ and $w$ misreport their
preferences. For any matching $\mu^{\prime}\in S_{\succ^{\prime}}$ and for any
pair $(m^{\prime},w^{\prime})$ that blocks $\mu^{\prime}$ with respect to
$\succ$, it must be that $m^{\prime}=m$ or $w^{\prime}=w$.

###### Proof.

Suppose, for contradiction, there exists a man-woman pair
$(m^{\prime},w^{\prime})$ that blocks $\mu^{\prime}$ with respect to $\succ$
(i.e., $w^{\prime}\succ_{m^{\prime}}\mu^{\prime}(m^{\prime})$ and
$m^{\prime}\succ_{w^{\prime}}\mu^{\prime}(w^{\prime})$) such that
$m^{\prime}\neq m$ and $w^{\prime}\neq w$. Since $m$ and $w$ are the only
agents whose preferences differ between $\succ$ and $\succ^{\prime}$, we have
that $\succ_{m^{\prime}}\,=\,\succ^{\prime}_{m^{\prime}}$ and
$\succ_{w^{\prime}}\,=\,\succ^{\prime}_{w^{\prime}}$. Thus,
$w^{\prime}\succ^{\prime}_{m^{\prime}}\mu^{\prime}(m^{\prime})$ and
$m^{\prime}\succ^{\prime}_{w^{\prime}}\mu^{\prime}(w^{\prime})$, implying that
the pair $(m^{\prime},w^{\prime})$ blocks $\mu^{\prime}$ with respect to
$\succ^{\prime}$, which contradicts the assumption that $\mu^{\prime}\in
S_{\succ^{\prime}}$. Therefore, it must be that $m^{\prime}=m$ or
$w^{\prime}=w$. ∎

We note that although there do indeed exist instances where the accomplice is
in a pair that blocks an optimal “two-for-one” manipulated matching (as shown
in 5), we have not yet found any instances where a pair blocking the optimal
“two-for-one” manipulated matching contains the strategic woman. We leave the
question of whether optimal pair manipulations are strictly $m$-stable as an
open problem.

##  Appendix C Omitted Material from Section 4

###  C.1 Proof of Proposition 3

See 3

###### Proof.

Our proof closely follows that of Lemma 2 in Hosseini et al. (2021), which,
under the same set of assumptions, showed that if
$\mu^{\prime\prime}(w)\succ_{w}\mu(w)$ for any fixed woman $w$, then
$\mu^{\prime}(w)\succeq_{w}\mu^{\prime\prime}(w)$. For completeness, we recall
their argument below with the necessary modifications to establish Proposition
3.

We will use case analysis based on whether or not $\mu^{\prime}(m)=\mu(m)$,
where $\mu\coloneqq\texttt{DA}(\succ)$.

Case I (when $\mu^{\prime}(m)=\mu(m)$): The list $\succ^{\prime\prime}_{m}$
can be considered as being derived from $\succ^{\prime}_{m}$ via a push down
operation on the set $Y$ (see Figure 7). From Proposition 7, we know that a
push down operation is weakly worse for all women; thus, in particular, we get
$\mu^{\prime}\succeq_{W}\mu^{\prime\prime}$, as desired. Note that the
relative ordering of $X$ and $Y$ above $\mu^{\prime}(m)$ in the list
$\succ^{\prime}_{m}$ is not important in light of Proposition 2.

${\succ_{m}:}$${\cdots}$${Y}$${\cdots}$${\mu(m)}$${\cdots}$${X}$${\cdots}$${\succ^{\prime}_{m}:}$${\cdots}$${X}$${\cdots}$${Y}$${\cdots}$${\mu(m)}$${\cdots}$${\succ^{\prime\prime}_{m}:}$${\cdots}$${X}$${\cdots}$${\mu(m)}$${\cdots}$${Y}$${\cdots}$
Figure 7: An illustration of man $m$’s preference lists under the profiles
$\succ$, $\succ^{\prime}$, and $\succ^{\prime\prime}$ in the proof of
Proposition 3. Note that the relative positions of the women in sets $X$ and
$Y$ are unimportant due to Proposition 2.

Case II (when $\mu^{\prime}(m)\neq\mu(m)$): Suppose $\mu^{\prime}(m)\in X$.
Then, the list $\succ^{\prime\prime}_{m}$ can be considered as being derived
from $\succ^{\prime}_{m}$ via a permutation of the women below
$\mu^{\prime}(m)$ (see Figure 7). By Proposition 2, this implies that
$\mu^{\prime}=\mu^{\prime\prime}$, as desired.

Therefore, for the remainder of the proof, let us assume that
$\mu^{\prime}(m)\notin X$. Since $\succ^{\prime}_{m}$ is derived from
$\succ_{m}$ via a push up operation on the set $X$, and since
$\mu^{\prime}(m)\neq\mu(m)$ by assumption, we have that
$\mu(m)\succ_{m}\mu^{\prime}(m)$. By Proposition 2, we can assume, without
loss of generality, that $\mu^{\prime}(m)$ is positioned immediately below
$\mu(m)$ in the list $\succ_{m}$. By construction, the same property also
holds for the lists $\succ^{\prime}_{m}$ and $\succ^{\prime\prime}_{m}$. Thus,
$\succ^{\prime\prime}_{m}$ can be considered as being obtained from
$\succ^{\prime}_{m}$ via a push down operation on the set $Y$ (note that this
operation is defined with respect to $\mu^{\prime}(m)$). By Proposition 7, we
have $\mu^{\prime}\succeq_{W}\mu^{\prime\prime}$, as desired. ∎

###  C.2 Proof of Lemma 3

See 3

###### Proof.

Suppose, for contradiction, that $\succ^{Y}$ is a with-regret profile. Then,
from Proposition 8, we have that $m$ matches with some $w_{y}\in Y$ under
$\succ^{Y}$, i.e., $\mu^{Y}(m)=w_{y}$. By definition of the no-regret set
$W^{\textsc{NR}}$, we know that the profile obtained by promoting only
$w_{y}$, namely $\succ^{y}\coloneqq\\{\succ_{-m},\succ_{m}^{y\uparrow}\\}$, is
a no-regret profile, i.e., $\mu^{y}(m)=\mu(m)$, where
$\mu^{y}\coloneqq\texttt{DA}(\succ^{y})$.

Now consider the profile $\succ^{y}$ wherein $m$ is matched with $\mu(m)$. If
$m$ were to submit the preference list $\succ^{Y}_{m}$ instead (obtained by
pushing up the set $Y\setminus\\{w_{y}\\}$ in $\succ^{y}_{m}$), then we will
obtain the profile $\succ^{Y}$ in which $m$ is matched with $w_{y}$. This,
however, implies that $m$ is unilaterally able to improve its match from
$\mu(m)$ to $w_{y}$ (with respect to the new list $\succ^{y}_{m}$ wherein
$w_{y}\succ^{y}_{m}\mu(m)$), which contradicts the strategyproofness of the DA
algorithm. Hence, $\succ^{Y}$ must be a no-regret profile. ∎

###  C.3 Proof of Lemma 4

See 4

###### Proof.

Suppose, for contradiction, that $\succ^{Y}$ is a no-regret profile.
Proposition 9 shows that the accomplice $m$ does not incur regret under
$\succ^{y}\coloneqq\\{\succ_{-m},\succ_{m}^{y\uparrow}\\}$ for all $w_{y}\in
Y$. However, it is given that $\succ^{y}$ is a with-regret profile, thus
posing a contradiction. ∎

###  C.4 Proof of Corollary 1

See 1

###### Proof.

(sketch) The algorithm promotes each woman who is below $\mu(m)$ in the
accomplice $m$’s true preference list to some position above $\mu(m)$ and
checks the DA outcome. Recall that Proposition 2 gives us the flexibility to
place the promoted woman anywhere above $\mu(m)$ in the accomplice’s list. The
set of women who, when individually pushed up, do not cause regret are
returned. The total number of checks is $\mathcal{O}(n)$, and for each check,
running the DA algorithm takes $\mathcal{O}(n^{2})$ time. ∎

###  C.5 Computing the Smallest-Size Optimal Strategy

Although pushing up the entire no-regret set $W^{\textsc{NR}}$ is optimal
(Theorem 2), the accomplice might want to displace as few women as possible in
order to remain close to his true preference list. Thus, it is of interest to
find an optimal push up set of the _smallest size_.

Formally, consider any set $Y\subseteq W^{\textsc{NR}}$. Let $\mu^{Y}$ and
$\mu^{\textsc{NR}}$ denote the DA matchings obtained by pushing up the sets
$Y$ and $W^{\textsc{NR}}$ in the true list of the accomplice, respectively. We
call $Y$ a _minimum_ no-regret push up set if $\mu^{Y}=\mu^{\textsc{NR}}$ and
there exists no other set $Z\subseteq W^{\textsc{NR}}$ such that
$\mu^{Z}=\mu^{\textsc{NR}}$ and $|Z|<|Y|$. In other words, $Y$ is the smallest
set of women that, when pushed up in $\succ^{m}$, results in an optimal no-
regret strategy for the accomplice. Similarly, we call $Y\subseteq
W^{\textsc{NR}}$ a _minimal_ no-regret push up set if
$\mu^{Y}=\mu^{\textsc{NR}}$ and there exists no other set $Z$ such that
$\mu^{Z}=\mu^{\textsc{NR}}$ and $Z\subset Y$.

A minimum no-regret push up set is clearly also minimal. Our next result
(Theorem 3) establishes a converse.

######  Theorem 3.

Let $Y\subseteq W^{\textsc{NR}}$ be a minimal no-regret push up set. Then, $Y$
is also a minimum no-regret push up set.

Theorem 3 naturally gives rise to a greedy algorithm for finding a minimum no-
regret push up set (Algorithm 2). Starting with the no-regret set
$W^{\textsc{NR}}$ as its current guess, the algorithm iteratively removes an
agent from the current no-regret set and checks if the resulting matching
changes. If the matching does not change, the guess is updated by removing the
said agent and the check is repeated for the reduced set.

Algorithm 2 Computing a minimum no-regret push up set

1:Preference profile $\succ$, accomplice $m$

2:Minimum no-regret push up set $Y$

3:Compute $W^{\textsc{NR}}\leftarrow\\{w\in
W\,:\,\succ^{\prime}\coloneqq\\{\succ_{-m},\succ_{m}^{w\uparrow}\\}$ is a no-
regret profile}

4:Initialize $Y\leftarrow W^{\textsc{NR}}$ and
$\mu^{*}\leftarrow\texttt{DA}(\succ_{-m},\succ_{m}^{Y\uparrow})$

5:for each $w_{y}\in Y$ do

6: $Y^{\prime}\leftarrow Y\setminus\\{w_{y}\\}$

7:
$\mu^{\prime}\leftarrow\texttt{DA}(\succ_{-m},\succ_{m}^{Y^{\prime}\uparrow})$

8: if $\mu^{\prime}=\mu^{*}$ then

9: Restart for-loop in Line 5 with $Y\leftarrow Y^{\prime}$

10:return $Y$

######  Corollary 2.

A minimum optimal one-for-all strategy can be computed by Algorithm 2 in
$\mathcal{O}(n^{4})$ time.

The proofs of Theorem 3 and Corollary 2 are presented in the forthcoming
sections.

######  Remark 5.

In Section C.11, we show that the size of a minimum no-regret push up set is
always at most $\lfloor\frac{n-1}{2}\rfloor$ (Proposition 16), and that this
bound is tight for a family of instances (7).

Since the optimal strategy only involves a no-regret push up operation,
Proposition 4 implies that the resulting matching is stable with respect to
the true preferences.

######  Corollary 3.

An optimal one-for-all strategy for the accomplice is stability-preserving.

###  C.6 Proof of Theorem 3

The proof of Theorem 3 relies on a number of intermediate results (Lemmas 9, 8
and 7). Before introducing these results, let us define some notation.

Given any profile $\succ$, let $P_{\succ}$ denotes the set of all proposals
that occur in the execution of the DA algorithm on the profile $\succ$.
Formally, for any man $m_{i}\in M$ and woman $w_{j}\in W$, the ordered pair
$(m_{i},w_{j})$ belongs to the set $P_{\succ}$ if $m_{i}$ proposes to $w_{j}$
during the execution of DA algorithm on the profile $\succ$. Additionally, let
$P_{\succ\setminus\succ^{\prime}}\coloneqq P_{\succ}\setminus
P_{\succ^{\prime}}$ denote the set of proposals that occur under the profile
$\succ$ but not under $\succ^{\prime}$.

Suppose $\succ$ is a true preference profile and
$\mu\coloneqq\texttt{DA}(\succ)$. For a fixed accomplice $m$ and any woman
$w_{x}$ such that $\mu(m)\succ_{m}w_{x}$, we use the shorthand notation
$\succ^{x}_{m}$, $\succ^{x}$, and $\mu^{x}$ to denote the list
$\succ_{m}^{w_{x}\uparrow}$, the profile
$\succ^{w_{x}\uparrow}\coloneqq\\{\succ_{-m},\succ^{w_{x}\uparrow}_{m}\\}$,
and the matching
$\mu^{w_{x}\uparrow}\coloneqq\texttt{DA}(\succ^{w_{x}\uparrow})$,
respectively. Similarly, given a set of women $Y\subseteq W$, we use
$\succ^{Y}_{m}$, $\succ^{Y}$, and $\mu^{Y}$ to denote the list
$\succ_{m}^{Y\uparrow}$, the profile
$\succ^{Y\uparrow}\coloneqq\\{\succ_{-m},\succ^{Y\uparrow}_{m}\\}$, and the
matching $\mu^{Y\uparrow}\coloneqq\texttt{DA}(\succ^{Y\uparrow})$,
respectively.

Given a woman $w_{x}$ and a corresponding profile $\succ^{x}$, let
$P^{\prime}_{x}\coloneqq\\{(m_{i},w_{j})\in
P_{\succ^{x}\setminus\succ}:m_{i}\neq m\\}$ denote the set of proposals that
occur under $\succ^{x}$ but not $\succ$ made by any man other than the
accomplice. Similarly, given a set of women $Y$ and a corresponding profile
$\succ^{Y}$, let $P^{\prime}_{Y}\coloneqq\\{(m_{i},w_{j})\in
P_{\succ^{Y}\setminus\succ}:m_{i}\neq m\\}$.

######  Lemma 7.

Let $Y\coloneqq\\{w_{y_{1}},w_{y_{2}},w_{y_{3}},\dots\\}$ be such that
$Y\subseteq W^{\textsc{NR}}$. Then
$\mu^{Y}=\mu^{y_{1}}\wedge\mu^{y_{2}}\wedge\mu^{y_{3}}\wedge\dots$.

######  Lemma 8.

Let $Y\coloneqq\\{w_{y_{1}},w_{y_{2}},w_{y_{3}},\dots\\}$ be such that
$Y\subseteq W^{\textsc{NR}}$. If for some $w_{x}\in W^{\textsc{NR}}$,
$P^{\prime}_{x}\subseteq P^{\prime}_{y_{1}}\cup P^{\prime}_{y_{2}}\cup
P^{\prime}_{y_{3}}\cup\dots$, then $P^{\prime}_{x}\subseteq
P^{\prime}_{y_{k}}$ for some $w_{y_{k}}\in Y$.

######  Lemma 9.

Let $Y\coloneqq\\{w_{y_{1}},w_{y_{2}},w_{y_{3}},\ldots\\}$ be such that
$Y\subseteq W^{\textsc{NR}}$. If $Y$ is a minimal no-regret push up set, then
$P^{\prime}_{y_{1}},P^{\prime}_{y_{2}},P^{\prime}_{y_{3}},\ldots$ are pairwise
disjoint.

The proofs of Lemmas 9, 8 and 7 are presented in the following sections.
Below, we will use these results to prove Theorem 3.

See 3

###### Proof.

Suppose, for contradiction, that there exists a minimum set $Z\subseteq
W^{\textsc{NR}}$ such that $|Z|<|Y|$. Let
$Y\coloneqq\\{w_{y_{1}},w_{y_{2}},w_{y_{3}},\dots\\}$ and
$Z\coloneqq\\{w_{z_{1}},w_{z_{2}},w_{z_{3}},\dots\\}$. By our definition of
minimal and minimum sets, we have that
$\mu^{W^{\textsc{NR}}}=\mu^{Y}=\mu^{Z}$.

Let $P^{\prime}\coloneqq P^{\prime}_{y_{1}}\cup P^{\prime}_{y_{2}}\cup
P^{\prime}_{y_{3}}\cup\dots$. We will now argue that
$P^{\prime}_{Y}=P^{\prime}$. 555Note that this claim does not immediately
follow from Proposition 13, as $P^{\prime}$ is the set of _new_ proposals in
relation to the original preference profile that do not involve the
accomplice. Suppose there exists a proposal $(m^{\prime},w^{\prime})\in
P^{\prime}_{Y}\setminus P^{\prime}$. By definition of sets $P^{\prime}_{Y}$
and $P^{\prime}_{y_{k}}$ for all $w_{y_{k}}\in Y$, we know that
$m^{\prime}\neq m$ (i.e., $m^{\prime}$ is truthful). Since men propose in
decreasing order of their preference and $\succ^{Y}_{m^{\prime}}\ =\
\succ^{y_{k}}_{m^{\prime}}$ for all $w_{y_{k}}\in Y$, we infer that
$\mu^{Y}(m^{\prime})\notin\\{\mu^{y_{1}}(m^{\prime}),\mu^{y_{2}}(m^{\prime}),\mu^{y_{3}}(m^{\prime}),\dots\\}$,
which poses a contradiction to Lemma 7.

Now, suppose there exists a proposal $(m^{\prime},w^{\prime})\in
P^{\prime}\setminus P^{\prime}_{Y}$. Then, it must be that for some
$w_{y_{k}}\in Y$,
$\mu^{Y}(m^{\prime})\succ_{m^{\prime}}\mu^{y_{k}}(m^{\prime})$, because men
propose in decreasing order of their preference and all men other than the
accomplice are truthful. However, this means that under the matching
$\mu^{Y}$, man $m^{\prime}$ is not matched to his least-preferred partner
among
$\mu^{y_{1}}(m^{\prime}),\mu^{y_{2}}(m^{\prime}),\mu^{y_{3}}(m^{\prime}),\dots$,
which contradicts Lemma 7. Thus, we obtain the desired property,
$P^{\prime}_{Y}=P^{\prime}$. Note that a similar line of reasoning may be used
to claim that $P^{\prime}_{Z}=P^{\prime\prime}$, where
$P^{\prime\prime}\coloneqq P^{\prime}_{z_{1}}\cup P^{\prime}_{z_{2}}\cup
P^{\prime}_{z_{3}}\cup\dots$.

We will now argue that $|Z|=|Y|$ to derive the desired contradiction. Notice
that if $P^{\prime}_{Y}\setminus P^{\prime}_{Z}\neq\emptyset$, then
$\mu^{Y}(m^{\prime})\neq\mu^{Z}(m^{\prime})$, because men propose in
decreasing order of their preference and $\succ^{Y}_{m^{\prime}}\ =\
\succ^{Z}_{m^{\prime}}$. However, this poses a contradiction to our claim that
$\mu^{Y}=\mu^{Z}$. Therefore, $P^{\prime}_{Y}\setminus
P^{\prime}_{Z}=\emptyset$, and for the same reason, $P^{\prime}_{Z}\setminus
P^{\prime}_{Y}=\emptyset$. This implies that $P^{\prime}_{Y}=P^{\prime}_{Z}$,
and thus $P^{\prime}=P^{\prime\prime}$. We infer from this result that
$P^{\prime}_{z_{k}}\subseteq P^{\prime}$ for all $w_{z_{k}}\in Z$. Lemma 8
then shows that for all $w_{z_{k}}\in Z$, there exists some $w_{y_{\ell}}\in
Y$ such that $P^{\prime}_{z_{k}}\subseteq P^{\prime}_{y_{\ell}}$. By a similar
argument, for every $w_{y_{\ell}}\in Y$, there exists some $w_{z_{k}}\in Z$
such that $P^{\prime}_{y_{\ell}}\subseteq P^{\prime}_{z_{k}}$. Additionally,
by Lemma 9, we know that
$P^{\prime}_{y_{1}},P^{\prime}_{y_{2}},P^{\prime}_{y_{3}},\dots$ are pairwise
disjoint sets, as are
$P^{\prime}_{z_{1}},P^{\prime}_{z_{2}},P^{\prime}_{z_{3}},\dots$. Then, given
$P^{\prime}=P^{\prime\prime}$, it must be the case that $|Z|=|Y|$, giving us
the desired contradiction. Hence, a minimal no-regret push up set must also be
a minimum no-regret push up set. ∎

###  C.7 Proof of Lemma 7

See 7

###### Proof.

Suppose, for contradiction, that $\mu^{Y}(w)\neq\mu^{y_{k}}(w)$ for some $w\in
W$, where
$\mu^{y_{k}}(w)\coloneqq\mu^{y_{1}}(w)\wedge\mu^{y_{2}}(w)\wedge\mu^{y_{3}}(w)\wedge\ldots$,
i.e., $\mu^{y_{k}}(w)$ is $w$’s favorite partner in
$\\{\mu^{y_{1}}(w),\mu^{y_{2}}(w),\mu^{y_{3}}(w),\ldots\\}$.

From Lemma 3, we know that $m$ matches with $\mu(m)$ under $\succ^{Y}$. Since
$w_{y_{k}}\in Y\subseteq W^{\textsc{NR}}$, we know that $m$ matches with
$\mu(m)$ under $\succ^{y_{k}}$ as well. Since, $\succ^{Y}$ is obtained via a
no-regret push up of set $Y\setminus\\{w_{y_{k}}\\}$ in $\succ^{y_{k}}_{m}$,
from Proposition 4, we infer that $\mu^{Y}(w)\succeq_{w}\mu^{y_{k}}(w)$. Given
our assumption that $\mu^{Y}(w)\neq\mu^{y_{k}}(w)$, we get that
$\mu^{Y}(w)\succ_{w}\mu^{y_{k}}(w)$. Due to this, the woman $w$ must receive a
proposal under $\succ^{Y}$ that she does not under
$\succ^{y_{1}},\succ^{y_{2}},\dots,\succ^{y_{k}}$. However, this poses a
contradiction to Proposition 13, which guarantees that any proposal under
$\succ^{Y}$ must occur under at least one of the profiles
$\succ^{y_{1}},\succ^{y_{2}},\dots,\succ^{y_{k}}$. ∎

###  C.8 Proof of Lemma 8

Given two women $w_{x},w_{y}\in W^{\textsc{NR}}$ and some man $m_{x}$ such
that $m_{x}\succ_{w_{x}}m$, we show that if $m_{x}$ proposes to $w_{x}$ under
the profile $\succ^{y}$, then $P^{\prime}_{x}$ is contained in
$P^{\prime}_{y}$ (Lemma 10). This result is leveraged in the proof of Lemma 8.

######  Lemma 10.

Let $w_{x},w_{y}\in W^{\textsc{NR}}$. If there is a proposal $(m_{x},w_{x})\in
P_{\succ^{y}}$ such that $m_{x}\succ_{w_{x}}m$, then $P^{\prime}_{x}\subseteq
P^{\prime}_{y}$.

###### Proof.

Let
$\succ^{xy}\coloneqq\\{\succ_{-m},\succ_{m}^{\\{w_{x},w_{y}\\}\uparrow}\\}$
denote the profile obtained by pushing up both $w_{x}$ and $w_{y}$ in the true
list $\succ_{m}$ of the accomplice. From Lemma 3, we get that $\succ^{xy}$ is
a no-regret profile, and can be obtained via a no-regret push up of $w_{x}$ in
$\succ^{y}_{m}$.

Given $(m_{x},w_{x})\in P_{\succ^{y}}$ where $m_{x}\succ_{w_{x}}m$, we also
have that $\mu^{y}(w_{x})\succ_{w_{x}}m$, because women match with their
favorite proposers and it is assumed that $\succ^{y}_{w_{x}}=\ \succ_{w_{x}}$
(since women report truthfully). Then, by Proposition 10, we have that
$\mu^{xy}=\mu^{y}$. Furthermore, since men propose in decreasing order of
their lists and all men except for the accomplice are truthful, we get that
$P^{\prime}_{xy}\setminus P^{\prime}_{y}=\emptyset$ and
$P^{\prime}_{y}\setminus P^{\prime}_{xy}=\emptyset$, and thus
$P^{\prime}_{xy}=P^{\prime}_{y}$.

It follows from Proposition 13 that $P_{\succ^{xy}}\subseteq P_{\succ^{x}}\cup
P_{\succ^{y}}$. Combining this with Lemma 11, we get

$P^{\prime}_{xy}\cup P_{\succ}\cup\\{(m,w_{x}),(m,w_{y})\\}\subseteq$
$P^{\prime}_{x}\cup P^{\prime}_{y}\cup
P_{\succ}\cup\\{(m,w_{x}),(m,w_{y})\\}.$

Since the sets on each side of the above containment relation are disjoint, we
get that $P^{\prime}_{xy}\subseteq P^{\prime}_{x}\cup P^{\prime}_{y}$.
Furthermore, we already have that $P^{\prime}_{xy}=P^{\prime}_{y}$, which
means that $P^{\prime}_{xy}\subseteq P^{\prime}_{x}\cup P^{\prime}_{xy}$.
Therefore, it must be that $P^{\prime}_{x}\subseteq P^{\prime}_{xy}$. Since
$P^{\prime}_{xy}=P^{\prime}_{y}$, we obtain $P^{\prime}_{x}\subseteq
P^{\prime}_{y}$, as desired. ∎

See 8

###### Proof.

Since $\succ^{x}$ is a no-regret profile, the accomplice $m$ proposes to and
is rejected by the woman $w_{x}$. Thus, there must be a proposal
$(m_{x},w_{x})\in P_{\succ^{x}}$ such that $m_{x}\succ_{w_{x}}m$.

Suppose $\mu(w_{x})\succ_{w_{x}}m$. Then, by Proposition 10, $\mu^{x}=\mu$.
Since men propose in decreasing order of their preference and all men other
than the accomplice are truthful, we have that $P^{\prime}_{x}=\emptyset$ and
the lemma trivially holds.

Otherwise, we must have that $m\succeq_{w_{x}}\mu(w_{x})$. Combining this with
$m_{x}\succ_{w_{x}}m$, we get $m_{x}\succ_{w_{x}}\mu(w_{x})$. Given this and
$m_{x}\neq m$, we have that $(m_{x},w_{x})\in P^{\prime}_{x}$. Due to our
assumption that $P^{\prime}_{x}\subseteq P^{\prime}_{y_{1}}\cup
P^{\prime}_{y_{2}}\cup P^{\prime}_{y_{3}}\cup\dots$, we infer
$(m_{x},w_{x})\in P^{\prime}_{y_{k}}$ for some $w_{y_{k}}\in Y$. Then, Lemma
10 shows that $P^{\prime}_{x}\subseteq P^{\prime}_{y_{k}}$, thus completing
the proof. ∎

###  C.9 Proof of Lemma 9

The proof of Lemma 9 uses a number of intermediate results (Lemmas 11, 12, 10
and 13). We will start by showing that the set of proposals under the profile
$\succ^{Y}$, namely $P_{\succ^{Y}}$, is equivalent to the union of
$P^{\prime}_{Y}$, $P_{\succ}$, and the set of proposals $m$ makes to the women
in $Y$ (Lemma 11).

######  Lemma 11.

Let $Y\subseteq W^{\textsc{NR}}$. Then, $P_{\succ^{Y}}=P^{\prime}_{Y}\cup
P_{\succ}\cup\\{(m,w_{j}):w_{j}\in Y\\}$.

###### Proof.

By definition of $P^{\prime}_{Y}$, we know that
$P^{\prime}_{Y}=P_{\succ^{Y}}\setminus(P_{\succ}\cup\\{(m,w_{j}):w_{j}\in
Y\\})$ which implies that $P_{\succ^{Y}}\subseteq P^{\prime}_{Y}\cup
P_{\succ}\cup\\{(m,w_{j}):w_{j}\in Y\\}$. It is also easy to see that
$P^{\prime}_{Y}\cup\\{(m,w_{j}):w_{j}\in Y\\}\subseteq P_{\succ^{Y}}$. From
Lemma 3, we know that $\succ^{Y}$ is a no-regret profile, and thus, by
Proposition 12, $P_{\succ}\subseteq P_{\succ^{Y}}$. Combining this with the
above observation, we get $P^{\prime}_{Y}\cup
P_{\succ}\cup\\{(m,w_{j}):w_{j}\in Y\\}\subseteq P_{\succ^{Y}}$. Since we have
shown containment in both directions, the two sets must be the same, i.e.,
$P_{\succ^{Y}}=P^{\prime}_{Y}\cup P_{\succ}\cup\\{(m,w_{j}):w_{j}\in Y\\}$. ∎

Before stating the next intermediate result (Lemma 12), it would be helpful to
define a combinatorial structure that we will refer to as “chain of
proposals.” We note that Aziz et al. (2015) study a similar construct which
they call “chains of rejections” in the context of a many-to-one matching
model.

#### Chains of proposals

Given an arbitrary woman $w_{x}\in W^{\textsc{NR}}$, let $\succ^{x}$ be the
corresponding profile where $m$ pushes up $w_{x}$ in his preference list
without incurring regret. Additionally, let $\sigma_{\succ^{x}}$ be a
permutation of the sets of proposals that occur under profile $\succ^{x}$. It
is guaranteed by Proposition 12 that $P_{\succ}\subseteq P_{\succ^{x}}$. Due
to this, we suppose all proposals in $P_{\succ}$ are at the top of
$\sigma_{\succ^{x}}$, followed by $p^{0}_{x}\coloneqq(m,w_{x})$. We define
$C_{x}$, consisting of the proposals $p_{x}^{1},p_{x}^{2},\dots,p_{x}^{k}$ (in
that order), as a _chain of proposals_ that follows $p^{0}_{x}$ in
$\sigma_{\succ^{x}}$.

Let $p_{x}^{i}$ be the $i$-th proposal in the chain, and let
$p_{x}^{i-1}\coloneqq(m_{x}^{i-1},w_{x}^{i-1})$ be the proposal that comes
directly before $p_{x}^{i}$ in $\sigma_{\succ^{x}}$. Since $P_{\succ}$ yields
a complete matching and we have assumed that all proposals in $P_{\succ}$ take
place before $C_{x}$ according to $\sigma_{\succ^{x}}$, we infer that
$w_{x}^{i-1}$ must be tentatively matched to some man, say $m^{\prime}_{x}$,
prior to $p_{x}^{i-1}$. In other words, proposal
$(m^{\prime}_{x},w_{x}^{i-1})$ is above $p_{x}^{i-1}$ in $\sigma_{\succ^{x}}$,
and $m^{\prime}_{x}$ is $w_{x}^{i-1}$’s favorite proposer before
$p_{x}^{i-1}$. Depending on who $w_{x}^{i-1}$ prefers, there are two cases we
must consider.

Case A (when $m^{\prime}_{x}\succ_{w_{x}^{i-1}}m_{x}^{i-1}$): Then,
$w_{x}^{i-1}$ rejects $m_{x}^{i-1}$ in favor of $m^{\prime}_{x}$, and we
define $p_{x}^{i}$ to be $m_{x}^{i-1}$’s proposal to the next woman in his
preference list, say $w_{x}^{i}$ (i.e.,
$p_{x}^{i}\coloneqq(m_{x}^{i-1},w_{x}^{i})$).

Case B (when $m_{x}^{i-1}\succ_{w_{x}^{i-1}}m^{\prime}_{x}$): Then,
$w_{x}^{i-1}$ rejects $m^{\prime}_{x}$ in favor of $m_{x}^{i-1}$, and we
define $p_{x}^{i}$ to be $m^{\prime}_{x}$’s proposal to the next woman in his
preference list, say $w^{\prime}_{i}$ (i.e.,
$p_{x}^{i}\coloneqq(m^{\prime}_{x},w^{\prime}_{i})$).

Regardless of who $w_{x}^{i-1}$ prefers, we later show in Lemma 12 that
$p_{x}^{i}\in P^{\prime}_{x}$, and thus $p_{x}^{i}$ does indeed occur during
the DA execution on $\succ^{x}$.

We define $p_{x}^{k}$ to be the first proposal after $(m,w_{x})$ in
$\sigma_{\succ^{x}}$ such that some man $m_{x}\succ_{w_{x}}m$ proposes to
$w_{x}$. As stated above, $p_{x}^{k}$ is the last proposal in $C_{x}$. We use
6 to help illustrate the structure of these chains.

######  Example 6 (Chains of proposals).

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

${w_{3}}$${m_{5}}$${w_{2}}$${m_{1}}$${w_{1}}$${m_{2}}$${w_{5}}$${m_{4}}$${w_{2}}$${m_{4}}$${w_{3}}$${m_{3}}$${m_{3}}$${w_{1}}$${m_{1}}$${w_{1}}$ Figure 8: Illustration of the sequence of events surrounding the chains of proposals, $C_{1}$ and $C_{3}$, as described in 6. An edge from $m\in M$ to $w\in W$ represents $m$ proposing to $w$; an edge from $w\in W$ to $m\in M$ represents $w$ rejecting $m$. The bottom sequence represents the chain $C_{1}$, and the blue edges indicate proposals that belong to $C_{1}$. Similarly, the top sequence represents the chain $C_{3}$, and the red edges indicate proposals that belong to $C_{3}$ (e.g., $(m_{5},w_{2})\in C_{3}$). ${m_{1}}\colon$ |  $w_{5}$ |  $\underline{w_{2}}$ |  $w_{1}^{*,\dagger}$ |  $w_{4}$ |  $w_{3}$ |  |  ${w_{1}}\colon$ |  $m_{1}^{*,\dagger}$ |  $m_{5}$ |  $m_{3}$ |  $m_{4}$ |  $\underline{m_{2}}$
---|---|---|---|---|---|---|---|---|---|---|---|---
${m_{2}}\colon$ |  $\underline{w_{1}}$ |  $w_{5}^{*,\dagger}$ |  $w_{3}$ |  $w_{2}$ |  $w_{4}$ |  |  ${w_{2}}\colon$ |  $m_{5}^{*}$ |  $m_{4}^{\dagger}$ |  $\underline{m_{1}}$ |  $m_{2}$ |  $m_{3}$
$\boldsymbol{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{m_{3}}}}\colon$ |  $w_{2}$ |  $\underline{w_{4}^{*}}^{,\dagger}$ |  $w_{3}$ |  $w_{1}$ |  $w_{5}$ |  |  ${w_{3}}\colon$ |  $m_{4}^{*}$ |  $m_{3}$ |  $m_{1}$ |  $m_{2}$ |  $\underline{m_{5}}$
${m_{4}}\colon$ |  $\underline{w_{5}}$ |  $w_{2}^{\dagger}$ |  $w_{3}^{*}$ |  $w_{1}$ |  $w_{4}$ |  |  ${w_{4}}\colon$ |  $m_{5}$ |  $m_{4}$ |  $\underline{m_{3}^{*}}^{,\dagger}$ |  $m_{1}$ |  $m_{2}$
${m_{5}}\colon$ |  $\underline{w_{3}^{\dagger}}$ |  $w_{2}^{*}$ |  $w_{4}$ |  $w_{1}$ |  $w_{5}$ |  |  ${w_{5}}\colon$ |  $m_{3}$ |  $m_{2}^{*,\dagger}$ |  $\underline{m_{4}}$ |  $m_{1}$ |  $m_{5}$

Suppose the accomplice is $m_{3}$. The DA matchings after $m_{3}$ submits the
lists $\succ^{1}_{m_{3}}=w_{1}\succ w_{2}\succ w_{4}\succ w_{3}\succ w_{5}$
and $\succ^{3}_{m_{3}}\coloneqq w_{3}\succ w_{2}\succ w_{4}\succ w_{1}\succ
w_{5}$ are marked by $*$ and $\dagger$, respectively. Notice that
$\succ^{1}_{m_{3}}$ and $\succ^{3}_{m_{3}}$ are derived from $\succ_{m_{3}}$
by pushing up $w_{1}$ and $w_{3}$, respectively.

Under both $\succ^{1}\coloneqq\\{\succ_{-m_{3}},\succ^{1}_{m_{3}}\\}$ and
$\succ^{3}\coloneqq\\{\succ_{-m_{3}},\succ^{3}_{m_{3}}\\}$, there are
corresponding chains of proposals, $C_{1}$ and $C_{3}$. Figure 8 illustrates
the sequence of events that surround these two chains.

Let us walk through chain $C_{1}$ as an example. Recall that the set
$P_{\succ}$ given by

$P_{\succ}=\\{(m_{1},w_{5}),(m_{2},w_{1}),(m_{3},w_{2}),(m_{4},w_{5}),\\\
(m_{5},w_{3}),(m_{1},w_{2}),(m_{3},w_{4})\\}$

and proposal $(m_{3},w_{1})$ occur prior to the chain. Upon receiving
$m_{3}$’s proposal, $w_{1}$ rejects $m_{2}$, who then proposes to the next
woman in his preference list, $w_{5}$. Thus, $(m_{2},w_{5})$ is the first
proposal in $C_{1}$. Because $w_{5}$ prefers $m_{2}$ over her original DA
match, $m_{4}$, she rejects $m_{4}$ who, as a result, must propose to the next
woman in his preference list, $w_{2}$. Then, $(m_{4},w_{2})$ is the second
proposal in $C_{1}$. Next, $w_{2}$ rejects $m_{1}$ in favor of $m_{4}$, and
$m_{1}$ proposes to $w_{1}$. Since $(m_{1},w_{1})$ is the first proposal such
that some man above $m_{3}$, the accomplice, in $w_{1}$’s preference list
proposes to $w_{1}$. Thus, $(m_{1},w_{1})$ is the third and last proposal in
$C_{1}$.∎∎

Now that we have clearly defined what a chain of proposals $C_{x}$ is, we show
that the set of proposals belonging to the chain is equivalent to the set
$P^{\prime}_{x}$ (Lemma 12).

######  Lemma 12.

The set of proposals in $C_{x}$ is equivalent to the set $P^{\prime}_{x}$.

###### Proof.

We first show that $P^{\prime}_{x}$ is contained in
$\\{p_{x}^{1},p_{x}^{2},\dots,p_{x}^{k}\\}$, which is the set of proposals
that belong to $C^{\prime}_{x}$. Suppose, for contradiction, that
$p\coloneqq(m^{\prime},w^{\prime})$ is the _first_ proposal during the DA
execution on $\succ^{x}$ that belongs to
$P^{\prime}_{x}\setminus\\{p_{x}^{1},p_{x}^{2},\dots,p_{x}^{k}\\}$. Note that
for this proof we are not assuming the order defined by $\sigma_{\succ^{x}}$
and are instead assuming that proposals occur in the order in which the DA
algorithm traditionally executes.

Since men propose in decreasing order of their preference and it is assumed
that $p\in P_{\succ^{x}}$, it must be that $m^{\prime}$ was rejected by some
woman, say $w^{\prime\prime}$, under $\succ^{x}$ before proposing to
$w^{\prime}$. Notice that $w^{\prime}$ cannot be the first woman in
$m^{\prime}$’s list, otherwise it must be that $p\in
P_{\succ}\cup\\{(m,w_{x})\\}$, which would contradict our assumption that
$p\in P^{\prime}_{x}$. Therefore, without loss of generality, we assume
$w^{\prime\prime}$ is the woman directly above $w^{\prime}$ in
$\succ^{x}_{m^{\prime}}$. It must also be that $w^{\prime\prime}$ receives a
proposal from some other man, say $m^{\prime\prime}$, such that
$m^{\prime\prime}\succ_{w^{\prime\prime}}m^{\prime}$. Clearly,
$p^{\prime}\coloneqq(m^{\prime},w^{\prime\prime})$ and
$p^{\prime\prime}\coloneqq(m^{\prime\prime},w^{\prime\prime})$ both occur
before $p$ during the DA execution on $\succ^{x}$.

Because we assumed $p$ to be the first proposal during the DA execution on
$\succ^{x}$ to belong to
$P^{\prime}_{x}\setminus\\{p_{x}^{1},p_{x}^{2},\dots,p_{x}^{k}\\}$, we must
have that $p^{\prime}\notin
P^{\prime}_{x}\setminus\\{p_{x}^{1},p_{x}^{2},\dots,p_{x}^{k}\\}$. This
implies that $p^{\prime}\notin P^{\prime}_{x}$ or
$p^{\prime}\in\\{p_{x}^{1},p_{x}^{2},\dots,p_{x}^{k}\\}$ (or both). The same
can be said for proposal $p^{\prime\prime}$. Given these possibilities, we use
case analysis to proceed with the proof.

Case I (when $p^{\prime}\notin P^{\prime}_{x}$ and $p^{\prime\prime}\notin
P^{\prime}_{x}$): Then, $p^{\prime},p^{\prime\prime}\in
P_{\succ}\cup\\{(m,w_{x})\\}$ due to Lemma 11. If $p^{\prime}=(m,w_{x})$, then
$p=(m,\mu(m))$, because the woman directly below $w_{x}$ in $\succ^{x}_{m}$
is, without loss of generality, assumed to be $\mu(m)$. Recall that due to
Proposition 2, we are able to assume any order of the women above $\mu(m)$ in
$\succ^{x}_{m}$. However, this would mean that $p\in P_{\succ}$, posing a
contradiction to our assumption that $p\in P^{\prime}_{x}$. Therefore, we have
that $p^{\prime}\neq(m,w_{x})$, and thus $p^{\prime}\in P_{\succ}$.

Now, we show that $p^{\prime\prime}\neq(m,w_{x})$. Suppose the contrary (i.e.,
$p^{\prime\prime}=(m,w_{x})$) is true. Because $m^{\prime}\neq
m^{\prime\prime}$, it must be that $m^{\prime}\neq m$, and thus $p^{\prime}\in
P_{\succ}$ due to our previous claim that $p^{\prime},p^{\prime\prime}\in
P_{\succ}\cup\\{(m,w_{x})\\}$. If $m^{\prime}=\mu(w_{x})$ (i.e.,
$p^{\prime}=(\mu(w_{x}),w_{x})$), then by definition of $C_{x}$, we have that
$p=(\mu(w_{x}),w^{\prime})=p_{x}^{1}$, where $w^{\prime}$ is the woman
directly below $w_{x}$ in $\mu(w_{x})$’s preference list. However, this poses
a contradiction to our assumption that $p\in
P^{\prime}_{x}\setminus\\{p_{x}^{1},p_{x}^{2},\dots,p_{x}^{k}\\}$. If
$m^{\prime}\neq\mu(w_{x})$, on the other hand, then it must be that
$w^{\prime}$ is below $w_{x}$ in $\succ_{m^{\prime}}^{x}$, because
$p^{\prime}\in P_{\succ}$ and men propose in decreasing order of their
preference under the DA algorithm. This would imply that $p\in P_{\succ}$, and