d4-conf-aaai-2012-0190

I’d make a narrow case around Theorem 3, the paper’s NP-completeness result for manipulation under \(\operatorname{eliminate}(\mathrm{veto})\).

Theorem 3, proved in this paper (the article sketches the proof and says the full proof is in a technical report), says that with an unbounded number of candidates, deciding whether one manipulator can make a designated candidate win under \(\operatorname{eliminate}(\mathrm{veto})\) is NP-complete. The election uses unweighted votes, and the manipulator’s decision is which ranking to submit.

The mirror I’d put to a prover is Mass-Profile Veto-Elimination Manipulation. An instance has a candidate set \(C\), a fixed tie-breaking order, a target \(p\), a rational distribution \(\nu\) of nonstrategic mass over complete rankings, and a designated strategic block of mass \(\epsilon>0\) whose members share a true ranking \(t^\star\). The masses sum to one. The block must submit one common ranking \(r\). The question is whether some \(r\) makes \(p\) win when \(\operatorname{eliminate}(\mathrm{veto})\) is run on \(\nu+\epsilon\delta_r\): in each round, eliminate the candidate with the greatest mass ranked last among those still standing, using the fixed tie-breaker. A solution is the ranking \(r\). Here mass is a fraction of the electorate, and the reported ballot moves the strategic block’s mass from its true type to \(r\).

This preserves the paper’s core decision: can a strategic voter’s report make the target win? It also gives a direct bridge to the anchor. For an election with \(N\) ordinary voters and one manipulator, set \(\epsilon=1/(N+1)\) and \(\nu_t=n_t/(N+1)\), where \(n_t\) is the number of ordinary voters with ranking \(t\). Every elimination comparison is unchanged by this normalization. The continuous problem permits arbitrary rational masses as well, so the electorate itself is represented by proportions rather than an explicit list of voters. In a large election where many voters share a relatively small number \(\tau\) of rankings, the regime is natural; the strategic mass can be one pivotal voter or a coordinated bloc with a common report.

I expect hardness to transfer. The discrete instances from Theorem 3 embed directly, so the mirror is NP-hard. It is also in NP: a proposed ranking \(r\) is a polynomial-size certificate, and the elimination rounds can be computed with exact rational arithmetic. Thus this narrowly defined mirror is NP-complete. This is Class B hardness from the candidate dimension, not a claim that the paper’s hardness dissolves under population continuization.

The weak point is that the anchor is specifically about one manipulator, while a positive-mass block is a cohort; requiring the cohort to cast one common ranking keeps the action close to the paper’s, but limits the model. Also, as the population grows, a singleton’s fraction shrinks, so it is pivotal only when the relevant score margins shrink with it. If the desired mirror instead requires a nonatomic population and a manipulable bloc of fixed positive size whose members may split their reports, that is a different problem and Theorem 3 alone does not settle its complexity.

This mirror covers Theorem 3 only. Natural follow-up questions are whether a minimum manipulable fraction can be computed, what happens when a bloc may divide its mass across rankings, and whether the problem becomes tractable under restrictions on \(m\), \(\tau\), or the input bit length \(L\).