On Pareto optimality in social distance games

摘要

We investigate Pareto stability in Social Distance Games (SDGs), which are coalition formation games where 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 already been considered in the literature as outcomes arising from the strategic interaction of the self-interested agents. In particular, they are stable under the deviation of the grand coalition, as they do not permit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. First, by providing a polynomial-time reduction from the NP-complete Restricted Exact 3-Cover by 3-Sets problem, we prove that computing a Pareto stable solution for a SDG maximizing the social welfare is NP-hard also in bounded degree graphs. Then, we show that a 2min⁡(Δ,n)-approximating solution can be determined in polynomial time, where n is the number of agents and Δ the maximum node degree. Moreover, we provide asymptotically tight bounds on the price of Pareto optimality for several classes of social graphs arising from the following combinations: unbounded and bounded node degree, undirected and directed arcs, unweighted and weighted arcs.