Abstract
In this paper we consider Distance Hedonic Games (DHGs), a class of non-transferable utility coalition formation games that properly generalizes previously existing models, like Social Distance Games (SDGs) and unweighted Fractional Hedonic Games (FHGs). In particular, in DHGs we assume the existence of a scoring vector \(\alpha \), in which the i-th coefficient \(\alpha _i\) expresses the extent to which an agent x contributes to the utility of an agent y if they are at distance i. We focus on Nash stable outcomes in the arising games, i.e., on coalition structures in which no agent can unilaterally improve her gain by deviating.
We consider two different natural scenarios for the scoring vector, with monotonically increasing and monotonically decreasing coefficients. In both cases we give NP-hardness and inapproximability results on the problems of finding a social optimum and a best Nash stable outcome. Moreover, we characterize the topologies of coalitions that provide high social welfare and consequently give suitable bounds on the Price of Anarchy and on the Price of 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
Notes
- 1.
The girth of a graph is the length of the shortest cycle contained in it.
References
Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008)
Aziz, H., Brandl, F., Brandt, F., Harrenstein, P., Olsen, M., Peters, D.: Fractional hedonic games. ACM Trans. Econ. Comput. 7(2), 6:1–6:29 (2019)
Aziz, H., Gaspers, S., Gudmundsson, J., Mestre, J., Täubig, H.: Welfare maximization in fractional hedonic games. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pp. 461–467 (2015)
Balliu, A., Flammini, M., Melideo, G., Olivetti, D.: On non-cooperativeness in social distance games. J. Artif. Intell. Res. 66, 625–653 (2019)
Balliu, A., Flammini, M., Olivetti, D.: On pareto optimality in social distance games. In: Proceedings of the 31st Conference on Artificial Intelligence (AAAI), pp. 349–355 (2017)
Banerjee, S., Konishi, H., Sönmez, T.: Core in a simple coalition formation game. Soc. Choice Welf. 18(1), 135–153 (2001)
Bilò, V., Fanelli, A., Flammini, M., Monaco, G., Moscardelli, L.: On the price of stability of fractional hedonic games. In: Proceedings of the 14th Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 1239–1247 (2015)
Bilò, V., Fanelli, A., Flammini, M., Monaco, G., Moscardelli, L.: Nash stable outcomes in fractional hedonic games: existence, efficiency and computation. J. Artif. Intell. Res. 62, 315–371 (2018)
Bloch, F., Diamantoudi, E.: Noncooperative formation of coalitions in hedonic games. Int. J. Game Theory 40(2), 263–280 (2011)
Bogomolnaia, A., Jackson, M.O.: The stability of hedonic coalition structures. Games Econ. Behav. 38(2), 201–230 (2002)
Brandl, F., Brandt, F., Strobel, M.: Fractional hedonic games: individual and group stability. In: Proceedings of the 14th Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 1219–1227 (2015)
Brânzei, S., Larson, K.: Social distance games. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 91–96 (2011)
Dangalchev, C.: Residual closeness in networks. Phys. Stat. Mech. Appl. 365(2), 556–564 (2006)
Dangalchev, C.: Residual closeness and generalized closeness. Int. J. Found. Comput. Sci. 22(8), 1939–1948 (2011)
Dreze, J., Greenberg, J.: Hedonic coalitions: optimality and stability. Econometrica 48(4), 987–1003 (1980)
Dutton, R.D., Brigham, R.C.: Edges in graphs with large girth. Graphs Comb. 7(4), 315–321 (1991)
Elkind, E., Wooldridge, M.J.: Hedonic coalition nets. In: 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary, 10–15 May 2009, vol. 1, pp. 417–424 (2009)
Feldman, M., Lewin-Eytan, L., Naor, J.: Hedonic clustering games. TOPC 2(1), 4:1–4:48 (2015)
Gairing, M., Savani, R.: Computing stable outcomes in symmetric additively separable hedonic games. Math. Oper. Res. 44(3), 1101–1121 (2019)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)
Kaklamanis, C., Kanellopoulos, P., Patouchas, D.: On the price of stability of social distance games. In: Proceedings of the 11th International Symposium, Algorithmic Game Theory (SAGT), pp. 125–136 (2018)
Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65–69 (2009)
Olsen, M.: On defining and computing communities. In: Proceedings of the 18th Conference on Computing: The Australasian Theory Symposium (CATS), pp. 97–102 (2012)
Papadimitriou, C.H.: Algorithms, games, and the internet. In: Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP), pp. 1–3 (2001)
Wang, Z., Han, X., Dósa, G., Tuza, Z.: A general bin packing game: interest taken into account. Algorithmica 80(5), 1534–1555 (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Flammini, M., Kodric, B., Olsen, M., Varricchio, G. (2021). Distance Hedonic Games. In: Bureš, T., et al. SOFSEM 2021: Theory and Practice of Computer Science. SOFSEM 2021. Lecture Notes in Computer Science(), vol 12607. Springer, Cham. https://doi.org/10.1007/978-3-030-67731-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-67731-2_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-67730-5
Online ISBN: 978-3-030-67731-2
eBook Packages: Computer ScienceComputer Science (R0)