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...

Szczegółowa specyfikacja

Opis bibliograficzny
Główni autorzy: Elkind, E, Fanelli, A, Flammini, M
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