HEDONIC COALITION FORMATION GAMES: NASH STABILITY UNDER DIFFERENT MEMBERSHIP RIGHTS

Abstract

Purpose - We study hedonic coalition formation games in which each agent has preferences over the coalitions she is a member of. Hedonic coalition formation games are used to model economic, social, and political instances in which people form coalitions. The outcome of a hedonic coalition formation game is a partition. We consider stability concepts of a partition that are based on a single-agent deviation under different membership rights, that is, we study Nash stability under different membership rights. We revisit the conditions that guarantee the existence of Nash stable partitions and provide examples of hedonic coalition formation games satisfying these conditions. Methodology – While analyzing a stability notion for hedonic coalition formation games, two crucial points are considered: i) who can deviate from the given partition, ii) what are the allowed movements for the deviator(s), i.e., what deviators are entitled to do. For the first point, the deviation of a single agent is considered for Nash stabilities. For the second point, the allowed movements for deviators are determined by specifying membership rights, that is, membership rights describe whose approval is needed for a particular deviation. So, we reconsider stability concepts by using membership rights based on individual deviations, i.e., we consider Nash stability under different membership rights for hedonic coalition formation games. Findings- A classification of stability concepts based on a single-agent deviation for hedonic coalition formation games are provided by employing membership rights. The conditions in the literature guaranteeing the existence of Nash stable partitions for all membership rights are revisited. For each condition, an example of a hedonic coalition formation game satisfying the condition is given. Hence, a complete analysis of sufficient conditions for all Nash stability concepts are provided. Conclusion- To choose the correct stability notion one first should understand the membership rights in the environment that she studies. Then, for hedonic coalition formation problems, the appropriate Nash stability notion consistent with the ongoing membership rights should be chosen when single-agent deviation is considered.

Keywords

• Coalition formation
• Hedonic games
• Nash stability
• membership rights
• separable preferences

References

1. Alcalde, J. and Revilla, P., (2004). Researching with whom? Stability and manipulation. Journal of Mathematical Economics, 40(8), 869 - 887.
2. Aziz, H. and Brandl, F., (2012). Existence of stability in hedonic coalition formation games. Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, June 4-8, 2012, Valencia, V.2, 763–770. (https://www.ifaamas.org/Proceedings/aamas2012/papers/1E_1.pdf)
3. Aziz, H., Harrenstein, P., and Pyrga, E., (2011). Individual-based stability in hedonic games depending on the best or worst players. Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, June 4-8, 2012, Valencia, V. 3, 1311-1312. (https://www.ifaamas.org/Proceedings/aamas2012/papers/Z3_14.pdf)
4. Aziz, H. and Savani, R., (2016). Hedonic games. Chapter 15, Handbook of Computational Social Choice, F. Brandt, V. Conitzer, J. Lang U. Endriss, and AD Procaccia (Eds.), Cambridge University Press, Cambridge.
5. Ballester, C., (2004). NP-completeness in hedonic games. Games and Economic Behavior, 49(1), 1 - 30.
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. Bilò, V., Fanelli, A., Flammini, M., Monaco, G., and Moscardelli, L., (2018). Nash stable outcomes in fractional hedonic games: Existence, efficiency, and computation. Journal of Artificial Intelligence Research, 62, 315 - 371.
8. Bogomolnaia, A. and Jackson, M., (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38, 201 - 230.

9. Burani, N. and Zwicker, W. S., (2003). Coalition formation games with separable preferences. Mathematical Social Sciences, 45(1), 27 - 52.
10. Czarnecki, E. and Dutta, A., (2021). Scalable hedonic coalition formation for task allocation with heterogeneous robots. Intelligent Service Robotics, 14, 501 – 517.
11. Diamantoudi, E. and Xue, L., (2003). Farsighted stability in hedonic games. Social Choice and Welfare, 21, 39 – 61.
12. 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.
13. Dimitrov, D. and Sung, S. C., (2004). Enemies and friends in hedonic games: Individual deviations, stability, and manipulation. CentER Discussion Paper Series, Vol. 2004-111. (https://pure.uvt.nl/ws/portalfiles/portal/629611/111.pdf)
14. Dimitrov, D. and Sung, S. C., (2006). Top responsiveness and Nash stability in coalition formation games. Kybernetika, 42(4), 453 - 460.
15. Drèze, J. and Greenberg, J., (1980). Hedonic coalitions: Optimality and stability. Econometrica, 48, 987 - 1003.
16. Farrell, J. and Scotchmer, S., (1988). Partnerships. The Quarterly Journal of Economics, 103(2), 279 - 297.
17. Gale, D. and Shapley, L. S., (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9 - 15.
18. Hajduková, J., (2006). Coalition formation games: A survey. International Game Theory Review, 8(4), 613 - 641.
19. Jang, I., Shin, H. S., and Tsourdos, A., (2018). Anonymous hedonic game for task allocation in a large-scale multiple agent system. IEEE Transactions on Robotics, 34(6), 1534 – 1548.
20. Karakaya, M., (2011). Hedonic coalition formation games: A new stability notion. Mathematical Social Sciences, 61(3), 157 - 165.
21. Kerkmann, A. M. and Rothe, J., (2019). Stability in FEN-hedonic games for single-player deviations. Proceedings of the 18th International Conference on Autonomous Agents and Multi Agent Systems, 891 - 899.
22. Olsen, M., (2009). Nash stability in additively separable hedonic games and community structures. Theory of Computing Systems, 45(4), 917 - 925.
23. Pápai, S., (2007). Individual stability in hedonic coalition formation. Research Papers, Concordia University, Montreal, Quebec.
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, ISBN: 9781139052214.
25. Sertel, M. R., (1992). Membership property rights, efficiency, and stability. Research Papers, Boğaziçi University, Istanbul.
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(1), 31 - 45.
28. Sung, S. C. and Dimitrov, D., (2010). Computational complexity in additive hedonic games. European Journal of Operational Research, 203(3), 635 - 639.
29. Suzuki, K. and Sung, S. C., (2010). Hedonic coalition formation in conservative societies. Available at SSRN: https://ssrn.com/abstract=1700921.
30. Xiong, M. and Xie G., (2023). Swarm game and task allocation for autonomous underwater robots. Journal of Marine Science and Engineering, 11(1), 148 – 166.