![[2602.14321] Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.14321] Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions
Summary
This paper presents a model for offline learning of Nash stable coalition structures, addressing the complexities of overlapping coalitions and partial information among agents.
Why It Matters
Understanding coalition formation with overlapping memberships is crucial for applications in multi-agent systems and game theory. This research provides insights into efficient algorithms that can infer agent preferences from limited data, which is relevant for both theoretical exploration and practical implementations in AI.
Key Takeaways
- Introduces a model for coalition formation with overlapping coalitions under partial information.
- Analyzes the impact of dataset constraints on learning agent preferences.
- Presents sample-efficient algorithms for achieving Nash stability.
- Demonstrates optimality guarantees for sample complexity bounds.
- Experimental results show convergence to low approximation levels of Nash stability.
Computer Science > Computer Science and Game Theory arXiv:2602.14321 (cs) [Submitted on 15 Feb 2026] Title:Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions Authors:Saar Cohen View a PDF of the paper titled Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions, by Saar Cohen View PDF HTML (experimental) Abstract: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 ...