d4-conf-atal-2017-0192

The strongest mirror is manipulation by a bloc of voters who share one ideal approval ballot. Take a large multiple referendum or unconstrained committee election: millions of citizens may have only a modest number \(\tau\) of distinct ideal ballots because they follow a small set of party, union, or campaign positions. A type is a complete ideal ballot \(t\in\{0,1\}^m\), with Hamming-coherent preferences over outcomes; its mass \(\mu_t\) is the fraction of society with that ballot. A coordinated fraction of one type can report another ballot. This keeps the paper’s outcome rule, strategic misreporting, and voter utility, while making the population itself continuous.

My anchor is Theorem 1, proved in this paper. It says that if the rank weights are non-increasing and the resolute \(w\)-AV rule differs from resolute minisum, then for any number \(m\) of candidates there is a profile and a voter who can change their approval ballot and strictly improve their outcome under the fixed linear-order tie-break. In other words, every fair resolute rule in this family other than minisum is manipulable. This is a named strategic result, not a theorem about NP-hardness or running time; the paper gives no algorithmic complexity classification for manipulation.

Here is the continuous question I would hand to a prover: Continuous Mass-Bloc Manipulation. An instance gives \(m\), a finitely supported rational distribution \(\mu\) over \(\{0,1\}^m\), a fixed total order for breaking ties between winning outcomes, and a rational mass bound \(q>0\). It also gives a normalized rank-weight measure \(\lambda\), with non-increasing rational step-function density and, optionally, an atom at rank zero. For each outcome \(S\subseteq [m]\), let \(Q_{\mu,S}(u)\) be the population’s Hamming distances from \(S\), arranged in decreasing order by rank, and score it by
\[ D_{\lambda,\mu}(S)=\int_{[0,1]}Q_{\mu,S}(u)\,d\lambda(u). \]
The rule selects a score-minimizing outcome, resolving ties by the given order. The decision question is whether there are a type \(t\) with \(\mu_t>0\), a reported ballot \(b\), and a mass \(0<\varepsilon\leq\min(q,\mu_t)\) such that moving that mass from \(t\) to \(b\) makes the selected outcome strictly closer in Hamming distance to \(t\). A YES solution is the transfer and the before-and-after outcomes; NO means no such transfer exists. The scoring objective is the paper’s aggregate OWA objective in rank-integral form; the bloc’s goal is to improve its members’ Hamming utility.

This is an exact bridge for finite profiles. Given a paper weight vector \(w_n\), set the density to \(n w_n(i)\) on rank interval \(((i-1)/n,i/n]\). For a profile of \(n\) equally weighted voters, the integral score then equals the paper’s \(w_n\)-score exactly. A one-voter manipulation becomes a transfer of mass \(1/n\). Thus Theorem 1 supplies YES instances of the continuous question for every non-minisum weight vector it covers, with \(q=1/n\). This is an embedding of the paper’s result, not a claim that a new continuum theorem has been proved.

For the instance-specific decision or search problem, I would tentatively expect Class B, hardness transferring, because the agenda still has \(2^m\) possible outcomes and the discrete instances embed exactly. That is a forecast, not a hardness conclusion from Theorem 1: the paper does not establish a complexity lower bound for the corresponding discrete algorithmic problem. Natural follow-up questions are how to compute the minimum mass needed for a profitable manipulation, how that threshold depends on \(m,\tau\), and the input bit length, and whether manipulations persist when the required mass must stay bounded away from zero.

The weakest point is the move from an individual voter to a positive-mass bloc. A single atomless voter has zero mass and cannot change the outcome; allowing a fractional bloc therefore changes the strategic question. The finite embedding preserves the paper’s unilateral manipulation exactly at mass \(1/n\), but those masses shrink as the electorate grows. So this is a credible continuous extension of the paper’s problem, though a referee could reasonably ask whether the authors would accept coalition manipulation as their intended mirror. This case covers Theorem 1’s resolute manipulability result; it does not claim to mirror the paper’s experimental frequency-of-manipulation study or its separate irresolute-rule theorems.