Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation

Abstract : We consider fractional hedonic games, a subclass of coalition formation games that can be succinctly modeled by means of a graph in which nodes represent agents and edge weights the degree of preference of the corresponding endpoints. The happiness or utility of an agent for being in a coalition is the average value she ascribes to its members. We adopt Nash stable outcomes as the target solution concept; that is we focus on states in which no agent can improve her utility by unilaterally changing her own group. We provide existence, efficiency and complexity results for games played on both general and specific graph topologies. As to the efficiency results, we mainly study the quality of the best Nash stable outcome and refer to the ratio between the social welfare of an optimal coalition structure and the one of such an equilibrium as to the price of stability. In this respect, we remark that a best Nash stable outcome has a natural meaning of stability, since it is the optimal solution among the ones which can be accepted by selfish agents. We provide upper and lower bounds on the price of stability for different topologies, both in case of weighted and unweighted edges. Beside the results for general graphs, we give refined bounds for various specific cases, such as triangle-free, bipartite graphs and tree graphs. For these families, we also show how to efficiently compute Nash stable outcomes with provable good social welfare.
Document type :
Journal articles
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download
Contributor : Anne l'Azou <>
Submitted on : Wednesday, April 3, 2019 - 4:43:08 PM
Last modification on : Thursday, November 14, 2019 - 10:30:06 AM


Fanelli 2018 Nash Stable Outco...
Publisher files allowed on an open archive



Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, Luca Moscardelli. Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation. Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2018, 62, pp.315-371. ⟨10.1613/jair.1.11211⟩. ⟨hal-02089363⟩



Record views


Files downloads