Proceedings

Coalitional Voting Manipulation: A Game-Theoretic Perspective

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 49-53.

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

© 2011 International Joint Conferences on Artificial Intelligence

Abstract

Computational social choice literature has successfully studied the complexity of manipulation in variousvoting systems. However, the existing modelsof coalitional manipulation view the manipulatingcoalition as an exogenous input, ignoring thequestion of the coalition formation process. While such analysis is useful as a first approximation, a richer framework is required to model voting manipulationin the real world more accurately, and, inparticular, to explain how a manipulating coalitionarises and chooses its action. In this paper, we apply tools from cooperative game theory to developa model that considers the coalition formation processand determines which coalitions are likely toform and what actions they are likely to take. We explore the computational complexity of several standard coalitional game theory solution concepts in our setting, and study the relationship betweenour model and the classic coalitional manipulation problem as well as the now-standard bribery model.

  1. [Conitzer et al., 2007] V. Conitzer, T. Sandholm, and J. Lang. When are elections with few candidates hard to manipulate? Journal of the ACM, 54(3):Article 14, 2007.
  2. [Desmedt and Elkind, 2010] Y. Desmedt and E. Elkind. Equilibria of plurality voting with abstentions. In Proceed- ings of EC-10, pages 347-356, June 2010.
  3. [Elkind et al., 2009] E. Elkind, L. Goldberg, P. Goldberg, and M. Wooldridge. On the computational complexity of weighted voting games. Annals of Mathematics and Arti- ficial Intelligence, 56(2):109-131, 2009.
  4. [Faliszewski and Procaccia, 2010] P. Faliszewski and A. Procaccia. AI's war on manipulation: Are we winning? AI Magazine, 31(4):53-64, 2010.
  5. [Faliszewski et al., 2009] P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra. How hard is bribery in elections? Journal of AI Research, 35:485-532, 2009.
  6. [Faliszewski et al., 2010] P. Faliszewski, E. Hemaspaandra, and H. Schnoor. Manipulation of Copeland elections. In Proceedings of AAMAS-10, pages 367-374, May 2010.
  7. [Gibbard, 1973] A. Gibbard. Manipulation of voting schemes. Econometrica, 41(4):587-601, 1973.
  8. [Hazon and Elkind, 2010] N. Hazon and E. Elkind. Com- plexity of safe strategic voting. In Proceedings of SAGT- 10, pages 210-221, 2010.
  9. [Hemaspaandra and Hemaspaandra, 2007] E. Hemaspaan- dra and L. Hemaspaandra. Dichotomy for voting systems. Journal of Computer and System Sciences, 73(1):73-83, 2007.
  10. [Meir et al., 2010] R. Meir, M. Polukarov, J. Rosenschein, and N. Jennings. Convergence to equilibria in plurality voting. In Proceedings of AAAI-10, pages 823-828, July 2010.
  11. [Satterthwaite, 1975] M. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare func- tions. Journal of Economic Theory, 10(2):187-217, 1975.
  12. [Slinko and White, 2008] A. Slinko and S. White. Non- dictatorial social choice rules are safely manipulable. In Proceedings of COMSOC-08, pages 403-414, 2008.
  13. [Walsh, 2009] T. Walsh. Where are the really hard manipu- lation problems? The phase transition in manipulating the Veto rule. In Proceedings of IJCAI-09, pages 324-329, July 2009. IJCAI
  14. [Xia and Conitzer, 2010] L. Xia and V. Conitzer. Stackelberg voting games: Computational aspects and paradoxes. In Proceedings of AAAI-10, pages 921-926, July 2010.
  15. [Xia et al., 2009] L. Xia, V. Conitzer, A. Procaccia, and J. Rosenschein. Complexity of unweighted manipula- tion under some common voting rules. In Proceedings of IJCAI-09, pages 348-353, July 2009.
  16. [Xia et al., 2010] L. Xia, V. Conitzer, and A. Procaccia. A scheduling approach to coalitional manipulation. In Pro- ceedings of EC-10, pages 275-284, June 2010.

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

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