| paper | Complexity of Manipulating Sequential Allocation |
| authors | H. Aziz, S. Bouveret, J. Lang, Simon Mackenzie |
| venue | AAAI 2017 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finite role types \(A\), item types \(O\), rational role masses \(\mu_a\), item supplies \(\beta_o\), an ordered template of blocks \((a_q,\lambda_q)\), fixed rankings for nonstrategic roles, a common additive utility \(u_h\) for strategic cohort \(h\), and threshold \(\theta\), does there exist a strict report \(\widehat{\succ}_h\) such that sequential highest-ranked allocation of block mass, with marginal blocks split across item types, gives \(h\) average utility at least \(\theta\)?
Role and item types carry rational mass, ordered blocks preserve the paper's temporal structure, aggregate variables \(x_{q,o}\) record mass receiving item \(o\), and the strategic cohort chooses one ranking to maximise \(\frac{1}{\mu_h}\sum_{q:a_q=h}\sum_o u_h(o)x_{q,o}\).
The fluid block rule and positive-mass common-report manipulator are not forced by the paper's individual-agent sequence, so the mirror is a coalition extension rather than the literal atomless limit of individual best response.
fatal: False
The mirror covers Theorem 1's NP-completeness result and leaves Theorem 2, Corollary 1, the two-agent lemmas, counterexamples, and correction of prior claims unmirrored.
There is a defensible positive case, but it is a narrow one: a genuine high-multiplicity, fluid version of the paper’s main hardness result. I would make Theorem 1 the sole anchor.
Theorem 1, proved in this paper, states that computing a best response for sequential allocation is NP-complete. Its decision version is: given the fixed preferences of the non-manipulators, the picking sequence, the manipulator’s additive utility function \(u:O\to\mathbb{N}\), and a target \(T\), can the manipulator report a preference ordering that gives them utility at least \(T\)? Membership in NP follows by simulating the mechanism and evaluating the resulting bundle. Hardness is proved by reduction from the restricted NP-complete version of \(3\)-SAT in which every literal occurs exactly twice.
My continuous problem would be Sequential-Allocation Cohort Best Response\(_\infty\).
An instance has a finite set of item types \(O\), a finite set of complete agent-role types \(A\), rational masses \(\mu_a\) for the roles, and a finite turn template \(\sigma=(a_1,\ldots,a_L)\). A role type includes everything relevant to the mechanism: its fixed ranking, its turn positions in \(\sigma\), and, for the strategic role \(h\), its common cardinal utility \(u_h\). Items have rational per-capita supplies \(\beta_o\), with \(\sum_o\beta_o=\sum_q\mu_{a_q}\).
At turn block \(q\), a mass \(\mu_{a_q}\) of exchangeable agents of type \(a_q\) receives items according to the paper’s sequential rule. They take their highest-ranked available item; if its remaining supply is insufficient, that supply is assigned and the remaining mass proceeds to its next-ranked item. Thus the aggregate allocation is fractional, but every infinitesimal agent still receives an integral item at every turn. The variables \(x_{q,o}\) record the mass of type \(a_q\) receiving item \(o\) at block \(q\).
All reports are fixed except for the strategic role \(h\), which may choose any strict ranking \(\widehat{\succ}_h\). Its objective is average additive utility,
\[ U_h(\widehat{\succ}_h) = \frac{1}{\mu_h} \sum_{q:a_q=h}\sum_{o\in O}u_h(o)x_{q,o}. \]
The decision question is whether there exists a report \(\widehat{\succ}_h\) such that \(U_h(\widehat{\succ}_h)\geq \theta\). A solution is the report itself, together with the induced mass allocation.
This is a plausible regime for repeated course-seat allocation, school placement, or other sequential assignment systems with large cohorts of exchangeable applicants. There may be \(K\) copies of every role type and \(K\) copies of every item type, while the number of distinct role and item types remains fixed or moderate. The population is then \(K|A|\), but the type count is only \(|A|\). A department, applicant class, or institutional representative can submit one common ranking for its homogeneous cohort. That common ranking is the continuous analogue of the paper’s manipulator report.
The reduction from the paper survives exactly. Given a finite instance with \(n\) agent roles and \(m\) items, assign mass \(1/n\) to each role type and supply \(1/n\) to each item type. Each turn block then has mass \(1/n\), and the fluid process reproduces the original sequential allocation after scaling all quantities by \(1/n\). The manipulator’s average utility is exactly its finite utility. Clearing denominators gives the same construction with \(K\) exchangeable copies of every role and item, so the regime can genuinely have many agents per type.
Consequently, this mirror should be expected to lie in Class B: hardness transfers from the discrete problem. The important combinatorics in Theorem 1 live in the ordering of turns, items, clause gadgets, and preference rankings—not in idiosyncratic population counts. Replacing repeated agents by rational mass therefore does not remove the SAT structure. The mirror is not an outcome-space relaxation: individuals still receive indivisible items, with fractions appearing only as aggregate mass.
The main weakness is real. In the paper, the manipulator is one named agent; in the continuous model, the strategic unit is a positive-mass homogeneous cohort with a common report. If members of the cohort could submit independent rankings, the problem would become a distribution-over-reports or coalition-manipulation problem, not literally the paper’s best-response problem. I would not hide that change. The defence is that the underlying computational question remains identical—choose a ranking to maximize additive utility under the same sequential mechanism—and a common report is natural when the repeated agents are represented by one institutional or cohort-level decision. If the referee insists that only infinitesimal unilateral deviations count, then this particular mirror fails; atomless individual deviations have no aggregate effect.
Further work would ask whether mixed reports across a cohort convexify the problem, whether the two-agent polynomial boundary in the paper’s cited Theorem 2 extends to two role types, and how complexity depends on the number of types, item types, or turn blocks. The strongest claim, however, is already clear: Theorem 1 supports a precise continuous-population problem whose expected answer is transferred NP-hardness, not tractability.
Theorem 1 is a genuine computational anchor, so the negative case cannot rest on what the answer would be. The difficulty is that sequential allocation has no population state that can be quotiented cleanly while preserving the strategic problem.
In this mechanism, an agent’s turn position is computationally substantive. Two agents with identical preferences but different positions in the sequence are not interchangeable: they face different remaining inventories. Thus a complete type must include its turn pattern. In the reduction, the choice, clause, and collection rounds encode the SAT assignment through precisely these positions. If positions are retained, assigning mass \(1/n\) to each named role is merely a rescaled copy of the finite instance; the “continuous society” has not replaced the relevant individual structure. If positions are omitted, the mass distribution is insufficient to determine the outcome.
The proposed fluid block rule introduces a new mechanism. A block of mass acts synchronously, possibly splitting across item types, whereas the paper’s mechanism orders individual picks. Different ways of refining the same masses—periodic repetition, grouping all copies of a role, or interleaving reports—can produce different strategic environments. The paper supplies no canonical population limit that selects one of these.
More seriously, the individual best-response problem degenerates in an atomless population. A single agent has measure zero, so changing their report cannot affect the residual inventory faced by later agents. The SAT reduction depends exactly on the manipulator’s individual picks removing items that later agents would otherwise take. Preserving that externality requires giving the manipulator positive mass.
But a positive-mass manipulator is no longer the paper’s agent. It is a coordinated coalition of identical agents required to submit one common ranking. That common-report constraint is not forced by continuization; it is an added institutional assumption. If cohort members may report independently, the strategic object becomes a distribution over rankings and hence a different coalition-manipulation problem.
The proponent’s claim that the reduction “survives exactly” therefore overstates the case. The mass assignment \(1/n\) is just a scaling of the original finite run. Obtaining genuine multiplicity requires duplicating every role and item and imposing a common cohort report, thereby changing both the strategic unit and the mechanism’s temporal interpretation. The resulting cohort problem may be well-posed, but it is better described as a new fluid coalition model than as the continuous mirror of Theorem 1.
That is the strongest negative case. It is not airtight: a course-allocation institution with a homogeneous cohort submitting one ranking could make the cohort model plausible, and under the programme’s permissive standard that is a defensible mirror. So I would reject the proponent’s claim of an exact preservation, but I could not honestly maintain that every worthwhile continuous version is ruled out.
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.