Portal de Periódicos da CAPES

Pareto optimality in coalition formation

2013; Elsevier BV; Volume: 82; Linguagem: Inglês

10.1016/j.geb.2013.08.006

1090-2473

Haris Aziz, Felix Brandt, Paul Harrenstein,

Auction Theory and Applications

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.