d4-conf-ijcai-2019-0826

I would lead with Theorem 1, proved in this paper. It states that, assuming \(\mathrm{W[1]}\ne\mathrm{FPT}\), there are continuous willingness functions for which Plurality EBEU has no \(g(k)\)-approximation algorithm running in FPT time parameterized by \(k\), for any computable function \(g\), even with only two candidates. The paper proves this by reduction from a cited hardness result for two-dimensional Knapsack (its Theorem 2, citing Kulik and Shachnai). This is the paper’s strongest anchor for asking whether population continuization dissolves a known hardness result.

A plausible regime is a very large online or local election whose voters fall into a modest number of behavioral types. For Plurality, a type \(t\) consists of a voter’s initial top candidate and willingness function \(f_t\); two voters share a type only if both match. Think millions of voters but perhaps dozens or hundreds of types, with type masses measured from the electorate. The attacker has a budget proportional to population size and may target a fraction of the population. In the corresponding finite election with \(N\) voters, mass \(\mu_t\) represents about \(N\mu_t\) voters, the recipient limit is about \(\kappa N\), and the budget is about \(NB\).

Here is the continuous problem I would hand to a prover: Mean-Field Plurality Bribery with Uncertain Response, the mirror of Theorem 1. There are two candidates, \(c_1\) and the target \(c_2\); type masses \(\mu_t\in\mathbb{Q}_{\ge0}\) sum to \(1\), and \(c_1\) initially wins. Each type has an explicit rational piecewise-linear willingness function \(f_t:\mathbb{R}_{\ge0}\to[0,1]\), eventually constant. The attacker may select mass \(\kappa\), assigning different bribe amounts to different portions of each type, subject to a per-capita budget \(B\). Represent that decision by a nonnegative measure \(\nu_t\) over bribe amounts: \(\nu_t(A)\) is the mass of type \(t\) paid an amount in \(A\). Require \(\nu_t(\mathbb{R}_{\ge0})\le\mu_t\), total selected mass \(\sum_t\nu_t(\mathbb{R}_{\ge0})=\kappa\), and total spend \(\sum_t\int x\,d\nu_t(x)\le B\). Zero-payment selections can pad the exact mass, as in the paper’s exact-\(k\) formulation.

In the nonatomic electorate, a bribed mass \(\nu_t\) produces converted mass \(q_t=\int f_t(x)\,d\nu_t(x)\): individual response uncertainty becomes a deterministic fractional response. The problem is to return a feasible payment schedule maximizing \(q=\sum_{t:\,t\text{ initially votes }c_1}q_t\). The target wins precisely when \(\mu_{c_2}+q\ge\mu_{c_1}-q\), with ties counted as wins. Thus the question, the type information, the bribe action, and the plurality objective all remain recognizable; the population and budget are expressed in mass units.

I expect this explicit-input version to be Class A. For each type, mass assigned across payment levels generates a convex combination of points \((x,f_t(x))\). With piecewise-linear curves, it suffices to use their breakpoints: a variable records how much type mass receives each breakpoint amount. The budget, recipient-mass, and winning-margin constraints are linear, so maximizing converted mass is an LP of size polynomial in the number of types, curve breakpoints, and input bit length. The sharp willingness-function increases used in Theorem 1’s reduction remain representable, but the attacker can split each type’s mass continuously. That removes the reduction’s all-or-nothing item choice.

The weakest point is substantial: this is a mean-field analogue of the paper’s success-probability objective, not an exact preservation of it. As the electorate grows, independent responses concentrate around their expected masses; the finite election’s nontrivial win probability survives mainly near a zero vote margin. Also, Theorem 1’s reduction gives key voters item-specific willingness functions, so the number of distinct types generally grows with the number of items. Its construction therefore does not itself exhibit the large-population, small-support regime.

The next questions are whether a positive-margin continuous solution can be rounded to a finite high-multiplicity election with a useful win-probability guarantee; how to handle the near-tie regime where response fluctuations matter; and whether succinct or oracle representations of willingness functions make the payment-level pricing problem hard. The mirror covers Theorem 1’s two-candidate Plurality EBEU result, with explicit piecewise-linear curves. It does not cover the paper’s results for other voting rules or claim that its finite stochastic objective has an identical continuum limit.