On the performance of stable outcomes in modified fractional hedonic games with egalitarian social welfare

In this paper we consider modified fractional hedonlc games, that are coalition formation games defined over an undirected edge-weighted graph G = (N, E, w), where N is the set of agents and for any edge {u.v} E, wu = wu-u reflects how much agents u and v benefit from belonging to the same coalition More specifically, given a coalition structure, Le., a partition of the agents into coalitions, the utility of an agent u is given by the sum of wu over all other agents v belonging to the same coalition of u averaged over all other members of that coalition, i.e., excluding herself We focus on common stability notions: We are interested in strong Nash stable, Nash stable and core stable outcomes In [18], the existence of these natural outcomes for modified fractional hedonic games is completely characterized; moreover, many tight or asymptotically tight results on their performance are shown for the classical utilitarian social welfare function, that is defined as the sum of all agents' utilities Motivated by the fact that an outcome with an high utilitarian social welfare could be extremely harsh for some agents, we pro-vide a comprehensive analysis on the performance of strong Nash stable, Nash stable and core stable outcomes for modified fractional hedonic games under the egalitarian social welfare function, that is defined as the minimum among all agents' utilities.