Computing Stable Outcomes in Hedonic Games

DOI10.1007/978-3-642-16170-4_16zbMath1310.91042MaRDI QIDQ3162517

Rahul Savani, Martin Gairing

Publication date: 19 October 2010

Published in: Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16170-4_16

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

91A43: Games involving graphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Dynamics of Profit-Sharing Games, Coordination Games on Weighted Directed Graphs, Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games, Unique End of Potential Line, Generalized graph \(k\)-coloring games, On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities, Coordination games on graphs, Dynamics in matching and coalition formation games with structural constraints, On Pareto optimality in social distance games, Hedonic expertise games, The Parallel Complexity of Coloring Games, The Price of Stability of Simple Symmetric Fractional Hedonic Games, Selfish Transportation Games, Settling the Complexity of Local Max-Cut (Almost) Completely

Cites Work

• Unnamed Item
• Unnamed Item
• The stability of hedonic coalition structures
• Computational complexity in additive hedonic games
• How easy is local search?
• Coalition formation games with separable preferences.
• NP-completeness in hedonic games
• Simple Local Search Problems that are Hard to Solve
• On the Power of Nodes of Degree Four in the Local Max-Cut Problem
• Local Search: Simple, Successful, But Sometimes Sluggish
• Hedonic Coalitions: Optimality and Stability
• Approximate Local Search in Combinatorial Optimization
• Convergence and Approximation in Potential Games