Article ID Journal Published Year Pages File Type
427672 Information Processing Letters 2012 5 Pages PDF
Abstract

We consider the problem of computing non-trivial Nash equilibria in additive hedonic games with symmetric 0/1-utilities. Such a game can be represented by an undirected unweighted graph G(V,E)G(V,E) where a non-trivial Nash equilibrium corresponds to a partition of V into at least two sets such that each node has at least as many neighbours in its own set compared to any other set in the partition. We show that computing such an equilibrium is NP-complete. On the other hand, we show that such an equilibrium is computable in polynomial time if (1) G is triangle free, (2) G contains no 4-cycles sharing and edge, and (3) G is not a star. If G   is not a star with girth at least 5 we show how to compute a non-trivial equilibrium in O(n)O(n)-time.

► We study the computational complexity of additive hedonic games with symmetric 0/1 utilities. ► Sufficient conditions for the existence of non-trivial Nash stable partitions computable in polynomial time are presented. ► Computing non-trivial Nash stable partitions is shown to be NP-hard in such games.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,