Answer: —
Theorem 5.7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe time complexity of TTC-M is O(|S| · |C|) under the assumption that we can check in O(1) time whether ν ∈F for an M-convex set F and a vector ν on C.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given schools \(C\), a finite supported distribution \(\mu\) over types \(t=(\omega_t,\succ_t)\), and a rational per-capita quota polytope \(P\), suppose \(F_N=\{v\in\mathbb{Z}_{\ge 0}^{|C|}:\sum_{c\in C}v_c=N,\ v/N\in P\}\) is M-convex and the replicated endowment load is feasible for each admissible \(N\). Replicate each type \(t\) into \(N\mu_t\) students, draw a uniform common priority order, and run TTC-M. For \(a_N(t,c)\), the expected number of type-\(t\) students assigned to \(c\), divided by \(N\), determine whether \(a_N\) converges along admissible replication sizes and, if it does, compute its limiting matrix within additive error \(\epsilon\) in time polynomial in \(m,\tau,L,\log(1/\epsilon)\).
Let \(C\) be a nonempty set of \(m\) schools. A society is given by its support: the list of the \(\tau\) types \(t=(\omega_t,\succ_t)\) with positive mass \(\mu_t\), each mass a binary rational, with \(\sum_t\mu_t=1\); \(\omega_t\in C\) and \(\succ_t\) is a strict ranking of all schools. Here \(\tau\) is the support size, not the number of possible types.
An explicitly given rational inequality system defines a polytope \(P\subseteq\{x\in\mathbb R_{\ge0}^{m}:\sum_c x_c=1\}\). Let \(L\) be the total bit length of the society and this system.
A positive integer \(N\) is admissible exactly when every \(N\mu_t\) is integral. Define \(F_N=\{v\in\mathbb Z_{\ge0}^{m}:\sum_c v_c=N,\ v/N\in P\}\). Promise that, for every admissible \(N\), \(F_N\) is M-convex and \(Ne\in F_N\), where \(e_c=\sum_{t:\omega_t=c}\mu_t\).
M-convexity means that for \(u,v\in F_N\) and \(i\) with \(u_i<v_i\), some \(j\) with \(u_j>v_j\) satisfies \(u+\chi_i-\chi_j\in F_N\) and \(v-\chi_i+\chi_j\in F_N\), where \(\chi_c\) is the unit vector for school \(c\).
For each admissible \(N\), create \(N\mu_t\) distinct students of each type and draw one uniform permutation of all students as their common priority order, fixed throughout TTC-M.
TTC-M starts with all students unassigned and all schools active. At each round, let \(v\) count finalized assignments together with the original endowments of unassigned students; an unassigned student \(s\) is acceptable to school \(c\) exactly when \(v+\chi_c-\chi_{\omega(s)}\in F_N\).
Permanently remove schools with no acceptable unassigned student. Each remaining school points to its highest-priority acceptable student, giving its own endowment holders precedence over all others and using the common order within both groups; every unassigned student points to her favorite remaining school.
Simultaneously execute all directed cycles, assigning each participating student to the school she points to and removing those students. Schools remain unless removed by the preceding rule. Repeat until all students are assigned.
Define \(a_N(t,c)=N^{-1}\mathbb E[\#\{\text{type-}t\text{ students assigned to }c\}]\), with expectation over the permutation. Approximation error is the maximum absolute error over matrix entries; accuracy is \(\epsilon=2^{-k}\) for a positive integer \(k\).
Does \(a_N\) converge as \(N\to\infty\) through all admissible sizes for every promised instance?
Is deciding convergence and, when a limit exists, approximating it within \(\epsilon\) solvable in time polynomial in \(m,\tau,L,\log(1/\epsilon)\), or is this computational problem NP-hard?
For a fixed priority order, discrete TTC-M runs in \(O(Nm)\) time with constant-time feasible-vector membership tests ([Suzuki–Tamura–Yokoo](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p50.pdf)); the [2023 full version](https://www.mdc.e.u-tokyo.ac.jp/wp/wp-content/uploads/2023/09/UTMD-056.pdf) retains this guarantee.
[Leshno–Lo](https://www.columbia.edu/~iyl2104/Leshno,Lo%20-%20TTC%20cutoffs.pdf) characterize continuum school-choice TTC using trade-balance and capacity equations; their model uses school capacities and priorities rather than the general endowment-dependent feasibility tests above. No result settling this precise replication-limit problem was located.
The two general questions remain unresolved here. I prove an additional subclass that allows arbitrarily many schools and endowment populations.
Theorem. Suppose every supported type has the same strict ranking of schools. Then:
The proof includes a general consequence of M-convexity: a school with no acceptable remaining student cannot become acceptable after a feasible continuation. Different rankings remain outside the convergence argument.
For $S\subseteq C$, write $x(S)=\sum_{c\in S}x_c$. Define
$$ f(S)=\max_{x\in P}x(S). $$
Admissible sizes exist because all masses are rational. The promise $Ne\in F_N$ therefore implies $e\in P$. Thus $P$ is nonempty and compact.
Lemma 1. The function $f$ is rational-valued, monotone, and submodular, with $f(\varnothing)=0$ and $f(C)=1$. Moreover,
$$ P=\left\{ x\in\mathbb R_{\ge 0}^{m}: x(C)=1,\quad x(S)\le f(S)\text{ for every }S\subseteq C \right\}. $$
First, every edge of $P$ is parallel to an exchange direction $\chi_i-\chi_j$.
Indeed, let $[p,q]$ be an edge. Its endpoints are rational. Choose an admissible $N$ clearing their denominators, and put $u=Np$, $v=Nq$. Both belong to $F_N$. Choose $i$ with $u_i<v_i$. M-convexity supplies $j$ with $u_j>v_j$ such that
$$ u'=u+\chi_i-\chi_j\in F_N, \qquad v'=v-\chi_i+\chi_j\in F_N. $$
Let $w$ expose the edge $[u,v]$ of $NP$, with maximum value $M$. Since
$$ w\cdot u'+w\cdot v' =w\cdot u+w\cdot v =2M, $$
and both summands on the left are at most $M$, both are equal to $M$. Hence $u'$ lies on the edge. Its nonzero displacement from $u$ is $\chi_i-\chi_j$, proving the assertion.
Fix an ordering $\pi=(\pi_1,\ldots,\pi_m)$. Every weight vector satisfying
$$ w_{\pi_1}>w_{\pi_2}>\cdots>w_{\pi_m} $$
has a unique maximizing vertex of $P$: otherwise its maximizing face would contain an edge, whereas no exchange-direction edge is orthogonal to such a weight vector.
That maximizing vertex is locally constant throughout the strict-order region. To justify this, at a weight with a unique maximizing vertex, its advantage over every other vertex is strictly positive; there are only finitely many vertices. The strict-order region is connected, so the maximizing vertex is constant there. Denote it by $x^\pi$.
For the prefixes $S_k=\{\pi_1,\ldots,\pi_k\}$, approach the indicator of $S_k$ by weights in this region. Passing to the limit in the maximizing inequalities gives
$$ x^\pi(S_k)=f(S_k). $$
For diminishing returns, take $A\subseteq B$ and $i\notin B$. Choose $\pi$ beginning with $A$, then $i$, then $B\setminus A$. Its prefix identities imply
$$ \begin{aligned} f(A\cup\{i\})-f(A) &=x^\pi_i\\ &=f(B\cup\{i\})-x^\pi(B)\\ &\ge f(B\cup\{i\})-f(B). \end{aligned} $$
These inequalities imply submodularity explicitly as follows. Enumerate $X\setminus Y$ as $i_1,\ldots,i_q$. At step $\ell$, compare adding $i_\ell$ to
$$ (X\cap Y)\cup\{i_1,\ldots,i_{\ell-1}\} $$
with adding it to
$$ Y\cup\{i_1,\ldots,i_{\ell-1}\}. $$
Summing the diminishing-return inequalities yields
$$ f(X)-f(X\cap Y)\ge f(X\cup Y)-f(Y). $$
Monotonicity follows from nonnegativity of vectors in $P$. Rationality follows because each maximum is attained at a rational vertex.
Finally, suppose $z\ge 0$, $z(C)=1$, and $z(S)\le f(S)$ for every $S$. For any $w$, choose $\pi$ sorting its coordinates in nonincreasing order. Summation by parts gives
$$ \begin{aligned} w\cdot z &=w_{\pi_m} +\sum_{k=1}^{m-1} (w_{\pi_k}-w_{\pi_{k+1}})z(S_k)\\ &\le w_{\pi_m} +\sum_{k=1}^{m-1} (w_{\pi_k}-w_{\pi_{k+1}})f(S_k)\\ &=w\cdot x^\pi. \end{aligned} $$
Thus no linear functional strictly separates $z$ from $P$. The separating-hyperplane theorem applies because $P$ is nonempty, compact, and convex, and gives $z\in P$. This proves the representation. $\square$
The following lemma does not require a common ranking.
Lemma 2. Fix an admissible $N$ and a feasible provisional count vector $v\in F_N$. Let $R$ be the set of endowment schools represented among the remaining students. Suppose school $d$ has no acceptable remaining student. Then every $z\in F_N$ satisfying
$$ z_j\ge v_j\qquad(j\notin R) $$
also satisfies $z_d\le v_d$.
Consequently, along any feasible continuation of assignments, $d$'s provisional count stays fixed and $d$ cannot become acceptable again.
First, $d\notin R$: a remaining holder of $d$ would be acceptable to $d$, since assigning her there leaves $v$ unchanged.
Suppose $z_d>v_d$. Apply M-convexity to $v,z$ with receiving coordinate $d$. It supplies $j$ such that
$$ v_j>z_j, \qquad v+\chi_d-\chi_j\in F_N. $$
The inequality $v_j>z_j$ forces $j\in R$. Therefore a remaining student endowed with $j$ is acceptable to $d$, contradicting the hypothesis.
For the consequence, let $w$ be a later feasible provisional vector. No remaining student at the earlier state had an endowment outside $R$, so
$$ w_j\ge v_j\qquad(j\notin R). $$
In particular $w_d\ge v_d$, while the first part gives $w_d\le v_d$. Hence $w_d=v_d$.
If a remaining student endowed with $i$ were now acceptable to $d$, then $i\in R$ and
$$ z=w+\chi_d-\chi_i\in F_N. $$
This $z$ still satisfies $z_j\ge v_j$ outside $R$, but $z_d=v_d+1$, contradicting the first part. $\square$
Assume henceforth that every supported type has ranking
$$ c_1\succ c_2\succ\cdots\succ c_m. $$
There is exactly one supported type for each school $d$ with $e_d>0$; denote it by $t_d$. Its mass is $e_d$.
While the highest-ranked active school is $c$, every remaining student points to $c$. Consequently the only directed cycle is
$$ c\longrightarrow s\longrightarrow c, $$
where $s$ is the student selected by $c$.
School $c$ first assigns all its remaining endowment holders to itself. Every such holder is acceptable, and endowment holders have precedence. These assignments leave the provisional vector unchanged.
Afterward, school $c$ repeatedly assigns the highest-priority acceptable remaining student to itself, until none is acceptable.
Thus TTC-M proceeds in destination stages, in the common ranking order. A school removed before its stage has no remaining holder, and Lemma 2 ensures that it remains unable to accept anyone. We may therefore include such a school as a stage making no assignments.
All provisional vectors in this description remain feasible: each cycle assigns one student, and its feasibility is exactly the acceptability test.
Use normalized quantities. Immediately after $c$'s remaining holders have been assigned, let:
For an import vector $y\in\mathbb R_{\ge 0}^{D}$, define
$$ x(y)=v+y(D)\chi_c-\sum_{d\in D}y_d\chi_d. $$
The feasible import polytope is
$$ Q(v,r,c)= \left\{ y\ge 0: y_d\le r_d\text{ for }d\in D,\quad x(y)\in P \right\}. $$
Here $r_d\le v_d$, since provisional counts include all remaining endowments.
Lemma 3. The polytope $Q(v,r,c)$ is downward closed: if $y\in Q(v,r,c)$ and $0\le z\le y$, then $z\in Q(v,r,c)$.
The bounds $0\le z_d\le r_d$ imply $x(z)\ge 0$, and $x(z)(C)=1$.
For a subset $S$ not containing $c$,
$$ x(z)(S)=v(S)-z(S\cap D)\le v(S)\le f(S). $$
For a subset $S$ containing $c$,
$$ x(z)(S) =v(S)+z(D\setminus S) \le v(S)+y(D\setminus S) =x(y)(S) \le f(S). $$
Lemma 1 now gives $x(z)\in P$. $\square$
Write an input inequality as $B_jx\le b_j$. Substitution gives
$$ \sum_{d\in D}(B_{j,c}-B_{j,d})y_d \le b_j-B_jv. $$
Include also the bounds $y_d\le r_d$. This produces a polynomial-size system
$$ Q(v,r,c)=\{y\ge 0:a_j\cdot y\le s_j\}. $$
Every $s_j$ is nonnegative because $0\in Q(v,r,c)$.
Replace each $a_j$ by its coordinatewise positive part $A_j$. This preserves $Q$. Indeed, for $y\in Q$, set to zero the coordinates where $a_j$ is negative, obtaining $z\le y$. By Lemma 3, $z\in Q$, so
$$ A_j\cdot y=a_j\cdot z\le s_j. $$
Conversely, for $y\ge 0$,
$$ a_j\cdot y\le A_j\cdot y, $$
so every strengthened inequality implies the original one. Hence
$$ Q(v,r,c)=\{y\ge 0:A_j\cdot y\le s_j\}, \qquad A_j\ge 0. $$
For a fixed destination $c$, the coefficient matrix $A$ depends only on the input inequalities and $D$. The right sides depend affinely on $v,r$.
Give each distinct student an independent uniform priority in $[0,1]$, with smaller values having higher priority. Almost surely these values are distinct, and their order is a uniform permutation.
Within each endowment population, previously assigned students always form a priority prefix. Whenever a destination accepts students from origin $d$, acceptability is identical for all remaining students of that origin, and it chooses its highest-priority remaining holder before any lower-priority holder.
The import stage at $c$ can therefore be implemented by scanning the entire priority order once, skipping previously assigned students:
Once an origin fails this test, it cannot pass later in that stage. A failed test has a witness row
$$ s_j-A_j\cdot y<A_{j,d}/N, $$
and subsequent imports only increase coordinates of $y$. Thus the violation persists.
The scanner consequently selects exactly the same students as repeated highest-priority acceptable selection.
Maintain normalized provisional counts $v$, remaining endowment masses $r$, and an assignment matrix $M$, initially
$$ v=e,\qquad r=e,\qquad M=0. $$
Process destinations $c_1,\ldots,c_m$ in order.
For destination $c$:
$$
h_d=1-\frac{r_d}{e_d}.
$$
This is the fraction of origin $d$ already consumed.
For a feasible $y$, define
$$ U(y)= \left\{ d\in D: A_{j,d}=0 \text{ whenever }A_j\cdot y=s_j \right\}. $$
Thus $U(y)$ consists of coordinates not blocked by a tight row. Define the rates
$$ \lambda_d= \begin{cases} e_d,&d\in U(y)\text{ and }h_d\le u,\\ 0,&\text{otherwise}. \end{cases} $$
When $u<1$, take
$$ \Delta= \min\left( \{1-u\} \cup \{h_d-u:h_d>u\} \cup \left\{ \frac{s_j-A_j\cdot y}{A_j\cdot\lambda}: A_j\cdot\lambda>0 \right\} \right), $$
and update
$$ y\leftarrow y+\Delta\lambda, \qquad u\leftarrow u+\Delta. $$
Repeat until $u=1$. Then add $y_d$ to $M(t_d,c)$ and update
$$ r_d\leftarrow r_d-y_d\qquad(d\in D), $$
$$ v\leftarrow v+y(D)\chi_c-\sum_{d\in D}y_d\chi_d. $$
A tight row has zero product with $\lambda$: every coordinate where that row has a positive coefficient is excluded from $U(y)$. Thus every ratio included in the minimum has positive numerator and denominator.
The minimum preserves all inequalities until the next event. At a new boundary event, a newly tight row with positive product with the preceding rate blocks at least one previously unblocked coordinate. Tight rows remain tight afterward because $y$ is nondecreasing and feasible.
There are at most $|D|$ blocking events and at most $|D|$ activation times $h_d$. Including the final interval, each destination therefore has at most $2|D|+1$ phases.
The algorithm is well-defined even when several rows become tight simultaneously: all of them are included in the next computation of $U(y)$.
Let $H_{d,N}(u)$ count students endowed with $d$ whose uniform priority is at most $u$. Define
$$ E_N= \max_{d:e_d>0} \sup_{0\le u\le 1} \left| \frac{H_{d,N}(u)}{N}-e_du \right|. $$
For fixed $u$,
$$ \mathbb E[H_{d,N}(u)]=Ne_du, $$
$$ \operatorname{Var}(H_{d,N}(u)) =Ne_du(1-u)\le N/4. $$
On a grid with $K+1$ points, Chebyshev's inequality and a union bound give
$$ \Pr\left( \max_{d,\ell} \left| \frac{H_{d,N}(\ell/K)}{N}-e_d\ell/K \right|>\eta \right) \le \frac{m(K+1)}{4N\eta^2}. $$
Between grid points, monotonicity of $H_{d,N}$ increases the bound by at most $1/K$. Choosing $K$ first and then letting $N$ grow proves
$$ E_N\longrightarrow 0 \quad\text{in probability}. $$
Consider a deterministic sequence of priority realizations with $E_N\to 0$. Suppose the normalized parameters at a stage converge:
$$ v_N\to v,\qquad r_N\to r. $$
Then the stage right sides satisfy $s_N\to s$.
For origin $d$, let
$$ k_{d,N}=e_d-r_{d,N}, \qquad h_{d,N}=\frac{k_{d,N}}{e_d}. $$
The already assigned students of that origin form a priority prefix of normalized size $k_{d,N}$.
Let $T_{d,N}$ be the priority of its first rejected remaining student in this stage; set $T_{d,N}=1$ if no such rejection occurs. Let $y_{d,N}(u)$ be the imports from $d$ after scanning priorities up to $u$.
Because all students before the first rejection are accepted and all later students of that origin are skipped,
$$ \left| y_{d,N}(u)- \left( \frac{H_{d,N}(\min\{u,T_{d,N}\})}{N} -k_{d,N} \right)_+ \right| \le \frac1N. $$
The possible discrepancy is the first rejected student itself.
Pass to a subsequence on which every $T_{d,N}$ converges to $T_d$. Uniform empirical convergence then gives uniform convergence of imports to
$$ y_d(u)=e_d\bigl(\min\{u,T_d\}-h_d\bigr)_+, \qquad h_d=1-\frac{r_d}{e_d}. $$
This trajectory is absolutely continuous and coordinatewise nondecreasing. Finite feasibility and convergence of the right sides imply
$$ Ay(u)\le s. $$
If $T_d<1$, a rejecting finite test has a witness row satisfying
$$ 0\le s_{j,N}-A_j\cdot y_N(T_{d,N}) <A_{j,d}/N, \qquad A_{j,d}>0. $$
There are finitely many rows, so pass to a further subsequence fixing that witness. Uniform convergence gives
$$ A_j\cdot y(T_d)=s_j. $$
That row remains tight thereafter. Consequently, every origin whose limiting rejection time has passed is blocked by a tight row.
A tight row remains tight because its left side is nondecreasing and cannot exceed its right side. For almost every time after it becomes tight,
$$ A_j\cdot y'(u)=0. $$
Since both $A_j$ and $y'(u)$ are nonnegative, every coordinate blocked by that row has derivative zero.
On the other hand, if $u>h_d$ and $d$ is unblocked, then $u<T_d$. Otherwise the rejection witness just established would make $d$ blocked. The explicit formula for $y_d$ therefore gives derivative $e_d$.
Thus, for almost every $u$,
$$ y_d'(u)= \begin{cases} e_d,&u>h_d\text{ and }d\in U(y(u)),\\ 0,&\text{otherwise}. \end{cases} $$
This equation has a unique feasible nondecreasing trajectory starting at zero. To verify uniqueness, between activation times and new tight rows, both the activated origins and the unblocked origins are constant. Hence the derivative is constant. The first possible next event is exactly the minimum defining $\Delta$ in Section 4. At that event, tight rows remain tight and all coordinates they block are excluded. Induction over the finitely many events identifies the trajectory uniquely with the phase algorithm.
Every convergent subsequence of rejection times consequently produces the same stage output. Compactness of those times implies convergence of the full stage sequence.
Initially $v_N=r_N=e$. Applying the one-stage result inductively through the finitely many destinations proves:
Every deterministic sequence of priority realizations with $E_N\to 0$ has normalized assignment matrices converging to the matrix $M$ computed in Section 4.
This implies convergence in probability for random priorities. Otherwise, along a subsequence, the probability of a fixed positive assignment error would stay bounded away from zero. Since $E_N\to 0$ in probability, one could select realizations along a further subsequence having both $E_N\to 0$ and that positive assignment error, contradicting the deterministic statement.
Each normalized assignment entry lies in $[0,1]$. For any entry $Z_N$ and $\delta>0$,
$$ \mathbb E|Z_N-M(t,c)| \le \delta+\Pr(|Z_N-M(t,c)|>\delta). $$
The right side tends to at most $\delta$, and $\delta$ is arbitrary. Therefore
$$ a_N(t,c)\longrightarrow M(t,c) $$
through all admissible sizes.
The algorithm uses at most $m$ destination stages and $O(m)$ phases per stage.
Clear denominators in each input inequality before constructing its stage rows. The resulting nonnegative coefficients $A_{j,d}$ are integers with polynomial bit length. Write the endowment masses with a common denominator,
$$ e_d=\frac{n_d}{D_0}, $$
where $D_0$ and all $n_d$ have bit lengths polynomial in $L$.
Every rate vector has the form $\lambda=q/D_0$, where each $q_d$ is either $n_d$ or zero. At a boundary event,
$$ A_j\cdot\lambda=\frac{A_j\cdot q}{D_0}, $$
and the nonzero integer $A_j\cdot q$ has polynomial bit length. Activation times use
$$ h_d=1-\frac{D_0r_d}{n_d}. $$
Each update is therefore affine in the current rational state, with rational coefficients of polynomial bit length. Its denominator introduces only polynomial-bit factors of the forms $n_d$ and $A_j\cdot q$.
Across $O(m^2)$ updates, a common denominator accumulates a product of only polynomially many such factors, so its bit length remains polynomial. All assignment masses, residual masses, scanner times, and normalized counts are bounded between zero and one; their reduced numerators consequently have polynomial bit length as well.
Constructing the systems, comparing event times, and performing these exact updates takes polynomial time in $m,\tau,L$. Thus the limit can be returned exactly. Rounding it to entrywise accuracy $2^{-k}$ takes time polynomial in $m,\tau,L,k$.
There is also an exact finite characterization of the school totals.
Proposition 4. Under a common ranking, the final count vector is the lexicographically greatest element of $F_N$, with coordinates ordered as $c_1,\ldots,c_m$.
At the end of destination $c_\ell$'s stage, all earlier destination counts are finalized, no holder of $c_\ell$ remains, and $c_\ell$ has no acceptable remaining student.
Suppose a feasible vector $z\in F_N$ agrees with the current vector $v$ on earlier coordinates but has $z_{c_\ell}>v_{c_\ell}$. M-convexity supplies $j$ with
$$ v_j>z_j, \qquad v+\chi_{c_\ell}-\chi_j\in F_N. $$
The coordinate $j$ cannot be earlier, because those coordinates agree, and cannot be $c_\ell$. It is therefore a later school. No student has yet been finalized at any later school, so $v_j>0$ means a remaining holder of $j$ exists. That holder is acceptable to $c_\ell$, a contradiction.
Thus each stage maximizes its coordinate subject to the preceding coordinates. This is precisely lexicographic maximization. $\square$
This vector is unique and therefore independent of priority.
Its normalized limit has a simple geometric description. Let
$$ w_{c_\ell}=m-\ell. $$
By the strict-order argument in Lemma 1, $w$ has a unique maximizing vertex $p$ of $P$, and that vertex is the lexicographic maximum of $P$.
To relate this to $F_N$, observe that every edge of $\operatorname{conv}(F_N)$ also has an exchange direction. The exposing-functional argument from Lemma 1 applies directly to its integer endpoints using M-convexity. The same strict-order and prefix-maximization argument shows that the lexicographic maximum of $F_N$ maximizes $w$ over $F_N$.
Choose an integer $D$ clearing the denominators of $p$ and all masses. For an admissible $N$, put
$$ K=D\left\lfloor\frac ND\right\rfloor, \qquad u_N=Kp+(N-K)e. $$
Both summands are integral: $K$ clears the denominators of $p$, and $N-K$ is admissible. Also,
$$ \frac{u_N}{N} =\frac KNp+\left(1-\frac KN\right)e\in P. $$
Hence $u_N\in F_N$ and $u_N/N\to p$. The maximizing property implies that any subsequential limit of the normalized final vector maximizes $w$ over $P$. Uniqueness forces that limit to be $p$.
Thus
$$ \sum_t M(t,c)=p_c. $$
The aggregate limit is a unique vertex even though individual transfer entries can depend on priority at finite sizes.
Let the common ranking be $A\succ B\succ C$, with
$$ e=(1/5,\,2/5,\,2/5), $$
and let
$$ P= \left\{ x\ge 0: x_A+x_B+x_C=1,\quad x_A\le 1/2,\quad 3/10\le x_B\le 2/5 \right\}. $$
This instance satisfies the promise. For every admissible $N$, its integer feasible vectors have a fixed sum and coordinatewise integer lower and upper bounds. If $u_i<v_i$, choose $j$ with $u_j>v_j$. Both exchanged vectors remain within those bounds, establishing M-convexity. The endowment vector is feasible.
At destination $A$, its own mass $1/5$ is assigned first. Origins $B$ and $C$ initially import at rate $2/5$ each. At scanner time $1/4$, each has exported $1/10$. The lower bound on $B$ then blocks further exports from $B$. Origin $C$ continues until scanner time $1/2$, when $A$ reaches $1/2$.
At destination $B$, its remaining own mass $3/10$ is assigned first. Origin $C$, whose priority prefix has reached $1/2$, exports another $1/10$ before $B$ reaches its upper bound $2/5$. The remaining $1/10$ stays at $C$.
With rows ordered by endowment and columns by destination, the limit is
$$ M= \begin{pmatrix} 1/5&0&0\\ 1/10&3/10&0\\ 1/5&1/10&1/10 \end{pmatrix}. $$
Finite type matrices need not equal this matrix or be priority-independent. For example, at $N=10$, if three $C$-holders precede every $B$-holder in the relevant priority order, those three fill $A$'s remaining places, and all four $B$-holders stay at $B$. Nevertheless, the aggregate final counts are always $(5,4,1)$.
The common-ranking assumption makes every round have a single cycle and turns the mechanism into destination stages with monotone import coordinates. With different rankings, multiple cycles can involve different destinations at once. The scanner proof above does not identify their limiting interaction.
Accordingly, this argument establishes neither convergence for every promised instance nor a polynomial algorithm or hardness reduction for the general computational problem.
⟨structured verdict parsed — rendered above⟩
The output establishes a rigorous common-ranking subclass, subject to one minor edge-case correction. It does not resolve either general question in USER_TASK, and it explicitly acknowledges that limitation.
The overall status is partial. No central false step or substantive gap was found in the subclass proof.
Lemma 1 is valid.
The resulting representation is used theoretically; the proposed algorithm does not enumerate its exponentially many subset inequalities.
Lemma 2 is valid.
A remaining holder of $d$ would be acceptable to $d$, so $d\notin R$. If $z_d>v_d$, M-convexity produces a donor coordinate $j$ with $v_j>z_j$. The assumed inequalities outside $R$ force $j\in R$, producing the stated contradiction.
For a later feasible provisional vector, coordinates outside the earlier set $R$ cannot decrease: no subsequently assigned student has an original endowment there. This justifies the application of the lemma to the continuation. The proposed subsequent acceptable transfer also preserves those outside-coordinate inequalities, so the persistence conclusion follows.
The result is appropriately stated for feasible continuations.
The destination-stage description is correct.
While students remain, every active endowment school of a remaining student has an acceptable holder. Thus a highest-ranked active school exists and points to a student. Since every student points to that school, the only cycle is its two-vertex cycle.
Endowment precedence assigns its remaining holders first. Their assignments leave the provisional vector unchanged. Subsequent assignments import one acceptable student at a time and preserve feasibility.
A school removed before its nominal stage has no remaining holders. Lemma 2 justifies treating it as a stage with no assignments.
Under a common ranking, a supported type is determined by its endowment school, so indexing the supported types by positive-mass endowment schools is valid.
Lemma 3 and the positive-coefficient transformation are correct.
For $0\le z\le y$, the condition $r_d\le v_d$ ensures nonnegativity of $x(z)$. The two subset cases correctly establish all inequalities from Lemma 1, proving downward closure.
Replacing a row by its coordinatewise positive part preserves the entire feasible set:
The scanner argument also holds. Acceptability is identical within each remaining origin population. Therefore previously assigned students form a priority prefix within each origin. With nonnegative coefficients, a failed import test remains failed throughout that stage. The scanner consequently reproduces repeated highest-priority acceptable selection.
The algorithm is feasible, terminates, and has the claimed polynomial phase count.
A tight row excludes every coordinate on which it has a positive coefficient. Hence its product with the current rate is zero. Every row ratio included in the event minimum therefore has positive numerator and denominator.
Each update preserves feasibility. A newly tight row reached with positive rate blocks at least one previously unblocked coordinate. Tight rows remain tight, so blocked coordinates cannot become unblocked. There are consequently at most $|D|$ blocking events and at most $|D|$ activation times per destination.
Simultaneous events are handled by recomputing the blocked set using all tight rows. Zero residual masses are handled by the included upper-bound rows.
The convergence argument is sound.
The expectation, variance bound, Chebyshev bound, and union bound are correct. Monotonicity between grid points adds at most $1/K$. Choosing a sufficiently fine fixed grid and then taking $N$ large proves convergence of $E_N$ in probability.
The first-rejection representation correctly describes imports from each origin, with discrepancy at most $1/N$. Uniform empirical convergence and convergence of rejection times establish uniform convergence of the import trajectories.
Feasibility passes to the limit because the coefficient matrix is fixed and the right sides converge. A rejected finite transfer has a witness row with positive coefficient on its origin and slack less than that coefficient divided by $N$. Passing to a fixed-row subsequence therefore establishes a tight limiting witness.
Nonnegative coefficients and nondecreasing feasible trajectories ensure that tight rows remain tight and blocked coordinates have zero derivative almost everywhere. Activated, unblocked coordinates have derivative $e_d$ by the explicit rejection-time formula.
The uniqueness argument is sufficient: between activation and blocking events the derivative is fixed, and feasibility determines the next boundary event. Permanence of blocking prevents additional behavior at a boundary. Thus every subsequential limit agrees with the finite phase algorithm.
Induction applies because the output state of one stage supplies convergent input parameters for the next. The deterministic-sequence assertion implies convergence in probability by the stated contradiction argument.
Every entry lies in $[0,1]$, so the final expectation inequality correctly yields entrywise convergence of $a_N$ through all admissible sizes.
The polynomial-time claim is supported for the common-ranking subclass.
Clearing input-row denominators produces integer coefficients of polynomial bit length. The common denominator of the endowment masses also has polynomial bit length.
The possible rates use only the fixed endowment numerators. Event updates are affine rational operations whose coefficient denominators introduce polynomial-bit factors of the specified forms. Across polynomially many updates, a shared denominator can therefore accumulate only polynomial total bit length. Bounded state values then give polynomial-bit numerators.
Construction of the systems, event comparisons, and exact arithmetic consequently take polynomial time. Producing accuracy $2^{-k}$ also has the claimed polynomial dependence on $k$.
Proposition 4 and its limiting characterization are valid, with one minor wording error.
At the end of a destination stage, earlier coordinates are finalized. If a feasible vector agrees on those coordinates and increases the current coordinate, M-convexity supplies a donor at a later school. No student has yet been assigned to a later destination, so a positive provisional count there identifies a remaining holder. This contradicts completion of the current stage.
The induction therefore establishes lexicographic maximality and priority independence of school totals.
The exchange-edge argument also applies to $\operatorname{conv}(F_N)$, so its lexicographic maximum maximizes the stated strictly ordered weight vector. The constructed vectors $u_N$ establish approximation to the unique maximizing vertex of $P$.
Minor issue: The sentence asserting that $N-K$ “is admissible” is false when $D$ divides $N$, because then $N-K=0$, whereas admissibility is defined only for positive integers.
Minimum clarification: State that $(N-K)e$ is integral, treating $N-K=0$ separately. This is an immediate edge-case correction and does not affect the argument.
The example checks out.
For each admissible size, integer feasibility is described by a fixed sum and rounded coordinate bounds. The stated exchange argument preserves these bounds in both exchanged vectors. The endowment vector satisfies the constraints.
The phase calculations yield exports of $1/10$ from $B$ and $1/5$ from $C$ to $A$, followed by $1/10$ from $C$ to $B$. The displayed matrix has the correct row masses and aggregate destination masses.
The finite example at $N=10$ also correctly demonstrates priority dependence of type assignments while preserving aggregate counts $(5,4,1)$.
The genuine progress consists of the structural and persistence lemmas, plus convergence, exact polynomial computation, and priority-independent school totals under a common ranking.
Two major requirements remain unanswered:
These are acknowledged scope limitations, not hidden errors. To resolve USER_TASK, a further output must explicitly settle both general questions. The present subclass write-up needs only the minor zero-remainder clarification.
⟨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.