NP-completeness in hedonic games

DOI10.1016/j.geb.2003.10.003zbMath1067.91006MaRDI QIDQ1886742

Coralio Ballester

Publication date: 19 November 2004

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.geb.2003.10.003

zbMATH Keywords

NP-hard; NP-complete; Computational complexity; Coalition formation; Hedonic games

Mathematics Subject Classification ID

91A12: Cooperative games

Related Items

On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities, Hedonic coalition formation games: a new stability notion, Nash stability in additively separable hedonic games and community structures, Formation of segregated and integrated groups, Individual and group stability in neutral restrictions of hedonic games, The computational complexity of rationalizing behavior, Computational complexity in additive hedonic games, Group activity selection problem with approval preferences, A social choice approach to ordinal group activity selection, Stable and Pareto optimal group activity selection from ordinal preferences, Universally balanced combinatorial optimization games, On myopic stability concepts for hedonic games, Simple priorities and core stability in hedonic games, Pareto optimality in coalition formation, Two hardness results for core stability in hedonic coalition formation games, Testing substitutability of weak preferences, On core membership testing for hedonic coalition formation games, The Parallel Complexity of Coloring Games, Computing Stable Outcomes in Hedonic Games, COALITION FORMATION GAMES: A SURVEY

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The stability of hedonic coalition structures
• The complexity of computing best-response automata in repeated games
• The complexity of computing a best response automaton in repeated games with mixed strategies
• On the complexity of testing membership in the core of min-cost spanning tree games
• Computing the nucleolus of min-cost spanning tree games is NP-hard.
• Core in a simple coalition formation game
• Farsighted stability in hedonic games
• An efficient algorithm for the “stable roommates” problem
• Hedonic Coalitions: Optimality and Stability
• Minesweeper is NP-complete.