Relaxed Core Stability in Fractional Hedonic Games

Abstract

The core is a well-known and fundamental notion of stability in games intended to model coalition formation such as hedonic games. The fact that the number of deviating agents (that have to coordinate themselves) can be arbitrarily high, and the fact that agents may benefit only by a tiny amount from their deviation (while they could incur in a cost for deviating), suggest that the core is not able to suitably model many practical scenarios in large and highly distributed multi-agent systems. For this reason, we consider relaxed core stable outcomes where the notion of permissible deviations is modified along two orthogonal directions: the former takes into account the size of the deviating coalition, and the latter the amount of utility gain for each member of the deviating coalition. These changes result in two different notions of stability, namely, the q-size core and k-improvement core. We investigate these concepts of stability in fractional hedonic games, that is a well-known subclass of hedonic games for which core stable outcomes are not guaranteed to exist and it is computationally hard to decide nonemptiness of the core. Interestingly, the considered relaxed notions of core also possess the appealing property of recovering, in some notable cases, the convergence, the existence and the possibility of computing stable solutions in polynomial time.