Answer: —
Theorem 3.6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe time complexity of QRDA isO(n×m), assuming school-feasibility can be checked in a constant time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite schools \(C\), finite complete types \(\Theta\) with rational masses \(\mu_\theta\), type-specific school preferences, school priority classes with boundary-mass splitting, rational \(\alpha\), and cyclic order \(\sigma\), compute exactly the event-driven mass-QRDA outcome, including \(x_{\theta,c}\), the quota-breakpoint sequence, and the first ratio-feasible stage.
A society is given by its support: \(\tau\) complete types with positive binary-rational masses \(\mu_\theta\), normalized by \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types. There are \(m\ge2\) schools; each type strictly ranks all schools, all schools and types are mutually acceptable, and each school specifies an ordered partition of the types into priority classes. The input also contains rational \(\alpha\in[0,1]\) and a cyclic permutation \(\sigma\) of the schools; \(L\) is the total input bit length.
For quotas \(q_C\), mass deferred acceptance uses synchronous student-proposing rounds: rejected mass applies to its next school, and schools reconsider newly applying and tentatively held mass together. Each school retains higher priority classes first; if its remaining quota is smaller than the offered mass of the boundary class, it retains the same fraction of every type's offered mass in that class. Define the outcome by the limit of these rounds, writing \(x_{\theta,c}\) for assigned mass and \(y_c=\sum_\theta x_{\theta,c}\).
Define continuous balanced mass-QRDA as follows. Initialize every quota at \(Q=1/(1+(m-1)\alpha)\), and decrease their common value \(q\) continuously toward \(1/m\), evaluating mass deferred acceptance at each value. This is the continuous limit of equal-size round-robin reductions; simultaneous school events are ordered by \(\sigma\). Stop at the first point satisfying \(\min_c y_c\ge\alpha\max_c y_c\), including the initial point.
A quota breakpoint is a value where the deferred-acceptance outcome changes regime: the set of positive type-school assignments, the set of binding quotas, or a school's partially retained priority class changes. Coalesce simultaneous breakpoints, include the initial and stopping quota vectors, and define the first feasible stage by its breakpoint interval and exact stopping value. Exact numerical outputs use real-algebraic representations.
Is computing this mass-QRDA outcome—its \(x_{\theta,c}\), complete quota-breakpoint sequence, and first ratio-feasible stage—possible in time polynomial in \(m,\tau,L\), or is the problem NP-hard?
Discrete QRDA has running time \(O(nm)\), assuming constant-time school-feasibility checks ([verified full version](https://link.springer.com/article/10.1007/s10458-020-09448-9)). No result settling this precisely specified continuous computation was located.
The general problem with priority ties remains unresolved. I prove a stronger special-case result than those in the notes:
Theorem. If every school’s priority classes are singletons, then all the requested outputs—assignments, the complete quota-breakpoint sequence, and the first ratio-feasible stage—are computable in time polynomial in $m,\tau,L$. All numerical outputs in this restriction are rational. There are at most $m\tau$ interior quota breakpoints.
The schools may use different strict priority orders.
I also give strict-priority examples showing that individual assignments can be discontinuous in the quota and that direct synchronous simulation can require exponentially many rounds. Neither phenomenon implies hardness of the exact computation.
These preliminary facts apply even when priority classes contain multiple types. They are needed below, so I prove them here.
Write type $\theta$’s ranking as
$$
c_{\theta,1},\ldots,c_{\theta,m}.
$$
Fix a common quota $q\ge 1/m$. Let $A_{\theta,k}(t)$ and $R_{\theta,k}(t)$ be cumulative applications and cumulative rejections at the type’s $k$th school through round $t$. Before the first round both are zero. Synchronous applications satisfy
$$
A_{\theta,1}(t)=\mu_\theta,\qquad
A_{\theta,k}(t)=R_{\theta,k-1}(t-1)\quad(k\ge 2).
$$
The mass held after round $t$ is
$$
H_{\theta,k}(t)=A_{\theta,k}(t)-R_{\theta,k}(t).
$$
Cumulative applications and rejections are nondecreasing in $t$, and
$$
0\le R_{\theta,k}(t)\le A_{\theta,k}(t)\le\mu_\theta.
$$
The last bound follows inductively along the ranking. Thus both cumulative quantities converge, and every held coordinate has a limit.
Let $Y_c(t)$ be the total held by school $c$, and let $a_c(t)$ be its newly applying mass. Mutual acceptability gives
$$
Y_c(t)=\min\{q,Y_c(t-1)+a_c(t)\}.
$$
Hence school totals are nondecreasing in time, and any school that rejects positive mass remains full thereafter.
There can be no positive last-school rejection in a finite round. Such rejection for a type would entail earlier positive rejection from every other school in its complete ranking. All schools would therefore be full, holding total mass $mq\ge 1$, while positive mass remained unheld. This contradicts conservation of the unit total mass.
Finally, convergence of cumulative rejection implies
$$
R_{\theta,k}(t)-R_{\theta,k}(t-1)\longrightarrow 0.
$$
After a round, unheld mass consists precisely of rejection awaiting its next application. There is no exhausted mass, and there are finitely many coordinates. Consequently all pending mass vanishes. The limit therefore satisfies
$$
\sum_c x_{\theta,c}=\mu_\theta,\qquad
\sum_c y_c=1,\qquad
0\le y_c\le q.
$$
School totals are continuous in $q$. To see this, a type offered mass $a_\theta$ in a priority class of total offer $A$, with higher-class offer $B$, is retained in amount
$$
a_\theta\min\left\{1,\max\left\{0,\frac{q-B}{A}\right\}\right\}
$$
when $A>0$. At $A=0$, continuity follows from the bound between zero and $a_\theta$. Thus every finite-round state is continuous in $q$.
Since $Y_c(t,q)$ increases to $y_c(q)$, each $y_c$ is lower semicontinuous. Full assignment also gives
$$
y_c(q)=1-\sum_{d\ne c}y_d(q),
$$
so it is upper semicontinuous as well. Therefore it is continuous.
Put
$$
I=[1/m,Q],\qquad
Q=\frac{1}{1+(m-1)\alpha},
$$
and define
$$
g(q)=\min_c y_c(q)-\alpha\max_c y_c(q).
$$
This function is continuous. At $q=1/m$, all school totals equal $1/m$, so the feasible set
$$
F=\{q\in I:g(q)\ge 0\}
$$
is nonempty and compact. The first stopping quota is therefore the attained value
$$
q_*=\max F.
$$
This argument does not assume that feasibility is monotone.
From this section through Section 5, assume that every school strictly orders the supported types.
Let $C_q(a)$ denote a school’s retained vector from offered vector $a$. For a priority prefix $P$,
$$
\sum_{\theta\in P}C_q(a)_\theta
=
\min\left\{q,\sum_{\theta\in P}a_\theta\right\}.
$$
For nonnegative offer vectors $a,b$, it follows that
$$
\begin{aligned}
\sum_{\theta\in P}C_q(C_q(a)+b)_\theta
&=
\min\left\{q,\min\left\{q,\sum_{\theta\in P}a_\theta\right\}
+\sum_{\theta\in P}b_\theta\right\}\\
&=
\min\left\{q,\sum_{\theta\in P}(a_\theta+b_\theta)\right\}.
\end{aligned}
$$
Because every priority class is a singleton, prefix totals determine all coordinates. Hence
$$
C_q(C_q(a)+b)=C_q(a+b).
$$
Applying this identity inductively to the specified held-plus-new process shows that the held vector at a school after every round equals its strict-priority choice from cumulative applications.
Write $r_{\theta,c}$ for limiting cumulative rejection and define the corresponding cumulative application by
$$
a_{\theta,c}(r)=
\begin{cases}
\mu_\theta,&c=c_{\theta,1},\\
r_{\theta,c_{\theta,k-1}},&c=c_{\theta,k},\ k\ge 2.
\end{cases}
$$
Let
$$
s_{\theta,c}(r)=
\sum_{\eta:\,\eta\text{ has higher priority than }\theta\text{ at }c}
a_{\eta,c}(r).
$$
Strict-priority rejection is
$$
T_q(r)_{\theta,c}
=
\min\left\{
a_{\theta,c}(r),
\max\{0,a_{\theta,c}(r)+s_{\theta,c}(r)-q\}
\right\}.
$$
The map $T_q$ is continuous and coordinatewise nondecreasing in $r$. It is also coordinatewise nonincreasing in $q$. It maps
$$
\mathcal B=\prod_{\theta,c}[0,\mu_\theta]
$$
into itself.
By path independence, actual cumulative rejection after round $t$ is exactly
$$
r^{(t)}=T_q(r^{(t-1)}),\qquad r^{(0)}=0.
$$
Its limit $r(q)$ is a fixed point by continuity.
It is the coordinatewise least fixed point. Indeed, if $\widehat r=T_q(\widehat r)$, induction gives
$$
r^{(t)}\le\widehat r
$$
for every $t$, and hence $r(q)\le\widehat r$.
Quota monotonicity follows from the same iteration:
$$
q_1<q_2
\quad\Longrightarrow\quad
r_{\theta,c}(q_1)\ge r_{\theta,c}(q_2)
\quad\text{for every }\theta,c.
$$
Thus cumulative applications $a_{\theta,c}(q)$ are also nonincreasing in $q$.
I verify that standard strict stable-allocation algorithms compute this particular fixed point.
Call an allocation stable if it assigns every type’s mass, respects school quotas, and has no pair $(\theta,c)$ such that $\theta$ has positive mass at a less preferred school while $c$ either has unused capacity or holds positive mass of a lower-priority type.
For a fully assigned allocation $x$, define
$$
a_{\theta,c}
=
\mu_\theta-\sum_{d\succ_\theta c}x_{\theta,d}.
$$
Then $a_{\theta,c}-x_{\theta,c}$ is exactly the mass of $\theta$ assigned below $c$.
Stability is equivalent to
$$
C_q(a_{\cdot,c})=x_{\cdot,c}
\quad\text{at every school }c.
$$
For the nontrivial direction, suppose choice differs from $x$, and take the highest-priority type where they differ. Earlier coordinates agree. Choice must retain more of this type than $x$ does, because $x_{\theta,c}\le a_{\theta,c}$ and $x$ respects the remaining quota. The type has mass below $c$, and the remaining capacity beyond $x_{\theta,c}$ is either unused or occupied by lower-priority types. This is a blocking pair.
Conversely, greedy choice rejects a type only when the school is full with types of at least that priority, so choice admits no blocking pair.
Fixed points of $T_q$ also give fully assigned allocations. Their rejection coordinates satisfy
$$
r_{\theta,c_{\theta,k}}\le r_{\theta,c_{\theta,k-1}}.
$$
If a last-school rejection were positive, rejection would be positive at every school for that type. Every school would then be full, whereas telescoping the allocation equations gives held total
$$
1-\sum_\theta r_{\theta,c_{\theta,m}}<1,
$$
contradicting $mq\ge 1$.
Thus fixed points correspond to stable allocations. Moreover,
$$
\sum_{j=1}^k x_{\theta,c_{\theta,j}}
=
\mu_\theta-r_{\theta,c_{\theta,k}}.
$$
The least fixed point therefore simultaneously maximizes every type’s assigned mass in every preference prefix. Its allocation is the proposer-optimal stable allocation.
The known strict bipartite stable-allocation algorithm computes the proposer-optimal allocation in polynomial time; see Dean and Munshi, Section 3 and Lemma 5. Here the bipartition consists of types and schools, with quotas $\mu_\theta$ and $q$, strict orders on both sides, and edge capacities $\min\{\mu_\theta,q\}$. These edge bounds impose no additional restriction. Unused capacity is handled by the standard dummy construction. For rational data, scaling by a common denominator gives integral data of polynomial bit length; the augmenting algorithm uses additions, subtractions, comparisons and minima. Thus it supplies a polynomial-time exact oracle at every rational $q$. [Faster Algorithms for Stable Allocation Problems](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf)
At school $c$, list types in strict priority order as
$$
\theta_{c,1},\ldots,\theta_{c,\tau}.
$$
Define cumulative prefix offers
$$
S_{c,j}(q)=\sum_{\ell=1}^j a_{\theta_{c,\ell},c}(q)
$$
and predicates
$$
P_{c,j}(q):\quad S_{c,j}(q)\ge q.
$$
Each $S_{c,j}$ is nonincreasing in $q$. Consequently each predicate changes at most once as $q$ decreases. More explicitly, for $q_1<q_2$,
$$
S_{c,j}(q_1)\ge S_{c,j}(q_2),
$$
so
$$
S_{c,j}(q_2)\ge q_2
\quad\Longrightarrow\quad
S_{c,j}(q_1)>q_1.
$$
Equality $S_{c,j}(q)=q$ can occur at only one quota.
Let $E$ contain the interior transition values of all these predicates. Then
$$
|E|\le m\tau.
$$
I next prove that there are no outcome-regime breakpoints outside $E$.
Let $J$ be a nonempty open interval between consecutive values in $E$, including the intervals adjacent to the endpoints of $I$. All predicates are constant on $J$, and no prefix offer equals $q$ there.
A school is either:
$$ S_{c,j-1}<q<S_{c,j}. $$
In the latter case, higher-priority types have rejection zero, the boundary type has
$$
r_{\theta_{c,j},c}=S_{c,j}-q,
$$
and lower-priority types have rejection equal to their entire cumulative application.
Set $N=m\tau$. These equations have the form
$$
r=M r+b(q),
$$
where $M$ has entries in $\{0,1\}$ and $b(q)$ is affine. A boundary equation contributes coefficient $-1$ for $q$; other equations contribute coefficient zero.
Draw an edge from coordinate $u$ to coordinate $v$ when $M_{v,u}=1$.
Choose $q_1<q_2$ in $J$ and put
$$
\Delta=r(q_1)-r(q_2)\ge 0,\qquad
\delta=q_2-q_1>0.
$$
Subtracting the equations gives
$$
\Delta=M\Delta+\delta e,
$$
where $e_v=1$ at boundary coordinates and $e_v=0$ elsewhere.
Along every dependency edge $u\to v$,
$$
\Delta_v\ge\Delta_u.
$$
If $v$ is a boundary coordinate, the stronger inequality is
$$
\Delta_v\ge\Delta_u+\delta.
$$
Therefore a directed cycle containing a boundary coordinate is impossible.
A zero-rejection coordinate has no incoming edges. A remaining coordinate rejects its entire application, so its only dependency is the same type’s rejection at the immediately preceding school in its ranking. A cycle consisting solely of these coordinates would strictly advance that type’s ranking position at every edge, which is also impossible.
The dependency graph is thus acyclic. In particular, $M^N=0$, and
$$
r(q)=(I+M+\cdots+M^{N-1})b(q)
\quad(q\in J).
$$
All rejection coordinates, applications and assignments are affine functions of $q$ on $J$.
A lower-priority type below the boundary has assignment zero. The boundary type has strictly positive assignment and strictly positive rejection throughout $J$, so its singleton class is partially retained.
An assignment above the boundary, or at an undersubscribed school, equals its application. It is a nonnegative affine function throughout $J$. Such a function either vanishes identically or is positive everywhere on $J$: an interior zero of a nonconstant affine function would force a negative value on one side.
Thus the positive assignment set, binding schools and partially retained classes are all constant on $J$.
Every interior transition in $E$ changes a school’s cutoff, or changes it between undersubscribed and full. Hence it changes the binding status or partially retained class on the adjacent open intervals. Therefore $E$ is precisely the set of interior quota breakpoints, after coalescing simultaneous transitions.
The previous section bounds their number. Exact polynomial computation also needs a uniform bound on their representation lengths.
For each rejection coordinate, the fixed-point equation has three closed linear branches:
$$
\begin{array}{ll}
r_{\theta,c}=0,
& S_{\theta,c}\le q,\\[2mm]
r_{\theta,c}=a_{\theta,c},
& s_{\theta,c}\ge q,\\[2mm]
r_{\theta,c}=S_{\theta,c}-q,
& s_{\theta,c}\le q\le S_{\theta,c},
\end{array}
$$
where $S_{\theta,c}=s_{\theta,c}+a_{\theta,c}$.
Selecting branches for all coordinates, and imposing $0\le r_{\theta,c}\le\mu_\theta$, describes a bounded polytope at each fixed $q$. The fixed-point set is the union of finitely many such polytopes.
The least fixed point uniquely minimizes
$$
\sum_{\theta,c}r_{\theta,c}
$$
over this union. Indeed, every other fixed point is coordinatewise at least the least one, with some coordinate strictly larger.
In any branch polytope containing it, this unique minimizer must be a vertex. Otherwise it would be a nontrivial convex combination of two points of the polytope, and linearity of the objective would contradict uniqueness.
A vertex is determined by $N$ independent active constraints. Their coefficients in $r$ belong to $\{-1,0,1\}$, their coefficients in $q$ have absolute value at most one, and their constants are signed sums of input masses.
Cramer’s rule therefore produces a finite family of rational affine candidate vectors. At each quota, $r(q)$ is a feasible member with minimum objective value.
Let $D$ be the product of the denominators of the input masses. Then
$$
D\le 2^L.
$$
Set
$$
K=(N+1)^{N+1}.
$$
Expanding determinants bounds their absolute values by $K$. Each candidate coordinate can consequently be written as
$$
v_i(q)=\frac{p_i+D s_iq}{D d},
$$
with integers satisfying
$$
1\le |d|\le K,\qquad
|p_i|\le DK,\qquad
|s_i|\le K.
$$
A candidate is feasible on an interval, possibly empty or a singleton, because its feasibility conditions are linear in $q$. A finite endpoint of this interval has numerator and denominator bounded in absolute value by
$$
(N+1)DK.
$$
An intersection of two nonidentical candidate objective functions has numerator and denominator bounded by
$$
2NDK^2.
$$
The same feasibility-size bound applies to a candidate’s prefix equation $S_{c,j}(q)=q$.
Between these finitely many event values, candidate feasibility and objective ordering are constant. Uniqueness of the minimizing vector then makes $r(q)$ one affine candidate throughout each resulting interval. A predicate transition must occur either at an event value or at a candidate prefix-equation root.
Thus all interior quota breakpoints are rational. Their reduced numerators and denominators are bounded by, for example,
$$
H=4(N+1)m\,2^L K^2.
$$
The endpoints $1/m$ and $Q$ satisfy this bound as well. Crucially,
$$
\log_2 H=O\bigl(L+N\log(N+1)+\log m\bigr),
$$
which is polynomial in the input parameters.
For each of the $m\tau$ predicates $P_{c,j}$, evaluate it at $1/m$ and $Q$ using the rational-quota oracle.
If its endpoint values agree, monotonicity excludes an interior transition. Otherwise, binary search brackets its unique transition. Predicate membership at the transition itself need not be known during this search.
Continue until the bracket has width less than
$$
\frac{1}{4H^2}.
$$
This takes polynomially many oracle calls, all at rationals of polynomial bit length.
Distinct reduced fractions with denominators at most $H$ are separated by at least $1/H^2$. Hence the bracket contains exactly one possible transition rational of denominator at most $H$.
It can be recovered in polynomial time by continued fractions. Specifically, the bracket midpoint differs from the transition by less than $1/(8H^2)$. For its reduced denominator $b\le H$, this is less than $1/(2b^2)$, so the standard continued-fraction approximation criterion makes the transition a convergent of the midpoint, unless they are equal. Listing the convergents and testing bracket membership recovers the unique rational.
Sort and coalesce the recovered values. This gives the complete breakpoint partition of $I$.
Choose one rational sample in every open breakpoint interval. The oracle determines the school cutoffs there. Section 3 proves that the corresponding dependency graph is acyclic.
Topological substitution in
$$
r=M r+b(q)
$$
computes all affine formulas exactly. Assignments follow from
$$
x_{\theta,c}(q)=a_{\theta,c}(q)-r_{\theta,c}(q).
$$
The determinant bounds above, or direct substitution along the acyclic graph, show that their rational coefficients have polynomial bit length.
At breakpoint values, use the oracle itself. This is necessary because assignments can jump, as shown below.
On each open breakpoint interval, every school total is affine. Ratio feasibility is equivalent to the collection of linear inequalities
$$
y_c(q)-\alpha y_d(q)\ge 0
\qquad\text{for all schools }c,d.
$$
Indeed, these inequalities hold exactly when the smallest total is at least $\alpha$ times the largest.
The affine school-total formulas extend to the interval endpoints with their actual values, by the continuity proved in Section 1. Intersecting the inequalities with each closed interval therefore determines its feasible quotas exactly.
Take the largest feasible quota over these intervals. It is $q_*$, is rational, and has polynomial bit length. Its location identifies the first feasible breakpoint interval, including endpoint cases. Evaluate the exact assignments at $q_*$ with the oracle.
Finally, retain the breakpoints encountered from $Q$ down to $q_*$ and include the initial and stopping quota vectors, coalescing coincidences. Simultaneous school events can be listed in the supplied cyclic order $\sigma$ before coalescing.
There are at most $m\tau$ interior breakpoints, and every step uses polynomially many operations on numbers of polynomial bit length. This proves the strict-priority theorem.
Rational outputs satisfy the requested real-algebraic representation requirement using degree-one polynomials.
Take three schools $A,B,C$ and two types of mass $1/2$, with preferences
$$
u:A\succ B\succ C,\qquad
v:B\succ A\succ C.
$$
At $A$, put $v$ above $u$; at $B$, put $u$ above $v$. School $C$ has either strict order.
For $q\ge 1/2$, each type receives its first choice completely.
Now let $1/3\le q<1/2$, and write
$$
\varepsilon=\frac12-q>0.
$$
Initially, each of $A,B$ holds native mass $q$ and rejects native mass $\varepsilon$. These rejections apply to the other school, where they have higher priority than the native type.
As long as at least $\varepsilon$ native mass remains, the next round displaces exactly $\varepsilon$ native mass at each school. When less remains, all of it is displaced. Thus after finitely many rounds the native holdings vanish. Each of $A,B$ holds quota $q$ entirely of the other type.
School $C$ never rejects: once $A,B$ are full, its held-plus-new offer is at most
$$
1-2q\le q.
$$
The outcome is therefore
$$
\begin{array}{c|ccc}
& A&B&C\\ \hline
u&0&q&1/2-q\\
v&q&0&1/2-q
\end{array}
\qquad(1/3\le q<1/2).
$$
In particular,
$$
\lim_{q\uparrow 1/2}x_{u,A}(q)=0,
\qquad
x_{u,A}(1/2)=\frac12.
$$
School totals remain continuous.
This jump occurs on an actual QRDA path. For $\alpha=1/4$,
$$
Q=\frac23,\qquad q_*=\frac49,
$$
because below $1/2$ the ratio condition is exactly
$$
1-2q\ge\frac14q.
$$
Take four schools $A,B,C,D$ and set $\alpha=1$. Initialization and stopping both occur at
$$
q=Q=\frac14.
$$
For an integer $b\ge 4$, let
$$
\varepsilon=2^{-b}.
$$
Use four types with dyadic masses
$$
\mu_u=\mu_v=q+\varepsilon,\qquad
\mu_w=q,\qquad
\mu_z=q-2\varepsilon.
$$
These are positive and sum to one.
Their preferences are
$$
\begin{array}{c|l}
u&A\succ B\succ D\succ C\\
v&B\succ A\succ D\succ C\\
w&C\succ D\succ A\succ B\\
z&D\succ C\succ A\succ B.
\end{array}
$$
At $A$, use $v\succ u\succ w\succ z$; at $B$, use $u\succ v\succ w\succ z$. The other schools use arbitrary strict orders.
Put
$$
N=\frac{q}{\varepsilon}=2^{b-2}.
$$
After round one, $A,B$ each hold native mass $q$ and reject native mass $\varepsilon$. School $C$ holds $w$ of mass $q$, and $D$ holds $z$ of mass $q-2\varepsilon$.
For every round
$$
1\le t\le N+1,
$$
school $A$ holds
$$
q-(t-1)\varepsilon
\quad\text{of }u,\qquad
(t-1)\varepsilon
\quad\text{of }v,
$$
and $B$ has the symmetric holdings. Each round rejects native mass $\varepsilon$ from both schools. This follows inductively because arriving nonnative mass has higher priority and displaces the same amount of native mass.
After round $N+1$, native holdings are zero. In round $N+2$, the final incoming nonnative mass $\varepsilon$ is rejected from each already full school. In round $N+3$, this total mass $2\varepsilon$ reaches $D$, exactly filling its remaining capacity. No further rejection occurs.
Thus synchronous DA takes $N+3$ rounds. Here $m=\tau=4$ and the input length is $O(b)$, while
$$
N=2^{b-2}.
$$
The number of rounds is exponential in input length.
The final allocation is nevertheless simple:
$$
x_{u,B}=q,\quad x_{u,D}=\varepsilon,\quad
x_{v,A}=q,\quad x_{v,D}=\varepsilon,\quad
x_{w,C}=q,\quad x_{z,D}=q-2\varepsilon,
$$
with all other coordinates zero. Section 5 computes it in polynomial time.
The strict-priority proof depends essentially on path independence. Proportional retention within a nonsingleton class does not have that property.
For example, take one tied class with two types and quota $q=2/5$. Let
$$
a=(1/2,0),\qquad b=(0,3/10).
$$
Then
$$
C_q(a)=(2/5,0),
$$
and
$$
C_q(C_q(a)+b)=\left(\frac8{35},\frac6{35}\right),
$$
whereas
$$
C_q(a+b)=\left(\frac14,\frac3{20}\right).
$$
These vectors differ.
Consequently, the fixed-point equations, quota monotonicity and breakpoint bound proved above cannot be transferred to the specified tied-priority process by replacing held-plus-new offers with cumulative offers.
The general polynomial-time versus NP-hardness question therefore remains open in this write-up. The strict-priority theorem isolates nonsingleton priority classes as the remaining source of difficulty; it does not establish their computational hardness.
⟨structured verdict parsed — rendered above⟩
The output is a valid partial resolution in substance. Its strict-priority argument withstands verification, subject to minor endpoint bookkeeping omissions. It also establishes well-defined limiting outcomes and an attained stopping quota for the general process with ties.
It does not settle the question in USER_TASK: whether the computation for arbitrary priority classes is polynomial-time solvable or NP-hard. The prover explicitly acknowledges this limitation. I found no false central step.
Section 1 is correct.
$$
Y_c(t)=\min\{q,Y_c(t-1)+a_c(t)\}
$$
correctly follows from mutual acceptability and the retention rule. Consequently, a school remains full after it first rejects positive mass.
$$
y_c(q)=1-\sum_{d\ne c}y_d(q),
$$
which also makes each school total upper semicontinuous.
$$
q_*=\max F
$$
is attained. This correctly identifies the first feasible quota when quotas decrease from $Q$, without assuming monotone ratio feasibility.
These results establish existence and continuity of school totals. They do not establish algebraicity or efficient exact computation of the general limiting assignments.
Sections 2.1 and 2.2 are correct.
The priority-prefix calculation proves path independence for singleton classes. Since prefix totals determine every coordinate under strict priorities, the vector identity follows.
Its application to the held-plus-new process correctly identifies school holdings with choice from cumulative applications. Thus the synchronous rejection recurrence is exactly iteration of $T_q$ from zero.
The displayed rejection formula is correct in all three cases: full retention, partial retention, and complete rejection. The map is continuous, nondecreasing in rejection coordinates, and nonincreasing in quota.
The least-fixed-point argument is valid within the stated box
$$
\mathcal B=\prod_{\theta,c}[0,\mu_\theta].
$$
Comparison of the iterations also proves the asserted quota monotonicity of cumulative rejections and applications.
Section 2.3 is substantively correct, including the external algorithm application.
The stability-to-choice equivalence is valid. At the highest-priority coordinate where feasible allocation and greedy choice differ, greedy choice must retain more. The discrepancy then produces precisely the blocking pair described in the text. Conversely, the greedy choice identity excludes such a pair.
The full-assignment argument for fixed points is also correct. Positive last-school rejection would force every school to be full, while telescoping yields total assigned mass strictly below one.
The prefix identity
$$
\sum_{j=1}^k x_{\theta,c_{\theta,j}}
=\mu_\theta-r_{\theta,c_{\theta,k}}
$$
shows that the least fixed point dominates every stable allocation in every type’s preference prefix. It therefore has the proposer-optimality required by the cited algorithm.
I checked [Dean and Munshi’s paper](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf). Its strict bipartite model, dummy construction, and Section 3 algorithm apply here; Lemma 5 identifies the output as the job-optimal allocation. The paper’s operation bound is polynomial in the graph size.
The chosen edge capacities introduce no additional constraint: every feasible coordinate already satisfies
$$
x_{\theta,c}\le\min\{\mu_\theta,q\}.
$$
Moreover, a blocking pair under the prover’s definition cannot occur at a saturated edge: saturation at $\mu_\theta$ excludes mass below that school, and saturation at $q$ excludes unused capacity or lower-priority holdings.
Scaling rational inputs, including the queried quota, gives integral data of polynomial bit length. The stated arithmetic operations preserve the polynomial bit-complexity conclusion.
Section 3 is correct.
Each prefix offer is nonincreasing as a function of increasing quota. The stronger inequality used in the text correctly implies that a predicate can transition at most once and that prefix equality can occur at most once.
On an open interval without transitions, each school’s cutoff pattern is fixed. The rejection equations are therefore linear with the asserted nonnegative dependency coefficients.
The acyclicity argument is valid:
Thus the affine formula follows from nilpotence of $M$.
The support argument is also correct: a nonnegative affine function on an open interval either vanishes identically or is positive throughout. Boundary assignments and rejections are both positive under the strict prefix inequalities.
Finally, a predicate transition necessarily changes the cutoff pattern on adjacent open intervals. It consequently changes binding status or the partially retained singleton class. This supports the claimed correspondence between interior predicate transitions and quota breakpoints, and the bound of at most $m\tau$ such breakpoints.
Section 4 is correct.
The closed branches accurately describe the fixed-point equation, including their overlaps at equality. Their feasible sets are bounded polytopes.
The least fixed point uniquely minimizes the sum of rejection coordinates over all fixed points. In every branch polytope containing it, uniqueness forces it to be a vertex. Selecting independent active constraints therefore produces the finite family of rational affine candidates asserted in the text.
The determinant bounds are sufficient. The relevant coefficient entries have absolute value at most one, and constant terms have absolute value at most one because they are signed sums of distinct normalized masses. The generous bound
$$
K=(N+1)^{N+1}
$$
covers the determinants and replaced-column determinants.
The subsequent feasibility-endpoint and objective-intersection bounds follow by clearing candidate denominators. The stated $H$ covers these bounds and the input endpoints, with polynomial $\log_2 H$.
The finite candidate family is used only to establish representation bounds; the proposed algorithm does not enumerate it. Its potentially large cardinality therefore does not invalidate the running-time argument.
Section 5 is correct in substance, with two minor omissions.
Binary search uses monotone predicates and rational-quota oracle calls. Polynomially bounded denominator size supplies the required polynomial number of search steps.
The rational-separation bound and continued-fraction criterion are correctly applied. A bracket of the specified width contains at most one reduced rational with denominator at most $H$; the true transition supplies existence.
Topological substitution computes the interval formulas. Evaluating assignments separately at breakpoint quotas correctly handles possible discontinuities.
The inequalities
$$
y_c(q)-\alpha y_d(q)\ge 0
$$
for all school pairs are equivalent to the requested ratio condition. School-total continuity justifies extending interval formulas to their actual endpoint values. Taking the largest feasible quota therefore correctly identifies stopping.
When $\alpha=1$,
$$
Q=1/m,
$$
so there are no open breakpoint intervals. Section 5.3’s instruction to take the largest feasible quota “over these intervals” then has no interval to process.
This is a routine omitted base case, not a substantive obstacle. The write-up should explicitly specify the single-quota procedure, including the oracle evaluation and coalesced initial/stopping output.
Different predicate values at $1/m$ and $Q$ need not indicate an interior transition. A transition can occur exactly at an endpoint.
For example, take $m=2$, $\tau=1$, $\alpha=0$, mass one, and preference $A\succ B$. At $Q=1$, the predicate for $B$ is false, whereas at $q=1/2$ it is true because
$$
a_{\theta,B}(q)=1-q=q.
$$
Its transition is exactly the lower endpoint.
The reconstruction still works, but the algorithm should explicitly say that recovered endpoint values are merged with the existing endpoints and excluded from the interior-breakpoint list.
Sections 6 and 7 are correct.
The discontinuity example has the stated assignments. For $\alpha=1/4$, its stopping calculation gives
$$
q_*=\frac49,
$$
and the assignment jump occurs before stopping.
The exponential-round example also checks out. Native holdings reach zero in round $N+1$; the final incoming nonnative mass is rejected in round $N+2$ and reaches $D$ in round $N+3$. All masses are positive for the stated range, sum to one, and require $O(b)$ bits. Thus the exponential round count is established.
The tied-class calculation is correct:
$$
C_q(C_q(a)+b)=\left(\frac8{35},\frac6{35}\right),
\qquad
C_q(a+b)=\left(\frac14,\frac3{20}\right).
$$
This demonstrates failure of path independence for proportional retention. The prover correctly limits its inference: the strict-priority framework cannot simply be transferred to ties. The example establishes neither hardness nor impossibility of a different polynomial algorithm.
Major unresolved requirement: USER_TASK permits nonsingleton priority classes. The output gives neither a polynomial algorithm nor an NP-hardness result for that domain. Its explicit partial-resolution claim is accurate.
The minimum feedback is:
⟨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.