How Hard is Bribery in Elections with Randomly Selected Voters

The strongest case is a high-multiplicity, sparse-committee mirror of the paper’s BRSV problem. My lead anchor is Theorem 1, proved in this paper, although its proof invokes the earlier classical bribery hardness results [35], [8], and [9].

Consider a protocol with \(N\) eligible voters, where \(N\gg\tau\), but voters fall into only \(\tau\) complete types. A type is \(t=(\sigma,\kappa)\), where \(\sigma\) is a complete ranking and \(\kappa\) is that type’s per-voter bribery cost. This is plausible in the paper’s blockchain setting: millions of validators may be distributed among a relatively small number of standardized policy profiles and fee or economic tiers. The briber can purchase a fraction of a cohort, rather than address individuals one by one.

The natural non-degenerate limit of the paper’s sampling rule is the sparse-committee regime. Let the expected committee size be \(\lambda\), with the finite population using sampling probability \(p_N=\lambda/N\). If \(N\mu_t\) voters have type \(t\), then the selected number of such voters converges to an independent Poisson random variable with mean \(\lambda\mu_t\). This preserves random committee uncertainty while making the population itself continuous.

I would call the resulting problem Poissonized Continuous Random-Sample Borda Bribery, or \(\mathrm{PCRSB}_\infty\)-Borda.

An instance consists of candidates \(D=\{d_1,\ldots,d_{m+1}\}\), a designated candidate \(d^\star\), an explicit finite type set \(\mathcal T\subseteq \Sigma(D)\times\mathbb Q_{\ge0}\), rational masses \(\mu_t\ge0\) with \(\sum_t\mu_t=1\), an integer \(\lambda>0\), and a rational budget \(B\).

The briber chooses variables \(x_{t,\rho}\ge0\), where \(x_{t,\rho}\) is mass transferred from type \(t=(\sigma_t,\kappa_t)\) to ranking \(\rho\). The constraints are

\[ \sum_{\rho\in\Sigma(D)}x_{t,\rho}\le\mu_t \]

for every \(t\), and

\[ \sum_{t=(\sigma,\kappa)}\sum_{\rho\in\Sigma(D)} \kappa\,x_{t,\rho}\le B. \]

The resulting mass of ranking \(\rho\) is

\[ \nu_\rho= \sum_{\kappa}\left(\mu_{(\rho,\kappa)} -\sum_{\eta}x_{(\rho,\kappa),\eta}\right) +\sum_{t,\rho'= \rho}x_{t,\rho}. \]

After bribery, independently sample

\[ Z_\rho\sim\operatorname{Pois}(\lambda\nu_\rho) \]

for every ranking \(\rho\). Under Borda, define the score of candidate \(a\) by

\[ S_a(Z)=\sum_{\rho} Z_\rho\,s_{\mathrm{Borda}}(\rho,a). \]

The value of a feasible transfer \(x\) is

\[ W(x)= \Pr\!\left[ S_{d^\star}(Z)\ge S_a(Z) \text{ for every }a\in D \right]. \]

The problem asks for a feasible \(x\) maximizing \(W(x)\). Its approximation version asks, given \(\varepsilon>0\), for a transfer with value at least \(\operatorname{OPT}/(1+\varepsilon)\); its threshold version asks whether some feasible transfer has \(W(x)\ge\theta\).

This is recognizably the authors’ problem: the candidates, rankings, scoring rule, pre-sampling bribery action, individual bribery costs, budget, random committee, and co-winner objective are all retained. The changes are that identical voters are represented by rational mass and the independent-sampling process is taken in its sparse high-multiplicity limit. Clearing denominators in \(\mu\) recovers finite clone populations, and the Poisson law is the limit of the paper’s own independent Bernoulli committee rule.

The connection to Theorem 1 is direct in spirit. Theorem 1 states that, assuming \(P\ne NP\), BRSV has no polynomial-time \(O(1)\)-approximation for Borda, \(k\)-approval with \(k\ge3\), or \(k\)-veto with \(k\ge2\). The paper proves this by observing that \(p=1\) recovers ordinary bribery, and that \(p\) arbitrarily close to \(1\) preserves a large probability gap.

For the continuous problem, I would provisionally expect Class C, rather than automatic hardness transfer. Fractional mass transfer may dissolve the subset-selection component of classical bribery: within a type, the briber may buy any amount of mass. Thus Theorem 1’s reduction does not transfer unchanged. But the Poisson winning probability is a genuinely nonlinear function of the post-bribery mass vector, involving a multidimensional distribution of Borda-score differences. When \(m\) is part of the input, optimizing this probability may remain hard for a new, continuum-specific reason. The paper’s own observation that the winning probability is difficult to compute even for a given finite solution makes this a credible Class C candidate.

There are also tractable subregimes. With fixed \(m\), the score-difference state space is finite-dimensional, suggesting an analogue of Theorem 5. In the dense regime where \(p\) is fixed as \(N\to\infty\), sampling fluctuations vanish and the winner is determined by weighted Borda scores; the bribery problem then becomes a linear or piecewise-linear mass-transfer problem. The interesting question is therefore the sparse random-committee regime, where randomness survives the population limit.

The weakest point is precisely the Poissonization. Theorem 1’s hardness proof uses \(p=1\) or \(p\) close to \(1\), whereas my mirror uses \(p_N=\lambda/N\). A referee could reasonably say that this changes the asymptotic regime. I would concede that it is an extension rather than a literal theorem-preserving translation. Nevertheless, it is the natural non-degenerate high-multiplicity limit of the paper’s sampling model: with fixed \(p>0\), an atomless population has deterministic sampled mass almost surely, so the paper’s central randomness disappears entirely.

This mirror covers Theorem 1 only. Theorem 3 suggests a separate plurality mirror that may admit a continuous approximation scheme, perhaps via convex or configuration optimization, but I would not add it as an anchor without proving that its Poisson objective retains the paper’s semantics. The main follow-up questions are whether Theorem 1’s inapproximability survives any mass-splitting model, whether the general Borda version is Class C, and where the transition occurs between the deterministic dense limit and the genuinely stochastic sparse limit.