🤖 machine learning

Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions

This paper introduces a new model for offline learning of Nash stable coalition structures with possibly overlapping agents under partial information, proposing sample-efficient algorithms that infer unknown preferences from fixed datasets to recover approximately stable partitions under varying feedback constraints.

Original authors: Saar Cohen

Published 2026-02-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Saar Cohen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a massive, high-stakes consulting firm. You have hundreds of consultants, and every week, you need to assign them to different client projects. Some projects are in finance, some in logistics, some in tech.

Here's the catch: You don't know who gets along with whom.

You know that two people might be a perfect team for a logistics project but a disaster for a finance one. But you can't just keep shuffling them around to test it out; that would cost the company millions and annoy the clients. Instead, you only have a fixed, old archive of past projects and performance reviews. Your goal is to look at this old data, figure out the hidden "chemistry" between your employees, and assign them to teams where everyone is happy and no one wants to switch groups.

This paper is about solving that exact puzzle using a new kind of math.

The Core Problem: The "Overlapping" Team

In most old theories, a person could only be on one team at a time. But in the real world, a consultant might work on a Finance project and a Logistics project simultaneously. They belong to overlapping coalitions.

The paper asks: How do we find a "Nash Stable" arrangement?

Nash Stable means a state where no single person can improve their situation by unilaterally switching teams. If everyone is happy with their current mix of projects, and no one has a reason to jump ship, you've found the perfect balance.

The Challenge: The "Blind" Data

The problem is that your old data is messy. You have two types of data archives:

The "Semi-Bandit" Archive (The Detailed Log):
- Analogy: Imagine you have a spreadsheet where, for every past project, you know exactly how much Alice enjoyed working with Bob, and how much Bob enjoyed Alice. You have the granular, person-to-person ratings.
- The Paper's Solution: If your archive covers enough different team sizes (e.g., you have data on teams of 2, 3, 4, and 5 people), you can mathematically reconstruct the perfect team structure. The authors built an algorithm that learns these hidden preferences and finds the stable arrangement with very little data.
The "Bandit" Archive (The Vague Summary):
- Analogy: Now imagine your spreadsheet is much worse. You only know the total score for a project. You know "Team A got a 7/10," but you have no idea if that was because Alice loved Bob, or if Bob hated Alice but tolerated it. You don't know the individual relationships.
- The Paper's Solution: This is much harder. The authors show that with this vague data, you need a stricter condition: your archive must be incredibly diverse. It needs to contain examples of almost every possible team combination to make an educated guess. If your data is too narrow, you simply cannot figure out the perfect team structure, no matter how much data you have.

The "Secret Sauce": The Coverage Rule

The paper introduces a golden rule called "Coverage."

The Metaphor: Imagine you are trying to learn how to bake a cake by looking at photos of cakes people have made in the past.
- If you only have photos of chocolate cakes, you can't learn how to bake a vanilla cake, even if you have a million chocolate photos.
- To learn how to bake any cake (or form any stable team), your photo album (dataset) must include examples of the specific ingredients (team sizes and combinations) that might appear in the final solution.

The authors prove that if your dataset covers these "ingredients" (specifically, the team sizes that would result if someone tried to switch teams), their algorithm can find the perfect arrangement. If the dataset misses even one crucial "ingredient," the algorithm might fail.

How the Algorithm Works (The "Optimistic" Learner)

The algorithm doesn't just guess; it plays a game of "Optimistic Pessimism."

Estimate: It looks at the data and guesses how much people like each other.
Add a Safety Buffer: Because the data is old and incomplete, it adds a "bonus" to the uncertainty. It assumes the worst-case scenario for what it doesn't know.
Find the Balance: It tries to find a team arrangement where, even with these worst-case assumptions, no one has a strong reason to leave.

The Results

The authors tested this with computer simulations:

When they gave the algorithm detailed data (Semi-bandit) that covered enough team sizes, it found near-perfect stable teams very quickly.
When they gave it vague data (Bandit), it still worked, but only if the data was incredibly diverse.
If the data was missing the right "ingredients" (Coverage), the algorithm failed, proving that you can't magic up information that isn't there.

Why This Matters

This isn't just about consultants. This logic applies to:

Organizing research teams in universities.
Assigning drivers to ride-sharing pools.
Forming study groups in schools.

In a world where we often can't run live experiments (because it's too expensive or risky), this paper gives us a blueprint for how to use our past data to build future stability, ensuring that everyone ends up in a group where they belong.

1. Problem Statement

The paper addresses the challenge of Coalition Formation in settings where:

Agents are Selfish: They act to maximize their own utility.
Coalitions Overlap: Unlike traditional Hedonic Games where agents belong to exactly one disjoint group, agents here can join multiple coalitions simultaneously (e.g., a consultant working on multiple projects).
Partial Information: Agents' preferences (utility functions) are unknown a priori.
Offline Setting: The system cannot interact with the environment to gather new data (active exploration is costly or risky). Instead, an algorithm must infer preferences and construct a stable outcome using only a fixed, pre-collected offline dataset of past interactions and utility feedbacks.

The specific goal is to learn a joint strategy (a partition of agents into coalitions) that is $\epsilon$ -Nash Stable ( $\epsilon$ -NS). A strategy is $\epsilon$ -NS if no agent can unilaterally deviate to improve their utility by more than $\epsilon$ .

2. Methodology

2.1 Game Model

POCF Game: Defined as $G = (N, \{A_i\}_{i \in N})$ , where $N$ is the set of agents and $A_i$ is the set of possible subsets of candidate coalitions an agent can join.
Preferences: The paper focuses on Additively Separable and Symmetric (S-ASHG) preferences. An agent's utility is the sum of pairwise utilities with other members in their chosen coalitions. Crucially, pairwise utilities can vary depending on which coalition the pair is in (e.g., two consultants might collaborate well in logistics but poorly in finance).
Stability: The authors prove that symmetric POCF games are Potential Games, guaranteeing the existence of at least one pure Nash Equilibrium.

2.2 Feedback Models

The paper analyzes two types of feedback available in the offline dataset $S = \{(a_m, v_m)\}_{m=1}^M$ :

Semi-Bandit Feedback: The dataset contains agent-level utility feedbacks. For every agent $i$ and every coalition $\ell$ they joined, the algorithm observes the specific utility derived from each other agent $j$ in that coalition ( $v_{i,j}^\ell$ ).
Bandit Feedback: The dataset contains only coalition-level (global) utility feedbacks. The algorithm observes the total utility $v_i(a_m)$ for agent $i$ but cannot decompose it into pairwise interactions.

2.3 Algorithmic Framework: Surrogate Minimization

The core algorithm (Algorithm 1) is a Surrogate Minimization approach designed to handle uncertainty:

Estimation: Construct an estimator $\hat{v}_i(a)$ for the mean utility of agent $i$ under joint action $a$ .
Exploration Bonus: Add an exploration bonus $b_i^\delta(a)$ to create Upper and Lower Confidence Bounds (UCB/LCB) for the utility estimates. This ensures the algorithm is "optimistic" about unexplored actions.
Optimization: The algorithm seeks a joint mixed strategy $\phi_{out}$ that minimizes the dual gap (the difference between the best possible response and the current strategy) based on these optimistic/pessimistic bounds:
$\min_{\phi} \max_{i \in N} \left[ V_i^{\star, \delta}(\phi_{-i}) - V_i^\delta(\phi) \right]$
where $V^\delta$ represents the estimated utility bounds.

3. Key Contributions

3.1 Theoretical Assumptions for Learnability

The paper identifies necessary and sufficient conditions on the dataset coverage required to learn a stable outcome.

For Semi-Bandit Feedback (Assumption 1 - Coalition Size Coverage):
- Condition: The dataset must cover all coalition sizes that can result from unilateral deviations from a Nash Stable (NS) strategy.
- Necessity: The authors prove this assumption is necessary. If the dataset misses even one specific coalition size reachable via a unilateral deviation, no algorithm can efficiently learn an $\epsilon$ -NS strategy (proven via an indistinguishability argument between two game instances).
- Sufficiency: Under this assumption, they derive a sample-efficient algorithm.
For Bandit Feedback (Assumption 2 - Action Coverage):
- Condition: A stricter assumption is required. The dataset's covariance matrix must be "as informative as" a dataset generated by sampling from the strategy induced by any unilateral deviation.
- Impossibility Result: The paper proves that Assumption 1 (Coalition Size Coverage) is insufficient for Bandit feedback. Without observing pairwise utilities, the algorithm cannot distinguish between different underlying preference structures that yield the same total utility, making learning impossible without the stricter Action Coverage.

3.2 Sample Complexity Bounds

The authors provide algorithms with low sample complexity (requiring small datasets) that achieve $\epsilon$ -NS outcomes:

Semi-Bandit: The sample complexity scales optimally with respect to $\epsilon$ (up to logarithmic factors) and polynomially with the number of agents $n$ and coalitions $k$ .
$M = O\left( \frac{n^2 k}{\epsilon^2} \cdot \text{polylog}(n, k, 1/\delta) \right)$
Bandit: The sample complexity is higher due to the lack of granular data but still achieves optimality guarantees up to logarithmic factors under the stricter assumption.
$M = O\left( \frac{n^2 k}{\epsilon^2} \cdot \text{polylog}(n, k, 1/\delta) \right)$
(Note: The specific constants and dependencies on $n$ and $k$ differ slightly between the two, but both avoid the exponential dependency on the action space size often found in general multi-agent settings.)

3.3 Pure vs. Mixed Strategies

While the framework handles mixed strategies, the authors show that for symmetric games, pure Nash Stable strategies always exist. They adapt the algorithm to output pure strategies, which reduces the sample complexity factor related to the number of possible coalition sizes (from $n+1$ to a constant 3).

4. Results and Experiments

Synthetic Experiments: The authors evaluated Algorithm 1 on synthetic datasets with varying numbers of agents ( $n$ ) and coalitions ( $k$ ).
Verification of Assumptions:
- When the dataset was generated by a uniformly random policy (satisfying the coverage assumptions), the algorithm consistently converged to a low duality gap (high Nash stability) as the dataset size increased.
- When the dataset was generated by a biased policy (violating the coverage assumptions, e.g., missing specific coalition sizes), the algorithm failed to converge to a stable outcome, confirming the theoretical necessity of the coverage assumptions.
Scaling: The empirical results matched the theoretical $1/\sqrt{M}$ convergence rate and the scaling with $n$ and $k$ .

5. Significance and Impact

Bridging Offline RL and Game Theory: This work is a significant step in applying offline reinforcement learning techniques to cooperative game theory, specifically addressing the "coverage" problem in multi-agent settings.
Real-World Applicability: The model of overlapping coalitions and partial information is highly relevant to real-world scenarios like consulting firms, research collaborations, and gig economies, where agents work on multiple teams and historical data is the only source of preference information.
Theoretical Rigor: The paper provides the first necessary and sufficient conditions for offline learning of Nash stability in overlapping coalition games. It rigorously distinguishes between the information requirements of semi-bandit and bandit feedback, showing that granular data is crucial for weaker coverage assumptions.
Efficiency: By removing the exponential dependency on the number of actions (which is typical in general-sum games), the proposed algorithms offer a practical path to finding stable coalition structures in large-scale systems without requiring active, costly exploration.

In summary, the paper establishes a robust theoretical framework for learning stable coalition structures from static data, proving that with the right dataset coverage, one can efficiently infer hidden preferences and construct stable groupings even in complex, overlapping environments.