Abstract
We study the computational complexity of finding stable outcomes in symmetric additively-separable hedonic games. These coalition formation games are specified by an undirected edge-weighted graph: nodes are players, an outcome of the game is a partition of the nodes into coalitions, and the utility of a node is the sum of incident edge weights in the same coalition. We consider several natural stability requirements defined in the economics literature. For all of them the existence of a stable outcome is guaranteed by a potential function argument, so local improvements will converge to a stable outcome and all these problems are in PLS. The different stability requirements correspond to different local search neighbourhoods. For different neighbourhood structures, our findings comprise positive results in the form of polynomial-time algorithms for finding stable outcomes, and negative (PLS-completeness) results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aarts, E.H.L., Lenstra, J.K.: Local Search in Combinatorial Optimization. Wiley Interscience, Hoboken (1997)
Balcan, M.-F., Blum, A., Mansour, Y.: Improved equilibria via public service advertising. In: SODA, pp. 728–737 (2009)
Ballester, C.: NP-completeness in hedonic games. Games and Economic Behavior 49(1), 1–30 (2004)
Bhalgat, A., Chakraborty, T., Khanna, S.: Approximating pure Nash equilibrium in cut, party affiliation and satisfiability games. In: ACM Conference in Electronic Commerce (EC), pp. 132–146 (2010)
Bogomolnaia, A., Jackson, M.O.: The stability of hedonic coalition structures. Games and Economic Behavior 38(2), 201–230 (2002)
Burani, N., Zwicker, W.S.: Coalition formation games with separable preferences. Mathematical Social Sciences 45(1), 27–52 (2003)
Cechlárová, K.: Stable partition problem. In: Encyclopedia of Algorithms. Springer, Heidelberg (2008)
Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A.: Convergence and approximation in potential games. In: STACS, pp. 349–360 (2006)
Dreze, J.H., Greenberg, J.: Hedonic coalitions: Optimality and stability. Econometrica 48(4), 987–1003 (1980)
Elkind, E., Wooldridge, M.: Hedonic coalition nets. In: Int. Conference on Autonomous Agents and Multiagent Systems, pp. 417–424 (2009)
Greenberg, J.: Coalition structures. In: Aumann, R.J., Hart, S. (eds.) Handbook of Game Theory with Economic Applications II. Elsevier, Amsterdam (1994)
Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? Journal of Computer and System Sciences 37, 79–100 (1988)
Monien, B., Tscheuschner, T.: On the power of nodes of degree four in the local max-cut problem. In: 7th International Conference on Algorithms and Complexity, CIAC (2010)
Monien, B., Dumrauf, D., Tscheuschner, T.: Local search: Simple, successful, but sometimes sluggish. In: 37th International Colloquium on Automata, Languages and Programming, ICALP (2010)
Orlin, J.B., Punnen, A.P., Schulz, A.S.: Approximate local search in combinatorial optimization. SIAM Journal of Computing 33(5), 1201–1214 (2004)
Schäffer, A.A., Yannakakis, M.: Simple Local Search Problems that are Hard to Solve. SIAM Journal of Computing 20(1), 56–87 (1991)
Sipser, M.: Introduction to the Theory of Computation. Thomson (2006)
Sung, S.C., Dimitrov, D.: Computational complexity in additive hedonic games. European Journal of Operational Research 203(3), 635–639 (2010)
Tscheuschner, T.: The local max-cut problem is PLS-complete even on graphs with maximum degree five (2010), http://arxiv.org/abs/1004.5329
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gairing, M., Savani, R. (2010). Computing Stable Outcomes in Hedonic Games. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds) Algorithmic Game Theory. SAGT 2010. Lecture Notes in Computer Science, vol 6386. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16170-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-16170-4_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16169-8
Online ISBN: 978-3-642-16170-4
eBook Packages: Computer ScienceComputer Science (R0)