AAAI Publications, Workshops at the Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
Manipulation and Bribery in Preference Reasoning under Pareto Principle
Ying Zhu, Miroslaw Truszczynski

Last modified: 2014-06-18


Manipulation and bribery have received much attention from the social choice community. We consider these concepts in the setting of preference formalisms, where the Pareto principle is used to assign to preference theories collections of optimal outcomes, rather than a single winning outcome as is common in social choice. We adapt the concepts of manipulation and bribery to this setting. We provide characterizations of situations when manipulation and bribery are possible. Assuming a particular logical formalism for expressing preferences, we establish the complexity of determining a possibility for manipulation or bribery. In all cases that do not in principle preclude a possibility of manipulation or bribery, our complexity results show that deciding whether manipulation or bribery are actually possible is computationally hard.

Full Text: PDF