Pareto optimality in coalition formation
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.
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Matthew O. Jackson & Asher Wolinsky, 1994.
"A Strategic Model of Social and Economic Networks,"
1098, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- ALCADE-UNZU, Jorge & MOLIS, Elena, .
"Exchange of indivisible goods and indifferences: the top trading absorbing sets mechanisms,"
CORE Discussion Papers RP
2331, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- Alcalde-Unzu, Jorge & Molis, Elena, 2011. "Exchange of indivisible goods and indifferences: The Top Trading Absorbing Sets mechanisms," Games and Economic Behavior, Elsevier, vol. 73(1), pages 1-16, September.
- ALCALDE-UNZU, Jorge & MOLIS, Elena, 2009. "Exchange of indivisible goods and indifferences: the Top Trading Absorbing Sets mechanisms," CORE Discussion Papers 2009062, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
- Abdulkadiroglu, Atila & Sonmez, Tayfun, 1999. "House Allocation with Existing Tenants," Journal of Economic Theory, Elsevier, vol. 88(2), pages 233-260, October.
- Aytek Erdil & Haluk Ergin, 2007.
"What`s the Matter with Tie-breaking? Improving Efficiency in School Choice,"
Economics Series Working Papers
349, University of Oxford, Department of Economics.
- Aytek Erdil & Haluk Ergin, 2008. "What's the Matter with Tie-Breaking? Improving Efficiency in School Choice," American Economic Review, American Economic Association, vol. 98(3), pages 669-89, June.
- Hideo Konishi & Thomas Quint & Jun Wako, 2000.
"On the Shapley-Scarf Economy: The Case of Multiple Types of Indivisible Goods,"
Boston College Working Papers in Economics
484, Boston College Department of Economics.
- Konishi, Hideo & Quint, Thomas & Wako, Jun, 2001. "On the Shapley-Scarf economy: the case of multiple types of indivisible goods," Journal of Mathematical Economics, Elsevier, vol. 35(1), pages 1-15, February.
- Tayfun Sönmez & M. Utku Ünver, 2009. "Matching, Allocation, and Exchange of Discrete Resources," Boston College Working Papers in Economics 717, Boston College Department of Economics.
- Dreze, J H & Greenberg, J, 1980. "Hedonic Coalitions: Optimality and Stability," Econometrica, Econometric Society, vol. 48(4), pages 987-1003, May.
- Tayfun Sönmez & Suryapratim Banerjee & Hideo Konishi, 2001.
"Core in a simple coalition formation game,"
Social Choice and Welfare,
Springer, vol. 18(1), pages 135-153.
- Masarani, F. & Gokturk, S. S., 1991. "A problem in discrete distributive justice," Economics Letters, Elsevier, vol. 36(3), pages 253-256, July.
- Alcalde, Jose & Barbera, Salvador, 1994.
"Top Dominance and the Possibility of Strategy-Proof Stable Solutions to Matching Problems,"
Springer, vol. 4(3), pages 417-35, May.
- Alcalde, J. & Barberà, S., 1992. "Top Dominance and the Possibility of Strategy-Proof Stable Solutions to Matching Problems," UFAE and IAE Working Papers 196.92, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
- Ballester, Coralio, 2004. "NP-completeness in hedonic games," Games and Economic Behavior, Elsevier, vol. 49(1), pages 1-30, October.
- Tim Roughgarden, 2010. "Computing equilibria: a computational complexity perspective," Economic Theory, Springer, vol. 42(1), pages 193-236, January.
- Bogomolnaia, Anna & Jackson, Matthew O., 2002. "The Stability of Hedonic Coalition Structures," Games and Economic Behavior, Elsevier, vol. 38(2), pages 201-230, February.
- Atila Abdulkadiroglu & Tayfun Sonmez, 1998. "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems," Econometrica, Econometric Society, vol. 66(3), pages 689-702, May.
- Morrill, Thayer, 2010. "The roommates problem revisited," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1739-1756, September.
When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:82:y:2013:i:c:p:562-581. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
If references are entirely missing, you can add them using this form.