Computational complexity characterization of protecting elections from bribery

Lin Chen, Ahmed Imtiaz Sunny, Lei Xu, Shouhuai Xu, Zhimin Gao, Yang Lu, Weidong Shi, Nolan Shah

Research output: Contribution to journalArticlepeer-review

Abstract

The bribery problem in election has received considerable attention in the literature, upon which various algorithmic and complexity results have been obtained. In this setting, it is natural to ask whether we can protect an election from potential bribery attacks. We consider a scenario where the protector (or defender) can protect a voter at some cost such that a protected voter cannot be bribed (e.g., by isolating the voter from potential bribers). This leads to the following bi-level decision problem: Is it possible for the protector to protect a proper subset of voters such that no briber with a fixed budget for bribery can alter the election result? The goal of this paper is to give a full characterization of the complexity of the associated protection problems. We conduct an extensive study on the protection problem and provide algorithmic and complexity results. When compared with the bribery problems that have been studied in the literature, we observe that the protection problem we study is significantly harder in general. Indeed, it becomes Σ2p-complete even for very restricted special cases, while most bribery problems lie in NP. However, it is not necessarily the case that the protection problem is always harder. Some of the protection problems can still be solved in polynomial time, while some of them remain as hard as the bribery problem with the same setting.

Original languageEnglish
Pages (from-to)189-209
Number of pages21
JournalTheoretical Computer Science
Volume891
DOIs
StatePublished - Nov 4 2021

Keywords

  • Complexity
  • NP-hardness
  • Voting
  • Σ-hardness

Fingerprint

Dive into the research topics of 'Computational complexity characterization of protecting elections from bribery'. Together they form a unique fingerprint.

Cite this