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.

Price of Pareto Optimality in hedonic games

Flammini, Michele
2020

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.
File in questo prodotto:
File Dimensione Formato  
2020_ArtifIntell _288_Elkind.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 748.24 kB
Formato Adobe PDF
748.24 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/14373
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? ND
social impact