| paper | Complexity of Shift Bribery in Committee Elections |
| authors | Robert Bredereck, Piotr Faliszewski, R. Niedermeier, Nimrod Talmon |
| venue | AAAI 2016 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the decision and minimum-cost optimization problems are in \(\mathrm{P}\), and the decision problem is fixed-parameter tractable with parameter \(\tau\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given candidates \(C\), preferred candidate \(p\), finite voter types \(T\), where each \(t\in T\) consists of a complete ranking \(\rho_t\) and price function \(\pi_t\), and rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), choose masses \(x_{t,j}\ge 0\) for \(j=0,\ldots,\operatorname{pos}_{\rho_t}(p)-1\) satisfying \(\sum_j x_{t,j}=\mu_t\). Each mass \(x_{t,j}\) receives exactly \(j\) upward shifts of \(p\); decide whether the total cost \(\sum_{t,j}\pi_t(j)x_{t,j}\) is at most \(b\) and makes \(p\) a Borda winner, or compute the minimum cost.
A high-multiplicity Borda Shift Bribery model with ranking-and-price types \(t\), society mass \(\mu\), shift-allocation variables \(x_{t,j}\), additive objective \(\sum_{t,j}\pi_t(j)x_{t,j}\), and linear Borda-winning constraints.
The mirror does not provide a parameter-preserving continuation of the paper's \(n\)-parameterized \(\mathrm{W[1]}\)-hardness, since the reduction uses a small engineered electorate that need not contain repeated types.
fatal: False
The mirror covers Theorem 2's single-winner Borda Shift Bribery result and leaves the multiwinner \(k\)-Borda, Chamberlin–Courant, greedy, and other parameterized results unexamined.
My lead mirror is the paper’s Theorem 2, not one of the more complicated committee rules. The theorem states, and is proved in this paper by a parameterized reduction from Multicolored Independent Set, that Borda Shift Bribery is \(\mathrm{W[1]}\)-hard when parameterized by the number \(n\) of voters, even when every voter has the unit price function \(\pi_v(i)=i\). Here Borda is the single-winner rule: given an election, preferred candidate \(p\), voter-specific shift prices, and budget \(B\), one asks whether \(p\) can be made a Borda winner by shifting \(p\) forward in voters’ rankings within budget. The reduction makes the number of voters depend only on the parameter of Multicolored Independent Set. The paper then observes in Corollary 1 that the same hardness transfers to \(k\)-Borda Shift Bribery, but I do not rely on that extension as a separate anchor.
I would call the following problem \(\mathrm{Borda\text{-}ShiftBribery}_\infty\). An instance contains candidates \(C\), a preferred candidate \(p\), and a finite list \(T\) of voter types. A type \(t\in T\) is a complete ranking of \(C\), together with its shift-price function \(\pi_t\). The society is a rational distribution \(\mu\), where \(\mu_t\) is the fraction of the population of type \(t\) and \(\sum_{t\in T}\mu_t=1\). In the unit-price version, \(\pi_t(j)=j\) for every type.
For every type \(t\) and every integer \(j\) from \(0\) up to the position of \(p\) minus one, choose a variable \(x_{t,j}\). It represents the mass of type \(t\) whose members receive exactly \(j\) upward shifts of \(p\). Thus every individual still receives an integral number of ranking shifts; only the mass of people receiving each shift is fractional. The constraints are \(\sum_j x_{t,j}=\mu_t\) and \(x_{t,j}\ge 0\). Let \(\operatorname{shift}_j(t)\) be the ranking obtained from \(t\) after shifting \(p\) upward by \(j\) positions. The cost of the action is \(\sum_{t,j}\pi_t(j)x_{t,j}\). The question is whether there is such a mass-splitting shift action of cost at most a given per-capita budget \(b\) that makes \(p\) a Borda winner; equivalently, one can ask for the minimum possible cost.
This is recognisably the paper’s problem. The candidates, target \(p\), complete rankings, upward shifts, voter prices, budget objective, and nonunique-winner convention are unchanged. The only change is that the electorate is represented by its type distribution and the action is specified at mass level. It is not a noise model, a fractional outcome, or an arbitrary preference-change model.
The regime is a large electorate in which voters occur in repeated segments: for example, millions of constituents or customers whose complete rankings and campaign-response costs are identical. The number of people can be enormous while the number \(\tau=|T|\) of distinct ranking-and-price types is moderate. This is precisely a high-multiplicity version of the paper’s election. A discrete election with counts \(n_t\) gives \(\mu_t=n_t/n\); conversely, a rational mass action can be lifted to a finite election after multiplying by a common denominator. The continuous problem removes the artificial requirement that a type can be persuaded only in indivisible units of \(1/n\) of the population.
The expected classification is Class A. For each type and shift amount, the resulting Borda score is fixed, so the entire problem is the linear program
\(\min \sum_{t,j}\pi_t(j)x_{t,j}\)
subject to \(\sum_j x_{t,j}=\mu_t\), \(x_{t,j}\ge 0\), and, for every opponent \(c\neq p\),
\(\sum_{t,j}x_{t,j}\bigl(\beta_{\operatorname{shift}_j(t)}(p)-\beta_{\operatorname{shift}_j(t)}(c)\bigr)\ge 0\).
There are at most \(\tau m\) variables and polynomially many constraints, with rational coefficients of polynomial encoding length. Hence the exact optimum and the budgeted decision problem are solvable in time polynomial in \(m\), \(\tau\), and the input bit length. This remains true for arbitrary rational type-level price functions, not merely unit prices.
That gives the continuous programme a meaningful answer to the paper’s hardness result: the discrete \(\mathrm{W[1]}\)-hardness does not survive this mirror. The combinatorial difficulty exploited by Theorem 2 is tied to indivisible voter-level choices. Once the society is represented by masses, the campaign can distribute a type’s mass among the allowed integral shift amounts, and the Borda winning condition becomes linear. The result is not merely “the same election with probabilities”; it is a computationally different high-multiplicity problem with an exact optimization algorithm.
The weakest point is that this lead mirror concerns the paper’s single-winner Borda baseline rather than its most distinctive multiwinner rules. Moreover, fractional mass allocation is a genuine relaxation: a finite election may require whole voters to move, whereas the continuous problem may move \(0.37\) of a type by one position and \(0.63\) by two positions. I would not claim from this alone that the hardness of Theorem 3 for \(k\)-Borda, or Theorem 5 for Greedy-Approval-CC and Greedy-Borda-CC, disappears. Those are further questions. In particular, a natural next mirror is the same mass-action model with the requirement that \(p\) belong to a top-\(k\) Borda committee; its winning condition is no longer a single system of score inequalities, so the LP argument may fail and hardness might survive. Likewise, continuous Greedy-Approval-CC Shift Bribery would test whether the set-cover combinatorics in Theorem 5 survive fractional type masses.
That limitation is also why this is a credible positive case rather than an overclaim. It covers one named hardness result emphatically, gives the authors’ exact underlying problem in a sensible high-multiplicity regime, and shows a genuine Class A outcome: a discrete \(\mathrm{W[1]}\)-hard campaign problem becomes an explicit polynomial-time LP when the population, rather than the outcome or the uncertainty model, is continuized.
The negative case is weak here because the proponent’s anchor is a legitimate continuous-population problem, and it directly satisfies the programme’s scope.
Theorem 2 is a named computational result about Borda Shift Bribery: a preferred candidate is promoted in voters’ rankings at voter-specific prices, and the objective depends only on the resulting aggregate Borda scores. Nothing in that objective requires voter identity. A perfectly sensible high-multiplicity regime has large blocs of voters sharing both a ranking and a campaign-response cost. The relevant type is therefore exactly the pair \((\text{ranking},\text{price function})\), as the proponent specifies.
The proposed mass action is also not an illicit continuization of the outcome. Every unit of mass still receives an integral shift; only identical voters are divided into subpopulations receiving different shifts. For each type \(t\), the variables \(x_{t,j}\) describe a distribution over the finitely many permitted shifts. Since Borda scores and costs are additive, the resulting problem really is
\[ \min \sum_{t,j}\pi_t(j)x_{t,j} \]
subject to the type-mass constraints and the linear inequalities requiring \(p\) to score at least as highly as every opponent. This is a polynomial-size LP in \(\tau m\) variables. It is a genuine high-multiplicity relaxation of the paper’s problem, not a noise model, fractional outcome, or arbitrary preference-change problem.
The strongest available objection is narrower: Theorem 2’s stated parameter is the number \(n\) of voters, whereas the continuous problem has no voter count and is naturally parameterized by the number \(\tau\) of types. Moreover, the reduction proving \(\mathrm{W[1]}\)-hardness uses a small, highly engineered electorate whose voters need not occur with large multiplicity. Thus the proponent has not shown a parameter-preserving translation of that particular hardness theorem.
That objection does not defeat the mirror under ChoCo’s rules. The programme asks whether the underlying computational problem has a worthwhile high-multiplicity version, not whether the original reduction survives unchanged. The continuous LP gives exactly the sort of Class A result the programme seeks: a discrete campaign problem that is hard in its ordinary formulation becomes exactly solvable when a society is represented by masses. Saying that the hardness is really encoded in the candidates, or that the continuous answer is easier, would be an impermissible answer-based objection.
Nor can the mirror be rejected as unrealistic. Unit prices are already one of the paper’s explicit regimes, and electorates or customer populations with repeated preference-and-cost profiles are standard high-multiplicity instances. If identities or individualized prices matter, they can be included in the type; that may increase \(\tau\), but it does not invalidate the repeated-type regime.
The paper’s more distinctive multiwinner results may produce harder or more interesting mirrors, especially for \(k\)-Borda and the greedy Chamberlin–Courant variants. But the programme explicitly needs only one surviving mirror. Consequently, I cannot honestly defend the universal claim that this paper has no worthwhile continuous mirror. The only defensible negative qualification is that the proposed mirror is not a literal continuation of the \(\mathrm{W[1]}\)-parameterized statement; it is nevertheless a sound and computationally meaningful high-multiplicity mirror of the underlying Borda Shift Bribery problem.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.