Welfare Maximization in Fractional Hedonic Games
Aziz, Haris (NICTA and University of New South Wales) | Gaspers, Serge (NICTA and University of New South Wales) | Gudmundsson, Joachim (University of Sydney) | Mestre, Julian (University of Sydney) | Taubig, Hanjo (TU Munich)
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.
Jul-15-2015
- Technology: