  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
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.
