TY - GEN
T1 - Pareto optimality in coalition formation
AU - Aziz, Haris
AU - Brandt, Felix
AU - Harrenstein, Paul
PY - 2011
Y1 - 2011
N2 - A minimal requirement on allocative efficiency in the social sciences is Pareto optimality. In this paper, we identify a far-reaching structural connection between Pareto optimal and perfect partitions that has various algorithmic consequences for coalition formation. In particular, we show that computing and verifying Pareto optimal partitions in general hedonic games and B-hedonic games is intractable while both problems are tractable for roommate games and W-hedonic games. The latter two positive results are obtained by reductions to maximum weight matching and clique packing, respectively.
AB - A minimal requirement on allocative efficiency in the social sciences is Pareto optimality. In this paper, we identify a far-reaching structural connection between Pareto optimal and perfect partitions that has various algorithmic consequences for coalition formation. In particular, we show that computing and verifying Pareto optimal partitions in general hedonic games and B-hedonic games is intractable while both problems are tractable for roommate games and W-hedonic games. The latter two positive results are obtained by reductions to maximum weight matching and clique packing, respectively.
UR - http://www.scopus.com/inward/record.url?scp=80054048306&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-24829-0_10
DO - 10.1007/978-3-642-24829-0_10
M3 - Conference contribution
AN - SCOPUS:80054048306
SN - 9783642248283
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 93
EP - 104
BT - Algorithmic Game Theory - 4th International Symposium, SAGT 2011, Proceedings
T2 - 4th International Symposium on Algorithmic Game Theory, SAGT 2011
Y2 - 17 October 2011 through 19 October 2011
ER -