Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games

Published Online:6 Jun 2019https://doi.org/10.1287/moor.2018.0960

References

  • [1] Aarts EHL, Lenstra JK (1997) Local Search in Combinatorial Optimization (Wiley-Interscience, New York).Google Scholar
  • [2] Alcalde J, Revilla JP (2004) Researching with whom? Stability and manipulation. J. Math. Econom. 40(8):869–887.Crossref, Google Scholar
  • [3] Anshelevich E, Dasgupta A, Kleinberg JM, Tardos É, Wexler T, Roughgarden T (2008) The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4):1602–1623.Crossref, Google Scholar
  • [4] Aziz H, Brandl F (2012) Existence of stability in hedonic coalition formation games. van der Hoek W, Padgham L, Conitzer V, Winikoff M, eds. Proc. 11th Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 763–770.Google Scholar
  • [5] Aziz H, Savani R (2016) Hedonic games. Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD, eds. Handbook of Computational Social Choice (Cambridge University Press, Cambridge, UK), 356–376.Google Scholar
  • [6] Aziz H, Brandt F, Harrenstein P (2013) Pareto optimality in coalition formation. Games Econom. Behav. 82:562–581.Crossref, Google Scholar
  • [7] Aziz H, Brandt F, Harrenstein P (2014) Fractional hedonic games. Bazzan ALC, Huhns MN, Lomuscio A, Scerri P, eds. Proc. 13th Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 5–12.Google Scholar
  • [8] Aziz H, Brandt F, Seedig HG (2013) Computing desirable partitions in additively separable hedonic games. Artificial Intelligence 195(February):316–334.Crossref, Google Scholar
  • [9] Aziz H, Gaspers S, Gudmundsson J, Mestre J, Täubig H (2015) Welfare maximization in fractional hedonic games. Yang Q, Woolridge M, eds. Proc. Internat. Joint Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 461–467.Google Scholar
  • [10] Aziz H, Brandl F, Brandt F, Harrenstein P, Olsen M, Peters D (2017) Fractional hedonic games. arXiv:1705.10116.Google Scholar
  • [11] Balcan MF, Blum A, Mansour Y (2009) Improved equilibria via public service advertising. Mathieu C, ed. Proc. ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 728–737.Crossref, Google Scholar
  • [12] Ballester C (2004) NP-completeness in hedonic games. Games Econom. Behav. 49(1):1–30.Crossref, Google Scholar
  • [13] Banerjee S, Konishi H, Sönmez T (2001) Core in a simple coalition formation game. Soc. Choice Welfare 18(1):135–153.Crossref, Google Scholar
  • [14] Bhalgat A, Chakraborty T, Khanna S (2010) Approximating pure Nash equilibrium in cut, party affiliation and satisfiability games. Parkes DC, Dellarocas C, Tennenholtz M, eds. Proc. ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 132–146.Crossref, Google Scholar
  • [15] Bilò V, Fanelli A, Flammini M, Monaco G, Moscardelli L (2018) Nash stable outcomes in fractional hedonic games: Existence, efficiency and computation. J. Artificial Intelligence Res. 62:315–371.Crossref, Google Scholar
  • [16] Bloch F, Diamantoudi E (2011) Noncooperative formation of coalitions in hedonic games. Internat. J. Game Theory 40(2):263–280.Crossref, Google Scholar
  • [17] Bogomolnaia A, Jackson MO (2002) The stability of hedonic coalition structures. Games Econom. Behav. 38(2):201–230.Crossref, Google Scholar
  • [18] Brânzei S, Larson K (2009) Coalitional affinity games and the stability gap. Kitano H, ed. Proc. Internat. Joint Conf. Artificial Intelligence (Morgan Kaufmann Publishers, San Francisco), 1319–1320.Google Scholar
  • [19] Burani N, Zwicker WS (2003) Coalition formation games with separable preferences. Math. Soc. Sci. 45(1):27–52.Crossref, Google Scholar
  • [20] Chalkiadakis G, Elkind E, Polukarov M, Jennings NR (2009) The price of democracy in coalition formation. Sierra C, Castelfranchi C, Decker KS, Sichman JS, eds. Proc. 8th Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 401–408.Google Scholar
  • [21] Christodoulou G, Mirrokni VS, Sidiropoulos A (2006) Convergence and approximation in potential games. Durand B, Thomas W, eds. Proc. Sympos. Theoret. Aspects Comput. Sci., Lecture Notes in Computer Science, vol. 3884 (Springer, Heidelberg), 349–360.Crossref, Google Scholar
  • [22] Dimitrov D, Sung SC (2007) On top responsiveness and strict core stability. J. Math. Econom. 43(2):130–134.Crossref, Google Scholar
  • [23] Dimitrov D, Borm P, Hendrickx R, Sung SC (2006) Simple priorities and core stability in hedonic games. Soc. Choice Welfare 26(2):421–433.Crossref, Google Scholar
  • [24] Drèze JH, Greenberg J (1980) Hedonic coalitions: Optimality and stability. Econometrica 48(4):987–1003.Crossref, Google Scholar
  • [25] Elkind E, Wooldridge M (2009) Hedonic coalition nets. Sierra C, Castelfranchi C, Decker KS, Sichman JS, eds. Proc. 8th Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 417–424.Google Scholar
  • [26] Elkind E, Fanelli A, Flammini M (2016) Price of Pareto optimality in hedonic games. Schuurmans D, Wellman MP, eds. Proc. Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 475–481.Google Scholar
  • [27] Elsässer R, Tscheuschner T (2011) Settling the complexity of local max-cut (almost) completely. Aceto L, Henzinger M, Sgall J, eds. Automata, Languages and Programming—ICALP 2011, Lecture Notes in Computer Science, vol. 6755 (Springer, Heidelberg), 171–182.Crossref, Google Scholar
  • [28] Fabrikant A, Papadimitriou CH, Talwar K (2004) The complexity of pure Nash equilibria. Babai L, ed. Proc. ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 604–612.Crossref, Google Scholar
  • [29] Gairing M, Savani R (2010) Computing stable outcomes in hedonic games. Kontogiannis SC, Koutsoupias E, Spirakis PG, eds. Algorithmic Game Theory—SAGT 2010, Lecture Notes in Computer Science, vol. 6386 (Springer, Heidelberg), 174–185.Crossref, Google Scholar
  • [30] Gairing M, Savani R (2011) Computing stable outcomes in hedonic games with voting-based deviations. Sonenberg L, Stone P, Tumer K, Yolum P, eds. Proc. 10th Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 559–566.Google Scholar
  • [31] Ieong S, Shoham Y (2005) Marginal contribution nets: A compact representation scheme for coalitional games. Proc. ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 193–202.Crossref, Google Scholar
  • [32] Johnson DS, Papadimitriou CH, Yannakakis M (1988) How easy is local search? J. Comput. System Sci. 37(1):79–100.Crossref, Google Scholar
  • [33] Karakaya M (2011) Hedonic coalition formation games: A new stability notion. Math. Soc. Sci. 61(2):157–165.Crossref, Google Scholar
  • [34] Koutsoupias E, Papadimitriou CH (1999) Worst-case equilibria. Meinel C, Tison S, eds. Proc. Internat. Sympos. Theoret. Aspects Comput. Sci., Lecture Notes in Computer Science, vol. 1563 (Springer-Verlag, Berlin), 404–413.Crossref, Google Scholar
  • [35] Krentel MW (1989) Structure in locally optimal solutions. Proc. Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 216–221.Crossref, Google Scholar
  • [36] Monaco G, Moscardelli L, Velaj Y (2018) Stable outcomes in modified fractional hedonic games. Andre E, Koenig S, Dastani M, Sukthankar G, eds. Proc. 17th Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 937–945.Google Scholar
  • [37] Monien B, Tscheuschner T (2010) On the power of nodes of degree four in the local max-cut problem. Calamoneri T, Diaz J, eds. Algorithms and Complexity—CIAC 2010, Lecture Notes in Computer Science, vol. 6078 (Springer, Heidelberg), 264–275.Crossref, Google Scholar
  • [38] Monien B, Dumrauf D, Tscheuschner T (2010) Local search: Simple, successful, but sometimes sluggish. Abramsky S, Gavoille C, Kirchner C, Meyer auf der Heide F, Spirakis PG, eds. Automata, Languages and Programming—ICALP 2010, Lecture Notes in Computer Science, vol. 6078 (Springer, Heidelberg), 1–17.Crossref, Google Scholar
  • [39] Olsen M (2012) On defining and computing communities. Mestre J, ed. Proc. Comput.: Australasian Theory Sympos., vol. 128 (Australian Computer Society, Darlinghurst, Australia), 97–102.Google Scholar
  • [40] Orlin JB, Punnen AP, Schulz AS (2004) Approximate local search in combinatorial optimization. SIAM J. Comput 33(5):1201–1214.Crossref, Google Scholar
  • [41] Peters D (2016) Graphical hedonic games of bounded treewidth. Schuurmans D, Wellman MP, eds. Proc. Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 586–593.Google Scholar
  • [42] Peters D (2017) Precise complexity of the core in dichotomous and additive hedonic games. Rothe J, ed. Algorithmic Decision Theory—ADT 2017, Lecture Notes in Computer Science, vol. 10576 (Springer, Heidelberg), 214–227.Crossref, Google Scholar
  • [43] Peters D, Elkind E (2015) Simple causes of complexity in hedonic games. Yang Q, Wooldridge M, eds. Proc. Internat. Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 617–623.Google Scholar
  • [44] Poljak S (1995) Integer linear programs and local search for max-cut. SIAM J. Comput. 21(3):450–465.Google Scholar
  • [45] Schäffer AA, Yannakakis M (1991) Simple local search problems that are hard to solve. SIAM J. Comput. 20(1):56–87.Crossref, Google Scholar
  • [46] Sipser M (2006) Introduction to the Theory of Computation (International Thomson Publishing, Stamford, CT).Google Scholar
  • [47] Sung SC, Dimitrov D (2007) On myopic stability concepts for hedonic games. Theory Decision 62(1):31–45.Crossref, Google Scholar
  • [48] Sung SC, Dimitrov D (2010) Computational complexity in additive hedonic games. Eur. J. Oper. Res. 203(3):635–639.Crossref, Google Scholar
  • [49] Woeginger GJ (2013) A hardness result for core stability in additive hedonic games. Math. Soc. Sci. 65(2):101–104.Crossref, Google Scholar
  • [50] Yannakakis M (2008) Equilibria, fixed points, and complexity classes. Albers S, Weil P, eds. Proc. Internat. Sympos. Theoret. Aspects Comput. Sci. (Schloss Dagstuhl—Leibniz Center for Informatics, Saarbrücken, Germany), 19–38.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree