# varepsilon-fractional Core Stability in Hedonic Games

arXiv: https://arxiv.org/abs/2311.11101 · HTML: https://mlsanity.com/paper/2311.11101/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 18 Nov 2023.

## Builds on (most cited first, 11 of 11)

- [Model-sharing Games: Analyzing Federated Learning Under Voluntary Participation](https://mlsanity.com/paper/2010.00753/) (2020)
- [Optimality and Stability in Federated Learning: A Game-theoretic Approach](https://mlsanity.com/paper/2106.09580/) (2021)
- [Fractional Hedonic Games](https://mlsanity.com/paper/1705.10116/) (2017)
- [Statistical Cost Sharing](https://mlsanity.com/paper/1703.03111/) (2017)
- [Neural Payoff Machines: Predicting Fair and Stable Payoff Allocations Among Team Members](https://mlsanity.com/paper/2208.08798/) (2022)
- [A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts](https://mlsanity.com/paper/1903.08322/) (2019)
- [Forming Probably Stable Communities with Limited Interactions](https://mlsanity.com/paper/1811.04616/) (2018)
- [PAC learning and stabilizing Hedonic Games: towards a unifying approach](https://mlsanity.com/paper/2301.13756/) (2023)
- [Simple Causes of Complexity in Hedonic Games](https://mlsanity.com/paper/1507.03474/) (2015)
- [Noise Robust Core-Stable Coalitions of Hedonic Games](https://mlsanity.com/paper/2109.07738/) (2021)
- [Assignment Markets with Budget Constraints](https://mlsanity.com/paper/2205.06132/) (2022)

## Abstract (arXiv)

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.