How Hard Is Bribery in Elections?

Simple item page
dc.creatorFaliszewski, Piotr
dc.creatorHemaspaandra, Edith
dc.creatorHemaspaandra, Lane A.
dc.date2006-08-19
dc.date2008-08-22
dc.date.accessioned2026-07-07T09:57:43Z
dc.date.available2026-07-07T09:57:43Z
dc.descriptionWe 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 homogeneous-vs.-nonhomogeneous electorate bribability, bounded-size-vs.-arbitrary-sized candidate sets, weighted-vs.-unweighted voters, and succinct-vs.-nonsuccinct input specification. We obtain both polynomial-time bribery algorithms and proofs of the intractability of bribery, and indeed our results show that the complexity of bribery is extremely sensitive to the setting. For example, we find settings in which bribery is NP-complete but manipulation (by voters) is in P, and we find settings in which bribing weighted voters is NP-complete but bribing voters with individual bribe thresholds is in P. For the broad class of elections (including plurality, Borda, k-approval, and veto) known as scoring protocols, we prove a dichotomy result for bribery of weighted voters: We find a simple-to-evaluate condition that classifies every case as either NP-complete or in P.
dc.descriptionEarlier version appears in Proc. of AAAI-06, pp. 641-646, 2006
dc.identifierhttps://arxiv.org/abs/cs/0608081
dc.identifierhttp://arxiv.org/abs/cs/0608081
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/167448
dc.subjectComputer Science and Game Theory
dc.subjectComputational Complexity
dc.subjectMultiagent Systems
dc.subjectI.2.11; F.2.2; F.1.3
dc.titleHow Hard Is Bribery in Elections?
dc.typetext

Files

Collections

arXiv