Generalized Distance Bribery

The bribery problem in elections asks whether an external agent can make some distinguished candidate win or prevent her from winning, by bribing some of the voters. This problem was studied with respect to the weighted swap distance between two votes by Elkind et al. (2009). We generalize this defi...

Full description

Saved in:
Bibliographic Details
Main Authors: Baumeister, Dorothea, Hogrebe, Tobias, Rey, Lisa
Format: Conference Proceeding
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The bribery problem in elections asks whether an external agent can make some distinguished candidate win or prevent her from winning, by bribing some of the voters. This problem was studied with respect to the weighted swap distance between two votes by Elkind et al. (2009). We generalize this definition by introducing a bound on the distance between the original and the bribed votes. The distance measures we consider include a restriction of the weighted swap distance and variants of the footrule distance, which capture some realworld models of influence an external agent may have on the voters. We study constructive and destructive variants of distance bribery for scoring rules and obtain polynomial-time algorithms as well as NP-hardness results. For the case of element-weighted swap and element-weighted footrule distances, we give a complete dichotomy result for the class of pure scoring rules.
ISSN:2159-5399
2374-3468
DOI:10.1609/aaai.v33i01.33011764