# PAC learning and stabilizing Hedonic Games: towards a unifying approach

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 34 references that are in the map.
- First posted on arXiv 31 Jan 2023.

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

- [Learning Combinatorial Functions from Pairwise Comparisons](https://mlsanity.com/paper/1605.09227/) (2016)
- [Learning Cooperative Games](https://mlsanity.com/paper/1505.00039/) (2015)
- [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)
- [Noise Robust Core-Stable Coalitions of Hedonic Games](https://mlsanity.com/paper/2109.07738/) (2021)
- [The Price is (Probably) Right: Learning Market Equilibria from Samples](https://mlsanity.com/paper/2012.14838/) (2020)

## Built on by (most cited first, 3 of 3)

- [LongDiff: Training-Free Long Video Generation in One Go](https://mlsanity.com/paper/2503.18150/) (2025)
- [varepsilon-fractional Core Stability in Hedonic Games](https://mlsanity.com/paper/2311.11101/) (2023)
- [Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions](https://mlsanity.com/paper/2602.14321/) (2026)

## Abstract (arXiv)

We study PAC learnability and PAC stabilizability of Hedonic Games (HGs), i.e., efficiently inferring preferences or core-stable partitions from samples. We first expand the known learnability/stabilizability landscape for some of the most prominent HGs classes, providing results for Friends and Enemies Games, Bottom Responsive, and Anonymous HGs. Then, having a broader view in mind, we attempt to shed light on the structural properties leading to learnability/stabilizability, or lack thereof, for specific HGs classes. Along this path, we focus on the fully expressive Hedonic Coalition Nets representation of HGs. We identify two sets of conditions that lead to efficient learnability, and which encompass all of the known positive learnability results. On the side of stability, we reveal that, while the freedom of choosing an ad hoc adversarial distribution is the most obvious hurdle to achieving PAC stability, it is not the only one. First, we show a distribution independent necessary condition for PAC stability. Then, we focus on W-games, where players have individual preferences over other players and evaluate coalitions based on the least preferred member. We prove that these games are PAC stabilizable under the class of bounded distributions, which assign positive probability mass to all coalitions. Finally, we discuss why such a result is not easily extendable to other HGs classes even in this promising scenario. Namely, we establish a purely computational property necessary for achieving PAC stability.