  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
$\varepsilon$-fractional core-stability, where at most an
$\varepsilon$-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 $\varepsilon$-fractional core-stable partition, with $\varepsilon$
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 $\varepsilon$-fractional core equivalent to requiring
that uniformly sampled coalitions core-block with probability lower than
$\varepsilon$, 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
$\varepsilon$-fractional core-stable with arbitrarily high confidence.
