NP-completeness in hedonic games

DOI10.1016/j.geb.2003.10.003zbMath1067.91006OpenAlexW2070069359MaRDI 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-hardNP-completeComputational complexityCoalition formationHedonic games

Mathematics Subject Classification ID

Cooperative games (91A12)

Related Items (35)

Generating Empirical Core Size Distributions of Hedonic Games Using a Monte Carlo Method ⋮ Group activity selection problem with approval preferences ⋮ Computing Stable Outcomes in Hedonic Games ⋮ Altruistic Hedonic Games ⋮ COALITION FORMATION GAMES: A SURVEY ⋮ On myopic stability concepts for hedonic games ⋮ Unnamed Item ⋮ A social choice approach to ordinal group activity selection ⋮ Testing substitutability of weak preferences ⋮ On core membership testing for hedonic coalition formation games ⋮ Non-existence of stable social groups in information-driven networks ⋮ Formation of segregated and integrated groups ⋮ Additively separable hedonic games with social context ⋮ Finding and Recognizing Popular Coalition Structures ⋮ Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games ⋮ Individual and group stability in neutral restrictions of hedonic games ⋮ Stability and welfare in (dichotomous) hedonic diversity games ⋮ Simple priorities and core stability in hedonic games ⋮ Hedonic diversity games revisited ⋮ Pareto optimality in coalition formation ⋮ Group activity selection with few agent types ⋮ On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities ⋮ Two hardness results for core stability in hedonic coalition formation games ⋮ Stable and Pareto optimal group activity selection from ordinal preferences ⋮ Hedonic coalition formation games: a new stability notion ⋮ The computational complexity of rationalizing behavior ⋮ Local fairness in hedonic games via individual threshold coalitions ⋮ Nash stability in additively separable hedonic games and community structures ⋮ The Parallel Complexity of Coloring Games ⋮ Answers set programs for non-transferable utility games: expressiveness, complexity and applications ⋮ An empirical distribution of the number of subsets in the core partitions of hedonic games ⋮ Borda-induced hedonic games with friends, enemies, and neutral players ⋮ Computational complexity in additive hedonic games ⋮ How long does it take for all users in a social network to choose their communities? ⋮ Universally balanced combinatorial optimization games

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.

This page was built for publication: NP-completeness in hedonic games