EUVIMEDEUVIMED entdecken
Crossref

Efficiently Negative: Complexity and Approximations of Targeted Negative Campaigning

Avishai Zagoury, Orgad Keller, Avinatan Hassidim, Noam Hazon

Journal of Artificial Intelligence Research · 08.07.2026 · 86

DOI: 10.1613/jair.1.21371 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 08.07.2026. Verfasst von Avishai Zagoury und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given the ubiquity of negative campaigning in recent political elections, we find it important to study its properties from a theoretical 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 min(t, m - t)-factor approximation for t-approval for every t ∈ {1,..., m - 1} (where m is the number of candidates), 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 and provide an FPTAS for the general case.

Zitieren

APA

Zagoury, A., Keller, O., Hassidim, A., & Hazon, N. (2026). Efficiently Negative: Complexity and Approximations of Targeted Negative Campaigning. Journal of Artificial Intelligence Research, 86. https://doi.org/10.1613/jair.1.21371

Vancouver

Zagoury A, Keller O, Hassidim A, Hazon N. Efficiently Negative: Complexity and Approximations of Targeted Negative Campaigning. Journal of Artificial Intelligence Research. 2026;86. doi:10.1613/jair.1.21371

BibTeX
@article{Zagoury2026,
  author = {Zagoury, Avishai and Keller, Orgad and Hassidim, Avinatan and Hazon, Noam},
  title = {Efficiently Negative: Complexity and Approximations of Targeted Negative Campaigning},
  journal = {Journal of Artificial Intelligence Research},
  year = {2026},
  volume = {86},
  doi = {10.1613/jair.1.21371}
}
Kostenlos starten →