We consider fractional hedonic games, where self-organized groups (or clusters) are created as a result of the strategic interactions of independent and selfish players and the happiness of each player in a group is the average value she ascribes to its members. We adopt Nash stable outcomes, that is states where no player can improve her utility by unilaterally changing her own group, as the target solution concept. We study the quality of the best Nash stable outcome and refer to the ratio of its social welfare to the one of an optimal clustering as to the price of stability. 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 users. We provide upper and lower bounds on the price of stability for games played on different network topologies. In particular, we give an almost tight bound (up to a 0.026 additive factor) for bipartite graphs and suitable bounds on more general families of graphs.

On the Price of Stability of Fractional Hedonic Games

FLAMMINI, MICHELE;MONACO, Gianpiero;
2015

Abstract

We consider fractional hedonic games, where self-organized groups (or clusters) are created as a result of the strategic interactions of independent and selfish players and the happiness of each player in a group is the average value she ascribes to its members. We adopt Nash stable outcomes, that is states where no player can improve her utility by unilaterally changing her own group, as the target solution concept. We study the quality of the best Nash stable outcome and refer to the ratio of its social welfare to the one of an optimal clustering as to the price of stability. 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 users. We provide upper and lower bounds on the price of stability for games played on different network topologies. In particular, we give an almost tight bound (up to a 0.026 additive factor) for bipartite graphs and suitable bounds on more general families of graphs.
978-1-4503-3413-6
File in questo prodotto:
File Dimensione Formato  
fp448-moscardelli-main.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 345.67 kB
Formato Adobe PDF
345.67 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: http://hdl.handle.net/11697/42194
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 28
  • ???jsp.display-item.citation.isi??? 23
social impact