| paper | The Power of Local Manipulation Strategies in Assignment Mechanisms |
| authors | Timo Mennle, Michael Weiss, Basil Philipp, Sven Seuken |
| venue | IJCAI 2015 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The opponent wins on the required computational-result gate: Proposition 1 is an explicit counterexample to a heuristic, not a named algorithm, approximation guarantee, computational formulation, or hardness result; the PS NP-hardness is only cited. The proposed continuum question is statable, but preserving nonzero influence requires replacing one unilateral agent by a positive-mass coordinated cohort, so it is at best a re-modeling and cannot supply the missing qualifying anchor.
fails bit a — no named computational result to mirror
In a faithful continuum population an individual has zero mass and cannot change PS exhaustion times; the proposed positive-mass common-report cohort changes unilateral best response into coalition manipulation.
fatal: True
The candidate mirror covers only the PS EGM phenomenon of Proposition 1 and leaves Propositions 2–3, the behavioral and simulation Results 1–6, and the cited external NP-hardness uncovered.
Strictly speaking, this paper contains no qualifying named complexity anchor. It has no numbered theorem, lemma, corollary, or proposition asserting NP-hardness, membership in P, parameterized tractability, or a similar classification. The introduction only states, without a theorem number, that the PS manipulation problem was shown NP-hard by Aziz et al. [2015b]; that result is cited from elsewhere, not proved here. The paper’s Results 1–6 are empirical findings, not complexity theorems.
The strongest honest positive case therefore uses Proposition 1, proved in this paper, as a weaker computational anchor. It states that there exist exclusively globally manipulable situations for Probabilistic Serial. Specifically, with four agents, four objects, unit capacity, reports
\[ \succ_1,\succ_2:a\succ b\succ c\succ d,\qquad \succ_3:c\succ d\succ b\succ a,\qquad \succ_4:b\succ c\succ d\succ a, \]
and agent \(1\)'s utility vector \(u_1=(1.21,1.1,1.0,0.0)\), truthful reporting gives utility \(0.87\), while all adjacent-swap reports give strictly less—\(0.85\), \(0.86\), and \(0.79\). Nevertheless, the non-local report
\[ \succ_1^\star:b\succ c\succ a\succ d \]
gives utility \(0.92\). Thus local manipulation can fail even though a profitable global manipulation exists.
My continuous mirror would be Continuum-PS Cohort Best Response. An instance consists of:
The cohort chooses one reported ranking \(r\in\mathcal{P}(M)\); its mass is transferred from truthful type \(\succ^\star\) to reported type \(r\), while all other masses remain fixed. The continuum Probabilistic Serial eating process is then run on the resulting distribution. If \(x_j(r)\) is the allocation share of object \(j\) received by each cohort member, the objective is
\[ U(r)=\sum_{j\in M}u^\star(j)x_j(r). \]
The problem is to output a ranking
\[ r^\star\in\arg\max_{r\in\mathcal{P}(M)} U(r). \]
The corresponding EGM decision question asks whether
\[ U(\succ^\star)>U(r) \]
for every adjacent swap \(r\) of \(\succ^\star\), while some non-local ranking \(r^\star\) satisfies
\[ U(r^\star)>U(\succ^\star). \]
This is a genuine population mirror rather than merely another fractional-assignment model. Probabilistic Serial already has probabilistic outcomes; the new continuous object is the society itself. The natural regime is a large school-choice or course-allocation market with many applicants sharing a relatively small number of preference-and-utility types—for example, cohorts from the same district, curriculum, or advising programme. Object capacities scale with population, and the strategic cohort may represent a coordinated group of interchangeable applicants submitting a common ranking.
Proposition 1 embeds directly. Give the strategic cohort mass \(1/4\), give the other three original agent positions mass \(1/4\) each, and set every object’s capacity to \(1/4\). Replicating every position \(K\) times produces \(4K\) agents but the same type proportions and the same PS eating dynamics. The truthful, local, and non-local utilities remain \(0.87\), \(0.85/0.86/0.79\), and \(0.92\). Hence the phenomenon survives high multiplicity exactly, although “agent 1” has become a positive-mass cohort.
I would expect the underlying best-response problem to be Class B in the natural variable-\(m\), sparse-ranking representation: the paper reports external NP-hardness for discrete PS manipulation, and a finite instance can be converted into a rational mass distribution by cloning each agent type and scaling capacities. The combinatorics live in the ranking space and number of objects, not merely in the number of individually listed agents. For fixed \(m\) and explicitly represented support, exhaustive optimization is finite and straightforward; the interesting question is the variable-agenda regime.
The main weakness is substantial: a single individual has zero influence in an atomless population. A meaningful mirror must therefore replace unilateral manipulation by manipulation by a positive-mass, coordinated cohort. The paper’s authors would recognize the same mechanism, report space, utility objective, and local-search structure, but they might reasonably regard the coalition variant as a new problem. Also, Proposition 1 is not a complexity classification, so under the programme’s strict anchor rule this is only a conditional positive case, not a fully compliant complexity-theoretic one.
The strongest negative point is decisive at the programme’s gate: this paper contains no qualifying computational result. Its Propositions 1–3 are existence proofs of counterexamples to local search, not complexity classifications, algorithms, or hardness theorems. The NP-hardness of PS manipulation is merely cited from Aziz et al.; it is not a result of this paper. Results 1–6 are behavioural and simulation findings. Thus there is no named computational theorem here whose continuous analogue the programme is being asked to study.
Proposition 1 does not repair that omission. The proposed continuum instance is a valid normalization of the four-agent example: assign mass \(1/4\) to each type and capacity \(1/4\) to each object. Replicating every agent \(K\) times gives exactly the same PS eating process and the same utilities. But what is being preserved is only a finite existential witness, not a computational problem. The continuous statement “an EGM situation exists” is just the finite statement written in proportions. The issue is not that the answer happens to be unchanged; it is that the proposition never asserted an algorithmic question whose high-multiplicity version could expose the programme’s machinery.
There is also a genuine degeneracy in trying to preserve the paper’s actual strategic unit. In the paper, one agent deviates while the other reports are fixed. In a continuum population, that agent has mass zero. Under PS, a zero-mass agent does not affect exhaustion times. Conditional on those fixed exhaustion times, truthful reporting is optimal: at every moment the truthful ranking selects the most-preferred object that remains available, whereas a misreport can only select a less-preferred available object. The strategic externality that creates the EGM witness disappears. Hence the faithful individual-level continuum limit eliminates precisely the phenomenon Proposition 1 establishes.
The proponent avoids that degeneracy by giving the manipulator mass \(1/4\). That is not merely a continuization of the paper’s model; it is a coordinated-coalition manipulation problem. If the cohort must submit one common ranking, coordination is an additional assumption absent from the paper. If its members may report independently, there is no longer one report \(r\) and one best-response objective; one needs a distribution of reports, an equilibrium concept, or a coalition objective. The mechanism and ranking space are inherited, but the strategic problem is not.
The cited NP-hardness does not close this gap. Cloning the nonstrategic agents while retaining one manipulator makes the manipulator’s mass vanish, so it does not preserve the nontrivial PS manipulation phenomenon in the continuum limit. Cloning the manipulator as well preserves the phenomenon only by changing the problem to manipulation by a positive-mass coalition. That may be a sensible new research problem, but its hardness would be a result about that new problem, not a continuous mirror of the paper’s individual manipulation result.
The same diagnosis applies to the empirical claims about swaps, greedy search, and average performance. One could impose a distribution over agent types or over whole assignment instances, but those are different probability spaces: the paper’s simulations randomize finite situations, while population continuization aggregates agents. No computational statement in the paper identifies a canonical continuous object.
The negative case is therefore strongest on the programme’s stated eligibility criterion, and on the loss of unilateral influence in the genuine continuum limit. It is not airtight in the broader modelling sense: a coalition version of PS best response with high-multiplicity applicant cohorts could be worthwhile in its own right. But that would be a new computational-social-choice problem motivated by the paper, not a surviving named computational anchor from it.
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.