Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions

Saar Cohen Department of Computer Science, Bar Ilan University, Ramat Gan, Israel Department of Computer Science, University of Oxford, Oxford, United Kingdom [email protected] · 2026

Read Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions by Saar Cohen Department of Computer Science, Bar Ilan University, Ramat Gan, Israel Department of Computer Science, University of Oxford, Oxford, United Kingdom [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-14321.txt.

Introduction

Saar Cohen, writing alone, models a 2026 arXiv coalition problem with overlapping groups and partial knowledge. Standard models assume disjoint coalitions and fully known preferences, but real agents may join several coalitions at once while their preferences stay partly hidden. Information arrives only as past interaction data and utility feedback in a fixed offline dataset.

The paper studies two feedback types: agent-level and coalition-level utility feedback. For each, it identifies conditions under which the dataset covers enough information for an offline learner to infer preferences. With those conditions met, the learner can recover a partition that is approximately Nash stable, meaning no agent gains much by switching coalitions alone.

Catalog record

CREATORSaar Cohen Department of Computer Science, Bar Ilan University, Ramat Gan, Israel Department of Computer Science, University of Oxford, Oxford, United Kingdom [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE200 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-14321

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions Saar Cohen Department of Computer Science, Bar Ilan University, Ramat Gan, Israel Department of Computer Science, University of Oxford, Oxford, United Kingdom [email protected] 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 regarding past interactions and associated utility feedbacks 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 feedbacks that can be stored in the dataset: semi-bandit (agent-level) and bandit (coalition-level) utility feedbacks. 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 semi-bandit 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 bandit 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. 1 Introduction In a large consulting firm, managers must assign consultants to upcoming client projects across various domains (e.g., finance, logistics). A consultant may work on multiple projects, one per domain. The compatibility between consultants depends on the domain, e.g., two employees may collaborate efficiently on logistics, but clash in finance due to differing approaches. However, the managers do not have full access to employees’ preferences over team compositions. Testing new team structures through trial projects is also infeasible due to the financial and organizational costs of reassignments, client-facing risks, and time constraints. Instead, managers rely on a fixed dataset of historical project outcomes and post-project peer evaluations. Based only on this limited, pre-collected information, they aim to assign consultants to teams that align with their true but unknown preferences, ensuring no one would prefer to switch groups unilaterally. Such scenarios and many other real-world cases exemplify coalition formation , where agents perform activities in coalitions rather than on their own, and the challenge is forming coalitions that satisfy some desired criteria. A popular model for studying coalition formation is that of hedonic games [ 23 ] , whose outcome is a set of disjoint coalitions (hereafter, partition ). The desirability of partitions is often evaluated in terms of various concepts of single-agent stability based on agents’ preferences [ 2 , 9 ] , where no agent benefits from leaving her current coalition to join another one on her own. A common such notion is Nash stability , where no agent can increase her utility by unilaterally deviating (e.g., no consultant can improve by changing teams unilaterally). In the hedonic games literature, agents express preferences only for coalitions they are part of while disregarding inter-coalitional relationships, and these preferences are typically assumed to be fully known when computing stable partitions. Yet, both assumptions may not hold in many real-life scenarios, as in our consulting firm example. In this paper, we thus introduce and study a new framework of coalition formation with possibly overlapping coalitions in partial information settings, where selfish agents may join several coalitions concurrently, following either mixed or pure strategies, while their full preferences are initially unknown. Instead, we only have partial knowledge about past interactions and corresponding utility feedbacks, which is stored in a fixed offline dataset. The dataset is collected in advance, without further interactions within the environment, reflecting real-life settings where active interactions may be costly and risky, like in our consulting firm example. Our goal is to maximally exploit the available dataset to efficiently infer agents’ preferences. We exhibit our results for additively separable and symmetric preferences [ 8 ] , where any pair of agents assigns the same cardinal utility to one another, and an agent’s utility for her chosen coalitions is the sum of her utilities from their members. However, agents’ mutual utilities for one another may vary across different coalitions, reflecting real-world cases such as our consulting firm example, where a consultant may benefit more from another peer in one domain than in another. Symmetric preferences are realistic in reciprocal interactions like friendships, as widely studied in friend-oriented hedonic games [ 27 , 22 ] . Further, our results for mixed strategies readily extend to asymmetric preferences, where agents may value each other differently, but extending our analysis for pure strategies may be generally infeasible (see Remark 2 ). Many realistic scenarios differ in the type and granularity of utility information available in the dataset. We thus explore the effect of different information constraints by studying two forms of utility feedbacks that can be stored in the dataset. Specifically, we examine semi-bandit utility feedbacks, where agent-level utilities are available for each agent’s interactions with other members of her chosen coalitions. We also analyze bandit feedback settings with less granular utility information, where we can only observe coalition-level utility feedbacks about each agent’s overall utility from her chosen coalitions. Contributions. In both semi-bandit and bandit feedback settings, we characterize assumptions under which the dataset covers sufficient information for an offline learning algorithm to deduce agents’ preferences and use them to construct an outcome that is (approximately) Nash stable. Under those assumptions, we develop algorithms with low sample complexity , requiring only a small dataset to reach a desired approximation to Nash stability. In semi-bandit feedback settings, we design a sample-efficient offline learning algorithm that attains an approximately Nash stable outcome under a minimal assumption on the information covered by the dataset. Our assumption is sufficient and necessary , as we prove that no weaker assumption enables efficient learning of an approximately Nash stable outcome, regardless of the dataset size. Intuitively, we require that the dataset reflects the partitions that may form through unilateral deviations. For instance, in our consulting firm example, if a unilateral deviation would result in a finance team of a certain size, then the dataset should include some past project outcomes with a finance team of that same size. However, under bandit feedback, we show that only a stricter assumption is sufficient for sample-efficient learning of an approximately Nash stable outcome. Specifically, for any agent and any unilateral deviation of that agent from some Nash stable outcome, the stricter assumption requires that the dataset is at least as informative as a sufficiently large dataset generated according to the outcome of that deviation. In many

Read the complete text