TY - GEN
T1 - Protecting election from bribery
T2 - 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
AU - Chen, Lin
AU - Xu, Lei
AU - Xu, Shouhuai
AU - Gao, Zhimin
AU - Shah, Nolan
AU - Lu, Yang
AU - Shi, Weidong
N1 - Publisher Copyright:
© 2018 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
PY - 2018
Y1 - 2018
N2 - The bribery problem in elections has received a considerable amount of attention. In this paper, we initiate the study of a related, but new problem, the protection problem, namely protecting elections from bribery. In this problem, there is a defender who is given a defense budget and can use the budget to award some of the voters such that they cannot be bribed anymore. This naturally leads to the following bi-level decision problem: Is it possible for the defender with a given defense budget to protect an election from being manipulated by the attacker with a given attack budget for bribing voters? We characterize the computational complexity of the protection problem. We show that it is in general significantly harder than the bribery problem. However, the protection problem can be solved, under certain circumstances, in polynomial time.
AB - The bribery problem in elections has received a considerable amount of attention. In this paper, we initiate the study of a related, but new problem, the protection problem, namely protecting elections from bribery. In this problem, there is a defender who is given a defense budget and can use the budget to award some of the voters such that they cannot be bribed anymore. This naturally leads to the following bi-level decision problem: Is it possible for the defender with a given defense budget to protect an election from being manipulated by the attacker with a given attack budget for bribing voters? We characterize the computational complexity of the protection problem. We show that it is in general significantly harder than the bribery problem. However, the protection problem can be solved, under certain circumstances, in polynomial time.
KW - Bribery
KW - Complexity
KW - Voting
UR - http://www.scopus.com/inward/record.url?scp=85054718353&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85054718353
SN - 9781510868083
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 1894
EP - 1896
BT - 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Y2 - 10 July 2018 through 15 July 2018
ER -