Core stability in altruistic coalition formation games. (English) Zbl 07857879
Soto, José A. (ed.) et al., Latin 2024: theoretical informatics. 16th Latin American symposium, Puerto Varas, Chile, March 18–22, 2024. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 14579, 320-333 (2024).
Summary: Coalition formation games model settings where sets of agents have to partition into groups. We study the notion of core stability in the context of altruistic coalition formation games (ACFGs). While in most commonly studied classes of coalition formation games agents seek to maximize their individual valuations, agents are not completely selfish in ACFGs. Given some underlying network of friendship, the agents also take into account their friends’ valuations when comparing different coalitions or coalition structures. The notion of the core has been extensively studied for several classes of (hedonic) coalition formation games. Kerkmann and Rothe [7] initiated the study of core stability in ACFGs. They showed that verifying core stability is coNP-complete for selfish-first ACFGs – their least altruistic case of ACFGs. The complexity of the other two (more altruistic) degrees of altruism, however, remained an open problem. We show that the core stability verification problem is coNP-complete for all cases of ACFGs, i.e., for all three degrees of altruism and for both sum-based and minimum-based aggregation of the friends’ preferences.
For the entire collection see [Zbl 1539.68038].
For the entire collection see [Zbl 1539.68038].
MSC:
| 68Qxx | Theory of computing |
| 68Rxx | Discrete mathematics in relation to computer science |
| 68Wxx | Algorithms in computer science |
References:
| [1] | Banerjee, S.; Konishi, H.; Sönmez, T., Core in a simple coalition formation game, Soc. Choice Welfare, 18, 1, 135-153, 2001 · Zbl 1069.91504 · doi:10.1007/s003550000067 |
| [2] | Bullinger, M., Kober, S.: Loyalty in cardinal hedonic games. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence, pp. 66-72. ijcai.org (2021) |
| [3] | Dimitrov, D.; Borm, P.; Hendrickx, R.; Sung, S., Simple priorities and core stability in hedonic games, Soc. Choice Welfare, 26, 2, 421-433, 2006 · Zbl 1158.91310 · doi:10.1007/s00355-006-0104-4 |
| [4] | Gonzalez, T., Clustering to minimize the maximum intercluster distance, Theor. Comput. Sci., 38, 293-306, 1985 · Zbl 0567.62048 · doi:10.1016/0304-3975(85)90224-5 |
| [5] | Kerkmann, A., Cramer, S., Rothe, J.: Altruism in coalition formation games. Annals Math. Artifi. Intell. (2024). doi:10.1007/s10472-023-09881-y · Zbl 07904646 |
| [6] | Kerkmann, A., et al.: Altruistic hedonic games. J. Artif. Intell. Res. 75, 129-169 (2022) · Zbl 1542.91012 |
| [7] | Kerkmann, A., Rothe, J.: Altruism in coalition formation games. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence, pp. 347-353. ijcai.org (2020) |
| [8] | Munagala, K., Shen, Y., Wang, K.: Auditing for core stability in participatory budgeting. In: Hansen, K., Liu, T.X., Malekian, A. (eds.) WINE 2022. LNCS, vol. 13778, pp. 292-310. Springer, Cham (2022). doi:10.1007/978-3-031-22832-2_17 · Zbl 1533.91183 |
| [9] | Nguyen, N., Rey, A., Rey, L., Rothe, J., Schend, L.: Altruistic hedonic games. In: Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, pp. 251-259. IFAAMAS (2016) |
| [10] | Peters, D.: Precise complexity of the core in dichotomous and additive hedonic games. In: Rothe, J. (ed.) Algorithmic Decision Theory. ADT 2017. LNCS, vol. 10576, pp. 214-227. Springer, Cham (2017). doi:10.1007/978-3-319-67504-6_15 · Zbl 1398.91044 |
| [11] | 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. Math. Artif. Intell., 77, 3, 317-333, 2016 · Zbl 1371.68121 · doi:10.1007/s10472-015-9461-y |
| [12] | Rothe, J.: Thou shalt love thy neighbor as thyself when thou playest: Altruism in game theory. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence, pp. 15070-15077. AAAI Press (2021) |
| [13] | Sung, S.; Dimitrov, D., On core membership testing for hedonic coalition formation games, Oper. Res. Lett., 35, 2, 155-158, 2007 · Zbl 1303.91035 · doi:10.1016/j.orl.2006.03.011 |
| [14] | Woeginger, G., A hardness result for core stability in additive hedonic games, Math. Soc. Sci., 65, 2, 101-104, 2013 · Zbl 1260.91035 · doi:10.1016/j.mathsocsci.2012.10.001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
