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.
Acknowledgements:
We thank the anonymous BEJTE, MFCS’16, AAMAS’16, CoopMAS’16, and LOFT’16 reviewers for many helpful comments on earlier drafts of this paper. This work was supported in part by DFG grant RO-1202/14-2.
References
Aziz, H., Y. Bachrach, E. Elkind, and M. Paterson. 2011. “False-Name Manipulations in Weighted Voting Games.” Journal of Artificial Intelligence Research 40: 57–93.10.1613/jair.3166Search in Google Scholar
Bachrach, Y., and E. Elkind. 2008. “Divide and Conquer: False-Name Manipulations in Weighted Voting Games. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 975–982. IFAAMAS.Search in Google Scholar
Bachrach, Y., and E. Porat. 2010. “Path Disruption Games. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, pp. 1123–1130. IFAAMAS.Search in Google Scholar
Banzhaf III, J. 1965. “Weighted Voting Doesn’t Work: A Mathematical Analysis.” Rutgers Law Review 19: 317–343.Search in Google Scholar
Bartholdi III, J., C. Tovey, and M. Trick. 1989. “The Computational Difficulty of Manipulating an Election.” Social Choice and Welfare 6 (3): 227–241.10.1007/BF00295861Search in Google Scholar
Bartholdi III, J., C. Tovey, and M. Trick. 1992. “How Hard is it to Control an Election? Mathematical Computer Modelling 16 (8/9): 27–40.10.1016/0895-7177(92)90085-YSearch in Google Scholar
Baumeister, D., G. Erdélyi, O. Erdélyi, and J. Rothe. 2012. “Control in Judgment Aggregation. In Proceedings of the 6th European Starting AI Researcher Symposium, pp. 23–34. IOS Press.Search in Google Scholar
Baumeister, D., G. Erdélyi, O. Erdélyi, and J. Rothe. 2015a. “Complexity of Manipulation and Bribery in Judgment Aggregation for Uniform Premise-Based Quota Rules.” Mathematical Social Sciences 76: 19–30.10.1016/j.mathsocsci.2015.03.006Search in Google Scholar
Baumeister, D., G. Erdélyi, and J. Rothe. 2015b. “Judgment Aggregation, Chapter 6.” In Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, edited by J. Rothe, pp. 361–391. Springer-Verlag.10.1007/978-3-662-47904-9_6Search in Google Scholar
Baumeister, D. and J. Rothe. 2015. “Preference Aggregation by Voting, Chapter 4.” In Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, edited by J. Rothe, pp. 197–325. Springer-Verlag.10.1007/978-3-662-47904-9_4Search in Google Scholar
Beigel, R., L. Hemachandra, and G. Wechsung. 1989. “On the Power of Probabilistic Polynomial Time: PNP [log] ⊆ PP.” In Proceedings of the 4th Structure in Complexity Theory Conference, pp. 225–227. IEEE Computer Society Press.Search in Google Scholar
Brandt, F., V. Conitzer, and U. Endriss. 2013. “Computational Social Choice.” In Multiagent Systems, 2nd ed. edited by G. Weiß, pp. 213–283. MIT Press.Search in Google Scholar
Brandt, F., V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, eds. 2016. Handbook of Computational Social Choice. Cambridge University Press.10.1017/CBO9781107446984.002Search in Google Scholar
Chalkiadakis, G., E. Elkind, and M. Wooldridge. 2011. Computational Aspects of Cooperative Game Theory. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers.10.2200/S00355ED1V01Y201107AIM016Search in Google Scholar
Conitzer, V., and T. Walsh. 2016. “Barriers to Manipulation in Voting, Chapter 6.” In Handbook of Computational Social Choice edited by F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, pp. 127–145. Cambridge University Press.10.1017/CBO9781107446984Search in Google Scholar
Deng, X., and C. Papadimitriou. 1994. “On the Complexity of Comparative Solution Concepts.” Mathematics of Operations Research 19 (2): 257–266.10.1287/moor.19.2.257Search in Google Scholar
Dubey, P., and L. Shapley. 1979. “Mathematical Properties of the Banzhaf Power Index.” Mathematics of Operations Research 4 (2): 99–131.10.1287/moor.4.2.99Search in Google Scholar
Elkind, E., D. Pasechnik, and Y. Zick. 2013a. “Dynamic Weighted Voting Games.” In Proceedings of the 12th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 515–522. IFAAMAS.Search in Google Scholar
Elkind, E., T. Rahwan, and N. Jennings. 2013b. “Computational Coalition Formation.” In Multiagent Systems, 2nd ed. edityed by G. Weiß, pp. 329–380. MIT Press.Search in Google Scholar
Elkind, E., and J. Rothe. 2015. “Cooperative Game Theory, Chapter 3.” In Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, edited by J. Rothe, pp. 135–193. Springer-Verlag.10.1007/978-3-662-47904-9_3Search in Google Scholar
Endriss, U. 2013. “Sincerity and Manipulation Under Approval Voting.” Theory and Decision 74 (3): 335–355.10.1007/s11238-012-9301-zSearch in Google Scholar
Endriss, U. 2016. “Judgment Aggregation, Chapter 17.” In Handbook of Computational Social Choice edited by F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, pp. 399–426. Cambridge University Press.10.1017/CBO9781107446984.018Search in Google Scholar
Endriss, U., U. Grandi, and D. Porello. 2012. “Complexity of Judgment Aggregation.” Journal of Artificial Intelligence Research 45: 481–514.10.1613/jair.3708Search in Google Scholar
Faliszewski, P., E. Hemaspaandra, and L. Hemaspaandra. 2009a. How Hard is Bribery in Elections? Journal of Artificial Intelligence Research 35: 485–532.10.1613/jair.2676Search in Google Scholar
Faliszewski, P., E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. 2009b. “Llull and Copeland Voting Computationally Resist Bribery and Constructive Control.” Journal of Artificial Intelligence Research 35: 275–341.10.1613/jair.2697Search in Google Scholar
Faliszewski, P. and L. Hemaspaandra. 2009. “The Complexity of Power-Index Comparison.” Theoretical Computer Science 410 (1): 101–107.10.1016/j.tcs.2008.09.034Search in Google Scholar
Faliszewski, P. and J. Rothe. 2016. “Control and Bribery in Voting, Chapter 7.” In Handbook of Computational Social Choice, edited by F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, pp. 146–168. Cambridge University Press.10.1017/CBO9781107446984.008Search in Google Scholar
Felsenthal, D., and M. Machover. 1995. “Postulates and Paradoxes of Relative Voting Power – A Critical Re-Appraisal.” Theory and Decision 38 (2): 195–229.10.1007/BF01079500Search in Google Scholar
Fortnow, L., and N. Reingold. 1996. “PP is Closed Under Truth-Table Reductions.” Information and Computation 124 (1): 1–6.10.1006/inco.1996.0001Search in Google Scholar
Freixas, J., and M. Pons. 2008. “Circumstantial Power: Optimal Persuadable Voters.” European Journal of Operational Research 186: 1114–1126.10.1016/j.ejor.2007.02.045Search in Google Scholar
Garey, M., and D. Johnson. 1979. “Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.Search in Google Scholar
Gill, J. 1977. “Computational Complexity of Probabilistic Turing Machines.” SIAM Journal on Computing 6 (4): 675–695.10.1137/0206049Search in Google Scholar
Hemaspaandra, E., L. Hemaspaandra, and J. Rothe. 1997a. “Exact Analysis of Dodgson Elections: Lewis Carroll’s 1876 Voting System is Complete for Parallel Access to NP.” Journal of the ACM 44 (6): 806–825.10.1145/268999.269002Search in Google Scholar
Hemaspaandra, E., L. Hemaspaandra, and J. Rothe. 1997b. “Raising NP Lower Bounds to Parallel NP Lower Bounds.” SIGACT News 28 (2): 2–13.10.1145/261342.261344Search in Google Scholar
Hemaspaandra, E., L. Hemaspaandra, and J. Rothe. 2007. “Anyone But Him: The Complexity of Precluding an Alternative.” Artificial Intelligence 171 (5–6): 255–285.10.1016/j.artint.2007.01.005Search in Google Scholar
Loreggia, A., N. Narodytska, F. Rossi, B. Venable, and T. Walsh. 2015. “Controlling Elections by Replacing Candidates or Votes (Extended Abstract).” In Proceedings of the 14th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 1737–1738. IFAAMAS.Search in Google Scholar
Myerson, R. 1980. “Conference Structures and Fair Allocation Rules.” International Journal of Game Theory 9 (3): 169–182.10.1007/BF01781371Search in Google Scholar
Nisan, N., T. Roughgarden, E. Tardos, and V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press.10.1017/CBO9780511800481Search in Google Scholar
Papadimitriou, C. 1995. Computational Complexity, 2nd ed. Addison-Wesley.Search in Google Scholar
Papadimitriou, C., and S. Zachos. 1983. “Two Remarks on the Power of Counting.” In Proceedings of the 6th GI Conference on Theoretical Computer Science (Lecture Notes in Computer Science #145), pp. 269–276. Springer-Verlag.10.1007/BFb0009651Search in Google Scholar
Peleg, B., and P. Sudhölter. 2007. Introduction to the Theory of Cooperative Games, 2nd ed. Springer-Verlag.Search in Google Scholar
Penrose, L. 1946. “The Elementary Statistics of Majority Voting.” Journal of the Royal Statistical Society 109 (1): 53–57.10.2307/2981392Search in Google Scholar
Prasad, K., and J. Kelly. 1990. “NP-Completeness of Some Problems Concerning Voting Games.” International Journal of Game Theory 19 (1): 1–9.10.1007/BF01753703Search in Google Scholar
Rahwan, T., T. Michalak, and M. Wooldridge. 2014. “A Measure of Synergy in Coalitions. Technical Report arXiv: 1404.2954.v1 [cs.GT], ACM Computing Research Repository (CoRR).Search in Google Scholar
Rey, A., and J. Rothe. 2014. “False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time.” Journal of Artificial Intelligence Research 50: 573–601.10.1613/jair.4293Search in Google Scholar
Rey, A., J. Rothe, and A. Marple. 2017. “Path-Disruption Games: Bribery and a Probabilistic Model.” Theory of Computing Systems 60 (2): 222–252.10.1007/s00224-016-9669-1Search in Google Scholar
Rothe, J. 2005. Complexity Theory and Cryptology. An Introduction to Cryptocomplexity. EATCS Texts in Theoretical Computer Science. Springer-Verlag.Search in Google Scholar
Rothe, J. ed. 2015. Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer Texts in Business and Economics. Springer-Verlag.10.1007/978-3-662-47904-9Search in Google Scholar
Shapley, L., and M. Shubik. 1954. “A Method of Evaluating the Distribution of Power in a Committee System.” American Political Science Review 48 (3): 787–792.10.2307/1951053Search in Google Scholar
Shoham, Y., and K. Leyton-Brown. 2009. Multiagent Systems. Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press.10.1017/CBO9780511811654Search in Google Scholar
Toda, S. 1991. “PP is as hard as the polynomial-time hierarchy.” SIAM Journal on Computing 20 (5): 865–877.10.1137/0220053Search in Google Scholar
Zick, Y. 2013. “On Random Quotas and Proportional Representation in Weighted Voting Games.” In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, pp. 432–438. AAAI Press/IJCAI.Search in Google Scholar
Zick, Y., A. Skopalik, and E. Elkind. 2011. “The Shapley Value as a Function of the Quota in Weighted Voting Games.” In Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp. 490–496. AAAI Press/IJCAI.Search in Google Scholar
Zuckerman, M., P. Faliszewski, Y. Bachrach, and E. Elkind. 2012. “Manipulating the Quota in Weighted Voting Games.” Artificial Intelligence 180–181:1–19.10.1016/j.artint.2011.12.003Search in Google Scholar
© 2018 Walter de Gruyter GmbH, Berlin/Boston
