| paper | Campaign Management under Approval-Driven Voting Rules |
| authors | Ildikó Schlotter, Piotr Faliszewski, Edith Elkind |
| venue | AAAI 2011 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), even for arbitrary strict rankings. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 11
statement extracted from the paper’s text layer
Given candidates \(C\), an axis \(\triangleleft\), a finite set of single-peaked voter types \(t=(\succ_t,\ell_t)\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), and target \(p\), choose \(x_{t,k}\ge0\) with \(\sum_k x_{t,k}=\mu_t\) to minimize \(\sum_{t,k}|k-\ell_t|x_{t,k}\), subject to \(p\) being an SP-AV winner after the mass transfer; equivalently, decide whether a transfer of cost at most \(B\) exists.
High-multiplicity single-peaked SP-AV support bribery: types carry mass, each mass unit has an integral approval cutoff, \(x_{t,k}\) is transferred mass, and the objective is total cutoff-change cost \(\sum_{t,k}|k-\ell_t|x_{t,k}\).
The mirror covers the support-bribery hardness results in Theorems 9 and 11, including mass-bounded intervention and minimum-cost formulations; it leaves the shift-bribery results and the remaining parameterized, approximation, and destructive-bribery results unmirrored.
My lead anchor is Theorem 9. The paper proves it itself: both Fallback-support bribery and simplified Fallback-support bribery are NP-complete and W[2]-hard when parameterized by \(\alpha\), the maximum number of voters bribed in an optimal minimal bribery. This remains true when every cost is either \(0\) or \(+\infty\), and even when all cost functions are positive or all are negative. The proof reduces Dominating Set: choosing which voters to alter corresponds exactly to choosing vertices whose closed neighborhoods must cover the graph.
The natural mirror is Continuous Fallback Support Bribery. An instance contains candidates \(C\), a preferred candidate \(p\), and a finite set of voter types. A type \(t\) consists of a complete preference order \(\succ_t\), an integral approval cutoff \(\ell_t\in\{0,\ldots,|C|\}\), and a support-bribery cost function \(\sigma_t\). The society is a rational distribution \(\mu\) over these types. A mass-transfer action chooses \(x_{t,k}\ge 0\), where \(x_{t,k}\) is the mass of type \(t\) whose approval cutoff is changed from \(\ell_t\) to \(k\); thus \(\sum_k x_{t,k}=\mu_t\). The preference order is unchanged, exactly as in support bribery. Its cost is
\[ \sum_{t,k} \sigma_t(k-\ell_t)x_{t,k}. \]
For \(r\in\{1,\ldots,|C|\}\), define the \(r\)-round score of candidate \(c\) by
\[ S_r(c)=\sum_{t,k}x_{t,k}\mathbf{1}\!\left[\operatorname{rank}_{\succ_t}(c)\le r \ \land\ \operatorname{rank}_{\succ_t}(c)\le k\right]. \]
The question is: find a minimum-cost mass transfer after which \(p\) wins under Fallback, with strict majority interpreted as \(S_r(c)>1/2\). The simplified-Fallback version uses the paper’s simplified winner condition. The continuous analogue of \(\alpha\) is the mass touched,
\[ \alpha_\infty(x)=\sum_{t}\sum_{k\ne \ell_t}x_{t,k}. \]
One can therefore also ask for the minimum cost subject to \(\alpha_\infty(x)\le \rho\), where \(\rho\) is a permitted fraction of society to campaign toward.
This is a faithful mirror. The objects being changed are still approval counts, the preference orders remain complete and integral, and the campaign manager still pays for moving approval thresholds. Only the voter list has become a distribution. In the positive and negative cases of Theorem 9, the type costs are simply \(0\) or \(+\infty\), with only upward or only downward cutoff changes allowed.
The expected classification is Class A. For each possible Fallback winning round \(r\), the conditions that \(p\) wins in round \(r\), that no candidate wins earlier, and that \(p\) defeats the other candidates in that round are linear inequalities in the variables \(x_{t,k}\). The no-majority fallback case is another linear system. Enumerating the rounds gives finitely many linear programs. The mass cap \(\alpha_\infty(x)\le\rho\) is also linear. Thus the continuous problem is polynomial-time solvable in the explicit type representation, even though the discrete problem is W[2]-hard for the number of bribed voters.
The disappearance of hardness is meaningful rather than accidental. The Dominating Set reduction needs an indivisible choice of exactly \(k\) voters. In the mirror, a cohort can be split: a fraction of the mass of one type can be changed while the rest remains unchanged. The resulting covering constraints become fractional and are handled by the LP. The reduction’s combinatorics live partly in indivisible population units, so this is precisely the sort of hardness that continuization might dissolve.
The regime is a large electorate such as a national organization, platform-based political constituency, or professional membership whose voters fall into a moderate number of recurring preference-and-approval templates. A type includes the entire relevant description: preference order, cutoff, and cost schedule. Millions of voters may therefore be represented by hundreds or thousands of types. This is not claiming that every election is high-multiplicity; it identifies a concrete cohort regime in which the mirror is natural.
My second anchor is Theorem 11, also proved in this paper. It states that support bribery under single-peaked preferences is NP-hard and W[1]-hard with respect to \(\beta\), the total change in approval counts, for each of SP-AV, Fallback, and simplified Fallback, even when every cost function is the unit function \(\sigma_i(k)=|k|\). The reduction is from Multicolored Clique. Its construction forces the briber to select voters representing clique vertices and then use edge voters to repair the approval scores; a bribery of cost \(B\) exists exactly when the graph contains the required clique.
The corresponding question is Continuous Single-Peaked SP-AV Support Bribery. The instance consists of a candidate axis \(\triangleleft\), a finite collection of voter types \(t=(\succ_t,\ell_t)\) whose rankings are single-peaked with respect to that axis, a distribution \(\mu\), and a target \(p\). A unit of mass may change its approval cutoff from \(\ell_t\) to \(k\), at cost \(|k-\ell_t|\) per unit, while retaining \(\succ_t\). The task is to minimize total cost subject to \(p\) becoming an SP-AV winner:
\[ \sum_{t,k}x_{t,k}\mathbf{1}\!\left[ \operatorname{rank}_{\succ_t}(p)\le k \right] \ge \sum_{t,k}x_{t,k}\mathbf{1}\!\left[ \operatorname{rank}_{\succ_t}(c)\le k \right] \]
for every \(c\in C\).
The normalized counterpart of the paper’s parameter \(\beta\) is
\[ \beta_\infty(x)=\sum_{t,k}|k-\ell_t|x_{t,k}. \]
One can ask whether \(p\) can win with \(\beta_\infty(x)\le \bar\beta\), or optimize cost subject to that bound. This is again a linear program, so the expected classification is Class A. The same construction works for the two Fallback variants by replacing the SP-AV winner inequalities with the round-by-round inequalities above.
This second mirror is especially plausible because single-peaked electorates are a standard substantive model: many voters may share an ideological axis, preference template, and initial approval threshold. The continuous question does not discard the paper’s structural restriction or replace support bribery with a different operation. It asks what fraction of each ideological cohort should receive a campaign intervention.
The scope is deliberately limited to Theorems 9 and 11. I am not claiming that every result in the paper has been mirrored, nor that the paper’s shift-bribery algorithms need continuization. The positive claim is narrower: its central support-bribery hardness results generate well-defined high-multiplicity problems, and in the explicit finite-type model those problems become LPs.
The weakest point is that the paper’s reductions use graph-specific voters and candidates, so the reduction instances themselves do not represent a particularly convincing real electorate with \(\tau\ll N\). Moreover, allowing a cohort to split fractionally is a genuine relaxation of the discrete problem. But that is the intended high-multiplicity move, not a change of voting rule: each mass unit still receives an integral ballot, and only the population measure is continuous. The resulting questions remain recognizably the authors’ support-bribery problems, while providing a concrete test of whether their discrete hardness is caused by population indivisibility.
The strongest negative case is that the proponent’s reductions do not themselves describe high-multiplicity electorates. In Theorem 9, each voter \(x_i\) encodes the graph-specific neighborhood \(N[v_i]\); in Theorem 11, voters encode individual vertices and edges. Replicating these voters merely scales the instance. With divisible mass, the reductions become fractional domination or fractional clique-repair problems, so the paper’s combinatorial gadgets no longer survive.
Theorem 9 is also a weak anchor for a worthwhile optimization mirror. Its strongest hardness uses costs in \(\{0,+\infty\}\), so minimum cost collapses to a feasibility question. Replacing the objective by minimum touched mass, \(\alpha_\infty\), is natural but is no longer exactly the paper’s optimization problem. A more realistic repair—fixed campaign costs for targeting an entire type—would restore the discrete choice that causes the hardness, but would also reintroduce indivisible type-level decisions rather than continuize the population.
Theorem 11 is harder to dismiss. Its graph-specific vertex and edge types again do not yield a convincing moderate-type electorate, and \(\beta_\infty\) is not exactly the paper’s parameter \(\beta\): the latter is an instance parameter defined through optimal discrete briberies, whereas the proposed quantity is a budget imposed on a fractional action. Still, this is a technical qualification, not a fundamental obstruction. The natural fixed-budget version remains a faithful support-bribery problem.
Indeed, the proposed LPs retain complete integral rankings, integral approval cutoffs for every individual mass unit, the original support-bribery operation, and the paper’s winner rules. Approval scores and Fallback round conditions are linear after conditioning on the winning round. A society of repeated ideological or organizational cohorts with common rankings, cutoffs, and campaign prices is a credible high-multiplicity regime. Making the campaign action fractional is precisely the population continuization, not an outcome-space relaxation.
One could preserve the paper’s clique or dominating-set gadgets by requiring an entire type to be bribed together, or by adding fixed setup costs. But that would make the population effectively indivisible at the relevant decision level. It is therefore not a successful objection to the ordinary continuous mirror; it is evidence about which extra modelling assumptions restore hardness.
Consequently, I cannot honestly defeat both anchors. The first is a rather routine and possibly low-impact Class A mirror, but Theorem 11 supplies a valid continuous-population question, especially for SP-AV support bribery. The negative case can argue that the contribution may be modest, not that no worthwhile mirror exists in any scenario.
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.