Power in normative systems

ABSTRACT

Power indices such as the Banzhaf index were originally developed within voting theory in an attempt to rigorously characterise the influence that a voter is able to wield in a particular voting game. In this paper, we show how such power indices can be applied to understanding the relative importance of agents when we attempt to devise a coordination mechanism using the paradigm of social laws, or normative systems. Understanding how pivotal an agent is with respect to the success of a particular social law is of benefit when designing such social laws: we might typically aim to ensure that power is distributed evenly amongst the agents in a system, to avoid bottlenecks or single points of failure. After formally defining the framework and illustrating the role of power indices in it, we investigate the complexity of computing these indices, showing that the characteristic complexity result is #P-completeness. We then investigate cases where computing indices is computationally easy.

REFERENCES

• 1: Thomas Ågotnes , Wiebe van der Hoek , Michael Wooldridge, Normative system games, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329284]
• 2: N. I. Al-Najjar and R. Smorodinsky. Pivotal players and the characterization of influence. Journal of Economic Theory, 92(2):318--342, 2000.
• 3: Yoram Bachrach , Jeffrey S. Rosenschein, Computing the Banzhaf power index in network flow games, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329433]
• 4: J. F. Banzhaf III. Weighted voting doesn't work: A mathematical analysis. Rutgers Law Review, 19(2):317--343, 1965.
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: 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]
• 7: E. Allen Emerson, Temporal and modal logic, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 8: D. S. Felsenthal and M. Machover. The Measurement of Voting Power. Edward Elgar: Cheltenham, UK, 1998.
• 9: David Fitoussi , Moshe Tennenholtz, Choosing social laws for multi-agent systems: minimality and simplicity, Artificial Intelligence, v.119 n.1-2, p.61-101, May 2000 [doi>10.1016/S0004-3702(00)00006-0]
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press: Cambridge, MA, 1994.
• 12: Y. Shoham and M. Tennenholtz. On the synthesis of useful social laws for artificial agent societies. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), San Diego, CA, 1992.
• 13: Y. Shoham and M. Tennenholtz. On social laws for artificial agent societies: Off-line design. In P. E. Agre and S. J. Rosenschein, editors, Computational Theories of Interaction and Agency, pages 597--618. The MIT Press: Cambridge, MA, 1996.
• 14: W. van der Hoek, M. Roberts, and M. Wooldridge. Social laws in alternating time: Effectiveness, feasibility, and synthesis. Synthese, 156(1):1--19, May 2007.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Theory

Keywords:
coalitional games, complexity, logic, normative systems