| paper | d4-conf-atal-2013-0043 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
The named results are computational, but each studies a single designated manipulator. A positive-mass coordinated type changes that actor into a coalition, a distinction the paper itself recognizes; retaining the committee utility and tie-breaking rules does not preserve the anchored question. A unilateral manipulator's mass vanishes in the continuum, leaving influence only at score ties.
fails bit b-changes — the continuum limit changes the question
The proposed bloc formulation would cover Theorems 3.1, 4.1, and 4.2, but none survives as a continuous-population mirror; the paper proves no hardness result.
There is a credible positive case, but it is for the paper’s tractability results. The paper gives no named hardness theorem; its claim that general scoring rules with unrestricted committee size may be NP-hard is a conjecture in the conclusion, not a proved anchor.
The mirror I would defend is continuous bloc manipulation. The society has a finite support of types, each with a ranking and a rational mass. A distinguished strategic type has mass \(\lambda>0\); its members share the same true ranking and additive utility \(u\), and coordinate on one reported ranking \(L\). The remaining types, with masses \(\mu_t\) summing to \(1-\lambda\), vote truthfully. For a scoring vector \(\boldsymbol{\alpha}\), the score after the report is
\[ S_L(c)=\sum_t \mu_t\,\alpha_{r(c,t)} +\lambda\,\alpha_{r(c,L)}. \]
The committee remains a discrete set of \(\ell\) candidates. The question is whether some ranking \(L\) gives the strategic type utility at least \(q\): \(\sum_{c\in K(L)}u(c)\ge q\) under lexicographic tie-breaking, or expected utility at least \(q\) under the paper’s uniform random tie-breaking. A solution is the ranking \(L\). The instance gives the scoring rule, committee size, tie-breaking rule, rational masses, utility, and threshold. Its size is measured in \(m\), support size \(\tau\), and the bit length \(L\) of the data.
This fits a plausible regime such as a large movie-recommendation platform: millions of users may fall into relatively few ranking-and-utility profiles, with one organized cohort coordinating its ballot to affect a shortlist. The paper itself names movie recommendation as an application and studies the same ingredients—rankings, a fixed-size committee, additive utility, a reported ballot, and score-based selection. The type masses are shares of the population; they are not probabilities over outcomes or fractional committees. A discrete instance embeds by giving each voter mass \(1/n\); a positive \(\lambda\) also represents many identical strategic voters acting as a bloc.
My lead anchor is Theorem 4.1, proved in the paper: for any family of scoring rules \(F\), \(F\)-LexMultManipulation can be solved in time \(O(nm^{\ell+2})\), where \(n\) is the number of voters, \(m\) the number of candidates, and \(\ell\) the committee size. Its continuous question is the lexicographic bloc problem just defined, for any scoring family and fixed \(\ell\). I expect it to be tractable. The proof enumerates candidate committees and uses a greedy ordering to complete the manipulator’s ranking. Scaling that ballot’s score contributions by the rational mass \(\lambda\) preserves the ordering argument; base scores can be computed from the \(\tau\) types, with exact rational comparisons. This is the strongest mirror because it keeps general scoring rules and arbitrary additive utilities while making the population a distribution.
Theorem 4.2, also proved here, gives a distinct anchor for the other tie rule: for any family \(F\), \(F\)-RandMultManipulation is in P when \(\ell\) is bounded by a constant. Its continuous counterpart asks whether a bloc ranking \(L\) can achieve expected utility at least \(q\) when ties at the cutoff are resolved by choosing uniformly among the eligible subsets. I also expect this version to be tractable for fixed \(\ell\). The paper’s algorithm works with score levels and assignments of the scoring vector; multiplying those assigned contributions by \(\lambda\) preserves that structure, and the rational arithmetic has polynomial bit complexity. This is a separate mirror because the randomized outcome and expected-utility objective are part of the paper’s problem, not incidental details.
A third, broader special case is Theorem 3.1, proved here: for every \(k\ge1\), both \(F^k\)-LexMultManipulation and \(F^k\)-RandMultManipulation are decidable in polynomial time. The continuous question is the same bloc-manipulation problem under \(k\)-Approval, with either tie-breaking rule and no bound on \(\ell\). I expect this to be tractable as well: each report gives mass \(\lambda\) to \(k\) candidates, and the paper’s score-level case analysis carries over with score increments of \(\lambda\). After computing the base scores from the support, the running time should be polynomial in \(m,\tau,L\), and the input size of \(k\).
These mirrors cover only the paper’s named polynomial-time results. They do not establish that a continuous population makes discrete hardness disappear: the anchors are already in P. They do generate a useful next question: for general scoring rules and unrestricted \(\ell\), does the paper’s conjectured hardness persist in the mass-based problem, or can rational population masses support a more efficient algorithm? Parameterized complexity in \(\ell\) is another natural question.
The soft spot is the strategic bloc. The paper studies one manipulator, whereas a positive mass of coordinated, identical agents is a high-multiplicity version of that model; a literal single manipulator’s share tends to zero as the electorate grows. That is a real change in regime. I think the mirror remains recognizable because the bloc still chooses one reported ranking to improve the same committee utility under the same scoring and tie-breaking rules, but an author who insists on strictly unilateral manipulation could reject it.
The strongest objection is that the paper’s manipulation problem is intrinsically unilateral. Its input singles out one voter, \(v_n\), and asks whether that voter can improve the committee by changing one ballot. In a society normalized to mass \(1\), one voter among \(n\) contributes only \(1/n\) of the score. As \(n\) grows, that contribution vanishes. For a fixed continuous society with a strict score gap, the voter cannot change the winners; on exact score ties, an infinitesimal report can matter, but only on those knife-edge profiles. That gives a degenerate mirror of unilateral manipulation, concentrated on tie boundaries rather than the general computational problem studied in the paper.
This objection applies to all three anchors. For Theorem 4.1, the continuous question is whether a single voter can change the winning committee under lexicographic tie-breaking; at zero mass, the ranking has no effect except at ties. Theorem 4.2 has the same problem: random tie-breaking may make the result sensitive to an infinitesimal perturbation at a tied cutoff, but that sensitivity does not give the voter influence over a generic continuous profile. Theorem 3.1’s \(k\)-Approval restriction changes which scores the voter can add, not the fact that the voter’s mass disappears. Bounded committee size and \(k\)-Approval do not restore unilateral influence.
The proponent’s better version is a positive-mass bloc with a shared ranking and utility, coordinating on a reported ballot. That is a sensible question, and a large user cohort on a movie platform is a plausible setting. But it changes the strategic actor: the paper explicitly studies one voter, and its introduction distinguishes single-voter from coalitional manipulation. A bloc’s report changes a positive fraction of the score, so the problem is coalition manipulation by a homogeneous type, not a continuous version of the paper’s unilateral problem. Keeping the same committee utility and tie-breaking rules does not remove that change. If the bloc’s mass tends to zero, the original degeneracy returns; if it stays positive, the coalition is doing the work.
This is a strong case against the three *unilateral* mirrors. It does not establish the requested universal negative. The bloc model is a credible high-multiplicity computational question, and the paper’s setting and utility model give its authors a clear reason to recognize it as a close extension. The proponent’s claimed algorithm transfers would need justification, but whether the resulting problem is tractable is not an objection to asking it. I cannot honestly say the negative case rules out every worthwhile mirror; it rests on treating the paper’s single-manipulator scope as binding, and the positive-mass bloc is a plausible way around that boundary.
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.