Price of pareto optimality in hedonic games
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...
| Prif Awduron: | , , |
|---|---|
| Fformat: | Conference item |
| Iaith: | English |
| Cyhoeddwyd: |
AAAI Press
2016
|
| _version_ | 1826300198449577984 |
|---|---|
| author | Elkind, E Fanelli, A Flammini, M |
| author_facet | Elkind, E Fanelli, A Flammini, M |
| author_sort | Elkind, E |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T05:13:32Z |
| format | Conference item |
| id | oxford-uuid:dc5c4792-c12a-49f8-9fe7-26d6a64302fe |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T05:13:32Z |
| publishDate | 2016 |
| publisher | AAAI Press |
| record_format | dspace |
| spelling | oxford-uuid:dc5c4792-c12a-49f8-9fe7-26d6a64302fe2022-03-27T09:17:21ZPrice of pareto optimality in hedonic gamesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:dc5c4792-c12a-49f8-9fe7-26d6a64302feEnglishSymplectic Elements at OxfordAAAI Press2016Elkind, EFanelli, AFlammini, MPrice 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. |
| spellingShingle | Elkind, E Fanelli, A Flammini, M Price of pareto optimality in hedonic games |
| title | Price of pareto optimality in hedonic games |
| title_full | Price of pareto optimality in hedonic games |
| title_fullStr | Price of pareto optimality in hedonic games |
| title_full_unstemmed | Price of pareto optimality in hedonic games |
| title_short | Price of pareto optimality in hedonic games |
| title_sort | price of pareto optimality in hedonic games |
| work_keys_str_mv | AT elkinde priceofparetooptimalityinhedonicgames AT fanellia priceofparetooptimalityinhedonicgames AT flamminim priceofparetooptimalityinhedonicgames |