| paper | Complexity of Strategic Behavior in Multi-Winner Elections |
| authors | R. Meir, Ariel D. Procaccia, J. Rosenschein, Aviv Zohar |
| venue | JAIR 2008 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 4.15
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), distinguished candidate \(p\), rational type masses \(\mu_t\), integral Bloc ballots \(B_t\subseteq C\) with \(|B_t|=k\), and rational budget \(\rho\), does there exist \(x_t\) with \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le\rho\) such that \(S_x(c)=\sum_t(\mu_t-x_t)\mathbf{1}[c\in B_t]\) makes \(p\) one of the \(k\) winners under adversarial tie-breaking?
A high-multiplicity Bloc electorate with finite ballot types \(B_t\), masses \(\mu_t\), and removable masses \(x_t\); the decision objective is feasibility under budget \(\rho\), with the optimization variant minimizing \(\sum_t x_t\).
The proponent treats \(x_t=q_t/n\) as an exact equivalence, but the continuous problem permits fractional removals with no integral \(q_t\) counterpart; therefore Proposition 4.15 does not establish Class B hardness.
fatal: False
The mirror covers the voter-removal results in Propositions 4.13 and 4.15. It leaves manipulation, SNTV voter control, candidate control, and the remaining table entries untouched.
The strongest honest case is a high-multiplicity mirror of the paper’s voter-control problems, not of its single-voter manipulation problem. A single manipulator would have zero mass in an atomless population, so I would not use Proposition 3.9 as my lead. The voter-control results retain the paper’s action exactly while making the electorate continuous.
My lead anchor is Proposition 4.15, proved in this paper. It states:
Control by Removing Voters in Bloc is NP-complete, even when the chairman merely wants to include a distinguished candidate among the winners.
The proof reduces from the paper’s cited Approval-control hardness result, but Proposition 4.15 itself is established in this paper.
The corresponding problem is Mass-Removal Bloc Control\(_\infty\). An instance contains a finite candidate set \(C\), a committee size \(k\), a distinguished candidate \(p\), a finite list of voter types \(t=1,\ldots,\tau\), rational masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), and a rational removal budget \(\rho\). A type \(t\) is a Bloc ballot \(B_t\subseteq C\) with \(|B_t|=k\); equivalently, it can be represented by a ranking whose top \(k\) candidates are \(B_t\). Thus every individual ballot remains integral, while \(\mu_t\) records the fraction of the population submitting that ballot.
The chairman chooses removed masses \(x_t\) satisfying
\[ 0\le x_t\le \mu_t \qquad\text{and}\qquad \sum_t x_t\le \rho. \]
After removal, candidate \(c\) has Bloc score
\[ S_x(c)=\sum_{t=1}^{\tau}(\mu_t-x_t)\mathbf{1}[c\in B_t]. \]
The question is whether there exists such an \(x\) for which \(p\) belongs to the \(k\) winners, using exactly the paper’s adversarial tie-breaking convention. A solution is the vector of removed masses \(x\).
This is recognisably the authors’ problem: the same Bloc rule, the same chairman, the same operation of removing voters, the same budget constraint, and the same constructive objective. Only the representation changes from a list of named voters to masses of indistinguishable ballot types, with \(r\) replaced by a population fraction \(\rho\).
A natural regime is a large membership-based election or online committee poll. Millions of members may use a relatively small menu of standard slates—for example, party slates, professional-association slates, or recommendation templates. The authority may invalidate at most \(\rho\) of the electorate after an eligibility audit, and can target members by ballot cohort. Here \(n\) is enormous while \(\tau\) is modest. The mass action is not an outcome-space relaxation: each member still casts an ordinary \(k\)-candidate Bloc ballot, and only the population of each ballot type is continuous.
The discrete-to-continuous correspondence is exact for rational instances. Given a discrete election with \(n_t\) voters of type \(t\), set
\[ \mu_t=\frac{n_t}{n}, \qquad \rho=\frac{r}{n}. \]
Removing \(q_t\) voters of type \(t\) corresponds to \(x_t=q_t/n\), and every Bloc score is divided by the same factor \(n\). Therefore the winner relation, including ties, is unchanged. Conversely, rational masses and removal amounts can be cleared of denominators to obtain an equivalent finite high-multiplicity election. Consequently, Proposition 4.15 gives a direct NP-hardness transfer to Mass-Removal Bloc Control\(_\infty\). I would classify this mirror as Class B: the hardness lives in the candidate and ballot structure, not in the mere existence of individually named voters.
A second worthwhile anchor is Proposition 4.13, also proved in this paper. It states:
Control by Removing Voters in Cumulative voting is NP-complete, even when the chairman is trying to make a distinguished candidate win in single-winner elections.
The paper proves this by reducing from Approval voter-control hardness.
The corresponding problem is Mass-Removal Cumulative Control\(_\infty\). An instance contains \(C\), a distinguished candidate \(p\), a point budget \(L\), rational masses \(\mu_t\), and a removal budget \(\rho\). A type \(t\) is an integral cumulative ballot
\[ a_t\in\mathbb{Z}_{\ge 0}^{C}, \qquad \sum_{c\in C}a_t(c)=L. \]
The chairman chooses \(x_t\) with \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le\rho\). The resulting score of \(c\) is
\[ S_x(c)=\sum_t(\mu_t-x_t)a_t(c). \]
For the exact anchored version, \(k=1\), and the question is whether \(p\) can become the unique winner under the paper’s adversarial tie-breaking rule. A solution is again the removed-mass vector \(x\).
This is also a plausible high-multiplicity regime: a very large electorate may use a finite collection of recurring cumulative-voting templates, such as “all points to one slate,” “split points between two policy blocs,” or standard organizational recommendations. Individual ballots remain integer point allocations; their aggregate frequencies are fractional. The same normalization argument transfers the paper’s hardness result, so this mirror is also Class B.
These two anchors cover a coherent part of the paper: voter control under Bloc and Cumulative voting. They do not claim to continuize every result. In particular, I would leave aside the paper’s candidate-control results and its one-manipulator results unless a separate model introduced a positive-mass strategic bloc. I would also not claim that the continuous formulation automatically makes anything easier. Its value is that it creates the correct computational object for asking whether hardness survives high multiplicity.
The main follow-up questions are whether hardness persists when \(\tau\) is fixed or small, whether minimum removed mass can be computed or approximated, what happens with type-dependent removal costs, and whether restrictions on the ballot templates yield an LP or configuration algorithm. One could also compare exact rational masses with approximate masses and study how much removal is needed to overcome a prescribed score margin.
The weakest point is the realism of fractional control. A real authority may be able to remove individual accounts but not exactly \(37.4\%\) of a ballot cohort. The mirror is defensible when cohorts are genuinely large and administratively divisible; it is weaker when voters are organized into indivisible local units. A second limitation is that the paper’s worst-case reductions may use many distinct ballot types, so they establish hardness of the general continuous problem without proving hardness in the particularly interesting regime \(\tau\ll n\). That is a limitation on the eventual theorem, not on whether the mirror is the authors’ problem. The proposed questions preserve the paper’s rule, action, objective, and winner semantics while making the electorate itself the continuous object, which is exactly the continuization programme’s target.
The strongest negative case is not that these mirrors are ill-posed. Both anchors are genuine named computational results, and both admit a plausible high-multiplicity interpretation. The honest negative case is therefore weak: the proponent has overclaimed what their reductions establish, but has not shown a worthless mirror.
The central technical error is the claimed hardness transfer. Let \(a_t(c)\) be the score given by type \(t\), and let \(x_t\) be removed mass. Both anchors have the form
\[ S_x(c)=\sum_t(\mu_t-x_t)a_t(c), \qquad 0\le x_t\le\mu_t, \qquad \sum_t x_t\le\rho. \]
A discrete solution with \(q_t\) removed voters gives \(x_t=q_t/n\), but the converse fails: a feasible continuous solution may remove a fractional amount of every type even when no integral vector \(q\) exists. Thus normalization proves only that the discrete problem embeds into the continuous relaxation; it does not preserve no-instances and does not transfer NP-hardness. The proponent’s Class B classification for either Proposition 4.15 or Proposition 4.13 is therefore unsupported.
For Proposition 4.13 the relaxation is especially transparent. Since the anchor uses \(k=1\) and a distinguished candidate \(p\), the continuous control question is simply whether there are \(x_t\) satisfying
\[ S_x(p)>S_x(c) \]
for every \(c\neq p\), together with the mass-budget constraints. After a conventional margin or tie-breaking restatement, this is an ordinary linear-programming feasibility problem. The paper’s knapsack hardness comes from choosing whole voters; fractional removal destroys precisely that integrality. This is a legitimate Class A mirror, but it is also a very generic convex relaxation. Nothing in the paper suggests a distinctive cumulative-voting phenomenon, a pricing problem, or a nontrivial continuous structure. Type-dependent removal costs still leave the same LP.
Bloc control is more interesting because multi-winner membership introduces a disjunction: \(p\) must outrank enough competitors under the tie rule. But that does not rescue the proponent’s argument. The paper’s hardness reduction again uses individually selectable voters, while the proposed natural regime has relatively few ballot cohorts. The reduction supplies no hardness result when \(n\) is large relative to \(\tau\); indeed, that is exactly the regime in which fractional cohort removal is most unlike the paper’s combinatorial control problem. A worthwhile follow-up could study the resulting union of linear regions, its parameterized complexity, rounding guarantees, or minimum-cost removal. But those would be new continuous-control results, not consequences of Proposition 4.15.
The realism objection is also insufficient. Removing \(37.4\%\) of a ballot cohort can be a sensible administrative operation, and the ballot itself remains integral. The authors’ problem is recognisably preserved. Nor can one object that high multiplicity merely groups voters: grouping identical agents is precisely the programme’s intended regime.
Consequently, I cannot honestly defeat both anchors on the stronger universal claim. The best negative conclusion is narrower: the proponent has not demonstrated a Class B continuation, and the cumulative anchor may collapse to a routine LP. But both are legitimate population continuizations, and the Bloc version in particular could support meaningful new work on fractional control, rounding, and the boundary between cohort-level tractability and individual-level hardness. A claim that no worthwhile mirror exists in any scenario would overreach the evidence.
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.