2012/10/25 by Lane A. Hemaspaandra, Hemaspaandra, Lane A., Rahman Lavaee +3
Computer Science · Economics, Econometrics and Finance · Social Sciences · #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Electoral Systems and Political Participation #F.2.2 #FOS: Computer and information sciences #Game Theory and Voting Systems #I.2.11 #Internet Traffic Analysis and Secure E-voting #Multiagent Systems (cs.MA) #cs.DS #cs.GT #cs.MA
paper · pdf · doi:10.48550/arxiv.1210.6963
openalex publication_date 2012/10/25 · arxiv created 2014/06/21 · arxiv updated 2014/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Schulze and ranked-pairs elections have received much attention recently, and the former has quickly become a quite widely used election system. For many cases these systems have been proven resistant to bribery, control, or manipulation, with ranked pairs being particularly praised for being NP-hard for all three of those. Nonetheless, the present paper shows that with respect to the number of candidates, Schulze and ranked-pairs elections are fixed-parameter tractable to bribe, control, and manipulate: we obtain uniform, polynomial-time algorithms whose degree does not depend on the number of candidates. We also provide such algorithms for some weighted variants of these problems.