Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games
From MaRDI portal
Publication:5108232
Abstract: We study the computational complexity of finding stable outcomes in hedonic games, which are a class of coalition formation games. We restrict our attention to symmetric additively-separable hedonic games, which are a nontrivial subclass of such games that are guaranteed to possess stable outcomes. These games are specified by an undirected edge- weighted graph: nodes are players, an outcome of the game is a partition of the nodes into coalitions, and the utility of a node is the sum of incident edge weights in the same coalition. We consider several stability requirements defined in the literature. These are based on restricting feasible player deviations, for example, by giving existing coalition members veto power. We extend these restrictions by considering more general forms of preference aggregation for coalition members. In particular, we consider voting schemes to decide if coalition members will allow a player to enter or leave their coalition. For all of the stability requirements we consider, the existence of a stable outcome is guaranteed by a potential function argument, and local improvements will converge to a stable outcome. We provide an almost complete characterization of these games in terms of the tractability of computing such stable outcomes. Our findings comprise positive results in the form of polynomial-time algorithms, and negative (PLS-completeness) results. The negative results extend to more general hedonic games.
Recommendations
- Computing Stable Outcomes in Hedonic Games
- Computing desirable partitions in additively separable hedonic games
- A hardness result for core stability in additive hedonic games
- On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities
- Computational complexity in additive hedonic games
- Nash Stability in Additively Separable Hedonic Games Is NP-Hard
- Precise complexity of the core in dichotomous and additive hedonic games
- On the price of stability of some simple graph-based hedonic games
- Nash stability in additively separable hedonic games and community structures
Cites work
- scientific article; zbMATH DE number 5595162 (Why is no real title available?)
- scientific article; zbMATH DE number 1016966 (Why is no real title available?)
- A hardness result for core stability in additive hedonic games
- Approximate Local Search in Combinatorial Optimization
- Coalition formation games with separable preferences.
- Computational complexity in additive hedonic games
- Computing Stable Outcomes in Hedonic Games
- Computing desirable partitions in additively separable hedonic games
- Convergence and Approximation in Potential Games
- Core in a simple coalition formation game
- Equilibria, fixed points, and complexity classes
- Hedonic Coalitions: Optimality and Stability
- Hedonic coalition formation games: a new stability notion
- Hedonic games
- How easy is local search?
- Improved equilibria via public service advertising
- Local search: simple, successful, but sometimes sluggish
- NP-completeness in hedonic games
- Nash stable outcomes in fractional hedonic games: existence, efficiency and computation
- Noncooperative formation of coalitions in hedonic games
- On myopic stability concepts for hedonic games
- On the Power of Nodes of Degree Four in the Local Max-Cut Problem
- On top responsiveness and strict core stability
- Pareto optimality in coalition formation
- Precise complexity of the core in dichotomous and additive hedonic games
- Researching with whom? Stability and manipulation
- Settling the complexity of local max-cut (almost) completely
- Simple Local Search Problems that are Hard to Solve
- Simple priorities and core stability in hedonic games
- The Price of Stability for Network Design with Fair Cost Allocation
- The complexity of pure Nash equilibria
- The stability of hedonic coalition structures
- Worst-case equilibria
Cited in
(13)- Nash Stability in Additively Separable Hedonic Games Is NP-Hard
- Stability based on single-agent deviations in additively separable hedonic games
- Computing desirable partitions in additively separable hedonic games
- Strategyproof mechanisms for friends and enemies games
- Strategyproof mechanisms for additively separable and fractional hedonic games
- Solidarity to achieve stability
- Distance hedonic games
- Precise complexity of the core in dichotomous and additive hedonic games
- Computing Stable Outcomes in Hedonic Games
- On the price of stability of some simple graph-based hedonic games
- Unique end of potential line
- Computational complexity in additive hedonic games
- Nash stability in additively separable hedonic games and community structures
This page was built for publication: Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5108232)
