Computing the Banzhaf power index in network flow games

ABSTRACT

Preference aggregation is used in a variety of multiagent applications, and as a result, voting theory has become an important topic in multiagent system research. However, power indices (which reflect how much "real power" a voter has in a weighted voting system) have received relatively little attention, although they have long been studied in political science and economics. The Banzhaf power index is one of the most popular; it is also well-defined for any simple coalitional game.

In this paper, we examine the computational complexity of calculating the Banzhaf power index within a particular multiagent domain, a network flow game. Agents control the edges of a graph; a coalition wins if it can send a flow of a given size from a source vertex to a target vertex. The relative power of each edge/agent reflects its significance in enabling such a flow, and in real-world networks could be used, for example, to allocate resources for maintaining parts of the network.

We show that calculating the Banzhaf power index of each agent in this network flow domain is #P-complete. We also show that for some restricted network flow domains there exists a polynomial algorithm to calculate agents' Banzhaf power indices.

REFERENCES

• 1: J. F. Banzhaf. Weighted voting doesn't work: a mathematical analysis. Rutgers Law Review, 19:317--343, 1965.
• 2: Xiaotie Deng , Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, v.19 n.2, p.257-266, May 1994 [doi>10.1287/moor.19.2.257]
• 3: P. Dubey and L. Shapley. Mathematical properties of the Banzhaf power index. Mathematics of Operations Research, 4(2):99--131, 1979.
• 4: E. Ephrati and J. S. Rosenschein. The Clarke Tax as a consensus mechanism among automated agents. In Proceedings of the Ninth National Conference on Artificial Intelligence, pages 173--178, Anaheim, California, July 1991.
• 5: Eithan Ephrati , Jeffrey S. Rosenschein, A heuristic technique for multi-agent planning, Annals of Mathematics and Artificial Intelligence, v.20 n.1-4, p.13-67, 1997 [doi>10.1023/A:1018924209812]
• 6: Sumit Ghosh , Manisha Mundhe , Karina Hernandez , Sandip Sen, Voting for movies: the anatomy of a recommender system, Proceedings of the third annual conference on Autonomous Agents, p.434-435, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301303]
• 7: Thomas Haynes , Sandip Sen , Neeraj Arora , Rajani Nadella, An automated meeting scheduling system that utilizes user preferences, Proceedings of the first international conference on Autonomous agents, p.308-315, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267733]
• 8: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Anyone but him: The complexity of precluding an alternative. In Proceedings of the 20th National Conference on Artificial Intelligence, Pittsburgh, July 2005.
• 9: E. Kalai and E. Zemel. On totally balanced games and games of flow. Discussion Papers 413, Northwestern University, Center for Mathematical Studies in Economics and Management Science, Jan. 1980. available at http://ideas.repec.org/p/nwu/cmsems/413.html.
• 10: E. Kalai and E. Zemel. Generalized network problems yielding totally balanced games. Operations Research, 30:998--1008, September 1982.
• 11: A. Laruelle. On the choice of a power index. Papers 99-10, Valencia -Instituto de Investigaciones Economicas, 1999.
• 12: Y. Matsui and T. Matsui. A survey of algorithms for calculating power indices of weighted majority games. Journal of the Operations Research Society of Japan, 43, 2000.
• 13: Yasuko Matsui , Tomomi Matsui, NP-completeness for calculating power indices of weighted majority games, Theoretical Computer Science, v.263 n.1-2, p.306-310, July 28 2001
• 14: N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35:166--196, 2001.
• 15: Ariel D. Procaccia , Jeffrey S. Rosenschein, Junta distributions and the average-case complexity of manipulating elections, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160726]
• 16: J. S. Rosenschein and M. R. Genesereth. Deals among rational agents. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence, pages 91--99, Los Angeles, California, August 1985.
• 17: T. Sandholm and V. Lesser. Issues in automated negotiation and electronic commerce: Extending the contract net framework. In Proceedings of the First International Conference on Multiagent Systems (ICMAS-95), pages 328--335, San Francisco, 1995.
• 18: L. S. Shapley. A value for n-person games. Contributions to the Theory of Games, pages 31--40, 1953.
• 19: L. S. Shapley and M. Shubik. A method for evaluating the distribution of power in a committee system. American Political Science Review, 48:787--792, 1954.
• 20: P. Straffin. Homogeneity, independence and power indices. Public Choice, 30:107--118, 1977.
• 21: M. Tennenholtz and A. Altman. On the axiomatic {see pdf for details}.

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
            Subjects: Multiagent systems

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
computational complexity, power indices, voting