Proceedings

On the Complexity of Voting Manipulation under Randomized Tie-Breaking

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 319-323.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-063

© 2011 International Joint Conferences on Artificial Intelligence

Abstract

Computational complexity of voting manipulation is one of the most actively studied topics in the area of computational social choice, starting with the groundbreaking work of [Bartholdi et al., 1989]. Most of the existing work in this area, including that of [Bartholdi et al., 1989], implicitly assumes that whenever several candidates receive the top score with respect to the given voting rule, the resulting tie is broken according to a lexicographic ordering over the candidates. However, till recently, an equally appealing method of tiebreaking, namely, selecting the winner uniformly at random among all tied candidates, has not been considered in the computational social choice literature. The first paper to analyze the complexity of voting manipulation under randomized tiebreaking is [Obraztsova et al., 2011], where the authors provide polynomial-time algorithms for this problem under scoring rules and—under an additional assumption on the manipulator’s utilities—for Maximin. In this paper, we extend the results of [Obraztsova et al., 2011] by showing that finding an optimal vote under randomized tie-breaking is computationally hard for Copeland and Maximin (with general utilities), as well as for STV and Ranked Pairs, but easy for the Bucklin rule and Plurality with Runoff.

  1. [Bartholdi et al., 1989] J. J. Bartholdi, C. A. Tovey, and M. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6:227-241, 1989.
  2. [Conitzer et al., 2009] V. Conitzer, M. Rognlie, and L. Xia. Prefer- ence functions that score rankings and maximum likelihood esti- mation. In IJCAI'09, pp. 109-115, 2009. IJCAI
  3. [Desmedt and Elkind, 2010] Y. Desmedt and E. Elkind. Equilibria of plurality voting with abstentions. In ACM EC'10, pp. 347- 356, 2010.
  4. [Ephrati and Rosenschein, 1997] E. Ephrati and J. Rosenschein. A heuristic technique for multi-agent planning. Annals of Mathe- matics and Artificial Intelligence, 20(1-4):13-67, 1997.
  5. [Faliszewski et al., 2008] P. Faliszewski, E. Hemaspaandra, and H. Schnoor. Copeland voting: Ties matter. In AAMAS'08, pp. 983-990, 2008.
  6. [Faliszewski and Procaccia, 2010] P. Faliszewski and A. Procaccia. AI's war on manipulation: Are we winning? AI Magazine, 31(4):53-64, 2010.
  7. [Garey and Johnson, 1979] M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.
  8. [Gibbard, 1973] A. F. Gibbard. Manipulation of voting schemes: a general result. Econometrica, 41:597-601, 1973.
  9. [Gibbard, 1977] A. F. Gibbard. Manipulation of schemes that mix voting and chance. Econometrica, 45:665-681, 1977.
  10. [Hazon et al., 2008] N. Hazon, Y. Aumann, S. Kraus, M. Wooldridge. Evaluation of election outcomes under uncertainty. In AAMAS'08, pp. 959-966, 2008.
  11. [McGarvey, 1953] D. C. McGarvey. A theorem on the construction of voting paradoxes. Econometrica, 21(4):608-610, 1953.
  12. [Obraztsova et al., 2011] S. Obraztsova, E. Elkind, and N. Hazon. Ties matter: Complexity of voting manipulation revisited. In AAMAS'11, to appear. IJCAI
  13. [Satterthwaite, 1975] M. A. Satterthwaite. Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions. Journal of Eco- nomic Theory, 10:187-217, 1975.
  14. [Xia et al., 2009] L. Xia, M. Zuckerman, A. Procaccia, V. Conitzer, and J. Rosenschein. Complexity of unweighted manipulation un- der some common voting rules. In IJCAI'09, pp. 348-353, 2009.
  15. [Zuckerman et al., 2009] M. Zuckerman, A. Procaccia, and J. Rosenschein. Algorithms for the coalitional manipulation problem. Artificial Intelligence Journal, 173(2):392-412, 2009.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards