| paper | New Approximations for Coalitional Manipulation in Scoring Rules |
| authors | Orgad Keller, Avinatan Hassidim, Noam Hazon |
| venue | JAIR 2019 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Deterministic polynomial-time solvable exactly; the requested additive guarantee holds with zero failure probability. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given \(m+1\) candidates, scoring vector \(\alpha\), target \(p\), rational nonmanipulator distribution \(\nu\) of mass \(1-\rho\) over complete rankings, and rational manipulator mass \(\rho\) of one repeated true type with admissible \(p\)-first reports, choose a distribution \(q\) over those reports so that \(\mu^q=\nu+\rho q\) minimizes \(T_\infty(q)=\max_{c\ne p}\operatorname{sc}_{\mu^q}(c)\), equivalently the score margin, or decide whether \(p\) is a co-winner.
Types are complete rankings; mass \(\rho\) is transferred from one \(p\)-top type to report types with variables \(q_r\ge0\) and \(\sum_rq_r=1\). With \(a_c=\operatorname{sc}_\nu(c)\), minimize \(T\) subject to \(T\ge a_c+\rho\sum_rq_rs_\alpha(r,c)\) for every \(c\ne p\); the exponential columns have a sorting-based pricing oracle.
The mirror covers Theorem 8 and Corollary 9 directly, plus a repeated-weight high-multiplicity analogue of Theorems 15 and 17; it leaves heuristic comparisons, implementation details, experiments, and arbitrary distinct-weight instances aside.
The strongest honest positive case is a Class A mirror of coalitional manipulation, led by the paper’s unweighted result.
The paper contains no numbered NP-hardness theorem of its own. Its statements that Borda-UCM is NP-hard are literature summaries citing Davies et al. and Betzler et al. I therefore use the numbered algorithmic results proved in this paper as anchors, rather than misrepresenting those citations as the authors’ theorems.
My lead anchor is Theorem 8, proved here. It states that for every scoring rule \(R_\alpha\), the unweighted coalitional-manipulation problem has a randomized Monte Carlo algorithm that returns a strategy whose maximum competitor score is at most \(T^{\mathrm{OPT}}+k g(\alpha)\), with exponentially small failure probability, where \(T^{\mathrm{OPT}}\) is the minimum possible maximum score of a nonpreferred candidate and \(g(\alpha)\) is the maximum score drop over a distance \(\beta=d\sqrt{m\ln m}\) in the scoring vector. The paper’s Borda specialization is Corollary 9, giving additive \(O(k\sqrt{m}\log m)\).
The corresponding continuous problem is Continuous Score-Margin Manipulation. Its instance consists of candidates \(C=\{p,c_1,\ldots,c_m\}\), a scoring vector \(\alpha\), a target \(p\), a rational nonmanipulator distribution \(\nu\) over complete rankings, and a rational manipulator mass \(\rho\). The nonmanipulator mass is \(1-\rho\); the manipulator mass \(\rho\) initially consists of one complete type whose agents all prefer \(p\). A feasible action assigns that mass to \(p\)-first rankings: if \(q_r\) is the fraction assigned to ranking \(r\), then \(q_r\ge 0\), \(\sum_r q_r=1\), and the transfer is \(x_{t_p,r}=\rho q_r\). Every infinitesimal agent still receives an integral ranking; only the mass of identical agents is divisible.
The resulting society is \(\mu^q=\nu+\rho q\). The problem asks for a distribution \(q\) minimizing
\[ T_\infty(q)=\max_{c\neq p}\mathrm{sc}_{\mu^q}(c), \]
or equivalently the score margin
\[ \Delta_\infty(q)=T_\infty(q)-\mathrm{sc}_{\mu^q}(p). \]
It may also be posed as the decision question whether some \(q\) makes \(p\) a co-winner. The input may be given directly as \(\nu\), or by the paper’s compiled score vector \(a_c=\sum_t\nu_t s_\alpha(t,c)\), since the nonmanipulator rankings matter only through those scores.
This is recognisably the paper’s problem: the candidates, scoring rule, preferred candidate, p-first manipulator ballots, and score-margin objective are unchanged. The only change is that a large population of identical manipulators can be divided among several integral ballots. The continuous optimization is
\[ \begin{array}{ll} \min & T\\ \text{s.t.} & T\ge a_c+\rho\sum_r q_r s_\alpha(r,c) \quad(c\neq p),\\ &\sum_r q_r=1,\qquad q_r\ge 0, \end{array} \]
over the exponentially many \(p\)-first rankings \(r\). Its pricing problem is polynomial: given dual coefficients on the competitors, choose the ranking assigning \(\alpha_1,\ldots,\alpha_m\) to candidates so as to maximize a weighted sum, which is solved by sorting. Thus the continuous problem should be exactly solvable by column generation or the ellipsoid/separation machinery. It is a natural Class A result, not merely a fractional scoring exercise.
The high-multiplicity regime is plausible in a proxy or delegate election, party-controlled membership vote, or large platform-governance election. Suppose millions of voters fall into perhaps \(50\)–\(500\) recurring preference and access types, with a coordinated bloc forming a positive fraction \(\rho\) of the electorate. Agents sharing a type have the same ranking, voting access, and strategic permissions. In the weighted version, they also share the same voting weight. This is precisely the high-multiplicity regime: \(N\gg\tau\), and the individual names carry no information relevant to the problem.
The finite bridge is exact at the representation level. A finite election with \(n_t\) nonmanipulators and \(k\) manipulators becomes a rational mass instance with \(\nu_t=n_t/(n+k)\) and \(\rho=k/(n+k)\). Conversely, rational masses can be cleared of denominators to produce a finite repeated-type election. The new question is whether the limit object, where a coalition’s mass can be distributed among rankings, is tractable and how its optimum relates to the finite optimum. The paper’s configuration LP and randomized rounding are strong evidence that this is the right fault line: their fractional variables already describe mixtures of score configurations, but the paper uses them as an intermediate relaxation rather than as an actual continuum population.
A second, weaker anchor is Theorem 17, also proved here. It states that for weighted coalitional manipulation with arbitrary weights, and for every constant \(\epsilon>0\), a randomized Monte Carlo algorithm finds a strategy with
\[ T\le (1+\epsilon)T^{\mathrm{OPT}}+Wg(\alpha), \]
with exponentially small failure probability, where \(W\) is the total manipulator weight. Theorem 15 gives the sharper additive guarantee \(T\le T^{\mathrm{OPT}}+Wg(\alpha)\) when integer weights are polynomially bounded.
Its continuous counterpart is Continuous Weighted Score-Margin Manipulation. In addition to \(\nu\), \(p\), and \(\alpha\), the instance has finitely many manipulator types \(h\), each with mass \(\rho_h\) and voting weight \(w_h\), with \(\sum_h\rho_h=\rho\). A solution supplies a distribution \(q^h\) over \(p\)-first rankings for every weight type. The final score is
\[ S_q(c)=a_c+\sum_h \rho_h w_h \sum_r q^h_r s_\alpha(r,c), \]
and the objective is to minimize \(\max_{c\neq p}S_q(c)\), or to decide whether \(p\) can win. This remains a population continuization rather than an outcome relaxation: each mass element receives one ordinary ranking, while weight, like preference, is part of the type.
This weighted problem should also be Class A under the stated regime. The action variables form a linear program, and the pricing problem for each weight type is the same assignment-by-sorting problem. Further questions include whether type-dependent reporting costs preserve polynomial pricing, whether a compact-support optimum can always be chosen, and what finite-population convergence rate follows from the continuous optimum.
The weakest point is that the mirror deliberately removes ballot integrality. The paper reports that Borda-UCM is NP-hard even with very few voters and manipulators, so some of its discrete hardness may survive independently of population size. A referee could therefore say that the continuous problem is easier because it is a relaxation, not because the electorate is large. That objection is real. The answer is that this is exactly what continuization is intended to test: whether hardness comes from population multiplicity and indivisible individual actions, or from the candidate-ranking geometry itself. The proposed mirror preserves the paper’s underlying manipulation question and makes only the high-multiplicity move. It covers the coalitional-manipulation and score-margin results, not the paper’s heuristic comparisons or implementation details.
The strongest negative case is that the proposed mirror attaches continuity to the manipulators’ action set, not to the society. In the paper, the nonmanipulators are compiled away into a score vector \(\sigma\), while the \(k\) manipulators are an external finite coalition. Replacing their \(k\) ballot rows by a distribution \(q\) over ballots is therefore a convexification of a strategic action, not obviously a continuous population of voter types. It also changes the quantifier from “there exists a deterministic assignment of ballots” to “there exists a divisible allocation of coalition mass.” The paper’s configuration LP already contains essentially this fractional object as an auxiliary relaxation and then treats rounding back to actual voters as the substantive issue.
This is the best objection to Theorem 8 and Corollary 9. Their guarantees concern a finite coalition, with additive error \(k g(\alpha)\), and the paper’s Borda hardness occurs even with very small electorates. To obtain \(q\), one must instead let the coalition size grow, normalize scores, and study a limiting problem. That is a legitimate new problem, but it is not the theorem’s computational setting merely with \(n\) replaced by a continuum.
The objection does not survive the strongest repair, however. One can model a large party-controlled bloc whose members share the same true type—ranking \(p\) first—and whose allowed reports are \(p\)-first rankings. The action is then a mass transfer from one true type to several reported types, exactly in the sense of the programme. A rational \(q\) can be realized by clearing denominators and creating finitely many repeated agents; conversely, every finite repeated-type coalition yields such a distribution. The resulting LP has a genuine population interpretation, and its pricing problem is polynomial by sorting candidates according to the dual coefficients. Thus Theorem 8 does have a clean high-multiplicity mirror. Calling it “only an LP relaxation” is not enough: the paper never formulates that relaxation as a society, and the finite-to-continuous correspondence is itself a worthwhile result.
The weighted anchors are more vulnerable. Theorem 15 and Theorem 17 rely on the identity of each manipulator through its weight \(w_\ell\). If all weights are distinct, there is no repeated type and hence no meaningful high-multiplicity limit. If one groups manipulators by repeated weights, the proposed \(q^h\)-model is sensible, but it mirrors only a restricted regime rather than the arbitrary weight-vector problem proved in the paper. Retaining individual identities destroys the mass interpretation; discarding them changes the weighted problem. This is a real limitation of the weighted mirror, though not of the unweighted one.
Accordingly, I cannot honestly sustain the requested universal negative verdict. The semantic objection defeats the proponent’s informal presentation and shows that the mirror must be formulated with true types and allowed reports, rather than as a bare mixed strategy. After that repair, however, the unweighted anchor survives: it is a natural continuous-population version with a precise high-multiplicity bridge and a nontrivial separation formulation. The weighted anchors may deserve a narrower verdict, but they cannot rescue the claim that no worthwhile continuous 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.