Paper Info
Title
Computing stable outcomes in hedonic games with voting-based deviations
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 a nontrivial subclass of such games, which are guaranteed to possess stable outcomes, i.e., the set of symmetric additively-separable hedonic games. 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.
Year
DOI
Venue
2011
10.5555/2031678.2031697
AAMAS
Keywords
Field
DocType
voting-based deviation,hedonic game,existing coalition members veto,general form,stable outcome,computing stable outcome,feasible player deviation,general hedonic game,coalition member,symmetric additively-separable hedonic game,stability requirement,coalition formation game,local search,voting
Computer science,Artificial intelligence,Veto,Aggregation problem,Mathematical economics,Voting,Simulation,Local search (optimization),Partition (number theory),Argument of a function,Machine learning,restrict,Computational complexity theory
Conference
ISBN
Citations 
PageRank 
0-9826571-6-1
12
0.74
References 
Authors
24
2
Name
Order
Citations
PageRank
Martin Gairing163347.14
Rahul Savani224330.09