| paper | d4-conf-atal-2011-0224 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-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: Borda and \(\mathrm{Copeland}_{\alpha}\) for every fixed rational \(\alpha\in[0,1]\) are \(\mathrm{NP}\)-complete, even with dyadic rational masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.2
statement extracted from the paper’s text layer
Given candidates \(C\), the paper’s tie-breaker \(T\), a rule \(F\in\{\mathrm{Borda},\mathrm{Copeland}_{\alpha}\}\), a rational-mass society \(\mu\) containing a designated strategic atom \(b\delta_{R^{\star}}\) with \(b>0\), and the bloc’s strict preference order \(\succ\), decide whether some ballot \(L\in\mathcal{L}(C)\) makes \(T(W_F(\mu-b\delta_{R^{\star}}+b\delta_L))\succ T(W_F(\mu))\), where \(W_F\) is the set of maximum-score candidates.
The society is a finite-support distribution over rankings with binary-rational masses. A designated mass \(b\) acts as a coordinated bloc and chooses one ranking \(L\); Borda uses mass-weighted scores, while Copeland uses pairwise population shares and the usual majority threshold \(1/2\). The decision question is whether that ballot changes the selected winner to one the bloc strictly prefers.
A shared type does not itself make agents submit one report, so the common ballot needs a coordinating delegate or coalition; this makes the mirror a weighted-coalition problem rather than the paper’s unilateral deviation problem.
fatal: False
The mirror covers the hardness results in Theorem 5.2 for Borda and Theorem 5.5 for Copeland with the paper’s simple tie-breaker; it leaves the randomized tie-breaking algorithms and the other hardness results unaddressed.
My lead is a high-multiplicity version of the paper’s manipulation problem: a large bloc of voters who share a preference order and objective coordinates on one ballot. The society is still a distribution over voter types; the co-modification is that this bloc acts together so its mass can affect the outcome.
For both mirrors, take candidates \(C\), a fixed scoring correspondence \(F\), and the paper’s simple polynomial-time tie-breaker \(T\). An instance gives background ranking types \(R_1,\ldots,R_k\) with rational masses \(a_1,\ldots,a_k\), plus a strategic type of mass \(b>0\), truthful ranking \(R^\star\), and shared strict preference order \(\succ\), where \(\sum_i a_i+b=1\). A solution is a ranking \(L\) for the whole strategic bloc. It changes the society from \(\nu_{R^\star}=\sum_i a_i\delta_{R_i}+b\delta_{R^\star}\) to \(\nu_L=\sum_i a_i\delta_{R_i}+b\delta_L\). The question is whether some \(L\) makes \(T(W_F(\nu_L))\succ T(W_F(\nu_{R^\star}))\), where \(W_F\) is the set of maximum-score candidates.
For Borda continuous bloc manipulation with \(T\), scores are \(\mathrm{sc}_{\nu}(c)=\sum_r \nu_r(m-\mathrm{pos}_r(c))\). My lead anchor is Theorem 5.2, proved in this paper: \(T\circ\mathrm{Borda}\)-MANIPULATION is NP-hard. Here \(T\) is the paper’s simple tie-breaker, which decodes certain tied-candidate sets as a 3-SAT instance and selects a candidate according to whether the encoded assignment satisfies it. The theorem says that finding a beneficial vote for one manipulator is NP-hard under Borda and this tie-breaker. In the mass version, the question is whether the coordinated bloc can choose a ballot that gives its members a strictly preferred winner.
A second, independently useful anchor is Theorem 5.5, also proved here: for every \(\alpha\in[0,1]\), \(T\circ\mathrm{Copeland}_{\alpha}\)-MANIPULATION is NP-hard. Its continuous mirror uses pairwise support \(p_\nu(c,d)=\sum_{r:c\succ_r d}\nu_r\); a candidate gets \(1\), \(\alpha\), or \(0\) points against \(d\) as \(p_\nu(c,d)\) is greater than, equal to, or less than \(1/2\). The same question asks whether the bloc can change the selected winner to one it strictly prefers. This anchor matters on its own terms: the aggregate quantities are pairwise population shares, rather than additive Borda scores.
The hardness carries over directly. Given either paper instance with \(n\) background voters and one manipulator, assign each background ranking its frequency divided by \(n+1\), and give the strategic type mass \(1/(n+1)\). Every Borda score is scaled by \(1/(n+1)\); every pairwise-majority comparison is preserved. Thus each report produces exactly the same winner set, and \(T\) sees exactly the same input. The original 3-SAT reduction therefore gives NP-hardness for both mass problems. Their specified versions are also in NP: a ranking is a polynomial-size certificate, and the scores and fixed \(T\) can be evaluated in polynomial time. They are NP-complete. They belong in Class B: the discrete problem embeds in the continuous one, and the reduction’s combinatorics live in the candidate agenda, not in the number of voters.
This is a genuine high-multiplicity regime. Replicate every voter in the reduction \(q\) times, with each type’s members sharing the same relevant preferences and role. The proportions stay fixed, while the population grows and the number of distinct types stays bounded by the original profile’s support. A plausible setting is a large organization whose members share a ballot type and coordinate through a common delegate or campaign. The type includes the shared preferences, objective, and strategic role, so the grouping follows the programme’s high-multiplicity definition.
The weakest point is that the paper studies a single manipulator, whereas this mirror gives a cohort one common report. It is a recognizable coordinated-bloc extension, but not an identity with unilateral manipulation; allowing the bloc to split its mass across ballots would be a different problem and would need its own hardness argument. Also, the tie-breaker in the lower-bound construction is deliberately engineered, so these anchors do not establish hardness for ordinary lexicographic or randomized tie-breaking. I think the mirror remains worth asking: it preserves the paper’s underlying computational question—whether strategic voting can improve the selected winner—while making the society an explicit distribution and showing precisely where the hardness survives.
The strongest objection is that a faithful continuum limit erases the actor whose manipulation the paper studies. In an atomless society, one voter has mass zero. Changing that voter’s report leaves Borda scores and Copeland pairwise shares unchanged, so it cannot change the winner. In finite populations the voter changes shares by \(1/N\); if a margin also shrinks at that scale, the limiting distribution \(\mu\) loses the information that decided the election. The unilateral manipulation question therefore degenerates in the limit.
The proposed mirrors avoid that by giving a coordinated bloc positive mass \(b\) and requiring it to cast one common ballot. That is a coherent model of weighted or coalitional manipulation, but it changes the strategic actor and its feasible deviations. A positive-mass group of identical voters need not coordinate: if its members can report separately, the action is a distribution over ballots; if they cannot, the common delegate is an added institutional assumption. The type definition justifies grouping indistinguishable voters; it does not by itself justify making them act as one voter.
This applies to both anchors. In Theorem 5.2, the continuous Borda bloc changes each score by \(b\) times the ballot’s contribution. In Theorem 5.5, it shifts pairwise shares by up to \(b\), potentially crossing \(1/2\). Those are meaningful weighted-manipulation questions, but they do not preserve the paper’s single-voter deviation. The reduction’s scaling argument establishes an exact embedding of the finite instance; replicating the manipulator establishes an embedding only after those copies are required to share one report. Neither resolves the change in agency.
A more flexible mirror could ask for the minimum mass of a coordinated coalition needed to improve the selected winner. That may be worth studying on its own, but it is a coalition-control question rather than a continuization of these unilateral-manipulation results. The engineered tie-breaker makes the proposed instances especially dependent on arranging a particular tied set, though that alone does not invalidate them.
This is a serious objection, not a decisive one. A common delegate for a large, like-minded bloc is plausible, and the programme allows model co-modifications when they preserve a recognizable question. My negative case rests on whether that change in strategic unit remains the authors’ problem; it cannot establish that no worthwhile cohort-level mirror exists.
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.