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

Vittorio Bilò (), Angelo Fanelli (), Michele Flammini (), Gianpiero Monaco () and Luca Moscardelli ()
Additional contact information
Vittorio Bilò: Dipartimento di Matematica Ennio De Giorgi - Università del Salento = University of Salento [Lecce], Università del Salento = University of Salento [Lecce]
Angelo Fanelli: CREM - Centre de recherche en économie et management - UNICAEN - Université de Caen Normandie - NU - Normandie Université - UR - Université de Rennes - CNRS - Centre National de la Recherche Scientifique
Michele Flammini: DISIM - Dipartimento di Ingegneria, Scienza dell'Informazione e Matematica - UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila, UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila
Gianpiero Monaco: DI - Dipartimento di Informatica [Italy] - UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila
Luca Moscardelli: Department of Economic Studies - University of Chieti-Pescara, Dipartimento di Scienze - Universita di Chieti-Pescara - UNICH - Universita' degli Studi "G. d'Annunzio" Chieti-Pescara

Post-Print from HAL

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.

Date: 2018-05-13
New Economics Papers: this item is included in nep-gth and nep-hap
Note: View the original document on HAL open archive server: https://hal.science/hal-02089363v1
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Published in Journal of Artificial Intelligence Research, 2018, 62, pp.315-371. ⟨10.1613/jair.1.11211⟩

Downloads: (external link)
https://hal.science/hal-02089363v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-02089363

DOI: 10.1613/jair.1.11211

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().