Answer: The first stated approximation factor remains NP-hard to attain; the second remains hard to attain under UGC.
Theorem 13 — class: hardness
Given finite resident and hospital type sets with positive rational masses \(\rho_i,\eta_j\), tied and incomplete rankings over types, mutual acceptability, and a common quota pair \(1\le\ell\le u\), find a maximum-score stable flow \(x_{ij}\ge0\). Require \(\sum_j x_{ij}\le\rho_i\), \(q_j=\sum_i x_{ij}\le u\eta_j\), and \(x_{ij}=0\) for unacceptable pairs; for each acceptable pair define \(D_{ij}=\rho_i-\sum_{j':j'\succeq_i j}x_{ij'}\) and \(A_{ij}=u\eta_j-q_j+\sum_{k:i\succ_j k}x_{kj}\), and require \(D_{ij}=0\) or \(A_{ij}=0\). Maximize \(\sum_j\eta_j\min\{1,q_j/(\ell\eta_j)\}\), with complexity measured in the type support and input bit length.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass encoded as a binary rational; \(\tau\) counts supported types, not possible types. Let there be \(r\ge1\) resident types and \(m\ge1\) hospital types, with \(\tau=r+m\), masses \(\rho_i,\eta_j>0\), and total input bit length \(L\). Masses are unnormalized population quantities.
Each type has a weak ranking of its acceptable opposite-side types; acceptability is mutual, lists may be incomplete, and every acceptable assignment is strictly preferred to being unmatched or leaving capacity vacant. Write \(\succeq_i\) for resident type \(i\)'s weak preference and \(\succ_j\) for hospital type \(j\)'s strict preference; ties are retained.
Common quotas are binary-encoded integers \(1\le\ell\le u\le\sum_i\rho_i\), with \(\theta=u/\ell\); hospital type \(j\) has capacity \(u\eta_j\) and soft lower quota \(\ell\eta_j\).
A feasible flow has \(x_{ij}\ge0\), \(\sum_jx_{ij}\le\rho_i\), \(q_j:=\sum_ix_{ij}\le u\eta_j\), and \(x_{ij}=0\) on unacceptable pairs. Resident mass may split among hospitals.
For every acceptable pair define \(D_{ij}:=\rho_i-\sum_{j':j'\succeq_i j}x_{ij'}\) and \(A_{ij}:=u\eta_j-q_j+\sum_{k:i\succ_j k}x_{kj}\). A flow is stable precisely when \(D_{ij}=0\) or \(A_{ij}=0\) for every acceptable pair.
The objective is to maximize \(S(x):=\sum_j\eta_j\min\{1,q_j/(\ell\eta_j)\}\) over stable flows.
For \(\varepsilon>0\), do approximation factors \(1+(2-\sqrt2)\theta/3-\varepsilon\theta^2>1\) remain NP-hard to attain, or are they attainable in polynomial time?
Likewise, under UGC, do factors \(1+\theta/3-\varepsilon\theta^2>1\) remain hard to attain, or are they attainable in polynomial time? Measure running times in \(m,\tau,L\), with dependence on \(\ell,u,\varepsilon\) explicit.
For discrete uniform-quota matching, these two inapproximability bounds hold under \(\mathrm{P}\ne\mathrm{NP}\) and UGC, respectively; a polynomial-time \(1+\theta/2\) approximation is known. [Source](https://arxiv.org/html/2203.06660)
For fractional ordinal stability with ties, maximizing welfare or the number of fully matched agents is NP-hard even in bipartite instances; these objectives differ from \(S\). [Source](https://www.ijcai.org/proceedings/2021/0013.pdf)
No result settling the stated approximation factors for this mass-weighted soft-quota objective was located.
Both inapproximability bounds remain valid. Divisible mass does not improve the optimum on the unit-mass instances used for the discrete hardness results.
The key is a rounding theorem: when resident masses, hospital capacities, and lower-quota thresholds are integers, every stable fractional flow can be converted in polynomial time into a stable integral flow with at least the same score.
Let \(E\) be the acceptable pairs. Write \(c_j=u\eta_j\), \(b_j=\ell\eta_j\), and \(d_i(x)=\sum_jx_{ij}\). The objective satisfies
\(\ell S(x)=\sum_j\min\{b_j,q_j(x)\}\).
Fix a stable flow \(x\). Define \(F_x\) to consist of feasible flows \(y\) satisfying:
This set is nonempty because it contains \(x\).
Lemma. Every flow in \(F_x\) is stable.
For an acceptable pair \((i,j)\), the resident deficit can be written as
\(D_{ij}(x)=\rho_i-d_i(x)+\sum_{h:\,j\succ_i h}x_{ih}\),
where \(\succ_i\) denotes the strict part of the resident’s weak ranking. Both terms are nonnegative. Consequently, \(D_{ij}(x)=0\) implies that \(d_i(x)=\rho_i\) and every assignment strictly worse than \(j\) has zero mass. The defining restrictions of \(F_x\) preserve both properties, so \(D_{ij}(y)=0\).
Likewise,
\(A_{ij}(x)=c_j-q_j(x)+\sum_{k:\,i\succ_j k}x_{kj}\).
Its terms are nonnegative. Thus \(A_{ij}(x)=0\) implies that hospital \(j\) is full and every assignment to a resident strictly worse than \(i\) has zero mass. These properties are also preserved in \(F_x\), giving \(A_{ij}(y)=0\).
Stability of \(x\) supplies at least one of these zero deficits for every acceptable pair. The same deficit remains zero in \(y\). This proves the lemma.
Assume now that all \(\rho_i\), \(c_j\), and \(b_j\) are integers. We optimize the score over \(F_x\) using a minimum-cost circulation.
Create nodes \(s,t\), one node for each resident type \(i\), and two nodes \(j,v_j\) for each hospital type. Put \(R=\sum_i\rho_i\). Use the following arcs; all unspecified costs are zero.
| Arc | Lower bound | Upper bound | Cost |
|---|---:|---:|---:|
| \(s\to i\) | \(\rho_i\) if \(d_i(x)=\rho_i\), otherwise \(0\) | \(\rho_i\) | \(0\) |
| \(i\to j\), only when \(x_{ij}>0\) | \(0\) | \(\rho_i\) | \(0\) |
| \(j\to v_j\) | \(c_j\) if \(q_j(x)=c_j\), otherwise \(0\) | \(c_j\) | \(0\) |
| First arc \(v_j\to t\) | \(0\) | \(b_j\) | \(-1\) |
| Second arc \(v_j\to t\) | \(0\) | \(c_j-b_j\) | \(0\) |
| \(t\to s\) | \(0\) | \(R\) | \(0\) |
The two \(v_j\to t\) arcs are parallel arcs. Their capacities are nonnegative because \(\ell\le u\).
For any \(y\in F_x\), assign flow \(y_{ij}\) to \(i\to j\). The other arc flows are determined by its row and column totals, except that the two outgoing hospital arcs receive respectively
\(\min\{b_j,q_j(y)\}\quad\text{and}\quad q_j(y)-\min\{b_j,q_j(y)\}\).
This produces a feasible circulation of cost \(-\ell S(y)\). In particular, the circulation problem is feasible.
Conversely, every feasible circulation defines a flow in \(F_x\) through its \(i\to j\) arc values. At an optimal circulation, the cost-\(-1\) hospital arc must carry \(\min\{b_j,q_j\}\): if its capacity were unused while the parallel cost-zero arc carried positive flow, transferring flow between them would strictly decrease the cost. Hence an optimal circulation has cost exactly \(-\ell S(y)\).
The circulation has integral lower and upper bounds. The network-flow integrality theorem therefore gives an integral optimal circulation. Its hypotheses hold here: the node-arc incidence matrix is totally unimodular, the bounds and node balances are integral, and the feasible polytope is nonempty and bounded. Thus an optimal vertex is integral.
Extract its resident-hospital flows \(y\). They are integral, belong to \(F_x\), and are stable by the preceding lemma. Comparing the optimal circulation with the circulation induced by \(x\) gives
\(-\ell S(y)\le-\ell S(x)\),
so \(S(y)\ge S(x)\).
This proves the rounding theorem. The essential integrality condition includes the thresholds \(b_j\), so the argument explicitly accounts for the objective’s truncation.
Take a discrete uniform-quota instance. Make each resident and each hospital a supported type of mass one:
\(\rho_i=1,\qquad\eta_j=1\).
Copy the preference lists, including ties and unacceptable pairs, and retain the common quotas \(\ell,u\). Then \(c_j=u\) and \(b_j=\ell\) are integers.
Integral feasible flows in this instance are precisely discrete matchings: each resident row has sum at most one, so its entries are zero or one.
For such a matching \(M\):
Thus the supplied stability equations coincide with discrete weak stability. The objectives also coincide:
\(S(M)=\sum_j\min\{1,|M(j)|/\ell\}\).
Every discrete stable matching is therefore a stable mass flow with the same score. Conversely, the rounding theorem converts every stable fractional flow into a discrete stable matching with at least its score. Consequently,
\(\operatorname{OPT}_{\mathrm{mass}}=\operatorname{OPT}_{\mathrm{discrete}}\)
on these embedded instances.
Moreover, this is an approximation-preserving conversion of solutions. If a mass algorithm returns \(x\) with \(S(x)\ge\operatorname{OPT}_{\mathrm{mass}}/\alpha\), rounding returns a discrete stable matching \(M\) satisfying
\(S(M)\ge S(x)\ge\operatorname{OPT}_{\mathrm{discrete}}/\alpha\).
The discrete result states that, for uniform quotas with \(\theta=u/\ell\), approximation within
\(\alpha_{\mathrm{NP}}=1+(2-\sqrt2)\theta/3-\varepsilon\theta^2\)
is NP-hard, and approximation within
\(\alpha_{\mathrm{UGC}}=1+\theta/3-\varepsilon\theta^2\)
is hard under UGC. Proposition 16 supplies the reduction for every fixed pair of positive integer quotas \(\ell\le u\). [Makino–Miyazaki–Yokoi, Theorem 13 and Proposition 16](https://arxiv.org/pdf/2203.06660v3).
If a polynomial-time mass algorithm attained either corresponding factor, apply it to the unit-mass embedding and then perform the polynomial-time rounding above. This would attain the same factor for the discrete problem, contradicting the corresponding hardness theorem.
Therefore, whenever the stated factor exceeds one:
Let \(B\) be the binary encoding length of a supplied rational flow \(x\). The rounding network has \(r+2m+2\) vertices and at most \(|E|+r+3m+1\) arcs, with \(|E|\le rm\). Support and saturation can be determined by exact rational arithmetic in polynomial time.
On the embedded instances, all capacities are at most \(\max\{r,u\}\), and costs belong to \(\{-1,0\}\). Standard exact minimum-cost circulation algorithms therefore make the conversion in time
\(\operatorname{poly}\bigl(rm+\tau,\ L+B+\log(u+1)+\log(\ell+1)\bigr)\).
It has no dependence on \(\varepsilon\) and requires no expansion into individual capacity slots.
The embedding adds only unit masses and copies the original supported agents and lists. In particular, \(\tau=r+m\) counts the listed types throughout. The cited graph construction has \(r=5uN/2\), \(m=(u+3/2)N\), and \(|E|=2u|F|+9uN/2\), where \(N\) and \(|F|\) are its graph sizes; hence it is polynomial for each fixed \(u\). [Appendix B.2](https://arxiv.org/pdf/2203.06660v3).
Because hardness holds for each fixed admissible \(\ell,u,\varepsilon\), it also excludes running times of the form \(f(\ell,u,\varepsilon)\operatorname{poly}(m,\tau,L)\), with polynomial degree independent of these parameters, under the respective assumptions.
⟨structured verdict parsed — rendered above⟩
The output resolves both approximation questions. The stability-preserving rounding argument is correct, the discrete embedding preserves the optimum and approximation guarantees, and the cited hardness results apply. I found no major or minor mathematical issues.
Since every hospital mass is positive and \(\ell>0\), the definitions \(b_j=\ell\eta_j\) give
\[
\ell\eta_j\min\{1,q_j/(\ell\eta_j)\}=\min\{b_j,q_j\}.
\]
Summing proves the claimed identity. This correctly retains the mass weights.
For an acceptable pair, the resident’s weak ranking partitions acceptable hospitals into those weakly preferred to \(j\) and those strictly worse. Unacceptable assignments have zero flow. Consequently, the displayed decomposition of \(D_{ij}(x)\) is correct.
Both its unmatched-mass term and its worse-assignment term are nonnegative. A zero deficit therefore forces a saturated resident row and zero flow on every strictly worse assignment. Both conditions persist throughout \(F_x\).
The same reasoning applies to \(A_{ij}(x)\): a zero value forces a full hospital column and zero flow from every strictly worse resident. These conditions also persist throughout \(F_x\).
Thus, for each acceptable pair, whichever zero deficit certifies stability of \(x\) also certifies stability of \(y\). This proves the lemma, including cases involving ties, incomplete lists, and partially unmatched residents.
All lower bounds are compatible with their upper bounds. In particular, \(c_j-b_j\ge0\).
The circulation induced by any \(y\in F_x\) satisfies conservation at every node. Its return-arc flow is the total assigned mass, which is at most \(R\). The second hospital-to-sink arc respects its capacity because
\[
q_j-\min\{b_j,q_j\}\le c_j-b_j.
\]
Conversely, conservation makes resident and hospital arc flows equal to the corresponding row and column totals. The bounds enforce feasibility and every defining restriction of \(F_x\). The correspondence is valid in both directions.
The parallel-arc exchange argument is correct: if the negative-cost arc has unused capacity while the zero-cost arc carries positive flow, a positive transfer preserves feasibility and decreases cost. Hence every optimal circulation has cost \(-\ell S(y)\).
The integrality theorem is applied with its hypotheses explicitly checked: integral bounds and balances, a totally unimodular incidence matrix, and a nonempty bounded feasible polytope. An integral optimal circulation therefore exists.
Comparing its cost with the circulation induced by \(x\) proves \(S(y)\ge S(x)\). Stability follows from the preceding lemma. The integer-threshold assumption is essential and is correctly included.
The existence statement applies to arbitrary fractional flows; the computational statement is interpreted with the rational encoding length \(B\) explicitly supplied in Section 5.
Unit resident masses force every integral resident row to contain at most one unit assignment. Unit hospital masses give exactly the original capacities, thresholds, and scores.
The two positive-deficit characterizations reproduce discrete weak blocking precisely: strict resident improvement together with either vacancy or strict hospital improvement. Ties introduce no mismatch.
Every discrete stable matching is therefore a stable mass flow. Conversely, every stable fractional flow rounds to a discrete stable matching of at least equal score. These two directions establish equality of optimal values and preserve the stated maximization approximation convention.
I checked the cited source. Theorem 13 states both claimed bounds, and Proposition 16 permits each fixed positive integer quota pair with \(\ell\le u\). The source’s mutual acceptability, incomplete lists, ties, weak stability, and soft-quota score match the embedded instance. Its construction also satisfies \(u\le r\), as required here. [Theorem 13 and Proposition 16](https://arxiv.org/pdf/2203.06660v3)
Thus a polynomial-time mass approximation attaining either requested factor would, through the written embedding and rounding, attain the forbidden discrete factor. The restriction to factors exceeding one correctly excludes vacuous parameter ranges.
The vertex and arc counts are correct. Exact support and saturation tests take polynomial time in the rational input length. Polynomial-time minimum-cost circulation algorithms operate on binary capacities, so the conversion requires no capacity-slot expansion.
The cited construction’s resident, hospital, and acceptable-pair counts agree with Appendix B.2. Its size is polynomial for fixed \(u\), which is sufficient for the fixed-parameter hardness claims. [Appendix B.2](https://arxiv.org/pdf/2203.06660v3)
Finally, fixing admissible \(\ell,u,\varepsilon\) makes the proposed parameter-dependent prefactor constant. Therefore a running time of the stated form would contradict the corresponding fixed-parameter hardness result. No dependence on \(\varepsilon\) is introduced by rounding.
No additional clarification or repair is needed to verify the conclusion.
⟨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.