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. A similar measure can be derived for other classes of stable outcomes. In this paper, we argue that Pareto optimality can be seen as a notion of stability, and introduce the concept of Price of Pareto Optimality: This is an analogue of the Price of Anarchy, where the maximum is computed over the class of Pareto optimal outcomes, i.e., outcomes that do not permit a deviation by the grand coalition that makes all players weakly better off and some players strictly better off. As a case study, we focus on hedonic games, and provide lower and upper bounds of the Price of Pareto Optimality in three classes of hedonic games: Additively separable hedonic games, fractional hedonic games, and modified fractional hedonic games; for fractional hedonic games on trees our bounds are tight.

Price of pareto optimality in hedonic games

FLAMMINI, MICHELE
2016-01-01

Abstract

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. A similar measure can be derived for other classes of stable outcomes. In this paper, we argue that Pareto optimality can be seen as a notion of stability, and introduce the concept of Price of Pareto Optimality: This is an analogue of the Price of Anarchy, where the maximum is computed over the class of Pareto optimal outcomes, i.e., outcomes that do not permit a deviation by the grand coalition that makes all players weakly better off and some players strictly better off. As a case study, we focus on hedonic games, and provide lower and upper bounds of the Price of Pareto Optimality in three classes of hedonic games: Additively separable hedonic games, fractional hedonic games, and modified fractional hedonic games; for fractional hedonic games on trees our bounds are tight.
9781577357605
Artificial Intelligence; Algorithmic Game Theory; Pareto Optimality; Hedonic Games
File in questo prodotto:
File Dimensione Formato  
2016_30thAAAICon_Elkind.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Accesso gratuito
Dimensione 662.25 kB
Formato Adobe PDF
662.25 kB Adobe PDF Visualizza/Apri

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/3276
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 23
social impact