Back to Search
Start Over
New Complexity Results on Coalitional Manipulation of Borda
- Publication Year :
- 2020
-
Abstract
- The Borda voting rule is a positional scoring rule for $z$ candidates such that in each vote, the first candidate receives $z-1$ points, the second $z-2$ points and so on. The winner in the Borda rule is the candidate with highest total score. We study the manipulation problem of the Borda rule in a setting with two non-manipulators while one of the non-manipulator's vote is weighted. We demonstrate a sharp contrast on computational complexity depending on the weight of the non-manipulator: the problem is NP-hard when the weight is larger than $1$ while there exists an efficient algorithm to find a manipulation when the weight is at most $1$.<br />Comment: 15 pages, 2 figures, 1 table
- Subjects :
- Computer Science - Computer Science and Game Theory
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2010.03372
- Document Type :
- Working Paper