Article2006

The complexity of bribery in elections

Piotr Faliszewski · Edith Hemaspaandra · Lane A. Hemaspaandra

91 citations0/0 files stored

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Voting Systems Electoral Systems and Political Participation Internet Traffic Analysis and Secure E-voting

Abstract

We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by a certain amount of bribing voters a specified candidate can be made the election’s winner? We study this problem for election systems as varied as scoring protocols and Dodgson voting, and in a variety of settings regarding the nature of the voters, the size of the candidate set, and the specification of the input. We obtain both polynomial-time bribery algorithms and proofs of the intractability of bribery. Our results indicate that the complexity of bribery is extremely sensitive to the setting. For example, we find settings where bribing weighted voters is NP-complete in general but if weights are represented in unary then the bribery problem is in P. We provide a complete classification of the complexity of bribery for the broad class of elections (including plurality, Borda, k-approval, and veto) known as scoring protocols.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 91 citations exist upstream.

References

1951Social Choice and Individual Values.1975Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions 1989Voting schemes for which it can be difficult to tell who won the election 1989The computational difficulty of manipulating an election 1978A Consistent Extension of Condorcet’s Election Principle 1995Classics of Social Choice 1992How hard is it to control an election?2009How Hard Is Bribery in Elections?

Cited by

2010Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates 2011Multivariate Complexity Analysis of Swap Bribery 2009Sincere‐Strategy Preference‐Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.