Answer: \(\mathrm{NP}\text{-hard}\), even without hospital-specific expansion limits
Proposition 1 — class: hardness
Given finitely many hospitals, a finite support \(T\) of resident types with rational masses \(\mu_t\), complete resident rankings and hospital priority classes, rational per-capita baseline capacities, an expansion budget and optional hospital limits, and a welfare threshold \(K\), does there exist a feasible real expansion vector whose resident-proposing mass-DA assignment has total resident rank at most \(K\)?
Let \(H\) contain \(m\geq 1\) hospitals. A society is given by its support: an ordered list \(T\) of \(\tau\geq 1\) resident types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a strict, complete ranking of hospitals; every hospital is acceptable. Each hospital has ordered priority classes covering all types; ties between distinct types are broken by their order in the support list. Mass within a type is divisible and interchangeable.
The input includes binary-rational baseline capacities \(q_h\geq 0\) with \(\sum_hq_h\geq 1\), a budget \(B\geq 0\), optional expansion limits \(b_h\geq 0\), and a threshold \(K\in\mathbb{Q}\). A feasible expansion satisfies \(e\in\mathbb{R}_{\geq 0}^{H}\), \(\sum_he_h\leq B\), and \(e_h\leq b_h\) wherever a limit is supplied.
For capacities \(q+e\), resident-proposing mass deferred acceptance starts with all mass applying to its first choice. In synchronous rounds, each hospital retains the highest-priority mass among its current holdings and new applications up to capacity, splitting the cutoff type if necessary; rejected mass applies next to its next-ranked hospital. Let \(x_{th}(e)\) be the terminal held mass, or its limit if rounds continue indefinitely.
Define \(r_t(h)\) as the number of hospitals ranked above \(h\), and \(C(e)=\sum_{t,h}r_t(h)x_{th}(e)\). Let \(L\) be the total binary input length, including all numerical data; state running times in \(m,\tau,L\).
Is deciding whether some feasible real expansion \(e\) satisfies \(C(e)\leq K\) solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite residents and integer expansions, this decision problem is \(\mathrm{NP}\)-complete even without hospital-specific limits, under strict, complete preferences ([original hardness source](https://arxiv.org/pdf/2110.00734v1)). No result settling the exact mass problem specified above was identified in the literature search.
The decision problem is \(\mathrm{NP}\text{-hard}\), even without hospital-specific expansion limits. The reduction below allows arbitrary real expansions and uses dyadic rational masses and capacities.
We reduce from positive-integer SUBSET SUM: given binary-encoded positive integers \(a_1,\ldots,a_n\) and an integer \(D\), decide whether some \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}a_i=D\). This is the classical \(\mathrm{NP}\text{-complete}\) problem called KNAPSACK in [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). We restrict to \(1\leq D\leq S\), where \(S=\sum_i a_i\); instances outside this range are immediately decidable, so this restriction preserves hardness.
Choose a power of two \(Q\) satisfying \(2S<Q\leq4S\), and put \(\alpha_i=a_i/Q\).
Create hospitals \(p_i,r_i\) for each index \(i\), together with a common hospital \(s\). Create types \(A_i,B_i\), each of mass \(\alpha_i\), and a ballast type \(Z\) of mass \(1-2S/Q\). The support order is
\((A_1,B_1,\ldots,A_n,B_n,Z)\).
All masses are positive and sum to one.
The first three hospitals in each relevant preference list are
\(A_i:\quad p_i\succ r_i\succ s,\qquad B_i:\quad r_i\succ p_i\succ s.\)
Append every remaining hospital in any fixed order. Type \(Z\) ranks \(s\) first and then all other hospitals.
Hospital \(p_i\) prioritizes \(B_i\) above \(A_i\), followed by all other types. Hospital \(r_i\) prioritizes \(A_i\) above \(B_i\), followed by all other types. Use singleton priority classes throughout, completing every list arbitrarily. Hospital \(s\) can have any strict priority order.
Set baseline capacities to
\(q_{p_i}=0,\qquad q_{r_i}=\alpha_i,\qquad q_s=1.\)
Thus \(\sum_hq_h=1+S/Q\geq1\). Supply no expansion limits, and set
\(B=D/Q,\qquad K=3(S-D)/Q.\)
All numerical data are dyadic rationals.
Since hospital \(s\) has capacity at least one, it never rejects any application: total resident mass is one. Consequently, no resident reaches a hospital ranked below \(s\). Each pair of types \(A_i,B_i\) therefore evolves independently of every other pair, while \(Z\) always obtains its first choice.
Consider a single pair of types, each of mass \(\alpha>0\). Write
\(u=e_p,\qquad v=e_r.\)
The relevant capacities are \(u\) at \(p\) and \(\alpha+v\) at \(r\). Let \(c_\alpha(u,v)\) denote the pair’s terminal cost.
We prove, for every real \(u,v\geq0\), that
\(\displaystyle c_\alpha(u,v)= \begin{cases} 0,&u\geq\alpha,\\ \alpha-u,&u<\alpha\ \text{and}\ u+v\geq\alpha,\\ 3\alpha-u-2v,&u+v<\alpha. \end{cases}\)
Both types fit at their first choices immediately. Their cost is zero.
Initially, \(p\) retains mass \(u\) of type \(A\), rejecting \(\alpha-u\) to \(r\). Hospital \(r\) already holds all \(\alpha\) units of type \(B\).
Their combined mass is \(2\alpha-u\leq\alpha+v\), so \(r\) retains everything. No further rejection occurs. Only the mass \(\alpha-u\) of type \(A\) receives its second choice, giving cost \(\alpha-u\).
This includes the boundary \(u+v=\alpha\).
Put \(d=\alpha-u-v>0\).
Hospital \(r\) never rejects type \(A\): it ranks \(A\) above \(B\), and its capacity is at least the entire mass \(\alpha\) of type \(A\).
After the first rejected \(A\)-mass reaches \(r\), let \(z_0=\alpha-u\) be the amount of type \(A\) held there. More generally, let \(z_j\) be its held \(A\)-mass after successive rounds in which newly rejected \(A\)-mass arrives.
Since \(z_j\geq z_0=\alpha-u>v\), hospital \(r\) is full and holds \(B\)-mass \(\alpha+v-z_j\). It has therefore cumulatively rejected \(B\)-mass \(z_j-v\).
By the following round, all that rejected \(B\)-mass has applied to \(p\). Because \(p\) prioritizes \(B\) above \(A\), its remaining \(A\)-mass is
\(\max\{u-(z_j-v),0\}=\max\{u+v-z_j,0\}.\)
Every other unit of \(A\)-mass has been rejected from \(p\) and reaches \(r\) in the next round. Hence
\(z_{j+1}=\alpha-\max\{u+v-z_j,0\}=\min\{\alpha,z_j+d\}.\)
Starting from \(z_0=\alpha-u\), this recurrence reaches \(\alpha\) after at most \(\lceil u/d\rceil\) updates. Thus this gadget terminates after finitely many rounds, even for arbitrary real capacities.
At termination, all \(A\)-mass is at \(r\). Hospital \(r\) also holds \(B\)-mass \(v\); hospital \(p\) holds \(B\)-mass \(u\); and the remaining \(B\)-mass \(d\) is at \(s\). Therefore
\(c_\alpha(u,v)=\alpha+u+2d=3\alpha-u-2v.\)
This proves the formula in every case.
At zero expansion, the gadget’s cost is \(3\alpha\). Define its improvement by
\(g_\alpha(u,v)=3\alpha-c_\alpha(u,v).\)
We claim that
\(g_\alpha(u,v)\leq3(u+v),\)
with equality exactly at
\((u,v)=(0,0)\quad\text{or}\quad(u,v)=(\alpha,0).\)
The cost formula proves this by three cases:
The exact equality characterization is what prevents fractional expansions from circumventing the reduction.
For an arbitrary feasible real expansion, write
\(u_i=e_{p_i},\qquad v_i=e_{r_i},\qquad w=e_s.\)
The ballast type contributes zero cost, and expanding \(s\) does not change any assignment. From the gadget calculation,
\(C(0)=3\sum_i\alpha_i=3S/Q.\)
Let \(G=C(0)-C(e)\) be the total improvement, and let \(E=\sum_i(u_i+v_i)+w\) be the total expansion. The sharp bound gives
\(G=\sum_i g_{\alpha_i}(u_i,v_i)\leq3\sum_i(u_i+v_i)\leq3E\leq3B.\)
If the SUBSET SUM instance is positive, choose \(I\) with \(\sum_{i\in I}a_i=D\). Expand \(p_i\) by \(\alpha_i\) for \(i\in I\), and leave every other expansion zero. This spends exactly \(D/Q=B\). Selected gadgets have zero cost and unselected gadgets have cost \(3\alpha_i\), so
\(C(e)=3(S-D)/Q=K.\)
Conversely, suppose a feasible real expansion satisfies \(C(e)\leq K\). Since \(K=C(0)-3B\), it follows that \(G\geq3B\). Every inequality in the preceding chain must therefore be an equality.
In particular, \(w=0\), the budget is exhausted, and every gadget attains equality in its individual improvement bound. The equality characterization implies
\(v_i=0,\qquad u_i\in\{0,\alpha_i\}\)
for every index \(i\). If \(I=\{i:u_i=\alpha_i\}\), budget exhaustion yields
\(\sum_{i\in I}\alpha_i=B,\)
and hence \(\sum_{i\in I}a_i=D\).
Thus the constructed mass instance admits a successful feasible real expansion if and only if the original SUBSET SUM instance is positive.
The construction has \(m=\tau=2n+1\). Since \(\log Q=O(\log(S+1))\), its total binary input length satisfies
\(L=O\!\left(n^2\log(n+1)+n\log(S+1)\right).\)
Complete preferences and priorities account for the first term; numerical data account for the second. The transformation can be implemented in \(O(m\tau L)\) bit operations and is polynomial in the source input length.
Therefore the specified decision problem is \(\mathrm{NP}\text{-hard}\), already in the subclass without expansion limits. An algorithm polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument resolves the assigned problem: it proves \(\mathrm{NP}\)-hardness for the specified divisible-mass model, even without hospital-specific expansion limits. I found no mathematical gaps or incorrect steps.
The source problem is precisely binary-encoded positive-integer SUBSET SUM, a standard \(\mathrm{NP}\)-complete problem. The historical name KNAPSACK is consistent with the cited [Karp paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). Restricting to \(1\leq D\leq S\) removes only immediately decidable instances and preserves hardness.
The choice \(2S<Q\leq4S\) ensures every \(\alpha_i=a_i/Q\) is positive and the ballast mass \(1-2S/Q\) is strictly positive. The displayed masses sum to one. All capacities and the budget are nonnegative, and the baseline capacities sum to \(1+S/Q\geq1\).
The preferences are strict and complete after the stated completion. Singleton priority classes satisfy the hospital-priority requirements; support-order tie breaking is immaterial.
The claim that \(s\) never rejects is valid. At any round, its holdings and incoming applications together contain at most the society’s total mass, which is one, while its capacity is at least one.
Consequently, each relevant type visits only its own two gadget hospitals and possibly \(s\). The arbitrary portions of the completed preference and priority lists cannot affect the dynamics. Type \(Z\) stays at its first choice and contributes zero cost. Expanding \(s\) cannot change any assignment.
When \(u\geq\alpha\), both types fit at their first choices, giving zero cost.
When \(u<\alpha\) and \(u+v\geq\alpha\), the rejected \(A\)-mass is \(\alpha-u\). The total demand at \(r\) is
\[
2\alpha-u\leq\alpha+v.
\]
Thus no further rejection occurs, and the cost is \(\alpha-u\). The equality boundary \(u+v=\alpha\) is handled correctly.
For \(u+v<\alpha\), the definition \(d=\alpha-u-v>0\) is valid. Hospital \(r\) cannot reject \(A\), because \(A\) has higher priority and its entire mass is at most \(r\)’s capacity.
At each stated checkpoint, \(z_j\geq\alpha-u>v\). Hence \(r\) is full and holds \(B\)-mass \(\alpha+v-z_j\), so its cumulative rejection of \(B\) is \(z_j-v\).
Once that mass has applied to \(p\), priority for \(B\) leaves exactly
\[
\max\{u+v-z_j,0\}
\]
of \(A\) there. The ensuing recurrence
\[
z_{j+1}=\min\{\alpha,z_j+d\}
\]
follows correctly from the synchronous round dynamics.
The initial distance to \(\alpha\) is \(u\), so the bound \(\lceil u/d\rceil\) on recurrence updates is correct, including \(u=0\). Subsequent applications finish after finitely many additional rounds.
The terminal holdings stated in the proof conserve mass and respect capacities. Their ranks give
\[
c_\alpha(u,v)=\alpha+u+2d=3\alpha-u-2v.
\]
Thus the complete piecewise formula is correct for every real \(u,v\geq0\).
Each branch yields \(g_\alpha(u,v)\leq3(u+v)\).
In the first branch, equality requires \(u+v=\alpha\), which together with \(u\geq\alpha\) forces \((u,v)=(\alpha,0)\). The second branch is strictly below the bound. In the third branch, the slack is \(2u+v\), which vanishes exactly at \((0,0)\).
The claimed equality characterization is therefore exact. It applies to arbitrary real expansions, with no integrality assumption.
A subset summing to \(D\) gives the stated feasible expansion and cost exactly \(K\).
Conversely, \(C(e)\leq K\) implies \(G\geq3B\). Combined with the proved inequality chain, this forces equality throughout. In particular, \(w=0\), \(E=B\), and every individual gadget has zero improvement slack: the slacks are nonnegative and their finite sum is zero.
Therefore every \(v_i=0\) and every \(u_i\) belongs to \(\{0,\alpha_i\}\). Budget exhaustion then gives a subset summing exactly to \(D\). The converse fully excludes fractional workarounds.
The counts \(m=\tau=2n+1\) are correct. Complete rankings and priorities require \(O(n^2\log(n+1))\) bits, and the numerical data require \(O(n\log(S+1))\) bits. The claimed construction-time bound is a valid polynomial upper bound.
The potentially large number of deferred-acceptance rounds when \(d\) is small does not undermine the reduction: the proof does not claim to simulate those rounds in polynomial time.
The output establishes the requested hardness alternative. It does not claim membership in \(\mathrm{NP}\) or strong \(\mathrm{NP}\)-hardness, and neither is needed. No additional clarification is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.