| paper | Strategyproof and Fair Matching Mechanism for Ratio Constraints |
| authors | Kentaro Yahiro, Yuzhe Zhang, N. Barrot, M. Yokoo |
| venue | ATAL 2018 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.6
statement extracted from the paper’s text layer
Given finite schools \(C\), finite complete types \(\Theta\) with rational masses \(\mu_\theta\), type-specific school preferences, school priority classes with boundary-mass splitting, rational \(\alpha\), and cyclic order \(\sigma\), compute exactly the event-driven mass-QRDA outcome, including \(x_{\theta,c}\), the quota-breakpoint sequence, and the first ratio-feasible stage.
A high-multiplicity school-choice market with \(x_{\theta,c}\ge0\), \(\sum_c x_{\theta,c}=\mu_\theta\), loads \(y_c=\sum_\theta x_{\theta,c}\), ratio constraints \(y_c\ge\alpha y_{c'}\), and event-driven student-proposing deferred acceptance with quota reductions following \(\sigma\).
Strict school priorities make complete repeated types impossible unless individual tie-breaking is removed; the fluid repair changes priority, fairness, and rejection accounting, and the proponent does not establish that this remains faithful to the paper’s exact mechanism.
fatal: False
The mirror directly covers QRDA execution and can investigate continuous analogues of Theorems 3.1, 3.5, and 3.9; it leaves ACDA and ESDA comparisons, nonwastefulness experiments, and the extended minimum-quota model largely untreated.
The strongest honest case is a high-multiplicity school-choice mirror of the paper’s ratio-constrained matching problem. It is a narrower positive case than “continuize all of QRDA,” because the paper contains no NP-hardness result. Its best computational anchor is therefore algorithmic.
The lead problem is Continuous QRDA Execution. An instance has a finite school set \(C\), a finite set of complete student types \(\Theta\), rational masses \(\mu_\theta\) with \(\sum_{\theta\in\Theta}\mu_\theta=1\), a strict school ranking \(\succ_\theta\) for every type, a priority ranking of types at each school, a rational ratio parameter \(\alpha\in[0,1]\), and the cyclic school order \(\sigma\) used by QRDA.
A type is complete: agents of type \(\theta\) have the same school preferences and the same priority status at every school. This describes, for example, a large annual university-admissions cohort in which many applicants share a preference order and the same publicly known admissions-priority profile. There may be hundreds of thousands of students but only a moderate number \(\tau=|\Theta|\) of distinct profiles. Schools and the ratio policy remain exactly those of the paper.
The decision variable is a mass assignment \(x=(x_{\theta,c})\), where \(x_{\theta,c}\) is the mass of type \(\theta\) assigned to school \(c\). It must satisfy
\[ x_{\theta,c}\ge 0,\qquad \sum_{c\in C}x_{\theta,c}=\mu_\theta. \]
The load of school \(c\) is \(y_c=\sum_\theta x_{\theta,c}\), and ratio feasibility requires
\[ y_c\ge \alpha y_{c'} \qquad\text{for every }c,c'\in C, \]
equivalently \(\min_c y_c/\max_c y_c\ge\alpha\). This is not fractionalizing an individual’s assignment: every infinitesimal student is assigned integrally to one school; \(x_{\theta,c}\) records the aggregate mass of such students.
The continuous mechanism runs a mass version of student-proposing deferred acceptance. A type sends its currently rejected mass down its preference list. Each school retains the highest-priority applicant mass up to its current quota, possibly splitting a boundary type’s mass. Begin with
\[ q_{\max}=\frac{1}{1+\alpha(m-1)}, \]
the normalized analogue of the paper’s largest admissible artificial quota. Then reduce quotas in the cyclic order \(\sigma\), using the next breakpoint at which the mass DA outcome changes, and stop at the first ratio-feasible outcome. The requested output is the resulting mass assignment, together with the finite sequence of DA breakpoints certifying that it is the first stopping outcome. The intended objective is the same mechanism-design objective as in the paper: produce a fair, ratio-feasible, student-proposing outcome, rather than maximize an unrelated scalar welfare function.
The principal anchor is Theorem 3.6, proved in this paper. It states that QRDA has time complexity \(O(n\times m)\), assuming school-feasibility can be checked in constant time. The reason is that QRDA repeatedly applies deferred acceptance, and each student can be rejected by each school at most once, so the total number of DA steps is at most \(n m\).
The continuous question is whether this individual-rejection bound has a genuine type-level analogue:
Given \((C,\Theta,\mu,\succ,\pi,\alpha,\sigma)\), can Continuous QRDA Execution be solved exactly in time polynomial in \(m\), \(\tau\), and the input bit length?
The expected answer is Class A, though this is a new result rather than something proved by the paper. Individual rejection events should collapse to type–school breakpoints. Ratio feasibility is itself a system of linear inequalities, and the mass DA process can be represented by a finite flow-like computation over priority types. Checking feasibility takes \(O(m)\), rather than the paper’s constant-time assumption, but this does not threaten polynomiality. The finite theorem supplies the structural clue: the algorithm’s work is controlled by rejection opportunities, and in the high-multiplicity regime the relevant opportunities are type–school pairs rather than named students.
The paper’s Theorems 3.1 and 3.5 provide the properties that this continuous execution problem should preserve, although I do not count them as separate computational anchors. Theorem 3.1, proved here, says that QRDA returns a feasible and fair matching. Theorem 3.5, also proved here, says that QRDA is strategyproof. In the mirror, fairness becomes absence of positive-mass justified envy between priority types, and strategyproofness is naturally stated for a representative infinitesimal agent, or more strongly as stochastic dominance for the mass assigned to a type. The paper’s Theorem 3.9 also suggests a further continuous comparison: construct the mass versions of QRDA and ACDA and test whether every type weakly prefers the QRDA assignment.
This is a credible continuization because the paper’s central object is already a population constraint: the ratio between the least- and most-populated schools. Replacing counts by masses changes the regime without changing the policy question. The natural many-agent scenario is not a seven-person committee; it is a large, repeated admissions or residency cycle with a fixed set of schools, hospitals, or university courses and a relatively small number of preference-and-priority profiles. For rational masses \(\mu_\theta=n_\theta/N\), the continuous society has an immediate finite realization by replicating each type \(n_\theta\) times. Conversely, large finite markets with repeated profiles are precisely the instances for which the continuous representation is intended.
The weakest point is that the paper’s QRDA reduces quotas by one student at a time, whereas the continuum has no canonical unit decrement. The event-driven breakpoint rule is therefore a genuine co-modification, not a literal transcription. Strict individual school priorities also become priority classes within a type, and unilateral strategyproofness may become partly trivial because one atomless agent cannot change aggregate loads. A sceptic could reasonably argue that the interesting part of Theorem 3.5 is weakened in the limit.
That weakness does not eliminate the mirror. The ratio constraint, deferred-acceptance process, priority structure, fairness requirement, and student-side manipulation question all remain; only the population representation changes. The main follow-up results would be to prove polynomial termination of event-driven QRDA, establish whether the paper’s strategyproofness theorem survives for positive-mass type coalitions, determine whether the QRDA-over-ACDA welfare guarantee survives, and identify whether any hardness can reappear when priority types, geographic eligibility, or other indivisibilities are added.
The proposed mirror has one genuine vulnerability, but it is not quite as strong as the proponent suggests. The only qualifying computational anchor is Theorem 3.6. Theorems 3.1 and 3.5 are correctness and strategyproofness results, while Theorem 3.9 is a welfare comparison; none is itself a complexity result.
Theorem 3.6 does not, however, transfer cleanly to a finite-type continuum. Its \(O(nm)\) bound counts rejection events of named students under strict school rankings. In the paper’s model, each school has a strict order over \(S\). Since a type must include every feature relevant to the problem, including priority status, two students cannot literally share a complete priority type: at every school their strict ranks distinguish them. Thus an exact type representation has \(\tau\) growing with \(n\). Normalising the student counts into masses changes notation but produces no high-multiplicity regime.
The proponent’s repair is to replace strict individual priorities by priority classes and split a boundary class when a quota cuts through it. That is a reasonable new matching model, but it is not merely the continuous version of the paper’s model. If ties are resolved by an exogenous individual tie-breaker, the lost identities return and the compression disappears. If ties are resolved by splitting mass, the paper’s fairness predicate and rejection-chain proof have been replaced by positive-mass notions. The paper proves neither that this fluid DA process has finitely many relevant breakpoints nor that their number is polynomial in \(m\) and \(\tau\). The proposed \(O(m\tau)\)-style compression is therefore a new conjecture, not a consequence of Theorem 3.6.
The same dilemma affects the paper’s substantive mechanism results. For an atomless individual, a unilateral misreport changes zero mass and cannot change the aggregate outcome, so Theorem 3.5 becomes vacuous. Making a whole type report jointly restores strategic content only by replacing individual strategyproofness with a coalition or cohort game. Likewise, a type may be split among several schools, so “every student weakly prefers QRDA” in Theorem 3.9 must become stochastic dominance or an average-rank comparison. Both are potentially interesting, but neither is the theorem proved in the paper.
The obvious stronger scenarios do not resolve this dichotomy. A large admissions cohort with repeated preference profiles still needs either priority bands, which alter the mechanism, or an individual score/tie-break coordinate, which makes the type space grow with the population. Ignoring priorities makes the population compressible but removes the very fairness and deferred-acceptance structure the paper studies.
So the strongest negative conclusion is that no faithful, non-vacuous mirror of the paper’s central mechanism survives: preserving strict priorities destroys multiplicity, while preserving multiplicity changes the matching and strategic objects. The remaining problem would be a worthwhile new study of fluid deferred acceptance, but its polynomial execution and properties are not a continuous consequence of this paper.
I would not claim the universal negative without qualification. If ChoCo accepts a priority-band fluid matching model as an author-recognisable extension, the proponent has a narrow surviving anchor in Theorem 3.6. The negative case is strongest as an argument that this is a new matching programme, not a compelling continuization of this particular paper.
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.