False name manipulations in weighted voting games: splitting, merging and annexation

ABSTRACT

An important aspect of mechanism design in social choice protocols and multiagent systems is to discourage insincere and manipulative behaviour. We examine the computational complexity of false-name manipulation in weighted voting games which are an important class of coalitional voting games. Weighted voting games have received increased interest in the multiagent community due to their compact representation and ability to model coalitional formation scenarios. Bachrach and Elkind in their AAMAS 2008 paper examined divide and conquer false-name manipulation in weighted voting games from the point of view of Shapley-Shubik index. We analyse the corresponding case of the Banzhaf index and check how much the Banzhaf index of a player increases or decreases if it splits up into sub-players. A pseudo-polynomial algorithm to find the optimal split is also provided. Bachrach and Elkind also mentioned manipulation via merging as an open problem. In the paper, we examine the cases where a player annexes other players or merges with them to increase their Banzhaf index or Shapley-Shubik index payoff. We characterize the computational complexity of such manipulations and provide limits to the manipulation. The annexation non-monotonicity paradox is also discovered in the case of the Banzhaf index. The results give insight into coalition formation and manipulation.

REFERENCES

• 1: E. Algaba, J. M. Bilbao, and J. Fernandez. The distribution of power in the European Constitution. European Journal of Operational Research, 176(3):1752--1755, 2007.
• 2: H. Aziz. Complexity of comparison of influence of players in simple games. Proceedings of the Second International Workshop on Computational Social Choice (COMSOC), 2:61--72, 2008.
• 3: H. Aziz and M. Paterson. Classification of computationally tractable weighted voting games. Lecture Notes in Engineering and Computer Science, World Congress on Engineering, 1:129--134, 2008.
• 4: H. Aziz, M. Paterson, and D. Leech. Efficient algorithm for designing weighted voting games. IEEE International Multi Topic Conference, 2007. 10.1109/INMIC.2007.4557718.
• 5: Yoram Bachrach , Edith Elkind, Divide and conquer: false-name manipulations in weighted voting games, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 6: Yoram Bachrach , Evangelos Markakis , Ariel D. Procaccia , Jeffrey S. Rosenschein , Amin Saberi, Approximating power indices, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 7: Yoram Bachrach , Jeffrey S. Rosenschein , Ely Porat, Power and stability in connectivity games, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 8: J. Bartholdi III and J. Orlin. Single transferable vote resists strategic voting. Social Choice and Welfare, 8(4):341--354, 1991.
• 9: J. Bartholdi III, C. Tovey, and M. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3):227--241, 1989.
• 10: J. Bartholdi III, C. Tovey, and M. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6(2):157--165, 1989.
• 11: J. Bartholdi III, C. Tovey, and M. Trick. How hard is it to control an election? Mathematical and Computer Modeling, 16(8/9):27--40, 1992.
• 12: J. Bilbao, J. Fernández, A. Losada, and J. López. Generating functions for computing power indices efficiently. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 8(2):191--213, December 2000.
• 13: V. G. Deineko and G. J. Woeginger. On the dimension of simple monotonic games. European Journal of Operational Research, 170(1):315--318, 2006.
• 14: P. Dubey and L. S. Shapley. Mathematical properties of the Banzhaf power index. Mathematics of Operations Research, 4(2):99--131, 1979.
• 15: E. Elkind, L. A. Goldberg, P. Goldberg, and M. Wooldridge. On the dimensionality of voting games. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-2008), Chicago, Illinois, USA, July 13--17 2008.
• 16: E. Elkind, L. A. Goldberg, P. W. Goldberg, and M. Wooldridge. Computational complexity of weighted threshold games. In AAAI, pages 718--723, 2007.
• 17: Shaheen Fatima , Michael Wooldridge , Nicholas R. Jennings, An anytime approximation method for the inverse Shapley value problem, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 18: D. Felsenthal and M. Machover. The Measurement of Voting Power. Edward Elgar Publishing, Cheltenham, UK, 1998.
• 19: G. Gambarelli. Power indices for political and financial decision making: A review. Annals of Operations Research, 51:1572--9338, 1994.
• 20: A. Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41(4):587--601, July 1973.
• 21: A. Iwasaki, D. Kempe, Y. Saito, M. Salek, and M. Yokoo. False-name-proof mechanisms for hiring a team. In WINE, pages 245--256, 2007.
• 22: A. Laruelle and M. Widgren. Is the allocation of voting power among EU states fair? Public Choice, 94(3--4):317--39, March 1998.
• 23: D. Leech. Voting power in the governance of the international monetary fund. Annals of Operations Research, 109(1):375--397, 2002.
• 24: M. Machover and D. S. Felsenthal. Annexations and alliances: When are blocs advantageous a priori? Social Choice and Welfare, 19(2):295--312, 2002.
• 25: T. Matsui and Y. Matsui. A survey of algorithms for calculating power indices of weighted majority games. Journal of the Operations Research Society of Japan, 43(7186), 2000.
• 26: S. Muroga. Threshold logic and Its Applications. Wiley Interscience, New York, 1971.
• 27: Naoki Ohta , Vincent Conitzer , Yasufumi Satoh , Atsushi Iwasaki , Makoto Yokoo, Anonymity-proof Shapley value: extending shapley value for coalitional games in open environments, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 28: Naoki Ohta , Atsushi Iwasaki , Makoto Yokoo , Kohki Maruono , Vincent Conitzer , Tuomas Sandholm, A compact representation scheme for coalitional games in open anonymous environments, Proceedings of the 21st national conference on Artificial intelligence, p.697-702, July 16-20, 2006, Boston, Massachusetts
• 29: Christos H. Papadimitriou , Mihalis Yannakakis, On complexity as bounded rationality (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.726-733, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195445]
• 30: K. Prasad , J. S. Kelly, NP-completeness of some problems concerning voting games, International Journal of Game Theory, v.19 n.1, p.1-9, Apr. 1990 [doi>10.1007/BF01753703]
• 31: K. Ramamurthy. Coherent structures and simple games (Theory and Decision Library). Kluwer Academic Publishers, Netherlands, first edition edition, 1990.
• 32: A. Roth (ed.). The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge U. Press, London, 1988.
• 33: A. Taylor and W. Zwicker. Simple Games: Desirability Relations, Trading, Pseudoweightings. Princeton University Press, New Jersey, first edition edition, 1999.
• 34: Arnold B. Urken, Social choice theory and distributed decision making, Proceedings of the ACM SIGOIS and IEEECS TC-OA 1988 conference on Office information systems, p.158-168, March 23-25, 1988, Palo Alto, California, United States
• 35: G. van der Laan and R. van den Brink. A Banzhaf share function for cooperative games in coalition structure. Theory and Decision, 53(1):61--86, 2002.
• 36: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944.
• 37: Makoto Yokoo, False-name bids in combinatorial auctions, ACM SIGecom Exchanges, v.7 n.1, p.48-51, December 2007 [doi>10.1145/1345037.1345049]
• 38: M. Yokoo, V. Conitzer, T. Sandholm, N. Ohta, and A. Iwasaki. Coalitional games in open anonymous environments. In AAAI, pages 509--515, 2005.
• 39: M. Zuckerman, P. Faliszewski, Y. Bachrach, and E. Elkind. Manipulating the quota in weighted voting games. In The Twenty-Third National Conference on Artificial Intelligence, Chicago, Illinois, July 2008.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms, Economics, Theory

Keywords:
Banzhaf index, Shapley-Shubik index, computational complexity, false-name manipulation, weighted voting games