| paper | Achieving Balanced Representation in School Choice with Diversity Goals |
| authors | Zhaohong Sun, Makoto Yokoo |
| venue | AAAI 2025 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given rational group masses \(\mu_u\) with \(\sum_{u\in U}\mu_u=1\), capacity mass \(\kappa\), ranked quota masses \(\eta_t^j\), and group targets \(\delta_u\), decide whether there exists \(f_{u,t,j}\ge0\) with \(t\in u\cup\{t_0\}\) such that \(\sum_{t,j}f_{u,t,j}\le\mu_u\), \(\sum_{u:t\in u}f_{u,t,j}\le\eta_t^j\), \(\sum_{u,t,j}f_{u,t,j}\le\kappa\), every group receives at least \(\delta_u\) mass, and \(f\) is rank-maximal by maximizing total selected mass and then lexicographically maximizing \(R_j=\sum_{u,t}f_{u,t,j}\).
A finite type-flow model in which \(u\in U\) is the complete eligibility type, \(\mu_u\) is its population mass, \(f_{u,t,j}\) is mass assigned at most once to type \(t\) and rank \(j\), and \(\kappa\), \(\eta\), and \(\delta\) are capacity, quota, and target masses.
The paper's flow network already aggregates students by groups, so replacing integer capacities with rational masses may add little new algorithmic structure; this is a limitation on novelty rather than a failure of the continuous question.
fatal: False
The mirror directly covers Theorem 5 and the flow-equivalence machinery behind Theorem 1, and it also supports a continuous version of Theorem 6. It does not preserve Theorem 7's exact named-student strict-priority choice, Theorem 2's uniqueness statement, or the generalized deferred-acceptance extension.
There is a credible continuous mirror, and its strongest form is narrower than “continuize the whole school-choice mechanism”: continuize the large applicant population while preserving the paper’s one-to-one type assignment and ranked diversity objectives.
The natural regime is a large admissions cohort with a small number of privilege attributes. Let \(P\) be the finite set of privilege types, and let \(U\subseteq 2^P\) be the occupied type combinations. A student in group \(u\in U\) may be assigned to at most one reserved type \(t\in u\), exactly as in the paper’s one-to-one convention. Add a general type \(t_0\) for unrestricted seats.
This is plausible for the Brazilian, Indian, or similar admissions settings discussed by the authors: perhaps \(d\) privilege dimensions produce at most \(2^d\) groups, while the applicant population is very large. To preserve priorities, the strongest full mirror uses finitely many priority classes. A complete population type is then \((u,\ell)\), where \(u\) is the exact type combination and \(\ell\) is a priority band. Agents in one such class have the same eligibility, quota treatment, and priority status. Their individual identities and arbitrary within-band tie-breaks are irrelevant to the aggregate choice.
Let \(\mu_{u,\ell}\) be the mass of class \((u,\ell)\), with total population mass \(1\), and let \(M_u=\sum_\ell\mu_{u,\ell}\). Let \(\kappa\) be the school-capacity fraction and \(\eta_t^j\) the mass quota for type \(t\) at rank \(j\). The action is a mass assignment \(f_{u,\ell,t,j}\ge 0\): mass from class \((u,\ell)\) assigned to type \(t\) and rank \(j\). It must satisfy \(\sum_{t,j}f_{u,\ell,t,j}\le\mu_{u,\ell}\), quota capacities \(\sum_{u,\ell:t\in u}f_{u,\ell,t,j}\le\eta_t^j\), and total capacity \(\sum_{u,\ell,t,j}f_{u,\ell,t,j}\le\kappa\). Thus mass is population mass, not a divisible seat or lottery outcome: every infinitesimal student is assigned at most once.
My lead anchor is Theorem 5, proved in this paper. It states that, for a target vector \(\delta\), validity can be checked through the associated flow network in time \(O(m\log(n)(m+n\log n))\). The theorem is exactly the paper’s computational validity question, and it has a clean continuous form:
Continuous Rank-Maximal Validity. Given \((P,U,r,\mu,\kappa,\eta,\delta)\), determine whether there exists a feasible mass assignment \(f\) that is rank-maximal and selects at least \(\delta_u\) mass from every group \(u\), where \(z_u(f)=\sum_{\ell,t,j}f_{u,\ell,t,j}\ge\delta_u\).
Here “rank-maximal” means that the total selected mass is maximized and, among assignments of that size, the vector of masses assigned to ranks \(1,\ldots,r\) is lexicographically maximized, precisely mirroring the paper’s rank-maximal matching notion. A solution is the flow \(f\), not merely a yes/no answer.
I expect this problem to be Class A. The paper’s flow network has size depending on \(|P|\), \(|U|\), and \(r\), not on the number \(N\) of students. Replacing integer capacities by rational masses changes no combinatorial structure. With rational input, this is a network-flow or linear-programming problem of polynomial bit complexity; with integral capacities it retains the usual flow integrality.
The finite-population dictionary is exact. For a discrete cohort of size \(N\), set \(\mu_{u,\ell}=|S_{u,\ell}|/N\), \(\kappa=q/N\), \(\eta_t^j=\eta_{t,\mathrm{disc}}^j/N\), and \(\delta_u=\delta_{u,\mathrm{disc}}/N\). A matching becomes a flow divided by \(N\). Conversely, clearing denominators and using flow integrality lifts an appropriate rational flow back to a matching in a replicated finite instance. Thus this is a genuine high-multiplicity relaxation, not merely fractional matching.
A second, stronger but more conditional anchor is Theorem 7, also proved here. It states that, given a crucial vector \(\delta^*\), Algorithm 5 returns a matching satisfying maximal diversity, non-wastefulness, balanced representation, and justified envy-freeness in polynomial time.
Its continuous counterpart is:
Balanced Continuous Choice. On the same instance, define \(F_{\mathrm{rm}}\) as the set of rank-maximal mass assignments and let \(\alpha^*\) be the largest value such that some \(f\in F_{\mathrm{rm}}\) satisfies \(z_u(f)\ge\alpha^*M_u\) for every occupied group \(u\). Among all such balanced assignments, return the assignment whose selected class-mass vector is lexicographically maximal in the priority order. The output is both the selected mass \(\sigma_{u,\ell}=\sum_{t,j}f_{u,\ell,t,j}\) and its one-to-one quota assignment \(f\).
This mirrors Algorithm 5 at the type level: instead of testing one named student at a time, it maximizes the selectable mass of each priority class while maintaining the balanced lower bounds. Theorem 6, also proved here, supplies the corresponding crucial-vector computation; in the continuous version, the floor \(\lfloor\alpha |S_u|\rfloor\) becomes the exact mass target \(\alpha M_u\), and \(\alpha^*\) can be obtained by a parametric flow or linear program.
I expect Balanced Continuous Choice also to be Class A when the number of complete priority types is finite. The rank-maximal constraints can be imposed by sequential flow optimizations, the max-min balance objective is a linear program, and the priority-respecting choice requires only finitely many further flow or LP optimizations. Theorem 1’s flow equivalence is the structural reason this works, although I use Theorems 5 and 7 as the computational anchors.
The mirror covers the paper’s flow-network validity algorithm, its balanced-representation computation, and its final priority-respecting choice algorithm. I would not claim that it continuizes every result: Theorem 2’s uniqueness is primarily an axiomatic statement, and the paper’s generalized deferred-acceptance extension would require a separate multi-school population model.
The weakest point is the strict priority order. In the paper, \(\succ\) is an order over named students. If every student has an idiosyncratic priority position, then priority becomes part of the complete type and the number of types grows with \(N\); the high-multiplicity gain disappears. The full Theorem 7 mirror therefore requires a defensible admissions regime with finitely many score or priority classes and anonymous tie-breaking. This does not weaken the Theorem 5 mirror, whose validity question is fundamentally priority-free, but it makes the full choice-function mirror conditional.
The resulting follow-up questions are whether exact rounding preserves the balanced ratio within \(O(1/N)\), how complexity depends on \(|P|\), \(|U|\), and the number of priority classes, whether individualized priorities can be compressed without changing justified envy, and whether the same mass-flow formulation extends to the paper’s multi-school deferred-acceptance application.
The strongest negative case is against the paper’s final choice-function result, Theorem 7, rather than against its flow subroutine.
The paper’s choice function is fundamentally about named students under a strict priority order. Balanced representation is an aggregate constraint, but justified envy-freeness and Algorithm 1 depend on the exact order in which individuals occur. If two students have the same privilege combination and the same coarse score class, the algorithm may accept one and reject the other solely because of their within-class priority. A finite mass vector \(\mu_{u,\ell}\) cannot recover that information. Putting the exact priority rank into the type makes essentially every student a different type, destroying the high-multiplicity regime.
The proposed repair—finite priority bands with anonymous ties—is sensible admissions modelling, but it changes the result. It replaces the paper’s strict-priority choice function by a choice rule for tied classes. The continuous output is then a selected mass vector, not the paper’s uniquely selected subset of students, and justified envy is weakened accordingly. A continuous priority quantile could preserve the strict order, but then priority is an additional continuous coordinate rather than a fixed finite type space. Thus Theorem 7 has no direct mirror with the paper’s semantics. Its proposed version is an extension, not a continuization of the theorem.
The same problem affects the claimed continuous version of Theorem 6. In the finite paper, \(\delta_u^*=\lfloor\alpha |S_u|\rfloor\) is used to identify concrete students who must be protected while the priority order is processed. Replacing this by \(\alpha M_u\) produces a well-defined max-min flow problem, but it no longer identifies the individual set needed by Algorithm 5. The resulting parametric flow rule may be useful, but it is a new anonymous selection mechanism.
There is also a genuine degeneracy in the literal large-population limit. If the school capacity \(q\) and quotas remain fixed while \(N\) grows, then \(\kappa=q/N\to0\), and the balanced selection ratio is typically \(0\). The proponent correctly avoids this by scaling capacity and quotas with population. That is the right repair, but it is a joint population-and-resource scaling extension rather than the limit of the paper’s stated one-school instance.
Theorem 5 is much harder to defeat. Its validity test deliberately forgets individual identities and priorities: it asks only whether some rank-maximal matching achieves group lower bounds. Because students in a group have identical eligibility, this really does admit an exact rational-clone interpretation. Setting \(\mu_u=|S_u|/N\), scaling \(q\), quotas, and targets by \(1/N\), and clearing denominators in the other direction recovers the finite matching problem. The continuous object is a mass flow in which each infinitesimal student is still assigned to at most one reserved type, so this is not merely fractionalizing a student’s assignment.
One technical caveat is that the paper’s stated edge cost \(i\) implements lexicographic rank-maximality only for two ranks; for general \(r\), ordinary minimum cost does not in general equal lexicographic maximization of the rank signature. Sequential optimization or suitably separated weights repairs this, however, and does not undermine the continuous formulation.
The best objection to Theorem 5 is therefore only that the paper has already performed the essential aggregation: its flow network is explicitly independent of the number of students. Replacing integer group capacities by rational masses adds a clean high-multiplicity dictionary but little new algorithmic structure. Under this programme’s rules, however, that is not a valid rejection. Existing high-multiplicity structure is evidence that the regime is sensible, not a novelty collision.
So the honest negative case defeats the full balanced, priority-sensitive mirror of Theorems 6–7, but it cannot defeat the priority-free validity mirror of Theorem 5. That anchor is a legitimate, author-recognizable Class A continuous mirror. I therefore cannot honestly sustain the universal claim that no worthwhile continuous mirror exists.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.