| paper | Manipulating the Probabilistic Serial Rule |
| authors | H. Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Nina Narodytska, T. Walsh |
| venue | ATAL 2015 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, even when every house has capacity \(1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
Given finite houses \(H\), rational capacities \(\kappa_h\), and a distribution \(\mu\) over complete agent types, with a designated type \(t^\star\) of mass \(\rho>0\), identical true ranking and utility \(u^\star\), and all other types truthful, choose one strict report \(r\) for the cohort. Run continuum PS with each reported type's mass eating at unit rate and house \(h\) having capacity \(\kappa_h\); ask whether \(U(r)=\rho^{-1}\sum_{h\in H}u^\star(h)x_{r,h}\ge T\), or compute a maximizing \(r\), where \(x_{r,h}\) is the cohort's allocation.
Positive-mass high-multiplicity manipulation of probabilistic serial: types carry population mass, a strategic cohort chooses a common ranking report, continuum PS determines its allocation, and the objective is maximizing its average expected utility.
The mirror covers Theorem 3's general-case EU-BR hardness and leaves Theorem 1's DL algorithm, Theorem 2's two-agent EU algorithm, and related special-case propositions untouched.
The strongest honest case is a positive-mass, high-multiplicity version of the paper’s expected-utility manipulation problem. This is a genuine population continuization, not merely a restatement of PS’s already-fractional outcomes.
The lead anchor is Theorem 3, proved in this paper. It states that EU-BR is NP-hard. More explicitly, with three or more agents, fixed strict preferences for all agents except agent \(1\), cardinal utilities \(u:H\to\mathbb N\) for agent \(1\), and a target utility \(T\), it is NP-complete to decide whether agent \(1\) can report some strict preference order whose PS allocation gives expected utility at least \(T\). The proof reduces from a restricted NP-complete version of \(3\mathrm{SAT}\) in which every literal appears exactly twice. Thus the theorem concerns the underlying manipulation problem, not merely an encoding: the manipulator chooses a ranking, PS produces the allocation, and the ranking is successful if the manipulator’s expected utility reaches \(T\).
I would mirror it as follows.
Call the problem Positive-Mass EU-PS Best Response\(_\infty\). An instance consists of a finite house set \(H\), rational per-capita house supplies \(\kappa_h\), and a society distribution \(\mu\) over complete agent types. A type contains the agent’s true strict ranking, cardinal utility function, and any eligibility information relevant to assignment. There are \(\tau\) types and total population mass \(1\). A designated type \(t^\star\) contains a strategic cohort of mass \(\rho>0\); its members have the same true ranking and utility \(u^\star\). All other mass reports truthfully.
The cohort chooses one strict report \(r\) over \(H\). The reported population distribution is obtained by moving mass \(\rho\) from the truthful report of \(t^\star\) to \(r\). The continuum PS rule then has every reported-ranking mass eat its most preferred currently available house at unit speed, with house \(h\) having capacity \(\kappa_h\). Let \(x_{r,h}\) be the amount of house \(h\) consumed by the strategic cohort. Its payoff is \(U(r)=\frac{1}{\rho}\sum_{h\in H}u^\star(h)x_{r,h}\). The problem asks for a report \(r^\star\) maximizing \(U(r)\), or, in decision form, whether some report satisfies \(U(r)\ge T\).
The per-capita supply parameter is important. If an \(N\)-agent finite instance is embedded by setting \(\mu_t=n_t/N\), \(\rho=1/N\), and \(\kappa_h=1/N\), the continuum eating process is exactly the finite PS process after scaling all masses and capacities by \(1/N\). The strategic cohort’s normalized allocation is therefore the original agent’s allocation, and its expected utility is unchanged. This gives a clean upward bridge from Theorem 3: the unrestricted continuous problem should be expected to be Class B, with NP-hardness transferring from the discrete problem.
The regime is plausible in school-seat, course, housing, or public-resource assignment. A large population may contain many repeated cohorts—students with the same preference order and utility scale, applicants from the same district, or employees with the same ranked set of eligible positions—so \(N\) can be very large while \(\tau\ll N\). A cohort may coordinate a common report, for example through a union, school, district, or advice platform. The mass \(\rho\) is then the honest continuum analogue of the manipulator’s influence. The paper’s authors should recognize the model: the houses, PS dynamics, strict-ranking report, and EU objective are unchanged; only the one named manipulator becomes a positive-mass bloc of otherwise indistinguishable agents.
This formulation also exposes the programme’s central question. The general problem remains hard because the finite problem embeds exactly. But the printed reduction does not show hardness when the number of preference-and-utility types is much smaller than the population and every strategic cohort has substantial mass. That restricted high-multiplicity regime could instead admit an algorithm based on the event structure of PS, dynamic programming over report positions, or a configuration/convex formulation. The finite theorem therefore supplies the right hard anchor while leaving a substantive continuization question: does NP-hardness survive when population multiplicity, rather than the number of individualized agents, is removed?
The weakest point is unavoidable: an individual deviation has zero effect in a genuinely atomless society. Replacing agent \(1\) by a positive-mass bloc changes the strategic problem. I think that change is principled rather than cosmetic—the continuum analogue of individual manipulation must be bloc manipulation, just as a mass transfer replaces a one-voter edit in other ChoCo mirrors—but the paper itself does not prove that its NP-hardness reduction works for repeated types or positive-mass blocs. Accordingly, I would claim a strong, precise mirror of Theorem 3 and transferred hardness for the unrestricted rational-mass problem, while presenting tractability or hardness in the genuinely compressed \(\tau\ll N\) regime as the new research question.
This mirror deliberately covers only Theorem 3. I would not stretch it to the paper’s Theorem 1 on lexicographic best response or Theorem 2 on the special two-agent case: both are useful algorithmic neighbours, but their proofs depend on individual-agent or exactly-two-agent structure that does not transfer as cleanly to a positive-mass population.
The best case against this anchor is that it does not actually produce a continuous version of the paper’s problem without changing the strategic object.
Theorem 3 concerns one named agent whose report changes the PS trajectory by an amount of order \(1/N\). If the finite instance is embedded with total population mass \(1\), house capacities \(\kappa_h=1/N\), and manipulator mass \(\rho=1/N\), the proposed continuum process is exactly the finite process after rescaling. But this is a vanishing atom, not a genuine positive-mass limit. The reduction therefore establishes only that an unrestricted rational-mass formulation can encode the finite problem. It says nothing about the regime the continuization programme chiefly seeks: fixed, non-negligible type masses with many repeated agents.
The obvious repair is to give the strategic type fixed mass \(\rho>0\). That avoids degeneration, but it changes the problem from individual manipulation to coordinated coalition manipulation. The paper explicitly treats coalition manipulation as a separate direction for future work. A type distribution does not by itself imply that all agents of one type must submit the same report. If they deviate individually in an atomless population, each has zero influence and best response becomes vacuous. If they coordinate on one report, coordination is an additional institutional assumption; if they may split their mass across reports, the object becomes a mass-reallocation or coalition-optimization problem not studied in the theorem.
The hardness bridge also gives no evidence for this repaired model. The reduction’s timing construction depends on a single manipulator interacting with many carefully arranged literal agents and duplicate gadgets. Replacing those agents by large repeated cohorts changes the eating rates and synchronization equations. Likewise, replacing the manipulator by a positive-mass bloc changes every subsequent event time. Thus the only direct transfer is through the vanishing-mass embedding, precisely where the proposed continuum has not removed individual-level structure.
One could nevertheless formulate a respectable problem: a positive-mass cohort with common ordinal preferences and utility chooses a common report, or redistributes its mass among reports. The houses, PS dynamics, and expected-utility objective would all remain recognizable to the authors, and the finite-to-continuum scaling would be mathematically clean. That is a genuine research question about high-multiplicity coalition manipulation. It is not, however, the paper’s named EU-BR problem, and the paper supplies no reason to regard the resulting model as anything more than a new strategic extension.
This is where the negative case fails. There is no identity obstruction once a cohort is treated as the strategic unit; the objective is an average over identical agents; and positive mass prevents the limit from collapsing. The paper contains a named computational theorem, and its setting—school seats, course places, or housing assignments with repeated preference cohorts—is entirely plausible. Existing fractional outcomes do not defeat the mirror, since the population, not merely the allocation, is being continuized.
So the strongest honest conclusion is not that no worthwhile mirror exists. It is narrower: the proponent overstates the theorem’s direct hardness transfer, because the embedding uses a vanishing strategic atom and the genuinely positive-mass version is coalition manipulation. But that repaired version survives as a worthwhile continuous mirror, and therefore the universal negative claim cannot be sustained.
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.