Journal article
Pareto optimality in coalition formation
- Abstract:
- A minimal requirement on allocative efficiency in the social sciences is Pareto optimality. In this paper, we identify a close structural connection between Pareto optimality and perfection that has various algorithmic consequences for coalition formation. Based on this insight, we formulate the Preference Refinement Algorithm (PRA) which computes an individually rational and Pareto optimal outcome in hedonic coalition formation games. Our approach also leads to various results for specific classes of hedonic games. In particular, we show that computing and verifying Pareto optimal partitions in general hedonic games, anonymous games, three-cyclic games, room-roommate games and B-hedonic games is intractable while both problems are tractable for roommate games, W-hedonic games, and house allocation with existing tenants.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 431.3KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.geb.2013.08.006
Authors
- Publisher:
- Elsevier
- Journal:
- Games and Economic Behavior More from this journal
- Volume:
- 82
- Pages:
- 562-581
- Publication date:
- 2013-09-03
- DOI:
- ISSN:
-
0899-8256
- Keywords:
- Pubs id:
-
pubs:591933
- UUID:
-
uuid:3a91def3-1c6e-4898-b5bb-7b8c6457da51
- Local pid:
-
pubs:591933
- Source identifiers:
-
591933
- Deposit date:
-
2016-01-20
Terms of use
- Copyright holder:
- Elsevier
- Copyright date:
- 2013
- Notes:
- © 2013 Elsevier Inc. All rights reserved. This is the accepted manuscript version of the article. The final version is available online from Elsevier at: [10.1016/j.geb.2013.08.006]
If you are the owner of this record, you can report an update to it here: Report update to this record