Answer: The stated mass procedure always terminates with a fair-with-diversity flow maximal under \(>_q\). Computing such a flow is polynomial-time solvable, although the stated procedure can require exponentially many rounds.
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe SPDiv mechanism is fair-with-maximal-diversity.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite schools \(C\), finite student types \(T\), rational type masses \(\mu_t\), per-capita capacities and diversity targets, and school priorities over tiers, does a school-proposing deferred-acceptance procedure on mass—allowing a type’s mass to split at a priority-tier cutoff—compute an assignment flow \(x_{tc}\) (including an outside option) that is fair-with-diversity and maximal under the mass version of \(>_q\)?
A society is given by its support: \(\tau\) student types \(T\), each with positive binary rational mass \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. There are \(m\geq1\) schools \(C\) and \(k\geq1\) disjoint diversity groups, with each type belonging to a group \(g(t)\).
Each type has a strict preference order \(\succ_t\) over \(C\cup\{0\}\), where \(0\) is the outside option. Each school specifies acceptable types and ordered priority tiers; break ties between distinct types by their support-list order, obtaining \(\succ_c\). Identical mass within a type has equal priority.
Capacities \(q_c\) and soft diversity targets \(r_{ch}\) are nonnegative binary rationals with \(\sum_h r_{ch}\leq q_c\). All quantities are per capita; targets need not be feasible. Let \(L\) be the total input bit length.
A feasible flow satisfies \(x_{td}\geq0\), \(\sum_{d\in C\cup\{0\}}x_{td}=\mu_t\), and \(\sum_t x_{tc}\leq q_c\). Individual rationality means positive school flows use mutually acceptable pairs; outside mass is permitted. Write \(N_{ch}(x)=\sum_{t:g(t)=h}x_{tc}\).
A type demands school \(c\) if it is acceptable to \(c\) and \(x_{td}>0\) for some \(d\) with \(c\succ_t d\). A flow is fair-with-diversity if it is individually rational and no demanding pair \((t,c)\) satisfies any of: \(\sum_u x_{uc}<q_c\); \(N_{c,g(t)}(x)<r_{c,g(t)}\); or there exists \(u\) with \(x_{uc}>0\), \(t\succ_c u\), and either \(g(u)=g(t)\) or \(N_{c,g(u)}(x)>r_{c,g(u)}\).
Define \(y>_q x\) when \(N_{ch}(y)\geq N_{ch}(x)\) for every pair with \(N_{ch}(x)\leq r_{ch}\), and \(N_{ch}(y)>N_{ch}(x)\) for at least one pair with \(N_{ch}(x)<r_{ch}\). A fair flow is maximal if no other fair flow dominates it under \(>_q\).
School choice from available amounts first discards unacceptable types, then selects up to \(r_{ch}\) mass from each group in priority order, then fills remaining capacity from residual mass in priority order; cutoff types may be split.
Mass school-proposing deferred acceptance starts with availability \(a_{tc}=\mu_t\). In each simultaneous round schools propose their choice vectors \(p_{tc}\); each type retains its preferred acceptable offers up to total mass \(\mu_t\), giving \(b_{tc}\), and rejects the rest. Update \(a_{tc}\leftarrow a_{tc}-(p_{tc}-b_{tc})\). Stop when there are no rejections, returning retained flows and assigning residual mass outside.
Does this mass school-proposing deferred-acceptance procedure always terminate with a fair-with-diversity flow maximal under \(>_q\)? Is computing such a flow possible in time polynomial in \(m,\tau,k,L\), or is it NP-hard?
For finite students with strict priorities, school-proposing deferred acceptance with these reserves returns a fair-with-maximal-diversity assignment ([Bó, 2016](https://inaciobo.com/files/Bo2016_GEB.pdf)).
Ordinary real-valued stable allocation admits a strongly polynomial algorithm ([Baïou–Balinski, corrected 2002 version](https://doi.org/10.1287/moor.27.4.662.302)); this result does not state the reserve-based diversity-maximality guarantee above. No result settling this exact mass problem was located.
Yes. For the rational inputs in the question, the stated procedure terminates and returns a fair-with-diversity flow maximal under \(>_q\).
Computing such a flow is polynomial-time solvable. However, executing the stated procedure round by round can require exponentially many rounds. A polynomial algorithm follows from a reduction to ordinary stable allocation, proved below.
Throughout, comparisons between vectors are coordinatewise. Competing fair flows may have arbitrary real coordinates; maximality is not restricted to rational competitors.
Write \(\operatorname{Ch}_c(a)\) for school \(c\)'s choice from availability vector \(a\). Unacceptable coordinates are ignored.
For \(z\leq a\), reserve choice satisfies
\[ \operatorname{Ch}_c(z)_t\geq \min\{z_t,\operatorname{Ch}_c(a)_t\}. \tag{1} \]
Here is a justification that also handles split types.
First suppose all quantities are rational. Multiply by a common denominator and replace each type's available amount by unit copies, ordered consecutively within that type. Capacities and reserves become integers. The finite reserve choice rule is substitutable: deleting candidates cannot cause a previously selected, undeleted candidate to become unselected. This is the finite choice-function property in [Bó, Lemma 1](https://inaciobo.com/files/Bo2016_GEB.pdf); its hypotheses hold because priorities on copies are strict and groups are disjoint.
For each type, both reserve selection and subsequent residual selection together select a prefix of its copies. Reducing availability from \(a_t\) to \(z_t\) deletes a suffix. Thus at least
\( \min\{z_t,\operatorname{Ch}_c(a)_t\} \)
of its selected amount survives, proving (1).
For real availability vectors, approximate \(z\leq a\) by rational vectors preserving that inequality. Reserve choice is continuous: its finitely many operations are sums, differences, minima, and positive parts. Passing to the limit proves (1).
This is a local argument about one school's choice rule; it does not assume a global equivalence between mass deferred acceptance and deferred acceptance on individual copies.
Lemma. Let \(y\) be fair-with-diversity, and suppose \(a_u\geq y_{uc}\) for every type \(u\). If \(t\) demands \(c\) under \(y\), then
\[ \operatorname{Ch}_c(a)_t\leq y_{tc}. \tag{2} \]
Proof. Put \(h=g(t)\). Fairness, together with demand, implies:
Define \(z\) by \(z_u=y_{uc}\) for \(u\neq t\), and \(z_t=a_t\).
Adding this extra availability of \(t\) leaves the reserve-stage selection unchanged. Other groups are unchanged. In group \(h\), the original mass of types strictly above \(t\), together with \(y_{tc}\), already fills the reserve: the group's total meets its reserve and no lower-priority type has positive mass.
Moreover, every lower-priority type's original mass is entirely selected in the reserve stage. Indeed, such a type's group total is at most its reserve. Consequently, the original residual mass consists only of types above \(t\) and \(t\) itself.
Since \(y\) fills the school, that original residual mass fills the entire residual capacity. Additional residual availability of \(t\) therefore cannot increase its selected amount. Hence
\( \operatorname{Ch}_c(z)_t=y_{tc}. \)
Now \(z\leq a\) and \(z_t=a_t\). Applying (1) gives
\( y_{tc}=\operatorname{Ch}_c(z)_t \geq \min\{a_t,\operatorname{Ch}_c(a)_t\} =\operatorname{Ch}_c(a)_t. \)
This proves (2). \(\square\)
Index rounds by \(n\), with availability \(a^n\), proposals \(p^n\), and retained offers \(b^n\).
Choose a positive integer \(D\) such that every input mass, capacity, and reserve is an integer multiple of \(1/D\). For example, take the product of their denominators.
Every quantity generated by the procedure remains on this grid, because all operations are sums, differences, minima, and positive parts. Also,
\( a^{n+1}_{tc}=a^n_{tc}-p^n_{tc}+b^n_{tc} \)
is nonnegative and no greater than \(a^n_{tc}\).
Initially,
\( \sum_{t,c}a^1_{tc}=m. \)
Every nonterminal round decreases this sum by at least \(1/D\). There are therefore at most \(mD\) nonterminal rounds.
The terminating flow is feasible and individually rational: school proposals respect capacities and school acceptability, types retain only acceptable offers within their masses, and remaining mass is assigned outside.
Since \(p^n_{tc}\leq a^n_{tc}\), the update satisfies
\( a^{n+1}_{tc}\geq b^n_{tc}. \)
Using (1),
\[ p^{n+1}_{tc} \geq \min\{a^{n+1}_{tc},p^n_{tc}\} \geq b^n_{tc}. \tag{3} \]
Thus the next round's proposals include every previously retained amount.
It follows that, for each type and each acceptable school \(c\), retained mass at schools weakly preferred to \(c\) cannot decrease. In fact, greedy retention assigns to such a preference prefix the minimum of the type's mass and the total offers in that prefix; (3) makes that total at least the previously retained prefix mass.
If a type rejects a positive amount from an acceptable school \(c\), it retains its entire mass at schools weakly preferred to \(c\). The preceding monotonicity then prevents it from having mass strictly below \(c\) at termination.
Consequently, if \(t\) demands \(c\) in the terminal flow \(x\), it never rejected \(c\), and hence
\[ a^{\mathrm{fin}}_{tc}=\mu_t>x_{tc}. \tag{4} \]
Demand and individual rationality also imply that \(c\) is acceptable to the type.
Consider any school choice \(p=\operatorname{Ch}_c(a)\) and acceptable type \(t\) with \(p_t<a_t\). We show that none of the school-side conditions in the question holds for \(t\).
Vacancy. Reserve choice is work-conserving. If the school were underfilled, it would select all acceptable available mass, contradicting \(p_t<a_t\).
Own-group deficit. Reserve selection chooses at least the minimum of the reserve and the available group total. If the selected group total is below its reserve, all available mass of that group is selected. Again \(p_t=a_t\), a contradiction.
Lower-priority mass in the same group. If a lower-priority type \(u\) receives any reserve-stage mass, all available mass of the higher-priority \(t\) must already have been selected in that stage. Otherwise, positive selected mass of \(u\) comes from the residual stage. That stage cannot select \(u\) while leaving residual availability of the higher-priority \(t\) unselected.
Lower-priority mass in a group above its reserve. Suppose \(p_u>0\), \(t\succ_c u\), and group \(j=g(u)\) has selected total above \(r_{cj}\). Some selected mass of group \(j\) therefore comes from the residual stage.
If \(u\) has no reserve-stage mass, use its own positive residual selection. If \(u\) has reserve-stage mass, the reserve stage has exhausted all available group-\(j\) types above \(u\). Thus any selected residual group-\(j\) mass has priority no higher than \(u\).
In either case, a residual-stage selected type lies strictly below \(t\), contradicting the unselected residual availability of \(t\).
At termination, \(x_{\cdot c}=\operatorname{Ch}_c(a^{\mathrm{fin}}_{\cdot c})\). Applying this argument to (4) proves that no demanding pair violates fairness.
The terminal flow is fair-with-diversity.
The crucial invariant is:
\[ a^n_{tc}\geq y_{tc} \quad\text{for every fair-with-diversity flow }y. \tag{5} \]
It holds initially because \(y_{tc}\leq\mu_t\).
Fix a fair flow \(y\) and assume (5) holds before a round. Consider a coordinate with \(y_{tc}>0\). For every school \(e\succ_t c\) that accepts \(t\), type \(t\) demands \(e\) under \(y\), because \(y_{tc}>0\). Lemma (2) gives \(p_{te}\leq y_{te}\). Schools that do not accept \(t\) propose zero. Therefore
\( \sum_{e\succ_t c}p_{te} \leq \sum_{e\succ_t c}y_{te} \leq \mu_t-y_{tc}. \)
When processing its offer from \(c\), the type consequently has room for at least \(y_{tc}\), so
\( b_{tc}\geq \min\{p_{tc},y_{tc}\}. \)
Hence
\( a'_{tc} =a_{tc}-p_{tc}+b_{tc} \geq a_{tc}-p_{tc}+\min\{p_{tc},y_{tc}\} \geq y_{tc}. \)
The last inequality follows from \(a_{tc}\geq y_{tc}\) and \(a_{tc}\geq p_{tc}\), considering respectively \(p_{tc}\leq y_{tc}\) and \(p_{tc}>y_{tc}\).
Coordinates with \(y_{tc}=0\) satisfy the invariant by nonnegativity. This completes the induction.
The reserve stage at termination, together with (5), gives, for every fair flow \(y\),
\[ N_{ch}(x)\geq \min\{r_{ch},N_{ch}(y)\} \quad\text{for every }c,h. \tag{6} \]
Only school-acceptable availability enters reserve selection; all positive school coordinates of \(y\) are acceptable, so the availability bound suffices.
If \(N_{ch}(x)<r_{ch}\), (6) implies
\( N_{ch}(y)\leq N_{ch}(x) \)
for every fair \(y\). Thus no fair flow can improve even one deficient coordinate of \(x\). In particular, no fair flow dominates \(x\) under \(>_q\).
This proves the stated procedure's guarantee.
Let \(N\) be a positive integer. Take two types of mass \(1/2\), one diversity group, two schools, and zero reserves. Set
\( q_A=\frac{N+1}{2N}, \qquad q_B=\frac12. \)
All pairs are mutually acceptable. Preferences and priorities are
\( B\succ_1 A\succ_1 0,\qquad A\succ_2 B\succ_2 0, \)
\( 1\succ_A 2,\qquad 2\succ_B 1. \)
For calculations, multiply amounts by \(2N\). Each type then has mass \(N\), and capacities are \(N+1\) and \(N\).
For \(j=0,\ldots,N-1\), proposals in round \(2j+1\), listed in type order, are
\( p_A=(N-j,j+1),\qquad p_B=(j,N-j). \)
Type \(2\) rejects one unit from \(B\). In round \(2j+2\), proposals are
\( p_A=(N-j,j+1),\qquad p_B=(j+1,N-j-1), \)
and type \(1\) rejects one unit from \(A\).
These formulas follow by induction: after each two-round pair, availability of type \(1\) at \(A\) and type \(2\) at \(B\) has decreased by one; the other two availabilities remain \(N\).
After \(2N\) rejecting rounds, the next proposals are
\( p_A=(0,N),\qquad p_B=(N,0), \)
and there are no rejections. Thus termination requires exactly \(2N+1\) rounds.
Choosing \(N\) to be a power of two makes the input length \(O(\log N)\). The round count is exponential in that length.
We now construct a different algorithm that computes a maximal fair flow in polynomial time.
Replace school \(c\) by these capacity classes:
Delete zero-capacity classes. Their total capacity is \(q_c\).
Every class accepts exactly the types mutually acceptable at \(c\). Priorities are strict:
A type ranks classes in blocks according to its original school preference. Within school \(c\), it ranks its own reserve class first, then the open class, then other reserve classes in any fixed strict order. Omitted classes are skipped.
Each type retains supply \(\mu_t\). Unallocated supply represents the outside option.
This is an ordinary bipartite stable-allocation instance. A pair blocks precisely when the type has unused supply or positive mass at a less preferred class, and the class has unused capacity or positive mass of a lower-priority type.
Any required edge upper bounds can be set to \(\mu_t\); these are redundant. A demanding type-class pair necessarily has current flow strictly below \(\mu_t\).
Let \(z\) be an expanded allocation with no blocking pair involving a move between classes of the same school. Aggregate it as
\( x_{tc}=\sum_{s:\,s\text{ is a class of }c}z_{ts}. \)
Define the own-group mass in a reserve class by
\( Z_{ch}=\sum_{t:g(t)=h}z_{t,R_{ch}}, \)
with value zero for an omitted class. Then
\[ Z_{ch}=\min\{r_{ch},N_{ch}(x)\}. \tag{7} \]
To prove this, suppose some group-\(h\) mass is assigned to another class of \(c\). Its type prefers \(R_{ch}\). Internal stability therefore requires \(R_{ch}\) to be full of group-\(h\) mass: vacancy or a non-\(h\) occupant would create a blocking pair. Hence \(Z_{ch}=r_{ch}\).
If no group-\(h\) mass is assigned elsewhere, then \(Z_{ch}=N_{ch}(x)\leq r_{ch}\). This proves (7), including the immediate zero-reserve case.
Internal stability also implies:
A group-\(h\) type assigned outside \(R_{ch}\) cannot have strictly higher school priority than a group-\(h\) type assigned inside \(R_{ch}\).
Otherwise, the former type blocks the reserve class.
Feasibility and individual rationality follow immediately. Suppose \(t\) demands school \(c\) in the aggregate. It then demands every class of \(c\), because some of its mass lies outside or at a less preferred school.
Each possible fairness violation yields an expanded blocking pair.
Vacancy. Aggregate vacancy implies vacancy in some class of \(c\).
Own-group deficit. If \(N_{c,g(t)}(x)<r_{c,g(t)}\), the own reserve class has vacancy or a non-own-group occupant, by (7).
Lower-priority occupant in the same group. Between two types of the same group, every class of \(c\) preserves their original school priority. Thus \(t\) blocks the class containing that occupant.
Lower-priority occupant in a group above its reserve. Let \(u\) be such an occupant, with group \(j\).
If some positive mass of \(u\) lies outside \(R_{cj}\), type \(t\) outranks it at that class: \(u\) has no own-group protection there.
Otherwise, \(u\) lies in \(R_{cj}\). Since \(N_{cj}(x)>r_{cj}\), some group-\(j\) type \(v\) has positive mass outside \(R_{cj}\). The internal priority property above implies that \(v\) has priority no higher than \(u\). Consequently \(t\succ_c v\), and \(t\) blocks the class containing that outside-reserve mass.
All cases contradict expanded stability. The aggregate is therefore fair-with-diversity.
Let \(y\) be any fair flow, including a real-valued one.
For each school \(c\), consider a local ordinary stable-allocation instance:
A local stable allocation exists. It assigns every local type's supply: if a type had unused supply, total assigned mass would be below \(\sum_t y_{tc}\leq q_c\), leaving vacancy in some class. The complete local acceptability graph would then give a blocking pair.
Combining these local allocations produces a lift \(w\) of \(y\). It satisfies (7) and has no internal blocking pair.
Suppose an expanded pair \((t,s)\), where \(s\) belongs to school \(c\), blocks this lift. If its demand comes from mass at a worse class of the same school, local stability rules it out. Otherwise, \(t\) demands \(c\) under \(y\).
Fairness then requires \(c\) to be full, so all its classes are full. A block must displace a lower-priority occupant \(u\).
In the latter two cases, the class comparison between \(t\) and \(u\) preserves their original school priority. Displacement therefore contradicts fairness under the excess-group condition.
Thus \(w\) is globally stable. We have proved both directions of the reduction.
The ordinary stable-allocation results needed here are:
These follow from the corrected [Baïou–Balinski paper](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302), specifically its inductive algorithm, Lemma 8, and Theorem 10 with Corollary 4.
For clarity, the prefix statement follows from their optimality order and equal-total property. If another stable allocation increases a coordinate of a chosen-side node, the optimal allocation has zero mass at every less preferred coordinate. If a prefix gained mass in the alternative, choose an increased coordinate in that prefix; the optimal allocation then places its entire assigned total inside the prefix. Equal assigned totals contradict the alleged prefix gain.
All hypotheses hold in the expanded instance: it is bipartite, supplies and capacities are nonnegative, preferences are strict, and zero-capacity nodes have been deleted.
Compute an allocation \(z^\star\) optimal for the class side, and aggregate it to \(x^\star\). Section 4.3 proves fairness.
Fix any fair flow \(y\), and lift it to an expanded stable allocation \(w\), using Section 4.4. At reserve class \(R_{ch}\), its own group is a priority prefix. Class-side optimality and (7) give
\[ \min\{r_{ch},N_{ch}(x^\star)\} \geq \min\{r_{ch},N_{ch}(y)\}. \tag{8} \]
If \(N_{ch}(x^\star)<r_{ch}\), inequality (8) implies \(N_{ch}(y)\leq N_{ch}(x^\star)\). Hence no fair flow can improve any deficient coordinate, and \(x^\star\) is maximal under \(>_q\).
Finally, the expanded instance has at most
\( \tau+m(k+1) \)
nodes and at most
\( m\tau(k+1) \)
acceptable edges. Its rational data have polynomial encoding length: the only new numerical capacities are \(q_c-\sum_h r_{ch}\). Constructing the instance, computing the class-optimal stable allocation, and aggregating its flows therefore take time polynomial in \(m,\tau,k,L\).
The reduction supplies the reserve-based maximality guarantee; that guarantee is not being assumed as part of the ordinary stable-allocation theorem.
⟨structured verdict parsed — rendered above⟩
The argument resolves both substantive questions: the stated rational-mass procedure terminates with a fair-with-diversity flow maximal under \(>_q\), and a different algorithm computes such a flow in polynomial time. The exponential-round example is also correct.
I found no false central step or gap requiring new mathematics. There is one minor omission in the justification of polynomial bit complexity.
The rational-copy argument is valid.
The cited finite result applies: Bó’s Lemma 1 concerns precisely the reserve-first, residual-priority choice rule and establishes substitutability. The disjoint-group and strict-priority hypotheses are satisfied by the copy construction. [Bó, Lemma 1](https://inaciobo.com/files/Bo2016_GEB.pdf).
The extension to real availability is also justified. With a fixed finite priority order, the choice coordinates are continuous functions formed from the operations listed in the output. Ordered rational approximations therefore preserve the inequality in the limit.
Assessment: Correct.
Each fairness implication used here follows directly from the task’s definition.
The argument about unchanged reserve selection is sound: in the demanding type’s group, the original mass at that type and above already meets the reserve, while lower-priority mass in that group is absent.
The residual-stage argument also holds. Every positive lower-priority occupant belongs to a group at or below its reserve, so its original mass is entirely absorbed in reserve selection. Consequently, the original residual contains only the demanding type and higher-priority types. Since the school is full, additional availability of the demanding type cannot increase its residual selection.
The final application of quantitative substitutability has the correct direction, and the equality \(z_t=a_t\) justifies the last simplification.
Assessment: Correct.
The grid invariant is valid. All generated amounts remain multiples of \(1/D\), availability remains nonnegative, and every rejecting round decreases total availability by at least \(1/D\).
The initial total availability is \(m\), because every school initially has the full unit population available. Thus the bound of \(mD\) nonterminal rounds is correct.
Feasibility and individual rationality follow from school choice, type retention, and assignment of residual mass outside.
Assessment: Correct. This establishes finite termination, not a polynomial round bound.
Inequality (3) follows correctly from the update and quantitative substitutability.
The preference-prefix monotonicity argument is valid: the next proposals contain all previously retained amounts, and greedy retention preserves at least the previous retained mass in every acceptable preference prefix.
A rejection from an acceptable school requires the type to retain its entire mass at that school or better schools. Prefix monotonicity therefore excludes terminal mass strictly below that school.
Consequently, terminal demand implies that the relevant availability coordinate was never reduced. Demand also implies that terminal assignment to the demanded school is strictly below the type’s mass, establishing (4).
Assessment: Correct.
All four cases are covered correctly.
At termination, proposals equal retained flows, so applying these properties to (4) establishes fairness.
Assessment: Correct.
The induction is valid, including for real-valued competing fair flows.
For a positive coordinate \(y_{tc}\), every school preferred to \(c\) that accepts the type is demanded under \(y\). Lemma (2) bounds its proposal by the corresponding coordinate of \(y\). Therefore, retention leaves room for at least \(y_{tc}\) when processing \(c\).
The two cases in the final availability inequality are correct. Zero coordinates follow from nonnegativity.
There is no quantifier interchange problem: the induction works for each arbitrary fair \(y\), yielding the stated universal invariant.
Assessment: Correct.
Inequality (6) follows from reserve-stage selection and the availability invariant.
For a coordinate below its target, (6) excludes any fair competitor with a strictly larger value. This is stronger than the required exclusion of a competitor satisfying \(>_q\), and therefore proves maximality.
Coordinates exactly at their targets require no separate improvement argument: domination requires a strict improvement in at least one deficient coordinate.
Assessment: Correct.
The displayed recurrence checks out.
In odd rounds, type \(2\) receives its full mass from \(A\) and \(B\) plus one extra unit, rejecting one unit from \(B\). In even rounds, type \(1\) analogously rejects one unit from \(A\). The availability changes match the stated induction.
The endpoint \(j=N-1\) remains valid. After the final even rejection, the next proposals are \((0,N)\) and \((N,0)\), with no rejection. Thus the count \(2N+1\) is correct, including \(N=1\).
Taking \(N\) to be a power of two gives input length \(O(\log N)\).
Assessment: Correct.
The capacities are nonnegative and sum to each original school’s capacity. Class priorities and type preferences are strict. Restricting edges to mutually acceptable school pairs correctly handles the outside option.
The edge bounds \(\mu_t\) are redundant: a demanding type-class pair necessarily has current flow below \(\mu_t\).
Assessment: Correct.
If own-group mass is assigned elsewhere, its preference for its own reserve class forces that class to be full of own-group mass. Otherwise, either vacancy or a non-own-group occupant would permit an internal block.
If no own-group mass is assigned elsewhere, its total equals its mass in the reserve class. These alternatives prove (7).
The internal priority property follows from the same blocking criterion. Omitted zero-reserve classes cause no difficulty.
Assessment: Correct.
School demand implies demand for every acceptable class of that school.
Each fairness violation yields the claimed block. In the excess-group case, the internal priority property correctly supplies an outside-reserve occupant with priority no higher than the protected occupant. At that outside-reserve class, the displaced type has no own-group protection, so the original school comparison applies.
Assessment: Correct.
The local instances have complete acceptability among their positive-supply types and existing classes. If supply remained unassigned, aggregate capacity would leave a vacancy, creating a local block. Thus each local allocation assigns all its supplies.
The global blocking analysis is exhaustive:
The priority comparisons in the latter cases are preserved correctly. The argument applies to arbitrary real-valued fair flows.
Assessment: Correct.
The cited stable-allocation results support the substantive claims. The corrected paper establishes real-valued existence, equal assigned totals, side-optimal allocations, and polynomially bounded allocation updates. Its optimality order has exactly the coordinate property used in the output’s preference-prefix argument. [Baïou–Balinski, corrected version, Corollary 1, Lemma 8, Theorem 10, and Corollary 4](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302).
The prefix argument is correct: an increased coordinate in a prefix forces the optimal allocation to place its entire assigned total inside that prefix; equal totals then exclude an alternative prefix gain.
Applying this to the own-group priority prefix of each reserve class yields (8), which proves diversity maximality.
The node and edge bounds are correct, and the newly constructed capacities have polynomial encoding length.
Where: Section 5, final polynomial-time conclusion.
Issue: The write-up moves from polynomial instance size and the cited algorithm to polynomial time in \(L\) without explicitly accounting for intermediate numerical encoding lengths. The cited update bounds alone count allocation changes rather than bit operations.
Minimum clarification: State the numerical-size guarantee accompanying the cited algorithms, or briefly justify that their rational intermediate quantities and exact arithmetic have polynomial bit complexity. This is a routine computational clarification, not a missing mathematical lemma.
Both guarantees are established in substance. The proof handles split types, real-valued fair competitors, infeasible targets, zero reserves, zero capacities, and the outside option consistently. No counterexample or major issue was found. Only the numerical-complexity clarification above remains.
⟨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.