| paper | Complexity of and Algorithms for Borda Manipulation |
| authors | Jessica Davies, G. Katsirelos, Nina Narodytska, T. Walsh |
| venue | AAAI 2011 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: The continuous decision problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). The minimum coalition mass is also exactly computable in polynomial time. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), a designated candidate \(d\), and a rational baseline distribution \(\nu\) over complete ranking types \(T\), decide whether a controllable coalition of mass \(\rho\) can choose \(x_t\ge 0\), with \(\sum_{t\in T}x_t=\rho\), so that \(d\) wins under Borda in the normalized society \((\nu+x)/(1+\rho)\); the optimization version minimizes \(\rho\).
The types are complete rankings \(t\in T\), \(\nu_t\) is baseline mass, and \(x_t\) is controllable mass assigned to ranking \(t\). Minimize \(\rho=\sum_t x_t\) subject to the linear Borda inequalities \(\mathrm{sc}_{\nu+x}(d)\ge \mathrm{sc}_{\nu+x}(c)\) for every \(c\ne d\); equivalently, use position-mass variables whose doubly stochastic solution decomposes into genuine rankings.
The continuum replaces the exact existential question over two permutations by an arbitrary distribution over rankings, removing the integrality and multiplicity restrictions responsible for Theorem 1's NP-hardness.
fatal: False
The mirror covers the paper's coalition-manipulation problem and its transition from feasibility to minimizing coalition mass. It does not preserve the exact two-manipulator hardness, the integral-row approximation algorithms, or the empirical comparisons among REVERSE, LARGEST FIT, and AVERAGE FIT.
The strongest positive case is a high-multiplicity version of the paper’s central coalition-manipulation problem. I would use only one anchor.
The lead anchor is Theorem 1, proved in this paper: “Unweighted coalition manipulation for the Borda rule is NP-complete with two manipulators.” The instance has a Borda election, a preferred candidate \(d\), complete information about the non-manipulators’ scores, and two unweighted manipulators who may submit arbitrary complete rankings. The question is whether they can make \(d\) win, with ties broken in their favour. Membership in NP follows from guessing the two ballots. NP-hardness is proved from Permutation Sum: given \(X_1,\ldots,X_n\) with \(\sum_i X_i=n(n+1)\), one asks whether there are permutations \(\sigma,\pi\) satisfying \(\sigma(i)+\pi(i)=X_i\). The reduction constructs an election with \(n+3\) candidates in which a successful manipulation exists exactly when such two permutations exist.
My mirror is Continuum Unweighted Coalition Manipulation for Borda. A baseline society is given by a rational distribution \(\nu\) over complete rankings \(T\), where \(T\) contains the \(m!\) ranking types. The baseline mass is normalized to \(1\). A large homogeneous pool of supporters, all with the same strategic objective of making \(d\) win, contributes available mass \(\rho\). The action is a distribution \(x=(x_t)_{t\in T}\), where \(x_t\ge 0\) is the mass submitting ranking \(t\) and \(\sum_t x_t=\rho\). The resulting society is \((\nu+x)/(1+\rho)\). The question is whether there is such an \(x\) for which \(d\) is a Borda winner; the optimization version minimizes \(\rho\).
This is a plausible high-multiplicity regime for the paper’s underlying problem: a very large organizational or platform election has many voters but relatively few repeated preference archetypes, while a campaign controls a macroscopic pool of interchangeable supporters. Each individual still casts an ordinary integral ranking; only the aggregate allocation of voters among rankings is continuous. Thus this is not replacing Borda by a fractional voting rule.
The continuous problem is naturally tractable. Let \(b_c\) be the baseline Borda score of candidate \(c\). It is without loss of generality that every manipulator ranks \(d\) first. For each \(c\ne d\) and each position \(p\in\{1,\ldots,m-1\}\), let \(y_{c,p}\) be the mass placing \(c\) in position \(p\) below \(d\). We require \(\sum_p y_{c,p}=\rho\) for each \(c\), and \(\sum_{c\ne d}y_{c,p}=\rho\) for each \(p\). The winning constraints are \(b_d+\rho(m-1)\ge b_c+\sum_p(m-1-p)y_{c,p}\). This is a polynomial-size linear program. The matrix \(y/\rho\) is doubly stochastic, so Birkhoff–von Neumann decomposition converts it into a distribution over genuine rankings. Hence the LP is not merely an invalid fractional relaxation: its solution is implementable by a continuum of ordinary voters.
The paper’s own Theorem 2 supports this interpretation. It says that any relaxed manipulation matrix, containing the right aggregate multiplicities of Borda scores and respecting the column gaps, can be converted in polynomial time into a genuine manipulation matrix with the same column sums. The continuum version makes this aggregate-to-ballot conversion exact through a doubly stochastic decomposition.
I therefore expect this mirror to fall in Class A, not because Borda manipulation has ceased to be the authors’ problem, but because the specific hardness in Theorem 1 comes from requiring two integral permutation rows. In the reduction, the two ballots encode \(\sigma\) and \(\pi\). With continuum mass, those rows may be mixed fractionally and then decomposed into a distribution of ballots, so the Permutation Sum obstruction disappears. The result is a useful positive boundary: the discrete NP-hardness does not survive this high-multiplicity relaxation.
The mirror covers Theorem 1 and the underlying coalition-manipulation question, but not the empirical claims or the approximation comparisons among REVERSE, LARGEST FIT, and AVERAGE FIT. Those results depend essentially on integral rows and are not needed for the case.
The weakest point is that this is not a literal continuization of “exactly two individual manipulators.” Two people are not a high-multiplicity population. The mirror instead continuizes the paper’s broader coalition-manipulation problem, which the authors themselves generalize to many manipulators when minimizing coalition size. If a referee insists that the number two must remain integral, the case is weak; if the relevant object is the authors’ underlying unweighted coalition-manipulation problem, this is a faithful and computationally meaningful continuous analogue. Further questions include how well an LP solution can be rounded for a finite coalition, and whether sparsity constraints, heterogeneous manipulation costs, or individually constrained supporters restore hardness.
The strongest negative case is that Theorem 1 has no nontrivial population limit. Its computational object is not a large electorate but exactly two integral strategic ballots. The reduction encodes a pair of permutations \(\sigma,\pi\), and the hardness lies in requiring those two rows to be genuine permutations. Repeating the non-manipulators does not change this: it merely scales an already sufficient score vector, while the two manipulators remain finitely many agents.
The proposed continuum therefore changes the problem at its crucial point. The paper asks whether
\[ \exists\,\sigma,\pi\in S_m \]
satisfying the score constraints. The proposed mirror asks whether there is an arbitrary distribution \(q\) over rankings, or equivalently a point in a Birkhoff polytope, satisfying them. With two manipulators, the position matrix is an average of two permutation matrices, with the associated integrality and multiplicity restrictions. With continuum mass, it may be any doubly stochastic matrix. Birkhoff decomposition proves that this is a valid continuum model, but it also confirms that the model has convexified away precisely the object whose complexity Theorem 1 establishes.
One can try to repair this by keeping exactly two manipulators while making the background electorate continuous. That produces a hybrid problem with a continuous score vector and two finite ballot choices. It is computationally legitimate, but the population continuum is then only a representation of data that Borda already compresses to candidate scores. The strategic problem remains the original two-permutation problem. The continuum contributes no population-level decision variable and no genuine high-multiplicity phenomenon.
Alternatively, one can scale the coalition with the electorate and retain integral ballots, asking for the minimum integer number of manipulators. That is a sensible new problem, but it is not the paper’s named two-manipulator result. It replaces the paper’s existential question over two ballots by a macroscopic campaign-allocation problem, with a different objective and different quantifiers. Requiring two large blocs to cast one common ballot preserves two permutation choices, but then the model is about collective blocs or institutional voters, not a continuum of interchangeable individual agents. Allowing members of those blocs to mix ballots returns to the proponent’s LP.
Thus the proposed construction is best understood as a valuable convexified coalition-manipulation problem inspired by the paper, not as a continuization of its central theorem. The paper’s approximation results reinforce this objection: REVERSE, LARGEST FIT, and AVERAGE FIT are explicitly about integral rows, integer coalition size, and the combinatorics of constructing individual ballots. Their central content disappears when arbitrary mass can be split among rankings.
This is not an objection that the continuum answer becomes easy; that could itself be an important Class A result. The objection is that the only natural continuous population in the paper is the non-manipulator electorate, and that part is already summarized exactly by a score vector. The proposed nontrivial continuum arises only by changing the strategic coalition from two individuals into a divisible mass.
That negative case is substantial but not decisive. The paper does discuss coalitions of arbitrary size and minimizing the number of manipulators, so a large campaign of interchangeable supporters is a plausible high-multiplicity reinterpretation. Under the programme’s broad rule that the scenario may differ from the paper’s story, the proponent’s mirror probably survives: it is a meaningful continuous-population version of the underlying coalition-manipulation problem. What fails is the claim that it is a faithful mirror of Theorem 1 specifically, not the stronger claim that no worthwhile mirror can be built at all.
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.