d4-conf-ijcai-2011-0224

The strongest honest case is a narrow Class A mirror: computing the paper’s low-influence approximation for plurality when the electorate is represented by masses of voter types. The paper has no named NP-hardness result. Theorem 5.5 says that for every \(\beta>0\), sufficiently large plurality elections have no trivial \(\beta n\)-approximation; that is an approximation lower bound, not a computational-hardness result.

My lead anchor is Corollary 4.6, proved in this paper. It says that if a voting rule \(f:(\Sigma_k)^n\to[k]\) is efficiently computable, independent of voter identities, and has a constant number \(k\) of outcomes, then the randomized approximation \(g\) constructed in Theorem 4.1 can be computed in polynomial time. Theorem 4.1 supplies its guarantees: for any \(\epsilon>0\) and \(\delta\ge k(k+1+\epsilon)/\epsilon-1\), \(g\) is \(\epsilon\)-strategy-proof and a \(\delta\)-approximation of \(f\). Its lottery weights are based on the minimum number of ballots that must be changed to make each outcome correct. Corollary 4.6’s proof computes those distances by examining \(O(n^{k!})\) vote configurations, so the stated runtime is polynomial in the explicit voter count \(n\) when \(k\) is fixed. That runtime fact is the anchor; it does not itself establish a polynomial-time algorithm for binary-encoded masses.

Here is the continuous problem I would put to a prover: Mass-Corruption Plurality Approximation. Fix \(k\) outcomes and let ballot types be complete rankings, augmented if needed by a fixed finite menu of cardinal utility vectors so agents with the same type are identical for the incentive question. A society is a rational distribution \(\mu\) over these types, listed by its \(\tau\) supported types and binary masses. Its size might represent millions of voters whose ballots fall into relatively few ranking classes. Plurality sees each type’s first choice; the output remains a lottery over the original \(k\) candidates.

For each candidate \(j\), define \(d_j(\mu)\) as the infimum mass that must change reported ranking to make \(j\) win. More explicitly, minimize \(\sum_{t\ne t'}x_{t,t'}\) over nonnegative mass transfers from type \(t\) to type \(t'\), with outgoing mass at most \(\mu_t\), subject to the resulting society giving \(j\) the plurality win. Transfers preserve each voter’s utility type. This is the continuous version of the paper’s vote-corruption distance. The plurality winning constraints are linear in the first-choice masses.

Let \(\alpha\) be a maximum coalition mass and \(\eta\) an allowed gain in aggregate utility, where each voter’s utility lies in \([0,1]\). Ask for an algorithm that, on input \((\mu,\alpha,\eta)\), computes the exact lottery \(G_{\alpha,\eta}(\mu)\) and whose rule across societies has the following guarantees: every outcome in its support is reachable by changing at most \(k(k+1)\alpha^2/\eta\) mass, and no coalition of mass at most \(\alpha\) can improve its integrated true utility by more than \(\eta\) through a joint report change. A natural candidate, directly modeled on the paper’s construction, assigns probability \(p_j\) proportional to \([1-\rho d_j(\mu)]_+\), with \(\rho=\eta/[k(k+1)\alpha^2]\). The scaling comes from the paper’s coalition extension, Corollary 4.5: taking a coalition of \(t\approx\alpha n\) voters and aggregate utility allowance \(n\eta\), then normalizing vote changes by \(n\), gives this mass-distance scale in the limit. The continuous coalition guarantee itself would still need to be established carefully.

I expect this problem to be tractable. Each \(d_j(\mu)\) is a minimum-mass-transfer LP. For plurality, it can be compressed to flows between first-choice candidates, with polynomially many variables in \(k\); the supported rankings give the first-choice masses in time polynomial in \(\tau\). Exact rational LP optimization then computes the lottery in time polynomial in \(k,\tau,L\), where \(L\) includes the input bit lengths. A solution is the exact probability vector, together with optimal transfer certificates for the \(d_j\) values and a proof of the coalition guarantee. This is a genuine population continuization: the input is a distribution over voter types, while outcomes remain candidates and the paper’s vote-corruption metric becomes changed mass.

The authors have a plausible reason to recognize it as their problem. It retains the same plurality rule, strategic reports, randomized approximation, utility bounds, and notion of closeness. The high-multiplicity setting is also credible: a large election can have many voters and relatively few distinct ballots. The continuous society replaces a ballot count with its population fraction, and the positive-mass coalition condition keeps incentives meaningful when individual voters have zero mass. The mirror covers Corollary 4.6’s algorithmic claim, specialized to plurality; it does not claim to continuize the paper’s outcomes or its full mechanism classification.

The weakest point is that this changes the incentive unit. Individual strategy-proofness becomes vacuous in an atomless population, so the mirror uses mass coalitions, supported by the paper’s own coalition extension but not by Corollary 4.6 itself. Also, the paper’s polynomial time is in \(n\), while the proposed question asks for complexity in the binary mass encoding. That is not already proved by the anchor; it is precisely the new high-multiplicity computational question.