Pareto optimality in coalition formation

• 成果类型: Article
• 署名作者: Aziz, Haris; Brandt, Felix; Harrenstein, Paul
• 署名单位: Australian National University; University of New South Wales Sydney; Technical University of Munich; University of Oxford
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2013.08.006
• 发表日期: 2013
• 页码: 562-581
• 关键词: Coalition formation; hedonic games; Pareto optimality; computational complexity

摘要

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 (PM) 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. (C) 2013 Elsevier Inc. All rights reserved.