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. 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
{"_id":"WSAdpygP6cHWcSECC","bibbaseid":"edith-angelo-michele-priceofparetooptimalityinhedonicgames-2016","authorIDs":[],"author_short":["Edith, E.","ANGELO, F.","MICHELE, F."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","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":[{"firstnames":["Elkind"],"propositions":[],"lastnames":["Edith"],"suffixes":[]},{"firstnames":["FANELLI"],"propositions":[],"lastnames":["ANGELO"],"suffixes":[]},{"firstnames":["FLAMMINI"],"propositions":[],"lastnames":["MICHELE"],"suffixes":[]}],"editor":[{"firstnames":["Dale","Schuurmans","Michael"],"propositions":[],"lastnames":["Wellman"],"suffixes":[]}],"year":"2016","pages":"475–481","annote":"Contributo in Atti di convegno","bibtex":"@inproceedings{elkind_edith_price_2016,\n\ttitle = {Price of pareto optimality in hedonic games},\n\tisbn = {978-1-57735-760-5},\n\turl = {http://www.aaai.org/ocs/index.php/AAAI/AAAI16/schedConf/presentations},\n\tabstract = {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.},\n\tbooktitle = {30th {AAAI} {Conference} on {Artificial} {Intelligence}, {AAAI} 2016},\n\tpublisher = {AAAI PRESS},\n\tauthor = {Elkind Edith and FANELLI ANGELO and FLAMMINI MICHELE},\n\teditor = {Dale Schuurmans Michael Wellman},\n\tyear = {2016},\n\tpages = {475--481},\n\tannote = {Contributo in Atti di convegno},\n}\n\n","author_short":["Edith, E.","ANGELO, F.","MICHELE, F."],"editor_short":["Wellman, D. S. M."],"key":"elkind_edith_price_2016","id":"elkind_edith_price_2016","bibbaseid":"edith-angelo-michele-priceofparetooptimalityinhedonicgames-2016","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/AAAI/AAAI16/schedConf/presentations"},"downloads":0},"bibtype":"inproceedings","biburl":"https://drive.google.com/uc?export=download&id=1Yz9Tay6l8reLuIpeLRQenrn7GKZ--M4o","creationDate":"2020-11-08T19:41:14.294Z","downloads":0,"keywords":[],"search_terms":["price","pareto","optimality","hedonic","games","edith","angelo","michele"],"title":"Price of pareto optimality in hedonic games","year":2016,"dataSources":["3w7wESM3KavuMMg2b"]}