Computational complexity in additive hedonic games

DOI10.1016/j.ejor.2009.09.004zbMath1177.90429OpenAlexW3125555204MaRDI QIDQ1046065

Dinko Dimitrov, Shao Chin Sung

Publication date: 21 December 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://ageconsearch.umn.edu/record/46655/files/98-08.pdf

zbMATH Keywords

computational complexityNP-hardNP-completecoalition formationhedonic gamesadditive preferences

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Cooperative games (91A12) Applications of game theory (91A80) Decision theory for games (91A35)

Related Items (14)

Computing Stable Outcomes in Hedonic Games ⋮ Altruistic Hedonic Games ⋮ Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games ⋮ Non-existence of stable social groups in information-driven networks ⋮ Additively separable hedonic games with social context ⋮ The three-dimensional stable roommates problem with additively separable preferences ⋮ Balancing stability and efficiency in team formation as a generalized roommate problem ⋮ Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games ⋮ Topological distance games ⋮ Dynamics in matching and coalition formation games with structural constraints ⋮ On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities ⋮ Path-disruption games: bribery and a probabilistic model ⋮ Borda-induced hedonic games with friends, enemies, and neutral players ⋮ On Pareto optimality in social distance games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The stability of hedonic coalition structures
• Good neighbors are hard to find: Computational complexity of network formation
• The complexity of computing best-response automata in repeated games
• Nash and correlated equilibria: Some complexity considerations
• The complexity of computing a best response automaton in repeated games with mixed strategies
• The complexity of two-person zero-sum games in extensive form
• On the complexity of testing membership in the core of min-cost spanning tree games
• Computational complexity of stable partitions with b-preferences
• Efficient computation of equilibria for extensive two-person games
• Stable partitions with \(\mathcal W\)-preferences
• NP-completeness in hedonic games
• Computing the nucleolus of min-cost spanning tree games is NP-hard.
• On myopic stability concepts for hedonic games
• Core in a simple coalition formation game
• Simple priorities and core stability in hedonic games
• On core membership testing for hedonic coalition formation games
• Hedonic Coalitions: Optimality and Stability
• Nash Stability in Additively Separable Hedonic Games Is NP-Hard

This page was built for publication: Computational complexity in additive hedonic games