We consider fractional hedonic games, where self-organized groups (orclusters) are created as a result of the strategic interactions ofindependent and selfish players and the happiness of each player ina group is the average value she ascribes to its members. We adoptNash stable outcomes, that is states where no player can improve her utility by unilaterallychanging her own group, as the target solution concept. We study thequality of the best Nash stable outcome and refer to the ratio ofits social welfare to the one of an optimal clustering as to the price of stability. Weremark that a best Nash stable outcome has a natural meaning ofstability 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
;
2015-01-01
Abstract
We consider fractional hedonic games, where self-organized groups (orclusters) are created as a result of the strategic interactions ofindependent and selfish players and the happiness of each player ina group is the average value she ascribes to its members. We adoptNash stable outcomes, that is states where no player can improve her utility by unilaterallychanging her own group, as the target solution concept. We study thequality of the best Nash stable outcome and refer to the ratio ofits social welfare to the one of an optimal clustering as to the price of stability. Weremark that a best Nash stable outcome has a natural meaning ofstability 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
