Schulze and Ranked-Pairs Voting are Fixed-Parameter Tractable to Bribe, Manipulate, and Control
| Autor: | Curtis Menton, Rahman Lavaee, Lane A. Hemaspaandra |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
FOS: Computer and information sciences
Ranked pairs Theoretical computer science Computer science media_common.quotation_subject Schulze method Complex system 0102 computer and information sciences 02 engineering and technology 01 natural sciences I.2.11 F.2.2 Artificial Intelligence Computer Science - Computer Science and Game Theory Voting Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) Computer Science - Multiagent Systems Control (linguistics) media_common Applied Mathematics 010201 computation theory & mathematics Computational social choice 020201 artificial intelligence & image processing Computer Science and Game Theory (cs.GT) Multiagent Systems (cs.MA) |
| Zdroj: | Scopus-Elsevier |
| Popis: | 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 running times' degrees do not depend on the number of candidates. We also provide such algorithms for some weighted variants of these problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|