Summary
This paper introduces the concept of an $\epsilon$-fractional core stability, relaxing the standard notion of core stability by allowing at most an $\epsilon$ fraction of all possible outcomes to core-block. They show that for sufficiently small values of $\epsilon$, $\epsilon$-fractional core stability always exists and can be computed in polynomial time for certain important subclasses of hedonic games, bypassing well-known difficulties with the usual notion of core stability. They also provide learning algorithms with PAC-type guarantees for identifying $\epsilon$-fractional core-stable outcomes under a broad class of underlying distributions over coalitions, as well as negative results for arbitrary distributions.
Strengths
The paper makes a concrete contribution in the algorithmic study of core-stability notions in important classes of hedonic games, namely simple fractional and anonymous hedonic games. More precisely, the usual notion of core stability is known to suffer from two major drawbacks: it is not universal, and even when it exists it can be hard compute. As a result, different relaxations have been studied over the years that try to address those issues. This paper lies in this line of work, proposing a natural relaxation that only requires most of the coalitions to not be core-blocking. Moreover, they provide a number of non-trivial positive and negative results under this new concept. As such, I believe it makes concrete contributions in this line of work, the results have been nicely placed into the existing literature, and the paper can bring much interesting future work.
Moreover, the paper is well-written and structured, and all the important ideas and techniques and sufficiently exposed in the main body. I did not find any notable issue in the technical part/proofs. The results appear to be sound.
Weaknesses
One notable weakness is that the central definition of the paper (Definition 3.1), albeit quite natural, is not entirely uncontroversial: the fact that most coalitions are not core-blocking may not be sufficient for certain scenarios. That is, it is not clear whether the introduced notion of fractional core stability is an appropriate notion of stability in hedonic games. It would be good to see some more motivation and suitable applications for this definition, as well scenarios wherein this notion fails to provide meaningful guarantees.
Besides the issue above, another weakness is that most of the results follow rather directly from prior work and standard techniques, but I don't view this as a basis for rejection.
Questions
Some minor issues:
1. Technically speaking, the term $2^{-n^{1/3}}$ (for example in Theorem 5.1) is sub exponential, so maybe it is worth rephrasing the claims that $\epsilon$ is decreasing exponentially with the number of players (but I leave this up to the authors).
2. There is something off with the citation style; for example, Line 89 reads "Donahue u. Kleinberg" instead of "Donahue and Kleinberg." This also occurs in many places.
3. There are missing punctuation marks in some equations throughout the paper.
4. Regarding the title, maybe it is worth considering either removing the word "epsilon" or replacing "epsilon" with $\epsilon$; currently it reads slightly weird.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The authors have adequately addressed the limitations.