The price of democracy in coalition formation

ABSTRACT

Whenever rational agents form coalitions to execute tasks, doing so via a decentralized negotiation process---while more robust and democratic---may lead to a loss of efficiency compared to a centralized solution. To quantify this loss, we introduce the notion of the Price of Democracy (PoD), which measures the amount of resources needlessly committed to the task(s) at hand. After defining this concept for general coalitional games, we instantiate it in the setting of weighted voting games, a simple but expressive class of coalitional games that can be used to model resource allocation in multiagent scenarios. We approach the problem of forming winning coalitions in this setting from a non-cooperative perspective, and put forward an intuitive deterministic bargaining process, which exhibits no delay of agreement (i.e., the agents are guaranteed to form a winning coalition in round one) and allows for efficient computation of bargaining strategies. We show a tight bound of 3/2 on the PoD of our process if two rounds of bargaining are allowed, and demonstrate that this bound cannot improve with more rounds. We then generalize our bargaining process to settings where multiple coalitions are allowed to be formed, show that this generalization also exhibits no delay of agreement, and discuss the PoD in such settings.

REFERENCES

• 1: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 2: J. F. Banzhaf. Weighted voting doesn't work: a mathematical analysis. Rutgers Law Review, 19:317--343, 1965.
• 3: C. Bird. On cost allocation for spanning tree: a game theoretic approach. Networks, 6:335--350, 1976.
• 4: P. Caillou, S. Aknine, and S. Pinson. Multi-agent models for searching pareto optimal solutions to the problem of forming and dynamic restructuring of coalitions. In Proceedings of the 15th European Conference on Artificial Intelligence (ECAI'02), pages 13--17, 2002.
• 5: K. Chatterjee, B. Dutta, and K. Sengupta. A noncooperative theory of coalitional bargaining. Review of Economic Studies, 60:463--477, 1993.
• 6: George Christodoulou , Elias Koutsoupias, The price of anarchy of finite congestion games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060600]
• 7: Edith Elkind , Georgios Chalkiadakis , Nicholas R. Jennings, Coalition Structures in Weighted Voting Games, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.393-397, June 27, 2008
• 8: E. Elkind, L. Goldberg, P. Goldberg, and M. Wooldridge. Computational complexity of weighted threshold games. In Proceedings of AAAI'07, pages 718--723, 2007.
• 9: Daniel Granot , Frieda Granot, On some network flow games, Mathematics of Operations Research, v.17 n.4, p.792-841, Nov. 1992 [doi>10.1287/moor.17.4.792]
• 10: S. A. J. M. Snyder Jr., M. M. Ting. Legislative bargaining under weighted voting. American Economic Review, 95(4):981--1004, 2005.
• 11: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS'99), pages 404--413, 1999.
• 12: Sarit Kraus , Onn Shehory , Gilad Taase, Coalition formation with uncertain heterogeneous information, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860577]
• 13: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• 14: A. Mas-Colell, M. Whinston, and J. Green. Microeconomic Theory. Oxford University Press, 1995.
• 15: T. Matsui and Y. Matsui. A survey of algorithms for calculating power indices of weighted majority games. J. Oper. Res. Soc. Japan, 43(1):71--86, 2000.
• 16: 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
• 17: K. Matsuyama. Perfect equilibria in a trade liberalization game. The American Economic Review, 80(3):480--492, 1990.
• 18: B. Moldovanu and E. Winter. Order independent equilibria. Games and Economic Behavior, 9:21--34, 1995.
• 19: R. Myerson. Game Theory: Analysis of Conflict. Harvard U. Press, 1991.
• 20: A. Okada. A Noncooperative coalitional bargaining game with random proposers. Games and Economic Behavior, 16:97--108, 1996.
• 21: M. Osborne and A. Rubinstein. Bargaining and Markets. Academic Press, San Diego, 1990.
• 22: 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]
• 23: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 24: Tuomas W. Sandholm , Victor R. Lesser, Coalitions among computationally bounded agents, Artificial Intelligence, v.94 n.1-2, p.99-137, July 1997 [doi>10.1016/S0004-3702(97)00030-1]
• 25: 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.
• 26: A. Taylor and W. Zwicker. Simple Games: Desirability Relations, Trading, Pseudoweightings. Princeton University Press, Princeton, 1999.
• 27: H. Yan. Noncooperative selection of the core. International Journal of Game Theory, 31(4):527--540, 2003.

INDEX TERMS

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

General Terms:
Economics, Measurement, Theory

Keywords:
coalition formation, game theory, multilateral bargaining