Price of Pareto Optimality in hedonic games

Edith Elkind, Angelo Fanelli () and Michele Flammini
Additional contact information
Edith Elkind: University of Oxford
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: GSSI - Gran Sasso Science Institute

Post-Print from HAL

Abstract: The Price of Anarchy measures the welfare loss caused by selfish behavior: it is defined as the ratio of the social welfare in a socially optimal outcome and in a worst Nash equilibrium. Similar measures can be derived for other classes of stable outcomes. We observe that Pareto optimality can be seen as a notion of stability: an outcome is Pareto optimal if and only if it does not admit a deviation by the grand coalition that makes all players weakly better off and some players strictly better off. Motivated by this observation, we introduce the concept of Price of Pareto Optimality: this is an analogue of the Price of Anarchy, with the worst Nash equilibrium replaced with the worst Pareto optimal outcome. We then study this concept in the context of hedonic games, and provide lower and upper bounds on the Price of Pareto Optimality in three classes of hedonic games: additively separable hedonic games, fractional hedonic games, and modified fractional hedonic games. © 2020 Elsevier B.V.

Keywords: Coalition formation; Hedonic games; Pareto optimality; Price of Pareto Optimality (search for similar items in EconPapers)
Date: 2020-11
Note: View the original document on HAL open archive server: https://hal.science/hal-02932135
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Published in Artificial Intelligence, 2020, 288, pp.103357. ⟨10.1016/j.artint.2020.103357⟩

Downloads: (external link)
https://hal.science/hal-02932135/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-02932135

DOI: 10.1016/j.artint.2020.103357

Access Statistics for this paper

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