On representing coalitional games with externalities

ABSTRACT

We consider the issue of representing coalitional games in multi-agent systems with externalities (i.e., in systems where the performance of one coalition may be affected by other co-existing coalitions). In addition to the conventional partition function game representation (PFG), we propose a number of new representations based on a new notion of externalities. In contrast to conventional game theory, our new concept is not related to the process by which the coalitions are formed, but rather to the effect that each coalition may have on the entire system and vice versa. We show that the new representations are fully expressive and, for many classes of games, more concise than the conventional PFG. Building upon these new representations, we propose a number of approaches to solve the coalition structure generation problem in systems with externalities. We show that, if externalities are characterised by various degrees of regularity, the new representations allow us to adapt coalition structure generation algorithms that were originally designed for domains with no externalities, so that they can be used when externalities are present. Finally, building upon Rahwan et al. [16] and Michalak et al. [9], we present a unified method to solve the coalition structure generation problem in any system, with or without externalities, provided sufficient information is available.

REFERENCES

• 1: E. Catilina and R.Feinberg. Market power and incentives to form research consortia. Review of Industrial Organization, 28(2):129--144, 2006.
• 2: V. Conitzer and T. Sandholm. Complexity of Determining Nonemptiness in The Core. In In Proceedings of IJCAI, pages 219--225, 2004.
• 3: Vincent Conitzer , Tuomas Sandholm, Computing shapley values, manipulating value division schemes, and checking core membership in multi-issue domains, Proceedings of the 19th national conference on Artifical intelligence, p.219-225, July 25-29, 2004, San Jose, California
• 4: Viet Dung Dang , Nicholas R. Jennings, Generating Coalition Structures with Finite Bound from the Optimal Guarantees, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.564-571, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.132]
• 5: G. de Clippel and R. Serrano. Marginal contributions and externalities in the value. Econometrica, 76:1413--1436, 2008.
• 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: Samuel Ieong , Yoav Shoham, Marginal contribution nets: a compact representation scheme for coalitional games, Proceedings of the 6th ACM conference on Electronic commerce, p.193-202, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064030]
• 8: W. Lucas and R. Thrall. n-person games in partition function form. Naval Res. Logist. Quart. X, pages 281--298, 1963.
• 9: Tomasz Michalak , Andrew Dowell , Peter McBurney , Michael Wooldridge, Optimal Coalition Structure Generation In Partition Function Games, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.388-392, June 27, 2008
• 10: Tomasz Michalak , Joanna Tyrowicz , Peter McBurney , Michael Wooldridge, Exogenous coalition formation in the e-marketplace based on geographical proximity, Electronic Commerce Research and Applications, v.8 n.4, p.203-223, July, 2009 [doi>10.1016/j.elerap.2008.12.001]
• 11: 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
• 12: J. Plasmans, J. Engwerda, B. vanAarle, G.D. Bartolomeo, and T. Michalak. Dynamic Modelling of Monetary and Fiscal Cooperation Among Nations. Springer, New York USA, 2006.
• 13: Talal Rahwan , Nicholas R. Jennings, An algorithm for distributing coalitional value calculations among cooperating agents, Artificial Intelligence, v.171 n.8-9, p.535-567, June, 2007 [doi>10.1016/j.artint.2007.03.002]
• 14: T. Rahwan and N.R. Jennings. Coalition structure generation: Dynamic programming meets anytime optimisation. In Proceedings of AAAI, pages 156--161, 2008.
• 15: Talal Rahwan , Nicholas R. Jennings, An improved dynamic programming algorithm for coalition structure generation, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 16: T. Rahwan, S.D. Ramchurn, A. Giovannucci, and N.R. Jennings. An anytime algorithm for optimal coalition structure generation. Journal of Artificial Intelligence Research (JAIR), 34:521--567, 2009.
• 17: Tuomas Sandholm , Kate Larson , Martin Andersson , Onn Shehory , Fernando Tohmé, Coalition structure generation with worst case guarantees, Artificial Intelligence, v.111 n.1-2, p.209-238, July 1999 [doi>10.1016/S0004-3702(99)00036-3]
• 18: Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]
• 19: D. Yun Yeh, A dynamic programming approach to the complete set partitioning problem, BIT, v.26 n.4, p.467-474, Jan. 1986 [doi>10.1007/BF01935053]

INDEX TERMS

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

General Terms:
Algorithms, Economics, Theory

Keywords:
coalition structure generation, partition function games, representation