d4-journals-jair-2019-0047

The strongest mirror is an exact, high-multiplicity version of SR-Weighted-\(\$Bribery\): spend money to change enough ballots that a preferred candidate wins. The input remains a society of voters with preferences, weights, and prices; only the population is represented by masses.

My lead anchor is Theorem 22, proved in this paper. It says that for SR-Weighted-\(\$Bribery\) under a constant or non-concentrated scoring rule, there is a polynomial-time randomized algorithm that makes \(p\) a co-winner at cost at most
\[ \Psi_{\mathrm{OPT}}+\widetilde O\!\left(\sqrt{\psi_{\max}(\Psi_{\mathrm{OPT}}+\psi_{\max})\,\bar r_{\max}r_{\max}}\right) \]
with exponentially small failure probability. Here \(\Psi_{\mathrm{OPT}}\) is the minimum total price of a successful bribery, \(\psi_{\max}\) is the maximum voter price, \(r_{\max}=\max_\ell \psi_\ell/w_\ell\), and \(\bar r_{\max}=\max_\ell w_\ell/\psi_\ell\); the suppressed factors are polylogarithmic in the input size. The theorem covers the case where weights and prices grow with the input. Its Corollary 23 gives the special case of constant weights and prices, with additive cost \(\widetilde O(\sqrt{\Psi_{\mathrm{OPT}}})\).

The paper discusses NP-hard bribery problems in its related-work prose, but the supplied text has no numbered hardness result for them. So I use Theorem 22 as the numbered anchor rather than presenting an unnumbered claim as a theorem. The mirror below concerns the same optimization problem that Theorem 22 approximates; it is not a claim that the theorem itself proves an exact continuous algorithm.

A plausible regime is a large election in which many voters share a ballot and a campaign-cost class. For example, a national campaign may face millions of voters but only a comparatively small number \(\tau\) of recurring combinations of ballot, voting weight, and per-voter persuasion price. Let each type be \(t=(r_t,w_t,\psi_t)\), where \(r_t\) is a complete ranking, and let \(\mu_t\) be its fraction of the population. Voters of that type are interchangeable for the problem: each contributes weight \(w_t\), and changing each ballot costs \(\psi_t\). This is a scenario about a particular large electorate, not a claim that every election has this regime.

The continuous problem — lead. Given candidates \(C\), preferred candidate \(p\), a scoring vector \(\alpha\) in either of Theorem 22’s scoring-rule classes, and a rational-mass support \(\{(t,\mu_t)\}\), choose amounts \(x_{t,\pi}\ge 0\) to move from each source type \(t\) to each different ranking \(\pi\), with \(\sum_{\pi\ne r_t}x_{t,\pi}\le\mu_t\). Each converted unit keeps its original weight and price. Minimize \(\sum_t\psi_t\sum_{\pi\ne r_t}x_{t,\pi}\), subject to \(p\)’s final weighted score being at least every competitor’s. In particular, the score of candidate \(c\) is
\[ S(c)=\sum_t w_t\left[\left(\mu_t-\sum_{\pi\ne r_t}x_{t,\pi}\right)\alpha_{\operatorname{pos}_{r_t}(c)} +\sum_{\pi\ne r_t}x_{t,\pi}\alpha_{\operatorname{pos}_{\pi}(c)}\right]. \]
A solution is an optimal rational mass-transfer schedule. For a discrete electorate with \(n_t\) voters of each type, \(\mu_t=n_t/n\); the continuous objective is total discrete price divided by \(n\), and score normalization does not change the winners.

I expect this mirror to be Class A, tractable. Its linear program has a mass-capacity constraint for each of the \(\tau\) source types and one score constraint per competitor, but exponentially many possible destination rankings. The pricing question for a source type is to optimize a linear combination of candidates’ positional scores over rankings. That is a weighted assignment problem, solvable in polynomial time; excluding the unchanged ranking can also be handled in polynomial time. Thus the LP can be optimized in time polynomial in \(m\), \(\tau\), and the input bit length \(L\). This gives the paper’s continuous population version a concrete computational question, and its fractional mass allocation is close to the LP relaxation the authors themselves use to jointly choose voters to bribe and their replacement ballots.

The mirror covers Theorem 22’s underlying weighted, priced bribery optimization, including its constant-weight-and-price special case in Corollary 23 and the unit-weight or unit-price cases. It does not attempt to mirror the paper’s separate WCM and UCM results. The exact continuous LP also appears to work for positional scoring vectors beyond the two classes in Theorem 22, though that would extend the mirror’s scope beyond this anchor.

The main follow-up is the discrete-to-continuous gap: when each type has \(n\mu_t\) voters, how close is the integer optimum to the fractional mass optimum, and how does that gap depend on \(n\), \(\tau\), weights, and prices? Theorem 22’s sublinear additive guarantee for constant weights and prices makes that a particularly natural comparison to investigate.

The weakest point is that fractional bribery allows converting part of a type’s mass. That is sensible when a large cohort can be targeted by share, but it is a genuine relaxation of decisions about individual people. It also depends on type being complete: if conversion prices or eligibility vary within a purported type, those attributes must be added to the type, potentially increasing \(\tau\) until the high-multiplicity advantage disappears. In the regime where many voters really do share those relevant attributes, the underlying question remains the authors’ question—what is the least campaign cost to change ballots so \(p\) wins—while the continuum makes the population itself the object being optimized.