Pareto optimality in coalition formation

Haris Aziz, Felix Brandt, Paul Harrenstein

Research output: Contribution to journalArticlepeer-review

61 Scopus citations

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.

Original languageEnglish
Pages (from-to)562-581
Number of pages20
JournalGames and Economic Behavior
Volume82
DOIs
StatePublished - Nov 2013

Keywords

  • Coalition formation
  • Computational complexity
  • Hedonic games
  • Pareto optimality

Fingerprint

Dive into the research topics of 'Pareto optimality in coalition formation'. Together they form a unique fingerprint.

Cite this