# Capacity Modification in the Stable Matching Problem

Salil Gokhale Shivika Narang IIT Delhi, India MSRI/SLMath, Berkeley, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS>Samarth Singla
Rohit Vaish IIT Delhi, India IIT Delhi, India<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We study the problem of capacity modification in the many-to-one stable
matching of workers and firms. Our goal is to systematically study how the set
of stable matchings changes when some seats are added to or removed from the
firms. We make three main contributions: First, we examine whether firms and
workers can improve or worsen upon changing the capacities under worker-
proposing and firm-proposing deferred acceptance algorithms. Second, we study
the computational problem of adding or removing seats to either match a fixed
worker-firm pair in some stable matching or make a fixed matching stable with
respect to the modified problem. We develop polynomial-time algorithms for
these problems when only the overall change in the firms’ capacities is
restricted, and show NP-hardness when there are additional constraints for
individual firms. Lastly, we compare capacity modification with the classical
model of preference manipulation by firms and identify scenarios under which
one mode of manipulation outperforms the other. We find that a threshold on a
given firm’s capacity, which we call its _peak_ , crucially determines the
effectiveness of different manipulation actions.

##  1 Introduction

The stable matching problem is a classical problem at the intersection of
economics, operations research, and computer science (Gusfield and Irving,
1989; Roth and Sotomayor, 1990; Knuth, 1997; Manlove, 2013). The problem
involves two sets of agents, such as workers and firms, each with a preference
ordering over the agents on the other side. The goal is to find a matching
that is _stable_ , i.e., one where no worker-firm pair prefer each other over
their current matches.

Many real-world matching markets have been influenced by the stable matching
problem, such as school choice Abdulkadiroğlu and Sönmez (2003);
Abdulkadiroğlu et al. (2005a, b), entry-level labor markets Roth (1984); Roth
and Peranson (1999), and refugee resettlement Ahani et al. (2021); Aziz et al.
(2018). In these applications, each agent on one side of the market (e.g., the
firms) has a _capacity constraint_ that limits the maximum number of agents on
the other side (namely, workers) it can be feasibly matched with. Remarkably,
for any given capacities, a stable matching of workers and firms always exists
and can be computed using the celebrated deferred-acceptance algorithm Gale
and Shapley (1962); Roth (1984).

While the stable matching problem assumes fixed capacities, it is common to
have _flexible_ capacities in practice. This is particularly useful in
settings with variable demand or popularity such as in vaccine distribution or
course allocation. Flexible capacities also allow for accommodating other
goals, such as Pareto optimality or social welfare Kumano and Kurino (2022).
For example, in 2016, nineteen colleges in Delhi University in India increased
their total capacity by 2000 seats across various courses Chettri . Another
example is the _ScheduleScout_ platform,111https://www.getschedulescout.com/
formerly known as Course Match Budish et al. (2017), used in course allocation
at the Wharton School. This platform allows the addition or removal of seats
in courses that are either undersubscribed or oversubscribed,
respectively.222https://www.youtube.com/watch?v=OSOanbdV3jI&t=1m38s In more
complex matching environments such as stable matching with couples where a
stable solution is not guaranteed to exist, a small change in the capacities
can provably restore the existence of a stable outcome (Nguyen and Vohra,
2018). We will use the term _capacity modification_ to refer to change in the
capacities of the firms by a central planner.

The theoretical study of capacity modification was initiated by Sönmez (1997),
who showed that under any stable matching algorithm, there exists a scenario
where some firm is better off when its capacity is reduced. The computational
aspects of capacity modification have also recently gained attention Bobbio et
al. (2022, 2023); Chen and Csáji (2023). However, some natural questions about
how the set of stable matchings responds to changes in capacities have not
been answered. Specifically, by modifying the capacities, can a given worker-
firm pair be matched under some stable matching? Or, can a given matching be
realized as a stable outcome of the modified instance? Furthermore, if we
consider the perspective of a strategic firm, there has been a lack of a
distinct comparison between "manipulation through capacity modification" and
the traditional approach of "manipulation through misreporting preferences".
Our interest in this work is to address these gaps.

### Our Contributions

We undertake a systematic analysis of the structural and computational aspects
of the capacity modification problem and make three main contributions:

##### Capacity modification trends.

In Section 3, we study the effect of capacity modification on workers and
firms. We observe that increasing a firm’s capacity by $1$ can, in some cases,
improve, and in other cases, worsen its outcome under both worker-proposing
and firm-proposing deferred acceptance algorithms. The workers, on the other
hand, can improve but never worsen (see Table 1).

##### Computational results.

In Section 4, we study a natural computational problem faced by a central
planner: Given a many-to-one instance, how can a fixed number of seats be
added to (similarly, removed from) the firms in order to either match a fixed
worker-firm pair in some stable matching or make a given matching stable in
the new instance? We show that these problems admit polynomial-time
algorithms. We also study a generalization where individual firms have
constraints on the seats added to or removed from them, in addition to an
aggregate budget. In this case, the problem of matching a fixed worker-firm
pair turns out to NP-hard while ensuring that a given matching is stable can
still be efficiently solved (see Table 2).

##### Capacity modification v/s preference manipulation.

In Section 5, we examine which mode of manipulation is more powerful for a
strategic firm: underreporting/overreporting capacity or misreporting
preferences. Interestingly, it turns out that the effectiveness of each
manipulation action (i.e., adding/deleting capacity or misreporting
preferences) depends on a threshold on the firm’s capacity which we call
_peak_ (see Figure 1). For a firm to successfully manipulate its preferences,
its capacity must be strictly below its peak (under the worker-proposing
algorithm) or at most its peak (when firms propose). Thus, the concept of peak
appears to have relevance beyond capacity modification.

### Related Work

The stable matching problem has inspired a large body of work in economics,
operations research, computer science, and artificial intelligence (Gale and
Shapley, 1962; Gusfield and Irving, 1989; Roth and Sotomayor, 1990; Knuth,
1997; Manlove, 2013).

Prior work has demonstrated strategic vulnerabilities of stable matching
algorithms. It is known that any stable matching algorithm is susceptible to
manipulation via misreporting of preferences (Dubins and Freedman, 1981; Roth,
1982), underreporting of capacities (Sönmez, 1997), and formation of pre-
arranged matches Sönmez (1999).333In pre-arranged matches, a worker and firm
can choose to match outside the algorithm. The worker does not participate in
the algorithm, and in return, is offered a seat at the firm. The firm then has
one less seat available through the algorithm. Subsequently, Roth and Peranson
(1999) showed via experiments on the data from the National Resident Matching
Program that less than $1\%$ of the programs can benefit by misreporting
preferences or underreporting capacities. Kojima and Pathak (2009) provided
theoretical justification for these findings by showing that incentives for
such manipulations vanish in large markets. Note that, unlike the above
results that only apply to specific datasets (Roth and Peranson, 1999) or in
the asymptotic setting (Kojima and Pathak, 2009), our algorithmic results
provide worst-case guarantees for _any_ given instance.

Another line of work has explored restricted preference domains for
circumventing the above impossibility results (Konishi and Ünver, 2006;
Kojima, 2007; Kesten, 2012). In particular, Konishi and Ünver (2006) have
shown that under strongly monotone preferences (formally defined in Section
2), a firm cannot manipulate by underreporting its capacity under the worker-
proposing algorithm (although other algorithms, like the firm-proposing
algorithm, can still be manipulated).

The computational problem of modifying capacities to serve a given objective
has seen significant attention in recent years. Bobbio et al. (2022) showed
that the problem of adding (similarly, removing) seats from the firms in order
to minimize the average rank of matched partners of the workers is NP-hard to
approximate within $\mathcal{O}(\sqrt{m})$, where $m$ is the number of
workers. Bobbio et al. (2023) developed a mixed integer linear program for
this problem.

Chen and Csáji (2023) studied the problem of increasing the firms’ capacities
to obtain a stable and perfect matching, and similarly, a matching that is
stable and Pareto efficient for the workers. They considered two objectives
for this problem: minimizing the overall increase in the firms’ capacities and
minimizing the maximum increase in any firm’s capacity. Dur and Van der Linden
(2021) studied the problem of adding seats to firms to achieve a matching that
is stable (with respect to the modified capacities) and not Pareto dominated
(as per workers’ preferences only) by any other stable matching. Some of our
computational results draw upon the work of Boehmer et al. (2021), who studied
the control problem for stable matchings in the one-to-one setting. We discuss
the connection with this work in Section 4.

##  2 Preliminaries

For any positive integer $r$, let $[r]\coloneqq\\{1,2,\dots,r\\}$.

##### Problem instance.

An instance of the _many-to-one_ matching problem is given by a tuple $\langle
F,W,C,\succ\rangle$, where $F=\\{f_{1},\dots,f_{n}\\}$ is the set of
$n\in\mathbb{N}$ _firms_ , $W=\\{w_{1},\dots,w_{m}\\}$ is the set of
$m\in\mathbb{N}$ _workers_ , $C=\\{c_{1},\dots,c_{n}\\}$ is the set of
_capacities_ of the firms (where, for every $i\in[n]$,
$c_{i}\in\mathbb{N}\cup\\{0\\})$, and
$\succ=(\succ_{f_{1}},\dots,\succ_{f_{n}},\succ_{w_{1}},\dots,\succ_{w_{m}})$
is the _preference profile_ consisting of the ordinal preferences of all firms
and workers. Each worker $w\in W$ is associated with a linear order (i.e., a
strict and complete ranking) $\succ_{w}$ over the set $F\cup\\{\emptyset\\}$.
Each firm $f\in F$ is associated with a linear order $\succ_{f}$ over the set
$W\cup\\{\emptyset\\}$. Throughout, we will use the term _agent_ to refer to a
worker or a firm, i.e., an element in the set $W\cup F$.

For two capacity vectors $C,\overline{C}\in(\mathbb{N}\cup\\{0\\})^{n}$, we
will write $\overline{C}\geq C$ to denote coordinate-wise greater than or
equal to, i.e., for every $i\in[n]$, $\overline{c}_{i}\geq c_{i}$, where
$c_{i}$ and $\overline{c}_{i}$ are the $i^{\textup{th}}$ coordinate of vectors
$C$ and $\overline{C}$, respectively. Additionally, we will write
$|\overline{C}-C|_{1}$ to denote the $L^{1}$ norm of the difference vector,
i.e., $|\overline{C}-C|_{1}\coloneqq\sum_{i=1}^{n}|\overline{c}_{i}-c_{i}|$.

When all firms have unit capacities (i.e., for each firm $f\in F,c_{f}=1$), we
obtain the _one-to-one_ matching problem. In this case, we will follow the
terminology from the literature on the stable marriage problem (Gale and
Shapley, 1962) and denote a problem instance by $\langle P,Q,\succ\rangle$,
where $P$ and $Q$ denote the set of $n$ _men_ and $m$ _women_ , respectively,
and $\succ$ denotes the corresponding preference profile.

##### Complete preferences.

A worker $w$ is said to be _acceptable_ to a firm $f$ if
$w\succ_{f}\emptyset$. A set of workers $S\subseteq W$ is said to be
acceptable to a firm $f$, denoted by $S\succ_{f}\emptyset$, if all workers in
it are acceptable to $f$. Likewise, a firm $f$ is acceptable to a worker $w$
if $f\succ_{w}\emptyset$. An agent’s preferences are said to be _complete_ if
all agents on the other side are acceptable to it.

##### Responsive preferences.

Throughout the paper, we will assume that firms’ preferences over subsets of
workers are _responsive_ (Roth, 1985). Informally, this means that for any
subsets $S,S^{\prime}\subseteq W$ of workers where $S$ is derived from
$S^{\prime}$ by replacing a worker $w^{\prime}\in S^{\prime}$ with a more
preferred worker $w$, it must be that $S\succ_{f}S^{\prime}$. More formally,
the extension of firm $f$’s preferences over subsets of workers is responsive
if for any subset $S\subseteq W$ of workers,

  * •

for all $w\in W\setminus S$, $S\cup\\{w\\}\succ_{f}S$ if and only if
$w\succ_{f}\emptyset$, and

  * •

for all $w,w^{\prime}\in W\setminus S$,
$S\cup\\{w\\}\succ_{f}S\cup\\{w^{\prime}\\}$ if and only if
$w\succ_{f}w^{\prime}$.

We will write $S\succeq_{f}S^{\prime}$ to denote that either
$S\succ_{f}S^{\prime}$ or $S=S^{\prime}$. Further, we will always consider the
transitive closure of any responsive extension of $\succ_{f}$, which, in turn,
induces a partial order over the set of all subsets of workers.

We will now define two subdomains of responsive preferences that will be of
interest to us: _strongly monotone_ and _lexicographic_.

##### Strongly monotone preferences.

A firm is said to have _strongly monotone_ preferences Konishi and Ünver
(2006) if its preferences are responsive and it prefers cardinality-wise
larger subsets of workers. That is, for any pair of acceptable subsets of
workers $S,T$ such that $|S|>|T|$, it holds that $S\succ_{f}T$.

##### Lexicographic preferences.

A firm $f$ is said to have _lexicographic_ preferences if it prefers any
subset of workers containing its favorite worker over any subset not
containing it, subject to which, it prefers any subset containing its second-
favorite worker over any subset not containing it, and so on. Formally, given
a linear order $\succ_{f}$ over the set $W\cup\\{\emptyset\\}$ and any pair of
distinct acceptable subsets of workers $S$ and $T$, we have $S\succ_{f}T$ if
and only if the favorite worker of firm $f$ (as per $\succ_{f}$) in the set
difference of $S$ and $T$ (i.e., $S\setminus T\cup T\setminus S$) lies in $S$.
Observe that lexicographic preferences are responsive.

For many-to-one instances with two workers (i.e., $|W|=2$) that are both
acceptable to a firm, lexicographic and strongly monotone preferences
coincide. However, for instances with three or more workers, strongly monotone
preferences are not lexicographic and lexicographic preferences are not
strongly monotone.444This can be easily seen by considering a firm with
preference over singletons as $w_{1}\succ w_{2}\succ w_{3}\succ\cdots$. A firm
with lexicographic preferences will prefer $\\{w_{1}\\}$ over
$\\{w_{2},w_{3}\\}$. On the other hand, under strongly monotone preferences,
the firm will prefer $\\{w_{2},w_{3}\\}$ over $\\{w_{1}\\}$. Hence,
lexicographic and strongly monotone preferences do not coincide when there are
three or more workers.

##### Many-to-one matching.

Given an instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, a many-to-one
matching for $\mathcal{I}$ is specified by a function $\mu:F\cup W\rightarrow
2^{F\cup W}$ such that:

  * •

for every firm $f\in F$, $|\mu(f)|\leq c_{f}$ and $\mu(f)\subseteq W$, i.e.,
each firm $f$ is matched with at most $c_{f}$ workers,

  * •

for every worker $w\in W$, $|\mu(w)|\leq 1$ and $\mu(w)\subseteq F$, i.e.,
each worker is matched with at most one firm, and

  * •

for every worker-firm pair $(w,f)\in W\times F$, $\mu(w)=\\{f\\}$ if and only
if $w\in\mu(f)$.

A firm $f$ with capacity $c_{f}$ is said to be _saturated_ under the matching
$\mu$ if $|\mu(f)|=c_{f}$; otherwise, it is said to be _unsaturated_.

For simplicity, we will use the term _matching_ in place of ‘many-to-one
matching’ whenever it is clear from context. We will explicitly use the
qualifiers ‘one-to-one’ and ‘many-to-one’ when the distinction between the two
notions is relevant to the context.

##### Stability.

A many-to-one matching $\mu$ is said to be

  * •

_blocked by a firm $f$_ if there is some worker $w\in\mu(f)$ such that
$\emptyset\succ_{f}\\{w\\}$. That is, firm $f$ prefers to keep a seat vacant
rather than offer it to worker $w$.

  * •

_blocked by a worker $w$_ if $\emptyset\succ_{w}\mu(w)$. That is, worker $w$
prefers being unmatched over being matched with firm $\mu(w)$.

  * •

_blocked by a worker-firm pair $(w,f)$_ if worker $w$ prefers being matched
with firm $f$ over its current outcome under $\mu$, and, simultaneously, firm
$f$ prefers being matched with worker $w$ along with a subset of the workers
in $\mu(f)$ over being matched with the set $\mu(f)$. That is,
$f\succ_{w}\mu(w)$ and there exists a subset $S\subseteq\mu(f)$ such that
$S\cup\\{w\\}\succ_{f}\mu(f)$ and $|S\cup\\{w\\}|\leq c_{f}$.555One might ask
about blocking coalitions, wherein a set of workers and firms together block a
given matching. It is known that if a coalition of workers and firms blocks a
matching, then so does some worker-firm pair (Roth and Sotomayor, 1990,
Theorem 3.3).

  * •

_stable_ if it is not blocked by any worker, any firm, and any worker-firm
pair.

The set of stable matchings for an instance $\mathcal{I}$ is denoted by
$\mathcal{S}_{\mathcal{I}}$. Note that the above definition of stability
assumes responsive preferences. A more general definition of stability in
terms of choice sets can be found in (Sönmez, 1997).

##### Firm and worker optimal stable matchings.

It is known that given any many-to-one matching instance, there always exists
a _firm-optimal_ (respectively, _worker-optimal_) stable matching that is
weakly preferred by all firms (respectively, all workers) over any other
stable matching. This result, due to Roth (1984), is recalled in Proposition 1
below. We will write FOSM and WOSM to denote the firm-optimal and worker-
optimal stable matching, respectively.

######  Proposition 1 (Firm-optimal and worker-optimal stable matchings (Roth,
1984)).

Given any instance $\mathcal{I}$, there exist (not necessarily distinct)
stable matchings $\mu_{F},\mu_{W}\in\mathcal{S}_{\mathcal{I}}$ such that for
every stable matching $\mu\in\mathcal{S}_{\mathcal{I}}$,
$\mu_{F}(f)\succeq_{f}\mu(f)\succeq_{f}\mu_{W}(f)$ for every firm $f\in F$ and
$\mu_{W}(w)\succeq_{w}\mu(w)\succeq_{w}\mu_{F}(w)$ for every worker $w\in W$.

##### Worker-proposing and firm-proposing algorithms.

Two well-known algorithms for finding stable matchings are the worker-
proposing and firm-proposing deferred acceptance algorithms, denoted by WPDA
and FPDA, respectively. The WPDA algorithm proceeds in rounds, with each round
consisting of a _proposal_ phase followed by a _rejection_ phase. In the
proposal phase, every unmatched worker proposes to its favorite acceptable
firm that hasn’t rejected it yet. Subsequently, in the rejection phase, each
firm $f$ tentatively accepts its favorite $c_{f}$ proposals and rejects the
rest. The algorithm continues until no further proposals can be made.

Under the FPDA algorithm, firms make proposals and workers do the rejections.
Each firm makes (possibly) multiple proposals in each round according to its
ranking over individual workers. Each worker tentatively accepts its favorite
proposal and rejects the rest. Roth (1984) showed that the WPDA and FPDA
algorithms return the worker-optimal and firm-optimal stable matchings,
respectively.

##### Rural hospitals theorem.

The _rural hospitals theorem_ is a well-known result which states that, for
any fixed firm $f$, the _number_ of workers matched with $f$ is the same in
_every_ stable matching (Roth, 1984). Furthermore, if $f$ is unsaturated in
any stable matching, then it is matched with the same _set_ of workers in
_every_ stable matching (Roth, 1986).

######  Proposition 2 (Rural hospitals theorem (Roth, 1984, 1986)).

Given any instance $\mathcal{I}$, any firm $f$, and any pair of stable
matchings $\mu,\mu^{\prime}\in\mathcal{S}_{\mathcal{I}}$, we have that
$|\mu(f)|=|\mu^{\prime}(f)|$. Furthermore, if $|\mu(f)|<c_{f}$ for some stable
matching $\mu\in\mathcal{S}_{\mathcal{I}}$, then $\mu(f)=\mu^{\prime}(f)$ for
every other stable matching $\mu^{\prime}\in\mathcal{S}_{\mathcal{I}}$.

##### Canonical one-to-one instance.

Given a many-to-one instance $\mathcal{I}=\langle F,W,C,\succ\rangle$ with
responsive preferences, there exists an associated one-to-one instance
$\mathcal{I}^{\prime}=\langle P,Q,\succ^{\prime}\rangle$ obtained by creating
$c_{f}$ men for each firm $f$ and one woman for each worker. Each man’s
preferences for the women mirror the corresponding firm’s preferences for the
corresponding workers. Each woman prefers all men corresponding to a more
preferred firm over all men corresponding to any less preferred firm (in
accordance with the corresponding worker’s preferences). For any fixed firm,
all women prefer the man corresponding to its first copy over the man
representing its second copy, and so on. Any stable matching in the one-to-one
instance $\mathcal{I}^{\prime}$ maps to a unique stable matching in the many-
to-one instance $\mathcal{I}$, obtained by “compressing” the former matching
in a natural way (see Example 5 in the appendix).

######  Proposition 3 (Canonical instance (Gale and Sotomayor, 1985)).

Given any many-to-one instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, there
exists a one-to-one instance $\mathcal{I}^{\prime}=\langle
P,Q,\succ^{\prime}\rangle$ such that there is a bijection between the stable
matchings of $\mathcal{I}$ and $\mathcal{I}^{\prime}$. Furthermore, the
instance $\mathcal{I}^{\prime}$ can be constructed in polynomial time.

##  3 How Does Capacity Modification Affect Workers and Firms?

In this section, we study how changing the capacity of a firm can affect the
outcomes of the firms and the workers. Specifically, we consider the worker-
proposing and firm-proposing algorithms (WPDA and FPDA) and ask if a firm can
improve/worsen when a unit capacity is added to it. Similarly, we will ask
whether all workers can improve or if some worker can worsen when a firm’s
capacity is increased. Table 1 summarizes these trends.

The trends for capacity _decrease_ by a firm can be readily inferred from
Table 1. In particular, if increasing capacity can improve the firm’s outcome,
then going back from the new to the old instance implies that decreasing its
capacity makes it worse off.

One might intuitively expect that a firm should improve upon increasing its
capacity, as it can now be matched with a strict superset of workers.
Similarly, it is natural to think that increase in a firm’s capacity can also
make some workers better off because an extra seat at a more preferable firm
can allow some worker to switch to that firm, opening up the space for some
other interested worker and so on, thus initiating a chain of improvements.
Example 1 confirms this intuition on an instance where the workers’
preferences are identical, also known as the _master list_ setting.

######  Example 1 (All workers can improve).

Consider an instance $\mathcal{I}$ with two firms $f_{1},f_{2}$ and two
workers $w_{1},w_{2}$. The firm $f_{1}$ initially has zero capacity, while the
firm $f_{2}$ has capacity $1$ (i.e., $c_{1}=0$ and $c_{2}=1$). Both workers
have the preference $f_{1}\succ f_{2}\succ\emptyset$, and both firms have the
preference $w_{1}\succ w_{2}\succ\emptyset$. The unique stable matching for
this instance is $\mu_{1}=\\{(w_{1},f_{2})\\}$.

Now consider a new instance $\mathcal{I}^{\prime}$ obtained by adding unit
capacity to firm $f_{1}$ (i.e., $c^{\prime}_{1}=1$). The instance
$\mathcal{I}^{\prime}$ has a unique stable matching
$\mu_{2}=\\{(w_{1},f_{1}),(w_{2},f_{2})\\}$. Observe that both workers
$w_{1},w_{2}$ as well as the firm $f_{1}$ that increased its capacity are
better off under the new matching $\mu_{2}$. Furthermore, as there is only one
stable matching, the said trend holds under both FPDA and WPDA algorithms.
Also note that the two sets of stable matchings are disjoint. Thus, no
matching is simultaneously stable for both old and new instances.∎

Somewhat surprisingly, it turns out that increasing capacity can also _worsen_
a firm. This observation follows from the construction of Sönmez (1997), who
showed that any stable matching algorithm is vulnerable to manipulation via
underreporting of capacity by some firm. We recall Sönmez’s construction in
Example 2 below.

Intuitively, when workers propose under the WPDA algorithm, a firm can worsen
upon capacity increase (equivalently, improve upon capacity decrease) because
of the following reason: By having _fewer_ seats, and thus by being _more_
selective, the firm can initiate rejection chains which may prompt more
preferable workers to propose to it. On the other hand, by adding an extra
seat, a firm may be forced to accept a suboptimal set of workers. This is
precisely what drives the manipulation in Example 2.

A similar reasoning works when the firms propose under the FPDA algorithm: Due
to extra seats, a firm may be _forced_ to make additional proposals to less-
preferred workers, thus kicking off rejection chains that prompt other firms
to take away its more preferred workers. Again, this phenomenon is at play in
Example 2.

| WPDA | FPDA
---|---|---
| Yes | Yes
Can the firm improve? | [Example 1] | [Example 1]
Can the firm worsen? | Yes | Yes
[Example 2], (Sönmez, 1997) | [Example 2], (Sönmez, 1997)
| Yes | Yes
Can all workers improve? | [Example 1] | [Example 1]
Can some worker worsen? | No | No
[Corollary 1], | [Corollary 1],
|  (Gale and Sotomayor, 1985), |  (Gale and Sotomayor, 1985),
| (Roth and Sotomayor, 1990) | (Roth and Sotomayor, 1990)
Table 1: The effect of one firm increasing its capacity by $1$ on itself and
the workers, under the worker-proposing (WPDA) and firm-proposing (FPDA)
algorithms.

######  Example 2 (Increasing capacity can worsen a firm (Sönmez, 1997)).

Consider an instance $\mathcal{I}$ with two firms $f_{1},f_{2}$ and three
workers $w_{1},w_{2},w_{3}$. The workers’ preferences are given by

$\textstyle w_{1}:f_{2}\succ f_{1}\succ\emptyset\hskip
43.36243ptw_{2},w_{3}:f_{1}\succ f_{2}\succ\emptyset$

The firms have lexicographic preferences given by

$\textstyle f_{1}$
$\textstyle:\\{w_{1},w_{2},w_{3}\\}\succ\\{w_{1},w_{2}\\}\succ\\{w_{1},w_{3}\\}\succ$
$\textstyle\hskip
72.26999pt\\{w_{1}\\}\succ\\{w_{2},w_{3}\\}\succ\\{w_{2}\\}\succ\\{w_{3}\\}\succ\emptyset$
$\textstyle f_{2}$
$\textstyle:\\{w_{1},w_{2},w_{3}\\}\succ\\{w_{2},w_{3}\\}\succ\\{w_{1},w_{3}\\}\succ$
$\textstyle\hskip
72.26999pt\\{w_{3}\\}\succ\\{w_{1},w_{2}\\}\succ\\{w_{2}\\}\succ\\{w_{1}\\}\succ\emptyset$

Initially, each firm has unit capacity, i.e., $c_{1}=c_{2}=1$. In this case,
there is a unique stable matching, namely

$\mu_{1}=\\{(w_{1},f_{1}),(w_{3},f_{2})\\}.$

Now consider a new instance $\mathcal{I}^{\prime}$ derived from the instance
$\mathcal{I}$ by increasing the capacity of firm $f_{1}$ by $1$ (i.e.,
$c^{\prime}_{1}=2$ and $c^{\prime}_{2}=1$). The stable matchings for the
instance $\mathcal{I}^{\prime}$ are

$\textstyle\mu_{2}$
$\textstyle=\\{(\\{w_{1},w_{2}\\},f_{1}),(w_{3},f_{2})\\}\text{ and }$
$\textstyle\mu_{3}$
$\textstyle=\\{(\\{w_{2},w_{3}\\},f_{1}),(w_{1},f_{2})\\}.$

Here, the firm-optimal stable matching (FOSM) is $\mu_{2}$ and the worker-
optimal stable matching (WOSM) is $\mu_{3}$.

Finally, consider another instance $\mathcal{I}^{\prime\prime}$ derived from
$\mathcal{I}^{\prime}$ by increasing the capacity of firm $f_{2}$ by $1$
(i.e., $c^{\prime\prime}_{1}=2$ and $c^{\prime\prime}_{2}=2$). The unique
stable matching for the instance $\mathcal{I}^{\prime\prime}$ is $\mu_{3}$.

By virtue of being the unique stable matching, the matching $\mu_{1}$ is FOSM
and WOSM for the instance $\mathcal{I}$, and the matching $\mu_{3}$ is FOSM
and WOSM for the instance $\mathcal{I}^{\prime\prime}$. Observe that firm
$f_{1}$ prefers $\mu_{1}$ over $\mu_{3}$. Thus, under WPDA algorithm, the
transition from $\mathcal{I}$ to $\mathcal{I}^{\prime}$ exemplifies that a
firm (namely, $f_{1}$) can worsen upon increasing its capacity. Similarly, the
firm $f_{2}$ prefers $\mu_{2}$ over $\mu_{3}$. Thus, under FPDA algorithm, the
transition from $\mathcal{I}^{\prime}$ to $\mathcal{I}^{\prime\prime}$
exemplifies that a firm (namely, $f_{2}$) can worsen upon increasing its
capacity.∎

Note that Example 2 crucially uses the lexicographic preference structure;
indeed, firm $f_{1}$ prefers being matched with the solitary worker
$\\{w_{1}\\}$ over being assigned the pair $\\{w_{2},w_{3}\\}$. One might ask
whether the implication of Example 2 holds in the absence of the lexicographic
assumption. Proposition 4, due to Konishi and Ünver (2006), shows that under
_strongly monotone_ preferences and WPDA algorithm, a firm _cannot_ worsen
upon capacity increase.

######  Proposition 4 (Konishi and Ünver (2006)).

Let $\mu$ and $\mu^{\prime}$ denote the worker-optimal stable matching before
and after a firm $f$ with strongly monotone preferences increases its capacity
by $1$. Then, $\mu^{\prime}(f)\succeq_{f}\mu(f)$.

The main idea in the proof of Proposition 4 is as follows: Under WPDA, it can
be shown that if the number of workers matched with a firm $f$ does not change
upon capacity increase, then the _set_ of workers matched with $f$ also
remains the same. (Notably, this observation does not require the preferences
to be strongly monotone.) It can also be shown that the number of workers
matched with firm $f$ cannot decrease upon capacity increase. (Again, this
observation does not require strong monotonicity.). Thus, in order for the
firm’s outcome to change, it must be matched with strictly more workers in the
new matching. Strong monotonicity then implies that the firm must strictly
prefer the new outcome.

In contrast to WPDA, a firm _can_ worsen upon capacity increase under the FPDA
algorithm even under strongly monotone preferences (Example 3).

######  Example 3 (Increasing capacity can worsen a firm under strongly
monotone preferences (Sönmez, 1997)).

Consider the following instance, with two workers $w_{1},w_{2}$ and two firms
$f_{1},f_{2}$ with strongly monotone preferences:

$\textstyle w_{1}$ $\textstyle:f_{2}\succ f_{1}\succ\emptyset$
$\textstyle\hskip 28.45274ptf_{1}$
$\textstyle:\\{w_{1},w_{2}\\}\succ\\{w_{1}\\}\succ\\{w_{2}\\}\succ\emptyset$
$\textstyle w_{2}$ $\textstyle:f_{1}\succ f_{2}\succ\emptyset$
$\textstyle\hskip 28.45274ptf_{2}$
$\textstyle:\\{w_{1},w_{2}\\}\succ\\{w_{2}\\}\succ\\{w_{1}\\}\succ\emptyset$

Initially, each firm has unit capacity, i.e., $c_{1}=c_{2}=1$. In this case,
the firm-optimal stable matching is

$\mu_{1}=\\{(w_{1},f_{1}),(w_{2},f_{2})\\}.$

Upon increasing the capacity of firm $f_{2}$ to $c_{2}=2$ while keeping
$c_{1}=1$, the firm-optimal stable matching of the new instance is

$\textstyle\mu_{2}$ $\textstyle=\\{(w_{1},f_{2}),(w_{2},f_{1})\\},$

which is worse for firm $f_{2}$ compared to the old matching $\mu_{1}$.∎

Finally, we note that under both FPDA and WPDA algorithms, no worker can
worsen when a firm increases its capacity. The reason is that increasing the
capacity of a firm corresponds to “adding a man” in the corresponding
canonical one-to-one instance. Due to the increased “competition” among the
men, the outcomes of all women weakly improve (Proposition 5).

######  Proposition 5 (Gale and Sotomayor (1985); Roth and Sotomayor (1990)).

Given any one-to-one instance $\mathcal{I}=\langle P,Q,\succ\rangle$, let
$\mathcal{I}^{\prime}=\langle P\cup\\{p\\},Q,\succ^{\prime}\rangle$ be another
one-to-one instance derived from $\mathcal{I}$ by adding the man $p$ such that
the new preferences $\succ^{\prime}$ agree with the old preferences $\succ$ on
$P$ and $Q$. Let $\mu_{P}$ and $\mu_{Q}$ be the men-optimal and women-optimal
stable matchings, respectively, for $\mathcal{I}$, and let $\mu^{\prime}_{P}$
and $\mu^{\prime}_{Q}$ denote the same for $\mathcal{I}^{\prime}$. Then, for
every woman $q\in Q$, we have
$\mu^{\prime}_{P}(q)\succeq^{\prime}_{q}\mu_{P}(q)$ and
$\mu^{\prime}_{Q}(q)\succeq^{\prime}_{q}\mu_{Q}(q)$.

Using Proposition 5 on the canonical one-to-one instance, we obtain that
increasing a firm’s capacity can never worsen the outcome of any worker under
either worker-optimal or firm-optimal stable matching.

######  Corollary 1.

Let $\mu_{W}$ and $\mu_{W}^{\prime}$ denote the worker-optimal stable matching
before and after a firm increases its capacity by $1$, and let $\mu_{F}$ and
$\mu_{F}^{\prime}$ be the corresponding firm-optimal matchings. Then, for all
workers $w\in W$, $\mu^{\prime}_{W}(w)\succeq_{w}\mu_{W}(w)$ and
$\mu^{\prime}_{F}(w)\succeq_{w}\mu_{F}(w)$.

##  4 Computational Results

In this section, we will study the algorithmic aspects of capacity
modification. We will take the perspective of a central planner who can modify
the capacities of the firms to achieve a certain objective. We will focus on
two natural (and mutually incomparable) objectives: (1) _Match a pair
$(f^{*},w^{*})$_, where the goal is to determine if a fixed firm $f^{*}$ and a
fixed worker $w^{*}$ can be matched under _some_ stable matching in the
modified instance, and (2) _stabilize a matching $\mu^{*}$_, where the goal is
to check if a given matching $\mu^{*}$ can be realized as a stable outcome of
the modified instance. These objectives have previously been studied in the
one-to-one stable matching problem motivated by _control_ problems Boehmer et
al. (2021); Gupta and Jain (2023).

We will assume that the central planner can modify the firms’ capacities in
one of the following two natural ways: (1) By _adding_ capacity, wherein the
firms can receive some extra seats (the distribution can be unequal), and (2)
by _deleting_ capacity, wherein some of the existing seats can be removed.
Under both addition and deletion problems, we will assume that there is a
_global budget_ $\ell\in\mathbb{N}$ that specifies the maximum number of seats
that can be added (or removed) in aggregate across all firms.

The two objectives (match the pair and stabilize) and two actions (add and
delete) together give rise to four computational problems. One of these
problems—adding capacity to match a pair—is formally defined below. The other
problems are defined analogously.

| Match the pair $(f^{*},w^{*})$ | Stabilize the matching $\mu^{*}$
---|---|---
| Add Capacity | Delete Capacity | Add Capacity | Delete Capacity
Unbudgeted | Poly time | Poly time | Poly time | Poly time
[Theorem 1] | [Theorem 4] | [Theorem 7] | [Theorem 9]
Budgeted | NP-hard | NP-hard | Poly time | Poly time
[Theorem 2] | [Theorem 5] | [Theorem 6] | [Theorem 8]
Table 2: Summary of our computational results for adding and deleting capacity
under two problems: matching a worker-firm pair (columns 2 and 3) and
stabilizing a given matching (columns 4 and 5). The top row contains the
results for the _unbudgeted_ problem (when only the aggregate change in firms’
capacities is constrained) while the bottom row corresponds to the _budgeted_
problem (with additional constraints on individual firms).

Add Capacity To Match Pair
---
Given: |  An instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, a worker-firm pair $(w^{*},f^{*})$, and a global budget $\ell\in\mathbb{N}\cup\\{0\\}$.
Question: |  Does there exist a capacity vector $\overline{C}\in(\mathbb{N}\cup\\{0\\})^{n}$ such that $\overline{C}\geq C$, $|\overline{C}-C|_{1}\leq\ell$, and $f^{*}$ and $w^{*}$ are matched in some stable matching of the instance $\mathcal{I}^{\prime}=\langle F,W,\overline{C},\succ\rangle$?

The aforementioned problems can be naturally generalized by considering
_individual_ budgets for the firms. For example, in the add capacity problem,
in addition to the global budget $\ell$, we can also have an individual budget
$\ell_{f}$ for each firm $f$ specifying the maximum number of additional seats
that can be given to firm $f$. We call this generalization the _budgeted_
version, and use the term _unbudgeted_ to refer to the problem with only
global—but not individual—budget. Formally, the budgeted version of Add
Capacity to Match Pair problem is defined as follows:

Budgeted Add Capacity To Match Pair
---
Given: |  An instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, a worker-firm pair $(w^{*},f^{*})$, a global budget $\ell\in\mathbb{N}\cup\\{0\\}$, and an individual budget $\ell_{f}\in\mathbb{N}\cup\\{0\\}$ for each firm $f$.
Question: |  Does there exist a capacity vector $\overline{C}\in(\mathbb{N}\cup\\{0\\})^{n}$ such that $\overline{C}\geq C$, $|\overline{C}-C|_{1}\leq\ell$, $|\overline{c}_{f}-c_{f}|\leq\ell_{f}$ for each firm $f$, and $f^{*}$ and $w^{*}$ are matched in some stable matching of the instance $\mathcal{I}^{\prime}=\langle F,W,\overline{C},\succ\rangle$?

The consideration of individual budgets results in eight computational
problems overall. Table 2 summarizes our results on the computational
complexity of these problems.

A special case of the budgeted/unbudgeted problems is when the global budget
is zero, i.e., $\ell=0$. In this case, the capacities of the firms cannot be
changed, and the goal is simply to check whether a worker-firm pair
$(w^{*},f^{*})$ are matched in some stable matching for the original instance
$\mathcal{I}$, or whether a given matching $\mu^{*}$ is stable for
$\mathcal{I}$. The latter problem is straightforward. To solve the former
problem, it is helpful to consider the canonical one-to-one instance of the
given instance $\mathcal{I}$. For the one-to-one stable matching problem, a
polynomial-time algorithm is known for listing all man-woman pairs that are
matched in one or more stable matchings Gusfield (1987). Using the bijection
between the stable matchings of the two instances (Proposition 3), we obtain
an algorithm to check if the worker $w^{*}$ is matched with any copy of firm
$f^{*}$ in any stable matching.

Thus, the zero budget case can be efficiently solved for all of the
aforementioned problems. In the remainder of the section, we will consider the
case of global budgets.

### Adding Capacity to Match A Pair: Unbudgeted

Let us start with the problem of adding capacity to match a worker-firm pair
$(w^{*},f^{*})$ in the unbudgeted setting, i.e., with global but without
individual budgets.

In order to check whether the worker-firm pair $(w^{*},f^{*})$ can be matched
in some stable matching in the given instance $\mathcal{I}$ by adding capacity
to the firms, our algorithm (see Algorithm 1) considers a modified instance
$\mathcal{I}^{\prime}$ where $w^{*}$ and $f^{*}$ are already matched, and
checks if it is possible to construct a stable matching of the remaining
agents satisfying some additional conditions.

More concretely, the algorithm considers the set of firms $DF$ (short for
“distracting firms”) that the worker $w^{*}$ prefers more than the firm
$f^{*}$, and the set of workers $DW$ (short for “distracting workers”) that
the firm $f^{*}$ prefers more than $w^{*}$. Note that once the worker $w^{*}$
is matched with the firm $f^{*}$, the firms in $DF$ are the only ones that it
could potentially form a blocking pair with (due to responsive preferences).
Similarly, the workers in $DW$ are the only ones that can block with $f^{*}$
due to the forced assignment of $w^{*}$ to $f^{*}$.

The algorithm creates the modified instance $\mathcal{I}^{\prime}$ by
truncating the preference lists of the firms in $DF$ (respectively, the
workers in $DW$) by having them declare all workers ranked below $w^{*}$
(respectively, all firms ranked below $f^{*}$) as unacceptable. The truncation
step is motivated from the following observation: In the original instance
$\mathcal{I}$, there is a stable matching that matches $(w^{*},f^{*})$ after
adding capacities to the firms if and only if there exists a stable matching
in the truncated instance $\mathcal{I}^{\prime}$ such that, after the added
capacities, all firms in the set $DF$ are _saturated_ (and thus, matched with
workers they prefer more than $w^{*}$), and all workers in the set $DW$ are
_matched_ (and thus, matched either with $f^{*}$ or with firms they prefer
more than $f^{*}$).

The key observation in our proof is that the desired matching exists in the
truncated instance $\mathcal{I}^{\prime}$ after adding capacities to the firms
if and only if there exists a stable matching in the instance
$\mathcal{I}^{\prime}$ when the _entire_ capacity budget is given to the firm
$f^{*}$. This observation readily gives a polynomial-time algorithm. We defer
the detailed proof of this observation to Section C.1.

######  Theorem 1.

Add Capacity To Match Pair can be solved in polynomial time.

Input: An instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, budget $\ell$,
worker-firm pair $(w^{*},f^{*})$

Output: A matching $\mu^{*}$ and a capacity vector $C^{*}$

1 Initialize the set of distracting workers $DW\leftarrow\\{w\in
W\,:\,w\succ_{f^{*}}w^{*}\\}$

2 Initialize set of distracting firms $DF\leftarrow\\{f\in
F\,:\,f\succ_{w^{*}}f^{*}\\}$

3 Create $\mathcal{I}^{\prime}=\langle
F^{\prime},W^{\prime},C^{\prime},\succ^{\prime}\rangle$ from $\mathcal{I}$ as
follows:

4 $F^{\prime}\leftarrow F$ and $W^{\prime}\leftarrow W\setminus\\{w^{*}\\}$

5 $c^{\prime}_{f}\leftarrow c_{f}$ for all $f\neq f^{*}$ and
$c^{\prime}_{f^{*}}\leftarrow c_{f^{*}}-1$

6 Preferences $\succ^{\prime}\leftarrow\succ$ (after removing $w^{*}$)

7 For all $w\in DW$, delete acceptability of all firms $f$ s.t.
$f^{*}\succ_{w}f$ under $\succ_{w}^{\prime}$

8 For all $f\in DF$, delete acceptability of all workers $w$ s.t.
$w^{*}\succ_{f}w$ under $\succ_{f}^{\prime}$

9

10Choose the worker-optimal stable matching $\mu^{\prime}$ for
$\mathcal{I}^{\prime}$

11

12Let $UDW\leftarrow\\{w\in DW\,:\,w$ is unmatched under $\mu^{\prime}\\}$

13 Let $UDF\leftarrow\\{f\in DF\,:\,f$ is unsaturated under $\mu^{\prime}\\}$

14

15if  _$UDF\neq\emptyset$ OR $|UDW|>\ell$_ then

16 $\mu^{*}\leftarrow\emptyset$ and $C^{*}\leftarrow C$

17

18else

19 $\mu^{*}\leftarrow\mu^{\prime}\cup(\\{w^{*},UDW\\},f^{*})$

20 For all $f\neq f^{*}$, $c^{*}_{f}\leftarrow c_{f}$

21 $c^{*}_{f^{*}}\leftarrow c_{f^{*}}+|UDW|$

22

23Return $\mu^{*}$ and $C^{*}$

Algorithm 1 Add Capacity to Match Pair

### Adding Capacity to Match A Pair: Budgeted

Next, we will consider a more general problem where, in addition to the global
budget of $\ell$ seats, we are also given an individual budget $\ell_{f}$ for
each firm $f$ specifying the maximum number of seats that can be added to the
firm $f$. The goal, as before, is to determine if, after adding capacities as
per the given budgets, it is possible to match the pair $(w^{*},f^{*})$ under
some stable matching.

Note that our algorithm for the unbudgeted problem assigns the entire
additional capacity to the firm $f^{*}$, which may no longer be feasible in
the budgeted problem. It turns out that, unless $P=NP$, no polynomial-time
algorithm can be developed for this problem.

######  Theorem 2.

Budgeted Add Capacity To Match Pair is NP-hard.

To prove Theorem 2, we leverage a result of Boehmer et al. (2021) on control
problems in the one-to-one stable matching problem (which, as per our
convention, involves a matching between men and women). Specifically, Boehmer
et al. (2021) study the problem of adding a set of at most $\ell$ agents (men
or women) such that in the resulting instance, a fixed man-woman pair are
matched under some stable matching.

Interestingly, the reduction of Boehmer et al. (2021) holds even when only men
(but not women) are required to be added. Due to this additional feature, we
slightly redefine the problem of Boehmer et al. (2021) and call it
Constructive-Exists-Add-Men. The formal definition of this problem is as
follows:

Constructive-Exists-Add-Men
---
Given: |  An instance $\mathcal{I}=\langle P_{orig},Q,\succ\rangle$, a set of addable men $P_{add}$ with the preference relation $\succ$ defined over the entire set of agents $P_{orig}\cup P_{add}\cup Q$, a man-woman pair $(p^{*},q^{*})$ from the original set of agents, and a budget $\ell\in\mathbb{N}\cup\\{0\\}$.
Question: |  Does there exist a set $\overline{P}\subseteq P_{add}$ such that $|\overline{P}|\leq\ell$ and $(p^{*},q^{*})$ is part of at least one stable matching in $\langle P_{orig}\cup\overline{P},Q,\succ\rangle$?

The result of Boehmer et al. (2021) shows that Constructive-Exists-Add-Men is
NP-hard. We now use their result to show NP-hardness for Budgeted Add Capacity
To Match Pair using the following straightforward construction: For each man
in the set $P_{orig}$, we create a firm with capacity $1$ and individual
budget $\ell_{f}=0$, while for each man in the addable set $P_{add}$, we
create a firm with capacity $0$ and individual budget $\ell_{f}=1$. Adding a
seat to an individual firm corresponds to adding the associated man. The
equivalence between the solutions of the two problems now follows.

##  5 Capacity Modification v/s Preference Manipulation

So far, we have discussed qualitative (Section 3) and computational (Section
4) aspects of capacity modification from the perspective of a _central
planner_. We will now adopt the perspective of a _firm_ and compare the
different manipulation actions available to it. Specifically, we will consider
_preference manipulation_ (abbreviated as Pref), wherein a firm can misreport
its preference list without changing its capacity, and compare it with the two
capacity modification actions we have already seen, namely Add and Delete
capacity, wherein the firm can increase or decrease its capacity without
changing its preferences. These actions are formally defined below.

  * •

Pref: Under this action, a firm can report any _permutation_ of its acceptable
workers without changing its capacity.666Manipulation via permutation has been
studied by several works in the stable matching literature Teo et al. (2001);
Kobayashi and Matsui (2009, 2010); Gupta et al. (2016); Vaish and Garg (2017);
Shen et al. (2021). That is, if a firm $f$’s true preference is $\succ_{f}$,
then $\succ^{\prime}_{f}$ is a valid preference manipulation if for any worker
$w$, $w\succ_{f}\emptyset$ if and only if $w\succ^{\prime}_{f}\emptyset$.

  * •

Add/Delete: Under Add (respectively, Delete), the firm $f$ strictly increases
(respectively, decreases) its capacity $c_{f}$ by an arbitrary amount without
changing its preferences.

Our goal is to examine which mode of manipulation—Pref, Add, or Delete—is
always/sometimes more beneficial for the firm compared to the others under the
FPDA and WPDA algorithms.777Throughout, we will use the word _algorithm_
instead of _mechanism_ because we only consider one strategic agent (all other
agents are truthful) and do not consider game-theoretic equilibria.

On first glance, each manipulation action may seem to offer a distinctive
ability to the firm: Add allows the firm to either tentatively accept more
proposals (under WPDA) or make more proposals (under FPDA), thus facilitating
larger-sized (and possibly more preferable) matches. Delete, on the other
hand, can allow a firm to be more selective, which, as we have seen in Section
3, can be advantageous in certain situations. Finally, Pref can allow a firm
to trigger specific rejection chains, resulting in a potentially better set of
workers. Given the unique advantage of each manipulation action, a systematic
comparison among them is well motivated.

We compare the manipulation actions under two algorithms, WPDA and FPDA, and
focus on a fixed firm $f$. An action $X$ is said to _outperform_ action $Y$
(where $X,Y\in\\{\texttt{Pref},\texttt{Add},\texttt{Delete}\\}$) if there
exists an instance such that the outcome for firm $f$ when it performs $X$ is
strictly more preferable to it than that under $Y$.

An important insight from our analysis is that the usefulness of a
manipulation action depends on a threshold on the firm’s capacity which we
call its _peak_. For fixed preferences of all agents and fixed capacities of
the other firms, the peak of firm $f$ is the size of the largest set of
workers matched to $f$ under any stable matching when $f$ is free to choose
its capacity $c_{f}\in\mathbb{N}$.

Formally, given an instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, a firm
$f\in F$ and any $b\in\mathbb{N}$, let $\mathcal{I}^{b}=\langle
F,W,(C_{-f},b),\succ\rangle$ denote the instance derived from $\mathcal{I}$
where the capacity of firm $f$ is changed from $c_{f}$ to $b$ (and no other
changes are made); here, $C_{-f}$ denotes the capacities of firms other than
$f$. Recall that the set of stable matchings for an instance $\mathcal{I}$ is
denoted by $\mathcal{S}_{\mathcal{I}}$. The _peak_ $p_{f}$ for firm $f$ is
defined as the size of the largest set of workers $f$ is matched with under
any stable matching in the instance $\mathcal{I}^{b}$ for an arbitrary choice
of $b$, i.e.,

$p_{f}(\mathcal{I})\coloneqq\max_{b\in\mathbb{N},\,\mu\in\mathcal{S}_{\mathcal{I}^{b}}}|\mu(f)|.$

Observe that when a firm’s capacity is above its peak (i.e., $c_{f}>p_{f}$),
it must necessarily be unsaturated in any stable matching. Similarly, by the
rural hospitals theorem (Proposition 2), it follows that peak is the maximum
number of proposals a firm receives under WPDA for an arbitrarily chosen
capacity.

Figure 1 illustrates the comparison between the various manipulation actions
under the FPDA and WPDA algorithms. Observe that in each of the three regimes
in Figure 1— _below peak_ (i.e., $c_{f}<p_{f}$), _at peak_ (i.e.,
$c_{f}=p_{f}$), and _above peak_ (i.e., $c_{f}>p_{f}$)—there exist scenarios
where Delete is strictly more beneficial than Add (and similarly, more
beneficial than Pref). In fact, Delete is the only manipulation that can be
beneficial above peak. The Add operation is only beneficial to a firm if its
capacity is below peak irrespective of the matching algorithm. By contrast,
Pref is beneficial to a firm at peak under FPDA but is unhelpful under WPDA.

In the rest of this section, we will discuss the comparison between Delete and
Pref under the WPDA algorithm. We discuss the other comparisons and the
manipulation trends for strongly monotone preferences in Appendix D.

WPDA:

PrefDelAdd (a) Below peak

PrefDelAdd (b) At peak

PrefDelAdd (c) Above peak

FPDA:

PrefDelAdd (d) Below peak

PrefDelAdd (e) At peak

PrefDelAdd (f) Above peak

Figure 1:  Manipulation trends for the WPDA (top) and FPDA (bottom) algorithm
in the below peak/at peak/above peak regimes. An arrow from action $X$ to
action $Y$ denotes the existence of an instance where $X$ is strictly more
beneficial for the firm than $Y$. Each missing arrow from $X$ to $Y$ denotes
that there is (provably) no instance where $X$ is more beneficial than $Y$.

###  Delete vs Pref

#### Below Peak

When the capacity of a firm is below its peak (i.e., $c_{f}<p_{f}$), there
exists an instance where Pref can outperform Delete (as well as Add) under
WPDA.

######  Example 4 (Pref outperforms Delete and Add under WPDA).

Consider an instance $\mathcal{I}$ with three firms $f_{1},f_{2},f_{3}$ and
four workers $w_{1},w_{2},w_{3},w_{4}$. The firms have unit capacities (i.e.,
$c_{1}=c_{2}=c_{3}=1$) and have lexicographic preferences given by

$\textstyle w_{1}$ $\textstyle:f_{2}\succ f_{1}\succ f_{3}\succ\emptyset$
$\textstyle f_{1}:w_{4}\succ w_{1}\succ w_{2}\succ w_{3}$ $\textstyle
w_{2}\,,w_{3}$ $\textstyle:f_{1}\succ f_{2}\succ f_{3}\succ\emptyset$
$\textstyle f_{2}:w_{3}\succ w_{2}\succ w_{1}\succ w_{4}$ $\textstyle w_{4}$
$\textstyle:f_{3}\succ f_{1}\succ f_{2}\succ\emptyset$ $\textstyle
f_{3}:w_{1}\succ w_{4}\succ w_{2}\succ w_{3}$

Under the WPDA algorithm, firm $f_{1}$ is matched with $\\{w_{1}\\}$. If
$f_{1}$ uses Add by switching to any capacity $c_{1}\geq 2$, its WPDA match is
the set $\\{w_{2},w_{3}\\}$. It is easy to verify that the peak for firm
$f_{1}$ is $p_{f}(\mathcal{I})=2$. Thus, under $\mathcal{I}$, the capacity of
firm $f_{1}$ is below peak.

If $f_{1}$ uses Pref in the instance $\mathcal{I}$ by misreporting its
preferences to be $w_{4}\succ w_{2}\succ w_{3}\succ w_{1}$, then its WPDA
match is $\\{w_{4}\\}$, which is more preferable for $f_{1}$ (according to its
true preferences) than its match under Add. On the other hand, using Delete in
the instance $\mathcal{I}$ (by reducing the capacity to $c_{1}=0$) is the
worst outcome for $f_{1}$ as it is left unmatched.∎

We defer the example of Delete outperforming Pref under the WPDA algorithm to
Appendix D.

#### At Peak

When the capacity of the firm is equal to the peak (i.e., $c_{f}=p_{f}$), Pref
becomes unhelpful under WPDA. This is because in this case, the number of
proposals received by the firm under the WPDA algorithm is equal to its
capacity. Thus, regardless of which permutation of the acceptable workers it
reports, the firm does not reject any worker and is therefore matched with the
same set.

#### Above Peak

When the capacity of the firm is above its peak, Pref again turns out to be
unhelpful under WPDA. To show this, we first make the following observation:
For any above-peak instance, the set of workers matched with firm $f$ in _any_
stable matching is the same as its worker-optimal match in the at-peak
instance.

######  Lemma 1.

Let $\mathcal{I}=\langle F,W,C,\succ\rangle$ be an instance with a firm $f$
such that $c_{f}>p_{f}$. Let $\mu^{*}$ be the worker-optimal stable matching
of the at-peak instance $\mathcal{I}^{p_{f}}$, and $\mu$ be any stable
matching of any above-peak instance $\mathcal{I}^{b}$ (where $b>p_{f}$). Then,
$\mu(f)=\mu^{*}(f)$.

In particular, Lemma 1 shows that the set of proposals made to the firm $f$
under WPDA algorithm stays the same at or above peak.

Aziz et al. (2015) have shown that under WPDA algorithm, a necessary condition
for beneficial preference manipulation by a firm is that it must be saturated
and receive more proposals than its capacity. By combining Lemma 1 with the
observation of Aziz et al. (2015), we get that Pref is ineffective in the at-
peak and above-peak regimes under the WPDA algorithm. In fact, using Lemma 1,
we can make a similar inference for _any_ stable matching algorithm.

######  Theorem 3.

Under any stable matching algorithm, a firm cannot improve via preference
manipulation $(\texttt{Pref})$ if its capacity is strictly greater than its
peak.

The proof of Lemma 1 and Theorem 3 can be found in Appendix D.

##  6 Concluding Remarks

We studied capacity modification in the many-to-one stable matching problem
from qualitative, computational, and strategic perspectives, and provided a
comprehensive set of results. Going forward, it would be interesting to
explore algorithms for capacity modification when _both_ add and delete
operations are allowed. It would also be relevant to study situations where a
firm can simultaneously misreport its preferences and change its capacity
Kojima and Pathak (2009). Finally, experiments on synthetic or real-world data
to evaluate the frequency of availability of various manipulation actions is
another natural direction to explore Roth and Peranson (1999).

## Acknowledgments

We thank the anonymous reviewers for their helpful comments. We are also
grateful to Manshu Khanna for pointing out the relevant work of Dur and Van
der Linden (2021). RV acknowledges support from DST INSPIRE grant no.
DST/INSPIRE/04/2020/000107 and SERB grant no. CRG/2022/002621. Part of this
work was done as the SURA (Summer Undergraduate Research Award) project of SG
and SS during May-July 2023.

This material is based upon work supported by the National Science Foundation
under Grant No. DMS-1928930 and by the Alfred P. Sloan Foundation under grant
G-2021-16778, while SN was in residence at the Simons Laufer Mathematical
Sciences Institute (formerly MSRI) in Berkeley, California, during the Fall
2023 semester.

## References

  * Abdulkadiroğlu and Sönmez [2003] Atila Abdulkadiroğlu and Tayfun Sönmez.  School Choice: A Mechanism Design Approach.  _American Economic Review_ , 93(3):729–747, 2003\.
  * 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, 2005a.
  * 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, 2005b.
  * Ahani et al. [2021] Narges Ahani, Tommy Andersson, Alessandro Martinello, Alexander Teytelboym, and Andrew C Trapp.  Placement Optimization in Refugee Resettlement.  _Operations Research_ , 69(5):1468–1486, 2021\.
  * 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 2015 International Conference on Autonomous Agents and Multiagent Systems_ , pages 939–947, 2015.
  * Aziz et al. [2018] Haris Aziz, Jiayin Chen, Serge Gaspers, and Zhaohong Sun.  Stability and Pareto Optimality in Refugee Allocation Matchings.  In _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems_ , pages 964–972, 2018.
  * Bobbio et al. [2022] Federico Bobbio, Margarida Carvalho, Andrea Lodi, and Alfredo Torrico.  Capacity Variation in the Many-to-one Stable Matching.  _arXiv preprint arXiv:2205.01302_ , 2022.
  * Bobbio et al. [2023] Federico Bobbio, Margarida Carvalho, Andrea Lodi, Ignacio Rios, and Alfredo Torrico.  Capacity Planning in Stable Matching: An Application to School Choice.  In _Proceedings of the 24th ACM Conference on Economics and Computation_ , page 295, 2023.
  * 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.
  * Budish et al. [2017] Eric Budish, Gérard P Cachon, Judd B Kessler, and Abraham Othman.  Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation.  _Operations Research_ , 65(2):314–336, 2017.
  * Chen and Csáji [2023] Jiehua Chen and Gergely Csáji.  Optimal Capacity Modification for Many-To-One Matching Problems.  In _Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems_ , pages 2880–2882, 2023.
  * [12] Shradha Chettri.  New courses in 19 colleges will increase 2,000 seats in DU.  _The Hindustan Times_.  URL https://www.hindustantimes.com/delhi/new-courses-in-19-colleges-will-increase-2-000-seats-in-du/story-aKie2NTKKAB3qyJnciyNAK.html.
  * 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.
  * Dur and Van der Linden [2021] Umut Dur and Martin Van der Linden.  Capacity Design in School Choice.  _Available at SSRN 3898719_ , 2021.
  * 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 [1985] David Gale and Marilda Sotomayor.  Some Remarks on the Stable Matching Problem.  _Discrete Applied Mathematics_ , 11(3):223–232, 1985.
  * Gupta and Jain [2023] Sushmita Gupta and Pallavi Jain.  Manipulation With (Out) Money in Matching Market.  _Available at SSRN 4289699_ , 2023.
  * Gupta et al. [2016] Sushmita Gupta, Kazuo Iwama, and Shuichi Miyazaki.  Total Stability in Stable Matching Games.  In _Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory_ , pages 23:1–23:12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
  * Gusfield [1987] Dan Gusfield.  Three Fast Algorithms for Four Problems in Stable Marriage.  _SIAM Journal on Computing_ , 16(1):111–128, 1987\.
  * Gusfield and Irving [1989] Dan Gusfield and Robert W Irving.  _The Stable Marriage Problem: Structure and Algorithms_.  MIT press, 1989.
  * Kesten [2012] Onur Kesten.  On Two Kinds of Manipulation for School Choice Problems.  _Economic Theory_ , 51:677–693, 2012.
  * Knuth [1997] Donald Ervin Knuth.  _Stable Marriage and its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms_ , volume 10.  American Mathematical Soc., 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 [2007] Fuhito Kojima.  When Can Manipulations be Avoided in Two-Sided Matching Markets?–Maximal Domain Results.  _The BE Journal of Theoretical Economics_ , 7(1), 2007.
  * Kojima and Pathak [2009] Fuhito Kojima and Parag A Pathak.  Incentives and Stability in Large Two-Sided Matching Markets.  _American Economic Review_ , 99(3):608–627, 2009\.
  * Konishi and Ünver [2006] Hideo Konishi and M Utku Ünver.  Games of Capacity Manipulation in Hospital-Intern Markets.  _Social Choice and Welfare_ , 27(1):3–24, 2006\.
  * Kumano and Kurino [2022] Taro Kumano and Morimitsu Kurino.  Quota Adjustment Process.  2022\.  URL https://ies.keio.ac.jp/en/publications/22210/.
  * Manlove [2013] David Manlove.  _Algorithmics of Matching under Preferences_ , volume 2.  World Scientific, 2013.
  * Nguyen and Vohra [2018] Thanh Nguyen and Rakesh Vohra.  Near-Feasible Stable Matchings with Couples.  _American Economic Review_ , 108(11):3154–3169, 2018.
  * Roth [1982] Alvin E Roth.  The Economics of Matching: Stability and Incentives.  _Mathematics of Operations Research_ , 7(4):617–628, 1982.
  * Roth [1984] Alvin E Roth.  The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory.  _Journal of Political Economy_ , 92(6):991–1016, 1984.
  * Roth [1985] Alvin E Roth.  The College Admissions Problem is Not Equivalent to the Marriage Problem.  _Journal of Economic Theory_ , 36(2):277–288, 1985.
  * Roth [1986] Alvin E Roth.  On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets.  _Econometrica_ , pages 425–427, 1986.
  * 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 Sotomayor [1990] Alvin E Roth and Marilda A Oliveira Sotomayor.  _Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis_.  Cambridge University Press, 1990.
  * Shen et al. [2021] Weiran Shen, Yuan Deng, and Pingzhong Tang.  Coalitional Permutation Manipulations in the Gale-Shapley Algorithm.  _Artificial Intelligence_ , 301:103577, 2021.
  * Sönmez [1997] Tayfun Sönmez.  Manipulation via Capacities in Two-Sided Matching Markets.  _Journal of Economic Theory_ , 77(1):197–204, 1997.
  * Sönmez [1999] Tayfun Sönmez.  Can Pre-Arranged Matches be Avoided in Two-Sided Matching markets?  _Journal of Economic Theory_ , 86(1):148–156, 1999.
  * 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\.
  * 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 Omitted Material from Section 2

######  Example 5 (Illustration of Canonical Reduction).

Consider the following instance with two firms $f_{1},f_{2}$, and three
workers $w_{1},w_{2},w_{3}$. The workers’ preferences are as follows:

$w_{1}$: | $f_{1}\succ f_{2}\succ\emptyset$
---|---
$w_{2}$: | $f_{2}\succ f_{1}\succ\emptyset$
$w_{3}$: | $f_{2}\succ\emptyset$

The firms have strongly monotone preferences given by

$\textstyle f_{1}$
$\textstyle:\\{w_{1},w_{2}\\}\succ\\{w_{2}\\}\succ\\{w_{1}\\}\succ\emptyset$
$\textstyle f_{2}$
$\textstyle:\\{w_{1},w_{2},w_{3}\\}\succ\\{w_{2},w_{3}\\}\succ\\{w_{1},w_{3}\\}\succ$
$\textstyle\hskip
36.135pt\\{w_{1},w_{2}\\}\succ\\{w_{3}\\}\succ\\{w_{2}\\}\succ\\{w_{1}\\}\succ\emptyset$

The capacities are $c_{1}=c_{2}=2$.

The canonical one-to-one instance consists of three women $q_{1},q_{2},q_{3}$
and four men $p^{1}_{1},p^{2}_{1},p^{1}_{2},p^{2}_{2}$. Their preferences are
given by

$q_{1}$: | $p^{1}_{1}\succ p^{2}_{1}\succ p^{1}_{2}\succ p^{2}_{2}\succ\emptyset$
---|---
$q_{2}$: | $p^{1}_{2}\succ p^{2}_{2}\succ p^{1}_{1}\succ p^{2}_{1}\succ\emptyset$
$q_{3}$: | $p^{1}_{2}\succ p^{2}_{2}\succ\emptyset$

$\textstyle p^{1}_{1}$ $\textstyle:q_{2}\succ q_{1}\succ\emptyset$ $\textstyle
p^{2}_{1}$ $\textstyle:q_{2}\succ q_{1}\succ\emptyset$ $\textstyle p^{1}_{2}$
$\textstyle:q_{3}\succ q_{2}\succ q_{1}\succ\emptyset$ $\textstyle p^{2}_{2}$
$\textstyle:q_{3}\succ q_{2}\succ q_{1}\succ\emptyset$

The unique stable matching in this instance is

$\mu^{\prime}=\\{(q_{1},p^{1}_{1}),(q_{2},p^{2}_{2}),(q_{3},p^{1}_{2})\\}$

which maps to

$\mu=\\{(w_{1},f_{1}),(\\{w_{2},w_{3}\\},f_{2})\\}$

in the many-to-one instance.

##  Appendix B Omitted Material from Section 3

###  B.1 Proof of Proposition 4

Recall the statement of Proposition 4. See 4

Proposition 4 was established in the works of Konishi and Ünver [2006] and
Kojima [2007]. Below, we recall the proof with the goal of highlighting which
part of the argument requires (or does not require) strong monotonicity.

To prove Proposition 4, we will first show that upon capacity increase by a
firm $f$ under the WPDA algorithm, if the number of workers matched with $f$
does not change, then firm $f$ must be matched with the same _set_ of workers
(Lemma 2). This observation does not rely on the preferences being strongly
monotone.

######  Lemma 2.

Let $\mu$ and $\mu^{\prime}$ denote the worker-optimal stable matching before
and after a firm $f$ increases its capacity by $1$. If the number of workers
matched with $f$ remains unchanged, i.e., if $|\mu^{\prime}(f)|=|\mu(f)|$,
then the set of workers matched with $f$ also remains unchanged, i.e.,
$\mu^{\prime}(f)=\mu(f)$.

###### Proof.

(of Lemma 2) Suppose, for contradiction, that $\mu^{\prime}(f)\neq\mu(f)$.

Let $\mathcal{I}$ and $\mathcal{I}^{\prime}$ denote the instances before and
after capacity increase by firm $f$. Consider the execution of WPDA on these
instances. Let $r$ be the _first_ round in which the two executions differ.
Then, the two executions must differ in the _rejection_ phase of round $r$
such that an acceptable worker, who was rejected by firm $f$ under
$\mathcal{I}$, is tentatively accepted under $\mathcal{I}^{\prime}$. This
implies that under the old instance $\mathcal{I}$, firm $f$ had strictly more
than $c_{f}$ tentative proposals in hand after the proposal phase of round
$r$. After round $r$ under $\mathcal{I}^{\prime}$, firm $f$ will be
tentatively matched with $c_{f}+1$ workers (in other words, the firm becomes
saturated in round $r$). Since the number of workers matched with any fixed
firm weakly increases during the execution of the worker-proposing algorithm,
it follows that $|\mu^{\prime}(f)|=c_{f}+1$. However, this contradicts the
fact that $|\mu^{\prime}(f)|=|\mu(f)|$ since $|\mu(f)|\leq c_{f}$. Hence, it
must be that $\mu^{\prime}(f)=\mu(f)$. ∎

A similar argument as in the proof of Lemma 2 shows that the number of workers
matched with a firm under WPDA algorithm cannot decrease if its capacity
increases. Again, strong monotonicity is not required for this claim.

######  Proposition 6.

Let $\mu$ and $\mu^{\prime}$ denote the worker-optimal stable matching before
and after a firm $f$ increases its capacity by $1$. Then,
$|\mu^{\prime}(f)|\geq|\mu(f)|$.

We will now use strong monotonicity to finish the proof of Proposition 4.

###### Proof.

(of Proposition 4) From Proposition 6, we know that
$|\mu^{\prime}(f)|\geq|\mu(f)|$. If $|\mu^{\prime}(f)|=|\mu(f)|$, then from
Lemma 2, we know that $\mu^{\prime}(f)=\mu(f)$ and the claim follows.
Otherwise, it must be that $|\mu^{\prime}(f)|>|\mu(f)|$. Then, due to strongly
monotone preferences, it follows that $\mu^{\prime}(f)\succ_{f}\mu(f)$, as
desired. ∎

##  Appendix C Omitted Material from Section 4

###  C.1 Adding Capacity To Match A Pair: Unbudgeted

In this section, we will discuss the problem of increasing the capacities of
the firms (under an aggregate budget but without individual budgets) in order
to match a fixed worker-firm pair $(w^{*},f^{*})$ in some stable matching of
the modified instance. The relevant computational problem is formally defined
below:

Add Capacity To Match Pair
---
Given: |  An instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, a worker-firm pair $(w^{*},f^{*})$ and a global budget $\ell\in\mathbb{N}\cup\\{0\\}$.
Question: |  Does there exist a capacity vector $\overline{C}\in(\mathbb{N}\cup\\{0\\})^{n}$ such that $\overline{C}\geq C$, $|\overline{C}-C|_{1}\leq\ell$, and $f^{*}$ and $w^{*}$ are matched in some stable matching for the instance $\mathcal{I}^{\prime}=\langle F,W,\overline{C},\succ\rangle$?

We will show that Add Capacity To Match Pair can be solved in polynomial time
using Algorithm 1. Before presenting the formal proof, let us discuss a high-
level idea of the algorithm.

##### Description of the algorithm

In order to check whether the worker-firm pair $(w^{*},f^{*})$ can be matched
in some stable matching in the given instance $\mathcal{I}$ by adding capacity
to the firms, our algorithm considers a modified instance
$\mathcal{I}^{\prime}$ where the worker-firm pair $(w^{*},f^{*})$ are already
matched, and checks if it is possible to construct a stable matching of the
remaining agents satisfying some additional conditions.

More concretely, the algorithm considers the set of firms $DF$ (short for
“distracting firms”) that the worker $w^{*}$ prefers more than the firm
$f^{*}$, and the set of workers $DW$ (short for “distracting workers”) that
the firm $f^{*}$ prefers more than $w^{*}$. Note that once the worker $w^{*}$
is matched with the firm $f^{*}$, the firms in $DF$ are the only ones that it
could potentially form a blocking pair with. Similarly, the workers in $DW$
are the only ones that can block with $f^{*}$ due to the forced assignment of
$w^{*}$ to $f^{*}$.

The algorithm creates the modified instance $\mathcal{I}^{\prime}$ by
truncating the preference lists of the firms in $DF$ (respectively, the
workers in $DW$) by having them declare all workers ranked below $w^{*}$
(respectively, all firms ranked below $f^{*}$) as unacceptable. The truncation
step is motivated from the following observation: In the original instance
$\mathcal{I}$, there is a stable matching that matches $(w^{*},f^{*})$ after
adding capacities to the firms if and only if there exists a stable matching
in the truncated instance $\mathcal{I}^{\prime}$ such that, after the added
capacities, all firms in the set $DF$ are _saturated_ (and thus, matched with
workers they prefer more than $w^{*}$), and all workers in the set $DW$ are
_matched_ (and thus, matched either with $f^{*}$ or with firms they prefer
more than $f^{*}$).

The key observation in our proof is that the desired matching exists in the
truncated instance $\mathcal{I}^{\prime}$ after adding capacities to the firms
if and only if there exists a stable matching in the instance
$\mathcal{I}^{\prime}$ when the entire capacity budget is given to the firm
$f^{*}$. This observation readily gives a polynomial-time algorithm.

See 1

###### Proof.

Given an instance $\mathcal{I}=\langle F,W,C,\succ\rangle$ as the input of Add
Capacity To Match Pair, we will show that whenever it possible to add at most
$\ell$ seats so that $f^{*}$ and $w^{*}$ are matched under some stable
matching, Algorithm 1 returns a capacity vector $C^{*}$ with
$|C^{*}-C|_{1}\leq\ell$ and a stable matching $\mu^{*}$ where $f^{*}$ and
$w^{*}$ are matched. Whenever, no solution exists to the problem, Algorithm 1
returns an empty matching $\mu^{*}=\emptyset$.

Let us start with the case when a solution exists for the given instance. That
is, there exists a way of adding at most $\ell$ seats to the firms such that
$f^{*}$ and $w^{*}$ are matched under some stable matching, say $\mu$, in the
new instance. Under this stable matching $\mu$, all distracting firms $DF$
must be saturated (after the added capacities) and matched to workers they
like more than $w^{*}$. Similarly, all distracting workers $DW$ must be
matched to either $f^{*}$ or a firm they prefer over $f^{*}$. We will write
$\Delta C\in(\mathbb{N}\cup\\{0\\})^{n}$ to denote the vector of seats added
to each firm under this solution.

Now consider the truncated instance $\mathcal{I}^{\prime}$ constructed by the
algorithm. Let $\mu^{\prime}$ denote the worker-optimal stable matching for
$\mathcal{I}^{\prime}$. Recall that by the rural hospital theorem (Proposition
2), a firm is matched with the same number of workers in all stable matchings,
and any unsaturated firm is matched with the same set of workers in all stable
matchings.

######  Lemma 3.

Suppose the given instance of Add Capacity To Match Pair admits a solution.
Then, all distracting firms are saturated in the matching $\mu^{\prime}$,
i.e., $UDF=\emptyset$.

###### Proof.

(of Lemma 3) Suppose, for contradiction, that there exists a firm $f\in UDF$.
Consider increasing the capacities in the instance $\mathcal{I}^{\prime}$ by
$\Delta C$, that is, the capacity vector is $C^{\prime}+\Delta C$.

We will argue that under the capacity vector $C^{\prime}+\Delta C$, firm $f$
cannot be matched to a larger set of workers in _any_ stable matching than it
does under $\mu^{\prime}$. Note that Lemma 3 follows from this claim. Indeed,
the claim implies that firm $f$ will be unsaturated under the new capacity
vector $C^{\prime}+\Delta C$. Thus, in the concatenated matching
$\mu^{\prime}\cup(w^{*},f^{*})$, there will be a blocking pair $(w^{*},f)$,
contradicting its stability.

To prove the above claim, we make the following two observations:

  * •

First, increasing the capacity of firm $f$ does not change the set of workers
it is matched with. This is because after the capacity increase, the set of
proposals firm $f$ receives does not change under the worker-proposing
algorithm. By the rural hospitals theorem, firm $f$ must be matched with the
same set of workers in all stable matchings.

  * •

Secondly, increasing the capacity of another firm also cannot increase the
number of workers matched with $f$. To see this, consider the canonical one-
to-one instance and the firm-proposing algorithm. Increasing a seat in another
firm is analogous to introducing a new agent on the proposing side. This agent
can serve to unmatch a previously matched proposer; however, no previously
unmatched proposer gets matched in the process.

From the above observations, it follows that firm $f$ will remain unsaturated
under the capacity vector $C^{\prime}+\Delta C$, which, as previously argued,
implies the lemma. ∎

From Lemma 3, we know that a necessary condition for a solution to exist is
that all distracting firms are saturated in $\mu^{\prime}$. This check if
performed by Algorithm 1 in Line 1.

Another necessary condition for a solution to exist is that, in the matching
$\mu^{\prime}$, the number of workers in $UDW$ is at most $\ell$. Indeed, note
that adding one seat to any one of the firms can decrease the number of
unmatched distracting workers by at most one. Therefore, if the number of
workers in $UDW$ is larger than $\ell$, the given instance of Add Capacity To
Match Pair has no solution. In this case, Algorithm 1 also returns no solution
(Line 1).

We will now argue that the two necessary conditions identified above—no
unsaturated distracting firms and at most $\ell$ unmatched distracting workers
in $\mu^{\prime}$—are also sufficient. Indeed, in this case, all unmatched
distracting workers can be assigned to $f^{*}$ by increasing its capacity by
$|UDW|$. The correctness of the algorithm follows.

Finally, observe that Algorithm 1 runs in time polynomial in the number of
firms and workers. Thus, Add Capacity To Match Pair can be solved in
polynomial time. ∎

###  C.2 Adding Capacity To Match A Pair: Budgeted

We will now look at the budgeted version of the previous problem. In this
version, each firm has an individual budget over the seats that can be added
to it. Formally, the problem is defined as:

Budgeted Add Capacity To Match Pair
---
Given: |  An instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, a worker-firm pair $(w^{*},f^{*})$, a global budget $\ell\in\mathbb{N}\cup\\{0\\}$, and an individual budget $\ell_{f}\in\mathbb{N}\cup\\{0\\}$ for each firm $f$.
Question: |  Does there exist a capacity vector $\overline{C}\in(\mathbb{N}\cup\\{0\\})^{n}$ such that $\overline{C}\geq C$, $|\overline{C}-C|_{1}\leq\ell$, $|\overline{c}_{f}-c_{f}|\leq\ell_{f}$ for each firm $f$, and $f^{*}$ and $w^{*}$ are matched in some stable matching of the instance $\mathcal{I}^{\prime}=\langle F,W,\overline{C},\succ\rangle$?

The additional prescription of individual budgets makes this problem NP-hard,
in contrast to the unbudgeted version.

See 2

Boehmer et al. [2021] proved that Constructive-Exists-Add is NP-hard even when
agents of only one side are in the addable set. We call this problem
Constructive-Exists-Add-Men and show that it reduces to Budgeted Add Capacity
To Match Pair. Formally, Constructive-Exists-Add-Men is defined as:

Constructive-Exists-Add-Men
---
Given: |  An instance $\mathcal{I}=\langle P_{orig},Q,\succ\rangle$, a set of addable men $P_{add}$ with the preference relation $\succ$ defined over the entire set of agents $P_{orig}\cup P_{add}\cup Q$, a man-woman pair $(p^{*},q^{*})$ from the original set of agents, and a budget $\ell\in\mathbb{N}\cup\\{0\\}$.
Question: |  Does there exist a set $\overline{P}\subseteq P_{add}$ such that $|\overline{P}|\leq\ell$ and $(p^{*},q^{*})$ is part of at least one stable matching in $\langle P_{orig}\cup\overline{P},Q,\succ\rangle$?

######  Lemma 4 (Boehmer et al. [2021]).

Constructive-Exists-Add-Men is NP-hard.

The fact that only men are the addable agents in Constructive-Exists-Add-Men
allows us to make a reduction from Constructive-Exists-Add-Men to Budgeted Add
Capacity To Match Pair.

See 2

###### Proof.

Let the given instance of Constructive-Exists-Add-Men be
$\langle\mathcal{I}=\langle
P_{orig},Q,\succ\rangle,P_{add},\ell,p^{*},q^{*},\rangle$. We construct an
instance $\langle\mathcal{I}^{\prime}=\langle
F,W,C,\succ^{\prime}\rangle,\ell^{\prime},\\{\ell^{\prime}_{f}:f\in
F\\},f^{*},w^{*}\rangle$ of Budgeted Add Capacity To Match Pair as follows:
Create a firm $f_{p}$ with capacity 1 and individual budget 0 for each man $p$
in $P_{orig}$, a firm $f_{p}$ with capacity 0 and individual budget 1 for each
man $p$ in $P_{add}$, a worker $w_{q}$ for each woman $q$ in $Q$. We keep the
same preferences over the corresponding agents and the same global budget. We
set $f^{*}=f_{p^{*}}$ and $w^{*}=w_{q^{*}}$.

It is clear that adding an agent in the original instance is equivalent to
increasing the capacity of its corresponding firm in the reduced instance.
Since Constructive-Exists-Add-Men is NP-hard by Lemma 4, we conclude that
Budgeted Add Capacity To Match Pair is NP-hard too. ∎

###  C.3 Deleting Capacity To Match A Pair: Unbudgeted

We now look at the problem of deleting capacity to match a worker-firm pair
$(f^{*},w^{*})$ in the unbudgeted setting. Formally the problem is defined as
follows:

Delete Capacity To Match Pair
---
Given: |  An instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, a worker-firm pair $(w^{*},f^{*})$, a global budget $\ell\in\mathbb{N}\cup\\{0\\}$
Question: |  Does there exist a capacity vector $\overline{C}\in(\mathbb{N}\cup\\{0\\})^{n}$ such that $C\geq\overline{C}$, $|C-\overline{C}|_{1}\leq\ell$, and $w^{*}$ and $f^{*}$ are matched in some stable matching for the instance $\mathcal{I}^{\prime}=\langle F,W,\overline{C},\succ\rangle$?

We can solve this problem in polynomial time, as we will show now.

######  Theorem 4.

Delete Capacity To Match Pair can be solved in polynomial time.

We will prove this theorem by showing a reduction into a problem solvable in
polynomial time. First, we state the following problem in which we try to
match a man-woman pair by deleting only men.

Constructive-Exists-Delete-Men
---
Given: |  An instance $\mathcal{I}=\langle P,Q,\succ\rangle$, a man-woman pair $(p^{*},q^{*})$ and a budget $\ell\in\mathbb{N}\cup\\{0\\})$.
Question: |  Does there exist a set $\overline{P}\subseteq P$ such that $|\overline{P}|\leq\ell$ and the pair $(p^{*},q^{*})$ is part of at least one matching in $\langle P\setminus\overline{P},Q,\succ\rangle$?

Note that this problem is not a special case, but rather a variant of
Constructive-Exists-Delete defined in Boehmer et al. [2021]. We will modify
the polynomial time Constructive-Exists-Delete algorithm given at [Boehmer et
al., 2021, Theorem 2] to solve Constructive-Exists-Delete-Men in polynomial
time.

The algorithm is based on the idea that all men(or women) preferred by
$q^{*}$(or $p^{*}$) over each other must either be deleted or matched with
someone they prefer over $q^{*}$(or $p^{*}$). If this is not done, all such
men(or women) will form a blocking pair with $q^{*}$(or $p^{*}$). To find the
set of agents to be deleted, we construct a instance where all these men(or
women) can only be matched with someone they prefer over $q^{*}$(or $p^{*}$)
or remain unmatched. All the unmatched agents are the agents which necessarily
must be deleted. Hence, if this set contains a woman or is larger than the
given budget, then we cannot achieve our goal. Otherwise, we claim that this
set of agents, which consists of only men is necessary and also sufficient to
match $(p^{*},q^{*})$ in some matching.

1

Input: A Constructive-Exists-Delete-Men instance $\langle\mathcal{I}=\langle
P,Q,\succ\rangle,\ell,p^{*},q^{*}\rangle$

Output: A set $\overline{P}$ which solves the given instance and a stable
matching $\mu$ in $\mathcal{I}\setminus\overline{P}$ containing
$(p^{*},q^{*})$

2 $A\leftarrow$ the set of men which $q^{*}$ prefers over $p*$

3 $B\leftarrow$ the set of women which $p^{*}$ prefers over $q^{*}$

4 Create a new one-to-one stable matching instance
$\mathcal{I}^{\prime}=\langle P^{\prime},Q^{\prime},\succ^{\prime}\rangle$ by
defining $P^{\prime}=P\setminus\\{p^{*}\\}$,
$Q^{\prime}=Q\setminus\\{q^{*}\\}$. For every agent $a$ in $A\cup B$, we
define $\succ^{\prime}_{a}$ from $\succ_{a}$ by deleting the acceptability of
agents less preferred to $p^{*}$ or $q^{*}$. For every agent $a$ in
$P^{\prime}\cup Q^{\prime}\setminus(A\cup B)$, we define $\succ^{\prime}_{a}$
same as $\succ_{a}$.

5

6Compute a stable matching $\mu^{\prime}$ in $\mathcal{I}^{\prime}$.

7

8Let $\overline{P}\leftarrow$ the set of agents in $A\cup B$ that are
unmatched in $\mu^{\prime}$

9

10if  _$|\overline{P}|\leq\ell$ and $\overline{P}$ contains no woman_ then

11 Output $\overline{P}$ and $\mu^{\prime}\cup(p^{*},q^{*})$

12

13else

Output $\emptyset$ and $\emptyset$

/* Cannot match $(p^{*},q^{*})$ within budget */

14

15

16

Algorithm 2 Constructive-Exists-Delete-Men algorithm

To prove that Algorithm 2 correctly solves Constructive-Exists-Delete-Men, we
need to use the following lemmas on the influence of a delete operation on the
set of agents matched in a stable matching.

######  Lemma 5 (Boehmer et al. [2021]).

Let $\mathcal{I}=\langle P,Q,\succ\rangle$ be a stable matching instance and
$a\in P\cup Q$ be some agent. Then, there exists at most one agent
$a^{\prime}\in P\cup Q$ which was unassigned in $\mathcal{I}$, and is matched
in $\mathcal{I}\setminus\\{a\\}$.

######  Lemma 6.

Let $\mathcal{I}=\langle P,Q,\succ\rangle$ be a stable matching instance and
$p\in P$ be some man. Then, there cannot exist a woman $q\in Q$ who was
unassigned in a stable matching $\mathcal{I}$, and is matched in a stable
matching in $\mathcal{I}\setminus\\{p\\}$.

###### Proof.

Let $\mu$ and $\mu^{\prime}$ be the women-optimal stable matching in
$\mathcal{I}\setminus\\{p\\}$ and $\mathcal{I}$ respectively. Using
Proposition 5 we know that $\mu^{\prime}$ is weakly preferred by all women
over $\mu$.

For the sake of contradiction, assume that there is a woman $q\in Q$ such that
$q$ is unassigned in some stable matching of $\mathcal{I}$, and is matched in
some stable matching of $\mathcal{I}\setminus\\{p\\}$. Proposition 2 states
that the set of unmatched agents in any stable matching in a given instance is
the same. Hence, $q$ is also unmatched in $\mu^{\prime}$. Since,
$\mu^{\prime}$ is weakly preferred by all women over $\mu$, $q$ is also
unmatched in $\mu$. Again using Proposition 2, we get that $q$ is unmatched in
all stable matchings of $\mathcal{I}\setminus\\{p\\}$, which is a
contradiction. ∎

We now proceed with the proof of correctness of Algorithm 2. Our proof differs
from the proof given by Boehmer et al. [2021] for their algorithm in the case
when $\overline{P}$ contains women.

######  Lemma 7.

Constructive-Exists-Delete-Men can be solved in polynomial time.

###### Proof.

We will first show that Algorithm 2 solves any given instance
$\langle\mathcal{I}=\langle P,Q,\succ\rangle,\ell,p^{*},q^{*}\rangle$ of
Constructive-Exists-Delete-Men correctly. Consider the set $\overline{P}$
constructed by the algorithm.

Firstly, we will show that if $|\overline{P}|\leq\ell$ and $\overline{P}$
contains no women, then the given instance is solved by $\overline{P}$ and
$\mu=\mu^{\prime}\cup(p^{*},q^{*})$ is a stable matching in the instance
$\mathcal{I}\setminus\overline{P}$. Note that $\overline{P}$ is within budget
and contains no women, hence it is a valid set of men that can be deleted. For
the sake of contradiction, assume that there exists a blocking pair $(p,q)$ in
$\mu$. $p\neq p^{*}$ because all agents that $p^{*}$ prefers over $q^{*}$ are
either deleted or matched to someone they prefer over $p^{*}$. Similarly
$q\neq q^{*}$. Since $(p,q)$ is not a blocking pair in
$\mathcal{I}^{\prime}\setminus\overline{P}$, it contains an agent $a\in(A\cup
B)\setminus\overline{P}$, and $a$ prefers $q^{*}$ to $q$ if $a=p$ or $a$
prefers $p^{*}$ to $p$ if $a=q$. Without loss of generality, we assume that
$a=p$. As $p$ is matched in $\mu^{\prime}$, he prefers
$\mu^{\prime}(p)=\mu(p)$ to $q^{*}$. Thus, $p$ prefers $\mu(p)$ to $q$, a
contradiction to $(p,q)$ being blocking for $\mu$. Hence, there are no
blocking pairs in $\mu$ and $\overline{P}$ solves the given instance.

Now we will show that if $|\overline{P}|>\ell$, then it is not possible to
solve the given instance without exceeding the budget. For the sake of
contradiction, assume that there exists a set of men
$\overline{P}^{\prime}=\\{p_{1},\dots,p_{k}\\}$ with $k\leq\ell$ such that
$\mathcal{I}\setminus\overline{P}^{\prime}$ admits a stable matching $\mu$
containing $(p^{*},q^{*})$. For each $i\in\\{0,1,\dots,k\\}$, let
$\mu^{\prime}_{i}$ be a stable matching in
$\mathcal{I}^{\prime}\setminus\\{p_{1},\dots,p_{i}\\}$. Since Proposition 2
guarantees that for a given instance, the set of unmatched agents in any
stable matching is the same, the choice of $\mu^{\prime}_{i}$ does not matter
for the purposes of the proof. By the definition of $\overline{P}$, all agents
in $\overline{P}$ are unassigned in $\mu_{0}^{\prime}$. Also, each agent $a\in
A\cup B$ is either part of $\overline{P}^{\prime}$ or prefers $\mu(a)$ to
$p^{*}$ or $q^{*}$ due to the stability of $\mu$. Hence, $\mu$ restricted to
$\mathcal{I}^{\prime}\setminus\overline{P}^{\prime}$ is also stable; in
particular, every agent $a\in\overline{P}$ is either contained in
$\overline{P}^{\prime}$ or matched in $\mu^{\prime}_{k}$. Since
$k\leq\ell<|\overline{P}|$, there exists an $i$ and two agents
$a,a^{\prime}\in\overline{P}$ which are unassigned in $\mu^{\prime}_{i-1}$ and
not contained in $\\{p_{1},\dots,p_{i-1}\\}$ but matched in $\mu^{\prime}_{i}$
or contained in $\\{p_{1},\dots,p_{i}\\}$. By Lemma 5, it is not possible that
both $a$ and $a^{\prime}$ are unassigned in $\mu^{\prime}_{i-1}$ but matched
in $\mu^{\prime}_{i}$. Consequently, without loss of generality, let $a=p_{i}$
with $a$ being unassigned in $\mu^{\prime}_{i-1}$, and $a^{\prime}$ is matched
in $\mu^{\prime}_{i}$ but unassigned in $\mu^{\prime}_{i-1}$. However, since
$a$ is unassigned in $\mu^{\prime}_{i-1}$, deleting it does not change the set
of matched agents. This contradicts $a^{\prime}$ being matched in
$\mu^{\prime}_{i}$ but unassigned in $\mu^{\prime}_{i-1}$. Hence, such a set
of men $\overline{P}^{\prime}$ cannot exist.

Finally, we will show that if $\overline{P}$ contains any woman, then it is
not possible to solve the given instance. For the sake of contradiction,
assume that there exists a set of men
$\overline{P}^{\prime}=\\{p_{1},\dots,p_{k}\\}$ with $k\leq\ell$ such that
$\mathcal{I}\setminus\overline{P}^{\prime}$ admits a stable matching $\mu$
containing $(p^{*},q^{*})$. Let $\mu^{\prime}$ and $\mu^{\prime}_{k}$ be
stable matchings in $\mathcal{I}^{\prime}$ and
$\mathcal{I}^{\prime}\setminus\overline{P}^{\prime}$ respectively. As in the
previous case, every agent $a\in\overline{P}$ is either contained in
$\overline{P}^{\prime}$ or matched in $\mu^{\prime}_{k}$. Choose a woman
$q\in\overline{P}\cap Q$. Note that $q$ is unassigned in $\mu^{\prime}$. By
Lemma 6, deleting a man from $\mu^{\prime}$ cannot match $q$. Consequently,
deleting a set of men also cannot match $q$. Hence,
$q\notin\overline{P}^{\prime}$ and $q$ is unassigned in $\mu^{\prime}_{k}$,
which is a contradiction. Hence, such a set of men $\overline{P}^{\prime}$
cannot exist.

This completes the proof of correctness. The complexity clearly follows from
the fact that we can create the new instance in linear time and a stable
matching can be computed in polynomial time.

∎

Now we will define a new one-to-one matching problem in which our goal is to
match a woman $q^{*}$ with any man from a given set $P^{*}$. We will show that
this problem can be solved in polynomial time too via a reduction to multiple
instances of Constructive-Exists-Delete-Men.

Multiple-Constructive-Exists-Delete-Men
---
Given: |  An instance $\mathcal{I}=\langle P,Q,\succ\rangle$, a subset $P^{*}\subseteq P$ of men, a woman $q^{*}$, and a budget $\ell\in\mathbb{N}\cup\\{0\\}$.
Question: |  Does there exist a set $\overline{P}\subseteq P$ such that $|\overline{P}|\leq\ell$ and the pair $(p^{*},q^{*})$ is part of at least one matching in $\langle P\setminus\overline{P},Q,\succ\rangle$ for at least one man $p^{*}\in P^{*}$?

The idea is that, for every man $p$ in $P^{*}$, we will try to match him with
$q^{*}$ by creating an instance of Constructive-Exists-Delete-Men in which our
goal is to match $(p^{*},q^{*})$.

######  Lemma 8.

Multiple-Constructive-Exists-Delete-Men can be solved in polynomial time.

###### Proof.

We will show that the given instance of
Multiple-Constructive-Exists-Delete-Men can be solved by reducing to a set of
instances of Constructive-Exists-Delete-Men.

Let $\langle\mathcal{I}=\langle P,Q,\succ\rangle,\ell,P^{*},q^{*}\rangle$
denote the given instance of Multiple-Constructive-Exists-Delete-Men. For
every man $p\in P^{*}$, we create a reduced instance
$\langle\mathcal{I}_{p}=\mathcal{I},\ell_{p}=\ell,p,q^{*}\rangle$ of
Constructive-Exists-Delete-Men.

First, we will show that if the given instance of Multiple-Constructive-
Exists-Delete-Men is solved by $\overline{P}$, then at least one of the
reduced instances of Constructive-Exists-Delete-Men has a solution. Let
$\mathcal{I}\setminus\overline{P}$ admit a stable matching $\mu$ containing
the pair $(p^{*},q^{*})$ for some $p^{*}\in P^{*}$. Let
$\langle\mathcal{I}_{p^{*}}=\mathcal{I},\ell_{p^{*}}=\ell,p^{*},q^{*}\rangle$
be the reduced instance of Constructive-Exists-Delete-Men corresponding to
this $p^{*}$. Clearly $\mu$ is a stable matching containing $(p^{*},q^{*})$ in
$\mathcal{I}_{p^{*}}\setminus\overline{P}$ since $\mu$ is stable in
$\mathcal{I}\setminus\overline{P}$. Hence, at least one the reduced instances
of Constructive-Exists-Delete-Men is solved by $P$.

Now, will show that if even one of the reduced instances(say corresponding to
$p^{*}$) has a solution $\overline{P}$, then the original instance is also
solved by $\overline{P}$. Let $\mathcal{I}_{p^{*}}\setminus\overline{P}$ admit
a stable matching $\mu$ containing the pair $(p^{*},q^{*})$. Since $\mu$ is
stable in $\mathcal{I}_{p^{*}}\setminus\overline{P}$, $\mu$ is also stable in
$\mathcal{I}\setminus\overline{P}$ and contains the pair $(p^{*},q^{*})$.
Hence the given instance of Multiple-Constructive-Exists-Delete-Men is also
solved by $\overline{P}$.

Since Constructive-Exists-Delete-Men is solvable in polynomial time by Lemma 7
and $|P^{*}|$ is polynomial in the input, solving $|P^{*}|$ instances of
Constructive-Exists-Delete-Men is also possible in polynomial time. Hence, we
conclude that Multiple-Constructive-Exists-Delete-Men is solvable in
polynomial time. ∎

Finally, we prove that Delete Capacity To Match Pair is solvable in polynomial
time by showing a reduction to Multiple-Constructive-Exists-Delete-Men. The
reduction is straightforward using the canonical one-to-one reduction.

###### Proof.

(of Theorem 4) We give a reduction from Delete Capacity To Match Pair to
Multiple-Constructive-Exists-Delete-Men. Let $\langle\mathcal{I}=\langle
F,W,C,\succ\rangle,\ell,f^{*},w^{*}\rangle$ denote the given instance of
Delete Capacity To Match Pair. We will construct an instance
$\langle\mathcal{I}^{\prime}=\langle
P^{\prime},Q^{\prime},\succ^{\prime}\rangle,\ell^{\prime},P^{*},q^{*}\rangle$
of Multiple-Constructive-Exists-Delete-Men in which $\mathcal{I}^{\prime}$ is
the canonical one-to-one reduction of $\mathcal{I}$, $\ell^{\prime}=\ell$,
$q^{*}$ is the woman corresponding to $w^{*}$, and $P^{*}$ is the set of men
corresponding to copies of $f^{*}$.

First assume that the given instance of Delete Capacity To Match Pair is
solved by $\overline{C}$ such that $\langle F,W,\overline{C},\succ\rangle$
admits a stable matching $\mu$ containing $(f^{*},w^{*})$. Let $\overline{P}$
be the set of men corresponding to the deleted capacities. Then, deleting
$\overline{P}$ from $\mathcal{I}^{\prime}$ solves the reduced instance of
Multiple-Constructive-Exists-Delete-Men. Observe that
$\mathcal{I}^{\prime}\setminus\overline{P}$ is the canonical one-to-one
reduction of $\langle F,W,\overline{C},\succ\rangle$. Hence, the stable
matching corresponding to $\mu$ in $\mathcal{I}^{\prime}\setminus\overline{P}$
will match $q^{*}$ with some man corresponding to a copy of $f^{*}$, and this
man will be in $P^{*}$.

Similarly we can construct a solution of the given instance of Delete Capacity
To Match Pair given a solution of the reduced instance of Multiple-
Constructive-Exists-Delete-Men.

Hence, we proved that Delete Capacity To Match Pair reduces to Multiple-
Constructive-Exists-Delete-Men. Since Multiple-Constructive-Exists-Delete-Men
can be solved in polynomial time by Lemma 8, we can solve Delete Capacity To
Match Pair in polynomial time too.

∎

###  C.4 Deleting Capacity To Match A Pair: Budgeted

We now look at the budgeted version of the previous problem, which can be
defined formally as follows:

Budgeted Delete Capacity To Match Pair
---
Given: |  An instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, a worker-firm pair $(w^{*},f^{*})$, a global budget $\ell\in\mathbb{N}\cup\\{0\\}$, and an individual budget $\ell_{f}\in\mathbb{N}\cup\\{0\\}$ for each firm $f\in F$.
Question: |  Does there exist a capacity vector $\overline{C}\in(\mathbb{N}\cup\\{0\\})^{n}$ such that $C\geq\overline{C}$, $|C-\overline{C}|_{1}\leq\ell$ and for every $f\in F$, $|c_{f}-\overline{c}_{f}|\leq\ell_{f}$, and $w^{*}$ and $f^{*}$ are matched in some stable matching for the instance $\mathcal{I}^{\prime}=\langle F,W,\overline{C},\succ\rangle$?

In contrast to the unbudgeted version, this problem is NP-hard.

######  Theorem 5.

Budgeted Delete Capacity To Match Pair is NP-hard.

We give a reduction from Constructive-Exists-Add-Men to Budgeted Delete
Capacity To Match Pair. Constructive-Exists-Add-Men was already shown to be
NP-hard at Lemma 4. The idea of the reduction is that we introduce a firm with
capacity 1 and individual budget 0 for every woman and a worker for every man.
Additionally, we introduce a firm with capacity 1 and individual budget 1 for
every man in $P_{add}$ which creates a soulmate pair with the worker
corresponding to this man. Thus, the deletion of capacity from such firms is
equivalent to the addition of a man in the original instance.

###### Proof.

Let $\langle\mathcal{I}=\langle
P_{orig},Q,\succ\rangle,\ell,P_{add},p^{*},q^{*}\rangle$ denote the given
instance of Constructive-Exists-Add-Men. We create a reduced instance
$\langle\mathcal{I}^{\prime}=\langle
F^{\prime},W^{\prime},C^{\prime},\succ^{\prime}\rangle,\ell^{\prime},\\{\ell^{\prime}_{f}:f\in
F\\},f^{*},w^{*}\rangle$ of Budgeted Delete Capacity To Match Pair as follows:

For every woman $q\in Q$, create a firm $f^{\prime}_{q}$ with capacity 1 and
individual budget 0 in the reduced instance $\mathcal{I}^{\prime}$. For every
man $p\in P_{orig}\cup P_{add}$, create a worker $w^{\prime}_{p}$ in the
reduced instance $\mathcal{I}^{\prime}$. The preference relation of these
agents over each other is kept the same as in the original instance
$\mathcal{I}$. Additionally, for every man $p\in P_{add}$, create a firm
$f^{\prime}_{p}$ with capacity 1 and individual budget 1 in the reduced
instance $\mathcal{I}^{\prime}$. These firms only consider their corresponding
worker $w^{\prime}_{p}$ acceptable. Similarly, these workers also prefer their
corresponding firm over other firms corresponding to women. In this way, these
workers and firms corresponding to each man in $P_{add}$ form soulmate pairs.
Finally, we set $\ell^{\prime}=\ell,f^{*}=f^{\prime}_{q^{*}}$ and
$w^{*}=w^{\prime}_{p^{*}}$.

First, assume that the given instance of Constructive-Exists-Add-Men is solved
by $\overline{P}$ such that $\mu$ is a stable matching in
$\mathcal{I}\cup\overline{P}$ containing $(p^{*},q^{*})$. We will show that
deleting the capacity of $f^{\prime}_{p}$ corresponding to each man
$p\in\overline{P}$ solves the reduced instance of Budgeted Delete Capacity To
Match Pair. Formally, this capacity vector $\overline{C}$ is defined as
$\overline{c}_{f^{\prime}_{p}}=0$ if $p\in\overline{P}$ and
$\overline{c}_{f^{\prime}_{a}}=1$ if $a\in(Q\cup
P_{add})\setminus\overline{P}$. Note that this capacity vector satisfies the
budget constraints. Define a matching $\mu^{\prime}$ in the instance $\langle
W^{\prime},F^{\prime},\overline{C},\succ^{\prime}\rangle$ as follows:

$\textstyle\mu^{\prime}=\\{(w^{\prime}_{p},f^{\prime}_{\mu(p)}):p\in
P_{orig}\cup\overline{P},p\textnormal{ is matched in }\mu\\}\cup\\\
\textstyle\\{(w^{\prime}_{p},f^{\prime}_{p}):p\in
P_{add}\setminus\overline{P}\\}$

Note that $\mu^{\prime}$ contains the pair $(w^{*},f^{*})$ and satisfies the
capacity vector we defined earlier. Now we prove that $\mu^{\prime}$ is
stable.

None of the workers or firms corresponding to a man in
$P_{add}\setminus\overline{P}$ can form a blocking pair because they are
matched with their soulmate. Assume for the sake of contradiction that
$(w^{\prime}_{p},f^{\prime}_{q})$ is a blocking pair in $\mu^{\prime}$ with
$p\in P_{orig}\cup\overline{P}$. However, this would imply that $(p,q)$ is a
blocking pair in $\mu$ because the preferences over corresponding agents are
kept same in $\mu^{\prime}$ and $\mu$. This is a contradiction to the
stability of $\mu$, and consequently we prove that $\mu^{\prime}$ is stable.
Hence, the reduced instance of Budgeted Delete Capacity To Match Pair is
solved by $\overline{C}$.

Now, assume that the reduced instance of Budgeted Delete Capacity To Match
Pair is solved by $\overline{C}$ such that the modified instance contains a
stable matching $\mu^{\prime}$ with the pair $(w^{*},f^{*})$. We will show
that adding the men corresponding to the firms whose capacity is deleted,
solves the given instance of Constructive-Exists-Add-Men. Notice that we can
only delete capacity from the firms corresponding to a man in $P_{add}$, due
to the individual budgets. Formally, this set is $\overline{P}=\\{p\in
P_{add}:\overline{c}_{f^{\prime}_{p}}=0\\}$. Note that this set has size
smaller than $\ell$. Define a matching $\mu$ in the instance
$\mathcal{I}\cup\overline{P}$ as follows:

$\mu=\\{(p,q):\mu^{\prime}(w^{\prime}_{p})=f^{\prime}_{q},p\in{P_{orig}\cup\overline{P}}\\}$

Note that $\mu$ also contains the pair $(p^{*},q^{*})$. For the sake of
contradiction, let $(p,q)$ be a blocking pair in $\mu$. This would imply
$(w^{\prime}_{p},f^{\prime}_{q})$ is a blocking pair in $\mu^{\prime}$ because
the preferences over corresponding agents are kept same in $\mu$ and
$\mu^{\prime}$. This is a contradiction to the stability of $\mu^{\prime}$,
and consequently we prove that $\mu$ is stable. Hence, the given instance of
Constructive-Exists-Add-Men is solved by the $\overline{P}$ we defined.

This completes the proof of reduction.

Since Constructive-Exists-Add-Men is NP-hard by Lemma 4, we conclude that
Budgeted Delete Capacity To Match Pair is NP-hard too.

∎

###  C.5 Adding Capacity To Stabilize A Matching: Budgeted

In this problem, our goal is to add seats to firms in order to make a subset
of the given matching stable. In the budgeted version, we have a global budget
on the total number of seats added to the instance and an individual budget on
the number of seats added to each firm. We also impose an additional
constraint of preferences being complete. The problem can be defined as:

Budgeted Add Capacity To Stabilize Matching
---
Given: |  An instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, individual budget $\ell_{f}\in\mathbb{N}\cup\\{0\\}$ for each firm $f\in F$, a global budget $\ell\in\mathbb{N}\cup\\{0\\}$, a matching $\mu^{*}$ with $|\mu^{*}(f)|\leq c_{f}+\ell_{f}$ for each $f\in F$. Preferences $\succ$ are complete.
Question: |  Does there exist a capacity vector $\overline{C}\in(\mathbb{N}\cup\\{0\\})^{n}$ such that $\overline{C}\geq C,|\overline{C}-C|_{1}\leq\ell$ and $|\overline{c}_{f}-c_{f}|\leq\ell_{f}$ for each $f\in F$ and there is a matching $\mu$ stable for $\mathcal{I}^{\prime}=\langle F,W,\overline{C},\succ\rangle$ which is a subset of $\mu^{*}$, i.e., $\mu(f)\subseteq\mu^{*}(f)$ for each $f$ and $\mu(w)=\mu^{*}(w)$ or $\emptyset$ for each $w$ ?

We will show that Budgeted Add Capacity To Stabilize Matching can be solved in
polynomial time by using the fact that its canonical one-to-one extension can
be solved in polynomial time.

######  Theorem 6.

Budgeted Add Capacity To Stabilize Matching can be solved in polynomial time.

We define Exact-Exists-Add-Men, which is a special case of Exact-Exists-Add in
Boehmer et al. [2021] because in this problem there are no women in the
addable set of agents.

Exact-Exists-Add-Men
---
Given: |  An instance $\mathcal{I}=\langle P_{orig},Q,\succ\rangle$, a set of addable men $P_{add}$, a global budget $\ell$, and a matching $\mu^{*}$ defined over $P_{orig}\cup P_{add}\cup Q$. Additionally, the preferences $\succ$ are complete and defined over $P_{orig}\cup P_{add}\cup Q$.
Question: |  Does there exist a set of men $\overline{P}\subseteq P_{add}$ such that $|\overline{P}|\leq\ell$ and the matching $\mu^{*}$ when restricted to $P_{orig}\cup\overline{P}\cup Q$ is stable. More formally, does there exist a stable matching $\mu$ in $\mathcal{I}\cup\overline{P}$ such that for each $p\in P_{orig}\cup\overline{P}$, $\mu(p)=\mu^{*}(p)$ and for each woman $q\in Q$, $\mu(q)=\mu^{*}(q)$ if $\mu^{*}(q)\in P_{orig}\cup\overline{P}$ or otherwise $\mu(q)=\emptyset$?

Since Exact-Exists-Add was shown to be solvable in polynomial time by [Boehmer
et al., 2021, Algorithm 1], we can solve Exact-Exists-Add-Men too.

######  Lemma 9 (Boehmer et al. [2021]).

Exact-Exists-Add-Men can be solved in polynomial time.

Now we show that Budgeted Add Capacity To Stabilize Matching can be solved in
polynomial time by giving a reduction to Exact-Exists-Add-Men. The reduction
is the usual canonical reduction along with making the one to one version of
the given matching $\mu^{*}$. For that, we match the copies of a firm $f$ with
the workers in $\mu^{*}(f)$ in the order of the firm’s preference. So if a
worker in $\mu^{*}(f)$ is more preferred, it is assigned a more preferred copy
of the firm (with a lower index).

###### .

(of Theorem 6) We give a reduction from Budgeted Add Capacity To Stabilize
Matching to Exact-Exists-Add-Men. Let $\langle\mathcal{I}=\langle
F,W,C,\succ\rangle,\ell,\\{\ell_{f}:f\in F\\},\mu^{*}\rangle$ denote the given
instance of Budgeted Add Capacity To Stabilize Matching. We create a reduced
instance $\langle\mathcal{I}^{\prime}=\langle
P_{orig},Q,\succ\rangle,P_{add},\ell^{\prime},\mu^{\prime}\rangle$ of Exact-
Exists-Add-Men as follows:

We set $\mathcal{I}^{\prime}$ to be the canonical one-to-one reduction of
$\mathcal{I}$. We set $P_{add}$ to have men corresponding to the copies of
firms from indices $c_{f}+1$ to $|\mu^{*}(f)|$. Formally,
$P_{orig}=\\{p^{f}_{i}:\forall f\in F,0\leq i\leq c_{f}\\}$ and
$P_{add}=\\{p^{f}_{i}:\forall f\in F,c_{f}<i\leq|\mu^{*}(f)|\\}$. Note that if
$|\mu^{*}(f)|\leq c_{f}$ for some firm $f$, then no men corresponding to that
firm will be in $P_{add}$. The preferences over the corresponding agents are
same as those in the original instance. Also we set $\ell^{\prime}=\ell$.

Now we convert the matching $\mu^{*}$ to its one-to-one version
$\mu^{\prime}$. For each $f\in F$, let $\mu^{*}(f)_{i}$ be the $i^{th}$ most
preferred worker in $\mu^{*}(f)$ according to $f$. Then we match the copies
$p^{f}_{i}$ of the firm to these workers in the order of preferences, i.e.,
set $\mu^{\prime}(p^{f}_{i})=\mu^{*}(f)_{i}$ for all $i\in[|\mu^{*}(f)|]$.
Rest of the copies remain unmatched. This is done because a lower index copy
of a firm is more preferred in every woman’s preference list. If we don’t make
such a matching, there would be blocking pairs between the firm copies in
$\mu^{\prime}$.

Now we prove the correctness of this reduction.

First assume that the given instance of Budgeted Add Capacity To Stabilize
Matching is solved by a capacity vector $\overline{C}$ such that $\langle
F,W,\overline{C},\succ\rangle$ admits a stable matching $\mu$ which is a
subset of $\mu^{*}$. Then we can see that adding men corresponding to
$\overline{C}$ in the reduced instance will create the canonical one-to-one
instance of $\langle F,W,\overline{C},\succ\rangle$. This instance admits the
one-to-one extension of $\mu$, which solves the reduced instance because this
matching is a subset of $\mu^{\prime}$, as is evident from the construction of
$\mu^{\prime}$.

Now assume that the reduced instance of Exact-Exists-Add-Men is solved by a
set $\overline{P}\subseteq P_{add}$ such that $\langle
P_{orig}\cup\overline{P},Q,\succ\rangle$ admits a stable matching $\mu$ which
is a subset of $\mu^{\prime}$. Then we can see that creating a capacity vector
$\overline{C}$ corresponding to $P_{orig}\cup\overline{P}$ will satisfy the
budget requirements and also solve the original instance of Budgeted Add
Capacity To Stabilize Matching because the many-to-one compression of $\mu$
will be a subset of $\mu^{*}$.

This completes the proof of reduction. Since Exact-Exists-Add-Men can be
solved in polynomial time by Lemma 9, we conclude that Budgeted Add Capacity
To Stabilize Matching can be solved in polynomial time too. ∎

###  C.6 Adding Capacity To Stabilize A Matching: Unbudgeted

The unbudgeted version is just a special case of the budgeted version and can
be solved by setting the individual budgets equal to the global budget.

Add Capacity To Stabilize Matching
---
Given: |  An instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, a global budget $\ell\in\mathbb{N}\cup\\{0\\}$, a matching $\mu^{*}$ with $|\mu^{*}(f)|\leq c_{f}+\ell$ for each $f\in F$. Preferences $\succ$ are complete.
Question: |  Does there exist a capacity vector $\overline{C}\in(\mathbb{N}\cup\\{0\\})^{n}$ such that $\overline{C}\geq C,|\overline{C}-C|_{1}\leq\ell$ and there is a matching $\mu$ stable for $\mathcal{I}^{\prime}=\langle W,F,\overline{C},\succ\rangle$ which is a subset of $\mu^{*}$, i.e., $\mu(f)\subseteq\mu^{*}(f)$ for each $f$ and $\mu(w)=\mu^{*}(w)$ or $\emptyset$ for each $w$ ?

######  Theorem 7.

Add Capacity To Stabilize Matching can be solved in polynomial time.

###### .

Since Budgeted Add Capacity To Stabilize Matching is solvable in polynomial
time by Theorem 6, an equivalent Budgeted Add Capacity To Stabilize Matching
instance with individual budgets set equal to the global budget can be used to
solve the given instance of Add Capacity To Stabilize Matching in polynomial
time. ∎

###  C.7 Deleting Capacity To Stabilize A Matching: Budgeted

In this problem, our goal is to delete seats from firms in order to make a
subset of the given matching stable.

Budgeted Delete Capacity To Stabilize Matching
---
Given: |  An instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, a global budget $\ell\in\mathbb{N}\cup\\{0\\}$, individual budget $\ell_{f}\in\mathbb{N}\cup\\{0\\}$ for each firm $f\in F$, and a matching $\mu^{*}$ with $|\mu^{*}(f)|\leq c_{f}$.
Question: |  Does there exist a capacity vector $\overline{C}\in(\mathbb{N}\cup\\{0\\})^{n}$ such that $\overline{C}\leq C,|\overline{C}-C|_{1}\leq\ell$ and $|\overline{c}_{f}-c_{f}|\leq\ell_{f}$ and there is a matching $\mu$ stable for $\mathcal{I}^{\prime}=\langle F,W,\overline{C},\succ\rangle$ which is a subset of $\mu^{*}$, i.e., $\mu(f)\subseteq\mu^{*}(f)$ for each $f$ and $\mu(w)=\mu^{*}(w)$ or $\mu(w)=\emptyset$ for each $w$ ?

We prove that we can solve this problem in polynomial time by showing an
algorithm for it’s one-to-one reduction.

######  Theorem 8.

Budgeted Delete Capacity To Stabilize Matching can be solved in polynomial
time.

We first define a problem Exact-Exists-Delete-Men, which is an extension of
Budgeted Delete Capacity To Stabilize Matching to the canonical one-to-one
instance.

Exact-Exists-Delete-Men
---
Given: |  A canonical one-to-one reduction $\mathcal{I}=\langle P,Q,\succ\rangle$ of a many-to-one instance $\langle F,W,C,\succ\rangle$, a global budget $\ell$, individual budgets $\ell_{f}$ for all men corresponding to firm $f$, and a matching $\mu^{*}$ defined on $\mathcal{I}$.
Question: |  Does there exist a set of men $\overline{P}\subseteq P$ such that $|\overline{P}|\leq\ell$, $\overline{P}$ has at most $\ell_{f}$ men corresponding to each firm $f$ and the matching $\mu^{*}$ when restricted to $P\cup Q\setminus\overline{P}$ is stable. More formally, does there exist a stable matching $\mu$ in $\mathcal{I}\setminus\overline{P}$ such that for each $p\in P\setminus\overline{P}$, $\mu(p)=\mu^{*}(p)$ and for each woman $q\in Q$, $\mu(q)=\mu^{*}(q)$ if $\mu^{*}(q)\in P\setminus\overline{P}$ or otherwise $\mu(q)=\emptyset$?

We present the following algorithm for solving Exact-Exists-Delete-Men, which
keeps deleting all the men that form a blocking pair till $\mu^{*}$ becomes
stable. The idea is similar to the exponential-time algorithm for Exact-
Exists-Delete given at [Boehmer et al., 2021, Algorithm 2]. In our problem, we
can only delete men and this change makes the time complexity polynomial, as
we will later prove.

1

Input: A Exact-Exists-Delete-Men instance $\langle\mathcal{I}=\langle
P,Q,\succ\rangle,\ell,\\{\ell_{f}:f\in F\\},\mu^{*}\rangle$

Output: A set $\overline{P}$ of men which solves the given instance and a
stable matching $\mu\subseteq\mu^{*}$ of $\mathcal{I}\setminus\overline{P}$.

2 Initialise $\overline{P}\leftarrow\emptyset$.

3 Initialise $B\leftarrow$ the set of men involved in a blocking pair of
$\mu^{*}$ restricted to $\mathcal{I}$.

4

5while  _$B$ is not empty_ do

6

7 forall  _$p^{f}_{i}\in B$_ do

8 Update $\ell\leftarrow\ell-1$

9 Update $\ell_{f}\leftarrow\ell_{f}-1$

10 Update $\overline{P}\leftarrow\overline{P}\cup\\{p^{f}_{i}\\}$

11 Update $B\leftarrow$ the set of men involved in a blocking pair of
$\mu^{*}$ restricted to $\mathcal{I}\setminus\overline{P}$.

12

13if  _$\ell\geq 0$ and $\ell_{f}\geq 0$ for all $f$ in $F$_ then

14 Output $\overline{P}$ and the restriction of $\mu^{*}$ to
$\mathcal{I}\setminus\overline{P}$

15

16else

Output $\emptyset$ and $\emptyset$

/* Cannot stabilize $\mu^{*}$ within the budget. */

17

18

19

Algorithm 3 Exact-Exists-Delete-Men algorithm

To prove the correctness of the algorithm, we need the following lemma:

######  Lemma 10.

Let $\mathcal{I}=\langle P,Q,\succ\rangle$ be a stable matching instance,
$P_{A}\subseteq P$ be a subset of men and $\mu^{*}$ be a matching in
$\mathcal{I}$. Suppose $(p,q)$ is a blocking pair for $\mu^{*}$ restricted to
$\mathcal{I}\setminus P_{A}$. Then, for any $P_{B}\subseteq
P\setminus\\{p\\}$, $(p,q)$ is still a blocking pair for $\mu^{*}$ restricted
to $\mathcal{I}\setminus(P_{A}\cup P_{B})$.

###### Proof.

Let $\mu$ be $\mu^{*}$ restricted to $\mathcal{I}\setminus P_{A}$. Since,
$(p,q)$ is a blocking pair for $\mu$, we get that $q\succ_{p}\mu(p)$ and
$p\succ_{q}\mu(q)$.

Let $\mu^{\prime}$ be $\mu^{*}$ restricted to $\mathcal{I}\setminus(P_{A}\cup
P_{B})$. Note that $P_{A}\cup P_{B}$ does not contain $p$, which means that
$p$ and $q$ are still in the instance. Clearly
$\mu^{\prime}\subseteq\mu\subseteq\mu^{*}$. Therefore,
$\mu^{\prime}(a)=\mu(a)$ or $\mu^{\prime}(a)=\emptyset$ for $a\in\\{p,q\\}$.
In both cases we get that $\mu(p)\succeq_{p}\mu^{\prime}(q)$ and
$\mu(q)\succeq_{q}\mu^{\prime}(q)$. Hence, we get that
$q\succ_{p}\mu^{\prime}(p)$ and $p\succ_{q}\mu^{\prime}(p)$. Consequently
$(p,q)$ is a blocking pair in $\mu^{\prime}$ and we are done. ∎

######  Lemma 11.

Exact-Exists-Delete-Men can be solved in polynomial time.

The case where the algorithm returns $\overline{P}$ is fairly straightforward
since the loop terminates when no blocking pair is remaining. Since we
explicitly check for budget satisfiability, the set returned is guaranteed to
be a valid solution. For the case with no solution, we show by induction that
the elements that are contained in set $\overline{P}$ computed by our
algorithm must also be present in any valid solution, and hence another set
cannot satisfy the budget constraints.

###### Proof.

We will show that Algorithm 3 solves any given instance
$\langle\mathcal{I}=\langle P,Q,\succ\rangle,\ell,\\{\ell_{f}:f\in
F\\},\mu^{*}\rangle$ in polynomial time. First we show the correctness of the
algorithm. Consider the set $\overline{P}$ computed by the algorithm.

We will show that whenever the algorithm terminates by returning the set
$\overline{P}$ and the stable matching, the given instance is solved by
$\overline{P}$. For every man we add to $\overline{P}$, we decrease the global
and individual budget by 1. Thus, at line 9 we check that $\overline{P}$ does
not exceed the global and individual budgets. Also $B$ is empty, hence, the
matching $\mu^{*}$ restricted to $\mathcal{I}\setminus\overline{P}$ is stable
and the given instance is solved by $\overline{P}$.

Now, we will show that whenever the algorithm terminates by returning the
empty matching, the given instance of Exact-Exists-Delete-Men has no solution.
The algorithm terminates with an empty matching when $\overline{P}$ exceeds
the global budget or the individual budgets. For the sake of contradiction,
assume that the given instance of Exact-Exists-Delete-Men is solved by a
subset of men $\overline{P}^{\prime}\subseteq P$ satisfying the global and
individual budgets such that $\mu^{*}$ is stable restricted to
$\mathcal{I}\setminus\overline{P}^{\prime}$. We will prove by induction that
$\overline{P}\subseteq\overline{P}^{\prime}$, which will contradict the fact
that $\overline{P}^{\prime}$ is within the budget. For the given instance, let
there be $t$ iterations of the while loop. Let $\overline{P}_{i}$ be the set
of men added to $\overline{P}$ during the $i$th iteration of the while loop.

We claim that $\overline{P}_{i}\subseteq\overline{P}^{\prime}$ for all
$i\in[t]$. The base case consists of showing
$\overline{P}_{1}\subseteq\overline{P}^{\prime}$. For the sake of
contradiction, assume that there is a man $p$ in $\overline{P}_{1}$ but not in
$\overline{P}^{\prime}$. Let $(p,q)$ be the blocking pair formed by $p$ for
$\mu^{*}$ restricted to $\mathcal{I}$. Using Lemma 10 on $\mathcal{I}$ with
$P_{A}=\emptyset$ and $P_{B}=\overline{P}^{\prime}$, we conclude that $(p,q)$
is still a blocking pair for $\mu^{*}$ restricted to
$\mathcal{I}\setminus\overline{P}^{\prime}$, which is a contradiction. Hence,
our assumption is wrong and no such man can exist. Hence,
$\overline{P}_{1}\subseteq\overline{P}^{\prime}$.

For the inductive step, assume that
$\overline{P}_{i}\subseteq\overline{P}^{\prime}$ for all $i\in[k]$ for some
$1\leq k<t$. By definition, $\overline{P}_{k+1}$ is the set of men involved in
a blocking pair of $\mu^{*}$ restricted to
$\mathcal{I}\setminus(\overline{P}_{1}\cup\dots\cup\overline{P}_{k})$. For the
sake of contradiction, assume that there is a man $p$ in $\overline{P}_{k+1}$
but not in $\overline{P}^{\prime}$. Let $(p,q)$ be the blocking pair formed by
$p$ for $\mu^{*}$ restricted to
$\mathcal{I}\setminus(\overline{P}_{1}\cup\dots\cup\overline{P}_{k})$. Using
Lemma 10 on $\mathcal{I}$ with
$P_{A}=(\overline{P}_{1}\cup\dots\cup\overline{P}_{k})$ and
$P_{B}=\overline{P}^{\prime}$, we obtain that $(p,q)$ is still a blocking pair
for $\mu^{*}$ restricted to
$\mathcal{I}\setminus(\overline{P}_{1}\cup\dots\cup\overline{P}_{k}\cup\overline{P}^{\prime})=\mathcal{I}\setminus\overline{P}^{\prime}$,
which is a contradiction. Hence, our assumption is wrong and no such man can
exist. Hence, $\overline{P}_{k+1}\subseteq\overline{P}^{\prime}$.

Hence, by induction, we prove that
$\overline{P}_{i}\subseteq\overline{P}^{\prime}$ for all $i\in[t]$, which
implies $\overline{P}\subseteq\overline{P}^{\prime}$. Since $\overline{P}$
exceeds the global budget or the individual budgets, so should
$\overline{P}^{\prime}$. This is a contradiction to the fact that
$\overline{P}^{\prime}$ solves the given instance, and we conclude that the
given instance of Exact-Exists-Delete-Men has no solution.

This completes the proof of correctness of Algorithm 3.

Observe that $B\cap\overline{P}$ is always $\emptyset$. This is because $B$
contains agents from $P\cup Q\setminus\overline{P}$. Hence, in each iteration
of the while loop we add at least one man to $\overline{P}$ and the while loop
terminates in at most $|P|$ iterations. The inner for loop terminates in
$|B|\leq|P|$ iterations and blocking pairs can be computed in linear time.
Hence, the algorithm terminates in polynomial time. This proves that Exact-
Exists-Delete-Men can be solved in polynomial time. ∎

Now we show that Budgeted Delete Capacity To Stabilize Matching can be solved
in polynomial time by giving a reduction to Exact-Exists-Delete-Men.

###### .

(of Theorem 8) We show a reduction from Budgeted Delete Capacity To Stabilize
Matching to Exact-Exists-Delete-Men. Let the given instance of Budgeted Delete
Capacity To Stabilize Matching be $\langle\mathcal{I}=\langle
F,W,C,\succ\rangle,\ell,\\{\ell_{f},f\in F\\},\mu^{*}\rangle$. We define an
instance $\langle\mathcal{I}^{\prime}=\langle
P,Q,\succ^{\prime}\rangle,\ell^{\prime},\\{\ell^{\prime}_{f}:f\in
F\\},\mu^{\prime}\rangle$ of Exact-Exists-Delete-Men as follows: Let
$\mathcal{I}^{\prime}$ be the canonical one-to-one reduction of $\mathcal{I}$.
We define $\mu^{\prime}$ to be the one-to-one extension of $\mu^{*}$ to the
one-to-one instance $\mathcal{I}^{\prime}$.

If we are able to solve the reduced instance by deleting a set of men
$\overline{P}$, then we can also stabilize $\mu^{*}$ in $\mathcal{I}$ by
deleting the corresponding capacities of firms.
$\mathcal{I}^{\prime}\overline{P}$ will be the canonical one-to-one reduction
of the instance we get after deleting the said capacities. Similarly, if we
can solve the original instance by deleting some capacities of firms, we can
solve the modified instance by deleting the corresponding men. Hence, Budgeted
Delete Capacity To Stabilize Matching reduces to Exact-Exists-Delete-Men.
Since Exact-Exists-Delete-Men can be solved in polynomial time by Lemma 11, we
conclude that Budgeted Delete Capacity To Stabilize Matching is solvable in
polynomial time too. ∎

###  C.8 Deleting Capacity To Stabilize A Matching: Unbudgeted

The unbudgeted version is just a special case of the budgeted version and can
be solved by setting the individual budgets equal to the global budget.

Delete Capacity To Stabilize Matching
---
Given: |  An instance $\mathcal{I}=\langle F,W,C,\succ\rangle$, a global budget $\ell\in\mathbb{N}\cup\\{0\\}$, and a matching $\mu^{*}$ with $|\mu^{*}(f)|\leq c_{f}$.
Question: |  Does there exist a capacity vector $\overline{C}\in(\mathbb{N}\cup\\{0\\})^{n}$ such that $\overline{C}\leq C,|\overline{C}-C|_{1}\leq\ell$ and there is a matching $\mu$ stable for $\mathcal{I}^{\prime}=\langle F,W,\overline{C},\succ\rangle$ which is a subset of $\mu^{*}$, i.e., $\mu(f)\subseteq\mu^{*}(f)$ for each $f$ and $\mu(w)=\mu^{*}(w)$ or $\mu(w)=\emptyset$ for each $w$ ?

######  Theorem 9.

Delete Capacity To Stabilize Matching can be solved in polynomial time.

###### Proof.

Since Budgeted Delete Capacity To Stabilize Matching can be solved in
polynomial time by Theorem 8, an equivalent Budgeted Delete Capacity To
Stabilize Matching instance with individual budgets equal to the global budget
can be used to solve the given instance of Delete Capacity To Stabilize
Matching in polynomial time. ∎

##  Appendix D Omitted Material from Section 5

We now present all the missing examples and proofs from Section 3. In our
comparisons, we first present examples from the lexicographic domain, which
clearly extend to the general responsive preferences domain. We shall then
present the key differences for strongly monotone preferences.

###  D.1 Delete vs Pref

We first compare the two manipulation action under the WPDA. We find that
below peak, both Delete and Pref can be beneficial, but only Delete is
beneficial at and above peak under the WPDA.

#### Comparison under WPDA

##### Below peak

In Section 5, we gave an example where for a firm with capacity below peak,
preference manipulation beats any capacity manipulation. We now show an
example where Delete is the best manipulation available to a firm with
capacity below peak under the WPDA.

######  Example 6.

Consider the following example with three firms $f_{1}$, $f_{2}$ and $f_{3}$
and four workers $w_{1},\cdots,w_{4}$. The firms have lexicographic
preferences with capacities being $c_{1}=2$ and $c_{2}=c_{3}=1$. The
preference relations are as follows:

$\textstyle w_{1}$ $\textstyle:f_{3}\succ f_{2}\succ f_{1}\succ\emptyset$
$\textstyle w_{2}$ $\textstyle:f_{1}\succ f_{2}\succ f_{3}\succ\emptyset$
$\textstyle w_{3},\,w_{4}$ $\textstyle:f_{1}\succ f_{3}\succ
f_{2}\succ\emptyset$ $\textstyle f_{1}$ $\textstyle:w_{1}\succ w_{2}\succ
w_{3}\succ w_{4}$ $\textstyle f_{2}$ $\textstyle:w_{2}\succ w_{4}\succ
w_{1}\succ w_{3}$ $\textstyle f_{3}$ $\textstyle:w_{3}\succ w_{4}\succ
w_{1}\succ w_{2}$

The worker optimal stable matching here is

$\mu_{1}=\\{(w_{2},f_{1}),(w_{3},f_{1}),(w_{1},f_{2}),(w_{4},f_{3})\\}$

In this case, however $f_{1}$ reports its preferences, with a capacity of two,
it will always be matched to one of the following sets $\\{w_{2},w_{3}\\}$,
$\\{w_{2},w_{4}\\}$ or $\\{w_{3},w_{4}\\}$. However, if $f_{1}$ were to report
its capacity as one, the WPDA would result in the following matching:

$\mu_{2}=\\{(w_{1},f_{1}),(w_{2},f_{2}),(w_{3},f_{3})\\}$

Clearly, $f_{1}$ prefers $\mu_{2}$ to $\mu_{1}$ and any matching resulting
from misreporting its preference. ∎

##### At peak

As we have discussed in Section 5, when a firm’s capacity is at peak, it
cannot permute its preferences and change its matched set under the WPDA. For
the example for Delete outperforming Pref at peak, please see the instance
given in the proof of Theorem 1 in Sönmez [1997].

##### Above peak

The example in Sönmez [1997] also shows that Delete can be more useful than
Pref if a firm’s capacity is above peak. For the converse, we now prove Lemma
1 and show how it leads to the proof that preference manipulation is unhelpful
above peak.

Recall that for any $b\in\mathbb{N}$, $\mathcal{I}^{b}$ denotes the instance
where the capacity of firm $f$ is changed to $b$. We first show that if the
capacity of a firm $f$ is above peak in the original instance $\mathcal{I}$
(i.e., $c_{f}>p_{f}$), then the set of workers matched to it under any stable
matching in the instance $\mathcal{I}^{b}$, where $b>p_{f}$, is the same as
its matched set under the worker-optimal stable matching for the instance
$\mathcal{I}^{p_{f}}$ (i.e., when the firm’s capacity is equal to the peak).
This observation helps us prove that preference manipulation is unhelpful
above peak.

See 1

###### Proof.

Consider an instance $\mathcal{I}=\langle F,W,C,\succ\rangle$ and a firm $f\in
F$ with $c_{f}>p_{f}$. Let $\mu^{*}_{c_{f}}$ be the worker optimal stable
matching and $\mu$ be an arbitrary stable matching for $\mathcal{I}$.

As $c_{f}>p_{f}$, by definition of peak,
$|\mu(f)|=|\mu^{*}_{c_{f}}(f)|<c_{f}$. Thus, $f$ is unsaturated and by rural
hospitals theorem we have that $\mu(f)=\mu^{*}_{c_{f}}(f)$.

Now consider $\mathcal{I}_{f}^{p_{f}}$. Recall that $\mu^{*}$ is the worker
optimal stable matching under $\mathcal{I}_{f}^{p_{f}}$. We have that
$|\mu^{*}(f)|=p_{f}$. Let $W_{f}$ be the set of workers acceptable to $f$ who
propose to $f$ in the WPDA on $\mathcal{I}_{f}^{p_{f}}$. We shall now show
that if the size of this set $|W_{f}|>p_{f}$ then $f$ would be matched to
$p_{f}+1$ workers under the matching computed by the WPDA on
$\mathcal{I}_{f}^{p_{f}}+1$ which is a contradiction.

Let $|W_{f}|>p_{f}$. Thus all the workers in $W_{f}\setminus\mu^{*}(f)$ must
have been rejected by $f$ when $f$ was saturated by workers $f$ prefers more.
Consider the very first of these workers, say $w$, to be rejected by $f$.
During the WPDA under $\mathcal{I}_{f}^{p_{f}}+1$, $f$ must not be saturated
and will accept $w$. Henceforth, during the WPDA the size of $f$’s matched set
will not decrease. Consequently, $f$ would be matched to $p_{f}+1$ workers in
a stable matching, which is a contradiction.

Thus, all agents that proposed to $f$ in the WPDA on
$\mathcal{I}_{f}^{p_{f}}$, $W_{f}$, must have been accepted. Now for any
$b>p_{f}$, all agents in $W_{f}$ will propose to $f$ during the WPDA on
$\mathcal{I}_{f}^{b}$ and be matched to $f$.

We can analogously argue that all agents who propose to $f$ under the WPDA on
$\mathcal{I}_{f}^{b}$ for any $b>p_{f}$ must have proposed to $f$ under