Computing stable outcomes in hedonic games with voting-based deviations

摘要: We study the computational complexity of finding stable outcomes in hedonic games, which are a class coalition formation games. restrict our attention to nontrivial subclass such guaranteed possess outcomes, i.e., set symmetric additively-separable These games specified by an undirected edge-weighted graph: nodes players, outcome game is partition into coalitions, and utility node sum incident edge weights same coalition. consider several stability requirements defined literature. based on restricting feasible player deviations, for example, giving existing members veto power. extend these restrictions considering more general forms preference aggregation members. In particular, we voting schemes decide if will allow enter or leave their For all consider, existence potential function argument, local improvements converge outcome. provide almost complete characterization terms tractability computing outcomes. Our findings comprise positive results form polynomial-time algorithms, negative (PLS-completeness) results. The