Affordable Access

Publisher Website

Algorithms for the coalitional manipulation problem

Authors
Journal
Artificial Intelligence
0004-3702
Publisher
Elsevier
Publication Date
Volume
173
Issue
2
Identifiers
DOI: 10.1016/j.artint.2008.11.005
Keywords
  • Computational Social Choice
  • Voting
  • Manipulation
  • Computational Complexity
Disciplines
  • Computer Science

Abstract

Abstract We investigate the problem of coalitional manipulation in elections, which is known to be hard in a variety of voting rules. We put forward efficient algorithms for the problem in Borda, Maximin and Plurality with Runoff, and analyze their windows of error. Specifically, given an instance on which an algorithm fails, we bound the additional power the manipulators need in order to succeed. We finally discuss the implications of our results with respect to the popular approach of employing computational hardness to preclude manipulation.

There are no comments yet on this publication. Be the first to share your thoughts.