Ties Matter: Complexity of Manipulation when Tie-Breaking with a Random Vote

Authors

  • Haris Aziz NICTA and University of New South Wales
  • Serge Gaspers NICTA and University of New South Wales
  • Nicholas Mattei NICTA and University of New South Wales
  • Nina Narodytska NICTA and University of New South Wales
  • Toby Walsh NICTA and University of New South Wales

DOI:

https://doi.org/10.1609/aaai.v27i1.8701

Keywords:

voting, social choice, manipulation, strategic voting, tie-breaking

Abstract

We study the impact on strategic voting of tie-breaking by means of considering the order of tied candidates within a random vote. We compare this to another non deterministic tie-breaking rule where we simply choose candidate uniformly at random. In general, we demonstrate that there is no connection between the computational complexity of computing a manipulating vote with the two different types of tie-breaking. However, we prove that for some scoring rules, the computational complexity of computing a manipulation can increase from polynomial to NP-hard. We also discuss the relationship with the computational complexity of computing a manipulating vote when we ask for a candidate to be the unique winner, or to be among the set of co-winners.

AAAI 2013 Proceedings Cover

Downloads

Published

2013-06-30

How to Cite

Aziz, H., Gaspers, S., Mattei, N., Narodytska, N., & Walsh, T. (2013). Ties Matter: Complexity of Manipulation when Tie-Breaking with a Random Vote. Proceedings of the AAAI Conference on Artificial Intelligence, 27(1), 74-80. https://doi.org/10.1609/aaai.v27i1.8701

Issue

Vol. 27 No. 1 (2013): Twenty-Seventh AAAI Conference on Artificial Intelligence

Section

Main Technical Papers