Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games

DOI10.1007/s10472-015-9461-yzbMath1371.68121OpenAlexW2264691341MaRDI QIDQ314437

Lena Schend, Hilmar Schadrack, Anja Rey, Jörg Rothe

Publication date: 16 September 2016

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-015-9461-y

zbMATH Keywords

game theoryhedonic gamesstrict core stabilitywonderful stability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cooperative games (91A12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Altruistic Hedonic Games ⋮ Path-disruption games: bribery and a probabilistic model ⋮ Borda-induced hedonic games with friends, enemies, and neutral players

Cites Work

• Unnamed Item
• Unnamed Item
• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
• Computing desirable partitions in additively separable hedonic games
• The complexity of computing minimal unidirectional covering sets
• The strong exponential hierarchy collapses
• The complexity of Kemeny elections
• Computational complexity in additive hedonic games
• The complexity of facets (and some facets of complexity)
• More complicated questions about maxima and minima, and some closures of NP
• Bounded queries to SAT and the Boolean hierarchy
• The polynomial-time hierarchy
• Exact complexity of the winner problem for Young elections
• A hardness result for core stability in additive hedonic games
• Handbook of social choice and welfare. Vol. 1.
• Simple priorities and core stability in hedonic games
• A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
• On core membership testing for hedonic coalition formation games
• Computational Aspects of Cooperative Game Theory
• Core Stability in Hedonic Coalition Formation
• Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
• Bounded Query Classes
• The difference and truth-table hierarchies for NP
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• Exact analysis of Dodgson elections
• On computing Boolean connectives of characteristic functions
• Reducibility among Combinatorial Problems
• Introduction to the Theory of Cooperative Games

This page was built for publication: Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games