Welfare Maximization in Fractional Hedonic Games / 461
Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Julian Mestre, Hanjo Taubig
PDF

We consider the computational complexity of computing welfare maximizing partitions for fractional hedonic games — a natural class of coalition formation games that can be succinctly represented by a graph. For such games, welfare maximizing partitions constitute desirable ways to cluster the vertices of the graph. We present both intractability results and approximation algorithms for computing welfare maximizing partitions.