Answer: —
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor any problem with B-common priority, there exists a feasible, fair and non-wasteful assignment. 3.3 Efficiency of DAPL In this subsection, we examine the efficiency of DAPL. In special cases where constraints are not type-specific, i.e., |T| = 1, we can show that there is no stable assignment that Pareto dominates the outcome of DAPL.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of types with rational masses \(\mu_t\u005c), school preferences, priority tiers, capacities \(\kappa_c\u005c), and category floors and ceilings \(\ell_{gc},u_{gc}\u005c), with schools agreeing on the same bottom priority-mass segments required by the mass analogue of B-common priority, find a feasible assignment \(x_{tc})\u005c) if one exists. Feasibility requires \(\sum_c x_{tc}=\mu_t\u005c), \(\sum_t x_{tc}\leq\kappa_c\u005c), and \(\ell_{gc}\leq\sum_{t:g(t)=g}x_{tc}\leq u_{gc}\u005c); stability means no positive feasible mass move into a preferred school can either use an available slot or displace lower-priority mass there.
A society is given by its support: a list of \(\tau\) 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 specifies a category \(g(t)\in G\), a strict preference order over \(m\ge2\) schools, and a priority tier at each school; all schools are acceptable. Write \(k=|G|\) and let \(L\) be the total input bit length. Priority ties do not justify displacement.
Capacities and quotas are nonnegative binary rationals satisfying \(0\le\ell_{gc}\le u_{gc}\le\kappa_c\), \(\sum_g\ell_{gc}\le\kappa_c\le\sum_g u_{gc}\), and \(\sum_c\kappa_c\ge1\). For \(M_g=\sum_{t:g(t)=g}\mu_t\), assume \(\sum_c\ell_{gc}<M_g<\sum_c u_{gc}\) for every category.
Let \(F\ne\varnothing\) be the set of real matrices \(x\ge0\) satisfying \(\sum_c x_{tc}=\mu_t\), \(\sum_t x_{tc}\le\kappa_c\), and \(\ell_{gc}\le\sum_{t:g(t)=g}x_{tc}\le u_{gc}\). For \(A\subseteq C\), let \(F(A,g)\) consist of the matrices in \(F\) attaining category \(g\)'s floor at every school in \(A\).
Define \(Q_g(c,c')=\max\{\sum_{d\in A}\ell_{gd}:A\subseteq C\setminus\{c,c'\},\ F(A,g)\ne\varnothing\}\) and \(Q_g(c)=\max_{c'\ne c}Q_g(c,c')\).
For any tier order \(R\) on category \(g\)'s support, define its bottom-mass vector \(B_g(R,a)\) by filling tiers from lowest priority upward until mass \(a\) is reached; within a partially filled tier, include the same fraction of every type's mass. The promised mass B-common priority condition is that, for every \(g\), some reference tier order \(R_g\) satisfies \(B_g(\succ_c,a)=B_g(R_g,a)\) for every school \(c\) and every real \(0\le a\le Q_g(c)\), where \(\succ_c\) is restricted to category \(g\).
A feasible assignment is stable if no type \(t\) with \(x_{ta}>0\) strictly prefers a school \(c\) to \(a\) and admits either of these feasible changes for some \(\varepsilon>0\): move \(\varepsilon\) mass of \(t\) from \(a\) to \(c\); or simultaneously move \(\varepsilon\) mass of \(t\) from \(a\) to \(c\) and \(\varepsilon\) mass of a strictly lower-priority type \(s\) from \(c\) to some school \(d\ne c\). All other entries remain unchanged; displaced mass need not prefer \(d\), and \(d=a\) is allowed.
Is finding a feasible stable assignment, or deciding that none exists, on this promised domain solvable in polynomial time in \(m,\tau,k,L\), or is this computational problem NP-hard?
For finite students with strict priorities, B-common priority guarantees a feasible, fair and non-wasteful assignment, constructed by Deferred Acceptance with Precedence Lists. [Tomoeda (2018)](https://www.sciencedirect.com/science/article/pii/S0022053118300917)
No result settling the computational problem with exactly the mass condition and stability moves above was identified in the literature search.
The general polynomial-time-versus-$\mathrm{NP}$-hard classification remains unresolved here.
The main new result is an exact algorithm with running time
$$
2^{m+2km}\prod_{g\in G}(\tau_g+1)^m
\operatorname{poly}(m,\tau,k,L),
$$
where $\tau_g$ is the number of support types in category $g$. It works without the B-common priority promise. In particular, the problem is polynomial-time solvable when both $m$ and $k$ are fixed, with arbitrary support size and binary rational masses.
The algorithm follows from an exact characterization of stability using only binding aggregate constraints and the lowest occupied priority tier in each category-school pair. I also give a self-contained proof of existence on the promised domain.
For a feasible assignment $x$, write
$$
z_{gc}(x)=\sum_{t:g(t)=g}x_{tc},
\qquad
y_c(x)=\sum_t x_{tc}.
$$
Define the sets of schools at which the relevant constraints have strict slack:
$$
D_g(x)=\{c:z_{gc}(x)>\ell_{gc}\},
$$
$$
U_g(x)=\{c:z_{gc}(x)<u_{gc}\},
\qquad
V(x)=\{c:y_c(x)<\kappa_c\}.
$$
Thus $D_g$ records slack above category floors, $U_g$ records slack below category ceilings, and $V$ records slack below school capacities.
At school $c$, number the priority tiers from highest to lowest, and let $p_c(t)$ be type $t$'s tier number. Consequently,
$$
t\succ_c s
\quad\Longleftrightarrow\quad
p_c(t)<p_c(s).
$$
Lemma 1. Suppose $x_{ta}>0$ and type $t$ strictly prefers $c$ to $a$. Put $g=g(t)$.
$$ a\in D_g,\qquad c\in U_g,\qquad c\in V. $$
$$
a\in D_g,\qquad c\in U_g,\qquad c\in D_h,
$$
and
$$
a\in U_h
\quad\text{or}\quad
(U_h\cap V)\setminus\{a,c\}\ne\varnothing.
$$
Proof. A direct move decreases $z_{ga}$ and increases both $z_{gc}$ and $y_c$. These are its only changes toward violation of aggregate constraints. Necessity follows immediately. For sufficiency, choose the move size smaller than the donor entry and all three positive slacks.
For the second assertion, the exchange preserves every row total, school total, and category-school total. A move size at most $\min(x_{ta},x_{sc})$ is therefore feasible.
For the third assertion, first fix $d$.
If $d=a$, the changes to category totals are
$$
z_{ga}\mapsto z_{ga}-\varepsilon,\qquad
z_{gc}\mapsto z_{gc}+\varepsilon,
$$
$$
z_{hc}\mapsto z_{hc}-\varepsilon,\qquad
z_{ha}\mapsto z_{ha}+\varepsilon.
$$
All school totals remain unchanged. Thus the required aggregate slacks are precisely
$$
a\in D_g,\qquad c\in U_g,\qquad c\in D_h,\qquad a\in U_h.
$$
If $d\notin\{a,c\}$, the category changes instead require
$$
a\in D_g,\qquad c\in U_g,\qquad c\in D_h,\qquad d\in U_h.
$$
The school total at $a$ decreases, the total at $c$ is unchanged, and the total at $d$ increases. Hence one additionally needs $d\in V$.
In both cases, necessity follows from the constraints that move toward violation. Sufficiency follows by choosing $\varepsilon>0$ no larger than both donor entries and every relevant positive slack. Taking the disjunction over possible $d$ proves the assertion. $\square$
This lemma uses the task's precise displacement rule: the displaced mass need not prefer its destination, and returning it to $a$ is permitted.
For each category-school pair define
$$
w_{gc}(x)=
\begin{cases}
0,&z_{gc}(x)=0,\\
\max\{p_c(s):g(s)=g,\ x_{sc}>0\},&z_{gc}(x)>0.
\end{cases}
$$
Thus a positive $w_{gc}$ is the tier number of the lowest-priority category-$g$ mass assigned to $c$.
Because tier numbers increase downward,
$$
\exists s:\ g(s)=h,\ x_{sc}>0,\ t\succ_c s
\quad\Longleftrightarrow\quad
w_{hc}(x)>p_c(t).
$$
Indeed, the forward implication follows from the definition of the maximum. For the reverse implication, some positive assigned entry attains that maximum.
Given sets $D_g,U_g,V$ and cutoffs $w_{gc}$, call an entry $(t,a)$ forbidden if there is a school $c$ strictly preferred by $t$ to $a$ for which at least one of the following holds, with $g=g(t)$:
$$ a\in D_g,\qquad c\in U_g\cap V. $$
$$ w_{gc}>p_c(t). $$
$$
w_{hc}>p_c(t),\qquad
a\in D_g,\qquad c\in U_g\cap D_h,
$$
and
$$
a\in U_h
\quad\text{or}\quad
(U_h\cap V)\setminus\{a,c\}\ne\varnothing.
$$
Proposition 2. A feasible assignment $x$ is stable if and only if
$$
x_{ta}=0
$$
for every entry forbidden by its own sets $D_g(x),U_g(x),V(x)$ and cutoffs $w_{gc}(x)$.
Proof. Suppose a forbidden entry has positive mass.
The direct-move condition gives a blocking move by Lemma 1. In the within-category case, the cutoff supplies a strictly lower-priority donor at $c$, and Lemma 1 supplies a feasible exchange. In the across-category case, the cutoff again supplies a strictly lower-priority donor, while Lemma 1 supplies a feasible destination for that donor. Each case contradicts stability.
Conversely, suppose $x$ has a blocking move. A direct move makes its donor entry forbidden by Lemma 1. For a displacement, let $h$ be the displaced type's category. Its strict priority comparison implies
$$
w_{hc}(x)>p_c(t).
$$
If $h=g(t)$, the within-category condition applies. Otherwise Lemma 1 gives exactly the additional conditions in the across-category rule. Thus the positive donor entry is forbidden. $\square$
The characterization handles priority ties exactly: the inequality between tier numbers is strict.
I use the standard rational linear-programming theorem: feasibility and optimization for a linear program with rational coefficients can be performed in time polynomial in its dimensions and total binary encoding length. For a feasible program with an attained finite optimum, a rational optimizer of polynomial encoding length can be returned.
The algorithm enumerates the following data:
$$ w_{gc}\in\{0\}\cup\{p_c(t):g(t)=g\}. $$
For a fixed choice, compute its forbidden entries using Section 2. Their computation takes polynomial time.
Now introduce assignment variables $x$ and one additional variable $\delta$, and maximize $\delta$ subject to the following linear constraints.
First impose feasibility and bound the additional variable:
$$
x\in F,\qquad 0\le\delta\le1.
$$
Require the selected slack sets to be realized:
$$
z_{gc}\ge\ell_{gc}+\delta
\quad\text{if }c\in D_g,
\qquad
z_{gc}=\ell_{gc}
\quad\text{if }c\notin D_g,
$$
$$
z_{gc}\le u_{gc}-\delta
\quad\text{if }c\in U_g,
\qquad
z_{gc}=u_{gc}
\quad\text{if }c\notin U_g,
$$
$$
y_c\le\kappa_c-\delta
\quad\text{if }c\in V,
\qquad
y_c=\kappa_c
\quad\text{if }c\notin V.
$$
Require the selected cutoffs to be realized. If $w_{gc}=0$, impose
$$
x_{sc}=0\qquad\text{for every }s\text{ with }g(s)=g.
$$
If $w_{gc}>0$, impose
$$
x_{sc}=0
\qquad\text{whenever }g(s)=g\text{ and }p_c(s)>w_{gc},
$$
and
$$
\sum_{\substack{s:g(s)=g\\p_c(s)=w_{gc}}}x_{sc}\ge\delta.
$$
Finally, impose
$$
x_{ta}=0
\qquad\text{for every forbidden entry }(t,a).
$$
Accept a case precisely when its optimum satisfies $\delta>0$, and return its assignment $x$. If every case fails, report that no stable assignment exists.
Theorem 3. This algorithm is correct, whether or not B-common priority holds.
Proof. Suppose a case has a feasible solution with $\delta>0$.
The aggregate constraints ensure that its selected slack sets are exactly $D_g(x),U_g(x),V(x)$. If $w_{gc}=0$, the category-school pair is empty. If $w_{gc}>0$, there is positive mass in the selected tier and no mass in a lower-priority tier. Thus its selected cutoff is exactly $w_{gc}(x)$.
All forbidden entries are zero. Proposition 2 therefore proves stability.
For the converse, suppose a real stable assignment $x$ exists. Enumerate its actual slack sets and actual cutoffs. By Proposition 2, every forbidden entry is zero.
Every selected aggregate slack is strictly positive. Every nonempty selected cutoff tier also has strictly positive assigned mass. There are finitely many such quantities. Choose $\delta$ to be the minimum of $1$ and these positive quantities; if the collection is empty, choose $\delta=1$. Then $\delta>0$, and $(x,\delta)$ satisfies the case's linear program.
Consequently, some enumerated case has positive optimum whenever a stable assignment exists. This proves both successful construction and correct nonexistence reporting. $\square$
There are at most
$$
2^{m+2km}
$$
choices of slack sets. Each $(g,c)$ has at most $\tau_g+1$ cutoff choices. Hence the number of cases is at most
$$
2^{m+2km}\prod_g(\tau_g+1)^m.
$$
Each linear program has polynomially many variables and constraints, with coefficients of polynomial encoding length. The assignment variables are bounded by their row masses, and $\delta$ is bounded by $1$, so any feasible program has an attained finite optimum.
This establishes the claimed running time. For fixed $m,k$, it is polynomial in $\tau,L$. The exponent depends on $km$, so this does not establish the requested polynomial bound when $m$ and $k$ vary.
The characterization also proves two useful facts independently of the promise.
Corollary 4. Feasibility and stability of a rational assignment can be verified in polynomial time in the input and assignment encoding lengths.
Proof. Check the defining constraints of $F$ using exact rational arithmetic. Compute all aggregate totals, slack sets, and occupied cutoffs. Then compute the forbidden entries and check that they are zero. Proposition 2 proves that this test is exact. All loops range over polynomially many types, schools, and categories. $\square$
Corollary 5. If a real stable assignment exists, a rational stable assignment of polynomial encoding length exists. Therefore the existence decision problem without the B-common promise belongs to $\mathrm{NP}$.
Proof. The completeness proof of Theorem 3 supplies an enumerated linear program with positive optimum. The rational linear-programming theorem supplies a rational optimizer of polynomial encoding length. The soundness proof makes its assignment stable.
Corollary 4 supplies polynomial-time verification of this certificate. $\square$
This rational-certificate argument does not expand the society into individual students.
For completeness, I reprove the existence result used to interpret the promised search problem.
Let $D$ be the product of the denominators of all input masses, capacities, and quotas. Then
$$
\log_2 D=O(L),
\qquad
n_t=D\mu_t\in\mathbb Z_{>0},
\qquad
\sum_t n_t=D.
$$
Scaled feasibility has a bounded-circulation representation. Use a source $p$, type nodes $t$, category-school nodes $v_{gc}$, school nodes $c$, and a sink $z$. The arcs and bounds are:
Conservation gives exactly the scaled assignment constraints, with
$$
f(t,v_{g(t)c})=Dx_{tc}.
$$
The integral-circulation theorem says that integral arc bounds admit an integral feasible circulation whenever they admit a real feasible circulation. Its hypotheses hold here. The theorem also applies after fixing any selected category-school arcs at their integral lower bounds. Consequently,
$$
F(A,g)\ne\varnothing
$$
if and only if it contains an assignment on the grid $D^{-1}\mathbb Z$.
Replace type $t$ by $n_t$ distinct cloned students. Integral scaled assignments correspond exactly to assignments of these clones, including assignments attaining any specified category floors.
We need the following property of bottom-mass vectors.
Lemma 6. Let $R,S$ be tier orders on the same positive-mass support. If
$$
B(R,a)=B(S,a)\qquad\text{for every }a\in[0,q],
$$
where $q>0$, then their tiers agree from the bottom through every tier whose starting cumulative mass is strictly below $q$.
Proof. For sufficiently small positive $a$, the positive coordinates of $B(R,a)$ identify exactly its bottom tier. Equality identifies the same tier in $S$, with the same total mass.
Suppose identical bottom tiers of cumulative mass $b<q$ have already been identified. For sufficiently small $h>0$, the positive coordinates of
$$
B(R,b+h)-B(R,b)
$$
identify the next tier. Equality identifies that same tier in $S$. Induction proves the claim, including an entire tier when $q$ lies inside it. $\square$
Fix one total order $H$ of all clones. Refine every school priority tie using $H$. Expand each promised reference order $R_g$ into clones and refine its ties using the same $H$.
For school $c$, Lemma 6 shows that its category-$g$ bottom tiers agree with the reference through mass $Q_g(c)$. Their refined orders therefore have identical bottom-student sets for every integer
$$
0\le K\le DQ_g(c).
$$
For a zero threshold, only the empty set is required.
The floor-feasibility equivalence above gives
$$
Q_g^{\mathrm{fin}}(c,c')=DQ_g(c,c'),
\qquad
Q_g^{\mathrm{fin}}(c)=DQ_g(c).
$$
Thus the cloned finite instance satisfies finite B-common priority.
The finite theorem guarantees a feasible, fair, non-wasteful assignment under this condition. Its fairness definitions exclude same-category justified envy and feasible two-student displacements across categories; non-wastefulness excludes feasible preferred direct moves. [Tomoeda, Definitions 1–5 and Theorem 2](https://opus.lib.uts.edu.au/rest/bitstreams/4b42dc45-2e98-4a7b-92b0-b66de649dea2/retrieve)
All required hypotheses hold: priorities are now strict, preferences remain strict, all schools are acceptable, feasibility and the school quota inequalities are preserved, and the category inequalities become
$$
\sum_c D\ell_{gc}<DM_g<\sum_c Du_{gc}.
$$
Aggregate the finite assignment and divide by $D$, obtaining $x\in F$.
Suppose a permitted mass move with direction $h$ is feasible for some positive size. Every assignment entry and every aggregate constraint slack at $x$ is a multiple of $D^{-1}$.
For either permitted move, the coefficient of each entry, school total, and category-school total in $h$ belongs to $\{-1,0,1\}$. Indeed, the moving and displaced types are distinct, the moving type's source differs from its destination, and the displaced type's destination differs from its source. Overlap at aggregate constraints only causes cancellation.
Any constraint moving toward violation must therefore have positive slack, hence slack at least $D^{-1}$. The positive donor entries likewise have size at least $D^{-1}$. It follows that
$$
x+D^{-1}h\in F.
$$
This step can be realized by one moving clone and, for a displacement, one displaced clone. Original strict priority comparisons survive the refinement.
A direct move contradicts finite non-wastefulness. A displacement across categories contradicts finite fairness. For a displacement within one category, exchanging the two clones' schools preserves all aggregate constraints and gives the same justified envy, contradicting finite same-category fairness.
Thus $x$ is stable.
Conclusion. Every instance in the promised domain has a feasible stable assignment. The decision whether one exists is consequently trivial on that domain; the intended computational question is construction. The cloning proof does not yield a polynomial construction because the numerical value of $D$ can be exponential in $L$.
There is also a structural restriction on the thresholds that may help future constructions.
Fix a category $g$ and put
$$
q_g=\max_c Q_g(c).
$$
Proposition 7. For every school $c$,
$$
\max\{0,q_g-\ell_{gc}\}\le Q_g(c)\le q_g.
$$
In particular, if $\ell_{gc}=0$, then $Q_g(c)=q_g$.
Proof. Choose distinct schools $a,b$ and a feasible floor set
$$
A\subseteq C\setminus\{a,b\}
$$
attaining $q_g$. Such a choice exists because all maximizations are over finite nonempty collections.
Set $A'=A\setminus\{c\}$. Removing a floor equality preserves feasibility, so $F(A',g)\ne\varnothing$. The set $A'$ excludes $c$ and at least one of $a,b$ distinct from $c$. It is therefore admissible for one of the pairwise thresholds defining $Q_g(c)$.
Moreover,
$$
\sum_{d\in A'}\ell_{gd}
=
q_g-\mathbf 1_{\{c\in A\}}\ell_{gc}
\ge q_g-\ell_{gc}.
$$
This proves the lower bound; nonnegativity and the definition of $q_g$ give the remaining bounds. $\square$
Corollary 8. On a promised instance, any school's category-$g$ tier order attaining $q_g$ can serve as the reference order. In particular, any school with $\ell_{gc}=0$ can serve as that reference.
Proof. Let $c_0$ attain $q_g$, and let $R_g$ be a promised reference. For any school $c$ and any $a\le Q_g(c)$, we have $a\le q_g$, so
$$
B_g(\succ_c,a)=B_g(R_g,a)=B_g(\succ_{c_0},a).
$$
Thus $\succ_{c_0}$ satisfies every required reference equality. The zero-floor assertion follows from Proposition 7. $\square$
Hence, when every category has a zero-floor school, valid references can be selected directly in polynomial time. This does not by itself prove a polynomial stable-assignment construction.
The proved algorithm replaces enumeration over assignment faces with enumeration over aggregate slack sets and occupied priority cutoffs. It resolves arbitrary support sizes and binary masses for every fixed pair $m,k$, and it computes no $Q_g(c,c')$ values.
For variable $m$ and $k$, its running time is still exponential in the number of category-school pairs. Neither this algorithm nor the existence proof establishes polynomial-time solvability or $\mathrm{NP}$-hardness of the general promised construction problem.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial correct partial results, but it does not settle the polynomial-time-versus-$\mathrm{NP}$-hardness question in USER_TASK. I found no substantive mathematical error in its characterization, enumeration algorithm, certificate argument, existence reduction, or threshold properties.
The prover explicitly acknowledges that the general complexity classification remains unresolved. Its established results are:
These are genuine progress. Existence alone does not resolve the requested construction complexity.
Verified.
For a direct move, strict preference implies $a\ne c$. The only aggregate constraints moving toward violation are the category floor at $a$, category ceiling at $c$, and capacity at $c$. Together with the positive donor entry, their strict slacks are necessary and sufficient for a sufficiently small positive move.
For a same-category exchange between $a$ and $c$, every row total, category-school total, and school total is preserved. The donor-entry bound stated in the proof suffices.
For cross-category displacement:
The disjunction exhausts every permitted destination because $d\ne c$. No preference requirement is incorrectly imposed on the displaced type.
The lemma concerns feasibility; the later characterization correctly adds the necessary strict priority comparison.
Verified.
Because the support is finite, every nonempty category-school pair has an occupied tier attaining its maximum tier number. Consequently,
$$
w_{hc}(x)>p_c(t)
$$
is equivalent to the existence of an occupied, strictly lower-priority donor in category $h$ at school $c$.
The empty-pair convention $w_{hc}=0$ cannot produce a false donor, since actual tier numbers are positive.
Each forbidden-entry condition supplies a permitted blocking move when the entry has positive mass. Conversely, every permitted blocking move satisfies one of those conditions:
Priority ties are handled correctly by the strict inequality.
Verified, including the running-time bound.
For an accepted case, $\delta>0$ ensures that selected slack sets are realized exactly. A selected positive cutoff has occupied mass in its tier and no occupied mass below it; a zero cutoff forces the pair to be empty. Thus Proposition 2 applies to the actual assignment, rather than merely to guessed data.
Conversely, a real stable assignment determines one enumerated case. Every strict slack and every selected occupied-tier mass is positive. Their finite minimum, capped at $1$, provides a positive feasible $\delta$. The empty-collection convention is valid.
The optimization problems are bounded: assignment entries are bounded by their row masses, and $\delta\in[0,1]$. Their feasible regions are closed, so a feasible program attains its optimum. The stated rational linear-programming theorem applies to their rational coefficients and polynomial encoding lengths.
The case count is correct:
$$
2^{m+2km}\prod_{g\in G}(\tau_g+1)^m.
$$
There are $m+2km$ independently selected set-membership bits, and at most $\tau_g+1$ cutoff choices for each category-school pair.
For fixed $m,k$, this is polynomial in $\tau,L$. When $m,k$ vary, this bound does not establish polynomial time. An exponential enumeration bound also supplies no hardness conclusion.
Verified.
Exact rational arithmetic can check feasibility, determine all strict slacks and occupied cutoffs, and test every forbidden entry in polynomial time in the input and assignment encoding lengths.
The certificate argument does not require a polynomial-time method for discovering the correct case. Existence of one rational linear program with positive optimum suffices. Its rational optimizer has polynomial encoding length and is stable by Theorem 3.
Thus the unrestricted existence decision problem belongs to $\mathrm{NP}$. This does not establish $\mathrm{NP}$-hardness, nor does it classify promised construction.
Verified.
The product of input denominators has binary length $O(L)$, makes all scaled quantities integral, and produces positive integer clone counts totaling $D$.
The circulation represents exactly the assignment constraints. All arc bounds are integral. Fixing selected category-school arcs at their lower bounds preserves integrality of the bounds, so the stated integral-circulation theorem applies both to feasibility and to every relevant floor-equality face.
Consequently, continuous and cloned finite floor-feasibility agree, and the finite thresholds equal the continuous thresholds multiplied by $D$.
Verified.
Positive masses ensure that a sufficiently small positive bottom mass identifies exactly the lowest tier through its positive coordinates. After matching complete bottom tiers of cumulative mass $b<q$, a sufficiently small increment identifies the next tier. This also identifies the entire tier containing an interior threshold.
Using the same clone order to refine matching tiers therefore produces identical bottom-clone sets through every required integer threshold. A zero threshold requires only the empty set.
The thresholds are within the bottom-mass domain: they are bounded by the total category floors, which the task assumes are strictly below $M_g$.
Verified against the cited source.
Tomoeda’s Definition 2 permits a cross-category replacement changing only the two students’ assignments, with the displaced student sent to any other school; it imposes no destination preference requirement. Definition 3 excludes same-category justified envy. Definition 1 excludes feasible preferred direct moves. Definition 5 uses the same floor-feasibility thresholds and bottom-set requirement, and Theorem 2 guarantees a feasible, fair, non-wasteful assignment. The scaled instance satisfies the source’s feasibility, acceptability, strict-order, capacity, quota, and category-total hypotheses. [Tomoeda, Definitions 1–5 and Theorem 2](https://opus.lib.uts.edu.au/rest/bitstreams/4b42dc45-2e98-4a7b-92b0-b66de649dea2/retrieve)
Verified.
The aggregated assignment and all relevant slacks lie on the grid $D^{-1}\mathbb Z$. For a permitted blocking direction, coefficients of entries and aggregate constraints have absolute value at most $1$. Any constraint moving toward violation must have positive slack, hence at least $D^{-1}$; donor entries have the same lower bound.
Therefore any positive feasible blocking direction permits a move of size $D^{-1}$, realizable by clones. Original strict priority comparisons survive refinement. The resulting finite move contradicts the corresponding fairness or non-wastefulness property.
The conclusion that every promised instance has a stable assignment follows.
Minor wording issue: the existence proof is described as “self-contained,” although its essential finite existence step invokes Tomoeda’s theorem. This affects presentation, not validity. Describe it as a reduction to the finite theorem.
Verified.
All threshold maxima are attained because the admissible collections are finite and contain the empty floor set.
Removing $c$ from a maximizing floor set preserves feasibility. The resulting set excludes $c$ and at least one of the two original excluded schools distinct from $c$, so it is admissible for a threshold defining $Q_g(c)$. The displayed floor-sum calculation gives the claimed lower bound; nonnegativity and the definition of $q_g$ give the remaining bounds.
The reference-order corollary correctly compares both school orders to the promised reference over their required mass ranges. The zero-floor conclusion follows from Proposition 7.
No counterexample or false central step was identified.
⟨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.