Manipulation of Nanson's and Baldwin's Rules

Authors

  • Nina Narodytska University of New South Wales and NICTA
  • Toby Walsh University of New South Wales and NICTA
  • Lirong Xia Duke University

Abstract

Nanson's and Baldwin's voting rules selecta winner by successively eliminatingcandidates with low Borda scores. We showthat these rules have a number of desirablecomputational properties. In particular,with unweighted votes, it isNP-hard to manipulate either rule with one manipulator, whilstwith weighted votes, it isNP-hard to manipulate either rule with a small number ofcandidates and a coalition of manipulators.As only a couple of other voting rulesare known to be NP-hard to manipulatewith a single manipulator, Nanson'sand Baldwin's rules appearto be particularly resistant to manipulation from a theoretical perspective.We also propose a number of approximation methodsfor manipulating these two rules.Experiments demonstrate that both rules areoften difficult to manipulate in practice.These results suggest that elimination stylevoting rules deserve further study.

Downloads

Published

2011-08-04

How to Cite

Narodytska, N., Walsh, T., & Xia, L. (2011). Manipulation of Nanson’s and Baldwin’s Rules. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 713-718. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7872

Issue

Section

AAAI Technical Track: Multiagent Systems