INTERNAL STABILITY AND PARETO OPTIMALITY IN HEDONIC COALITION FORMATION GAMES

Abstract

We study hedonic coalition formation games that consist of a finite set of agents and a list of agents’ preferences such that each agent’s preferences depend only on the members of her coalition. An outcome of a hedonic coalition formation game is a partition (i.e., coalition structure) of the finite set of agents. We study the existence of partitions that are both internally stable and Pareto optimal. We construct an algorithm that terminates for each given hedonic coalition formation game such that the outcome of the algorithm is internally stable and Pareto optimal. We also show that if the outcome of the algorithm is the partition that consists of singleton coalitions then it is also core stable and if it is the partition that contains only the grand coalition then it is also both core stable and Nash stable.

Keywords

• Coalition formation
• Core stability
• Hedonic games
• Internal stability
• Nash stability
• Pareto optimality.

References

1. Alcalde, J. and Revilla, P. (2004) “Researching with whom? Stability and Manipulation”, Journal of Mathematical Economics, 40: 869–887.
2. Alcalde, J. and Romero-Medina, A. (2006) “Coalition Formation and Stability”, Social Choice and Welfare, 27: 365–375.
3. Aziz, H. and Brandl, F. (2012) “Existence of stability in hedonic coalition formation games”, arXiv preprint arXiv:1201.4754.
4. Aziz, H., Brandt, F., and Harrenstein, P. (2013) “Pareto optimality in coalition formation”, Games and Economic Behavior, 82: 562–581.
5. Aziz, H. and Savani, R. (2016) “Hedonic games” F. Brandt, V. Conitzer, J. Lang U. Endriss, and AD Procaccia (eds.) Handbook of Computational Social Choice, Cambridge University Press, Cambridge.
6. Banerjee, S., Konishi, H., and Sönmez, T. (2001) “Core in a Simple Coalition Formation Game”, Social Choice and Welfare, 18: 135–153.
7. Bogomolnaia, A. and Jackson, M. (2002) “The Stability of Hedonic Coalition Structures”, Games and Economic Behavior, 38: 201–230.
8. Burani, N. and Zwicker, W. S. (2003) “Coalition Formation Games with Separable Preferences”, Mathematical Social Sciences, 45: 27–52.

9. Cechlárová, K. and Romero-Medina, A. (2001) “Stability in coalition formation games”, International Journal of Game Theory, 29(4): 487–494.
10. Dimitrov, D., Borm, P., Hendrickx, R., and Sung, S. C. (2006) “Simple Priorities and Core Stability in Hedonic Games”, Social Choice and Welfare, 26(2): 421–433.
11. Dimitrov, D. and Sung, S. C. (2004) “Enemies and friends in hedonic games: individual deviations, stability and manipulation”, CentER Discussion Paper Series.
12. Dimitrov, D. and Sung, S. C. (2006) “Top responsiveness and Nash stability in coalition formation games”, Kybernetika, 42(4): 453–460.
13. Drèze, J. and Greenberg, J. (1980) “Hedonic Coalitions: Optimality and Stability”, Econometrica, 48: 987–1003.
14. Gale, D. and Shapley, L. S. (1962) “College Admissions and the Stability of Marriage”, American Mathematical Monthly, 69: 9–15.
15. Hajduková, J. (2006) “Coalition formation games: A survey”, International Game Theory Review, 8(4): 613–641.
16. Iehlé, V. (2007) “The Core-partition of a Hedonic Game”, Mathematical Social Sciences, 54: 176–185.
17. İnal, H. (2019) “The existence of a unique core partition in coalition formation games”, Games and Economic Behavior, 114: 215–231.
18. Karakaya, M. (2011) “Hedonic Coalition Formation Games: A New Stability Notion”, Mathematical Social Sciences, 61: 157–165.
19. Liu, Y., Tang, P., and Fang, W. (2014) “Internally stable matchings and exchanges”, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 1433–1439.
20. Özbilen, S. (2019) “Three Essays on Coalition Formation Games”, Ph.D. thesis, İstanbul Bilgi University.
21. Özbilen, S. (2022) “Coalition Formation Games: Internal Stability”, forthcoming in Ankara University SBF Journal.
22. Pápai, S. (2004) “Unique Stability in Simple Coalition Formation Games”, Games and Economic Behavior, 48: 337–354.
23. Pápai, S. (2007) “Individual Stability in Hedonic Coalition Formation”, mimeo.
24. Roth, A. E. and Sotomayor, M. A. O. (1990) “Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis”, Cambridge University Press, Cambridge.
25. Schlueter, J. and Goldsmith, J. (2020) “Internal stability in hedonic games”, In The Thirty-Third International Flairs Conference, pages 154–159.
26. Suksompong, W. (2015) “Individual and group stability in neutral restrictions of hedonic games”, Mathematical Social Sciences, 78: 1–5.
27. Sung, S. C. and Dimitrov, D. (2007) “On Myopic Stability Concepts for Hedonic Games”, Theory and Decision, 62: 31–45.
28. Suzuki, K. and Sung, S. C. (2010) “Hedonic coalition formation in conservative societies”, SSRN: 1700921.