Document Open Access Logo

Structural Control in Weighted Voting Games

Authors Anja Rey, Jörg Rothe

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.80.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Author Details

Anja Rey
Jörg Rothe

Cite AsGet BibTex

Anja Rey and Jörg Rothe. Structural Control in Weighted Voting Games. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 80:1-80:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.80

Abstract

Inspired by the study of control scenarios in elections and complementing manipulation and bribery settings in cooperative games with transferable utility, we introduce the notion of structural control in weighted voting games. We model two types of influence, adding players to and deleting players from a game, with goals such as increasing a given player's Shapley-Shubik or probabilistic Penrose-Banzhaf index in relation to the original game. We study the computational complexity of the problems of whether such structural changes can achieve the desired effect.
Keywords
  • algorithmic games theory
  • weighted voting games
  • structural control
  • power indices
  • computational complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. H. Aziz, Y. Bachrach, E. Elkind, and M. Paterson. False-name manipulations in weighted voting games. Journal of Artificial Intelligence Research, 40:57-93, 2011. Google Scholar
  2. Y. Bachrach and E. Elkind. Divide and conquer: False-name manipulations in weighted voting games. In Proc. AAMAS'08, pages 975-982. IFAAMAS, 2008. Google Scholar
  3. Y. Bachrach and E. Porat. Path disruption games. In Proc. AAMAS'10, pages 1123-1130. IFAAMAS, 2010. Google Scholar
  4. J. Banzhaf III. Weighted voting doesn't work: A mathematical analysis. Rutgers Law Review, 19:317-343, 1965. Google Scholar
  5. J. Bartholdi III, C. Tovey, and M. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3):227-241, 1989. Google Scholar
  6. J. Bartholdi III, C. Tovey, and M. Trick. How hard is it to control an election? Mathematical Computer Modelling, 16(8/9):27-40, 1992. Google Scholar
  7. D. Baumeister, G. Erdélyi, O. Erdélyi, and J. Rothe. Control in judgment aggregation. In Proc. STAIRS'12, pages 23-34. IOS Press, 2012. Google Scholar
  8. D. Baumeister, G. Erdélyi, O. Erdélyi, and J. Rothe. Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules. Mathematical Social Sciences, 76:19-30, 2015. Google Scholar
  9. D. Baumeister, G. Erdélyi, and J. Rothe. Judgment aggregation. In J. Rothe, editor, Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, chapter 6, pages 361-391. Springer-Verlag, 2015. Google Scholar
  10. D. Baumeister and J. Rothe. Preference aggregation by voting. In J. Rothe, editor, Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, chapter 4, pages 197-325. Springer-Verlag, 2015. Google Scholar
  11. R. Beigel, L. Hemachandra, and G. Wechsung. On the power of probabilistic polynomial time: P^NP[log] ⊆ PP. In Proc. Structures'89, pages 225-227. IEEE Computer Society Press, 1989. Google Scholar
  12. F. Brandt, V. Conitzer, and U. Endriss. Computational social choice. In G. Weiß, editor, Multiagent Systems, pages 213-283. MIT Press, second edition, 2013. Google Scholar
  13. F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016. Google Scholar
  14. G. Chalkiadakis, E. Elkind, and M. Wooldridge. Computational Aspects of Cooperative Game Theory. Morgan &Claypool, 2011. Google Scholar
  15. V. Conitzer and T. Walsh. Barriers to manipulation in voting. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors, Handbook of Computational Social Choice, chapter 6, pages 127-145. Cambridge University Press, 2016. Google Scholar
  16. X. Deng and C. Papadimitriou. On the complexity of comparative solution concepts. Mathematics of Operations Research, 19(2):257-266, 1994. Google Scholar
  17. P. Dubey and L. Shapley. Mathematical properties of the Banzhaf power index. Mathematics of Operations Research, 4(2):99-131, 1979. Google Scholar
  18. E. Elkind, D. Pasechnik, and Y. Zick. Dynamic weighted voting games. In Proc. AAMAS'13, pages 515-522. IFAAMAS, 2013. Google Scholar
  19. E. Elkind, T. Rahwan, and N. Jennings. Computational coalition formation. In G. Weiß, editor, Multiagent Systems, pages 329-380. MIT Press, second edition, 2013. Google Scholar
  20. E. Elkind and J. Rothe. Cooperative game theory. In J. Rothe, editor, Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, chapter 3, pages 135-193. Springer-Verlag, 2015. Google Scholar
  21. U. Endriss. Sincerity and manipulation under approval voting. Theory and Decision, 74(3):335-355, 2013. Google Scholar
  22. U. Endriss. Judgment aggregation. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors, Handbook of Computational Social Choice, chapter 17, pages 399-426. Cambridge University Press, 2016. Google Scholar
  23. U. Endriss, U. Grandi, and D. Porello. Complexity of judgment aggregation. Journal of Artificial Intelligence Research, 45:481-514, 2012. Google Scholar
  24. P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra. How hard is bribery in elections? Journal of Artificial Intelligence Research, 35:485-532, 2009. Google Scholar
  25. P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Llull and Copeland voting computationally resist bribery and constructive control. Journal of Artificial Intelligence Research, 35:275-341, 2009. Google Scholar
  26. P. Faliszewski and L. Hemaspaandra. The complexity of power-index comparison. Theoretical Computer Science, 410(1):101-107, 2009. Google Scholar
  27. P. Faliszewski and J. Rothe. Control and bribery in voting. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors, Handbook of Computational Social Choice, chapter 7, pages 146-168. Cambridge University Press, 2016. Google Scholar
  28. D. Felsenthal and M. Machover. Postulates and paradoxes of relative voting power - A critical re-appraisal. Theory and Decision, 38(2):195-229, 1995. Google Scholar
  29. L. Fortnow and N. Reingold. PP is closed under truth-table reductions. Information and Computation, 124(1):1-6, 1996. Google Scholar
  30. J. Freixas and M. Pons. Circumstantial power: Optimal persuadable voters. European Journal of Operational Research, 186:1114-1126, 2008. Google Scholar
  31. J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675-695, 1977. Google Scholar
  32. E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Anyone but him: The complexity of precluding an alternative. Artificial Intelligence, 171(5-6):255-285, 2007. Google Scholar
  33. R. Myerson. Conference structures and fair allocation rules. International Journal of Game Theory, 9(3):169-182, 1980. Google Scholar
  34. N. Nisan, T. Roughgarden, É. Tardos, and V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007. Google Scholar
  35. C. Papadimitriou. Computational Complexity. Addison-Wesley, second edition, 1995. Google Scholar
  36. B. Peleg and P. Sudhölter. Introduction to the Theory of Cooperative Games. Springer-Verlag, second edition, 2007. Google Scholar
  37. L. Penrose. The elementary statistics of majority voting. Journal of the Royal Statistical Society, 109(1):53-57, 1946. Google Scholar
  38. K. Prasad and J. Kelly. NP-completeness of some problems concerning voting games. International Journal of Game Theory, 19(1):1-9, 1990. Google Scholar
  39. T. Rahwan, T. Michalak, and M. Wooldridge. A measure of synergy in coalitions. Technical Report arXiv:1404.2954.v1 [cs.GT], CoRR, Apr. 2014. Google Scholar
  40. A. Rey and J. Rothe. False-name manipulation in weighted voting games is hard for probabilistic polynomial time. Journal of Artificial Intelligence Research, 50:573-601, 2014. Google Scholar
  41. A. Rey, J. Rothe, and A. Marple. Path-disruption games: Bribery and a probabilistic model. Theory of Computing Systems, 2016. URL: http://dx.doi.org/10.1007/s00224-016-9669-1.
  42. J. Rothe, editor. Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer-Verlag, 2015. Google Scholar
  43. L. Shapley and M. Shubik. A method of evaluating the distribution of power in a committee system. American Political Science Review, 48(3):787-792, 1954. Google Scholar
  44. Y. Shoham and K. Leyton-Brown. Multiagent Systems. Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009. Google Scholar
  45. S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865-877, 1991. Google Scholar
  46. Y. Zick. On random quotas and proportional representation in weighted voting games. In Proc. IJCAI'13, pages 432-438. AAAI Press, 2013. Google Scholar
  47. Y. Zick, A. Skopalik, and E. Elkind. The Shapley value as a function of the quota in weighted voting games. In Proc. IJCAI'11, pages 490-496. AAAI Press, 2011. Google Scholar
  48. M. Zuckerman, P. Faliszewski, Y. Bachrach, and E. Elkind. Manipulating the quota in weighted voting games. Artificial Intelligence, 180-181:1-19, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact