Answer: $\mathrm{NP}$-complete
Theorem 4.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateChecking the existence of a strongly stable matching is NP-complete, even if all the supervisors have capacity one and each is responsible for at most two distinct projects.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses \(\mu_t\) over applicant types, type preferences, project priorities over types, project capacities, supervisor budgets, and the supervisor-project incidence structure, decide whether there are assignment masses \(x_{t,r}\) for \(r\in P\cup\{\bot\}\) and a feasible funding allocation such that no type \(t\) with positive mass at a source \(r\) has a preferred blocking project \(p\) for which all types assigned to \(p\) have at least as high a priority as \(t\), and some positive mass \(\varepsilon\leq x_{t,r}\) can move from \(r\) to \(p\) while preserving feasibility after funding is reallocated.
Let \(P\) be \(m\) projects and \(S\) supervisors, with incidence sets \(P_s\subseteq P\) covering \(P\). Capacities \(c_p\) and budgets \(q_s\) are nonnegative binary rationals; funding is divisible and costs one unit per unit of assigned mass.
A society is given by its support: the list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\). Here \(\tau\) is the support size, not the number of possible types; total mass is finite and need not equal \(1\). Each type strictly ranks its acceptable projects above being unmatched, denoted \(\bot\); each project strictly ranks its acceptable types, with equal priority within a type.
An assignment has real masses \(x_{t,r}\geq0\) for \(r\in P\cup\{\bot\}\), with \(\sum_r x_{t,r}=\mu_t\), and assigns mass only to mutually acceptable projects. Write \(z_p=\sum_t x_{t,p}\). Feasibility requires \(z_p\leq c_p\) and real funding \(y_{s,p}\geq0\) on incidences satisfying \(\sum_{s:p\in P_s}y_{s,p}=z_p\) and \(\sum_{p\in P_s}y_{s,p}\leq q_s\).
Call an assignment continuously strongly stable if, whenever \(x_{t,r}>0\) and a mutually acceptable project \(p\succ_t r\), both conditions hold: every \(u\) with \(x_{u,p}>0\) has priority at least as high as \(t\); and there is no real \(0<\varepsilon\leq x_{t,r}\) whose transfer from \(x_{t,r}\) to \(x_{t,p}\), keeping every other assignment entry fixed, remains feasible after funding is reallocated. Thus a preferred project holding lower-priority mass violates stability independently of transfer feasibility.
Is deciding whether a feasible continuously strongly stable assignment exists in \(\mathrm{P}\), with running time polynomial in \(m,\tau,|S|,L\), or is it \(\mathrm{NP}\)-hard, where \(L\) is the total input bit length?
For indivisible applicants, strongly stable existence is \(\mathrm{NP}\)-complete even when every supervisor has budget \(1\) and supervises at most two projects ([discrete result](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p97.pdf)). The extended treatment confirms this hardness and characterizes strong stability as fairness plus strong non-wastefulness ([extended result](https://link.springer.com/article/10.1007/s10107-022-01917-1)). No result settling the mass problem defined here was located.
The decision problem is $\mathrm{NP}$-complete, even when every type has mass $1$, every project has capacity $1$, every supervisor has budget $1$, and each project has exactly one supervisor, who supervises at most two projects.
The gap identified in the verifier’s report can be repaired: fairness permits mass to remain at the contested project, but its capacity then forces positive first-choice mass at the next project. Propagating this implication around the gadget gives a budget contradiction.
The proof below establishes both hardness and membership in $\mathrm{NP}$ for the stated model with real assignments and funding.
We use the following known $\mathrm{NP}$-complete problem: deciding whether a stable-marriage instance has a perfect weakly stable matching when one side has strict preferences and each participant on the other side either has strict preferences or accepts exactly two partners and ties them. Weak stability means that no acceptable pair strictly prefers each other to their assigned partners.
This restricted hardness is established in [McDermid’s thesis, Appendix A, Theorem A.0.1](https://theses.gla.ac.uk/2371/1/2010mcdermidphd.pdf). Its hardness construction has equally many participants on the two sides. Interchanging the sides if necessary, write them as
$$
U=\{u_1,\ldots,u_n\},\qquad W,\qquad |W|=n,
$$
where men have strict preferences, and women have either strict preferences or a single two-person tie. The additional bound of three on list lengths in the source theorem is compatible with everything below.
We use the construction supplied in the notes, adapted from [Aziz, Baychkov, and Biró, Theorem 4.4](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p97.pdf). Its correctness for divisible mass is proved independently below.
Every constructed type has mass $1$, every project has capacity $1$, and every supervisor has budget $1$. Each supervisor covers exactly the projects specified for it. Omitted pairs are unacceptable, and every acceptable project is preferred to $\bot$.
For each man $u_i$, create an external project $E_i$ with its own dedicated supervisor.
For each strictly ranking woman $w$, create a type $a_w$. Its preferences are obtained by replacing every man $u_i$ in her list by $E_i$.
Suppose $w$ ties exactly $u_{i_1}$ and $u_{i_2}$. Create four types and four internal projects with the following lists:
| Type | Preferences |
|---|---|
| $a_1^w$ | $H_2^w\succ H_1^w\succ E_{i_1}$ |
| $a_2^w$ | $H_3^w\succ H_2^w$ |
| $a_3^w$ | $H_4^w\succ H_3^w\succ E_{i_2}$ |
| $a_4^w$ | $H_1^w\succ H_4^w$ |
| Project | Priorities |
|---|---|
| $H_1^w$ | $a_1^w\succ a_4^w$ |
| $H_2^w$ | $a_2^w\succ a_1^w$ |
| $H_3^w$ | $a_3^w\succ a_2^w$ |
| $H_4^w$ | $a_4^w\succ a_3^w$ |
One supervisor covers $\{H_1^w,H_3^w\}$; two further supervisors cover $H_2^w$ and $H_4^w$ separately.
For every acceptable source pair $(w,u_i)$, define its representative type $e(w,i)$ as follows:
Project $E_i$ ranks these representatives in the strict order in which $u_i$ ranks their corresponding women.
Create types $v,b,c$ and projects $D_1,D_2$. A single supervisor covers $\{D_1,D_2\}$.
| Type | Preferences |
|---|---|
| $v$ | $E_1\succ E_2\succ\cdots\succ E_n\succ D_1$ |
| $b$ | $D_2\succ D_1$ |
| $c$ | $D_1\succ D_2$ |
| Project | Priorities |
|---|---|
| $D_1$ | $v\succ b\succ c$ |
| $D_2$ | $c\succ b$ |
Append $v$ last to every external project’s priority list.
If there are $k$ strict women and $h$ tied women, then $k+h=n$. The construction has
$$
n+4h+2
$$
projects,
$$
k+4h+3
$$
types, and
$$
n+3h+1
$$
supervisors. It therefore has polynomial size.
Because every project has exactly one supervisor, its funding is necessarily its load. Consequently, funding feasibility in this construction is precisely the requirement that each supervisor’s covered projects have total load at most $1$, together with the individual project capacities.
Lemma 1. In every continuously strongly stable assignment, each tied-woman gadget satisfies
$$
x_{a_2^w,H_2^w}=x_{a_4^w,H_4^w}=1,
\qquad
x_{a_1^w,H_1^w}+x_{a_3^w,H_3^w}=1.
$$
Moreover, all four first-choice entries are zero. Hence the gadget assigns at most one unit externally.
Proof. Suppress the superscript $w$ and read indices cyclically modulo $4$. Define
$$
f_i=x_{a_i,H_{i+1}},
\qquad
h_i=x_{a_i,H_i}.
$$
Suppose $f_i>0$. Project $H_{i+1}$ ranks $a_{i+1}$ above $a_i$. The fairness condition therefore prohibits $a_{i+1}$ from having positive mass at any destination strictly worse than $H_{i+1}$.
For $a_{i+1}$, the only acceptable project better than $H_{i+1}$ is $H_{i+2}$. Mass at $H_{i+1}$ itself remains permitted. Thus the justified conclusion is
$$
h_{i+1}+f_{i+1}=1.
$$
Capacity at $H_{i+1}$ gives
$$
h_{i+1}+f_i\leq1.
$$
Subtracting yields
$$
f_{i+1}\geq f_i>0.
$$
This implication propagates around the cycle. All four first-choice entries are positive, and the same fairness argument confines every type’s entire unit to its two internal projects. Hence the total internal load is $4$.
On the other hand, feasibility gives
$$
z_{H_1}+z_{H_3}\leq1,\qquad
z_{H_2}\leq1,\qquad
z_{H_4}\leq1.
$$
The total internal load is therefore at most $3$, a contradiction. Consequently,
$$
f_1=f_2=f_3=f_4=0.
$$
Type $a_2$ can now place mass only at $H_2$ or $\bot$. If $h_2<1$, it has positive unmatched mass, and $H_2$ has both capacity slack and dedicated-budget slack. A sufficiently small transfer from $\bot$ to $H_2$ is feasible, contradicting stability. Therefore $h_2=1$. The identical argument for $a_4$ gives $h_4=1$.
Write
$$
\alpha=h_1,\qquad \gamma=h_3.
$$
Their shared budget gives $\alpha+\gamma\leq1$. Suppose this inequality is strict. Since $\alpha<1$ and $f_1=0$, type $a_1$ has positive mass at some destination
$$
r\in\{E_{i_1},\bot\},
$$
both of which are worse than $H_1$.
Project $H_1$ has capacity slack $1-\alpha$, and its supervisor has budget slack $1-\alpha-\gamma$. Choose
$$
0<\varepsilon<
\min\{x_{a_1,r},\,1-\alpha,\,1-\alpha-\gamma\}.
$$
Transferring this amount from $r$ to $H_1$ respects those constraints. If $r$ is external, its load and funding decrease; if $r=\bot$, no other project load increases. The transfer is therefore feasible, contradicting stability.
Thus $\alpha+\gamma=1$. Exactly three units are assigned internally, out of the gadget’s four units. Its external mass is consequently at most one. $\square$
Lemma 2. Every continuously strongly stable assignment satisfies
$$
x_{v,D_1}=1,\qquad
x_{b,\bot}=x_{c,\bot}=1,
\qquad
z_{E_i}=1\quad\text{for every }i.
$$
Proof. Suppose $x_{b,D_2}>0$. Since $D_2$ ranks $c$ above $b$, fairness prohibits unmatched mass of $c$. Its entire unit must therefore lie in $\{D_1,D_2\}$. Together with the positive $b$-mass at $D_2$, this exceeds the detector’s shared budget $1$. Hence
$$
x_{b,D_2}=0.
$$
Likewise, if $x_{c,D_1}>0$, fairness prohibits unmatched mass of $b$, because $D_1$ ranks $b$ above $c$. The entire unit of $b$ would then lie in the detector region, again contradicting its budget. Thus
$$
x_{c,D_1}=0.
$$
Notice that these arguments confine the higher-priority type to the shared region; they do not assert that it occupies only one particular project.
Suppose next that $x_{b,D_1}>0$. Feasibility implies
$$
z_{D_2}\leq1-z_{D_1}<1.
$$
A sufficiently small transfer of $b$-mass from $D_1$ to its preferred $D_2$ respects both capacities and preserves total detector expenditure. It is feasible, contradicting stability. Therefore $x_{b,D_1}=0$.
The same argument, transferring $c$-mass from $D_2$ to its preferred $D_1$, shows $x_{c,D_2}=0$. Both $b$ and $c$ are entirely unmatched.
The detector’s only possible assigned mass is now $v$-mass at $D_1$. If $x_{v,D_1}<1$, a small transfer of unmatched $b$-mass to $D_1$ respects both its capacity and the shared budget. Therefore stability forces
$$
x_{v,D_1}=1.
$$
Since $v$ has unit mass, it has no external mass.
Finally, $v$ prefers every $E_i$ to $D_1$. If $z_{E_i}<1$, a small transfer from $D_1$ to $E_i$ is feasible: the external project has capacity and dedicated-budget slack, while detector expenditure decreases. Thus every $E_i$ is full. $\square$
Suppose a continuously strongly stable assignment exists. Define a matrix indexed by source women and men:
$$
F_{w,i}=x_{e(w,i),E_i}
$$
for acceptable pairs, and $F_{w,i}=0$ otherwise.
For a strict woman, the row sum is at most $1$ because her representative has unit mass. For a tied woman, Lemma 1 gives the same bound. Lemma 2 shows that every external project is full and receives no $v$-mass. Therefore
$$
\sum_wF_{w,i}=1
\quad\text{for every }i.
$$
There are $n$ rows, each with sum at most $1$, and the sum of all entries is $n$. Thus every row also has sum $1$.
Consider the bipartite graph consisting of the pairs with $F_{w,i}>0$. For any subset $B$ of women, let $N(B)$ be its neighboring men. Then
$$
|B|
=\sum_{w\in B}\sum_iF_{w,i}
\leq
\sum_{i\in N(B)}\sum_wF_{w,i}
=|N(B)|.
$$
Hall’s theorem applies to this finite bipartite graph and supplies a perfect matching $M$ using only positive entries.
We prove that $M$ is weakly stable. A tied woman is matched to one of her two equally ranked acceptable men, so she cannot strictly prefer another acceptable partner.
Suppose instead that a strict woman $w$ and man $u_i$ block $M$. Write
$$
M(w)=u_j,\qquad M(u_i)=w'.
$$
Since $M$ uses positive entries,
$$
x_{a_w,E_j}>0,\qquad
x_{e(w',i),E_i}>0.
$$
Woman $w$’s strict preference gives
$$
E_i\succ_{a_w}E_j.
$$
Man $u_i$’s strict preference means that $E_i$ ranks $a_w=e(w,i)$ above $e(w',i)$.
Thus $a_w$ has positive mass at a destination worse than $E_i$, while $E_i$ holds positive mass of a lower-priority type. This violates fairness, independently of transfer feasibility. No blocking pair exists.
A continuous solution therefore yields a perfect weakly stable source matching.
Conversely, let $M$ be a perfect weakly stable source matching.
For each strict woman $w$, assign the entire unit of $a_w$ to $E_i$, where $M(w)=u_i$.
For each tied woman $w$, use the following assignment:
| Source partner | Assignments |
|---|---|
| $u_{i_1}$ | $a_1^w$ to $E_{i_1}$; $a_2^w,a_3^w,a_4^w$ to $H_2^w,H_3^w,H_4^w$, respectively |
| $u_{i_2}$ | $a_3^w$ to $E_{i_2}$; $a_1^w,a_2^w,a_4^w$ to $H_1^w,H_2^w,H_4^w$, respectively |
Assign $v$ entirely to $D_1$, and leave $b,c$ entirely unmatched.
Every external project receives one unit. In each tied-woman gadget, $H_2^w$ and $H_4^w$ receive one unit each, and exactly one of $H_1^w,H_3^w$ receives one unit. The detector spends one unit at $D_1$. Thus the assignment is feasible.
We verify both stability conditions for every possible preferred destination.
Suppose a strict-woman type $a_w$ prefers $E_i$ to its assigned project. Let $w'=M(u_i)$. Weak stability of $M$ implies that $u_i$ does not prefer $w$ to $w'$. His preferences are strict, so he prefers $w'$ to $w$. Consequently, the occupant of $E_i$ outranks $a_w$.
The type $v$ is ranked below every external occupant. A tied-woman representative has only one acceptable external project and is either assigned there or assigned to an internal project it prefers.
These observations establish fairness at every relevant external destination. Every external project is full, which blocks any positive transfer into it.
Every occupied internal project holds its highest-priority acceptable type, so fairness holds.
A preferred target $H_2^w$ or $H_4^w$ is full. A preferred target in $\{H_1^w,H_3^w\}$ belongs to a region whose budget is exhausted.
Each type accepts at most one project in $\{H_1^w,H_3^w\}$. Consequently, any contemplated transfer into that pair originates outside it and increases expenditure in the exhausted region. Such a transfer is infeasible.
Project $D_1$ holds $v$, which outranks both $b$ and $c$, and $D_2$ is empty. Thus fairness holds for the unmatched types. Any transfer of their unmatched mass into either detector project exceeds the exhausted shared budget.
These cases exhaust all preferred destinations. The assignment is continuously strongly stable.
Together with Section 4, this proves the reduction equivalence and hence $\mathrm{NP}$-hardness under the stated unit restrictions.
Because assignments may be real, membership requires a polynomial-size rational certificate. We establish one without assuming integrality.
For $A\subseteq P$, define
$$
N(A)=\{s\in S:P_s\cap A\neq\varnothing\},
\qquad
Q(N(A))=\sum_{s\in N(A)}q_s,
\qquad
z(A)=\sum_{p\in A}z_p.
$$
Lemma 3. A nonnegative load vector $z$ admits feasible funding exactly when
$$
z(A)\leq Q(N(A))
\quad\text{for every }A\subseteq P.
$$
Proof. Necessity follows by summing the funding of projects in $A$: their funding comes only from supervisors in $N(A)$.
For sufficiency, set $Z=\sum_pz_p$ and construct a network with:
There is a cut of capacity $Z$, so a minimum cut cannot cross an incidence arc of capacity $Z+1$. If its source-side project set is $A$, all supervisors in $N(A)$ must also be on the source side. Their nonnegative budgets imply that its capacity is at least
$$
z(P\setminus A)+Q(N(A)).
$$
Conversely, putting exactly $A$ and $N(A)$ on the source side attains this expression. Therefore the minimum-cut value is
$$
\min_{A\subseteq P}
\bigl(z(P\setminus A)+Q(N(A))\bigr).
$$
The assumed inequalities make this value at least $Z$. By the max-flow/min-cut theorem for finite networks with nonnegative real capacities, a flow of value $Z$ exists. It saturates every source-to-project arc and gives the required funding. $\square$
Fix a feasible assignment, an entry $x_{t,r}>0$, and a mutually acceptable project $p\succ_t r$.
Lemma 4. No positive transfer from $x_{t,r}$ to $x_{t,p}$ is feasible exactly when at least one of the following holds:
$$
p\in A,\qquad r\notin A,\qquad z(A)=Q(N(A)),
$$
where $r\notin A$ is automatic for $r=\bot$.
Proof. A tight target capacity blocks any positive increase at $p$. A tight funding inequality with $p\in A$ and $r\notin A$ also blocks every positive transfer, because its left side increases by the transferred amount.
Conversely, suppose neither condition holds. The target capacity has positive slack. By Lemma 3, the funding inequalities whose left sides increase are exactly those sets containing $p$ but excluding $r$, and each has positive slack.
There are finitely many such sets. Choose $\varepsilon>0$ smaller than $x_{t,r}$, the target-capacity slack, and every increasing funding inequality’s slack. All other funding inequalities remain unchanged or decrease. Source nonnegativity is preserved, and the source-project capacity, if applicable, cannot be violated by a decrease.
The transferred assignment therefore satisfies all project capacities and all funding inequalities. Lemma 3 supplies funding after reallocation, proving feasibility. $\square$
If $\tau=0$, the zero assignment and zero funding are feasible and stable. Hence assume $\tau>0$ and that a real continuously strongly stable assignment exists.
Let $E$ be its assignment support, including unmatched entries. Since every type has positive mass, $E$ is nonempty.
For every triple $(t,r,p)$ with $(t,r)\in E$ and $p\succ_t r$, choose one blocking condition supplied by Lemma 4. There are at most
$$
\tau(m+1)m
$$
such triples. Each selected set $A$ can be encoded by an $m$-bit membership vector.
Consider the linear program with assignment variables $x$, funding variables $y$, and a variable $\delta$. Impose:
Maximize $\delta$.
The original real witness makes this system feasible with positive $\delta$: choose $\delta$ no larger than $1$ and the smallest positive assignment entry.
The feasible region is bounded. Every assignment entry is bounded by its type mass, every funding entry is bounded by its supervisor’s budget, and $\delta\leq1$. It is a nonempty closed polytope, so the optimum is attained at a vertex. Its optimal value is positive.
This linear program has polynomially many variables and constraints, and polynomial-bit rational coefficients. In particular, each selected right-hand side $Q(N(A))$ is a sum of input rationals and has polynomial bit length.
For completeness, let $D$ be its number of variables. Clearing denominators in each constraint produces integer coefficients of at most $B$ bits, where both $D$ and $B$ are polynomially bounded by the input parameters. A vertex is determined by $D$ linearly independent active constraints. Cramer’s rule expresses its coordinates as ratios of integer determinants. Hadamard’s inequality bounds the numerator and denominator bit lengths by
$$
O(DB+D\log D).
$$
Thus the optimal vertex has polynomial-size rational coordinates.
At this vertex, the assignment support is exactly $E$, because $\delta>0$. Fairness is preserved: it depends only on which assignment entries are positive and on the input preferences and priorities. All selected blocking equalities remain valid, so Lemma 4 blocks every relevant transfer. The rational assignment is therefore continuously strongly stable.
A certificate consists of this rational assignment, rational funding, and one selected blocking condition for every relevant triple. A verifier checks:
All these checks use polynomially many operations on polynomial-bit rationals. Every accepted certificate is sound by Lemma 4, and every real solution yields such a certificate. Hence the problem belongs to $\mathrm{NP}$.
The reduction proves $\mathrm{NP}$-hardness even with unit masses, capacities, and budgets and disjoint supervisor regions of size at most two. The rational-certificate argument proves membership in $\mathrm{NP}$ for the full model.
Thus the decision problem is $\mathrm{NP}$-complete. A running time polynomial in $m,\tau,|S|,L$ would imply $\mathrm{P}=\mathrm{NP}$.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated continuous problem. The reduction remains valid for real, divisible assignments, and the rational-certificate argument establishes membership in $\mathrm{NP}$. I found no major or minor mathematical issues.
1. Source problem and construction
The required source hardness is supported by [McDermid’s thesis, Appendix A, Theorem A.0.1](https://theses.gla.ac.uk/2371/1/2010mcdermidphd.pdf). The restricted problem asks for a complete weakly stable matching, with lists of length at most three, one side strict, and each participant on the other side either strict or accepting exactly two tied partners. Interchanging the sides preserves this decision problem. The source construction has equally many participants on both sides, as required.
The attribution to [Aziz, Baychkov, and Biró, Theorem 4.4](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p97.pdf) is also appropriate. Crucially, the prover supplies its own correctness argument for divisible mass rather than relying on the discrete theorem.
The constructed instance satisfies the target’s input requirements:
The counts
$$
m=n+4h+2,\qquad
\tau=k+4h+3,\qquad
|S|=n+3h+1
$$
are correct. Preference-list construction also has polynomial size. With a unique supervisor for each project, funding equals that project’s load, so the stated regional budget constraints characterize funding feasibility exactly.
2. Lemma 1: tied-woman gadget
The repaired propagation argument is correct.
If $f_i>0$, project $H_{i+1}$ contains positive mass of $a_i$, which has lower priority than $a_{i+1}$. Fairness therefore excludes every destination of $a_{i+1}$ strictly worse than $H_{i+1}$. Its only remaining destinations are its own project and its first choice, giving
$$
h_{i+1}+f_{i+1}=1.
$$
This conclusion correctly permits mass at the contested project itself.
Capacity gives
$$
h_{i+1}+f_i\leq1.
$$
Combining these equations yields
$$
f_{i+1}\geq f_i>0.
$$
Propagation applies to all four cyclic indices. Consequently, every type’s full unit lies internally, giving total internal load $4$. The three supervisor budgets permit total internal load at most $3$. This contradiction establishes that every $f_i$ vanishes.
Once those entries vanish, $a_2$ can occupy only $H_2$ or $\bot$, and $a_4$ only $H_4$ or $\bot$. Any deficit at either project supplies both positive unmatched source mass and positive capacity and dedicated-budget slack. The stated transfers therefore establish
$$
h_2=h_4=1.
$$
For the shared region, feasibility gives $\alpha+\gamma\leq1$. Under strict inequality, $a_1$ has positive mass at an external destination or at $\bot$. Every quantity in the displayed minimum is positive. The proposed transfer increases only the shared region’s expenditure and decreases external expenditure when applicable, so it is feasible. Thus
$$
\alpha+\gamma=1.
$$
Exactly three units are internal. The conclusion that external mass is at most one is correct; the proof does not incorrectly assume the remaining unit is externally assigned.
3. Lemma 2: detector
Each detector argument is valid for fractional mass.
Positive $b$-mass at $D_2$ excludes unmatched $c$-mass by fairness. Since $c$ accepts only detector projects, its entire unit must then occupy the detector region. Together with the positive $b$-mass, this exceeds budget $1$.
Similarly, positive $c$-mass at $D_1$ excludes unmatched $b$-mass and forces a budget violation. These arguments allow the higher-priority type to split between detector projects, which is essential for their validity in the continuous model.
If $b$ occupies $D_1$, the shared budget implies $z_{D_2}<1$. Moving a sufficiently small amount to its preferred $D_2$ preserves regional expenditure and respects capacities. The analogous transfer eliminates $c$-mass at $D_2$. Hence both types are entirely unmatched.
The only remaining detector occupant can be $v$ at $D_1$. If its load were below $1$, unmatched $b$-mass could enter $D_1$, violating the transfer condition. Therefore $v$ occupies $D_1$ with its entire unit.
Finally, every external project is preferred by $v$. Any external load below $1$ would permit a transfer from $D_1$ into that project, using its dedicated capacity and budget slack. External fullness follows.
4. Extraction of a perfect weakly stable matching
The matrix $F$ is nonnegative and supported on acceptable source pairs. Strict-woman row sums are at most $1$ by their type masses; tied-woman row sums are at most $1$ by Lemma 1.
Lemma 2 gives column sums exactly $1$, with no contribution from $v$. Since there are $n$ rows and $n$ columns, every row sum must also equal $1$.
The displayed neighborhood calculation verifies Hall’s condition for every subset of women. The graph is finite, bipartite, and balanced, so Hall’s theorem supplies a perfect matching using positive entries.
The weak-stability argument also checks out:
That configuration directly violates the target’s fairness condition. No assumption about transfer feasibility or integrality enters this extraction.
5. Construction from a source matching
The proposed assignment satisfies all type-mass, capacity, acceptability, and budget constraints.
The stability verification covers every relevant destination:
Thus both directions of the reduction are established under the exact continuous stability definition.
6. Lemma 3: funding feasibility
Necessity of the subset inequalities follows from the incidence restrictions and supervisor budgets.
For sufficiency, the network argument is correct. The source-only cut has capacity $Z$, whereas each incidence arc has capacity $Z+1$. Therefore a minimum cut crosses no incidence arc.
For a source-side project set $A$, all supervisors in $N(A)$ must be source-side. Nonnegative budgets give the stated lower bound, and choosing exactly those projects and supervisors attains it. The resulting minimum-cut formula is correct.
The max-flow/min-cut theorem applies to the finite network with nonnegative real capacities. A flow of value $Z$ saturates every source-to-project arc and supplies the required funding. This reasoning also covers $Z=0$.
7. Lemma 4: blocked transfers
Both sufficient blocking conditions are correct.
Conversely, a transfer increases a funding inequality precisely when its set contains $p$ and excludes the source project $r$, with exclusion automatic for $\bot$. If no such inequality is tight, each increasing inequality has positive slack.
Although there can be exponentially many inequalities, there are finitely many for the fixed instance. Their number therefore creates no obstacle to choosing a positive transfer amount smaller than every relevant slack. This is an existence argument, not a claim to enumerate them efficiently.
The chosen transfer preserves nonnegativity, all type totals, acceptability, capacities, and every funding inequality. Lemma 3 then supplies reallocated funding. The characterization is exact.
8. Rational certificates and membership in $\mathrm{NP}$
The support-preserving linear program is valid. A real stable witness satisfies its selected blocking equalities and gives a positive feasible value of $\delta$.
Its feasible region is closed and bounded: assignment entries are bounded by type masses, funding entries by supervisor budgets, and $\delta$ by $1$. Consequently, an optimal vertex exists, with positive optimal $\delta$.
The numbers of variables, constraints, selected triples, and encoded subset memberships are polynomial. Sums of input rational budgets have polynomial bit length. Clearing denominators therefore produces polynomial-bit integer coefficients.
The vertex-coordinate argument using independent active constraints, Cramer’s rule, and Hadamard’s inequality correctly gives the stated polynomial bit bound. It does not require the polytope to be full-dimensional.
At the selected vertex, positive $\delta$ preserves exactly the original assignment support. Fairness consequently remains valid, and the selected equalities block every relevant transfer by Lemma 4.
The certificate verifier checks all necessary conditions using polynomially many operations on polynomial-bit rationals. The explicit case $\tau=0$ is correct. Zero capacities, zero budgets, arbitrary positive rational masses, and unmatched entries introduce no omitted exception.
Adjudication and feedback
The output establishes $\mathrm{NP}$-completeness for the full continuous model and hardness under the advertised unit restrictions. No additional mathematical clarification or repair 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.