Journal article
Price of Pareto optimality in hedonic games
- Abstract:
- The 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. Similar measures can be derived for other classes of stable outcomes. We observe that Pareto optimality can be seen as a notion of stability: an outcome is Pareto optimal if and only if it does not admit a deviation by the grand coalition that makes all players weakly better off and some players strictly better off. Motivated by this observation, we introduce the concept of Price of Pareto Optimality: this is an analogue of the Price of Anarchy, with the worst Nash equilibrium replaced with the worst Pareto optimal outcome. We then study this concept in the context of hedonic games, and provide lower and upper bounds on the Price of Pareto Optimality in three classes of hedonic games: additively separable hedonic games, fractional hedonic games, and modified fractional hedonic games.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 653.1KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.artint.2020.103357
Authors
- Publisher:
- Elsevier
- Journal:
- Artificial Intelligence More from this journal
- Volume:
- 288
- Article number:
- 103357
- Publication date:
- 2020-07-27
- Acceptance date:
- 2020-07-16
- DOI:
- ISSN:
-
0004-3702
- Language:
-
English
- Keywords:
- Pubs id:
-
1123012
- Local pid:
-
pubs:1123012
- Deposit date:
-
2020-07-31
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier
- Copyright date:
- 2020
- Rights statement:
- ©2020 Elsevier B.V. All rights reserved.
- Notes:
-
This is the accepted manuscript version of the article. The final version is available from Elsevier at:
10.1016/j.artint.2020.103357
If you are the owner of this record, you can report an update to it here: Report update to this record