Price of Pareto Optimality in Hedonic Games

Authors

  • Edith Elkind University of Oxford
  • Angelo Fanelli Centre national de la recherche scientifique (CNRS)
  • Michele Flammini Universit degli Studi dell'Aquila and Gran Sasso Science Institute

DOI:

https://doi.org/10.1609/aaai.v30i1.10048

Keywords:

pareto optimality, hedonic games

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.

Downloads

Published

2016-02-21

How to Cite

Elkind, E., Fanelli, A., & Flammini, M. (2016). Price of Pareto Optimality in Hedonic Games. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10048

Issue

Section

Technical Papers: Game Theory and Economic Paradigms