On Pareto Optimality in Social Distance Games

We investigate Pareto stability in Social Distance Games, that are coalition forming games in which agents utilities are proportional to their harmonic centralities in the respective coalitions, i.e., to the average inverse distance from the other agents. Pareto optimal solutions have been already consid- ered in the literature as outcomes arising from the strategic interaction of the agents. In particular, they are stable un- der the deviation of the grand coalition, as they do not per- mit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. We first show that, while computing a Pareto stable solution maximiz- ing the social welfare is NP-hard in bounded degree graphs, a 2min{Δ,√n}-approximating one can be determined in polynomial time, where n is the number of agents and Δ the maximum node degree. We then determine asymptotically tight bounds on the Price of Pareto Optimality for several classes of social graphs arising from the following combina- tions: unbounded and bounded node degree, undirected and directed edges, unweighted and weighted edges.