Answer: \(\mathrm{NP}\)-complete, and hence \(\mathrm{NP}\)-hard
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-hard to compute an optimal stable assignment.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given hospitals with qualities \(q_j\), per-patient costs \(c_j\), a per-capita budget \(b\), and a society described by \(\tau\) patient-value types \(v_t\) with rational masses \(\mu_t\), compute a budget-feasible stable assignment maximizing average social welfare. The decision variables are masses \(x_{tj}\ge 0\) assigned from each type to each hospital and common waiting times \(w_j\ge 0\); require \(\sum_j x_{tj}=\mu_t\), \(\sum_{t,j}c_jx_{tj}\le b\), and every hospital receiving positive mass from type \(t\) maximizes that type's nonnegative utility \(v_tq_j-w_j\).
There are \(m\ge 2\) hospitals with positive binary-rational qualities \(q_j\) and per-unit-mass costs \(c_j\), and a binary-rational per-capita budget \(b\) satisfying \(\min_j c_j\le b<\max_j c_j\).
A society is given by its support: the list of \(\tau\ge 1\) distinct positive binary-rational patient values \(v_t\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
An assignment consists of real masses \(x_{tj}\ge 0\) and common real waiting times \(w_j\ge 0\), with \(\sum_jx_{tj}=\mu_t\) and \(\sum_{t,j}c_jx_{tj}\le b\). Every patient must be served; hospitals have no additional capacity constraints.
Stability requires that whenever \(x_{tj}>0\), \(v_tq_j-w_j\ge 0\) and \(v_tq_j-w_j\ge v_tq_k-w_k\) for every hospital \(k\), including hospitals receiving no mass. Mass may split arbitrarily among tied maximizers.
Average social welfare is \(W(x,w)=\sum_{t,j}x_{tj}(v_tq_j-w_j)\). Given a binary-rational threshold \(K\), the decision problem asks whether a feasible stable assignment has \(W(x,w)\ge K\).
Is this continuous stable-assignment decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For discrete indivisible patients with proportional valuations, exact optimal stable assignment is NP-hard, its welfare-threshold decision version is NP-complete, and an FPTAS exists. [Source](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p278.pdf)
For continuous populations, a common zero-wait lottery can be optimized by an LP; this uses expected-utility choice of lotteries rather than the stability requirement above. No result settling this exact support-encoded mass problem was located. [Source](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p278.pdf)
The continuous stable-assignment decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when every hospital satisfies \(c_j=q_j\), all qualities and costs are positive integers, and \(K=b\). The remaining input numbers in the construction are dyadic rationals.
The key is a welfare bound whose equality condition forces each support type to use a single hospital. Thus arbitrary mass splitting does not invalidate the reduction.
Order the support values as \(v_1>\cdots>v_n>0\), and write
\[
\]
\(M_i=\sum_{k=1}^{i}\mu_k.\)
For this section, suppose the values satisfy
\(M_i(v_i-v_{i+1})=\mu_i\quad\text{for }i<n,\qquad v_n=\mu_n.\)
Consider any stable assignment with \(c_j=q_j\). Define
\(u_i=\max_j(v_iq_j-w_j),\qquad r_i=\min\{q_j:x_{ij}>0\},\qquad \bar q_i=\frac{1}{\mu_i}\sum_jq_jx_{ij}.\)
These quantities are well defined because every type has positive mass and must be served. Stability implies that every hospital serving type \(i\) gives utility \(u_i\). Consequently,
\(W=\sum_i\mu_i u_i,\qquad C=\sum_i\mu_i\bar q_i,\)
where \(C\) denotes total cost.
Choose a hospital of quality \(r_i\) serving type \(i\). Type \(i+1\) can compare its utility with that hospital, so
\(u_{i+1}\ge u_i-(v_i-v_{i+1})r_i.\)
Hence
\(u_i-u_{i+1}\le(v_i-v_{i+1})r_i.\)
For the last type, nonnegative waiting times give
\(u_n\le v_nr_n.\)
Since \(M_n=1\), telescoping yields
\(\displaystyle W=u_n+\sum_{i=1}^{n-1}M_i(u_i-u_{i+1})\le v_nr_n+\sum_{i=1}^{n-1}M_i(v_i-v_{i+1})r_i=\sum_{i=1}^{n}\mu_i r_i.\)
Also, \(\bar q_i\ge r_i\). Therefore
\(\boxed{W\le\sum_i\mu_i r_i\le C.}\)
If \(W=C\), then
\(\sum_i\mu_i(\bar q_i-r_i)=0.\)
Every summand is nonnegative and every \(\mu_i\) is positive. Thus \(\bar q_i=r_i\) for every type. A weighted average of served qualities equals their minimum only when every positively served quality equals that minimum.
Equality condition. If all hospital qualities are distinct and \(W=C\), every support type sends all its mass to one hospital.
Use the standard \(\mathrm{NP}\)-complete problem \(\mathrm{SUBSET\ SUM}\): given positive integers \(s_1,\ldots,s_n\) and a target \(T\), decide whether some subset sums to \(T\). This is also the source problem in [Chan and Chen’s discrete reduction](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p278.pdf).
We may restrict to \(n\ge2\) and \(0<T<S\), where \(S=\sum_i s_i\). The excluded cases are directly decidable and can be mapped to fixed restricted yes or no instances.
Set
\(D=2^{n-1},\qquad a_1=1,\qquad a_i=2^{i-2}\text{ for }2\le i\le n,\qquad \mu_i=\frac{a_i}{D}.\)
Then
\(\sum_i a_i=D,\qquad M_i=\frac{2^{i-1}}{D}.\)
Choose the distinct positive values
\(v_1=\frac{n+1}{2},\qquad v_i=\frac{n-i+1}{2}\text{ for }2\le i\le n.\)
Their successive differences satisfy
\(v_1-v_2=1,\qquad v_i-v_{i+1}=\frac12\text{ for }2\le i<n.\)
It follows that
\(M_i(v_i-v_{i+1})=\mu_i\quad\text{for every }i<n,\qquad v_n=\frac12=\mu_n.\)
Thus the preceding welfare bound applies. All values and masses are dyadic rationals.
Choose a power of two \(R\) satisfying
\(R>D^2S.\)
For each \(i\), introduce two hospitals, indexed by \((i,0)\) and \((i,1)\), and put
\(h_i=\frac{D}{a_i}s_i,\)
\(q_{i,0}=c_{i,0}=R^{n-i+1},\qquad q_{i,1}=c_{i,1}=R^{n-i+1}+h_i.\)
Every \(h_i\) is a positive integer because \(a_i\) divides \(D\). Moreover,
\(h_i\le DS<R.\)
For \(i<n\),
\(q_{i+1,1}<R^{n-i}+R\le R^{n-i+1}=q_{i,0}.\)
Therefore all qualities are distinct, with ordering
\(q_{1,1}>q_{1,0}>q_{2,1}>q_{2,0}>\cdots>q_{n,1}>q_{n,0}.\)
Set the per-capita budget and welfare threshold to
\(\displaystyle b=K=\frac1D\sum_{i=1}^{n}a_iR^{n-i+1}+T.\)
This satisfies the required budget hypothesis. The minimum hospital cost is \(R\), and the baseline weighted average is strictly larger than \(R\), so \(b>R\).
For the upper bound, \(\mu_1=1/D\le1/2\), while every other baseline quality is at most \(R^{n-1}\). Hence
\(\displaystyle b\le\frac{R^n+R^{n-1}}2+T<R^n<q_{1,1}.\)
The strict middle inequality follows from
\(\displaystyle T<S<\frac{R(R-1)}2\le\frac{R^n-R^{n-1}}2,\)
using \(R>D^2S\ge4S\) and \(n\ge2\).
Thus \(\min_jc_j<b<\max_jc_j\).
The construction has polynomial bit length. We can choose \(R\) with
\(\log_2R=O(n+\log S).\)
The largest quality has bit length \(O(n(n+\log S))\); there are only \(2n\) hospitals and \(n\) support types. Every remaining input number also has polynomial bit length.
Suppose \(\varepsilon_i\in\{0,1\}\) satisfy
\(\sum_i\varepsilon_i s_i=T.\)
Assign all mass of type \(i\) to hospital \((i,\varepsilon_i)\), whose quality we denote by \(Q_i\). The ordering above gives \(Q_1>\cdots>Q_n\).
Set waiting times at these selected hospitals recursively:
\(w_n=0,\qquad w_i=w_{i+1}+v_{i+1}(Q_i-Q_{i+1})\quad\text{for }i<n.\)
These waiting times are nonnegative. To check stability, take \(i<k\). Then
\(\displaystyle w_i-w_k=\sum_{\ell=i}^{k-1}v_{\ell+1}(Q_\ell-Q_{\ell+1}).\)
Type \(i\)'s utility advantage over hospital \(k\) is
\(\displaystyle (v_iQ_i-w_i)-(v_iQ_k-w_k)=\sum_{\ell=i}^{k-1}(v_i-v_{\ell+1})(Q_\ell-Q_{\ell+1})\ge0.\)
Type \(k\)'s utility advantage over hospital \(i\) is
\(\displaystyle (v_kQ_k-w_k)-(v_kQ_i-w_i)=\sum_{\ell=i}^{k-1}(v_{\ell+1}-v_k)(Q_\ell-Q_{\ell+1})\ge0.\)
These comparisons cover every pair of selected hospitals. Furthermore,
\(\displaystyle w_i\le v_i\sum_{\ell=i}^{n-1}(Q_\ell-Q_{\ell+1})=v_i(Q_i-Q_n),\)
so each assigned utility is at least \(v_iQ_n>0\).
Set every unselected hospital’s waiting time to \(v_1q_{\max}\). Its utility for every support type is then nonpositive, so it cannot improve upon the assigned utility. The assignment is stable against all hospitals.
Its cost is
\(\displaystyle C=\sum_i\mu_iQ_i=\frac1D\sum_i a_iR^{n-i+1}+\frac1D\sum_i a_i\varepsilon_i h_i=\frac1D\sum_i a_iR^{n-i+1}+\sum_i\varepsilon_i s_i=b.\)
Writing \(u_i=v_iQ_i-w_i\), the waiting-time recursion gives
\(u_i-u_{i+1}=(v_i-v_{i+1})Q_i,\qquad u_n=v_nQ_n.\)
Therefore
\(\displaystyle W=u_n+\sum_{i<n}M_i(u_i-u_{i+1})=\sum_i\mu_iQ_i=C=b=K.\)
The constructed decision instance is a yes instance.
Conversely, suppose a feasible stable assignment satisfies \(W\ge K=b\). The welfare bound gives
\(b\le W\le\sum_i\mu_i r_i\le C\le b.\)
Every inequality is therefore an equality. Since all qualities are distinct, the equality condition forces each type to use exactly one hospital.
Let type \(k\) choose hospital \((j(k),\varepsilon_k)\), where \(\varepsilon_k\in\{0,1\}\). Since \(C=b\), multiplying the cost equality by \(D\) gives
\(\displaystyle \sum_{k=1}^{n}a_kR^{n-j(k)+1}+\sum_{k=1}^{n}a_k\varepsilon_k h_{j(k)}=\sum_{j=1}^{n}a_jR^{n-j+1}+DT.\)
Define
\(\displaystyle N_j=\sum_{\{k:j(k)=j\}}a_k,\qquad E=\sum_k a_k\varepsilon_k h_{j(k)}.\)
These coefficients obey
\(0\le N_j\le D<R,\qquad 0\le E\le D^2S<R,\qquad 0<DT<R.\)
Consequently, both sides of
\(\displaystyle \sum_jN_jR^{n-j+1}+E=\sum_j a_jR^{n-j+1}+DT\)
are valid base-\(R\) expansions with no carries between the displayed positions. Uniqueness of base-\(R\) representation implies
\(N_j=a_j\text{ for every }j,\qquad E=DT.\)
Since every \(a_j\) is positive, every hospital pair receives at least one type. There are \(n\) types and \(n\) pairs, so every pair receives exactly one type.
We also need to identify which type uses which pair. For any \(i<k\), stability of their chosen hospitals implies
\(v_iQ_i-w_i\ge v_iQ_k-w_k,\qquad v_kQ_k-w_k\ge v_kQ_i-w_i.\)
Adding yields
\((v_i-v_k)(Q_i-Q_k)\ge0.\)
Since \(v_i>v_k\), we have \(Q_i\ge Q_k\). Hospital pairs are strictly ordered by quality, and each pair is used exactly once. Thus the pair indices must occur in increasing order:
\(j(k)=k\quad\text{for every }k.\)
Finally,
\(\displaystyle DT=E=\sum_i a_i\varepsilon_i h_i=D\sum_i\varepsilon_i s_i.\)
Dividing by \(D\) gives
\(\sum_i\varepsilon_i s_i=T.\)
This is a subset-sum solution, completing the polynomial reduction and proving \(\mathrm{NP}\)-hardness.
The real-valued variables do not prevent polynomial-size certificates.
Let \(M=v_{\max}q_{\max}\). Any feasible stable assignment can be assumed to satisfy
\(0\le w_j\le M,\qquad 0\le u_t\le M,\qquad 0\le x_{tj}\le1.\)
Indeed, a used hospital has \(w_j\le v_tq_j\le M\) for some served type, by nonnegative utility. Set every unused hospital’s wait to \(M\); its utility for every type becomes nonpositive, preserving stability.
Guess a set \(F\) of allowed type–hospital pairs. Introduce variables \(x_{tj},w_j,u_t\), and impose the bounded linear system
\(x_{tj}=0\text{ for }(t,j)\notin F,\qquad x_{tj}\ge0,\qquad \sum_jx_{tj}=\mu_t,\)
\(\sum_{t,j}c_jx_{tj}\le b,\qquad 0\le w_j\le M,\qquad 0\le u_t\le M,\)
\(u_t\ge v_tq_j-w_j\text{ for all }t,j,\)
\(u_t=v_tq_j-w_j\text{ for }(t,j)\in F,\qquad \sum_t\mu_tu_t\ge K.\)
A real stable witness makes this system feasible when \(F\) is its positive-mass support. Conversely, any feasible point of the system defines a stable assignment: positive mass occurs only on pairs in \(F\), where utility equals the common maximum \(u_t\). Its welfare equals \(\sum_t\mu_tu_t\).
This is a bounded rational polyhedron with polynomially many variables and constraints and polynomial-size coefficients. If nonempty, it has a vertex with polynomial-size rational coordinates. Explicitly, a vertex is determined by linearly independent active constraints; after clearing denominators, Cramer’s rule and the determinant bound give polynomial bit length for its coordinates.
Thus every yes instance has a polynomial-size rational certificate, whose feasibility, stability, and welfare can be checked by exact rational arithmetic in polynomial time. The decision problem belongs to \(\mathrm{NP}\).
Combining membership with the reduction proves \(\mathrm{NP}\)-completeness. A general algorithm polynomial in \(m,\tau,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is established: the support-encoded continuous stable-assignment decision problem is \(\mathrm{NP}\)-complete. The reduction addresses arbitrary mass splitting and checks stability against unused hospitals. I found no substantive gaps or incorrect steps.
Every type has positive mass and must be served, so its minimum served quality \(r_i\) exists. Stability makes every positively used hospital attain the maximum utility \(u_i\). Thus both identities \(W=\sum_i\mu_i u_i\) and \(C=\sum_i\mu_i\bar q_i\) are valid when \(c_j=q_j\).
Comparing type \(i+1\) with a hospital of quality \(r_i\) serving type \(i\) correctly gives
\(u_i-u_{i+1}\le(v_i-v_{i+1})r_i\).
This comparison is permitted whether or not that hospital serves type \(i+1\).
At a hospital of quality \(r_n\) serving the last type, nonnegative waiting time gives \(u_n\le v_nr_n\). The telescoping identity uses \(M_n=1\) correctly. Substitution of the stated value–mass identities therefore proves
\(W\le\sum_i\mu_i r_i\le C\).
If \(W=C\), the intermediate quantity \(\sum_i\mu_i r_i\) must also equal \(C\). Hence
\(\sum_i\mu_i(\bar q_i-r_i)=0\).
Every summand is nonnegative, so every served-quality average equals its minimum.
This forces all hospitals receiving positive mass from a particular type to have the same quality. With distinct hospital qualities, there is exactly one such hospital. This argument applies to arbitrary real masses; it does not assume indivisibility.
The stated positive-integer subset-sum decision problem is a standard \(\mathrm{NP}\)-complete source problem. Restricting to \(n\ge2\) and \(0<T<S\) excludes only directly decidable cases and preserves hardness through the stated fixed-instance mapping. The incidental attribution to Chan and Chen is also accurate: their discrete reduction uses subset sum. [Chan and Chen, proof of Theorem 1](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p278.pdf)
The mass formulas satisfy \(\sum_i a_i=D\) and \(M_i=2^{i-1}/D\), including \(i=n\). All masses are positive dyadic rationals.
The values are positive and strictly decreasing. Their first difference is \(1\), and all subsequent differences are \(1/2\), exactly as claimed. Consequently, \(M_i(v_i-v_{i+1})=\mu_i\) for every \(i<n\), while \(v_n=\mu_n=1/2\).
The boundary case \(n=2\) satisfies all these formulas. Here the range of subsequent differences is empty, which causes no problem.
Each \(a_i\) divides \(D\), so every \(h_i\) is a positive integer. The bound \(h_i\le DS<R\) is valid.
Within each pair, the perturbed quality is strictly larger than the baseline. Between consecutive pairs, the displayed inequality correctly separates the entire lower pair from the higher pair. Thus all qualities are distinct and ordered as required.
The minimum cost is \(R\). The baseline weighted average is strictly greater than \(R\), since a positive mass receives a baseline quality exceeding \(R\). Adding \(T>0\) preserves this strict inequality.
For the upper budget bound, \(\mu_1\le1/2\) and all other baseline qualities are at most \(R^{n-1}\). The stated estimate for \(b\) follows. The inequalities used to show \(b<R^n\) hold under \(R>D^2S\), \(D\ge2\), and \(n\ge2\). Therefore the construction satisfies the task’s budget promise.
The bit-length bounds are polynomial in the subset-sum input length. Raising \(R\) to an exponent at most \(n\) increases binary length by a factor of at most \(n\); it does not require exponentially many output bits. The construction has \(m=2n\) hospitals and \(\tau=n\) support types.
The selected qualities are strictly decreasing. The waiting-time recursion therefore produces nonnegative waits.
Both pairwise utility-comparison identities have the correct signs. Their summands are nonnegative because the values and selected qualities are ordered. Together they check every type’s comparison between its assigned hospital and every other selected hospital.
The bound \(w_i\le v_i(Q_i-Q_n)\) correctly implies strictly positive assigned utility, including for the last type.
Giving every unselected hospital waiting time \(v_1q_{\max}\) makes its utility nonpositive for every support type. Since assigned utilities are strictly positive, unused hospitals cannot be profitable deviations. This verifies the task’s explicit requirement to include hospitals receiving no mass.
The cost calculation correctly uses \(a_ih_i=Ds_i\). The waiting-time recursion also gives the stated adjacent utility differences, so the welfare calculation establishes \(W=C=b=K\).
Feasibility and the welfare bound give
\(b\le W\le\sum_i\mu_i r_i\le C\le b\).
Thus all quantities coincide, and the equality condition forces each type to use one hospital.
After multiplying the cost equation by \(D\), all displayed base-\(R\) coefficients are integers. The bounds \(N_j\le D<R\), \(E\le D^2S<R\), and \(0<DT<R\) are valid. In particular, the offset term occupies only the units position, so it cannot carry into a hospital-pair position.
Uniqueness of base-\(R\) representation therefore gives \(N_j=a_j\) and \(E=DT\). Since every \(a_j>0\), every pair receives a type. With exactly \(n\) types and \(n\) pairs, each pair receives exactly one type.
Adding the two stability inequalities correctly yields
\((v_i-v_k)(Q_i-Q_k)\ge0\).
Strictly ordered values imply nonincreasing chosen qualities. Because the pairs are strictly ordered and each is used once, their indices must satisfy \(j(k)=k\).
Substituting this identification into \(E=DT\) gives precisely the required subset-sum solution. No assumption about distinct masses is needed.
The waiting-time normalization preserves stability: used hospitals already have waits at most \(M=v_{\max}q_{\max}\), while setting unused waits to \(M\) makes all their utilities nonpositive. Existing assigned utilities remain unchanged and nonnegative.
For a guessed set \(F\), the displayed system has exactly the required implications. Every type has some positive assigned mass, so at least one equality in \(F\) identifies \(u_t\) with an attained hospital utility. The inequalities against all hospitals then make it the actual maximum. Allowing some pairs in \(F\) to receive zero mass creates no false positive.
The system is bounded: the row equations and nonnegativity imply \(x_{tj}\le\mu_t\le1\), and the waits and utilities have explicit bounds. Its dimensions, number of constraints, and rational coefficient lengths are polynomial in \(m,\tau,L\).
The invoked rational-polyhedron vertex fact applies even when the feasible polyhedron has lower dimension. The active-constraint and determinant argument supplies polynomial-size rational coordinates. Exact rational verification of feasibility, stability, and welfare is consequently polynomial-time.
The proof establishes hardness for the exact continuous problem in the task, with its support representation and arbitrary splitting. Together with membership, it establishes \(\mathrm{NP}\)-completeness, even under the claimed restrictions \(c_j=q_j\) and \(K=b\).
It does not claim strong \(\mathrm{NP}\)-hardness or an unconditional separation from \(\mathrm{P}\). Its statement that a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\) is correct.
Required clarification or repair: none.
⟨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.