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

Haris Aziz, Serge Gaspers, Nicholas Mattei, Nina Narodytska, Toby Walsh

AAAI 2013 pp. 74-80

doi:10.1609/AAAI.V27I1.8701 /aaai/2013/aziz2013aaai-ties/

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.

PDF AAAI Semantic Scholar

Cite

Text

Aziz et al. "Ties Matter: Complexity of Manipulation When Tie-Breaking with a Random Vote." AAAI Conference on Artificial Intelligence, 2013. doi:10.1609/AAAI.V27I1.8701

Markdown

[Aziz et al. "Ties Matter: Complexity of Manipulation When Tie-Breaking with a Random Vote." AAAI Conference on Artificial Intelligence, 2013.](https://mlanthology.org/aaai/2013/aziz2013aaai-ties/) doi:10.1609/AAAI.V27I1.8701

BibTeX

@inproceedings{aziz2013aaai-ties,
  title     = {{Ties Matter: Complexity of Manipulation When Tie-Breaking with a Random Vote}},
  author    = {Aziz, Haris and Gaspers, Serge and Mattei, Nicholas and Narodytska, Nina and Walsh, Toby},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2013},
  pages     = {74-80},
  doi       = {10.1609/AAAI.V27I1.8701},
  url       = {https://mlanthology.org/aaai/2013/aziz2013aaai-ties/}
}