| paper | Order Symmetry: A New Fairness Criterion for Assignment Mechanisms |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper contains no named result asserting complexity, an algorithm, approximation, or parameterized tractability, so bit (a) fails. The proposed continuous Boston optimization is a plausible new research direction, but it cannot serve as a ChoCo mirror of this paper's results under the stated source gate.
fails bit a — no named computational result to mirror
Theorem 5.1 is not computational, and the proposed priority-profile optimization is introduced by the proponent rather than supplied by the paper.
fatal: True
The proposed model covers the paper's cyclic-tiebreak Boston fairness theorem and order-bias objective, but no named computational result exists to anchor a qualifying mirror.
The strongest honest case is narrow but real: the paper has no named NP-hardness, membership-in-\(\mathrm P\), W[1]-hardness, or FPT theorem. Its named results are structural mechanism-design theorems. My lead anchor is therefore Theorem 5.1, proved in this paper:
“Cyclic-tiebreak Boston is order-symmetric with respect to any fully symmetric probability measure.”
A natural high-multiplicity mirror is school allocation. There are \(q\) school types \(O=\{o_1,\ldots,o_q\}\), with rational capacity fractions \(\nu_j\) satisfying \(\sum_j\nu_j=1\). A student type is \(t=(r,\pi)\), where \(\pi\in S_q\) is a complete ranking of schools and \(r\in\{1,\ldots,q\}\) is a priority cohort. The priority cohort is part of the type because it affects the mechanism; students with the same \((r,\pi)\) are indistinguishable for the problem. The society is a rational distribution \(\mu_{r,\pi}\), meaning that this fraction of the student population has that type.
This is a credible regime for a large school district, a university course-allocation system, or repeated housing cohorts: \(N\) is large, \(q\) is fixed or modest, and many students share a small number of preference and priority types. The finite instance with \(N\) students has counts \(N\mu_{r,\pi}\) and \(N\nu_j\); the continuum instance records their limiting proportions. Each infinitesimal student still receives one indivisible school. Only the aggregate assignment is represented continuously.
For school \(o_j\), use the cyclic priority order \(j,j+1,\ldots,q,1,\ldots,j-1\), with indices modulo \(q\). In Boston round \(k\), every unmatched mass of type \((r,\pi)\) applies to its \(k\)-th ranked school. Each school accepts applicants in its cyclic priority order until its capacity is filled; if a priority class is cut, the corresponding mass is split. Let \(x_{r,\pi,j}\) be the resulting mass assigned to school \(j\).
For each priority cohort \(r\), define its rank distribution by
\[ D_{r,k}(\mu)= \frac{1}{\eta_r} \sum_{\substack{\pi,j\\ \operatorname{rank}_{\pi}(j)=k}} x_{r,\pi,j}, \qquad \eta_r=\sum_{\pi}\mu_{r,\pi}. \]
The continuous version of order symmetry is that \(D_{r,k}(\mu)\) is independent of \(r\) for every rank \(k\). With a scoring vector \(s\), its quantitative relaxation is
\[ \beta_s(\mu)= \frac{ \max_{r,r'} \left| \sum_k s_k\bigl(D_{r,k}(\mu)-D_{r',k}(\mu)\bigr) \right| }{ s_1-s_q }. \]
I would call the resulting problem Continuous Boston Order-Symmetry:
Given \(q\), \(\nu\), a finite type set \(T\), rational masses \(\mu\), a scoring vector \(s\), and an allowed family \(\mathcal R\) of school-priority profiles, choose \(\rho\in\mathcal R\) and an aggregate assignment \(x\) generated by the mass Boston mechanism so as to minimize \(\beta_s(\mu)\), subject to achieving at least the utilitarian welfare of cyclic-tiebreak Boston. A solution is the priority profile \(\rho\), the rational assignment table \(x\), and the exact value of \(\beta_s(\mu)\). The fixed-mechanism decision version asks whether \(\beta_s(\mu)=0\), or whether \(\beta_s(\mu)\le b\).
Theorem 5.1 supplies the central positive prediction: on the symmetric subfamily—most directly, populations invariant under the joint cyclic relabelling of schools and priority cohorts—the cyclic profile should have \(\beta_s(\mu)=0\). The paper’s stronger hypothesis is a fully symmetric probability measure over complete finite profiles; that is not identical to a population mass vector, so Theorem 5.1 does not already solve this problem. Rather, it is the named finite-agent result whose symmetry argument motivates the continuum theorem one would now prove.
For a fixed priority profile, this mirror is likely Class A. The mass Boston process can be simulated directly over the explicit type set in time polynomial in \(q\), \(|T|\), and the encoding length of \(\mu\); all resulting masses remain rational. The interesting optimization problem over arbitrary priority profiles may instead be hard for reasons living in the number of schools and priority orders, hence potentially Class B rather than continuum-specific hard. Restricting \(\mathcal R\) to cyclic rotations or another bounded family should remain tractable. Further questions include approximating the best priority profile, parameterizing by \(q\) or the number of preference types, and extending the symmetry theorem to non-neutral distributions such as discretized Mallows populations.
The mirror is plausible because it preserves the paper’s actual object: deterministic rank-based assignment under a priority rule. It does not replace assignment by a lottery or merely make outcomes fractional. Boston’s rounds, conflicts, priority orders, welfare comparison, and order-bias objective all survive. The only changes are school capacities and high multiplicity, both standard in the school-choice setting that motivates Boston.
My weakest point is that the paper’s order symmetry compares named agents after averaging over a probability measure on whole profiles, whereas the mirror compares priority cohorts after averaging over population mass. Correlations between agents’ preferences disappear from \(\mu\). A theorem for the continuum therefore needs either a genuine population-level symmetry assumption or a richer type carrying the relevant cohort correlation. The latter can make the type space as large as \((q!)^q\), weakening the high-multiplicity gain. Exact neutrality is also unrealistic for many districts. Thus this is not a claim that the whole paper continuizes cleanly; it is a focused, credible mirror for Theorem 5.1 and its order-bias mechanism-design question.
The proponent’s sole anchor, Theorem 5.1, fails ChoCo’s source gate. It is a fairness theorem about a fixed mechanism under a symmetric probability measure, not a theorem about complexity, algorithms, approximation, or parameterized computation. The paper never poses a computational search or decision problem. Defining one afterwards—choose a priority profile minimizing \(\beta_s\)—manufactures a new problem rather than continuizing a computational result. The same objection applies to the paper’s other numbered theorems: they concern symmetry, strategyproofness, or probabilistic formulas, not computational complexity.
The proposed model also does not faithfully take the paper’s high-multiplicity limit. Boston’s priority profile is a strict ordering of named agents for each object. If \(N\) agents and \(N\) object copies are used, every clone has a distinct priority position. Encoding that position as part of the type makes the number of types grow with \(N\), eliminating the intended compression. If agents are instead grouped into priority cohorts \((r,\pi)\), then the model has introduced tied priorities and proportional cutoff splitting. That is a natural school-choice extension, but it is no longer the paper’s cyclic-tiebreak Boston mechanism, and Theorem 5.1 does not apply to it.
The capacity change creates a second mismatch. The paper has \(n\) individually distinct objects and its theorem assumes full symmetry under permutations of all agents and all objects. The proposed model has \(q\) school types with capacities \(\nu_j\), repeated copies, and only a \(q\)-cycle of priorities. Invariance under that cycle is much weaker than invariance under the paper’s \(S_n\times S_n\) symmetry. A more faithful model would need to retain a distribution over complete preference profiles, including correlations between agents. The mass vector \(\mu_{r,\pi}\) contains only individual-type marginals and cannot represent those correlations. Adding profile-level configurations would make this a stochastic profile model rather than a compact continuous society.
The proposed objective is also weaker than order symmetry. \(D_{r,k}\) compares the average rank of a priority cohort, although agents in that cohort may have different rankings and different outcomes. The paper compares every named agent’s expected rank distribution. Requiring equality for each full type would change the problem; requiring equality only by cohort defines a new fairness criterion. Neither is a direct mirror.
For a fixed priority profile, the mass Boston process is simply a finite simulation over the explicit type list. The nontrivial search over priority profiles is a discrete permutation-design problem over schools and priority classes. That may be a legitimate new mechanism-design problem, but its substance comes from choosing permutations, not from continuizing the population, and it is not motivated by a computational result of this paper.
Thus Theorem 5.1 is defeated: its proposed mirror is neither anchored in a named computational result nor faithful under rational-clone expansion. A separate project on capacitated school types with tied cohort priorities could certainly be worthwhile, but it would be a new extension requiring new symmetry theorems. The strongest defensible negative verdict is therefore “no qualifying ChoCo mirror of this paper”; the universal claim that no independently valuable continuum school-choice model could ever be built is, honestly, stronger than the evidence permits.
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.