Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Local distance restricted bribery in voting
Dey P.  AAMAS 2019 (Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, Montreal, QC, Canada, May 13-17, 2019)1925-1927.2019.Type:Proceedings
Date Reviewed: Jul 6 2020

The bribery problem asks whether there exists an appropriate-“cost” collection of voters in an election such that, if one strategically changes their votes, one’s favored candidate will win. In that model, each voter comes with a “bribery cost” that, if paid, will allow one to completely control the voter’s vote. However, even the paper that initiated the complexity-theoretic study of bribery [1] already realized that not all replacement votes might be equally palatable to the bribed voters. And so it also defined and studied a variant, called microbribery, in which one paid based on how far from the voter’s initial vote the voter was being bribed to. Later papers explored using many other distance notions to define the cost of bribery.

The paper under review, however, studies a case where there separately are costs on the voters, but also each voter has a (or in some cases, all share the same) maximum distance that the voter can be bribed. Within that distance, all votes that the voter might be bribed to are priced the same as each other; beyond it, their cost becomes infinite. Within this setting, the paper proves polynomial-time and NP-completeness results over a range of different election systems and distance notions, often focusing particularly on the case where the maximum distance is set to be one or two.

This interesting paper’s natural audience is the computational social choice community.

Reviewer:  Lane A. Hemaspaandra Review #: CR147009 (2011-0274)
1) Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. How hard is bribery in elections? Journal of Artificial Intelligence Research 35, (2009), 485-532.
Bookmark and Share
  Reviewer Selected
 
 
Multiagent Systems (I.2.11 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Multiagent Systems": Date
Engineering intelligent hybrid multi-agent systems
Khosla R., Dillon T. (ed), Kluwer Academic Publishers, Norwell, MA, 1998. Type: Book (9780792399827)
Aug 1 1998
Linguistic geometry: from search to construction
Stilman B., Kluwer Academic Publishers, Norwell, MA, 2000.  395, Type: Book (9780792377382)
Jan 1 2001
 Transactional agents: towards a robust multi-agent system
Nagi K., Springer-Verlag New York, Inc., New York, NY, 2002.  205, Type: Book (9783540430469)
Apr 13 2004
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy