TY - JOUR
T1 - Pareto optimality in coalition formation
AU - Aziz, Haris
AU - Brandt, Felix
AU - Harrenstein, Paul
N1 - Funding Information:
This material is based on work supported by the Deutsche Forschungsgemeinschaft under grants BR-2312/6-1 (within the European Science Foundationʼs EUROCORES program LogICCC ), BR 2312/7-1 , and BR 2312/9-1 . Preliminary results of this paper were presented at the IJCAI Workshop on Social Choice and Artificial Intelligence (Barcelona, July 2011), the 4th International Symposium on Algorithmic Game Theory (Amalfi, October 2011), the Workshop on Multi-Agent Organisation (Leiden, December 2011), the Dagstuhl Seminar on Computation and Incentives in Social Choice (Dagstuhl, March 2012), and the Optimization and Incentives Seminar (Cambridge, February 2013).
PY - 2013/11
Y1 - 2013/11
N2 - 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.
AB - 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.
KW - Coalition formation
KW - Computational complexity
KW - Hedonic games
KW - Pareto optimality
UR - http://www.scopus.com/inward/record.url?scp=84884946144&partnerID=8YFLogxK
U2 - 10.1016/j.geb.2013.08.006
DO - 10.1016/j.geb.2013.08.006
M3 - Article
AN - SCOPUS:84884946144
SN - 0899-8256
VL - 82
SP - 562
EP - 581
JO - Games and Economic Behavior
JF - Games and Economic Behavior
ER -