| paper | d4-conf-ecai-2020-0223 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard parameterized by \(k_{\max}\); not \(\mathrm{FPT}\) unless \(\mathrm{FPT}=\mathrm{W}[1]\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given item categories \(I\) with rational supplies \(q_i\), a finite set of types \(T\) with masses \(\mu_t>0\), their strict rankings and turn schedules, and a positive-mass manipulator type \(t^\star\) with a true ranking and additive utility \(u\), does there exist a common reported ranking for \(t^\star\) that gives its members greater average utility than truthful reporting? At each scheduled occurrence of a type, its mass takes one unit per member from the remaining supplies, greedily by its ranking.
Use a finite type set \(T\), masses \(\mu_t\) summing to \(1\), item categories \(I\) with rational per-capita supplies \(q_i\), and a fixed ordered schedule of type occurrences. Each type specifies a complete ranking and schedule; the distinguished type \(t^\star\) has a common truthful ranking and additive utility \(u\), and all its members use one reported ranking \(\succ\). Let \(x_{r,i}\) be the mass of category \(i\) taken at occurrence \(r\); its objective is the cohort's per-member utility \(U(\succ)=\mu_{t^\star}^{-1}\sum_{r:t_r=t^\star}\sum_{i\in I}u(i)x_{r,i}\).
A positive-mass manipulator must share one report across the cohort, making this a coalition deviation; the paper's engagement with coalition manipulation supports recognition but does not make the deviation unilateral.
fatal: False
The mirror covers the successful-manipulation decision in Theorem 9 and the optimal-manipulation problem in Theorem 10; it leaves the paper's parameterized algorithm bounds and welfare-ratio result unaddressed.
The strongest mirror is a cohort version of sequential allocation. It keeps the paper’s central decision—a manipulator chooses a ranking that changes what they receive under a fixed picking schedule—while allowing many agents with the same complete role description to be represented by mass.
Let \(I\) be a finite set of good categories, with rational supplies \(q_i\), and let \(T\) be a finite set of agent types with masses \(\mu_t>0\), where \(\sum_t\mu_t=1\). A type specifies a strict ranking and its full turn schedule; the manipulator type also specifies its true ranking and additive utility \(u(i)\). A finite ordered schedule lists types \(t_1,\ldots,t_R\). At each occurrence of \(t\), mass \(\mu_t\) takes one unit per member from the remaining goods, greedily following its ranking. Goods are divisible stock, so the type’s average allocation can be fractional even though each infinitesimal member makes an ordinary pick.
The manipulator is a positive-mass cohort \(t^\star\). Its members use one common reported ranking \(\succ\). If \(x_{r,i}\) is the mass of good \(i\) taken at stage \(r\), the cohort’s per-member utility is
\[
U(\succ)=\frac{1}{\mu_{t^\star}}\sum_{r:t_r=t^\star}\sum_{i\in I}u(i)x_{r,i}.
\]
Truthful reporting gives the baseline \(U(\succ^\star)\). This preserves the paper’s ordinal report, fixed schedule, greedy choices by everyone else, and additive utility objective. It does not relax the manipulator’s choice into a fractional allocation.
This is a genuine high-multiplicity model. For rational masses, choose a common denominator \(Q\): represent type \(t\) by \(Q\mu_t\) identical agents and good \(i\) by \(Qq_i\) copies. Put each type’s copies consecutively at each corresponding schedule stage. The continuum process then gives exactly the per-member outcome of the clone instance. Thus type-level fractional averages arise from many agents sharing a role, and per-capita supplies scale with population.
My lead is Fluid Successful Manipulation: given the types, masses, goods, supplies, schedule, manipulator’s true ranking and utility, determine whether some common reported ranking satisfies \(U(\succ)>U(\succ^\star)\). Its parameter is \(p_{\max}\), the maximum number of scheduled picks per member of any type.
The anchor is Theorem 9, proved here. It states that deciding whether \(a_1\) has a successful manipulation is W[1]-hard with respect to \(\mu^{\mathtt{max}}\), the largest number of picks received by any agent. The proof reduces from CLIQUE: its constructed instance has \(\mu^{\mathtt{max}}=\mu(a_1)=k(k+1)/2+1\), and whether the manipulator can beat truthful utility encodes whether the graph has a \(k\)-clique. The clone-to-mass correspondence gives a concrete route for carrying that hardness into the fluid problem. I expect hardness to transfer: the reduction’s choices over goods and agent roles remain present after scaling, rather than depending on one-person mass granularity.
A second question is Fluid Optimal Manipulation: on the same input, return a ranking maximizing \(U(\succ)\). Its parameter is \(\tau=|T|\), the number of positive-mass complete types. The anchor is Theorem 10, also proved here: \(\MSA\) is W[1]-hard with respect to the number \(n\) of agents. The proof reduces from Multicolored Clique using Sidon sequences to encode vertex choices and pairwise edges; the construction has \(k(k+1)+2\) agents. In the cohort model, the corresponding parameter is support size \(\tau\), not total population size. Since one can scale each role into a large cohort while retaining finitely many types, I expect this hardness to transfer as well.
These anchors cover the paper’s successful-manipulation decision and optimal-manipulation objective. They do not cover its FPT results or its welfare-ratio bound. The paper’s general NP-hardness statement in Section 2 is cited from Aziz et al.; I have not used it as an anchor.
The weakest point is the strategic actor: the paper studies one named manipulator, while this mirror gives a common reporting decision to a whole cohort. That is a real change in strategic semantics. A large coordinated course-allocation cohort or a representative acting for many identical participants makes it plausible, and the exact clone scaling supports it mathematically, but the authors might still regard it as coalition manipulation rather than their individual problem. The case depends on whether they accept that cohort-level decision as the natural high-multiplicity form of the same manipulation question.
The strongest objection is a dilemma about the manipulator’s mass. It applies to both anchors, because Theorems 9 and 10 concern a single agent’s unilateral change of report. The manipulation in this paper works through feedback: the agent’s picks change what remains for later pickers, which in turn changes what the agent can get on later turns.
Keep that agent as an individual in a continuum population, and their mass is zero. With supplies scaled per capita, their picks no longer change the aggregate stock seen by other types. The background flow is therefore independent of their report. Since their true ranking agrees with their additive utility, reporting truthfully lets them take the highest-utility available good at each turn; misreporting cannot improve a later choice by changing what others take. The successful-manipulation question anchored on Theorem 9 then loses its strategic effect, and the optimal-manipulation question anchored on Theorem 10 loses the feedback that makes optimization nontrivial.
Give the manipulator positive mass to preserve that feedback, and the actor becomes a cohort. The proposed mirror requires its members to use one common report. That is a coordinated coalition decision, not the paper’s unilateral deviation. If the members can report independently, the problem instead concerns a profile of deviations or a strategic interaction among them; there is no longer one manipulator choosing one ranking. High multiplicity justifies grouping agents with the same complete type. It does not make them share a decision. So Theorem 9’s W[1]-hardness and Theorem 10’s W[1]-hardness may well carry to the cohort coalition problem, but that would support a related research question, not establish a continuous mirror of either theorem as stated.
The proponent’s scaling argument can make the cohort process mathematically exact for a batch schedule. That is a virtue of the cohort model, but it does not remove the semantic change: either the actor is an atom with no aggregate influence, or a positive-mass bloc with a shared strategy. I do not see a way to retain both the paper’s individual manipulator and the consequential feedback that drives its results in a population continuum.
This is a strong case against a faithful mirror, but it is not an airtight case against every worthwhile extension. A central representative for a large bloc could be a plausible setting, and its fluid manipulation problem could be worth studying. If the authors accept that coalition question as their problem, the two anchors survive in that revised sense. My honest negative case is therefore weakest exactly there: the boundary between a useful cohort extension and a different strategic problem.
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.