| paper | d4-conf-ecai-2012-0025 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable for every fixed \(Y\in\{\mathrm{cup},\mathrm{Copeland},\mathrm{maximin},\mathrm{Bucklin}\}\) with \(m=3\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 13
statement extracted from the paper’s text layer
For three candidates \(a,b,c\), choose \(Y\in\{\text{cup},\text{Copeland},\text{maximin},\text{Bucklin}\}\). Given rational nonmanipulator masses \(\nu_{w,r}\) by weight \(w\) and ranking \(r\), and rational manipulator mass \(\kappa_w\) by weight, does there exist an allocation \(x_{w,r}\geq 0\) with \(\sum_r x_{w,r}=\kappa_w\) for every \(w\), such that \(c\) wins under \(\text{plurality}+Y\)? Evaluate weighted tallies using effective mass \(w(\nu_{w,r}+x_{w,r})\); use the paper’s tie-breaking in favor of \(c\), and include the agenda as input when \(Y\) is cup.
A finite-support rational distribution over voter types \((w,r,\sigma)\), where \(w\) is the voter’s weight, \(r\) is a ranking, and \(\sigma\) distinguishes fixed voters from manipulators. The decision variables split each manipulator weight class’s mass among the six rankings; weighted tallies use \(w\) times the resulting mass. The objective is feasibility: make \(c\) win under the paper’s combined rule.
The mirror covers Proposition 13’s weighted three-candidate manipulation results for plurality combined with cup, Copeland, maximin, or Bucklin. It leaves the paper’s other manipulation results, normative properties, and approximation results outside its scope.
My lead is the weighted, three-candidate manipulation result in Proposition 13, proved in this paper. It says that computing a manipulation of plurality \(+\,Y\) is NP-complete with weighted votes and three candidates for each \(Y\in\{\text{cup},\text{Copeland},\text{maximin},\text{Bucklin}\}\). The paper gives a PARTITION reduction in detail for plurality \(+\,\text{cup}\) and says the other proofs are similar. This is a good anchor because the paper also notes that the base rules are individually polynomial to manipulate in this setting: the hardness belongs to their combination.
The mirror I would hand to a prover is Continuous Three-Candidate Plurality–\(Y\) Manipulation. The candidates are \(a,b,c\), the manipulators all want \(c\), and \(Y\) is one of the four rules in Proposition 13. An instance gives rational masses of nonmanipulators by type \((w,r)\), where \(w>0\) is the voter’s weight and \(r\) is one of the six rankings, plus a rational manipulator mass \(\kappa_w\) for each weight class \(w\). Normalize these masses so the population mass sums to one. For cup, include the agenda; for the proposition’s reduction, \(a\) plays \(b\), and the winner then plays \(c\). Use the paper’s tie-breaking convention, which favors the target.
A solution is an allocation \(x_{w,r}\geq 0\) of each weight class’s manipulator mass among the six possible reported rankings, with
\[
\sum_r x_{w,r}=\kappa_w\qquad\text{for every }w.
\]
The question is whether such an allocation makes \(c\) win under the paper’s plurality \(+\,Y\) combinator. The rules evaluate the resulting weighted profile: the effective mass of ranking \(r\) is \(\sum_w w(\nu_{w,r}+x_{w,r})\), where \(\nu_{w,r}\) is the nonmanipulator mass. As in the paper’s manipulation problem, this is a feasibility question, not a cost-minimization problem; the allocation is the certificate.
This is a plausible high-multiplicity regime for a large membership organization or coalition voting over three fixed alternatives. Many members can share one of a few voting-power classes; nonmanipulators fall into at most six ranking types per class, and manipulators share the same target. Weight belongs in the type because it changes how an agent affects every tally. The mirror keeps the paper’s strategic question, weighted influence, voting rules, and recursive run-off; it makes the population mass divisible. That is recognizably the paper’s problem with a continuous population, rather than a change to fractional outcomes or a different election rule.
I expect this mirror to be tractable (Class A). With three candidates, there are only six report rankings per weight class, and the relevant plurality scores, pairwise tallies, and rule scores are linear in the allocation variables. One can enumerate the finitely many possible outcome and tie cases for the base rules and run-off, then check rational linear feasibility. This gives an algorithm polynomial in the number of weight classes and the input bit length. The same approach applies to the four choices of \(Y\) in Proposition 13. It would be a meaningful result even if the continuous answer is easier: the question is whether the combination’s discrete hardness survives when manipulators are a divisible population.
The soft spot is substantial and comes directly from the reduction. Its PARTITION instance uses manipulators with weights \(2k_i\), so the proof’s coalition is built from potentially many distinct, individually significant weights. Those instances are not themselves a convincing low-support high-multiplicity scenario. In the continuous mirror, each weight class’s mass can split across rankings, so the partition constraint that creates the hardness can disappear. That weakens any claim that this mirror explains the paper’s hardness. It does not, I think, defeat the mirror: the authors explicitly study weighted coalition manipulation, and a population with repeated weight classes is a sensible instance regime for that same problem. The mirror preserves weights as type information instead of treating named individuals as types.
The scope here is just Proposition 13’s weighted manipulation results. Further questions include whether this tractability extends when the number of candidates grows, how the running time depends on the support of weight classes, and which restrictions on the manipulators’ assignments would make indivisibility—and perhaps the original hardness—reappear.
Proposition 13 is the paper’s strongest computational anchor, and the best skeptical argument is that its hardness lives in the manipulators’ individual weights. The PARTITION reduction assigns each manipulator a weight \(2k_i\), then relies on each choosing exactly one ballot. In the proposed mirror, a weight class with many agents can divide its mass among ballots. That is a sensible high-multiplicity relaxation when the class really contains many interchangeable people; it does not preserve the reduction’s singleton weight classes, where splitting mass would split an individual’s ballot.
The natural repair is a large electorate with repeated weight classes—for example, a federation whose many delegates have the same voting power. That scenario is coherent, but it requires many independent manipulators to share a weight and a target, and to coordinate arbitrary reports. Some weighted-voting settings instead give weight to a small set of identifiable blocs, whose members do not each cast a ballot with the bloc’s full weight. Ordinary member elections usually give each person one vote. Those distinctions narrow the settings in which this mirror fits the paper’s strategic actors closely.
That is a real limitation on how broadly to pitch the mirror, but it does not defeat it. A large federation with repeated, independently voting delegates is plausible, and a continuous coalition assigning its mass across rankings is a recognizable version of coalition manipulation. The fact that indivisibility in the reduction disappears under continuization is not itself a reason to dismiss the question; that is exactly the sort of change the programme is meant to investigate.
So the strongest honest case against is that this mirror should not be presented as a continuous account of Proposition 13’s PARTITION reduction. Its credible population regimes require repeated weighted agents, while the proof uses potentially distinct weights. I cannot make the stronger claim that no scenario yields a worthwhile mirror: under the programme’s standard, this anchor survives.
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.