Abstract
Hedonic games provide a general model of coalition formation, in which a set of agents is partitioned into coalitions, with each agent having preferences over which other players are in her coalition. We prove that with additively separable preferences, it is \(\varSigma _2^p\)-complete to decide whether a core- or strict-core-stable partition exists, extending a result of Woeginger (2013). Our result holds even if valuations are symmetric and non-zero only for a constant number of other agents. We also establish \(\varSigma _2^p\)-completeness of deciding non-emptiness of the strict core for hedonic games with dichotomous preferences. Such results establish that the core is much less tractable than solution concepts such as individual stability.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aziz, H., Brandl, F., Brandt, F., Harrenstein, P., Olsen, M., Peters, D.: Fractional hedonic games, [CS.GT] (2017). arXiv:1705.10116
Aziz, H., Brandt, F., Seedig, H.G.: Computing desirable partitions in additively separable hedonic games. Artif. Intell. 195, 316–334 (2013)
Aziz, H., Brandt, F., Harrenstein, P.: Fractional hedonic games. In: Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 5–12 (2014)
Aziz, H., Harrenstein, P., Lang, J., Wooldridge, M.: Boolean hedonic games. In: Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR), pp. 166–175 (2016)
Aziz, H., Savani, R.: Hedonic games. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.) Handbook of Computational Social Choice. Cambridge University Press (2016). Chapter 15
Ballester, C.: NP-completeness in hedonic games. Games Econ. Behav. 49(1), 1–30 (2004)
Banerjee, S., Konishi, H., Sönmez, T.: Core in a simple coalition formation game. Soc. Choice Welfare 18(1), 135–153 (2001)
Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT. Technical report. ECCC TR03-049 (2003)
Bogomolnaia, A., Jackson, M.O.: The stability of hedonic coalition structures. Games Econ. Behav. 38(2), 201–230 (2002)
Cechlárová, K., Hajduková, J.: Stable partitions with \(\cal{W}\)-preferences. Discrete Appl. Mathe. 138(3), 333–347 (2004)
Dimitrov, D., Borm, P., Hendrickx, R., Sung, S.C.: Simple priorities and core stability in hedonic games. Soc. Choice Welfare 26(2), 421–433 (2006)
Elkind, E., Wooldridge, M.: Hedonic coalition nets. In: Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 417–424 (2009)
Ko, K.I., Lin, C.L.: On the complexity of min-max optimization problems and their approximation. In: Du, D.Z., Pardalos, P.M. (eds.) Minimax and Applications, vol. 4, pp. 219–239. Springer, Boston (1995)
Malizia, E., Palopoli, L., Scarcello, F.: Infeasibility certificates and the complexity of the core in coalitional games. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1402–1407 (2007)
Ohta, K., Barrot, N., Ismaili, A., Sakurai, Y., Yokoo, M.: Core stability in hedonic games among friends and enemies: impact of neutrals. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI) (2017)
Peters, D.: Complexity of hedonic games with dichotomous preferences. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp. 579–585 (2016)
Peters, D.: Graphical hedonic games of bounded treewidth. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp. 586–593 (2016)
Peters, D., Elkind, E.: Simple causes of complexity in hedonic games. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pp. 617–623 (2015)
Rey, A., Rothe, J., Schadrack, H., Schend, L.: Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games. Ann. Mathe. Artif. Intell., 1–17 (2015)
Shrot, T., Aumann, Y., Kraus, S.: On agent types in coalition formation problems. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 757–764 (2010)
Stockmeyer, L.J.: The polynomial-time hierarchy. Theoret. Comput. Sci. 3(1), 1–22 (1976)
Sung, S.C., Dimitrov, D.: Computational complexity in additive hedonic games. Eur. J. Oper. Res. 203(3), 635–639 (2010)
Woeginger, G.J.: Core stability in hedonic coalition formation. In: van Emde Boas, P., Groen, F.C.A., Italiano, G.F., Nawrocki, J., Sack, H. (eds.) SOFSEM 2013. LNCS, vol. 7741, pp. 33–50. Springer, Heidelberg (2013). doi:10.1007/978-3-642-35843-2_4
Woeginger, G.J.: A hardness result for core stability in additive hedonic games. Mathe. Soc. Sci. 65(2), 101–104 (2013)
Acknowledgements
I thank the anonymous reviewers for helpful feedback that improved the clarity of presentation, and Lena Schend for useful discussions. I am supported by EPSRC, by ERC under grant number 639945 (ACCORD), and by COST Action IC1205.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Peters, D. (2017). Precise Complexity of the Core in Dichotomous and Additive Hedonic Games. In: Rothe, J. (eds) Algorithmic Decision Theory. ADT 2017. Lecture Notes in Computer Science(), vol 10576. Springer, Cham. https://doi.org/10.1007/978-3-319-67504-6_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-67504-6_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-67503-9
Online ISBN: 978-3-319-67504-6
eBook Packages: Computer ScienceComputer Science (R0)