Hedonic coalition nets

ABSTRACT

In hedonic games, players have the opportunity to form coalitions, and have preferences over the coalitions they might join. Such games can be used to model a variety of settings ranging from multi-agent coordination to group formation in social networks. However, the practical application of hedonic games is hindered by the fact that the naive representation for such games is exponential in the number of players. In this paper, we study hedonic coalition nets---a succinct, rule-based representation for hedonic games. This formalism is based on marginal contribution nets, which were developed by Ieong and Shoham for representing coalitional games with transferable utility. We show that hedonic coalition nets are universally expressive, yet are at least as succinct as other existing representation schemes for hedonic games. We then investigate the complexity of many natural decision problems for hedonic coalition nets. In particular, we provide a complete characterisation of the computational difficulty of problems related to coalitional stability for hedonic games represented with hedonic nets.

REFERENCES

• 1: C. Ballester. NP-completeness in hedonic games. Games and Econ. Beh., 49:1--30, 2004.
• 2: S. Banerjee, H. Konishi, T. Sönmez. Core in a simple coalition formation game. Social Choice and Welfare, 18:135--153, 2001.
• 3: Hans L. Bodlaender, Treewidth: Algorithmoc Techniques and Results, Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, p.19-36, August 25-29, 1997
• 4: A. Bogomolnaia and M. O. Jackson. The stability of hedonic coalition structures. Games and Econ. Beh., 38:201--230, 2002.
• 5: K. Cechlarova and J. Hajdukova. Computational complexity of stable partitions with B-preferences. Int. Jnl of Game Th., 31(3):353--364, 2002.
• 6: Katarína Cechlárová , Jana Hajduková, Stable partitions with W-preferences, Discrete Applied Mathematics, v.138 n.3, p.333-347, 15 April 2004 [doi>10.1016/S0166-218X(03)00464-5]
• 7: Katarína Cechlárová , Antonio Romero-Medina, Stability in coalition formation games, International Journal of Game Theory, v.29 n.4, p.487-494, December 2000 [doi>10.1007/s001820000053]
• 8: D. Dimitrov, P. Borm, R. Hendrickx, and S. Sung. Simple priorities and core stability in hedonic games. Social Choice and Welfare, 26(2):421--433, 2006.
• 9: P. E. Dunne, The complexity of Boolean networks, Academic Press Professional, Inc., San Diego, CA, 1988
• 10: Paul E. Dunne , Wiebe van der Hoek , Sarit Kraus , Michael Wooldridge, Cooperative Boolean games, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 11: M. R. Garey and D. S. Johnson. Computers and Intractability. W. H. Freeman, 1979.
• 12: 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]
• 13: E. Malizia, L. Palopoli, and F. Scarcello. Infeasibility certificates and the complexity of the core in coalitional games. In Proc. IJCAI-07, 2007.
• 14: Martin Olsen, Nash Stability in Additively Separable Hedonic Games Is NP-Hard, Proceedings of the 3rd conference on Computability in Europe: Computation and Logic in the Real World, p.598-605, June 18-23, 2007, Siena, Italy [doi>10.1007/978-3-540-73001-9_62]
• 15: S. C. Sung and D. Dimitrov. On core membership testing for hedonic coalition formation games. Oper. Res. Letters, 35:155--158, 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:
complexity, hedonic games, marginal contribution nets