Price of pareto optimality in hedonic games. Edith, E., ANGELO, F., & MICHELE, F. In 30th AAAI Conference on Artificial Intelligence, AAAI 2016, pages 475–481, 2016. AAAI PRESS.
Price of pareto optimality in hedonic games [link]Paper  abstract   bibtex   
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.
@inproceedings{elkind_edith_price_2016,
	title = {Price of pareto optimality in hedonic games},
	isbn = {978-1-57735-760-5},
	url = {http://www.aaai.org/ocs/index.php/AAAI/AAAI16/schedConf/presentations},
	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.},
	booktitle = {30th {AAAI} {Conference} on {Artificial} {Intelligence}, {AAAI} 2016},
	publisher = {AAAI PRESS},
	author = {Elkind Edith and FANELLI ANGELO and FLAMMINI MICHELE},
	editor = {Dale Schuurmans Michael Wellman},
	year = {2016},
	pages = {475--481},
	annote = {Contributo in Atti di convegno},
}

Downloads: 0