| paper | The Computational Impact of Partial Votes on Strategic Voting |
| authors | Nina Narodytska, T. Walsh |
| venue | ECAI 2014 |
| filed under | voting · manipulation |
| judged by | gpt-5.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: feasibility and rational witness construction take \(O((\tau+1)L^2)\) bit operations, hence \(O(L^2)\) for \(m=3\) and \(\tau\leq15\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 4
statement extracted from the paper’s text layer
Given \(C=\{a,b,p\}\), a rational fixed society distribution \(\nu\) over the \(15\) nonempty top-truncated ballots, rational manipulator mass \(\alpha\) with \(\sum_b\nu_b+\alpha=1\), and target \(p\), choose rational masses \(x_b\ge0\) with \(\sum_b x_b=\alpha\) so that \(p\) wins under the paper's modified Borda rule, with ties favoring \(p\); output such an \(x\) if one exists.
A finite mass-allocation LP whose types encode strategic role, target \(p\), and partial reports; fixed ballot masses are \(\nu_b\), decision masses are \(x_b\), and linear modified-Borda score inequalities enforce \(p\)'s victory.
The mirror directly covers the weighted partial-vote hardness mechanisms of Propositions 4 and 8. It leaves the other Borda variants, STV, Copeland's unweighted algorithm, Proposition 10, and the empirical analysis untouched.
My lead is Proposition 4. It gives a particularly clean test of whether the paper’s hardness comes from population indivisibility rather than from the voting rule itself.
A natural high-multiplicity regime is a large coalition of otherwise interchangeable supporters of a target candidate \(p\). They share the same objective, permitted reports, and underlying preference type; only the mass assigned to different submitted partial ballots changes. The nonmanipulators are also represented by a rational distribution over a few partial-ballot types. Thus \(N\) may be arbitrarily large while the number of distinct types is constant: in the reduction behind Proposition 4 there are only the \(a\)-only and \(b\)-only nonmanipulator types, plus one manipulator type.
A type can be taken to include a complete underlying ranking, strategic role, target candidate, and, for fixed voters, their submitted truncation. The action variable does not fractionalize ballots: \(x_b\) is the mass of agents who each cast the integral partial ballot \(b\). This is faithful to the paper’s own observation that a weighted vote of weight \(w\) can be viewed as \(w\) identical agents.
The strongest anchor is Proposition 4, proved in this paper:
Computing a coalition manipulation of the modified Borda count with weighted and partial votes and \(3\) candidates is NP-hard.
The reduction is from Number Partitioning. Given integers \(k_i\) summing to \(2K\), the question is whether they can be divided into two groups of sum \(K\). There are candidates \(a,b,p\), with \(p\) preferred by the coalition. The fixed profile has partial votes of total weight \(3K\) for \(a\) and \(3K\) for \(b\), giving both score \(3K\). A perfect partition lets weight \(K\) vote \(p>a>b\) and weight \(K\) vote \(p>b>a\); then all three candidates score \(4K\), so \(p\) wins by tie-breaking. Conversely, if \(p\) wins, one may assume all manipulators rank \(p\) first. If \(x\) is the weight voting \(p>a>b\), \(y\) the weight voting \(p>b>a\), and \(z\) the weight voting only \(p\), then \(x+y+z=2K\). The inequalities that \(p\) defeat both \(a\) and \(b\) force \(x\ge K\) and \(y\ge K\), hence \(x=y=K\) and \(z=0\). The successful manipulation therefore encodes a perfect partition.
I would mirror it as Continuous Modified-Borda Partial-Ballot Coalition Manipulation, with the following precise instance. Let \(C=\{a,b,p\}\), let \(\mathcal B(C)\) be the fifteen nonempty top-truncated ballots, let \(\nu_b\in\mathbb Q_{\ge0}\) be the mass of nonmanipulators casting ballot \(b\), and let \(\alpha\in\mathbb Q_{\ge0}\) be the manipulator mass, with total mass normalized to \(1\). The target is \(p\). Choose variables
\[ x_b\ge0\qquad(b\in\mathcal B(C)),\qquad \sum_{b\in\mathcal B(C)}x_b=\alpha . \]
The resulting society has ballot mass \(\nu_b+x_b\). The objective is to minimize the target deficit
\[ D(x)=\max_{q\in C\setminus\{p\}} \bigl(\operatorname{score}_{\nu+x}(q)-\operatorname{score}_{\nu+x}(p)\bigr), \]
where the modified Borda rule is exactly the paper’s rule: a length-\(k\) partial ballot gives its ranked candidates scores \(k,k-1,\ldots,1\), and unranked candidates score \(0\), while complete ballots receive the ordinary Borda scores. The decision question is whether \(D(x)\le0\), with ties favoring \(p\); a solution is the mass vector \(x\).
This is a direct population continuization of the paper’s manipulation problem. Every score is linear in \(x\), and with three candidates there are only fifteen ballot variables, so the problem is a rational linear program and is therefore in Class A. The Number Partitioning hardness disappears for exactly the reason the programme is designed to expose: the coalition mass can be divided continuously. In the reduction, one may assign mass \(K\) to \(p>a>b\) and mass \(K\) to \(p>b>a\), whether or not the original list of indivisible weights has a perfect partition. Clearing denominators converts any rational solution back into a finite election of sufficiently many identical agents, preserving all scores and ties.
A second strong anchor is Proposition 8, also proved in this paper:
Computing a coalition manipulation of Copeland’s method with weighted and partial votes and \(4\) candidates is NP-hard.
Here the reduction again comes from Number Partitioning. There are candidates \(a,b,c,p\), \(K\) fixed votes \(a>b>c>p\), and \(K\) fixed votes \(a>c>b>p\). The manipulating weights are the integers \(k_i\), summing to \(2K\). If a perfect partition exists, one part votes \(p>b>c>a\) and the other \(p>c>b>a\); all four candidates then have Copeland score \(0\), so \(p\) wins by tie-breaking. Conversely, if \(p\) wins, the manipulators may be assumed to rank \(p\) first. They must all rank both \(b\) and \(c\) above \(a\), otherwise \(a\) retains a positive Copeland score. Since \(b\) and \(c\) are initially tied, exactly weight \(K\) must rank \(b\) above \(c\) and weight \(K\) must rank \(c\) above \(b\), which again yields a perfect partition.
The corresponding mirror is Continuous Copeland Partial-Ballot Coalition Manipulation. Its instance consists of four candidates, a rational nonmanipulator distribution \(\nu\) over the \(64\) top-truncated ballots, rational manipulator mass \(\alpha\), and target \(p\). The solution is a vector \(x_b\ge0\) summing to \(\alpha\). The objective is
\[ D_{\mathrm{Cop}}(x) = \max_{q\ne p} \bigl(\operatorname{Cop}_{\nu+x}(q) -\operatorname{Cop}_{\nu+x}(p)\bigr), \]
where unranked candidates are tied in last place exactly as in the paper. The question is whether \(D_{\mathrm{Cop}}(x)\le0\).
For four candidates this is also expected to be Class A. Each pairwise majority relation is determined by a linear inequality in \(x\). There are only \(\binom{4}{2}=6\) pairs, so one can enumerate the finitely many strict, tied, or reversed pairwise patterns and solve a linear program for each pattern. The source reduction again collapses: weight \(K\) can be assigned continuously to each of the two required manipulator ballots without solving a partition instance.
The scope claim is deliberately limited: these mirrors cover Propositions 4 and 8, not the paper’s entire treatment of Borda, STV, Copeland, or its experiments. Their common expected outcome is informative: the paper’s weighted hardness is population-multiplicity hardness, while the voting-rule semantics remain intact. The variable-candidate versions would generate further questions about pricing over exponentially many partial ballots and about whether Copeland’s pairwise-pattern explosion creates a continuum-specific hard case.
The weakest point is that the continuous model lets an atomless coalition split across reports, whereas an individual weighted voter in the source instance must cast one ballot. That is a real modelling change. I think it remains defensible because the paper explicitly interprets weight \(w\) as \(w\) identical voters, and the proposed regime is precisely the one in which those clones form a large interchangeable population. The mirror therefore does not claim that the original finite weighted problem is easy; it asks the programme’s central question: whether its hardness survives when the population, rather than the outcome, is represented continuously.
The negative case is weak, because Proposition 4 survives the strongest objections.
The best objection is semantic. In the paper’s weighted problem, each \(k_i\) is an indivisible weighted voter: that bloc must submit one ballot. The proposed continuum permits its mass to split between \(p>a>b\) and \(p>b>a\). If the weighted bloc is treated as an atom, the partition hardness remains and there is no genuine continuum. Thus the proposed problem is not literally the paper’s weighted manipulation problem; it is a nonatomic-coalition variant.
That objection is nevertheless undermined by the paper itself, which explicitly interprets a weight \(w\) as \(w\) identical voters. Once those clones are treated as a high-multiplicity population, allowing different clones to cast different reports is natural. The continuous allocation \(x_b\) is then exactly a mass-level description of individual strategic ballots. Clearing denominators also gives a finite unweighted coalition with the same outcome. So this is a legitimate high-multiplicity relaxation, even though it is not the same as preserving each weighted bloc as an indivisible actor.
One can argue that the resulting Proposition 4 mirror is too thin to justify a research programme: with three candidates there are only \(15\) partial ballots, so the continuum problem is merely a constant-size rational LP. The population has disappeared as a computational dimension; only rational precision remains. But that is a criticism of its depth, not of its validity. A constant-size LP exposing the disappearance of Number Partitioning is still a meaningful Class A result under the programme’s stated standards.
Proposition 8 has the same limitation more sharply. With four candidates there are \(64\) partial ballots and only six pairwise contests. Enumerating the finitely many majority-sign patterns and solving the corresponding linear feasibility problems gives a constant-size continuous formulation. Again, the original weighted partition gadget vanishes because mass can be divided. Preserving the weighted blocs would preserve the hardness, but would also preserve the atoms and therefore abandon the intended high-multiplicity relaxation.
The proponent’s proposed extensions to variable \(m\) are less immediate: they become new, broader continuous manipulation problems rather than direct continuizations of the fixed-\(m\) propositions. That is the strongest basis for saying the anchors overstate the paper’s general relevance. It does not, however, defeat the mirrors themselves. The paper contains two named computational results whose hardness is plausibly driven precisely by indivisible population weights, and both admit sensible mass-level versions.
So the strongest honest negative conclusion is that these are narrow and technically elementary mirrors, not yet a broad theory of partial-vote manipulation. I cannot honestly establish that no worthwhile continuous mirror exists: Proposition 4 alone supplies a credible counterexample to that claim.
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.