| paper | d4-conf-atal-2015-0332 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given a finite set of colleges \(C\), a finite support \(T\) of applicant types, rational masses \(\mu_t>0\) summing to \(1\), and rational capacity shares \(\kappa_c\), each type \(t\) has a complete ranking of colleges and a priority position at each college. Colleges have true complete rankings of types. Run student-proposing mass DA, in which unheld mass proposes to its next-ranked college and each college holds its highest-ranked applicant mass up to its capacity, splitting type mass at a cutoff if needed. For a target college \(c^\star\), compare its truthful allocation with the allocation produced when it reports an arbitrary complete ranking of types and all other reports stay fixed. Determine whether some report gives \(c^\star\) a strictly beneficial bundle under its true responsive preferences: after padding both bundles with vacant seats to capacity, there is a mass-preserving coupling under which every new type is weakly preferred to its paired truthful type, with strict improvement on positive mass.
A finite college set and finite support of applicant types with rational masses and capacity shares; mass DA routes and splits those masses, while one named college chooses a reported ranking of types. The objective is to decide whether the resulting allocation is strictly better for that college under its true responsive preferences.
The mirror covers Theorem 3’s single-college manipulation problem under student-proposing DAA; it leaves Theorem 4’s college-proposing result and the simulation findings aside.
The paper has no named hardness result, so the strongest anchor is its positive algorithmic result: Theorem 3. It says that, in a many-to-one market with complete preferences, deciding whether a given college can beneficially misrepresent its preferences under student-proposing DAA is solvable in polynomial time. The paper proves this by reducing the question to manipulation by a proposee in an associated one-to-one market, using the polynomial algorithm of Teo, Sethuraman, and Tan (2001). I would mirror this result alone.
Lead mirror: Type-Mass Student-Proposing DA Manipulation. Take a finite set \(C\) of colleges and a support \(T\) of \(\tau\) student types. A type specifies a student’s complete ranking of the colleges and their priority category at every college. Type \(t\) has rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Each college \(c\) has a rational capacity share \(\kappa_c\) and a complete ranking of the types. Mass DA runs student-proposing DAA: unheld mass proposes down its type’s ranking, and each college holds its highest-ranked applicants up to capacity, splitting a type’s mass if necessary.
The instance also names a target college \(c^\star\), whose true ranking is known. Ask whether there is a complete reported ranking \(\widehat{\succ}_{c^\star}\) of the types such that, with all other reports fixed, mass DA assigns \(c^\star\) a bundle that is beneficial under its true responsive preferences. Precisely, pad both its truthful and manipulated bundles with vacant seats up to \(\kappa_{c^\star}\). A manipulated bundle qualifies if there is a mass-preserving coupling from the truthful bundle to the new one in which every paired new type is weakly preferred to the old type (a filled seat is preferred to a vacancy), with strict improvement on positive mass. A solution is the report and the resulting allocation, with such a coupling as a witness. The complexity question is whether this can be decided and witnessed in time polynomial in \(m=|C|\), \(\tau\), and the input bit length \(L\).
A plausible regime is a large annual admissions or residency market with a modest, stable set of institutions. There may be \(N\) applicants but only \(\tau\ll N\) recurring preference-and-priority profiles; each institution’s capacity scales with the applicant pool, giving it share \(\kappa_c\). One target institution remains a named strategic actor, while positive masses of applicants can move through rejection chains. Each applicant still receives at most one institution: the fractional values describe how much of a type goes where. Continuum matching models already use a unit mass of applicants facing finitely many schools; for example, [Grigoryan’s continuum DA model](https://onlinelibrary.wiley.com/doi/10.3982/TE5478) studies the convergence of stable assignments. That supports the market regime. Its convergence question does not answer this computational manipulation question.
I would tentatively expect Class A, tractable, given the paper’s polynomial result and the finite type-level state space. But Theorem 3 does not establish that classification: expanding rational masses into individual copies can take time proportional to a denominator that is exponential in \(L\). A continuous algorithm must work with the masses directly. This leaves a concrete follow-up: can the paper’s one-to-one reduction be adapted to a mass representation with bit-length dependence, or does type-level manipulation introduce continuum-specific hardness?
The weakest point is the type-level treatment of colleges’ preferences. Compressing applicants into types makes a college indifferent among applicants of the same type, while the paper assumes strict rankings of individuals. That is a real co-modification, motivated by the high-multiplicity regime, but it may be unacceptable if the authors view individual tie-breaking as part of the manipulation problem. There is a related proof gap: Theorem 1’s structural claim that one rejected student can suffice has no literal atomless counterpart; changing an outcome may require rejecting positive mass. So the mirror is a credible research question, not a consequence of Theorem 3.
This mirror covers only Theorem 3’s single-college manipulation problem under student-proposing DAA. It does not claim to mirror the paper’s college-proposing FPT result or its simulation findings.
The paper does have a named computational result: Theorem 3, which decides in polynomial time whether a college can profitably misreport under student-proposing DAA. The proponent raises just this one anchor, and it is difficult to defeat under the programme’s criteria.
The strongest case against it is that the relevant types must preserve a lot of information. A student’s type needs to include their ranking of every college and their priority category at every college. Repeated student rankings alone are not enough: two otherwise identical applicants who occupy different places in colleges’ priorities can behave differently in the rejection chains that drive the manipulation. In many admissions markets, the support of these *joint* profiles may grow with the applicant pool, leaving little compression.
But that is a concern about how common the regime is, not a reason the mirror is ill-posed. Large cohorts with recurring rankings and priority categories are plausible, and the type-mass version keeps the relevant information. Scaling college capacities with the cohort is also an admissible co-modification. The proposed mass-DA model gives the manipulation question a concrete meaning: can one college change its ranking of types and obtain a positively larger bundle it prefers under a mass-preserving coupling?
The original proof’s one-student rejection argument will not simply carry over: a type may be split, and a manipulation may move positive mass through rejection chains. That weakens any claim that Theorem 3 already settles the continuous case. It does not weaken the research question; it identifies what the mirror would need to resolve. Existing continuum DA work on convergence or stable assignments does not answer this computational manipulation question.
So the negative case is weak. The joint-type requirement may make the mirror a poor fit for some matching markets, but it does not rule out a sensible high-multiplicity regime. I cannot honestly defeat this anchor; on the material given, the continuous mirror survives.
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.