Answer: Exact computation is polynomial-time in \(m,\tau,L\). Every integral replication scale \(K\) has normalized aggregate TTCR-SS outcome \(x\).
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe time complexity of TTCR-SS is O(|S|· |C|).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Input schools \(C\), types \(T\) with binary-rational masses \(\mu_t\), strict rankings \(\succ_t\), initial schools \(\omega(t)\), and ordered priority blocks with each type contiguous in the induced individual master list, plus rational quotas \(p_c,q_c\) satisfying initial feasibility. Can the paper’s representative, dummy-student, school-state, and cycle rules be batched to compute the exact allocation matrix \(x_{t,c}\) in time polynomial in \(m,\tau,L\), and does that allocation equal the aggregate TTCR-SS outcome on every integral replication of the instance?
Let \(C\) contain \(m\geq1\) schools. A society is given by its support: \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Each type has a strict ranking \(\succ_t\) over \(C\), an initial school \(\omega(t)\), and a position in a strict ordering of contiguous type blocks. Let \(L\) be the total input bit length.
Quotas are binary rationals satisfying \(0\leq p_c\leq\sum_{t:\omega(t)=c}\mu_t\leq q_c\). An allocation has \(x_{t,c}\geq0\), \(\sum_c x_{t,c}=\mu_t\), \(p_c\leq\sum_t x_{t,c}\leq q_c\), and \(x_{t,c}=0\) whenever \(\omega(t)\succ_t c\).
An integral replication at scale \(K\) uses \(K\mu_t\) identical students of type \(t\) and quotas \(Kp_c,Kq_c\), all integers; its strict master list concatenates the ordered type blocks.
Define TTCR-SS on a replication as follows. Initially all students remain and no assignments are finalized. Write \(r_c\) for remaining students initially endowed with \(c\), and \(z_c\) for finalized assignments to \(c\).
A school is minimum if \(r_c>0\) and \(r_c+z_c=Kp_c\), decrementable if \(r_c>0\) and \(r_c+z_c>Kp_c\), maximum if \(r_c=0\) and \(z_c=Kq_c\), and incrementable if \(r_c=0\) and \(z_c<Kq_c\).
Each school with \(r_c>0\) supplies its highest-priority remaining endowed student as representative; each incrementable school supplies a dummy representative only when some school is decrementable. Maximum schools supply none.
Each real representative points to the representative of her favorite represented school. Every dummy points to the highest-priority real representative whose initial school is decrementable.
Execute all directed cycles simultaneously, including self-loops: assign each real student in a cycle to the school of her outgoing neighbor and remove her from the remaining students; dummies receive no assignment. Recompute and repeat until no students remain.
Let \(D\) be the least positive integer clearing all mass and quota denominators, and define \(x_{t,c}\) as the number of type-\(t\) students assigned to \(c\) at scale \(D\), divided by \(D\).
Is exact computation of \(x\) polynomial-time in \(m,\tau,L\), or is it NP-hard? Does the normalized aggregate TTCR-SS outcome equal \(x\) for every integral replication scale \(K\)?
Discrete TTCR-SS has an \(O(nm)\) algorithm for \(n\) explicitly listed students, also stated in the [2017 full version](https://www.researchgate.net/publication/316567382_Strategy-proof_School_Choice_Mechanisms_with_Minimum_Quotas_and_Initial_Endowments). No result settling this exact rational-mass computation or replication agreement was located.
1. Result. Exact computation is polynomial-time in \(m,\tau,L\), and the normalized aggregate outcome equals \(x\) at every integral replication scale \(K\).
The proof gives an exact simulation using at most \(\tau+2m\) batches, regardless of the number of replicated students. It analyzes the rule in the question directly; the corresponding discrete cycle construction appears in the [2017 full version](https://www.researchgate.net/publication/316567382_Strategy-proof_School_Choice_Mechanisms_with_Minimum_Quotas_and_Initial_Endowments).
2. Compressed states and the effect of one round. Fix an integral replication scale \(K\). Write \(P_c=Kp_c\), \(Q_c=Kq_c\), and let \(u_t\) be the number of remaining students of type \(t\). Relabel types so their blocks occur in the order \(1,\ldots,\tau\).
For every school with \(r_c>0\), its representative’s type is
\(\displaystyle h(c)=\min\{t:\omega(t)=c,\ u_t>0\}.\)
Consequently, the representative’s preferences are determined by \(h(c)\). Representatives at different schools have different types, and their relative priorities are determined by their block order. The identities and priorities of individual students within a block therefore do not affect the graph after its vertices are labeled by schools.
Let \(s_c=r_c+z_c\). We first prove the invariant
\(\displaystyle P_c\leq s_c\leq Q_c\quad\text{for every school }c.\)
It holds initially by the input assumptions.
When some school is decrementable, let \(a\) be the school whose real representative has highest priority among representatives of decrementable schools. Every dummy points to \(a\). This has two consequences:
Consider the simultaneous execution of all cycles.
In a cycle containing only real representatives, each participating school loses one remaining endowed student and receives one finalized assignment. Thus its \(s_c\) is unchanged. Incoming edges from outside the cycle contribute no assignments, because their originating students are not executed.
If there is a dummy-containing cycle, let \(b\) denote its dummy’s school. Its structure is
\(\displaystyle b\longrightarrow a\longrightarrow\cdots\longrightarrow b.\)
The school \(a\) loses one remaining endowed student and receives no assignment from its predecessor, which is the dummy. Hence \(s_a\) decreases by one. The empty school \(b\) receives one assignment, so \(s_b=z_b\) increases by one. Every intermediate real school loses one remaining student and receives one assignment. All other cycles preserve their schools’ \(s_c\).
Therefore the only changes to \(s\) are
\(\displaystyle s_a\leftarrow s_a-1,\qquad s_b\leftarrow s_b+1\)
when a dummy-containing cycle exists. Before execution, \(a\) is decrementable and \(b\) is incrementable. Since all quantities are integers,
\(\displaystyle s_a-P_a\geq1,\qquad Q_b-z_b\geq1.\)
These inequalities prove preservation of the invariant.
Whenever students remain, the graph is nonempty and every vertex has one outgoing edge: each real representative can at least point to her own represented school, and every supplied dummy has its specified real successor. A finite graph with one outgoing edge per vertex contains a cycle. Every such cycle contains a real representative, so each round removes at least one student. The discrete procedure consequently terminates.
At termination, \(r_c=0\), and the invariant gives \(P_c\leq z_c\leq Q_c\). Moreover, every assigned student receives a school weakly preferred to her initial school, since that initial school was represented when she chose her outgoing edge. Thus the resulting allocation satisfies all constraints in the question.
3. An exact batching lemma. At any nonterminal compressed state, construct the graph on school labels and identify all its cycles.
Let \(H\) be the set of schools whose real representatives lie on cycles. For \(c\in H\), let \(f(c)\) be its outgoing neighbor’s school. The preceding argument shows \(H\neq\varnothing\).
Define a positive integer batch length \(B\) as follows.
If no cycle contains a dummy, set
\(\displaystyle B=\min_{c\in H}u_{h(c)}.\)
If a cycle contains the dummy of school \(b\), whose successor is the real representative of decrementable school \(a\), set
\(\displaystyle B=\min\left(\{u_{h(c)}:c\in H\}\cup\{s_a-P_a,\ Q_b-z_b\}\right).\)
Claim. The next \(B\) discrete rounds have the same graph on school labels, with the same representative types, immediately before each round. Their aggregate effect is to assign \(B\) students of type \(h(c)\) to school \(f(c)\), for every \(c\in H\).
To prove the claim, consider an integer \(j\) with \(0\leq j<B\). Provided the first \(j\) rounds use the stated cycles, every participating type still has
\(\displaystyle u_{h(c)}-j>0\)
students remaining. Nonparticipating types have not lost any students. Hence all representative types remain unchanged. In particular, no previously nonempty school becomes empty: its representative type remains present.
When there is no dummy-containing cycle, all \(s_c\) remain unchanged. When there is such a cycle, only \(s_a\) and \(z_b\) change, and
\(\displaystyle s_a-j>P_a,\qquad z_b+j<Q_b.\)
Thus \(a\) remains decrementable and \(b\) remains incrementable. All other school categories remain unchanged as well.
It follows that the represented schools, real representatives’ preferences, and the highest-priority decrementable representative all remain unchanged. Therefore every outgoing edge remains unchanged.
Starting with \(j=0\), this proves the claim by induction. At the end of the \(B\)-th round, at least one defining minimum is attained: a participating type is exhausted, a decrementable school reaches its lower quota, or an incrementable school reaches its upper quota. The graph can then be recomputed.
Accordingly, one batch performs the simultaneous updates
\(\displaystyle u_{h(c)}\leftarrow u_{h(c)}-B,\qquad r_c\leftarrow r_c-B\quad(c\in H),\)
and
\(\displaystyle z_{f(c)}\leftarrow z_{f(c)}+B,\qquad A_{h(c),f(c)}\leftarrow A_{h(c),f(c)}+B\quad(c\in H),\)
where \(A_{t,c}\) records cumulative assignments. If several updates address the same variable, their increments are summed. By the batching claim, these updates exactly reproduce the discrete execution.
4. A polynomial bound on the number of batches. Every batch ends with at least one of the following events:
There are at most \(\tau\) events of the first kind.
For the second kind, observe that while \(r_c>0\), the quantity \(s_c\) can only stay constant or decrease. An increase is possible only when the school supplies a dummy, which requires \(r_c=0\). Thus, after a nonempty school reaches \(s_c=P_c\), it cannot become decrementable again while nonempty. Once empty, it stays empty and cannot become decrementable either. Each school therefore has at most one event of the second kind.
For the third kind, an empty school remains empty, and its finalized count \(z_c\) never decreases. Once \(z_c=Q_c\), it cannot become incrementable again. Each school has at most one event of the third kind.
Hence the total number of batches is at most
\(\displaystyle \tau+2m.\)
Simultaneous events only reduce this bound. There is no need to count school exhaustion separately: a school becomes empty only when its last remaining type is exhausted.
5. Exact computation and bit complexity. Apply the batched algorithm at scale \(D\), with initial state
\(\displaystyle u_t=D\mu_t,\qquad r_c=\sum_{\omega(t)=c}u_t,\qquad z_c=0,\qquad A_{t,c}=0.\)
The batching lemma proves that its final \(A\) is exactly the assignment-count matrix of discrete TTCR-SS at scale \(D\). Return
\(\displaystyle x_{t,c}=\frac{A_{t,c}}{D}.\)
This is a polynomial-time computation in the binary input model.
To verify that statement, reduce the input rationals and compute \(D\) as the least common multiple of their denominators. If those denominators are \(d_1,\ldots,d_N\), then
\(\displaystyle D\leq\prod_{i=1}^{N}d_i,\qquad \log_2D\leq\sum_{i=1}^{N}\log_2d_i=O(L).\)
Thus \(D\) has \(O(L)\) bits, even when its numerical value is exponentially large. Computing it by successive greatest-common-divisor and least-common-multiple operations takes polynomial bit time.
All remaining and finalized student counts are at most \(D\). The integers \(Dp_c\) and \(Dq_c\) also have \(O(L)\) bits; this remains true when an upper quota exceeds one, because its numerator is part of the input. Batch lengths, quota slacks, and assignment counts consequently have \(O(L)\) bits.
For implementation, maintain at each school a queue of its types in block order. A queue advances whenever its current type is exhausted, so there are at most \(\tau\) advances in total.
In a batch, there are at most \(m\) represented schools. Scanning each real representative’s ranking finds all outgoing edges using \(O(m^2)\) elementary operations. Finding the cycles of this graph takes \(O(m)\) operations, and computing and applying the batch requires \(O(m)\) arithmetic operations. Together with initialization and denominator computation, at most \(\tau+2m\) batches on integers of \(O(L)\) bits give polynomial bit complexity.
The output itself has polynomial size: it consists of \(\tau m\) rational entries with numerators at most \(D\) and common denominator \(D\).
6. Replication agreement. Let \(K\) be any integral replication scale allowed by the question. For a reduced rational with denominator \(d\), integrality after multiplication by \(K\) requires \(d\) to divide \(K\). Hence every denominator entering \(D\) divides \(K\), so
\(\displaystyle K=\lambda D\)
for a positive integer \(\lambda\).
Compare the batched executions at scales \(D\) and \(K\). Initially, every count and quota at scale \(K\) is \(\lambda\) times its counterpart at scale \(D\).
Suppose this proportionality holds at corresponding batch boundaries. Positivity, zero tests, and quota equalities and inequalities agree between the two states. The representative types therefore agree, as do their priorities, the represented schools, and every edge of the graph.
Each candidate in the formula for the batch length at scale \(K\) is \(\lambda\) times its counterpart at scale \(D\). Consequently,
\(\displaystyle B_K=\lambda B_D.\)
The batch updates preserve proportionality of all remaining counts, finalized counts, and cumulative assignment counts. Induction proves that the executions have the same sequence of type-level graphs and terminate at corresponding batch boundaries. Their final matrices satisfy
\(\displaystyle A^{(K)}_{t,c}=\lambda A^{(D)}_{t,c}.\)
Since the batched executions exactly reproduce their respective discrete executions,
\(\displaystyle \frac{A^{(K)}_{t,c}}{K}=\frac{\lambda A^{(D)}_{t,c}}{\lambda D}=\frac{A^{(D)}_{t,c}}{D}=x_{t,c}.\)
This settles both questions: exact computation is polynomial-time, and normalized aggregate outcomes agree at every integral replication scale.
⟨structured verdict parsed — rendered above⟩
The output resolves both questions correctly. The batching argument reproduces the specified simultaneous discrete procedure, the number of batches is polynomially bounded independently of replication size, and the scaling argument establishes replication agreement. No major or minor issues were found.
The formula \(h(c)=\min\{t:\omega(t)=c,\ u_t>0\}\) correctly identifies the representative’s type whenever \(r_c>0\).
Each type has one initial school, so representatives at distinct schools necessarily have distinct types. Because the master list consists of contiguous, ordered type blocks, their relative priorities are determined by the block order. The identity of the particular remaining student within a block affects neither her preferences nor her priority relative to representatives from other blocks.
Consequently, the graph on school labels is determined by the compressed counts and the input. The proof correctly accounts for all priority comparisons used by the procedure, including the choice of the decrementable representative to which dummies point.
The initial invariant \(P_c\leq r_c+z_c\leq Q_c\) follows directly from the quota assumptions.
The description of dummy-containing cycles is correct:
Thus there is at most one dummy-containing cycle, and it contains exactly one dummy.
The count changes are also correct. In a real-only cycle, every participating school loses one endowed student and receives one assignment. In a dummy-containing cycle, only the dummy’s successor school \(a\) loses an endowed student without receiving an assignment, and only the dummy’s school \(b\) receives an assignment without losing an endowed student. Incoming edges from vertices outside the cycles cause no assignments under the specified execution rule.
Since \(a\) is decrementable and \(b\) incrementable, the integer slacks are at least one. The updates therefore preserve both quota bounds.
Whenever students remain, at least one real representative exists. Every represented vertex has an outgoing edge, so the finite graph contains a cycle. Every cycle contains a real representative, and execution therefore removes at least one student. This establishes termination.
At termination, the invariant yields the quota constraints. Every executed real representative had her initial school available when choosing her favorite represented school, so the assignment also satisfies the restriction against receiving a school below her initial school. Removing and assigning each student exactly once supplies the required type totals and nonnegativity.
These arguments cover the boundary cases of zero lower quotas, zero upper quotas at initially empty schools, self-loops, and the absence of decrementable schools.
Every candidate defining \(B\) is a positive integer: participating representative types have positive remaining counts, and the two additional quota slacks are positive whenever a dummy-containing cycle exists.
The induction correctly verifies the graph immediately before each of the next \(B\) rounds. For \(0\leq j<B\):
All other categories remain unchanged. Representative types, their relative priorities, dummy availability, and the highest-priority decrementable representative therefore remain unchanged. These facts determine every outgoing edge.
The induction is correctly restricted to states before the first \(B\) rounds. It does not incorrectly claim that the graph must remain unchanged after the last round, when a defining minimum is attained.
The simultaneous updates reproduce those \(B\) rounds exactly. Each participating real representative assigns one student per round to its fixed outgoing school; dummies produce no assignment. The assignment matrix records precisely those transfers.
Each batch attains at least one defining minimum and therefore produces at least one listed event.
The event counts are valid:
Each event can consequently be charged to one of at most \(\tau+2m\) occurrences. Simultaneous events do not invalidate this bound. School exhaustion requires exhaustion of its last remaining type, so no additional event category is needed.
This proves the claimed bound independently of the numerical replication size.
Computing the least common multiple of the reduced denominators gives the required scale \(D\). The bound \(\log_2 D\leq\sum_i\log_2 d_i=O(L)\) is correct: the denominator encodings are included in the input length.
Remaining counts, finalized counts, and assignment counts are bounded by \(D\). Scaled quotas and quota slacks also have \(O(L)\) bits, including when an upper quota exceeds one. Thus the algorithm does not require arithmetic on integers whose bit lengths grow with the numerical number of replicated students.
The implementation bounds are justified:
Together with polynomial-time rational reduction and denominator computation, these establish polynomial bit complexity. The \(\tau m\) output entries likewise have polynomial total encoding length.
The historical citation is contextual; the correctness and complexity conclusions are established by the supplied argument without relying on an external theorem about TTCR-SS.
For an allowed replication, all scaled masses are integers and their sum is \(K\), so \(K\) is a positive integer. Integrality of each reduced mass and quota then requires its denominator to divide \(K\). Hence \(D\) divides \(K\), as claimed.
At corresponding batch boundaries, multiplying all counts and quotas by the positive integer \(\lambda=K/D\) preserves every zero test, positivity test, quota comparison, and representative type. The two executions therefore construct the same graph.
Every candidate batch length scales by \(\lambda\), and taking the minimum preserves that scaling. The updates consequently preserve proportionality of remaining counts, finalized counts, and assignment matrices.
The induction establishes corresponding termination and \(A^{(K)}_{t,c}=\lambda A^{(D)}_{t,c}\). Dividing by the respective scales proves the requested equality of normalized aggregate outcomes for every allowed replication.
No additional clarification or repair is needed.
⟨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.