Computational Complexity Characterization of Protecting Elections from Bribery

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

The bribery problem in election has received considerable attention in the literature, upon which various algorithmic and complexity results have been obtained. It is thus natural to ask whether we can protect an election from potential bribery. We assume that the protector can protect a voter with some cost (e.g., by isolating the voter from potential bribers). A protected voter cannot be bribed. Under this setting, we consider 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 on bribery can alter the election result? The goal of this paper is to give a full picture on the complexity of protection problems. We give an extensive study on the protection problem and provide algorithmic and complexity results. Comparing our results with that on the bribery problems, we observe that the protection problem is in general significantly harder. Indeed, it becomes 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 under the same setting.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings
EditorsDonghyun Kim, R.N. Uma, Zhipeng Cai, Dong Hoon Lee
PublisherSpringer Science and Business Media Deutschland GmbH
Pages85-97
Number of pages13
ISBN (Print)9783030581497
DOIs
StatePublished - 2020
Event26th International Conference on Computing and Combinatorics, COCOON 2020 - Atlanta, United States
Duration: Aug 29 2020Aug 31 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12273 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on Computing and Combinatorics, COCOON 2020
CountryUnited States
CityAtlanta
Period08/29/2008/31/20

Keywords

  • Complexity
  • Hardness
  • NP-hardness
  • Voting

Fingerprint Dive into the research topics of 'Computational Complexity Characterization of Protecting Elections from Bribery'. Together they form a unique fingerprint.

Cite this