# Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions

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

## Key facts

- No citing papers in the map yet (data through 7 Oct 2026).
- Builds on 16 of its 44 references that are in the map.
- First posted on arXiv 15 Feb 2026.

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

- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets](https://mlsanity.com/paper/2202.07511/) (2022)
- [Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity](https://mlsanity.com/paper/1908.11071/) (2019)
- [Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus](https://mlsanity.com/paper/2206.00159/) (2022)
- [Cooperative Games with Overlapping Coalitions](https://mlsanity.com/paper/1401.3856/) (2014)
- [Forming Probably Stable Communities with Limited Interactions](https://mlsanity.com/paper/1811.04616/) (2018)
- [Causes of Stability in Dynamic Coalition Formation](https://mlsanity.com/paper/2211.17169/) (2022)
- [PAC learning and stabilizing Hedonic Games: towards a unifying approach](https://mlsanity.com/paper/2301.13756/) (2023)
- [Provably Efficient Offline Reinforcement Learning with Perturbed Data Sources](https://mlsanity.com/paper/2306.08364/) (2023)
- [Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals](https://mlsanity.com/paper/2601.16091/) (2026)
- [Cooperative Games with Overlapping Coalitions: Charting the Tractability Frontier](https://mlsanity.com/paper/1407.0420/) (2014)
- [Computing stable outcomes in symmetric additively-separable hedonic games](https://mlsanity.com/paper/1509.05322/) (2015)

## Abstract (arXiv)

Coalition formation concerns strategic collaborations of selfish agents that form coalitions based on their preferences. It is often assumed that coalitions are disjoint and preferences are fully known, which may not hold in practice. In this paper, we thus present a new model of coalition formation with possibly overlapping coalitions under partial information, where selfish agents may be part of multiple coalitions simultaneously and their full preferences are initially unknown. Instead, information about past interactions and associated utility feedback is stored in a fixed offline dataset, and we aim to efficiently infer the agents' preferences from this dataset. We analyze the impact of diverse dataset information constraints by studying two types of utility feedback that can be stored in the dataset: agent- and coalition-level utility feedback. For both feedback models, we identify assumptions under which the dataset covers sufficient information for an offline learning algorithm to infer preferences and use them to recover a partition that is (approximately) Nash stable, in which no agent can improve her utility by unilaterally deviating. Our additional goal is devising algorithms with low sample complexity, requiring only a small dataset to obtain a desired approximation to Nash stability. Under agent-level feedback, we provide a sample-efficient algorithm proven to obtain an approximately Nash stable partition under a sufficient and necessary assumption on the information covered by the dataset. However, under coalition-level feedback, we show that only under a stricter assumption is sufficient for sample-efficient learning. Still, in multiple cases, our algorithms' sample complexity bounds have optimality guarantees up to logarithmic factors. Finally, extensive experiments show that our algorithm converges to a low approximation level to Nash stability across diverse settings.