Price of pareto optimality in hedonic games

Conference item

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.

Authors: Elkind, E; Fanelli, A; Flammini, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: AAAI Press
• Host title: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16)
• Pages: 475-481
• Publication date: 2016-02-21
• Acceptance date: 2015-11-13
• Event title: 30th AAAI Conference on Artificial Intelligence
• Event location: Phoenix, Arizona, USA
• Event website: https://www.aaai.org/Conferences/AAAI/aaai16.php
• Event start date: 2016-02-12
• Event end date: 2016-02-17
• EISSN: 2374-3468
• ISSN: 2159-5399
• EISBN: 978-1-57735-760-5
• Language: English
• Keywords: hedonic games; pareto optimality