Research Article
BibTex RIS Cite

HEDONIC COALITION FORMATION GAMES: NASH STABILITY UNDER DIFFERENT MEMBERSHIP RIGHTS

Year 2023, Volume: 12 Issue: 1, 45 - 58, 31.03.2023
https://doi.org/10.17261/Pressacademia.2023.1725

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.

References

  • Alcalde, J. and Revilla, P., (2004). Researching with whom? Stability and manipulation. Journal of Mathematical Economics, 40(8), 869 - 887.
  • 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)
  • 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)
  • 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.
  • Ballester, C., (2004). NP-completeness in hedonic games. Games and Economic Behavior, 49(1), 1 - 30.
  • Banerjee, S., Konishi, H., and Sönmez, T., (2001). Core in a simple coalition formation game. Social Choice and Welfare, 18, 135 - 153.
  • 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.
  • Bogomolnaia, A. and Jackson, M., (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38, 201 - 230.
  • Burani, N. and Zwicker, W. S., (2003). Coalition formation games with separable preferences. Mathematical Social Sciences, 45(1), 27 - 52.
  • Czarnecki, E. and Dutta, A., (2021). Scalable hedonic coalition formation for task allocation with heterogeneous robots. Intelligent Service Robotics, 14, 501 – 517.
  • Diamantoudi, E. and Xue, L., (2003). Farsighted stability in hedonic games. Social Choice and Welfare, 21, 39 – 61.
  • 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.
  • 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)
  • Dimitrov, D. and Sung, S. C., (2006). Top responsiveness and Nash stability in coalition formation games. Kybernetika, 42(4), 453 - 460.
  • Drèze, J. and Greenberg, J., (1980). Hedonic coalitions: Optimality and stability. Econometrica, 48, 987 - 1003.
  • Farrell, J. and Scotchmer, S., (1988). Partnerships. The Quarterly Journal of Economics, 103(2), 279 - 297.
  • Gale, D. and Shapley, L. S., (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9 - 15.
  • Hajduková, J., (2006). Coalition formation games: A survey. International Game Theory Review, 8(4), 613 - 641.
  • 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.
  • Karakaya, M., (2011). Hedonic coalition formation games: A new stability notion. Mathematical Social Sciences, 61(3), 157 - 165.
  • 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.
  • Olsen, M., (2009). Nash stability in additively separable hedonic games and community structures. Theory of Computing Systems, 45(4), 917 - 925.
  • Pápai, S., (2007). Individual stability in hedonic coalition formation. Research Papers, Concordia University, Montreal, Quebec.
  • 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.
  • Sertel, M. R., (1992). Membership property rights, efficiency, and stability. Research Papers, Boğaziçi University, Istanbul.
  • Suksompong, W., (2015). Individual and group stability in neutral restrictions of hedonic games. Mathematical Social Sciences, 78, 1 - 5.
  • Sung, S. C. and Dimitrov, D., (2007). On myopic stability concepts for hedonic games. Theory and Decision, 62(1), 31 - 45.
  • Sung, S. C. and Dimitrov, D., (2010). Computational complexity in additive hedonic games. European Journal of Operational Research, 203(3), 635 - 639.
  • Suzuki, K. and Sung, S. C., (2010). Hedonic coalition formation in conservative societies. Available at SSRN: https://ssrn.com/abstract=1700921.
  • 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.
Year 2023, Volume: 12 Issue: 1, 45 - 58, 31.03.2023
https://doi.org/10.17261/Pressacademia.2023.1725

Abstract

References

  • Alcalde, J. and Revilla, P., (2004). Researching with whom? Stability and manipulation. Journal of Mathematical Economics, 40(8), 869 - 887.
  • 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)
  • 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)
  • 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.
  • Ballester, C., (2004). NP-completeness in hedonic games. Games and Economic Behavior, 49(1), 1 - 30.
  • Banerjee, S., Konishi, H., and Sönmez, T., (2001). Core in a simple coalition formation game. Social Choice and Welfare, 18, 135 - 153.
  • 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.
  • Bogomolnaia, A. and Jackson, M., (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38, 201 - 230.
  • Burani, N. and Zwicker, W. S., (2003). Coalition formation games with separable preferences. Mathematical Social Sciences, 45(1), 27 - 52.
  • Czarnecki, E. and Dutta, A., (2021). Scalable hedonic coalition formation for task allocation with heterogeneous robots. Intelligent Service Robotics, 14, 501 – 517.
  • Diamantoudi, E. and Xue, L., (2003). Farsighted stability in hedonic games. Social Choice and Welfare, 21, 39 – 61.
  • 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.
  • 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)
  • Dimitrov, D. and Sung, S. C., (2006). Top responsiveness and Nash stability in coalition formation games. Kybernetika, 42(4), 453 - 460.
  • Drèze, J. and Greenberg, J., (1980). Hedonic coalitions: Optimality and stability. Econometrica, 48, 987 - 1003.
  • Farrell, J. and Scotchmer, S., (1988). Partnerships. The Quarterly Journal of Economics, 103(2), 279 - 297.
  • Gale, D. and Shapley, L. S., (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9 - 15.
  • Hajduková, J., (2006). Coalition formation games: A survey. International Game Theory Review, 8(4), 613 - 641.
  • 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.
  • Karakaya, M., (2011). Hedonic coalition formation games: A new stability notion. Mathematical Social Sciences, 61(3), 157 - 165.
  • 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.
  • Olsen, M., (2009). Nash stability in additively separable hedonic games and community structures. Theory of Computing Systems, 45(4), 917 - 925.
  • Pápai, S., (2007). Individual stability in hedonic coalition formation. Research Papers, Concordia University, Montreal, Quebec.
  • 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.
  • Sertel, M. R., (1992). Membership property rights, efficiency, and stability. Research Papers, Boğaziçi University, Istanbul.
  • Suksompong, W., (2015). Individual and group stability in neutral restrictions of hedonic games. Mathematical Social Sciences, 78, 1 - 5.
  • Sung, S. C. and Dimitrov, D., (2007). On myopic stability concepts for hedonic games. Theory and Decision, 62(1), 31 - 45.
  • Sung, S. C. and Dimitrov, D., (2010). Computational complexity in additive hedonic games. European Journal of Operational Research, 203(3), 635 - 639.
  • Suzuki, K. and Sung, S. C., (2010). Hedonic coalition formation in conservative societies. Available at SSRN: https://ssrn.com/abstract=1700921.
  • 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.
There are 30 citations in total.

Details

Primary Language English
Subjects Economics, Finance, Business Administration
Journal Section Articles
Authors

Mehmet Karakaya 0000-0002-9495-2242

Seckin Ozbılen 0000-0001-8230-9789

Publication Date March 31, 2023
Published in Issue Year 2023 Volume: 12 Issue: 1

Cite

APA Karakaya, M., & Ozbılen, S. (2023). HEDONIC COALITION FORMATION GAMES: NASH STABILITY UNDER DIFFERENT MEMBERSHIP RIGHTS. Journal of Business Economics and Finance, 12(1), 45-58. https://doi.org/10.17261/Pressacademia.2023.1725

Journal of Business, Economics and Finance (JBEF) is a scientific, academic, double blind peer-reviewed, quarterly and open-access journal. The publication language is English. The journal publishes four issues a year. The issuing months are March, June, September and December. The journal aims to provide a research source for all practitioners, policy makers and researchers working in the areas of business, economics and finance. The Editor of JBEF invites all manuscripts that that cover theoretical and/or applied researches on topics related to the interest areas of the Journal. JBEF charges no submission or publication fee.



Ethics Policy - JBEF applies the standards of Committee on Publication Ethics (COPE). JBEF is committed to the academic community ensuring ethics and quality of manuscripts in publications. Plagiarism is strictly forbidden and the manuscripts found to be plagiarized will not be accepted or if published will be removed from the publication. Authors must certify that their manuscripts are their original work. Plagiarism, duplicate, data fabrication and redundant publications are forbidden. The manuscripts are subject to plagiarism check by iThenticate or similar. All manuscript submissions must provide a similarity report (up to 15% excluding quotes, bibliography, abstract, method).


Open Access - All research articles published in PressAcademia Journals are fully open access; immediately freely available to read, download and share. Articles are published under the terms of a Creative Commons license which permits use, distribution and reproduction in any medium, provided the original work is properly cited. Open access is a property of individual works, not necessarily journals or publishers. Community standards, rather than copyright law, will continue to provide the mechanism for enforcement of proper attribution and responsible use of the published work, as they do now.