Answer: —
Theorem 1 — class: other
Given schools \(C\), a finite type set \(T\) encoding complete student preferences and school-priority orders, a rational mass vector \(\mu\in\mathbb Q_{\ge 0}^{\tau}\) with \(\sum_t\mu_t=1\), and a rational normalized union of quota regions \(\mathcal V_\infty=\bigcup_{j=1}^{\ell}\{\nu\in\mathbb R_{\ge 0}^{m}:\mathbf 1^\top\nu=1,\ p_j\le\nu_c\le q_j\ \forall c\}\), compute the normalized aggregate limit \(x^\infty\) of QRDA on \(r\)-fold replications with \(r\mu_t\in\mathbb Z\), and determine whether this limit exists, is school-feasible, and is aggregate-fair.
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. There are ordered schools \(C=(c_1,\ldots,c_m)\), with \(m\ge1\). Each type has a strict complete preference \(\succ_t\) over schools; each school has a strict complete priority \(\succ_c\) over types. All student–school pairs are acceptable.
The input includes \(\ell\ge1\) rational pairs satisfying \(0\le p_j\le 1/m\le q_j\le1\), defining \(\mathcal V_\infty=\bigcup_{j=1}^{\ell}\{\nu\in\mathbb R_{\ge0}^{m}:\sum_c\nu_c=1,\ p_j\le\nu_c\le q_j\ \forall c\}\). Let \(L\) be the total input bit length; state running times in \(m,\tau,\ell,L\).
For every positive integer \(r\) with \(r\mu_t\in\mathbb Z\) for all types and \(V_r=\{v\in\mathbb Z_{\ge0}^{m}:v/r\in\mathcal V_\infty\}\ne\varnothing\), create \(r\mu_t\) students of each type. Schools rank type blocks by \(\succ_c\), breaking priorities within each type by increasing copy index at every school.
QRDA initializes every school's capacity to \(\max_{v\in V_r,c\in C}v_c\). Run student-proposing deferred acceptance; if the school-count vector belongs to \(V_r\), return the matching. Otherwise reduce one capacity by \(1\), cycling through \(c_1,\ldots,c_m\), and repeat deferred acceptance with the new capacities.
Let \(x^{(r)}_{tc}\) be the returned number of type-\(t\) students assigned to \(c\), divided by \(r\). Define \(x^\infty=\lim_{r\to\infty}x^{(r)}\) along all admissible integers above. An aggregate allocation has \(x_{tc}\ge0\) and \(\sum_cx_{tc}=\mu_t\); it is school-feasible if \((\sum_tx_{tc})_{c\in C}\in\mathcal V_\infty\), and aggregate-fair if no \(t,u,c,d\) satisfy \(x_{td}>0\), \(x_{uc}>0\), \(c\succ_t d\), and \(t\succ_c u\).
Does \(x^\infty\) always exist and yield a school-feasible, aggregate-fair allocation? Is deciding its existence and computing it exactly when it exists polynomial-time solvable in \(m,\tau,\ell,L\), or NP-hard?
For finite societies, QRDA terminates with a feasible, fair matching under nonempty unions of symmetric M-convex constraints. The full version also establishes an \(O(mn)\) implementation for \(n\) students, assuming constant-time feasibility checks ([verified source](https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0289965)). No result settling this precise replication-limit problem was located.
The replication limit need not exist. Whenever it exists, it is school-feasible and aggregate-fair.
The main additional result proved here is that the integer outcome sequence has an effective finite description: apart from finitely many exceptions, it is affine on residue classes of replication sizes. Consequently:
$$ 2^{2^{2^{(m+\tau+\ell+L)^{O(1)}}}}. $$
This does not settle whether the general problem is polynomial-time solvable or NP-hard. That classification remains open in this write-up.
Let
$$
a_j(r)=\lceil rp_j\rceil,\qquad b_j(r)=\lfloor rq_j\rfloor.
$$
The integer feasible vectors in component $j$ satisfy
$$
\sum_c v_c=r,\qquad a_j(r)\le v_c\le b_j(r).
$$
This component is nonempty exactly when
$$
ma_j(r)\le r\le mb_j(r).
$$
Necessity follows by summing the bounds. For sufficiency, start every coordinate at $a_j(r)$ and distribute the remaining $r-ma_j(r)$ units, adding at most $b_j(r)-a_j(r)$ to each coordinate. The displayed inequalities ensure that this is possible.
Fix an admissible $r$ and write
$$
Q_r=\max_{v\in V_r,\ c\in C}v_c.
$$
Because a feasible vector sums to $r$, we have $mQ_r\ge r$.
Starting from equal capacities $Q_r$, cyclic reductions keep capacities within one unit of each other. After exactly $mQ_r-r$ reductions, their sum is $r$, so every capacity is either $\lfloor r/m\rfloor$ or $\lceil r/m\rceil$.
Choose a nonempty component $j$. Its nonemptiness gives
$$
a_j(r)\le\lfloor r/m\rfloor,\qquad
b_j(r)\ge\lceil r/m\rceil.
$$
Thus this balanced capacity vector belongs to $V_r$.
Whenever total capacity is at least $r$, DA assigns every student. Otherwise, an unmatched student has applied to every school, and all schools must be full. The number assigned would then equal total capacity and be at least $r$, contradicting the existence of an unmatched student. At the balanced stage, school counts therefore equal capacities. This proves termination by that stage.
The returned matching is fair. A student preferring another school to her assignment applied there and was rejected. At a rejecting school, every subsequently retained student outranks the rejected student. The same argument also shows that such a school is full.
Every accumulation point of $x^{(r)}$ is an aggregate allocation that is school-feasible and aggregate-fair.
Proof. Let $D$ clear all mass denominators. Every positive multiple of $mD$ is admissible: type populations are integral, and the integer uniform school vector is feasible. Thus admissible replication sizes are unbounded.
Every returned allocation satisfies
$$
x^{(r)}_{tc}\ge0,\qquad \sum_c x^{(r)}_{tc}=\mu_t.
$$
These conditions define a compact set. They persist under limits.
The school-total map is continuous, and $\mathcal V_\infty$ is a finite union of closed sets. School feasibility therefore persists under limits.
Fix $t,u,c,d$ with $c\succ_t d$ and $t\succ_c u$. Finite fairness implies
$$
x^{(r)}_{td}x^{(r)}_{uc}=0.
$$
Indeed, positive entries would supply a copy of $t$ assigned to $d$ and a copy of $u$ assigned to $c$, with the former preferring $c$ and outranking the latter there. Taking limits preserves this equality. Since both entries are nonnegative, they cannot both be positive. This proves aggregate fairness. $\square$
Take $m=3$, three types $a,b,d$, and masses
$$
\mu_a=\frac12,\qquad \mu_b=\mu_d=\frac14.
$$
Use the following preferences and priorities.
| Type | Preference |
|---|---|
| $a$ | $c_1\succ_a c_2\succ_a c_3$ |
| $b$ | $c_2\succ_b c_1\succ_b c_3$ |
| $d$ | $c_3\succ_d c_1\succ_d c_2$ |
| School | Priority |
|---|---|
| $c_1$ | $b\succ_{c_1}a\succ_{c_1}d$ |
| $c_2$ | $a\succ_{c_2}b\succ_{c_2}d$ |
| $c_3$ | $d\succ_{c_3}a\succ_{c_3}b$ |
Set $\ell=1$, $p_1=0$, and $q_1=3/8$. These bounds satisfy the input hypotheses.
Mass integrality requires $4\mid r$. Put $Q=\lfloor3r/8\rfloor$. For $r=8k$, the vector $(3k,3k,2k)$ is feasible. For $r=8k+4$, $k\ge1$, the vector $(3k+1,3k+1,2k+2)$ is feasible. Their permutations show that the initial capacity is $Q$. The remaining positive multiple $r=4$ is inadmissible.
For every admissible $r$, initial total capacity is at least $r$. DA assigns everyone, and all school counts are at most $Q$. Since the constraint has only an upper bound, QRDA returns this initial DA outcome.
For $r=8k$, there are $4k$ copies of $a$ and $2k$ each of $b,d$, with capacities $3k$. School $c_1$ rejects $k$ copies of $a$. They join the $2k$ copies of $b$ at $c_2$, exactly filling it. No further rejection occurs. Hence
$$
x^{(8k)}=
\begin{pmatrix}
3/8&1/8&0\\
0&1/4&0\\
0&0&1/4
\end{pmatrix},
$$
with rows ordered as $a,b,d$.
For $r=8k+4$, populations are $4k+2,2k+1,2k+1$, and capacities are $3k+1$.
All copies of $d$ remain at $c_3$, where they have highest priority and fit. A copy of $b$ reaching $c_1$ is permanently retained, because the entire population of $b$ fits there and has highest priority. Thus no copy of $b$ reaches $c_3$.
The combined population of $a,b$ is $6k+3$, exceeding the combined capacity of $c_1,c_2$ by one. Full assignment therefore puts some copy of $a$ at $c_3$. Fairness then excludes any copy of $b$ at $c_2$: that copy of $a$ prefers $c_2$ and outranks $b$ there. All $2k+1$ copies of $b$ must consequently be at $c_1$.
A copy of $a$ reaching $c_3$ was rejected from both earlier schools, which remain full. The count rows are therefore
$$
a:(k,3k+1,1),\qquad
b:(2k+1,0,0),\qquad
d:(0,0,2k+1).
$$
Consequently,
$$
\lim_{k\to\infty}x^{(8k+4)}=
\begin{pmatrix}
1/8&3/8&0\\
1/4&0&0\\
0&0&1/4
\end{pmatrix}.
$$
The two subsequential limits differ. Thus $x^\infty$ does not always exist.
The common copy-index priorities permit a description using only integer type–school counts.
Fix nonnegative integer populations $n_t$ and capacities $\kappa_c$, with
$$
\sum_c\kappa_c\ge\sum_t n_t.
$$
For an integer count matrix $Y$, define
$$
H_c(Y)=\sum_tY_{tc},
$$
$$
W_{tc}(Y)=\sum_{d:\ c\succ_t d}Y_{td},
\qquad
B_{tc}(Y)=\sum_{u:\ t\succ_c u}Y_{uc}.
$$
A full matching is called stable if there is no student–school pair in which the student prefers that school and the school either has a vacancy or holds a lower-priority student.
A matrix $Y$ is the count matrix of a full stable matching exactly when
$$
Y_{tc}\ge0,\qquad \sum_cY_{tc}=n_t,\qquad H_c(Y)\le\kappa_c,
$$
and, for every $t,c$,
$$
W_{tc}(Y)=0
\quad\text{or}\quad
\bigl(H_c(Y)=\kappa_c\ \text{and}\ B_{tc}(Y)=0\bigr).
$$
Moreover, its full stable matching is uniquely determined by $Y$: assign each type’s copies, in increasing index, to schools in that type’s preference order according to the counts.
Proof. In a stable matching, an earlier copy cannot receive a worse school than a later copy of the same type. Otherwise, the earlier copy and the later copy’s school form a blocking pair. Thus every stable matching has the asserted canonical assignment.
If $W_{tc}(Y)>0$, some copy of $t$ prefers $c$ to her assignment. Stability requires $c$ to be full and to hold no lower-priority type, giving the displayed condition.
Conversely, construct the canonical assignment from a matrix satisfying the conditions. Consider a copy of $t$ assigned below $c$. The condition makes $c$ full and excludes lower-priority types there. Every copy of $t$ assigned to $c$ has a smaller index than the considered copy, by canonical assignment. Hence every student at $c$ outranks that copy. No blocking pair exists. $\square$
Write the preference order of $t$ as
$$
c_{t,1}\succ_t\cdots\succ_t c_{t,m},
$$
and define prefix counts
$$
F_{t,k}(Y)=\sum_{i=1}^{k}Y_{t,c_{t,i}}.
$$
For canonical assignments with the same populations, every copy weakly prefers its assignment under $Y$ to its assignment under $Z$ exactly when
$$
F_{t,k}(Y)\ge F_{t,k}(Z)
\qquad\text{for every }t,k.
$$
To verify the reverse implication, a copy with index $i$ assigned within the first $k$ schools under $Z$ satisfies $i\le F_{t,k}(Z)\le F_{t,k}(Y)$, so is also assigned within that prefix under $Y$. The forward implication follows by counting copies assigned within each prefix.
Let $S(n,\kappa,Y)$ denote the conditions in Lemma 2. The DA count matrix is the unique matrix satisfying
$$
S(n,\kappa,Y)
\quad\text{and}\quad
\forall Z\,
\left(
S(n,\kappa,Z)\Longrightarrow
\bigwedge_{t,k}F_{t,k}(Y)\ge F_{t,k}(Z)
\right).
$$
Proof. We prove the needed student-optimality property directly.
Fix any full stable matching $M$. Suppose DA rejects an edge belonging to $M$, and consider the first such rejection. Let student $s$ be rejected by school $c=M(s)$. At that moment $c$ holds $\kappa_c$ students, all outranking $s$. Since $M$ assigns $s$ to $c$, at least one held student $h$ is assigned elsewhere under $M$.
Student $h$ has proposed to $c$. If she preferred $M(h)$ to $c$, she would previously have been rejected by $M(h)$, contradicting the choice of the first rejected edge belonging to $M$. Since $M(h)\ne c$, she strictly prefers $c$ to $M(h)$. Together with $c$ preferring $h$ to $s$, this gives a blocking pair for $M$, a contradiction.
Thus DA never rejects any student’s edge in $M$. Its final assignment is weakly preferred by every student to her assignment in $M$. DA is full and stable by the argument in Section 1. Lemma 2 and the prefix characterization therefore imply that its matrix satisfies the displayed formula.
Conversely, a matrix satisfying the formula dominates the DA matrix, while student-optimality makes the DA matrix dominate it. All prefix counts are equal. Taking differences of successive prefixes makes all entries equal. $\square$
Both lemmas use only linear equalities, inequalities, Boolean operations, and quantification over integer count matrices.
Presburger arithmetic is first-order integer arithmetic using addition and order. Multiplication by a fixed integer is allowed as notation for repeated addition; multiplication of two variables is not used below.
All count variables in this section range over nonnegative integers. Such quantifiers can equivalently be expressed over all integers by adding nonnegativity guards.
Write $\mu_t=\alpha_t/\delta_t$. Define the population predicate
$$
\operatorname{Pop}(r,n):
\quad
r\ge1\ \text{and}\
\delta_t n_t=\alpha_t r\ \text{for every }t.
$$
Define feasible school counts by
$$
\operatorname{Feas}(r,v):
\quad
\sum_c v_c=r
\ \text{and}\
\bigvee_{j=1}^{\ell}
\bigwedge_{c=1}^{m}
\left(rp_j\le v_c\le rq_j\right).
$$
After clearing each input denominator, these are linear integer inequalities.
The initial capacity is characterized by
$$
\begin{aligned}
\operatorname{Init}(r,Q):\quad&
\exists v\,
\left(\operatorname{Feas}(r,v)\ \land\ \bigvee_c v_c=Q\right)\\
&{}\land
\forall w\,
\left(\operatorname{Feas}(r,w)\Longrightarrow
\bigwedge_c w_c\le Q\right).
\end{aligned}
$$
This predicate holds precisely when $V_r$ is nonempty and $Q=Q_r$.
After $k$ reductions, write $k=ms+b$, with $0\le b<m$. The capacities are specified by
$$
\begin{aligned}
\operatorname{Path}(r,Q,k,\kappa):\quad
\exists s,b\quad&
k=ms+b,\quad b<m,\quad k\le mQ-r,\\
&\bigwedge_{i=1}^{m}
\left[
(b\ge i\ \land\ \kappa_{c_i}+s+1=Q)
\ \lor\
(b<i\ \land\ \kappa_{c_i}+s=Q)
\right].
\end{aligned}
$$
Their total is $mQ-k\ge r$, so the full-DA characterization applies.
Let $\operatorname{DA}(n,\kappa,Y)$ be Lemma 3’s formula, and put
$$
\begin{aligned}
A(r,Q,n,k,Y):\quad
\exists\kappa\quad&
\operatorname{Path}(r,Q,k,\kappa)\\
&{}\land\operatorname{DA}(n,\kappa,Y)\\
&{}\land\operatorname{Feas}\bigl(r,(H_c(Y))_{c\in C}\bigr).
\end{aligned}
$$
Finally define
$$
\begin{aligned}
G(r,Y):\quad\exists Q,n,k\quad&
\operatorname{Pop}(r,n)\land\operatorname{Init}(r,Q)
\land A(r,Q,n,k,Y)\\
&{}\land
\forall k'\,
\left(k'<k\Longrightarrow
\neg\exists Z\,A(r,Q,n,k',Z)\right).
\end{aligned}
$$
The solutions of $G$ are exactly the pairs
$$
(r,Y^{(r)}),\qquad Y^{(r)}=r x^{(r)},
$$
for admissible $r$.
Proof. The population and initialization predicates impose exactly admissibility and QRDA’s initial capacity. The path predicate describes each cyclic reduction stage through the balanced stage. Lemma 3 identifies that stage’s unique DA count matrix. Predicate $A$ requires feasibility, and the final universal condition excludes every earlier feasible stage. Section 1 ensures that some feasible stage occurs within this path. Thus $G$ describes precisely the returned outcome. $\square$
The formula does not contain one variable per student. Its length is polynomial in the support input. More specifically, it can be constructed with length
$$
N=
O\!\left(
\bigl(\ell m+m\tau(m+\tau)+m+\tau\bigr)
\bigl(L+\log(m+\tau+\ell+2)\bigr)
\right).
$$
Indeed, feasibility contributes $O(\ell m)$ inequalities; stability and prefix formulas have $O(m\tau(m+\tau))$ variable occurrences. The remaining predicates have polynomial size, and each coefficient has $O(L)$ bits. Every displayed predicate is expanded only a constant number of times.
We use the following precise computational result.
Presburger decomposition theorem. An integer-arithmetic formula of length $N$ can be converted into a finite union
$$
\bigcup_i
\left\{
b+\sum_{p\in P_i}k_p p:
b\in B_i,\ k_p\in\mathbb Z_{\ge0}
\right\},
$$
where $B_i,P_i$ are finite integer-vector sets and each $P_i$ is linearly independent. The conversion has a triply exponential running-time bound in $N$. This is Corollary 5.2 of [Chistikov, Haase, and Mansutti, *Geometric decision procedures and the VC dimension of linear arithmetic theories*](https://wrap.warwick.ac.uk/id/eprint/166499/1/WRAP-Geometric-decision-procedures-VC-dimension-2022.pdf).
The theorem applies to $G$: all coefficients are fixed integers after denominator clearing, and all its operations are Boolean operations and integer quantifiers. Its free coordinates are $r$ and the $m\tau$ entries of $Y$.
The graph property imposes a particularly strong restriction on the resulting decomposition.
Suppose a set in nonnegative integer coordinates is the graph of a function of its first coordinate. In any linear component contained in that graph:
Proof. A base and every period are nonnegative: a negative coordinate in a period would, after sufficiently many additions, produce a point outside the nonnegative orthant.
Write a period as $(h,v)$. If $h=0$, the base and the base plus this period have the same first coordinate. Functionality forces $v=0$.
For two periods $(h_1,v_1)$ and $(h_2,v_2)$ with positive first coordinates, the points
$$
b+h_2(h_1,v_1)
\quad\text{and}\quad
b+h_1(h_2,v_2)
$$
have equal first coordinates. Functionality gives
$$
h_2v_1=h_1v_2.
$$
The periods are therefore collinear. Linear independence permits at most one nonzero period and excludes zero periods. $\square$
Splitting each finite base set $B_i$ into its individual bases, the theorem and lemma give
$$
\{(r,Y):G(r,Y)\}
=
F\ \cup\
\bigcup_{i=1}^{s}
\left\{
(b_{i,0},b_i)+k(h_i,v_i):
k\in\mathbb Z_{\ge0}
\right\},
$$
where $F$ is finite, $h_i>0$, and all listed vectors are nonnegative integer vectors. There is at least one ray because admissible replication sizes are unbounded.
The accumulation points of $x^{(r)}$ are exactly the distinct matrices
$$
\Lambda_i=\frac{v_i}{h_i},
\qquad 1\le i\le s.
$$
Consequently, $x^\infty$ exists exactly when all $\Lambda_i$ are equal.
Proof. On ray $i$,
$$
r=b_{i,0}+kh_i,\qquad Y^{(r)}=b_i+kv_i,
$$
so
$$
x^{(r)}
=
\frac{v_i}{h_i}
+
\frac{b_i-b_{i,0}v_i/h_i}{r}.
$$
As $k$ tends to infinity, this converges to $\Lambda_i$, proving that each listed matrix is an accumulation point.
Conversely, take any subsequence with replication sizes tending to infinity along which $x^{(r)}$ converges. Its graph points eventually avoid $F$. Because there are finitely many rays, infinitely many of these points lie on one ray. That further subsequence converges to the corresponding $\Lambda_i$, so the original subsequential limit equals it.
If two slopes differ, the corresponding rays give distinct subsequential limits. If all slopes equal $\Lambda$, let
$$
K=\max_i
\left\|b_i-b_{i,0}\Lambda\right\|_\infty.
$$
Outside the finite exceptional set,
$$
\left\|x^{(r)}-\Lambda\right\|_\infty\le\frac K r.
$$
Thus the entire sequence converges. $\square$
In particular, every existing limit is rational and has an $O(1/r)$ convergence bound, with an instance-dependent constant.
There is also an eventual residue-class description. Let
$$
H=\operatorname{lcm}(h_1,\ldots,h_s).
$$
For each residue modulo $H$, a ray either contains every sufficiently large integer in that residue or contains none. Thus admissibility is eventually a union of residue classes. On each such class, the output is eventually affine:
$$
Y^{(r)}=r\Lambda_a+\Gamma_a,
$$
with rational matrices $\Lambda_a,\Gamma_a$. If several rays cover the same residue, their affine expressions agree at infinitely many replication sizes; equality at those sizes forces both their slopes and their intercepts to agree.
The resulting algorithm is finite and explicit:
Correctness follows from Lemma 5 and Theorem 6. The algorithm can also return all accumulation points.
For completeness, the cited decomposition theorem gives the sharper bound
$$
2^{(a+2)^{d^{O(h)}}},
$$
where $a$ bounds coefficient bit lengths, $d$ bounds the number of free variables in a subformula, and $h$ is syntactic nesting depth. Each is at most the formula length $N$. Consequently, decomposition takes at most
$$
2^{2^{2^{N^{O(1)}}}}
$$
bit operations. Scanning the explicit output and comparing rational slopes takes polynomial time in that output’s bit length, preserving this bound.
Substituting the polynomial bound for $N$ gives
$$
2^{2^{2^{(m+\tau+\ell+L)^{O(1)}}}}.
$$
This bound depends on the support encoding, without expanding any replication into individual students.
The restricted polynomial-time result can also be proved directly.
For $m=1$, necessarily
$$
x^\infty_{t,c_1}=\mu_t.
$$
For $m=2$, define
$$
\beta_j=\min(q_j,1-p_j),
\qquad
\beta=\max_j\beta_j.
$$
Each component, expressed through its first coordinate, is the interval $[1-\beta_j,\beta_j]$. These intervals are nested, so their union is $[1-\beta,\beta]$, with $\beta\ge1/2$.
For admissible $r$, put $Q_r=\lfloor r\beta\rfloor$. The feasible integer school vectors satisfy
$$
v_{c_1}+v_{c_2}=r,\qquad r-Q_r\le v_{c_i}\le Q_r.
$$
Their endpoint vectors attain $Q_r$, so both initial capacities are $Q_r$. Admissibility gives $2Q_r\ge r$. Initial DA assigns everyone; its upper capacity bounds automatically imply the lower bounds. Thus QRDA returns initially.
Let $G_i$ contain the types preferring $c_i$, and, for $t\in G_i$, put
$$
S_{ti}=\sum_{\substack{u\in G_i\\u\succ_{c_i}t}}\mu_u.
$$
Then
$$
x^\infty_{t,c_i}
=
\min\{\mu_t,\max\{0,\beta-S_{ti}\}\},
\qquad
x^\infty_{t,c_{3-i}}=\mu_t-x^\infty_{t,c_i}.
$$
To prove this, write $h_r=Q_r/r\ge1/2$. At most one school’s first-choice demand exceeds $h_r$. If neither does, everyone receives her first choice. Otherwise, the overloaded school retains its highest-priority first-choice applicants. Rejected applicants move to the other school, whose total demand becomes $1-h_r\le h_r$, so it rejects nobody. The finite first-choice allocation is therefore the displayed formula with $h_r$ replacing $\beta$. Since $h_r\to\beta$, continuity proves the limiting formula.
Scanning constraints and priorities uses $O(m\tau+\ell)$ exact arithmetic operations. A common denominator has $O(L)$ bits, as do all intermediate rational values. Elementary arithmetic gives the bit bound
$$
O((m\tau+\ell)L^2).
$$
Universal existence is disproved, and feasibility and aggregate fairness whenever the limit exists are proved. The general sequence has an effective arithmetic-ray description, giving decidability, rationality, and exact computation with a triply exponential upper bound.
The missing classification is whether deciding convergence and computing an existing limit admit a polynomial-time algorithm in $m,\tau,\ell,L$, or whether an appropriate version of these problems is NP-hard. No hardness reduction or general polynomial-time bound is established here.
⟨structured verdict parsed — rendered above⟩
The output is a correct partial resolution, with one minor qualification in Lemma 5. It disproves universal existence, proves feasibility and aggregate fairness of every accumulation point, and establishes an effective exact convergence test. It does not resolve the requested general polynomial-time versus NP-hard classification, as it explicitly acknowledges.
The component nonemptiness criterion
$$
ma_j(r)\le r\le mb_j(r)
$$
is correct. The proposed distribution argument establishes sufficiency, including components consisting of a single vector.
The definition of $Q_r$ implies $mQ_r\ge r$. Cyclic reductions from equal capacities keep their difference at most one, and after $mQ_r-r$ reductions their sum is $r$. Consequently, their coordinates are $\lfloor r/m\rfloor$ or $\lceil r/m\rceil$.
For a nonempty component, integrality of its bounds correctly gives
$$
a_j(r)\le\lfloor r/m\rfloor,\qquad
b_j(r)\ge\lceil r/m\rceil.
$$
Thus the balanced capacity vector is feasible. Capacities remain nonnegative throughout the inspected path.
The full-assignment argument uses the task’s complete acceptability assumption correctly: an unmatched student has exhausted every school, making every school full. This contradicts total capacity being at least the population. At the balanced stage, full assignment and equality of total capacity and population force school counts to equal capacities.
The rejection argument proves fairness for the final DA run. It also establishes the absence of blocking pairs involving vacancies, as needed later. There is no reliance here on an unverified application of the finite QRDA theorem supplied in the task.
Every positive multiple of $mD$ is admissible: populations are integral, and the uniform integer school vector satisfies every component’s bounds. Hence the limit is considered along an unbounded domain.
The allocation constraints give a compact set, and their equalities and inequalities persist under limits. School feasibility persists because $\mathcal V_\infty$ is a finite union of closed sets.
For every fixed prohibited configuration of types and schools, finite fairness implies
$$
x^{(r)}_{td}x^{(r)}_{uc}=0.
$$
Type-block priorities guarantee the asserted individual priority comparison regardless of copy indices. Continuity of multiplication preserves the equality, and nonnegativity excludes both limiting entries being positive.
This proves the stated result for every accumulation point, which is stronger than the requested conditional property of an existing limit.
The masses are positive binary rationals summing to one, all preferences and priorities are strict and complete, and
$$
0\le\frac13\le\frac38\le1.
$$
Thus the instance satisfies the task’s hypotheses.
Mass integrality requires $4\mid r$. For $r=8k$, the proposed feasible vector sums to $8k$ and has maximum coordinate $3k$. For $r=8k+4$ with $k\ge1$, the proposed vector sums to $8k+4$, and
$$
2k+2\le3k+1.
$$
Thus its coordinates respect the upper bound. Since every coordinate of every feasible vector is at most $\lfloor3r/8\rfloor$, these witnesses establish the claimed initialization. For $r=4$, the maximum permitted total is $3$, so inadmissibility is correct.
Initial DA assigns everyone. With only the upper-bound constraint, its counts are immediately feasible, so no capacity reductions occur.
For $r=8k$, the stated initial rejection and subsequent exact filling of $c_2$ are correct. The displayed normalized allocation follows.
For $r=8k+4$, the argument that all copies of $d$ remain at $c_3$ and no copy of $b$ reaches $c_3$ is justified by their priorities and population bounds. The combined population of $a,b$ exceeds the combined capacity of $c_1,c_2$ by exactly one. Consequently, some copy of $a$ must reach $c_3$. Fairness then excludes any copy of $b$ at $c_2$.
The resulting count rows have the correct populations and school capacities:
$$
a:(k,3k+1,1),\qquad
b:(2k+1,0,0),\qquad
d:(0,0,2k+1).
$$
Their normalized limits are the displayed matrices. The two subsequential limits differ, so universal existence is conclusively disproved.
Lemma 2 correctly uses the common copy-index ordering. An inversion within a type produces a blocking pair, so stable assignments must be canonical. Conversely, in the canonical construction, copies of the same type assigned to a preferred school have earlier indices than copies assigned below it. The displayed conditions therefore exclude vacancies, lower-priority types, and lower-priority copies.
The domain is explicitly integer count matrices; nonnegativity, population totals, and capacity inequalities are all present. Zero populations and zero capacities do not invalidate the characterization.
The prefix inequalities correctly characterize individual weak preference between canonical assignments with identical populations.
Lemma 3 supplies a direct student-optimality proof. At the first rejection of an edge belonging to a fixed full stable matching, the held student selected in the argument must prefer the rejecting school to her assignment in that matching. Otherwise, an earlier rejection of another matching edge would have occurred. The resulting blocking pair is valid.
The uniqueness conclusion follows from equality of all prefix counts. Thus the formula characterizes the DA count matrix without expanding students.
The population predicate imposes precisely replication integrality. Denominator clearing makes feasibility a formula with fixed integer coefficients; no variable-variable multiplication occurs.
The initialization predicate both witnesses attainment of $Q$ and bounds every feasible coordinate by $Q$. It therefore specifies the correct maximum and enforces nonempty feasibility.
In the path predicate, nonnegative $s,b$ and $b<m$ specify the quotient and remainder of the reduction count. The conditions correctly reduce the first $b$ schools one additional time. The restriction
$$
k\le mQ-r
$$
keeps total capacity at least the population, matching the hypotheses of Lemma 3.
The final universal condition excludes every earlier feasible stage. All quantified stage indices are nonnegative under the declared convention. Together with the termination argument, this establishes Proposition 4.
Expansion introduces only a constant number of copies of the displayed predicates. The stated formula-size bound is a valid polynomial upper bound in the support encoding. No dependence on the number of possible unsupported types or on an expanded replication population is introduced.
Corollary 5.2 of the cited paper provides a computable finite union of hybrid linear sets with linearly independent period sets, together with the stated form of running-time bound. Its parameter measuring coefficients includes constants as well. The required dimension condition is satisfied because $G$ has at least the coordinates $r$ and one allocation entry. Its integer coefficients, Boolean operations, and quantifiers fall within the theorem’s scope. [Chistikov, Haase, and Mansutti, Corollary 5.2](https://wrap.warwick.ac.uk/id/eprint/166499/1/WRAP-Geometric-decision-procedures-VC-dimension-2022.pdf)
Minor issue: Lemma 5 must restrict its assertions to nonempty linear components. As written, an empty component is contained in any graph, but its periods need not satisfy the conclusions. For example,
$$
B=\varnothing,\qquad P=\{(0,1)\}
$$
generates the empty set, yet its period has zero first coordinate and is nonzero.
This does not undermine the application: splitting into individual bases removes such components, and the algorithm explicitly discards empty components. The minimum clarification is to state the nonemptiness hypothesis in Lemma 5.
For nonempty components, the proof is correct. Negative period coordinates contradict containment in the nonnegative orthant; functionality excludes nonzero periods with zero first coordinate; and comparing the two displayed points forces positive-first-coordinate periods to be collinear. Linear independence then permits at most one period.
On each ray, the normalized output has precisely the stated rational slope plus a constant matrix divided by $r$. Every ray therefore produces its claimed accumulation point.
Conversely, a convergent subsequence tending to infinite replication sizes avoids the finite exceptional set and has an infinite further subsequence on one ray. This proves that no additional accumulation points occur.
Distinct slopes prevent convergence. Equal slopes give the uniform stated $O(1/r)$ bound outside a finite set, proving convergence along all admissible integers.
The least-common-multiple argument correctly yields eventual residue classes. Overlapping rays on a residue have affine expressions agreeing at infinitely many replication sizes, which forces agreement of both slope and intercept.
The algorithm consequently decides convergence and computes an existing limit exactly. The parameters of the cited theorem are bounded by formula length, and the polynomial formula-size bound supports the claimed triply exponential upper bound in $m,\tau,\ell,L$. Scanning the explicit decomposition and comparing rational slopes preserves that bound.
The one-school conclusion follows directly from the allocation constraints.
For two schools, rewriting each component as
$$
[1-\beta_j,\beta_j]
$$
is correct. These intervals are nested because their centers coincide and $\beta_j\ge1/2$. Their union and its integer endpoints therefore have the stated form.
Initial capacity bounds imply both upper and lower feasibility bounds once everyone is assigned, so QRDA returns initially.
At most one school has excessive first-choice demand. In that case, its retained applicants are exactly its highest-priority first-choice applicants, and the other school’s resulting demand is $1-h_r\le h_r$. The allocation formula and its continuity argument are valid.
Prefix sums obtained by scanning priorities support the claimed arithmetic-operation count. Common denominators and intermediate rational values have $O(L)$ bits, supporting the stated elementary bit bound.
The only major unresolved requirement is the general complexity classification. Decidability with a triply exponential upper bound proves neither polynomial-time solvability nor NP-hardness. This is task incompleteness, not a hidden error in the established results. Minimum feedback is to retain the partial claim, qualify Lemma 5 for nonempty components, and provide a justified general classification before claiming completion of the full task.
⟨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.