Hedonic games are coalition formation games in which coalitions are created as a result of the strategic interaction of independent players. To this day, the literature on non-cooperative hedonic games has considered totally selfish players; our aim is that of defining and studying a new model in which, given a social graph, players also care about the happiness of their friends: we call this class of games social context hedonic games (SCHGs). We consider Nash equilibria of SCHGs, and study their existence, convergence and performance with respect to the classical notions of price of anarchy and price of stability. In particular, we provide an exact potential function for SCHGs implying the existence and convergence to Nash equilibria, and we prove tight or asymptotically tight bounds on the price of anarchy and the price of stability of SCHGs.
Additional Metadata
Keywords Coalition Formation, Hedonic Games, Nash Equilibrium, Price of Anarchy, Price of Stability, Social Context
Conference Italian Conference on Theoretical Computer Science
Citation
Monaco, G, Moscardelli, L, & Velaj, Y. (2018). Hedonic games with social context. In Proceedings of the 19th Italian Conference on Theoretical Computer Science (pp. 24–35).