ε-fractional core stability in Hedonic Games

Hedonic Games (HGs) are a classical framework modeling coalition formation of strategic agents guided by their individual preferences.According to these preferences, it is desirable that a coalition structure (i.e.a partition of agents into coalitions) satisfies some form of stability.The most well-known and natural of such notions is arguably core-stability.Informally, a partition is core-stable if no subset of agents would like to deviate by regrouping in a so-called core-blocking coalition.Unfortunately, core-stable partitions seldom exist and even when they do, it is often computationally intractable to find one.To circumvent these problems, we propose the notion of "-fractional core-stability, where at most an "-fraction of all possible coalitions is allowed to core-block.It turns out that such a relaxation may guarantee both existence and polynomial-time computation.Specifically, we design efficient algorithms returning an "-fractional core-stable partition, with " exponentially decreasing in the number of agents, for two fundamental classes of HGs: Simple Fractional and Anonymous.From a probabilistic point of view, being the definition of "-fractional core equivalent to requiring that uniformly sampled coalitions core-block with probability lower than ", we further extend the definition to handle more complex sampling distributions.Along this line, when valuations have to be learned from samples in a PAC-learning fashion, we give positive and negative results on which distributions allow the efficient computation of outcomes that are "-fractional core-stable with arbitrarily high confidence.