Targeted Negative Campaigning: Complexity and Approximations

Avishai Zagoury, Orgad Keller, Avinatan Hassidim, Noam HazonAAAI 2021 · OpenReview

Abstract

Given the ubiquity of negative campaigning in recent political elections, we find it important to study its properties from a computational perspective. To this end, we present a model where elections can be manipulated by convincing voters to demote specific non-favored candidates, and study its properties in the classic setting of scoring rules. When the goal is constructive (making a preferred candidate win), we prove that finding such a demotion strategy is easy for Plurality and Veto, while generally hard for $t$-approval and Borda. We also provide a $t$-factor approximation for $t$-approval for every fixed $t$, and a 3-factor approximation algorithm for Borda. Interestingly enough - following recent trends in political science that show that the effectiveness of negative campaigning depends on the type of candidate and demographic - when assigning varying prices to different possible demotion operations, we are able to provide inapproximability results. When the goal is destructive (making the leading opponent lose), we show that the problem is easy for a broad class of scoring rules.

Introduction

In traditional computational social choice, researchers often study "bribery"—how much it costs to change an election outcome by convincing voters to move a preferred candidate to the top of their list. However, modern political science shows that real-world campaigns are increasingly negative. Instead of saying "Vote for me," campaigns often use targeted ads to say "Don't vote for that person."

This paper identifies a gap in existing models: while Shift Bribery allows for the promotion of a single preferred candidate and Swap Bribery is often too granular, neither captures the "global" effect of a smear campaign. The authors introduce the Targeted Negative Campaigning (TNC) model, which reflects the "negativity bias" in psychology—the idea that it is often cheaper and more effective to lower a voter's opinion of an opponent than to raise their opinion of your own candidate.

The TNC Model

The authors formalize TNC as an optimization problem: find the minimum-cost sequence of "demotion operations" (moving a candidate down $\delta$ positions in a voter's preference list) to achieve a specific goal. They analyze two variants:

  1. Constructive TNC: Make a preferred candidate $p$ win.
  2. Destructive TNC: Make the current leader $d$ lose.

In this model, demoting a candidate by multiple positions can cost the same as demoting them by one, modeling a single advertisement's impact. This creates unique mathematical properties that distinguish TNC from standard swap-based bribery models.

Complexity and Approximation Results

The complexity landscape of TNC reveals that the difficulty of manipulation depends heavily on the voting rule and the campaign's objective.

Constructive TNC

  • Plurality and Veto: Solvable in polynomial time (P).
  • $t$-approval: NP-hard for $t \ge 3$. The authors provide a $t$-factor approximation algorithm for fixed $t$.
  • Borda Count: NP-hard. The authors provide a 3-approximation algorithm for the unpriced model. If prices depend on both the voter and the candidate, Borda-TNC cannot be approximated within a logarithmic factor unless P=NP.

Destructive TNC

Making a leader lose is computationally "easy" (in P) for almost all common scoring rules, including Plurality, Veto, Borda, and $t$-approval. This is because the campaign manager doesn't care who beats the leader, providing more degrees of freedom for optimization. The authors solve this by reducing the problem to a variant of the Knapsack problem called Group Fairness Knapsack (GFK).

Algorithmic Techniques

To address the NP-hard cases, the authors employ several algorithmic strategies. For $t$-approval voting, they construct priced flow networks to find approximate solutions. This approach models the selection of candidates to demote while respecting the constraints of the voting rule.

Flow network construction for analyzing demotion strategies in $t$-approval voting.

For the Borda count, the challenge lies in "side effects": demoting candidate A naturally promotes candidates B and C who were below them. The authors use a greedy approach on a simplified version of the problem, followed by a swapping procedure to mitigate these side effects, achieving a 3-approximation.

Conclusion and Future Work

This research establishes that while destructive negative campaigning is generally easy to optimize, constructive negative campaigning presents significant computational challenges under common voting rules like Borda and $t$-approval.

Future work may explore the complexity of $t$-approval for $t=2$, investigate non-scoring rules such as Copeland or Maximin, and incorporate social network influence to model how demotions spread through a population. As a theoretical study, these results are based on mathematical proofs and synthetic election instances rather than empirical datasets.

Summary updated

Abstract

Given the ubiquity of negative campaigning in recent political elections, we find it important to study its properties from a computational perspective. To this end, we present a model where elections can be manipulated by convincing voters to demote specific non-favored candidates, and study its properties in the classic setting of scoring rules. When the goal is constructive (making a preferred candidate win), we prove that finding such a demotion strategy is easy for Plurality and Veto, while generally hard for t-approval and Borda. We also provide a t-factor approximation for t-approval for every fixed t, and a 3-factor approximation algorithm for Borda. Interestingly enough - following recent trends in political science that show that the effectiveness of negative campaigning depends on the type of candidate and demographic - when assigning varying prices to different possible demotion operations, we are able to provide inapproximability results. When the goal is destructive (making the leading opponent lose), we show that the problem is easy for a broad class of scoring rules.
BibTeX
@inproceedings{zagoury2021targeted,
  author = {Avishai Zagoury and Orgad Keller and Avinatan Hassidim and Noam Hazon},
  title = {{Targeted Negative Campaigning: Complexity and Approximations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=-JW2OdkD7DJ},
}
Figure