Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5071786 | Games and Economic Behavior | 2013 | 20 Pages |
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.
Related Topics
Social Sciences and Humanities
Economics, Econometrics and Finance
Economics and Econometrics
Authors
Haris Aziz, Felix Brandt, Paul Harrenstein,