How hard is it to control an election by breaking ties?

Por • 29 abr, 2013 • Sección: sociologia

Nicholas Mattei, Nina Narodytska, Toby Walsh

Abstract: We study the computational complexity of the problem of controlling the result of an election by breaking ties. When the chair is only asked to break ties to choose between one of the co-winners, the problem is trivially easy. However, in multi-round elections like STV, we prove that it can be NP-hard for the chair to compute how to break ties to ensure a given result. Our results contain several surprises. For example, whilst it is NP-hard to compute a manipulating vote for a multi-round rule like Nanson, it is polynomial for the chair to control the result by breaking ties. As a second example, it can be NP-hard to control an election by breaking ties even with a simple two-stage voting rule.

Xiv:1304.6174v1 [cs.AI]

Post to Twitter

Etiquetado con: , , , , , , , ,

Escribe un comentario