Distance hedonic games

In this paper we consider Distance Hedonic Games, a class of nontransferable utility coalition formation games that properly generalizes previously existing models, like Social Distance Games and Fractional Hedonic Games. In particular, in Distance Hedonic Games we assume the existence of a scoring vector α, in which the i-th coefficient αi expresses the extent to which x contributes to the utility of y if they are at distance i. We focus on Nash stable outcomes and consider two natural scenarios for the scoring vector: monotonically decreasing and monotonically increasing coefficients. In both cases we give NP-hardness and inapproximability results for the problems of finding a social optimum and a best Nash stable outcome. Moreover, we characterize the topologies of coalitions with high social welfare and give bounds on the Price of Anarchy and on the Price of Stability.