Election with Bribe-Effect Uncertainty: A Dichotomy Result

<jats:p>We consider the electoral bribery problem in computational social choice. In this context, extensive studies have been carried out to analyze the computational vulnerability of various voting (or election) rules. However, essentially all prior studies assume a deterministic model where each voter has an associated threshold value, which is used as follows. A voter will take a bribe and vote according to the attacker's (i.e., briber's) preference when the amount of the bribe is above the threshold, and a voter will not take a bribe when the amount of the bribe is not above the threshold (in this case, the voter will vote according to its own preference, rather than the attacker's). In this paper, we initiate the study of a more realistic model where each voter is associated with a  willingness function, rather than a fixed threshold value. The willingness function characterizes the  likelihood a bribed voter would vote according to the attacker's preference; we call this bribe-