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...
Główni autorzy: | , , |
---|---|
Format: | Conference item |
Język: | English |
Wydane: |
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 |