| paper | Where Are the Really Hard Manipulation Problems? The Phase Transition in Manipulating the Veto Rule |
| authors | T. Walsh |
| venue | IJCAI 2009 |
| 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: Polynomial-time solvable: \(\mathrm P\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given three candidates \(A,B,C\), target \(C\), a fixed electorate distribution \(\nu\) of mass \(1-\lambda\), and a manipulating electorate distribution \(\mu\) of mass \(\lambda\) over finitely many voter types with per-agent veto weights, does there exist a mass assignment \(x_{t,j}\ge 0\) satisfying \(x_{t,A}+x_{t,B}+x_{t,C}=\lambda\mu_t\) for every manipulating type \(t\), such that \(C\)'s final veto weight is no greater than those of \(A\) and \(B\)?
A finite high-multiplicity type model: each type has mass and a fixed veto weight; decision variables \(x_{t,j}\) split each type's mass among veto reports; feasibility asks whether the target wins, or optimization can minimize manipulating mass. Aggregate veto weights are linear in the masses, yielding a linear program.
The mirror does not capture the paper's critical-coalition phenomenon: when \(m=\Theta(\sqrt n)\), normalized coalition mass \(m/n\) vanishes, and the continuum eliminates the partition geometry and CKK search behavior.
fatal: False
It covers the three-candidate weighted constructive manipulation formulation behind Theorem 1. It leaves the empirical phase transition, random-weight distributions, correlated hung elections, asymptotic rarity heuristic, and CKK running-time observations outside the mirror.
My lead, and sole anchor, is Theorem 1. The paper contains no numbered theorem asserting NP-hardness or membership in P; its NP-hardness statement is cited from Conitzer, Sandholm, and Lang (2007). Theorem 1 is nevertheless an eligible formulation anchor because the paper uses it to compute manipulations with the CKK partitioning algorithm.
Theorem 1, proved in this paper, states that a three-candidate weighted coalition can successfully manipulate the veto rule if and only if the multiset \(W\cup\{|a-b|\}\) can be partitioned into two bags whose sums differ by at most \(a+b-2c+\sum_{i\in W}i\). Here \(W\) is the multiset of manipulator weights, \(a,b,c\) are the total veto weights assigned to the three candidates by non-manipulators, and the coalition wants the candidate with veto weight \(c\) to win. The underlying reason is that manipulators should not veto their preferred candidate; they must divide their veto weight between the other two candidates.
My continuous mirror is Continuous Weighted-Veto Coalition Manipulation, \(\mathrm{CWVM}_\infty\).
The setting is a three-candidate election with candidates \(A,B,C\), where \(C\) is the coalition’s target and ties favour the coalition. The electorate is a continuum of total mass \(1\). A type includes its role, per-agent voting weight, preference or target, and—where relevant—the veto already cast. Thus agents of the same type are genuinely interchangeable.
Write the fixed electorate as a finite distribution \(\nu\), of total mass \(1-\lambda\), and the manipulating electorate as a finite distribution \(\mu\), of total mass \(\lambda\). A fixed type \(q\) has weight \(r_q\) and has already vetoed one candidate. A manipulating type \(t\) has weight \(w_t\); its mass may be divided between the three possible veto reports. The aggregate fixed veto weights are
\[ a=(1-\lambda)\sum_{q:\,q\text{ vetoes }A}\nu_qr_q, \]
with analogous definitions of \(b\) and \(c\).
An instance asks whether there are nonnegative masses \(x_{t,A},x_{t,B},x_{t,C}\) such that
\[ x_{t,A}+x_{t,B}+x_{t,C}=\lambda\mu_t \]
for every manipulating type \(t\), and such that \(C\) wins after the reassignment:
\[ c+\sum_t w_tx_{t,C}\le a+\sum_t w_tx_{t,A}, \]
\[ c+\sum_t w_tx_{t,C}\le b+\sum_t w_tx_{t,B}. \]
A solution is precisely such a mass assignment. This keeps every individual infinitesimal agent’s action discrete—each casts one veto—but allows a positive-mass type to be divided into subpopulations taking different actions. The continuity is in the population, not in the candidates or the veto outcome.
The regime is plausible in a large shareholder, union, party, or delegate election with three nominees. There may be millions of participants but only a few share classes or organizational roles. Within a class, agents have the same voting weight and the same relevant preference; a large organized bloc forms the manipulating coalition. Thus \(N\) is very large while the number of distinct types \(\tau\) is fixed or modest. This is a legitimate high-multiplicity version of the paper’s weighted-veto problem, even though the paper’s random experiments deliberately draw almost-unique weights.
This mirror is close to the authors’ problem because it preserves the veto rule, weighted scores, the three-candidate target, coalition manipulation, and the exact strategic choice identified in Theorem 1: dividing manipulator veto weight between the two candidates that should lose. It changes only the indivisibility of repeated voter types.
The continuous problem is tractable. No manipulator needs veto \(C\), so set \(x_{t,C}=0\). Let
\[ W_{\mathrm{tot}}=\sum_t w_t\lambda\mu_t \]
be the coalition’s total veto weight, and let \(u\) be the amount assigned to veto \(A\). The remaining weight \(W_{\mathrm{tot}}-u\) vetoes \(B\). A successful manipulation exists exactly when
\[ \max\{0,c-a\}+\max\{0,c-b\}\le W_{\mathrm{tot}}. \]
Equivalently, the coalition has enough divisible weight to cover the two deficits below \(C\). A concrete assignment can be constructed greedily across the finite type list. More generally, the formulation is a linear program with \(O(\tau)\) variables and rational data, so this mirror is in Class A.
The continuous result therefore gives a meaningful answer to the paper’s central computational phenomenon: the discrete reduction to number partitioning is caused by indivisible weighted voters. In a high-multiplicity regime, the same weighted-veto manipulation becomes a fractional load-balancing problem. The discrete-to-continuous bridge is explicit: if type \(t\) represents \(N_t\) voters, then \(\mu_t=N_t/N\), and an integral discrete manipulation is an assignment in multiples of \(1/N\). The continuous solution is its high-multiplicity relaxation; rounding and margin bounds become natural follow-up questions.
This case does not claim to mirror the paper’s empirical phase-transition claims, its CKK running-time plots, or its random independent-weight distributions. Those are not numbered computational results, and almost-unique random weights are specifically unlike the high-multiplicity regime. It covers Theorem 1 and the underlying three-candidate weighted constructive manipulation problem.
The weakest point is also clear: the mirror removes precisely the indivisibility that makes the partitioning reduction interesting. If the authors regard arbitrary individual weights—and hence number partitioning—as essential to their problem rather than as a population-multiplicity phenomenon, they may reject this relaxation. My defence is that the rule, target, weights, coalition, and strategic choice are unchanged, while the proposed scenario supplies a credible population with many interchangeable agents per weight class. The mirror therefore asks a substantive question the paper does not ask: does weighted-veto manipulation remain computationally difficult when the electorate is genuinely high-multiplicity?
It also generates sharper follow-up questions: when does a fractional winning assignment round to an exact discrete manipulation; how large must the winning margin be; what happens when the number of weight classes grows with the input; and can continuum-specific hardness arise if the coalition faces additional coupling or budget constraints?
The strongest negative case attacks the only anchor, Theorem 1, at the level of what makes it computationally interesting. Its object is not a population distribution but a finite multiset of indivisible items. Each manipulator’s weight must go wholly to \(A\), \(B\), or \(C\); the subset-sum gaps created by that indivisibility are exactly what produces the partitioning formulation.
In the proposed continuum, that object disappears. For a type of weight \(w_t\), an arbitrary fraction of its mass can veto \(A\) and the remainder \(B\). More generally, with any atomless weight distribution, the attainable \(A\)-veto weight fills the entire interval from \(0\) to the coalition’s total weight. The multiset \(W\), including the special item \(\lvert a-b\rvert\), is replaced by one scalar \(W_{\mathrm{tot}}\). The feasibility condition consequently collapses to the two aggregate deficits
\( \max\{0,c-a\}+\max\{0,c-b\}\le W_{\mathrm{tot}}. \)
This is not merely an easy answer to a difficult question. The population structure has ceased to be an active part of the problem: weight classes, correlations among voters, and the entire partition geometry become irrelevant once only aggregate veto weight matters. Adding a richer ranking type space does not help, because under veto manipulation the ranking information has no effect after the target candidate is fixed.
The best rescue would be to let the continuum choose the coalition as well, perhaps minimizing coalition mass or incorporating type-dependent recruitment costs. That still gives a fractional knapsack or small linear program, since every type contributes only one scalar resource: veto weight. To recover the partitioning phenomenon, one must require every positive-mass type to act as an indivisible block, or retain finitely many exceptional indivisible voters. The former restores a discrete support constraint; the latter leaves a discrete problem embedded in the model. Neither is the atomless high-multiplicity mirror proposed by the programme.
The paper’s actual phase-transition phenomenon is even less continuizable. Its critical coalition has size \(m=\Theta(\sqrt n)\), hence normalized mass \(m/n\to0\). In a normalized continuum it disappears, while a positive-mass coalition belongs to a different asymptotic regime. The finite-sample fluctuations and CKK search behaviour therefore have no direct population-continuum counterpart without introducing additional scaling assumptions.
There is also a narrower anchor objection: Theorem 1 is a structural reduction, not a complexity theorem proved by this paper; the NP-hardness is cited from elsewhere. Thus the proposed LP is largely a new relaxation inspired by the paper, rather than a continuization of one of its main computational results.
Still, this negative case does not meet the universal burden. A large shareholder or delegate electorate with repeated weight classes is a credible high-multiplicity regime, and the proposed model genuinely asks what happens when the paper’s indivisible weighted voters become divisible mass. The disappearance of number partitioning is precisely the kind of Class A outcome ChoCo is meant to document. So the honest verdict is that the mirror may be too elementary and too far from the paper’s empirical contribution to be a strong showcase, but I cannot defend “no worthwhile continuous mirror in any scenario.” Theorem 1 survives as a legitimate, if low-impact, anchor.
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.