Generalized Capacity Planning for the Hospital-Residents Problem^††thanks: A preliminary version of this work appeared in IWOCA 2023 [15].

We are given a bipartite graph $G=(\mathcal{A}\cup\mathcal{P},E)$, where $\mathcal{A}$ denotes the set of agents and $\mathcal{P}$ denotes the set of programs. An edge $(a,p)\in E$ indicates that $a$ and $p$ form an acceptable agent-program pair. For each vertex $v\in\mathcal{A}\cup\mathcal{P}$, we define $\mathcal{N}(v)$ to be the set of vertices adjacent to $v$ (that is, the neighborhood of $v$). Each vertex $v\in\mathcal{A}\cup\mathcal{P}$ ranks vertices in $\mathcal{N}(v)$ in a strict order, called the preference list of vertex $v$. For any vertex $v\in\mathcal{A}\cup\mathcal{P}$, if $v$ prefers $x$ over $y$ then we denote it by $x\succ_{v}y$, equivalently, $y\prec_{v}x$. The length of the longest preference list of an agent is denoted by $\ell_{a}$ and the length of the longest preference list of a program is denoted by $\ell_{p}$. Each program $p$ has an initial quota $q(p)$ which is a positive integer. In literature, this instance is referred to as the hr instance (programs being the hospitals and agents being the residents). In our setting, in addition to the quotas, a program $p$ has an associated non-negative integral cost $c(p)$. As long as a matching matches upto $q(p)$ many agents to $p$, no cost is incurred. For each agent matched above the quota of $p$, we incur a cost $c(p)$ for exceeding the quota of $p$.

A many-to-one matching (called matching here onwards) $M\subseteq E$ in an hr instance is an assignment of agents to programs such that each agent is matched to at most one program and each program $p$ is matched to at most $q(p)$ many agents. Let $M(a)$ denote the program to which the agent $a\in\mathcal{A}$ is matched. We say $M(a)=\bot$ if $a$ is unmatched in $M$. Let $M(p)$ denote the set of agents matched to program $p$. We call a program $p\in\mathcal{P}$ under-subscribed in a matching $M$ if $|M(p)|<q(p)$ and fully-subscribed if $|M(p)|=q(p)$. We assume that any agent prefers to be matched (to some program) rather than being unmatched.

Given an hr instance, a stable matching is guaranteed to exist and can be computed in linear time by the celebrated Gale and Shapley algorithm [10]. A matching $M$ is $\mathcal{A}$-perfect if every agent is matched in $M$. In this work, our goal is to compute a matching that is stable and $\mathcal{A}$-perfect. There exist simple hr instances that do not admit an $\mathcal{A}$-perfect stable matching. An hr instance may admit multiple stable matchings, however, by the Rural Hospitals’ Theorem [18], it is known that all stable matchings in an hr instance match the same set of agents. Thus, one can efficiently determine whether an hr instance admits an $\mathcal{A}$-perfect stable matching.

In this work, to achieve $\mathcal{A}$-perfectness, we consider quota augmentation for programs. Let $\mathbb{N}$ be the set of non-negative integers. Let $\tilde{q}:\mathcal{P}\rightarrow\mathbb{N}$ be a function that maps a non-negative integer to every program $p\in\mathcal{P}$. The $\tilde{q}(p)$ indicates the amount by which the quota at program $p$ should be increased such that the modified hr instance admits an $\mathcal{A}$-perfect stable matching $M$ and for every program $p$ the quota of $p$ is equal to $q(p)+\tilde{q}(p)$.

A trivial quota augmentation wherein for every program $p$, $\tilde{q}(p)$ is set such that $q(p)+\tilde{q}(p)=|\mathcal{N}(p)|$ always results in an $\mathcal{A}$-perfect stable matching. To control $\tilde{q}(p)$, we use the cost function $c:\mathcal{P}\rightarrow\mathbb{N}$ over the set of programs. Given a matching $M$, the cost incurred at a program $p$ is $\tilde{q}(p)\cdot c(p)$. In other words, the initial $q(p)$ many positions of a program $p$ are free.

Given an hr instance along with costs, our goal is to compute an $\mathcal{A}$-perfect, stable matching that incurs the minimum cost. We consider two natural notions of minimization over cost:

• •

  minimize the total cost incurred, that is, $\sum_{p\in\mathcal{P}}(\tilde{q}(p)\cdot c(p))$.

• •

  minimize the maximum cost incurred at any program, that is, $\max_{p\in\mathcal{P}}\{\tilde{q}(p)\cdot c(p)\}$.

Based on this, we define the MinSum and the MinMax problems as follows:

1. 1.

   Unit cost for augmentation: When every program $p$ has $c(p)=1$, we denote the problems as MinSumQ and MinMaxQ. This is equivalent to the setting investigated by Chen et al. [7].

2. 2.

   Initial quotas being zero: When every program $p$ has $q(p)=0$, we denote the problems as MinSumC and MinMaxC. This is equivalent to the cost-controlled quotas setting investigated by Limaye and Nasre [15].

The notion of stability considered earlier, is defined with respect to input quotas. In a setting where initial quotas may be zero, we use the following well-studied relaxation of stability. Recall that if the matching $M$ is not stable then there exists a blocking pair $(a,p)$ with respect to $M$. The blocking pair may arise due to under-subscription of the program or may arise due to the matching $M$ assigning to $p$ an agent that $p$ prefers lower than $a$. If we allow blocking pairs arising due to an under-subscribed program $p$, then we get a relaxation of stability, called envy-freeness [20].

We observe the following about envy-freeness and stability when the initial quotas of all programs are zero. Let $H$ be an instance in our setting in which the initial quotas of all programs are zero. Let $M$ be an $\mathcal{A}$-perfect matching in the augmented instance $H^{\prime}$. If $M$ is stable in $H^{\prime}$, then by definition, $M$ is also envy-free in $H^{\prime}$. Next, suppose that $M$ is an envy-free matching in $H^{\prime}$. Let $G$ denote the hr instance wherein the preferences are borrowed from $H^{\prime}$ (that is, $H$), and for every program $p$, we set its quota in $G$ to be equal to $|M(p)|$. Then, $M$ is stable in $G$. This implies that when we start with initial quotas of all programs being zero, envy-freeness and stability are equivalent.

It is straightforward to verify that $M_{1}$ is the unique optimal solution for MinSum, whereas $M_{2}$ is the unique optimal solution for MinMax.

We show that the MinMax problem can be solved in polynomial time whereas the MinSum problem is $\sf NP$-hard. Moreover, the MinSum problem is inapproximable under standard complexity-theoretic assumptions.

We say that the preferences of elements of a particular set, say the agent set, are derived from a master list if there is an ordering of the programs and the preferences of all agents respect this ordering.

The above theorem immediately implies that the MinSum problem is constant-factor inapproximable. The constant factor inapproximability of the MinSum problem is known from the result of Chen et al. [7], however their result does not imply Theorem 1.2. We further show that under the Unique Games Conjecture (UGC) [13], MinSumC cannot be approximated to within $(\ell_{a}-\epsilon)$ for any $\epsilon>0$.

Theorem 1.3 implies that the MinSum problem is also ($\ell_{a}-\epsilon$)-inapproximable ($\epsilon>0$) under UGC. This gives another lower bound for the MinSum problem.

We now state our algorithmic results for MinSum. We present two approximation algorithms for the general instances of the MinSum problem.

We present an approximation algorithm with a guarantee of $\ell_{a}$ when the instance has two distinct costs, thereby meeting the lower bound presented in Theorem 1.3.

Our results are summarized in Table 1.

As noted earlier, envy-freeness and stability are not equivalent in the hr setting. We begin by noting a useful property about any blocking pair with respect to an envy-free matching.

Next we show that it is possible to convert an envy-free matching $M$ in an hr instance to a stable matching $M_{s}$ in the same hr instance (with the program quotas unchanged) such that the agents that are matched in $M$ remain matched in $M_{s}$. Algorithm 1 gives a simple procedure for the same.

It is easy to see that no agent who is matched in $M$ gets unmatched in $M_{s}$. Next, we prove that in each iteration of the algorithm in line 6, $M_{s}$ remains envy-free.

This establishes the following lemma.

Lemma 4 implies that if $M$ is an $\mathcal{A}$-perfect, envy-free matching in an hr instance , then there exists an $\mathcal{A}$-perfect, stable matching $M_{s}$ in the same instance.

In this section, we present a polynomial time algorithm for the MinMax problem. We begin with some observations. Let $M^{*}$ be an optimal solution for the MinMax problem and let $t^{*}=\max_{p}\{c(p)\cdot\tilde{q}(p)\}$ be the cost of $M^{*}$. For an integer $t$, we define $G_{t}$ to be the hr instance such that for every program $p\in\mathcal{P}$, its quota is $q(p)+\left\lfloor\frac{t}{c(p)}\right\rfloor$. We observe the following:

• •

  For any integer $t\geq t^{*}$, there exists an $\mathcal{A}$-perfect stable matching in $G_{t}$. This holds because $M^{*}$ is an $\mathcal{A}$-perfect stable matching in $G_{t}$ and for every program $p$, $q(p)$ in $G_{t}$ is at least as much as $q(p)$ in $G_{t^{*}}$. Therefore, $M^{*}$ is an $\mathcal{A}$-perfect envy-free matching in $G_{t}$. Combining these facts with Lemma 4 we get the desired result.

• •

  For any integer $t<t^{*}$, there does not exist an $\mathcal{A}$-perfect stable matching in $G_{t}$.

In the following lemma, we show an upper bound on the number of distinct values that $t^{*}$ can take. Recall that $m=|E|$.

We now give a polynomial-time algorithm for the MinMax problem – construct a sorted array $\hat{c}$ such that it contains all the possible values of $t^{*}$. Then perform a binary search on this array. For each cost $t$ being considered, construct the hr instance $G_{t}$ and check whether $G_{t}$ admits an $\mathcal{A}$-perfect stable matching. If yes, search over values less than or equal to $t$, otherwise search over values strictly greater than $t$.

By Lemma 5, there are $O(m)$ values in the array $\hat{c}$ and binary search over these costs takes $O(\log m)$ iterations. In each iteration a stable matching is computed and checked for $\mathcal{A}$-perfectness, thereby spending $O(m)$ time per iteration. This implies that the algorithm runs in $O(m\log{m})$ time. This proves Theorem 1.1.

Using the algorithm for the MinMax problem presented in Section 3.1, we present a $|P|$-approximation algorithm for the MinSum problem.

This proves Theorem 1.4.

In this section, we present an $\ell_{p}$-approximation algorithm for the MinSum problem. This algorithm is an extension of the algorithm presented in [15] for a restricted setting wherein all initial quotas are zero.

Let $G$ be the instance of the MinSum problem. Let $M_{I}$ be any stable matching in $G$. We call $M_{I}$ the initial stable matching. If $M_{I}$ is $\mathcal{A}$-perfect then we return $M_{I}$. Otherwise, at least one agent is unmatched in $M_{I}$. Let $\mathcal{A}_{u}$ denote the set of agents that are unmatched in $M_{I}$. It is well known that all stable matchings of an hr instance match the same set of agents [18]. Hence, the set $\mathcal{A}_{u}$ is invariant of $M_{I}$. For every agent $a$, let $p_{a}^{*}$ denote the least-cost program occurring in the preference list of $a$. If there are multiple such programs, let $p_{a}^{*}$ be the highest-preferred one among them. Using $M_{I}$ we construct an $\mathcal{A}$-perfect matching by matching every agent $u\in\mathcal{A}_{u}$ to $p_{u}^{*}$. This gives us an intermediate matching, we call it $M_{L}$. We observe that $M_{L}$ is $\mathcal{A}$-perfect but not necessarily stable. Next, we promote agents to ensure that $M_{L}$ is stable, as described below.

We start with the matching $M=M_{L}$. We consider a program $p$ and consider agents in the reverse order of the preference list of $p$. If an agent $a$ envies agent $a^{\prime}\in M(p)$ then we promote $a$ by unmatching it and matching it to $p$ (see Fig. 2). This process repeats for every program. The pseudo-code is given in Algorithm 2.

We proceed to prove the correctness. We begin by showing that the matching $M$ computed by Algorithm 2 is an $\mathcal{A}$-perfect stable matching.

Next, we show that $M$ is an $\ell_{p}$-approximation of MinSum. Let $P_{\text{empty}}$ denote the set of programs $p$ such that no agent is matched to $p$ in the matching $M_{I}$ and $P_{\text{LC}}$ denote the set of programs $p$ such that for at least one agent $u\in\mathcal{A}_{u}$, $p^{*}_{u}=p$. Let $S^{c}$ denote the complement of $S$ with respect to $\mathcal{P}$. We define the following four sets of programs. Clearly, these four sets are pairwise disjoint (see Fig. 3).

• •

  $P_{1}=P_{\text{empty}}^{c}\cap P_{\text{LC}}^{c}$

• •

  $P_{2}=P_{\text{empty}}^{c}\cap P_{\text{LC}}$

• •

  $P_{3}=P_{\text{empty}}\cap P_{\text{LC}}$

• •

  $P_{4}=P_{\text{empty}}\cap P_{\text{LC}}^{c}$

Now we proceed to prove the approximation guarantee by observing important properties of the programs in these sets.

Matchings $M_{I}$ and $M_{L}$ can be computed in $O(m)$ time using the Gale-Shapley algorithm. The for loop in line 8 takes $O(m\ell_{p})$ time. Thus, algorithm 2 runs in $O(m\ell_{p})$ time. This proves Theorem 1.5.

Fig. 4 shows the LP relaxation for the MinSumC problem. Let $H=(\mathcal{A}\cup\mathcal{P},E)$ be the underlying graph of the MinSumC instance. Let $x_{a,p}$ be a primal variable for the edge $(a,p)\in E$: $x_{a,p}$ is $1$ if $a$ is matched to $p$, $0$ otherwise. The objective of the primal LP (Eq. 1) is to minimize the total cost of all matched edges. Eq. 2 encodes the envy-freeness constraint: if agent $a$ is matched to $p$ then every agent $a^{\prime}\succ_{p}a$ must be matched to either $p$ or a higher-preferred program than $p$, otherwise $a^{\prime}$ envies $a$. In the primal LP, the envy-freeness constraint is present for a triplet $(a^{\prime},p,a)$ where $a^{\prime}\succ_{p}a$. We call such a triplet a valid triplet. Eq. 3 encodes $\mathcal{A}$-perfectness constraint.

In the dual LP, we have two kinds of variables, the $y$ variables which correspond to every agent and the $z$ variables which correspond to every valid triplet in the primal program. The dual constraint (Eq. 6) is for every edge $(a,p)$ in $E$. The $y_{a}$ variable corresponding to an agent $a$ appears in the dual constraint corresponding to every edge incident on $a$. The value $y_{a}$ can be interpreted as the cost paid by agent $a$ for matching $a$ to one of the programs in $\mathcal{N}(a)$. For an edge $(a,p)$ and an agent $a^{\prime}\succ_{p}a$, the dual variable $z_{a^{\prime},p,a}$ appears in negative form in exactly one constraint and it is for the edge $(a,p)$. The same dual variable $z_{a^{\prime},p,a}$ appears in positive form in the constraint for every edge $(a^{\prime},p^{\prime})$ such that $p^{\prime}=p$ or $p^{\prime}\succ_{a^{\prime}}p$ (refer Fig. 5). The value of $z_{a^{\prime},p,a}$ can be interpreted as the cost paid by agent $a$ in matching $a^{\prime}$ to a program $p^{\prime}$ such that $p^{\prime}=p$ or $p^{\prime}\succ_{a^{\prime}}p$ to resolve potential envy-pair $(a^{\prime},a)$ if $a$ gets matched to $p$. Following are the useful facts about the linear program and its dual.

For a given dual setting and an edge, if Eq. 6 is satisfied with equality then we call such an edge as a tight edge, otherwise it is a slack edge. For an edge $(a,p)$, $slack(a,p)$ denotes its slack. When referring to a $z$ variable, when a specific agent or program occurring in it does not matter, we use $\times$ in its place.

The definition of threshold agent is similar to the threshold resident defined in [14] and a barrier (vertex) defined in [9]. We remark that the threshold agent depends on the matching $M$, hence when $M$ gets modified, the threshold agents for programs may change.

It is straightforward to verify that for an envy-free matching $M$, if we match agent $a$ along a matchable edge then the resultant matching remains envy-free.

A reader may find the discussion in the Appendix about the challenges involved in designing a primal-dual algorithm for the general case of the MinSumC problem. In this section, we show that when the MinSumC instance has only two distinct costs $c_{1}$ and $c_{2}$ where $c_{1}<c_{2}$, we can circumvent the challenges and obtain an $\ell_{a}$-approximation algorithm for the MinSumC problem. We recall from Theorem 1.2 that even in this restricted setting, the problem remains NP-hard.

• •

  $M$ is envy-free, not necessarily $\mathcal{A}$-perfect and every matched edge is tight.

• •

  For an agent $a$ (matched or unmatched), for every $p\succ_{a}M(a)$, either (i) $(a,p)$ is tight and $thresh(p)\neq a$ or (ii) $slack(a,p)=c_{2}-c_{1}$.

Recall that when the matching is modified, thresholds may change, due to which a tight, non-matchable edge may become matchable. As long as there exists such an edge, we match it. This is achieved by the free-promotions routine. The free-promotions routine checks if there exists a matchable edge $(a,p)$. If there is no such edge, the routine terminates. Otherwise, it matches $(a,p)$, re-computes the threshold agents and repeats the search. Checking for a matchable edge and computing threshold agents takes $O(m)$ time where $m=|E|$. the free-promotions routine runs in $O(m^{2})$ time.

We begin with an empty matching $M$ and by setting all $y$ variables to $c_{1}$ and all $z$ variables to $0$ (line 1). Following this, for every agent $a$ with a cost $c_{1}$ program in $\mathcal{N}(a)$ we match the agent to its most-preferred program with cost $c_{1}$ (for loop at line 2). Next, we compute the threshold agent for every program w.r.t. $M$. As long as $M$ is not $\mathcal{A}$-perfect, we pick an arbitrary unmatched agent $a$ and update the dual variables as follows.

1. 1.

   For the agent $a$, we increase $y_{a}$ by $c_{2}-c_{1}$. We ensure that the dual setting is feasible and all edges incident on $a$ become tight for the dual constraint in Eq. 6. Although this step makes all edges incident on $a$ tight, they may not be necessarily matchable. Recall that a tight edge $(a,p)$ is matchable if $thresh(p)=a$.

2. 2.

   If there is a program $p$ such that $(a,p)$ is matchable, then $a$ is immediately matched to the most-preferred such program $p$ (line 10) and we are done with matching agent $a$. Since the matching is modified, we execute the free-promotions routine.

3. 3.

   In case there is no such program for which $a$ is the threshold agent, we update carefully selected $z$ variables in order to either promote the threshold agent (if matched) or match the (unmatched) threshold agent via the following steps.

   1. (a)

      We compute the set $\mathcal{P}(a)$ of programs $p\in\mathcal{N}(a)$ such that the dual constraint on edge $(a,p)$ is tight and $thresh(p)\neq a$ and $p\succ_{a}M(a)$ (line 13). In other words, $\mathcal{P}(a)$ is the set of programs in the neighbourhood of $a$ such that $p$ is higher-preferred over $M(a)$ and edge $(a,p)$ is tight but not matchable.

   2. (b)

      By the definition of $\mathcal{P}(a)$, for every $p_{j}\in\mathcal{P}(a)$, there exists $thresh(p_{j})=a^{\prime}\neq a$. We pick an arbitrary agent $a^{\prime}$ that is a threshold of some program in $\mathcal{P}(a)$ (line 15). Note that the agent $a^{\prime}$ can be the threshold agent of more than one program in $\mathcal{P}(a)$, and we let $\mathcal{P}(a,a^{\prime})$ denote the set of programs in $\mathcal{P}(a)$ for whom $a^{\prime}$ is the threshold. Let $p$ be the least-preferred program for $a^{\prime}$ in $\mathcal{P}(a,a^{\prime})$ (line 17).

   3. (c)

      Our goal is to match $a^{\prime}$ to a program $p^{\prime}$ such that $p^{\prime}=p$ or $p^{\prime}\succ_{a^{\prime}}p$. By the choice of $a,a^{\prime}$ and $p$ and from the primal LP, $(a^{\prime},p,a)$ is a valid triplet and therefore there exists a dual variable $z_{a^{\prime},p,a}$ (refer Fig. 5). We set $z_{a^{\prime},p,a}$ to $c_{2}-c_{1}$ (line 18). We ensure that this update maintains dual feasibility.

   4. (d)

      Recall that the variable $z_{a^{\prime},p,a}$ appears in the positive form in the dual constraint of every edge $(a^{\prime},p^{\prime})$ such that $p^{\prime}=p$ or $p^{\prime}\succ_{a^{\prime}}p$. We ensure that this update results in making all edges $(a^{\prime},p^{\prime})$ tight and at least one of these becomes matchable. We match $a^{\prime}$ along the most-preferred matchable edge (line 19). Recall that $z_{a^{\prime},p,a}$ variable appears in negative form in the dual constraint of edge $(a,p)$, hence edge $(a,p)$ becomes slack after this update.

   5. (e)

      Since $M$ is modified, we execute the free-promotions routine. If a tight edge incident on $a$ becomes matchable, then $a$ is matched inside the free-promotions routine.

   6. (f)

      We remark that the set $\mathcal{P}(a)$ computed in line 13 is dependent on the matching $M$, specifically $M(a)$ and the threshold agents w.r.t. $M$. In order to maintain a specific slack value on the edges that is useful in maintaining dual feasibility and ensuring progress, we re-compute the set $\mathcal{P}(a)$ (line 20) and re-enter the loop in line 14 if $\mathcal{P}(a)\neq\emptyset$.