Problem Definition
In the Stable Partition Problem a set of participants has to be split into several disjoint sets called coalitions. The resulting partition should fulfill some stability requirements that take into account the preferences of participants.
Various variants of this problem arise if the participants are required to express their preferences over all the possible coalitions to which they could belong or when only preferences over other players are given and those are then extended to preferences over coalitions. Sometimes one seeks rather a permutation of players and the partition is given by the cycles of the permutation [1, 19].
Notation
An instance of the Stable Partition Problem (SPP for...
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Abraham, D., Blum, A., Sandholm, T.: Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. EC'07, June 11–15, 2007, San Diego, California
Abraham, D., Cechlárová, K., Manlove, D., Mehlhorn, K.: Pareto-optimality in house allocation problems. In: Fleischer, R., Trippen, G. (eds.) Lecture Notes in Comp. Sci. Vol. 3341/2004, Algorithms and Computation, 14th Int. Symposium ISAAC 2004, pp. 3–15. Hong Kong, December 2004
Ballester, C.: NP-completeness in Hedonic Games. Games. Econ. Behav. 49(1), 1–30 (2004)
Banerjee, S., Konishi, H., Sönmez, T.: Core in a simple coalition formation game. Soc. Choice. Welf. 18, 135–153 (2001)
Biró, P., Cechlárová, K.: Inapproximability of the kidney exchange problem. Inf. Proc. Lett. 101(5), 199–202 (2007)
Bogomolnaia, A., Jackson, M.O.: The Stability of Hedonic Coalition Structures. Games. Econ. Behav. 38(2), 201–230 (2002)
Burani, N., Zwicker, W.S.: Coalition formation games with separable preferences. Math. Soc. Sci. 45, 27–52 (2003)
Cechlárová, K., Fleiner, T., Manlove, D.: The kidney exchange game. In: Zadnik-Stirn, L., Drobne, S. (eds.) Proc. SOR '05, pp. 77–83. Nova Gorica, September 2005
Cechlárová, K., Hajduková, J.: Stability testing in coalition formation games. In: Rupnik, V., Zadnik-Stirn, L., Drobne, S. (eds.) Proceedings of SOR'99, pp. 111–116. Predvor, Slovenia (1999)
Cechlárová, K., Hajduková, J.: Computational complexity of stable partitions with \( { \mathcal{B} } \)-preferences. Int. J. Game. Theory 31(3), 353–364 (2002)
Cechlárová, K., Hajduková, J.: Stable partitions with \( { \mathcal{W} } \)-preferences. Discret. Appl. Math. 138(3), 333–347 (2004)
Cechlárová, K., Hajduková, J.: Stability of partitions under WB-preferences and BW-preferences. Int. J. Inform. Techn. Decis. Mak. Special Issue on Computational Finance and Economics. 3(4), 605–614 (2004)
Cechlárová, K., Romero-Medina, A.: Stability in coalition formation games. Int. J. Game. Theor. 29, 487–494 (2001)
Cechlárová, K., Dahm, M., Lacko, V.: Efficiency and stability in a discrete model of country formation. J. Glob. Opt. 20(3–4), 239–256 (2001)
Cechlárová, K., Lacko, V.: The Kidney Exchange problem: How hard is it to find a donor? IM Preprint A4/2006, Institute of Mathematics, P.J. Šafárik University, Košice, Slovakia, (2006)
Dimitrov, D., Borm, P., Hendrickx, R., Sung, S. Ch.: Simple priorities and core stability in hedonic games. Soc. Choice. Welf. 26(2), 421–433 (2006)
Gusfield, D., Irving, R.W.: The Stable Marriage Problem. Structure and Algorithms. MIT Press, Cambridge (1989)
Roth, A., Sönmez, T., Ünver, U.: Kidney Exchange. Quarter. J. Econ. 119, 457–488 (2004)
Shapley, L., Scarf, H.: On cores and indivisibility. J. Math. Econ. 1, 23–37 (1974)
Yuan, Y.: Residence exchange wanted: A stable residence exchange problem. Eur. J. Oper. Res. 90, 536–546 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag
About this entry
Cite this entry
Cechlárová, K. (2008). Stable Partition Problem. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-30162-4_397
Download citation
DOI: https://doi.org/10.1007/978-0-387-30162-4_397
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-30770-1
Online ISBN: 978-0-387-30162-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering