Complexity of Shift Bribery in Iterative Elections

The strongest positive case is a continuous version of the paper’s constructive Hare problem. I would call it \( \textsc{Hare-Constructive-Shift-Bribery}_{\infty} \), and treat it as the lead mirror.

The relevant anchor is Theorem 3.1, proved in this paper by a reduction from the restricted version of Exact-Cover-by-3-Sets. The theorem states that Hare-Constructive-Shift-Bribery is NP-hard. More specifically, the reduction starts with \(X=\{x_1,\ldots,x_{3m}\}\) and \(3m\) three-element sets, with every \(x_j\) occurring in exactly three sets. It constructs candidates \(C=X\cup\mathcal S\cup\{p\}\), budget \(B=m\), and votes consisting of three votes associated with each set \(S_i\), four votes associated with each element \(x_i\), one vote \(S_i\,p\,\cdots\) for each set, and four votes beginning with \(p\). Initially every candidate has plurality score four. In the \(S_i\,p\,\cdots\) votes, moving \(p\) one position costs one, while every other shift costs \(B+1\). The theorem proves that \(p\) can be made the unique Hare winner within budget exactly when the X3C instance has an exact cover. Thus the named result is a hardness result proved here, not a result merely cited from elsewhere.

Here is the continuous mirror. An instance contains a finite candidate set \(C\), designated candidate \(p\), a finite set of voter types \(T\), rational masses \(\mu_t\) summing to one, and for each type \(t\) a complete ranking \(\pi_t\) together with a nondecreasing shift-price function \(\rho_t(k)\). The type therefore includes both the ballot and the cost schedule: agents of the same type are indistinguishable for this problem. A mass-transfer solution chooses numbers \(x_{t,k}\ge 0\), where \(x_{t,k}\) is the mass of type \(t\) shifted upward by exactly \(k\) positions, with \(\sum_k x_{t,k}=\mu_t\). The resulting society is the distribution of the transformed rankings. Its cost is \(\sum_{t,k}\rho_t(k)x_{t,k}\).

The decision question is:

Given \(b\in\mathbb Q_{\ge 0}\), is there a mass transfer \(x\) of cost at most \(b\) such that \(p\) is the unique winner under Hare’s iterative plurality rule?

Hare is applied exactly as in the paper, except that scores are masses rather than integer vote counts. In each round, a candidate’s score is the mass whose highest-ranked remaining candidate is that candidate; every candidate with minimum score is eliminated simultaneously; rankings are restricted to the survivors; and the process continues until \(p\) is the sole remaining candidate. Equivalently, one may ask for the minimum cost of such a transfer. If a finite election has \(N\) voters, then \(\mu_t=n_t/N\) and the normalized budget is \(b=B/N\), so this is genuinely the high-multiplicity relaxation of the paper’s problem.

This is a plausible regime rather than a formal re-description of the paper’s finite instances. Consider a national party, union, university, or professional election with a very large electorate. Many voters may share the same complete ranking and the same campaign-response schedule because they belong to the same constituency, demographic cohort, membership bloc, or standardized campaigning channel. The number of people \(N\) may be hundreds of thousands while the number of ballot-and-price types \(\tau\) is only hundreds or thousands. Mass is then the honest quantity: the attacker is deciding what fraction of each bloc to persuade, not which named individual to approach.

The authors should recognize this as their problem. The candidates remain discrete, rankings remain complete and integral, the action is still only shifting \(p\) forward, the costs are still their shift-price functions, and the iterative Hare rule is unchanged. Only the electorate is made continuous. This is not outcome-space continuity, a stochastic noise model, or a continuous-time process. Nor is it already what the paper studies: its profile is an integer list of votes, whereas the mirror permits fractional mass transfers and fractional scores.

My tentative classification is Class B: I expect hardness to transfer, although Theorem 3.1 itself does not establish that. The X3C structure in the proof lives mainly in the candidate set \(X\cup\mathcal S\) and in the incidence pattern of rankings. It is not fundamentally a consequence of having many individually named voters. That is exactly the kind of combinatorics that should survive continuization. At the same time, the continuous model gives a genuine algorithmic foothold: once an elimination sequence is fixed, all score conditions and budget constraints are linear in the variables \(x_{t,k}\), so each proposed sequence can be checked by linear programming. The open issue is whether the exponentially many possible elimination histories can be handled globally.

The main weakness is serious. Fractional mass can exploit the discontinuity of simultaneous elimination. In the discrete reduction, shifting one entire \(S_i\,p\,\cdots\) vote lowers \(S_i\)'s plurality score from four to three. In the continuous mirror, shifting an arbitrarily small positive mass of that type can lower its score below the tie level at an arbitrarily small proportional cost. That may activate an elimination cascade without paying the unit cost used in the reduction, potentially destroying the exact-cover equivalence. This is not a cosmetic technicality; it is the central proof obligation for any claimed hardness transfer.

That weakness is also a productive research question. One should ask whether the general continuous problem remains NP-hard under rational mass gaps, whether a margin-stable version restores the reduction, and whether the unrestricted exact-score version is instead tractable or hard for a continuum-specific reason. Parameterized variants in the number of candidates, number of types, or possible elimination rounds would also be natural.

I would therefore make only this one emphatic claim: \( \textsc{Hare-Constructive-Shift-Bribery}_{\infty} \) is a precise, recognizable, and worthwhile continuous mirror of Theorem 3.1. The paper’s discrete hardness does not make the mirror pointless; it creates the right question—whether candidate-level exact-cover structure survives fractional population mass.