AAAI Publications, Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Bribery in Voting With Soft Constraints
Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable

Last modified: 2013-06-30

Abstract


We consider a multi-agent scenario where a collection of agents needs to select a common decision from a large set of decisions over which they express their preferences. This decision set has a combinatorial structure, that is, each decision is an element of the Cartesian product of the domains of some variables. Agents express their preferences over the decisions via soft constraints. We consider both sequential preference aggregation methods (they aggregate the preferences over one variable at a time) and one-step methods and we study the computational complexity of influencing them through bribery. We prove that bribery is NPcomplete for the sequential aggregation methods (based on Plurality, Approval, and Borda) for most of the cost schemes we defined, while it is polynomial for one-step Plurality.

Full Text: PDF