Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games
From MaRDI portal
Publication:5108232
DOI10.1287/MOOR.2018.0960zbMATH Open1437.91018arXiv1509.05322OpenAlexW2963693668WikidataQ127737652 ScholiaQ127737652MaRDI QIDQ5108232FDOQ5108232
Authors: Martin Gairing, Rahul Savani 
Publication date: 30 April 2020
Published in: Mathematics of Operations Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1509.05322
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
Noncooperative games (91A10) Games involving graphs (91A43) Voting theory (91B12) Algorithmic game theory and complexity (91A68)
Cites Work
- Worst-case equilibria
- Title not available (Why is that?)
- Core in a simple coalition formation game
- The Price of Stability for Network Design with Fair Cost Allocation
- Title not available (Why is that?)
- The stability of hedonic coalition structures
- How easy is local search?
- The complexity of pure Nash equilibria
- Simple Local Search Problems that are Hard to Solve
- Computational complexity in additive hedonic games
- A hardness result for core stability in additive hedonic games
- Simple priorities and core stability in hedonic games
- Computing desirable partitions in additively separable hedonic games
- Improved equilibria via public service advertising
- Coalition formation games with separable preferences.
- Hedonic Coalitions: Optimality and Stability
- Noncooperative formation of coalitions in hedonic games
- Convergence and Approximation in Potential Games
- NP-completeness in hedonic games
- Computing Stable Outcomes in Hedonic Games
- Approximate Local Search in Combinatorial Optimization
- Hedonic coalition formation games: a new stability notion
- Researching with whom? Stability and manipulation
- On myopic stability concepts for hedonic games
- On top responsiveness and strict core stability
- Pareto optimality in coalition formation
- Nash stable outcomes in fractional hedonic games: existence, efficiency and computation
- Equilibria, fixed points, and complexity classes
- Precise complexity of the core in dichotomous and additive hedonic games
- Local search: simple, successful, but sometimes sluggish
- Hedonic games
- Settling the complexity of local max-cut (almost) completely
- On the Power of Nodes of Degree Four in the Local Max-Cut Problem
Cited In (13)
- Solidarity to achieve stability
- Distance hedonic games
- Computing Stable Outcomes in Hedonic Games
- On the price of stability of some simple graph-based hedonic games
- Stability based on single-agent deviations in additively separable hedonic games
- Computing desirable partitions in additively separable hedonic games
- Unique end of potential line
- Nash stability in additively separable hedonic games and community structures
- Nash Stability in Additively Separable Hedonic Games Is NP-Hard
- Computational complexity in additive hedonic games
- Strategyproof mechanisms for additively separable and fractional hedonic games
- Strategyproof mechanisms for friends and enemies games
- Precise complexity of the core in dichotomous and additive hedonic games
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)
