Optimal Capacity Modification for Stable Matchings with Ties

1 Introduction

The Hospitals/Residents (HR) problem [Gusfield and Irving, 1989; Roth and Sotomayor, 1990] is a many-to-one generalization of the classical stable marriage problem [Gale and Shapley, 1962]. As the name suggests, the HR problem models the assignment of junior doctors (residents) to hospitals where agents in both sets are allowed to rank acceptable agents from the other set in a preference order. The problem is extensively investigated since it has applications in a number of centralized matching schemes in many countries, including the National Resident Matching Program in the USA (NRMP), the Canadian Resident Matching Service (CaRMS), and the Scottish Foundation Allocation Scheme

(SFAS), to name a few. In addition, the HR problem models several real-world applications like assigning children to schools [Abdulkadiro˘glu et al., 2005] and students to undergraduate programs [Baswana et al., 2019].When agents' preferences form a total order, the preferences are said to be strict, whereas when agents are allowed to be indifferent among a subset of agents, the preferences are said to contain ties. This is known as the Hospitals/Residents problem with ties (HRT).

Ties in preference lists play an important role in real-world matching applications. For instance, hospitals with a large number of applicants often find it difficult to generate strict preference lists and have expressed the desire to include ties in their preference lists [Irving et al., 2000]. In the case of college admissions, it is natural for colleges to have all the students with equal scores in a single tie in their preference lists. On the other hand, it is natural to require students to express strict preferences over colleges. We refer to this setting as HR-HT - Hospitals/Residents problem with ties on hospitals' side only.

In the presence of ties, stability has been defined in the literature in three different ways -weak stability, strong stability and super stability (see Definition 1 and the footnote therein). As indicated by the names, super stability is the strongest notion and weak stability is the weakest among the three. It is well-known that every instance of the HRT problem admits a weakly stable matching and it can be obtained by breaking ties arbitrarily and computing a stable matching in the resulting strict-list instance.

In the HR-HT setting considered throughout this paper, the notions of strong and super stability coincide; however, neither of them is guaranteed to exist [Irving, 1994]. Weak stability, although guaranteed, is too weak, and as justified in [Manlove, 2002], is susceptible to compromise through persuasion or bribery (also see [Irving et al., 2003; Kunysz et al., 2016] for further details). Moreover, from a social perspective, weak stability may not be an acceptable notion despite its guaranteed existence. For instance, according to the equal treatment policy used in Chile and Hungary, it is not acceptable that a student is rejected from a college preferred by her, even though other students with the same score are admitted [Cseh and Heeger, 2020]. Thus, strong stability is not only appealing but also essential.

Given that strong stability is desirable but not guaranteed to exist, a natural option is to increase or augment the quotas

(of, say, colleges or hospitals) so that a strongly stable matching exists after the augmentation. We address this problem in this paper. We use the hospital-residents terminology, as is customary in many-to-one stable matchings. We note that unlike the stable matching problem (with strict lists), which is monotonic with respect to capacity increase, the strongly stable matching problem with ties is not monotonic with respect to capacity augmentation. That is, an instance that admits a strongly stable matching may stop admitting one after the capacities of certain hospitals are increased. This nonmonotonicity makes the problem challenging.

We explore two natural optimization criteria: (i) minimize the total increase (sum) in quotas across all hospitals (MINSUM), and (ii) minimize the maximum increase in quota for any hospital (MINMAX). To the best of our knowledge, our work is the first to explore capacity augmentation for the notion of strong stability, although capacity modification has received considerable attention in the strict list setting (see Section 1.3).

1.1 Preliminaries and Notations

The input to our problem is a bipartite graph G = (R∪H, E), where the vertex set R represents the set of residents, H represents the set of hospitals and the edge set E represents mutually acceptable resident-hospital pairs. Every hospital h ∈ H has an associated quota q(h) denoting the maximum number of residents that can be assigned to h in any assignment. Each vertex v ∈ R∪H ranks its neighbors as per its preference ordering, referred to as the preference list of v, denoted as Pref(v). A vertex strictly prefers a neighbor with a smaller rank over another neighbor with a larger rank. If a vertex is allowed to be indifferent between some of its neighbors and is allowed to assign the same rank to such neighbors, it is referred to as a tie. The length of a tie is the number of neighbors having equal rank. If ties are not allowed (or equivalently, all ties have length 1), the preference lists are said to be strict. We use u1 ≻v u2 to denote that v strictly prefers u1 over u2 and u1 ⪰v u2 to denote that v either strictly prefers u1 over u2 or is indifferent between them.

A matching M in G is a subset of E such that for each resident r ∈ R we have |M(r)| ≤ 1 and for each hospital h ∈ H we have |M(h)| ≤ q(h) where M(v) denotes the set of matched partners of v in M. For a resident r, if |M(r)| = 0, then r is unmatched in M. In this case, we denote the matched partner of r by M(r) = ⊥. A hospital h ∈ H is said to be fully subscribed in M with respect to its quota q(h), if |M(h)| = q(h), under-subscribed in M if |M(h)| < q(h). We abuse the term matching and say that h is over-subscribed in M if |M(h)| > q(h). If left unspecified, the quota under consideration for these terms is the original quota q(h). If h is under-subscribed, then we implicitly match the remaining q(h) - |M(h)| many positions of h to as many copies of ⊥. A vertex prefers any of its neighbors over ⊥.

Definition 1 (Strong Stability:). For a matching M in an instance of HRT setting, an edge (r, h) ∈ E \ M is a strong blocking pair w.r.t. M, if either (i) or (ii) holds:

(i) h ≻r M(r) and ∃ r′ ∈ M(h) such that r ⪰h r′

(ii) h ⪰r M(r) and ∃ r′ ∈ M(h) such that r ≻h r′ .

A matching M is strongly stable matching if there does not exist any strong blocking pair w.r.t. M. 1

Throughout the paper, we refer to a strong blocking pair as a blocking pair. There exist simple instances of HR-HT which do not admit a strongly stable matching. Any such instance can be augmented so as to admit a strongly stable matching by setting the quota of each hospital h equal to its degree in G. In the augmented instance G′ , the matching M ′ that assigns each resident to its rank-1 hospital, is a strongly stable matching. Such an augmentation is clearly wasteful, and hence our objective in this paper is to optimally increase hospitals' quotas to ensure that a strongly stable matching exists in the modified instance.

1.2 Our Problems and Contributions

For all our problems, unless stated explicitly, we assume that the given HR-HT instance G = (R∪H, E) does not admit a strongly stable matching. Deciding whether an HRT instance admits a strongly stable matching can be done in polynomial time using the algorithm by Irving et al. [2003]. Throughout this paper, the augmented instance G′ is the same as G except that for each h, we have q′ (h) ≥ q(h). Our first objective is to minimize the total increase in quotas across all hospitals, defined as the MINSUM-SS problem.

MINSUM-SS: Given an HR-HT instance G = (R ∪ H, E), construct an augmented instance G′ such that G′ admits a strongly stable matching and the sum of the increase in quotas over all hospitals (that is, ∑h∈H(q′ (h)-q(h))) is minimized.

Theorem 1. MINSUM-SS is solvable in polynomial time.

In Theorem 6 and Corollary 1, we provide an analog of the well-known Rural Hospitals theorem [Gale and Sotomayor, 1985; Roth, 1986] for the MINSUM-SS problem. We prove that strongly stable matchings across all optimal augmented instances match the same set of residents. Moreover, we show that the under-subscribed hospitals in the strongly stable matching produced by our algorithm match the same number of residents in each strongly stable matching across all optimal augmented instances.

Given the polynomial-time solution for the MINSUM-SS problem, we consider the optimal total quota augmentation (if possible) for matching a subset Q ⊆ E in G. We denote this problem as MINSUM-SS-FE (forced edges) and define it formally below.

The MINSUM-SS-FE problem arises in course allocation settings where final-year students in a university need to finish a certain course to complete graduation requirements. Such student course pairs are readily captured as forced edges.

MINSUM-SS-FE: Given an HR-HT instance G = (R ∪ H, E), which possibly admits a strongly stable matching, and a subset Q ⊆ E, construct an augmented instance G′ , if possible, such that G′ admits a strongly stable matching that contains Q, and the sum of the increase in quotas over all hospitals (that is, ∑h∈H(q′ (h) - q(h))) is minimized.

1 A pair (r, h) is a super blocking pair if both prefer each other strictly or equally to their matched partners. Also, (r, h) form a weak blocking pair if they prefer each other strictly more than their matched partners.

Theorem 2. The MINSUM-SS-FE problem is solvable in polynomial time.

Next, we consider a generalization of the MINSUM-SS problem, where increasing the quota of a hospital incurs a cost for each unit increase in the quota. This problem is denoted by MINSUM-COST.

MINSUM-COST: Given an HR-HT instance G = (R ∪ H,E), where each hospital h ∈ H has an associated cost c(h) for unit increase in its quota, the goal is to construct an augmented instance G′ such that G′ admits a strongly stable matching, and the total cost of the increasing quotas across all hospitals is minimized.

In contrast to the polynomial-time solvability for MINSUM-SS, we establish a hardness result for the MINSUM-COST problem.

Theorem 3. The MINSUM-COST problem is NP-hard and is inapproximable to within any multiplicative factor.

We now turn our attention to the alternative objective: minimizing the maximum increase in quota for any hospital and define MINMAX-SS problem.

MINMAX-SS: Given an HR-HT instance G = (R ∪ H, E), construct an augmented instance G′ such that G′ admits a strongly stable matching, and the maximum increase in the quota for any hospital is minimized, that is, maxh∈H{q′ (h)- q(h)} is minimized.

Theorem 4. MINMAX-SS problem is NP-hard. Moreover, the same minimization objective with the goal of constructing an instance that admits a resident-perfect strongly stable matching (one that matches all residents) is also NP-hard.

Finally, we consider a variant of the MINMAX problem where hospitals' preference lists have bounded tie lengths.

MINMAX-SS-BT: Given an HR-HT instance G = (R ∪ H,E), where the length of ties in the preference lists of hospitals is bounded by ℓ + 1, determine the existence of an augmented instance G′ such that G′ admits a strongly stable matching, and maxh∈H{q′ (h) - q(h)} ≤ ℓ. We use ℓ-augmented instance to denote an augmented instance that admits a strongly stable matching and is obtained from G by at most ℓ augmentations per hospital. An ℓ-augmented instance G′ is resident-optimal ℓ-augmented instance of G if the resident-optimal 2 strongly stable matching in G′ is the best for residents across all ℓ-augmented instances of G.

Theorem 5. For an instance of MINMAX-SS-BT problem, with the tie length at most ℓ+1, an ℓ-augmented instance exists. Moreover, a resident-optimal ℓ-augmented instance can be computed in polynomial time. Therefore, a strongly stable matching which matches the maximum number of residents across all ℓ-augmented instances can be computed efficiently.

1.3 RelatedWork

Capacity Modification. Chen and Cs´aji [2023] studied a problem similar to ours for the case of strict preference lists.

2 A strongly stable matching M is resident-optimal if for each resident r ∈ R, M(r) is the best possible hospital to which r can get matched in any strongly stable matching.

The goal was to augment the instance by increasing hospital quotas such that the resulting instance admits a resident perfect (R-perfect) stable matching. They showed that with the MINMAX objective, the problem admits a polynomial-time algorithm. In contrast, somewhat surprisingly, for strongly stable matching, we get an NP-hardness result (see Theorem 4) for MINMAX. They also consider the MINSUM objective, and show NP-hardness for obtaining an augmented instance that admits a stable and R-perfect matching. Note that this also implies NP-hardness for constructing an augmented instance in the HR-HT setting for achieving a strongly stable and R-perfect matching under the MINSUM objective. However, without the R-perfectness requirement, our result in Theorem 1 gives a polynomial-time algorithm.

Capacity modification to achieve specific objectives has attracted significant interest in recent years. Bobbio et al. [2022] explored the complexity of determining the optimal variation (augmentation or reduction) of hospital quotas to achieve the best outcomes for residents, subject to stability and capacity variation constraints, and showed NP-hardness results. In a follow-up work, Bobbio et al. [2023] developed a mixed integer linear program to address this issue, and provided a comprehensive set of tools for obtaining near-optimal solutions. Gokhale et al. [2024] considered the problem of modifying hospitals' quotas to achieve two objectives - (i) to obtain a stable matching so as to match a given pair, and, (ii) to stabilize a given matching, either by only augmenting or only reducing hospital quotas. Afacan et al. [2024] examined capacity design in the HR setting, to achieve a stable matching that is not Pareto-dominated by any other stable matching.

Kavitha and Nasre [2011] and Kavitha et al. [2014] addressed the capacity augmentation problem for popular matchings in the one-sided preference list setting (where every hospital is indifferent between its neighbours). It is known that a popular matching is not guaranteed to exist in this setting. Therefore, their objective was to optimally increase hospital quotas to create an instance that admits a popular matching. Although we focus on a different setting (two-sided preference lists) and a different optimality notion - strong stability, it is interesting to note that our results closely resemble those obtained by Kavitha and Nasre [2011] and Kavitha et al. [2014].

Strong Stability. The notion of strong stability was first studied in the one-to-one setting (i.e. q(h) = 1 for all h ∈ H) for balanced, complete bipartite graphs by Irving [1994], where he gave an O(n4 ) algorithm to compute a strongly stable matching if it exists. Since then, the strongly stable matching problem has received a significant attention in the literature. Manlove [1999] extended the results in [Irving, 1994] to the general one-to-one setting (i.e. incomplete bipartite graphs) and also showed that all strongly stable matchings have the same size and match the same set of vertices. Irving et al. [2003] further extended these results to theHRT setting and gave O(m2 ) algorithm for the strongly stable matching problem, which was later improved to O(mn) by Kavitha et al. [2007]. Manlove [2002] studied the structure of the set of strongly stable matchings and showed that, similar to the classical stable matchings, the set of strongly stable matchings forms a distributive lattice. Kunysz et al. [2016] showed that there exists a partial order with O(m) elements representing all strongly stable matchings and also provided an O(mn) algorithm to construct such a representation. In the presence of edge weights, Kunysz [2018] showed that when edge weights are small, the maximum weight strongly stable matching problem can be solved in O(mn) time, and in O(mn log(Wn)) if the maximum weight of an edge is W. Strong stability w.r.t. restricted edges viz. forced, forbidden and free edges has been studied by Cseh and Heeger [2020] and by Boehmer and Heeger [2023].

Organization of the Paper. In Sections 2 and 3, the objective of our problems is to minimize the total increase in quotas. In Section 4, our objective is to minimize the maximum increase in quotas. Proofs of lemmas/ theorems marked with ⋆ are deferred to the full version [Ranjan et al., 2024].

2 MINSUM-SS Problem

In this section, we present an efficient algorithm for the MINSUM-SS problem. Since the input instance does not admit a strongly stable matching we need to increase the quotas of certain hospitals to obtain G′ . Our algorithm (pseudo-code given in Algorithm 1) involves a sequence of proposals from hospitals and is inspired by the hospital-oriented algorithm for super-stability [Irving et al., 2000].

The algorithm starts with every resident being unmatched or, equivalently, matching every resident to its least preferred hospital ⊥. Call this matching M ′ (see line 2 of Algorithm 1). During the course of the algorithm, let h be a hospital that is under-subscribed in M ′ , and t be the most preferred rank in Pref(h) at which h has not yet made a proposal. Then, h simultaneously proposes to all residents at rank t in Pref(h) (see Line 4). Since a hospital h proposes to all the residents at a particular rank simultaneously, it may lead to the over-subscription of that hospital. A fully subscribed or over-subscribed hospital does not propose further, and the sequence of proposals terminates when either no hospital is under-subscribed or all under-subscribed hospitals have exhausted proposing to all residents on their preference lists. When a resident r receives a proposal from h, the resident accepts or rejects the proposal based on the resident's preference between h and its current matched partner M ′ (r). Let M ′ represent the set of matched edges when the proposal sequence terminates. Since G does not admit a strongly stable matching, there must exist at least one hospital h that is oversubscribed in M ′ . Let G′ denote the instance with the modified quotas where the quota of each hospital h ∈ H is set to q′ (h) = max{q(h), |M ′ (h)|}. The algorithm returns the augmented instance G′ and the matching M ′ . Next, we prove the correctness and optimality of our algorithm.

Lemma 1. The matching M ′ returned by Algorithm 1 is a strongly stable matching in the augmented instance G′ .

Proof. By the way quotas of the hospitals are set in G′ , it is clear that M ′ is a valid matching in G′ . Suppose for contradiction, M ′ is not strongly stable in G′ . This implies that there exists a strong blocking pair, say (r, h) w.r.t. M ′ in G′ . Therefore, h ≻r M ′ (r) and there exists r′ ∈ M ′ (h) such that

Algorithm 1: Algorithm for MINSUM-SS

• 1 Input: An HR-HT instance G = (R∪H,E) 2 M ′ = {(r,⊥) | for every resident r ∈ R } 3 while ∃ h that is under-subscribed inM ′ w.r.t. q(h) and h has not exhausted Pref(h) do 4 h proposes to all residents at the most preferred rank t that h has not yet proposed 5 for every resident r that receives a proposal from h do 6 if h ≻r M ′ (h) then 7 M ′ = M ′ \ {(r,M ′ (r))} ∪ {(r, h)} 8 G′ is the same as G, except quotas are set as follows 9 For each h ∈ H, set q′ (h) = max{q(h), |M ′ (h)|} 10 return G′ andM ′

r ⪰h r′ . Since hospitals propose in order of their preference list, h must have proposed r during the course of Algorithm 1. The fact that h ̸= M ′ (r) implies that the resident r must have rejected h. Thus, at the time when r rejected h, the resident r must have been matched to a better-preferred hospital, say h′ . Since during the course of the algorithm residents improve their matched hospital, the final matched hospital M ′ (r) of r must be such that M ′ (r) ⪰r h′ ≻r h. This contradicts the fact that h ≻r M ′ (r) and completes the proof.

To prove the optimality of our capacity increase, we establish useful properties of any augmented instance ˜G (not necessarily optimal), obtained from G, such that ˜G admits a strongly stable matching. Let ˜ M be a strongly stable matching in ˜G. In Claim 1, we show that if a resident r is matched to h (not equal to ⊥) in M ′ output by Algorithm 1, then r is matched in ˜G and is matched to either h or a better-preferred hospital in ˜G.

Claim 1. Let r be matched to h ∈ H in M ′ at the end of Algorithm 1. Then the resident r is matched in ˜ M, and ˜ M(r) ⪰r h.

Proof. In the proposal sequence of Algorithm 1, if possible, consider the first proposal by any hospital h to any resident r such that h ≻r ˜ M(r). The existence of such a proposal refutes the claim since M ′ (r) ⪰r h.

Since h ≻r ˜ M(r), and ˜ M is strongly stable, h must be full in ˜ M with better preferred residents than r w.r.t. its capacity ˜ q(h). Since ˜ q(h) ≥ q(h), there must be at least q(h) many neighbors for h in ˜ M(h), which h strictly prefers to r. In Algorithm 1, h proposes to all the residents in ˜ M(h) before proposing r.

Since h proposes to r in Algorithm 1, at least one resident, say r1, in ˜ M(h) must have rejected the proposal of h before h proposed to r. Thus M ′ (r1) ≻r1 h = ˜ M(r1). This contradicts the assumption that h to r is the first proposal such that h ≻r ˜ M(r).

In the next claim, we show that any hospital that remains under-subscribed in M ′ w.r.t. q(h) continues to remain under-subscribed (to the same extent or more) in a strongly stable matching ˜ M of any augmented instance ˜G.

Claim 2. Let M ′ be the output of Algorithm 1 and h ∈ H be any hospital such that |M ′ (h)| < q(h). Also, assume that ˜G is an augmented instance obtained from G, and ˜ M is a strongly stable matching in ˜G. Then, |˜ M(h)| ≤ |M ′ (h)|.

Proof. Since |M ′ (h)| < q(h), the hospital h exhausted proposing all residents in Pref(h) during the execution of Algorithm 1. Clearly, all neighbors of h received proposals from h. If there exists any resident, say r, who rejected h during the execution of Algorithm 1, then r must have been matched in M ′ to M ′ (r) where M ′ (r) ≻r h. Using Claim 1, we conclude that ˜ M(r) ⪰r M ′ (r) ≻r h. Thus, no resident who rejected h during the execution of Algorithm 1 can be matched to h in ˜ M implying that |˜ M(h)| ≤ |M ′ (h)|.

Lemma 2. The total quota increase by Algorithm 1 is optimal.

Proof. Let Rm ⊆ R be the set of residents who received some proposal during the execution of Algorithm 1 and hence residents in Rm are matched in M ′ . By Claim 1, every r ∈ Rm must be matched in ˜ M. Let Hu be the set of hospitals such that |M ′ (h)| < q(h), and Hf = H \ Hu. Let the Rum denote the set of residents matched in M ′ to hospitals in Hu. By Claim 2, the quota utilization over all hospitals Hu in a strongly stable matching ˜ M of any instance ˜Gmust be at most |Rum|. This implies that at least |Rm \ Rum| many residents must be matched to hospitals in Hf in the matching ˜ M. Let k = |Rm\Rum|-∑h∈Hf q(h). Thus, the total quota increase in any instance ˜G is at least k. Algorithm 1 increases the quotas of hospitals in Hf only and matches the residents in Rm \ Rum to hospitals in Hf . Thus, the total quota increase of hospitals in G′ is exactly k which is optimal.

Lemma 1 and Lemma 2 together imply Theorem 1.

It is well known that when an HR-HT instance admits a strongly stable matching, all strongly stable matchings of the instance match the same set of residents [Irving et al., 2003]. In a similar spirit, we prove that all optimal solutions of a given MINSUM-SS instance match the same set of residents.

Theorem 6. Let G′ be the instance returned by Algorithm 1 and Rm denote the set of residents matched in the strongly stable matching M ′ . Then for any optimal augmentation Gopt, the set of residents matched in a strongly stable matching is exactly Rm.

Proof. Theorem1 asserts that the instanceG′ returned byAlgorithm 1 is an optimal augmented instance for G. Let Mopt be a strongly stable matching in Gopt. Applying Claim 1, we know that Mopt must match all residents in Rm. If Mopt matches any resident r /∈ Rm, then Mopt must match more than |Rm| many residents for the instance Gopt. Using Claim 2, we observe that any hospital h that is undersubscribed in M ′ w.r.t. q(h) is matched to at most |M ′ (h)| many residents in Mopt. Thus, the matching Mopt must match r to a hospital h such that |M ′ (h)| ≥ q(h). Therefore, the total increase in quotas by Gopt is more than that of G′ . This contradicts the optimality of Gopt.

Using Claim 2 and Theorem 6 we have the following.

Corollary 1. Let G′ be the instance returned by Algorithm 1. Also, assume that Gopt be any optimal augmentation and Mopt be a strongly stable matching in Gopt. Then, |M ′ (h)| ≥ q(h) for a hospital h implies that |Mopt(h)| ≥ q(h). Moreover, if |M ′ (h)| < q(h), then |Mopt(h)| = |M ′ (h)|.

Now, let us consider a variant of the MINSUM-SS problem where our goal is to determine the existence of an augmented instance which admits an R-perfect strongly stable matching. Let us denote this problem by MINSUM-SS-RP. Chen and Cs´aji [2023] studied a special case of this problem called MINSUM CAP STABLE AND PERFECT problem. Given an HR instance (strict list), say G, and a budget ℓ, the MINSUM CAP STABLE AND PERFECT problem asks whether it is possible to obtain an augmented instance G′ from G, only by increasing the quotas of some hospitals, such that G′ admits an R-perfect stable matching, and the sum of the increase in quotas over all hospitals is at most ℓ. They showed that this problem is NP-complete even for a very restricted case. Therefore, we conclude that MINSUM-SS-RP problem is NP-complete.

2.1 MINSUM-SS for Forced Edges

In this section, we consider the MINSUM-SS-FE problem. Here, in addition to an HR-HT instance G, we are given a subset Q ⊆ E. Our goal in this problem is to decide the existence of an augmented instance G′ that admits a strongly stable matching M ′ such that Q ⊆ M ′ . Note that such an augmented instance is not guaranteed to exist even when |Q| = 1. Consider an instance with one resident r and two hospitals h1, h2 where r prefers h1 over h2. Let Q = {(r, h2)}. There is no way to augment the quotas of hospitals to get a strongly stable matching which contains Q. We show that the MINSUM-SS-FE problem admits a polynomial-time algorithm. Whenever an augmentation is possible, we output the optimally augmented instance.

We present the overall idea here and defer the details to the full version [Ranjan et al., 2024]. Our algorithm begins by constructing a pruned graph through the deletion of certain edges. Specifically, we remove any edge that, if included in a matching along with the edges in Q, would result in a blocking pair. The pruned graph may or may not admit a strongly stable matching. Hence, we use Algorithm 1 (for MINSUM-SS) to obtain an augmented instance. While the augmented instance admits a strongly stable matching, the matching along with the forced edges Q may not be strongly stable. To finally decide whether an augmentation is possible, we crucially require the Rural Hospitals theorem analogue for the MINSUM-SS problem that we establish in Theorem 1.

3 MINSUM-COST Problem

In this section, we consider the MINSUM-COST problem and show that this problem is NP-hard even when the costs of the hospitals are 0 or 1. We prove our hardness by reducing from an instance of the MONOTONE 1-IN-3 SAT problem. The input for the MONOTONE 1-IN-3 SAT problem is a conjunction of clauses. Each clause is a disjunction of exactly three variables, and no variable appears in negated form. The goal is to determine whether there exists a truth assignment to the variables such that for each clause, exactly one variable is set to true. This problem is known to be NP-complete [Schaefer, 1978; Garey and Johnson, 1979] even when each variable occurs in at most 3 clauses [Denman and Foster, 2009].

Gadget Reduction. Let I be an instance of MONOTONE 1-IN-3 SAT problem, where each variable occurs in at most three clauses. Let {X1,X2, . . . ,Xβ} be the set of variables and {C1,C2, . . . ,Cα} be the set of clauses in I, for nonnegative integers α and β.

Given I, we construct an instance G = (R ∪ H,E) of MINSUM-COST problem with quota q(h) = 1 for each h ∈ H such that G does not admit a strongly stable matching. We also associate a cost c(h) ∈ {0, 1} with each h ∈ H. We show that there exists an augmented instance G′ = (R ∪ H, E) with a total augmentation cost 0 that admits a strongly stable matching if and only if there exists an assignment of variables in I such that exactly one variable in each clause is set to true.

Let Cs= (Xi∨Xj ∨Xk) be a clause in the instance I. Corresponding to the clause Cs, there exists a gadget Gs in our reduced instance G. The gadget Gs consists of the resident set Rs = {asi , asj , ask , bsi , bsj , bsk , ds1 , ds2 }, and the hospital set Hs = {vs i , vs j , vsk , ws }. The augmentation cost of each hospital in the gadget Gs is given as: c(vs i ) = c(vs j ) = c(vsk ) = 0 and c(ws ) = 1.

The preference lists of residents and hospitals in Gs are given in Figure 1. The preference list of a resident bsp corresponding to the variable Xp for p ∈ {i, j, k} consists of four hospitals - two within the gadget Gs, and two outside the gadget Gs. Assume that in I, the variable Xi appears in three clauses, namely Cs, Ci1 and Ci2 . Then the preference list of bsi consists of hospitals vs i , vi1 i , vi2 i and ws in this order. Analogously, the hospital vs i corresponding to Xi ranks the resident asi as its top choice, followed by a tie of length three consisting of the three b-residents, namely bsi , bi1 i , bi2 i , from three different gadgets. If Xi appears in t clauses where t < 3, then the preference list of bsi consists of t many vihospitals (as mentioned above) followed by ws . This completes the description of our reduction.

Correctness. We claim that the reduced instance G does not admit a strongly stable matching. Recall that the quota of each hospital is one. Any strongly stable matching M in the reduced instance G, must match asp to vs p for the gadget Gs, as otherwise, (asp , vs p ) blocks M. The matching M cannot leave ws unmatched, otherwise (dst ,ws ) for some t ∈ {1, 2} is a strong blocking pair. Since ws has a unit quota, it cannot be matched with any of the d-residents. For the same reason, ws cannot accommodate all of the three b-residents in the gadget Gs. This implies that there exists a b-resident, say bsj , which is not matched to ws in M. Thus, the pair (bsj ,ws ) blocks M. Hence, the reduced instance G does not admit a strongly stable matching.

asi : vs i asj : vs j ask : vsk bsi : vs i , vi1 i , vi2 i ,ws bsj : vs j , vj1 j , vj2 j ,ws bsk : vsk , vk1 k , vk2 k ,ws ds1 : ws ds2 : ws (i) vs i : asi , (bsi , bi1 i , bi2 i ) vs j : asj , (bsj , bj1 j , bj2 j ) vsk : ask , (bsk , bk2 k , bk2 k ) ws : (bsi , bsj , bsk ), (ds1 , ds2 ) (ii)

Recall that I is an instance of MONOTONE 1-IN-3 SAT. A satisfying assignment for an instance of MONOTONE 1IN-3 SAT is an assignment of variables such that for each clause, exactly one variable is set to true.

Lemma 3 (⋆). If I admits a satisfying assignment, then there exists an instance G′ obtained from G with an augmentation cost 0 such that G′ admits a strongly stable matching.

Proof sketch. We construct G′ and M ′ as follows. Wlog, assume that for the clause Cs= (Xi ∨ Xj ∨ Xk), the variable Xk is set to true by the satisfying assignment. We set the quota q′ (h) = 2 for each h ∈ {vs i , vs j } and q′ (h) = 1 for h ∈ {ws , vsk }. Clearly, the total augmenting cost is 0. Let M ′ = ⋃αs=1 {(asi , vs i ), (bsi , vs i ), (asj , vs j ), (bsj , vs j ), (ask , vsk ), (bsk , ws )}. To show the strong stability of M ′ , we prove that for any s, no resident in the gadget Gs participates in a strong blocking pair w.r.t. M.

Lemma 4 (⋆). If there exists an instance G′ obtained from G with zero total augmentation cost such that G′ admits a strongly stable matching, say M ′ , then the instance I admits a satisfying assignment.

Proof sketch. We claim that |M ′ (ws )| = 1 and M ′ (ws ) ∈ {bsi , bsj , bsk } for each s ∈ {1, 2, . . . , α}. We further claim that (bsi ,ws ) ∈ M ′ , implies (bi1 i ,wi1 ) ∈ M ′ and (bi2 i ,wi2 ) ∈ M ′ . We set the truth assignment to variables as follows. If M ′ (bsk ) = ws , then set Xi and Xj to false and Xk = true in the clause Cs. The first claim proves the satisfiability, and the first and second claims together prove the validity as well as consistency.

This completes the hardness reduction which shows that the decision version of MINSUM-COST problem is NP-hard for the budget ℓ = 0. This completes the proof of Theorem 3.

4 MINMAX-SS Problem

In this Section, we consider the MINMAX-SS problem. We show that the MINMAX-SS problem is NP-hard even in a very restricted setting. For this, we consider a special case of this problem, where we set q(h) = 1 for all h ∈ H and the budget ℓ = 1. We call this special case 1-OR-2 CAPACITYSS problem as the quota of each hospital in the augmented instance is restricted to 1 or 2. Next, we show the hardness of 1-OR-2 CAPACITY-SS problem thereby proving Theorem 4.

4.1 Hardness of 1-OR-2 CAPACITY-SS Problem

We prove the hardness of 1-OR-2 CAPACITY-SS problem by reducing from an instance of the MONOTONE NOT-ALLEQUAL 3-SAT problem. The input for MONOTONE NOTALL-EQUAL 3-SAT problem is a conjunction of clauses. Each clause is a disjunction of exactly three variables, and no variable appears in negated form. The goal is to determine whether there exists a truth assignment to the variables such that for each clause, at least one variable is set to true and at least one to false. This problem is known to be NPcomplete [Porschen et al., 2014] even when each variable appears in exactly four clauses [Darmann and D¨ocker, 2020].

Gadget Reduction. Let I be an instance of the MONOTONE NOT-ALL-EQUAL 3-SAT problem, where each variable appears in exactly four clauses.

Given I, we construct an instance G = (R ∪ H, E) of 1OR-2 CAPACITY-SS problem with quota q(h) = 1 for each h ∈ H. In our reduced instance G, there exists a gadget Gs corresponding to the clause Cs in I. The gadget Gs is the same as the one constructed in Section 3. Hence, the intragadget edges are exactly the same. However, the inter-gadget edges appear in a cyclical order. The preference list of a resident bsp corresponding to the variable Xp for p ∈ {i, j, k} consists of three hospitals - two within the gadget Gs, and one outside the gadget Gs. Analogously, the hospital vs p corresponding to Xp ranks the resident asp as its top choice, followed by a tie of length two consisting of the two b-residents - one from the same gadget and the other from a different gadget. See full version [Ranjan et al., 2024] for details.

4.2 MINMAX-SS Problemwith Bounded Ties

In this section, we consider MINMAX-SS-BT problem - a special case of the MINMAX-SS problem. First, we observe that executing Algorithm 1 on an instance of the MINMAXSS-BT problem produces an ℓ-augmented instance. This is because the tie length is bounded by ℓ + 1, and a hospital h proposes to residents at a particular rank, say k, only if h remains under-subscribed after proposing to all residents up to rank k - 1. The facts that (i) h was under-subscribed before proposing to kth -rank residents, and (ii) the length of the tie at rank k is at most ℓ + 1, together imply that hospital h cannot be over-subscribed by more than ℓ residents. Thus, for a given MINMAX-SS-BT instance, the existence of an ℓ-augmented instance is guaranteed and can be computed efficiently. However, the strongly stable matchingM ′ returned by Algorithm 1 need not be resident-optimal. For example, for the instance shown in Figure 2, executing Algorithm 1 on G outputs the augmented instance G′ with q′ (h1) = 2 and q′ (h2) = 1 and the strongly stable matching M ′ = {(r1, h2), (r2, h1), (r3, h1)}. The resident-optimal strongly stable matching in G′ is M ′′ = {(r1, h1), (r2, h2), (r3, h1)}, which is better than M ′ for r1, r2 and no worse for the remaining residents. Yet, M ′′ is not the best for the residents

r1 : h1, h2 r2 : h2, h1 r3 : h1 [1] h1 : (r2, r3), r1 r4 : h2 [1] h2 : r1, r2, r4

among strongly stable matchings across all ℓ-augmented instances of G.

For example, the instance ̂G obtained from G (in Figure 2) by augmenting the capacities of both h1 and h2 by one, i.e. ˆ q(h1) = ˆ q(h2) = 2 contains the matching ̂ M = {(r1, h1), (r2, h2), (r3, h1), (r4, h2)}, which is a strongly stable matching in ̂G. Moreover, ̂ M(r) ⪰r M ′′ (r) for each resident r, and ̂ M(r4) ≻r4 M ′′ (r4). This example demonstrates that simply executing the resident-proposing algorithmby Irving et al. [2003] on the augmented instanceG′ output by Algorithm 1, does not give the best possible match to the residents. In this context, we define and consider a resident-optimal ℓ-augmented instance of G (see Section 1.2 for the definition).

We present an efficient algorithm that outputs a residentoptimal ℓ-augmented instance G′ . We begin by setting a temporary quota for each hospital h as qt(h) = q(h) + ℓ. Let us denote this instance by Gt. Next, we execute the algorithm by Irving et al. [2003] (restricted to H-side ties - see full version [Ranjan et al., 2024]) on the instance Gt. Let M ′ be the tentative matching (also called the engagement graph) obtained at the end of the execution by the algorithm of Irving et al. [2003]. We note that a hospital h may be oversubscribed in M ′ w.r.t. its original quota q(h). However, for every hospital h, we have |M ′ (h)| ≤ qt(h). We further note that the matching M ′ need not be strongly stable in Gt. Yet, we show that it is possible to fix the quota of each hospital h to q′ (h) = max{q(h), |M ′ (h)|} such that the tentative matching M ′ becomes a strongly stable matching in the modified instance G′ . See full version [Ranjan et al., 2024] for details.

Theorem 7 (⋆). The instance G′ returned by our algorithm is a resident-optimal ℓ-augmented instance of G. Moreover, the matching M ′ in G′ is a resident-optimal strongly stable matching across all ℓ-augmented instances of G.

Theorem 7 immediately gives us the following corollary.

Corollary 2. The strongly stable matchingM ′ output by our algorithm matches the maximum number of residents across strongly stable matchings of all ℓ-augmented instances of G.

Conclusion. In this paper, we study capacity augmentation problem in the many-to-one HR-HT setting for the notion of strong stability. We consider the MINSUM and MINMAX objectives. For the MINSUM-SS problem, apart from polynomial time solvability, we are able to show an invariance result with respect to all optimal augmentations. For the MINMAXSS problem, it is natural to ask for an approximation algorithm- we leave it as an open question. Another direction worth exploring is reduction in quotas to achieve stability, as is done by Gokhale et al. [2024] for strict preferences.

Acknowledgments

We thank the anonymous reviewers for their helpful comments. Keshav Ranjan acknowledges the support of a doctoral fellowship from the IIT Madras Pravartak Technologies Foundation for the academic year 2024-25.