BRIDGE: Bi-level Reinforcement Learning for Dynamic Group Structure in Coalition Formation Games
Authors: Shuqing Shi
Nam Phuong Tran
Hao Liang
Debmalya Mandal
Long Tran-Thanh
Yali Du
Venue: ICLR 2026 Poster (2026)
Keywords: coalition formation games
Bi-level reinforcement learning
multi-agent reinforcement learning
Primary area: reinforcement learning

Abstract: The challenge of coalition formation games lies in efficiently navigating the exponentially large space of possible coalitions to identify the optimal partition. While existing approaches to solve coalition formation games either provide optimal solutions with limited scalability or approximate solutions without quality guarantees, we propose a novel scalable and sample-efficient approximation method based on deep reinforcement learning. Specifically, we model the coalition formation problem as a finite Markov decision process and use deep neural network to approximate optimal coalition structures within the full and abstracted coalition space. Moreover, our method is applicable to bi-level optimization problems in which coalition values are determined by the policies of individual agents at a lower decision-making level. This way, our approach facilitates dynamic, adaptive adjustments to coalition value assessments as they evolve over time. Empirical results demonstrate our algorithm's effectiveness in approximating optimal coalition structures in both normal-form and sequential mixed-motive games.

Published as a conference paper at ICLR 2026
BRIDGE: BI-LEVEL REINFORCEMENT LEARNING FOR DYNAMIC GROUP STRUCTURE IN COALITION FORMA- TION GAMES
Shuqing Shi', Nam Phuong Tran", Hao Liang', Debmalya Mandal', Long Tran-Thanh', Yali Du
KKnn's College London, University of Warwick, 3hhe Alan Turing Institute (shuqing. hao. 1 liang, yali. duw@kukkl. ac aac.ia.u..ccc.c.........
(nam. p. tran, Debmalya Mandal,, long. tran tran- baaa--thhnnwwwwwick.c.k
ABSTRACT
Coalition Formation Games investigate how a group of autonomous agents vol- untarily organize into subgroups (i.e., coalitions) to achieve common goals or maximize collective utility. This field has been a subject of long-standing research within game theory and related disciplines. The core challenge in these games lies in efficiently exploring the exponentially large space of possible coalition structures to identify the optimal partition. While existing approaches to solve coalition formation games either provide exact solutions with limited scalability approximate solutions without quality guarantees, we propose a novel scalable and sample-efficient approximation method based on deep reinforcement learning. Specifically, we model the coalition formation game a finite Markov Decision Process (MDP) and utilize deep neural networks to approximate the optimal value functions within both the full and abstracted coalition structure spaces, thereby indirectly deriving optimal coalition structures. Furthermore, our method can be leveraged for bi-level optimization problems where coalition values are determined by the policies of individual agents at a lower decision-making level. This way, our approach can facilitate dynamic, adaptive adjustments to coalition value as- sessments as they evolve over time. Empirical results demonstrate our algorithm's is effectiveness in approximating optimal coalition structures in both normal-fome and mixed-monl motive Markov games.
INTRODUCTION
Coalition formation games constitute pivotal area of research within multi-agent systems, focusing on enabling groups of agents to collaborate accomplishing specific tasks (Shehory Kraus 1998). These games crucial for optimizing collaborative efforts and resource allocation among autonomous entities, exemplified by applications like cooperative social ride-sharing (Bistaffa et al.) 2017), disaster response coordination (Diehl & Adams 2023) Mouradian al.. (017) and smart
grid management (Chis Koivunen 2017 Han et al. 2019). A central challenge this game is
the Coalition Structure Generation (CSG) problem (Sandholm et al. 1998 Rahwan 2008 Dang
Jennings 2004] Aziz & de Keijzer, 2011). which requires partitioning set of agents into mutually
exclusive and collectively exhaustive coalitions, referred as a coalition structure, maximize
social welfare.
Determining the optimal coalition structure poses significant computational challenge, classified as NP-complet (Sandholm et al. 1999). Existing approaches have traditionally fallen into two categories: exact and approximation methodologies. Exact methods (Yun Yehl 1986 Rahwan et al.) 2009) guarantee optimality but are computationally prohibitive beyond small scales, leading to limitations in scalability and restricting their applicability to small-scale problems (e.g., fewer than 40 agents (Rahwan et al. 2015)). This inherent constraint renders them less viable for real-world scenarios involving a substantial number of agents. Conversely, approximation methods (Di Mauro al. 2010 Farinelli et al. 2013) offer more computationally efficient solutions but typically lack theoretical guarantees. Critically, both of these established lines research are primarily designed for normal-form games, necessitating re-computation for each new problem instance and lacking

---

Published as a conference paper at ICLR 2026
mechanisms to address sequential dicision-making in Markov games. Importantly, while any combinatorial problem can theoretically be encoded as an MDP, such naive formulations explode exponentially and provide no exploitable Trructurecomppune is PSPACE-hard (Littman 1996). Our contribution lies in designing a structured, RI-tractable formulation with compact representations and interpretable transitions.
optimal policies for arbitrary MDPs
In this work, to address the limitations of traditional CSG approaches, we formulate the CSG problem within the framework of Markov Decision Process (MDP). To address the complex, sequential massionnmmking inherent in Markov games, we propose a novel bi-level reinforcement learning framework. Our framework is designed with an upper level focused on optimizing coalition formation, modeled as an episodic MDP where states represent coalition structures and actions involve merging coalitions. The reward at this upper level is defined by the change in coalition structure value, crucial design choice that enables the generalization of learned values to unseen structures by exploiting the compositional nature of coalition values derived from their constituent sub-coalitions.. Simultaneously, the lower level of our framework addresses the optimization of individual agents strategies within the coalition structure dictated by the upper level, with agents learning their best responses to the current coalition structure. This bi-level architecture facilitates dynamic adaptation of coalition structures in response to the learning strategies of the lower-level agents, leading to potentially more robust and flexible collective behavior in dynamic multi-agent environments. The use of deep neural networks for function approximation in both levels allows our method to achieve efficient inference for approximating coalition structure values and guiding individual agent policy determination, ultimately lcading to optimal coalition structures.
Our contributions can be summarized follows: First, novel MDP formulation with structure- consistent N x N state representation, O(N) -dimmmmmnsi action encoding via shared scorer 1, and difference-based rewards enabling generalization; Second, BRIDGE, a bi-level RL framework with measurable equilibrium selection a NE(ss) + II, ensuring deterministic transitions; Third, comprehensive experiments showing generalization from to 100 agents, faster inference than traditional coalition structure generation baselines at scale, and robustness to follower suboptimality.
2 RELATED WORK
The CSG problem has been addressed by variety of algorithms, ranging from exact to approximate solutions. Exact methods, such as Integer Programming (IP) (Rahwan et al., 2009), guarantee optimality but suffer from high computational complexity. Notable examples include ODP-IP (Changder et al. 2019), which employs imperfect dynamic programming, and ODSS (Changder et al., 2020), which optimizes the search space by integrating IP with Integer Dynamic Programming (IDP) (Rahwan, 2008). Hybrid exact algorithms (Michalak et al., 2016) for complete set partitioning, have also been adapted for CSG. However, the inherent combinatorial nature of CSG limits the scalability of these exact approaches. In contrast, approximate algorithms aim to find high-quality solutions within reasonable time. Fast code based algorithm (FACS) (Taguelmimt al., 2021) utilizes specific search space representation and heuristics for efficient exploration. The Parallel Index-basee Search Algorithm (PICS) (Taguelmimt et al. 2022) offers an anytime and more scalable solution for larger problems. Our paper also contributes an approximation method based on deep reinforcement learning to tackle large-scale CSG instances.
Furthermore, the principles of CSG find natural extensions to the domain of Markov games, particu- larly in the context of multi-agent systems. Concepts such as task allocation (Zhao et al. 2019 Iqbal
et al.
Chen et al. [017 Peng et al.] 2017 [Shu & Tian 2018) and group division [Lhaksmana 2018 Macarthur et al. | Russell & Zimdars [003] Schneider 1999), widely studied within
2022
cct al. multi-agent reinforcement learning (MARL), exhibit a fundamental resemblance to the challenges of forming effective coalitions
mixeed-moivve Markov games Li et al. 2024). This inherent similarity provides a strong motivation for adopting bi-level reinforcement learning approach in this work to address the complexities of CSG in such settings.
PRELIMINARIES AND DEFINITIONS
In this section we first introduce the classic CSG setting then propose its extension to Bi-level Markoy Games.
2

---

Published as a conference paper at ICLR 2026
Coalition Structure Generation A CSG problem is of size if it is defined A coalition C is any non-empty subset of N. The characteristic function 22 + RR assigns real value to each coalition, indicating the value that this coalition could obtain if they cooperated. A coalition structure CS is partition of the agent set V into disjoint coalitions. Formally, coalition structure CS consists of {CI, C2,.C...... Ck}, where k = [CS] is the cardinality of CS, CS satisfies the following properties: -ن C2 = N, C2 C 0, vi * (1,2...., The goal is to find the optimal CS* that maximizes the value of coalition structure:
of agents
W := (1.2...... n).
of non-empty coalitions CS
k).
The value of CS is v(CS) = Ececs e(C).
CS == arg max v(CS), C)EIT.N)
where II(N) denotes the set of coalition structures on N. The problem of searching for the optimal coalition structure is NP-complete.
Bi-level Markov Games Following the definition of the Stackelberg Game (Simaan & Cruz Jr
1973). we define the high-level agent as the leader agent and the low-level agents as the follower agents. The goal of the leader agent is to obtain the optimal coalition structure. To achieve this, we define the leader's search process as an episodic MDP M₁ (St, T₁ Ar, r1. Hi). Here, S, II) Hi), 8L,, (CI,.... ) E represents coalition structure time step l.- The initial state is the singleton partition 8t,0 == [[-).... ................................ (N)). An action aj corresponds to choosing any two coalitions given si merge, that is, aj E C,),,)) 0 < < j S [ U Ø (where the action a₁ = keeps the coalition structure unchanged). Next, given the current state 8t, time step te and action or, define a deterministic transition function Ti as: T( a1,,,) = (s1.1. at,,.) U (Ucear, C). We set the horizon H; = N - 1. The horizon H; = N 1 is natural upper bound: each merge reduces coalition count by one, so at most N merges reach the grand coalition. The null action enables early termination for non-grand-coalition outputs. The reward of leader is defined as the difference between the next coalition structure value of the followers and that of the current step:
is the set of coalition structures. For each time step l. E (1,
(1(1,4177)) = Σ
Jf(TT 81) EJ 18):
CET(.),))
CEST
where the follower agents' policies are defined as TT. : S S + A(Ay). the follower agents' coalition cumulative reward under such policies is defined as Jÿ (xz). Given a (stochastic) leader's policy ni define the expected reward of the leader
N Σ
(1 TT) =
The (81,t2: Oreter Ty) ml
For the low-level cooperative game, we define the cooperative game as MM (N, Sy, Ty, Ay. Ty. (1) et al., [2024; Du al., (023). The environment state is given by 8f4, E Sy. At each episode k at each timsstep tx. each low-level agent E N receives state s',, and chooses an action of ~ T... The instantancous reward is defined as real-valued functions conditioned on the coalition: rf Sy x A, + R. The actions of all N agents form a joint action aftu := ==aa),,, [a],,," a. The states evolves according to the transition function T, (. & Each follower agent seeks to maximize the expected discounted rewards of its coalition, defined by
19(
= Σ E (1 B4
where E (0, 1) is the discount factor and f.z. (8y, ay) is reward for coalition C E CS. Due to the non-additive structure of the reward function (e.g., when collaboration among agents might incur some cost), the grand coalition A might not be the optimal one.
3

---

Published as a conference paper at ICLR 2026
4 METHODOLOGY
4.1 MDP FORMULATION FOR CSG
The conventional CSG problem centers on the identification of a coalition structure that optimizes social welfare. This optimization objective can be reformulated from the perspective of a single leader agent.
In this work, we employ deep reinforcement learning methodology to approximate the value of the optimal coalition structure. We define the state of the leader agent, denoted as 8,, as the current coalition structure. The action space of the leader agent, as, consists of decisions regarding which pair of existing coalitions within the current structure should be merged. The reward function for the leader agent, rz, is defined as the difference in the value of the coalition structure between the subsequent state, +1,4++1, and the current state, $1,4, To facilitate the application of deep reinforcement learning techniques, we represent each coalition structure 81 as an N x N binary adjacency matrix, flattened into a vector where (i, = 1 if agents i and j are in the same coalition. This compact representation remains equivariant under consistent permutations of agent indices. Actions are merge decisions of arbitrary two coalitions or a no-m no-merge option, encoded as an (N + -)ddimensiona two-hot vector. The encoding dimension thus scales linearly with N, avoiding quadratic growth in network outputs while uniquely representing each merge, which helps maintain scalability and stable learning. An illustration is provided in the Appendix [.T]
This matrix-based state representation facilitates generalization to coalition formation problems with larger agent populations by encoding coalition structures into a vector that systematically captures all pairwise relationships among agents. Such representation provides consistent input format for deep learning architectures. Crucially, this input format is equivariant under consistent permutations of agent indices, and by fixing the agent ordering during training and evaluation ensure stable performance. The framework enables the model to extract generalizable patterns regarding optimal agent grouping strategies. For instance, by acquiring these fundamental coalition formation principles from smaller problem instances, the neural architecture develops transferable knowledge that can be systematically applied to navigate the combinatorially complex space of possible coalition structures when scaling to larger agent populations (e.g.. the learned {{1, 2), {3}} coalition structure value could be transferred to {[1, 2), (3), (4. 5)).
4.2 BI-LEVEL MARKOV GAME FOR CSG
The traditional CSG problem focuses on identifying coalition structure that maximizes social welfare. This concept is also highly relevant to multi-agent reinforcement learning tasks, where coalition formation facilitates efficient coordination by minimizing redundant efforts in applications such as warehouse management. However, in practical scenarios, the value of a coalition structure is often influenced by learning agents. For example, agents must adapt and optimize their policies in response to a given coalition structure, making the problem inherently dynamic. This requires the algorithm to form the coalition structure dynamically. This interdependence between coalition formation and policy optimization can be naturally framed as a bi-level optimization problem. Our framework, however, adopts the bi-level optimization concept by redefining the leader's objective specifically to maximize the value of the coalition structures. This shift in focus aligns with the hierarchical nature of the problem, where the leader prioritizes the global optimization of coalition formation, while the followers engage in local cooperative optimization to realize their individual and collective goals. In this context, the leader is responsible for dynamically determining the optimal partition of follower agents into coalitions to maximize the overall value of the coalition structure. Meanwhile, the agents i E N, acting as followers, aim to optimize the value of their respective coalitions within the constraints established by the leader's partitioning.
By balancing these two levels of optimization, our framework provides an efficient framework for solving the CSG problem. The followers phase can be modeled as a cooperative game, wherein agents work together to maximize the value of their respective coalitions. In addition, the leader phase can be formulated an episodic MDP, reflecting the sequential decision decision-making with the goal of generating coalition structures dynamically. Therefore, the optimization objectives for the leader and followers in the Bi-level MDP can be defined as:
4

---

Published as a conference paper at ICLR 2026
Definition 4.1. In the bi-level optimization problem, the leader and followers aim to solve the following bi-level optimization problem respectively: Given each state St, define the set of Nash equilibrium for set of player C' E Sq:
NE(s)) = { (F fo , .. st).
Where Tf represents the policy of all agents not in C. Given the set of Nash equilibrium of followers' policy, define the objective of leader policy as follows:
max (T) THl
arg MaX Ef
S.L. TT
XyENE(#)) CERL
The above constraints Fy imply that, given the current coalition structure 8t, each coalition C E st acts as single rational agent. We further assume that the players corresponding to coalitions in st will choose the optimal Nash equilibrium if multiple Nash equilibria exist. We adopt a measurable selection rule a: NB(s;) + II, that selects the equilibrium yielding the highest coalition structure reward for each 8₁, which ensures a deterministic upper-level transition reward mapping. In practice, MADDPG-trainee followers provide approximate best responses; Figure 4 demonstrates robustness to moderate approximation errors.
Bi-level Optimization In this bi-level optimization framework (Figure D the leader and the followers operate at the upper level and the lower level. respectively. The tree structure is adapted from (Sandholm et al.) [999),.he leader aims to identify the best coalition structure by learning the optimal policy my E I, which maximizes the value of the coalition structure. The upper-level optimization incorporates the best responses of the followers, represented by their value functions
V/** The leader's objective function JI(mi, TT) depends the leader's action d;, the current coalition structure 8t, and the followers' policies - The constraint ensures that the leader's 's optimization accounts for the followers' best response Tÿ. which maximize their respective objectives. At the lower level, each follower agent i C,C E CSS independently optimizes its own value function J based on its coalition value +f,-- The goal of each follower is to identify the optimal action a} E A in the sense of coalition value, given the coalition structure defined by the leader's 's state st and its current state sy.
Based on the definition of the reward function (Equation TD. we can further define the action value functions for the leader in the CSG process. In framework, the leader agent orchestrates the CSG in high level, while the follower agents operate in the lower-level optimization process, aiming to maximize their coalition rewards. Let Q, and Q, denote the action-value functions for the followers and the leader, respectively. Then, the optimal action value function for the leader defined as:
Definition 4.2. The optimal action value function for the leader agent is:
Qf (st. TT) == (st, at Ty) + max Q7 (T)
of
Based on the definition of the action value function and Bellman operator of the leader agent, we could further define the followers' optimal action value function as follows: Definition 4.3. The optimal action value function for the follower agents is defined as:
Qj ( s1) + (s5) st) + max Q²y" (T)
Due to space constraints, we defer the detailed theoretical analysis in Appendix where we focus on the planning problem under the MDP formulation of CSG and establish the correctness of our RL-based approach. particular, we establish the correctness of our RI-bbased approach by proving that it converges to optimal coalition structures under standard assumptions. This analysis offers rigorous foundation for applying reinforcement learning to coalition structure generation problems.
Algorithm Overview In Algorithm I introduce Bi-level Reinforcement Leariing for Dynamic Group StructurE (BRIDGE) algorithm, a hierarchical framework for optimizing both coalition structures and agent strategies in multi-agent systems. Following the meta-reiinorcement learning
5

---

Published as a conference paper at ICLR 2026
High-Level
(9),
Rax- (8)
Mr
6:3
[P3, 0344)
(D.3)
40% 00.6241
(0.36-0004))
(1-40-20
(2) 83.4
(.0...44)
(1.0..
(D.0).
(D.4) Dusl)
Ag (1) (2.30
+
20,2,3,4)
Figure 1: Bi-level optimization process for the leader agent and follower agents. In the high-level optimization process, the leader agent determines the coalition structure of the follower agents and always starts from singleton coalition (#1.0 = {{1), (2), (3), {4}}). Then the leader will perform the action 0zo0 which leads to the next leader state. The reward is calculated by the difference between value of the coalition structures. This value is achieved by the optimization process in the low-level, where each follower agent optimizes its coalition reward. The high-level episode lasts for at most N 1 merge decisions. Because a null action is permitted at any step, the process may end with non-grand coalition partition.
paradigm, the algorithm's nested optimization structure consists of two levels: the upper level serves as a meta-policy that learns to propose effective coalition structures, while the lower level learns the optimal strategies within the proposed structure. By employing neural networks the meta- level, our method efficiently adapts the coalition structure based on the performance of lower-level policies, enabling efficient searching across different group configurations. The ultimate objective is to determine the optimal coalition structure and the optimal coalition strategies for all participating agents.
The algorithmic process (Algorithm) is structured around two nested iterative procedures. The outer loop is indexed by iteration counter c. each step tc, the leader agent produces coalition structure transition tuple [(S1.t,: Ai,t,, $1,,, (1,... using the leader agent's 's Q-function Qr. This outer loop provides the framework for optimization for the coalition structures. Within each outer loop iteration, the inner loop (indexed by episode counter tx) focuses optimizing follower agents behaviors within the given coalition structure. The follower agents' optimization process adapts the MADDPG framework (Lowe al. 2017) by integrating stochastic policies in place of the original deterministic ones. During each episode, the followers' actors generate transition tuples {(o%.... af. of 0f,4411.7 These transitions are then used to update the critic Qy, which evaluates the quality of actions. Subsequently, the actor is updated using the policy gradient, which is informed by the Critic's evaluations, to improve the agents' policies. Following the completion of each inner loop, the algorithm caleulates the leader's network loss [())). The leader's Q function parameters are subsequently updated using the second learning rate P:- This bi-level approach enables the joint optimization of both coalition structures and individual agent strategies. The slower outer loop focuses on coalition formation while the faster inner loop optimizes agent behaviors within established coalitions. This hierarchical learning structure allows the algorithm to effectively address the complex interdependencies between coalition formation and agent strategy optimization multi-agent systems.
5 NUMERICAL EVALUATION
In the experimental evaluation, we aim to demonstrate three key advantages of the BRIDGE frame- work when applied to CSG problems:

---

Published as a conference paper at ICLR 2026
Algorithm BRIDGE
Input: followers' replay buffer B, leader's replay buffer 9, learning rate faactoors critie Pt=
Output:
approximate coalition structure CS*, approximate coalition strategies for each agent
π
1: Initialize leader Q-network Qr(st, ar; 0t).
2: Initialize follower actor TØ and critic Q3 networks for each follower with random weights.
3: for Iteration c = 0, 1, 2...... ... C...Com do
4: for Coalition time step = 0, 1, N. do
5: Select a random leader action dt, with probability 6, otherwise select dree
arg or. 21,
6: Observe next state 81,t++1 and reward Fl,te
7:
Push transitions {(S1.t.: 31,t,,,8,,ttl1 T(.t.)) into replay buffer G. for Episode tx 0, 1,,1,,.... K do
8:
9:
For agent i 1 .N, play f.tz
CSe
TT based on current coalition structure CSc-
10:
Observe new observation o f reward ,cs.
CS.
fitt"
11:
Push transitions {(0f,1 f.t fou +1 T fit
CS.
CS.
CSe) into replay buffer B,
12:
Sample minibatch of [Biini transitions C
a f.b jib
CS. I.C..
, C.S)) from B.
Compute the target actions from the target policy: a f.b (
14:
Compute the target Q-values: vi
C f.b
.. n. 2Q f,bs f.bi 0z), for C,C CS..
Compute the critic loss: L(O+)
Frrrre En (v) -f af,0 07)
Update the critic by minimizing the loss: fj t fi Pffennic Vo, L(0)).
17:
Calculate the policy gradient: Jo sooma Voz log Toz (a) , (oC (,b:0,)))
Update the actor using the policy gradient: 0f + 0j as V (
19:
end for
20:
end for
21:
Sample a minibatch of 1mmini transitions {( og 86.9 (l,g)) from g.
22:
Compute the target Q-values: Vg .g + max. Qi(s) gg a' 01).
23:
Compute the Q-network loss: I((O)) 15re Eg Qi (1 "g 01))
24:
Update the leader Q-network parameters by minimizing the loss: O: + 6: pt oo,
25:
end for
Enhanced Generalizability: We investigate the capacity of BRIDGE to effectively gener- alize learned strategies from problem instances with a smaller number of agents to those involving larger agent population[Tablel]] T). We also provide comparative analysis our method and other baselines as well(Table
Efficient Inference: We assess the computational efficiency of BRIDGE by comparing its inference time to that of established heuristic CSG methods, highlighting its potential for rapid solution generation(Table 2
Performance improvement in maixed-motive Games:
We evaluate the performance of BRIDGE to address and solve CSG problems characterized by both cormal-form(fe
and Figure 7 and Markov games(Figure) and Figure
We compared our algorithm with C-Link (Farinelli al. 2013). GRASP (Di Mauro al. 2010). CSG-UCT (Wu & Ramchurn) 2020). SALDAE (Taguelmint et al. 2024), which are currently the leading approximate methods for the CSG problem. We provide further ablation studies with respect to our neural network size in Appendix D.3.3
5.1 COMMON CSG BENCHMARK PROBLEMS
A standard approach to evaluating CSG algorithms involves selecting representative problem in- stances and comparing various algorithms without providing them with prior knowledge of the types of utilities they will encounter. While our algorithm is capable of solving CSG problems
7

---

Published as a conference paper at ICLR 2026
Baseline Gain
Basaline Gain
1000
000
000
Number of Agents
Number of Agents
Number of Agents
(a) modified uniform
(b) modified normal
(c) agent- based
2003
1400
Baseline Gain
Baseline Gain
5200
Baseline
800
220
Number of Agents
Number of Agents
Number Agents
(d) hard modified uniform
(e) hard modified normal
(f) combined distribution
Figure 2: Coalition structure value comparison across six different value distributions: (a) modified uniform, (b) modified normal, (c) agent-based, (d) hard modified uniform, (e) hard modified normal, and (f) combined distribution scenarios. The experiments compare four coalition formation baselines comparing their achieved coalition structure values with our algorithm. For each baseline, independent experimental runs were conducted to compute the mean and standard deviation of the resulting coalition structure values,
with varying numbers of agents
across different utility types, we benchmark its performance using three commonly studied util- ity distributions and three harder utility distributions. The three traditional CSG problems are defined as: Modified Uniform(Adams
al. 2010): e(C) ~ UO, 10 x CC), and v(C) is in- creased by a random number r (O, 50) with probability 0.2. Modified ( (Rahwan et al. 2012): v(C) N(1 [C], 0.12), and the coalition value v(C) is increased by a random number r ~~ (0, 50) with probability 0.2. agent-based( Rahwan et al. 2012): (CC) = Eieo P'c where Pe (0, 2p:) and p; ~ U0, 10) is random power for agent i. We also introduce three additional, more challenging utility distributionsshard modified uniform, hard modified normal, combined distri- bution) that incorporate increased stochasticity and implement penalties for larger coalition sizes, thereby providing a more rigorous evaluation framework that better approximates real-world coalition formation scenarios. Detailed specifications of the value functions of these scenarios presented in Appendix [.2]
To evaluate the generalization capability of our algorithm, primary advantage posited in this work, we present the performance results across varying agent populations instances(5 to 10) under modified normal distribution in Table Following initialization of the network architecture to accommodate the 10-agent scenario, the algorithm was initially trained on instances involving agents and subsequently evaluated in environments with 10 agents. Optimal coalition structure values for these scenarios were determined via brute-force search, and the table reports the percentage of the achieved value relative to these optima. While the few-shot conditions involve continued training on the target agent instances for 100 and 200 episodes, respectively. As evidenced in Table I. our method, demonstrates substantial improvement in performance compared to random policy across all evaluated agent numbers. The few-shot training paradigms yield progressively higher performance, with the 200-episode fine-tuning achieving the highest value percentages. These results underscore the robust generalizability of BRIDGE to coalition structure generation problems with a larger number of agents than those encountered during initial training. We also provide a comparative analysis other traditional coalition structure baselines performance with the same budget in Appendix. BRIDGE trains for 300 loter-loop episodes with early stopping when reward variance stays below 1% for 20 episodes.
8

---

Published as a conference paper at ICLR 2026
Table 1: Evaluation of the generalization performance of different training paradigms on coalition structure generation taoks(mddified normal distribution) across varying numbers of agents (5 to 10), with models pre-trained on instances with 3 agents.
Pretrain on agents
5 agents
6 agents
agents
agents
9 agents
10 agents
Random Policy
44.42%
36.59%
36.32%
30.97%
25 35.05%
21.01%
Few-Shot (100 episode)
88.83%
66.17%
59.67%
55.62%
47.18%
41.61%
Few-Shot (200 episode)
97.2%
80.33% %
78.68 %
63.52%
58.15 %
48.24%
summarize our experimental results on the common benchmark problems with utilities using distributions described above. As seen in the figures, our method outperforms other algorithms with better solution quality in all tested instances. We use the Baseline Gain metric (Baseline Gain = =(CS) - -iex Eie v((i))) to quantify improvement over singleton coalitions in complex environments where optimal solutions uniform and hard modified normal experiment, our method can find better results than any other baseline algorithms. This set of experiments demonstrates the advantage of our method compared to state-of-the-art approximate methods. In order to further study how the leader agent's ability evolve over training, we propose visualization results in Appendix D.3
Figures 2a
intractable. In particular, in hard modified
Figure 7
5.2 MIXED-MOTIVE MARKOV GAMES
In the LBF (Level-Based Formation) environment (FigureB) tasks are rep-
LBF
Singleton
C-Link
GRASP
SALDAE
CSG-UCT
BRIDGE
9.11108
25.00.13
31.00116
M.17114
resented by apples with varying sizes that correspond to different resource requirements, where apples randomly spawn across the map. The leader agent must strategically select fol- lower agents to complete tasks while maximizing rewards and each fol- lower agent recruitment incurs cost. Our empirical evaluation compares gain. our framework against traditional CSG baselines across multiple configurations. Since traditional CSG baselines are not originally designed for the mixed-motive Markov games. We adopt the same training paradigm as BRIDGE by calculating the coalition structures value using low-level agents. In the Singleton baseline, each agent operates independently as a self-interested decision maker. Overall, theory assumes optimal follower for clarity of exposition,
6:5t
31.01:144
32.08-11
11.9010077
27.5011
3475118
3111112
Halt
32.95:1177
32.58-144
12:42:099
17.43
34.66115
3.57:11
815t
43.18.1..8
4068-
23.33.1100
31,33.16
15
$21712.11
10u4:
70.02+2.
66.23-18
29.71
41,33+177
73.35=23
77.4+:244
10a51
75.23:12.2
73
33,12113
63.81-200
8283225
89.29:266
Figure 3: Mixed-motive Markov game (LBF) across six dif- ferent scenarios. Values are reported as mean + standard deviation over multiple runs. 'a' represents agents, 't' rep- resents tasks (apples). The value defined as the baseline
this ablation verifies that although the practical system is robust to moderate follower suboptimality and only fails when the follower is so under-trained that it no longer provides reliable local value signals.
To assess our leader agent's robustness to fol- lower policy quality, we conducted ablation study by pairing a leader with follower policies of varying training epochs. The findings demon-
LBF
15 epochs
e0epschs
7 epochs
5 epochs
6a4t
32.11
34.17
26.73
2.82
6a5t
36.87
33.11
34.51
8a4t
37.05
38.57
21.46
9.84
strate that the leader's performance remains high and stable with well-converged followers (10-15 epochs) and degrades accordingly with moder- ately trained ones (7 epochs), showcasing re- silience to approximation errors. As expected, performance drops sharply when paired with poorly trained followers (5 epochs) that provide unreliable reward signals. This study confirms that while our framework theoretically assumes follower optimality, it practically robust to moderate errors.
8a5t
51.24
52.17
47.44
11.49
10a4t
77.54
77.43
69.78
5.38
10a5t
91.28
89.29
88.35
29.97
Figure 4: Comparative performance of the leader follower approximation errors.
CONCLUSION
This paper introduces BRIDGE, bi-level reinforcement learning framework that jointly optimizes coalition structures and agent policies. The framework dynamically adapts to changing conditions, and its theoretical formulation aligns the RI. objective with optimal coalition formation. Empirically,

---

Published as a conference paper at ICLR 2026
BRIDGE performs well across both classic CSG problems and Markov games. These results highlight the promise of bi-level reinforcement learning for multi-agent optimization tasks involving hierarchical decision- opening opportunities for research in coalition formation and multi-agent systems.
ACKNOWLEDGEMENT
This work was supported by the Engincering and Physical Sciences Research Council [grant number EP/Y003187/1 and UKRI849).
REFERENCES
Julie Adams al. Approximate coalition structure generation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, pp. 854-859, 2010.
Haris Aziz and Bart de Keijzer. Complexity of coalition structure generation. In Adaptive Agents and Multi-Agent Systems, 2011. URL httpps://apa www.aaiiisssaaicccoocoa.aaaaa www.aarrrrgrraoeoeee wrg/CorpusIDD
1543721
Filippo Bistaffa, Alessandro Farinelli, Georgios Chalkiadakis, and Sarvapali Ramchum, A cooperative teee--theoeeti approach to the social ridesharing problem. Artificial Intelligence, 246: 86-117, 2017.
Narayan Changder, Samir Aknine, and Animesh Dutta. An imperfect algorithm for coalition structure generation. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 9923-9924, 2019.
Narayan Changder, Samir Aknine, Sarvapali Ramchurn, and Animesh Dutta. Odss: Efficient hybridization for optimal coalition structure generation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7079-7086, 2020.
Yu Fan Chen, Miao Liu, Michael Everett, and Jonathan P How. Decentralized ton-communicating multiagent collision avoidance with deep reinforcement learning. In 2017 IEEE international conference on robotics and automation (ICRA), pp. 285-292. IEEE, 2017.
Adriana Chiy and Visa Koivunen. Coalitional game-based cost optimization of energy portfolio in smart grid communities. IEEE Transactions on Smart Grid, 10:1960-1970. 2017. URL aattps://api. semant icscholate
www.nt www.cooa......oooooooooooooo ID: 10421988
Viet Dung Dang and Nicholas R. Jemnings. Generating coalition structures with finite bound from
the optimal guarantees. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, 2004. AAMAS 2004., pp. 564-571, 2004. URL wtw.ttttst.. /api
semant escho ar. org/ Corpus ID: 866361
Nicola Di Mauro, Teresa MA Basile, Stefano Ferilli, and Floriana Esposito. Coalition structure
generation with grasp. In International Conference Artificial Intelligence: Methodology, Systems, and Applications, pp. 111-120. Springer, 2010.
Grace Diehl and Julie A. Adams. The viability of domain constrained coalition formation for robotic collectives. ArXiv, abs/2306.05590, 2023. httphhtps///aap www.:esssscacccccc.c...ommm
[CorpusDD:2591297]
Yali Du, Joel Z Leibo, Usman Islam, Richard Willis, and Peter Sunehag. A review of cooperation in multi-agent learning. arXiv preprint arXiv:2312.05162. 2023.
Alessandro Farinelli, Manuele Bicego, Sarvapali Ramchurn, and Mauro Zucchelli. C-link: hierar- chical clustering approach to large-scale near-optimal coalition formation. In Proceedings of the 'wweny-Third international joint conference Artificial Intelligence, pp. 106-112, 2013.
Liyang Han, Thomas Morstyn, and Malcolm D. Mcculloch. Incentivizing prosumer coalitions with energy management using cooperative game theory. IEEE Transactions on Power Systems, 34: 303-313, 2019. URL httpt:tttts... //api. semant cschol ar. /tt..o////arpps1105555111111
10

---

Published as a conference paper at ICLR 2026
Shariq Iqbal, Robby Costales, and Fei Sha. Alma: Hierarchical learning for composite multi-agent tasks. Advances Neural Information Processing Systems, 35:7155 35:7155-7166, 2022.
Sara Klein, Simon Weissmann, and Leif Döring. Beyond stationarity: Convergence analysis of stochastic softmax policy gradient methods. In The Twelfth International Conference on Learning Representutions, 2024.
Kemas M Lhaksmana, Yohei Murakami, and Toru Ishida. Role-based modeling for designing agent behavior in self-organizing multi-agent systems. International Journal of Software Engineering and Knowledge Engineering, 28(01):79-966 2018.
Yang Li, Wenhao Zhang, Jianhong Wang, Shao Zhang, Yali Du, Ying Wen, and Wei Pan. Aligning individual and collective objectives in multi-agent cooperation. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL httpps::/opeeeeiiiiiii Sttt//oorunn1d=22YSlBeeee
Michael Lederman Littman. Algorithms for sequential decision-making Brown University, 1996.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-competiive environments. Advances in neural information processing systems, 30, 2017.
Kathryn Macarthur, Ruben Stranders, Sarvapali Ramchurn, and Nicholas Jennings. A distributed anytime algorithm for dynamic task allocation in multi-agent systems. In Proceedings of the AAAI Conference Artificial Intelligence, volume 25, pp. 701-706, 2011.
Tomasz Michalak, Talal Rahwan, Edith Elkind, Michael Wooldridge, and Nicholas R Jennings. hybrid exact algorithm for complete set partitioning. Artificial Intelligence, 230: 130:14-50, 2016.
Carla Mouradian, Jagruti Sahoo, Roch H. Glitho, Monique J. Morrow, and Paul A. Polakos. A coali- tion formation algorithm for multi-robot task allocation in large-scals scale natural disasters. 2017 13th International Wireless Communications and Mobile Computing Conference (IWCMC), pp. 1909- 1914, 2017. URLphtts::/ http::///apppsaa.ieeeee.aao.mae
semant wwweemaantccccchhooo httpaaar..orrcoooo.sii111200000.
Peng Peng, Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent waarrectiiinllyyooodiiiee to play starcraft combat games. arXiv preprint
nets: Emergence of human-level coordination in learning
2017.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
T Rahwan. An improved dynamic programming algorithm for coalition structure generation. In Proceedings of the Seventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2008, pp. 1417-1420, 2008.
Talal Rahwan, Sarvapali D Ramchurn, Nicholas Jennings, and Andrea Giovannucci. An anytime algorithm for optimal coalition structure generation. Journal of artificial intelligence research, 34: 521-567, 2009.
Talal Rahwan, Tomasz Michalak, and Nicholas Jennings. A hybrid algorithm for coalition structure generation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, pp. 1443-1449, 2012.
Talal Rahwan, Tomasz P Michalak, Michael Wooldridge, and Nicholas R Jennings. Coalition structure generation: survey. Artificial Intelligence, 229:139-174, 2015.
Stuart J Russell and Andrew Zimdars. Q-decomposition for reinforcement learning agents. In Proceedings of the 20th international conference on machine learning (ICML-03), pp. 656-663, 2003.
Tuomas Sandholm, K. Larson, Martin Andersson. Onn Shehory, and Fermando A. Tohmé. Anytime coalition structure generation with worst case guarantees. In AAAI/IAI,, 1998. URL https:
7/api. www.ste http://eeeaaaiaccooorroooroo//om

---

Published as a conference paper at ICLR 2026
Tuomas Sandholm, Kate Larson, Martin Andersson, Onn Shehory, and Fernando Tohmé. Coalition structure generation with worst case guarantees. Artificial intelligence, 111(1-2):209-22 1999.
J Schneider. Distributed value functions. In Proceedings of the Sixteenth International Conference on Machine Learning, 1999, 1999.
Onn Shehory and Sarit Kraus. Methods for task allocation via agent coalition formation. Artificial intelligence, 101(1-2):165-200, 1998.
Tianmin Shu and Yuandong Tian. M rl: Mind-aware multi-agent management reinforcement learning. arXiv preprint arXiv:1810.001 00147, 2018.
Marwaan Simaan and Jose B Cruz Jr. On the stackelberg strategy in nonzero-sum games. Journal of Optimization Theory and Applications, 11(5):3335555, 1973.
Redha Taguelmimt, Samir Aknine, Djamila Boukredera, and Narayan Changder. Code-based algorithm for coalition structure generation. 2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI), pp. 1075-1082. IEEE, 2021.
Redha Taguelmimt, Samir Aknine, Djamila Boukredera, and Narayan Changder. Pics: Parallel index-based search algorithm for coalition structure generation. In 2022 IEEE 34th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 739-746. IEEE, 2022.
Redha Taguelmimt, Samir Aknine, Djamila Boukredera. Narayan Changder, and Tuomas Sandholm. A multiagent path search algorithm for large-scale coalition structure generation. Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pp. 2489-2491, 2024.
Nam P Tran, Shuqing Shi, Debmalya Mandal, Yali Du, Long Tran-Thanh, et al. Learning the expected core of strictly convex stochastic cooperative games, Advances Neural Information Processing Systems, 37:22534-22556 2024.
Feng Wu and Sarvapali D Ramehurn. Monte-carlo tree search for scalable coalition formation. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp. 407 413, 2020.
D Yun Yeh. A dynamic programming approach to the complete set partitioning problem. BIT Numerical Mathematics, 26:467-474 1986.
Xinyi Zhao, Qun Zong, Bailing Tian, Boyuan Zhang, and Ming You. Fast task allocation for heterogeneous unmanned aerial vehicles through reinforcement learning. Aerospace Science and Technology, 92:588-555 0888885594220 2019.
A DECLARATION OF THE USE OF LARGE LANGUAGE MODELS (LLMS)
We utilized large language model (LLM) to assist in proofreading and improving the language. grammar, and clarity of this manuscript. The authors retain full responsibility for all intellectual content and claims presented.
B ETHICS STATEMENT
C NOTATION TABLE
We provide the notation tableC here for the readers to check on the physical meaning of the notations.
12

---

Published as a conference paper at ICLR 2026
Symbol
Definition
Coalition Structure Generation
N
Number of agents
- (.,....., , N
Set of agents
CSN
Non-empty coalition (subset of agents)
CS = (CI...,,CE] C+}
Coalition structure (partition of N))
IIN)
Set of all possible coalition structures Characteristic function mapping coalitions to values
0:2N +R
eCS) Ecers v(C)
Value of coalition structure
Leader (Upper-Level) MDP
Mj = (St, Ti, A,, r1, Hi)
Episodic MDP for coalition formation
S II(A)
State space (coalition structures)
$1,0 {[I]..... {N}}
Initial state (singleton partition)
at (C,, C2) Ø
Action: merge two coalitions stop
Ti S: A + Si (1(81,01 TT)
Deterministic merge transition
Reward: coalition value difference (Eq. 1)
Hi = -1
Maximum number of merge steps
Leader policy and optimal policy
Qi(sn, or 01) JI(TI,T)
Leader action-value function Expected cumulative reward
Follower (Lover-Level) Game
M. (N S₁ Tú, AsTTH,3)
Cooperative Markov game among followers
81 E
Environment state
aʃ a-= |a= pap.... af
Joint action of all followers
(s(sss,,))
Environment transition dynamics
(1)
Instantaneous reward of coalition C'
" 7
Discount factor
J
Follower joint policy and optimal policy Expected discounted return of coalition C
(TF)
Follower i's daction-valus function
D DETAILS ON EXPERIMENT SETTINGS
D.1 ILLUSTRATION FOR N-NETWORK AND TRANSITION PROCESS
Q (1, -)
Coalition
O
91
Agent
0
0
flatten
((1), (2), (3), (3),(4)
8:
0
0
N N
N x
Figure 5: Illustration of the architecture of the Q-network used by the leader agent.
Figure 5 illustrates the Q-network architecture employed by the leader agent for making coali- tion formation decisions. The process begins with the initial coalition structure state, such as {{1}. [2], {3), {4]). This state is transformed into an N x binary adjacency matrix, where an entry (i,5) of denotes that agents i and j belong to the same coalition. This matrix is then flattened into an N2 x vector, creating a structured imput that captures all coalition relationships while remaining equivariant consistent permutations of agent indices. The vector feeds into the
13

---

Published as a conference paper at ICLR 2026
Q-network (parameterized by 81), which processes this information to evaluate potential merge actions. The network's 's output, visualized as the yellow vector, is fixed-size (N + 1 array. This vector represents latent values used to compute the Q-values for all valid actions, rather than directly representing the Q-values themselves. Let 2(8) E N+1+1 denote the output of the leader Q-network state For any legal merge (C;, Cj) with i < J. compute action values by composition
Ci a) = (()(
Qi(s, 2N+1(s),
where t is shared pairwise scorer (e.g., additive). We enforce legality via masking and operate only over the legal set in both selection and backup:
a" = arg max Qi(s,a), aEA((s)
y v=r+y max Qi(s', e'EA(s")
The leader agent selects the pair (i,j) that maximizes this computed Q-value, after masking any illegal or unused indices. The final element of the output vector represents the Q-value for the null action (to not merge). This architecture enables the leader agent to make informed decisions through an O(N) -dimensiis encoding of actions, which avoids quadratic growth network outputs even though the number of feasible merge pairs is O This design keeps the framework scalable while effectively guiding the coalition formation process toward arrangements that maximize collective utility.
Q
Coalition
Coalition
Coalition
Coalition
0
Agent
Agent
0
0
Agent
0
1 1
Figure 6: Illustration of the architecture of the transition of the leader agent.
TigureoJilluster the transition process employed by the leader agent in dynamic coalition formation, depicting the generated process from an initial coalition structure towards the final coalition structure. Beginning with the fully singleton coalition {11), (2), (3), {4}} the leftmost position, the system employs dual representational components: blue adjacency matrices that encode coalition membership relationships (with 1s indicating agents in the same coalition), and corresponding yellow action vectors a, that guide action selection. Notably, in the second state after the first merger (f{1,2), (3), {4) H) the system contains only three coalitions, making the fourth dimension of action vector a1 illegal and therefore unavailable for selection this constraint guides the agent toward valid coalitional structures only. The sequence proceeds with subsequent mergers joining agent with the [1, 2) coalition to form {(1, 2,3}. {4]} and finally incorporating agent 4 to achieve grand coalition in { {1,,2 2, 4)}, where the adjacency matrix contains all Is indicating universal coalition membership. Throughout this evolution, the architecture demonstrates how reinforcement learning enables the leader agent to navigate complex coalition spaces within operational constraints, making sequential decisions that optimize toward the system's 's collective objectives.
D.2 DETAILS ON CSG PROBLEMS
Below we detail the coalition value functions used Section 5.1 Throughout, let C (I...., N)
denote a coalition and A: := |C| its size. We write U( b) for the uniform distribution on [a, bj. For normal draws, we use the "scale" parameterization (1, where the second argument denotes the scale (not variance). Global parameters are: baseline factor a > 0. boost probability
0
E [0, 1]. interaction factor 2 0, and size penalty 2 0. The history factor is h ~ u((08, 1.2).
For compactness, we define
Pin (k) 2.2
Psire (k) (k: 4)2 [kk 4), Penal (k) U(0, 2k) 1 6).
14

---

Published as a conference paper at ICLR 2026
Hard Modified Uniform Distribution. Draw base value b 240,, ak). With probability p, draw a boost rb" ~ 11(0,40 40) (otherwise yumi
0). The coalition value
V(C) = max (0, h 16 ro Pim (im - Prize (k) Peoal (k)))
Hard Modified Normal Distribution. Draw a base value b ~ (N(0, 2k) (scale 2k). With prob- ability p. draw a boost vi (O, 40) (scale 40; otherwise rh 0). The coalition value
is
V(C) max h (b rb reom Pimi Pim Paize (k) Peual Pecm(()))) (A:)]
Combined Distribution. Draw two base values buni (0,, ak) and Deorm NO,,, 2k). With probability p, add independent boosts r. [d(,, 40) and rb NO, 40) (otherwise each 0). The coalition value is
V(C) = max( 0, [uuni + Unorm + rb + norm Pin (k) - Psize - Devas Deoa(k)))
D.3 ADDITIONAL. EXPERIMENT RESULTS
In order to further evaluate the learning dynamics of the BRIDGE framework, we provide additional results on evaluating the optimal gain across outer iterations. The optimal gain(max v(CS) is defined as the best coalition structure value algorithm could get under the present agent number. The results demonstrate the achievable optimal gain scales positively with the number of agents, as expected a system with increasing resources. This learning process appears to converge around 300 steps; the mean gain plot, box plot distributions, and heatmap all show that performance gains become marginal after this point, with the results for steps 300, 400, and 500 being nearly indistinguishable. While the average performance stabilizes, the standard deviation plots and the widening distributions in the box plot reveal that the variability of the optimal gain increases in larger systems, indicating a more complex and diverse solution landscape as the problem scales.
D.3.1 INFERENCE SPEED
The efficiency of inference following the training phase is another notable advantage of our framework. Table presents a comparative analysis of the inference times, measured in seconds, for BRIDGE and several baseline coalition structure generation algorithms under the modified normal distribution setting. While our method's 's inference speed is comparable to or slightly slower than other heuristic methods for lower agent counts (30-50), exhibits significantly improved performance as the number of agents increases (60-100). Notably, the inference time of our method demonstrates considerably less pronounced scaling trend with the number of agents compared to the heuristic baselines, particularly CSG-UCT. This characteristic suggests greater potential for BRIDGE to be effectively applied to coalition structure generation problems involving larger agent populations.
Table 2: Comparative analysis of inference times (in seconds) for coalition structure genera- moddiiieee normal distribution) using baseline algorithms and the proposed BRIDGE framework across varying numbers of agents (30 to 100).
Time(s)
30 agents
40 agents
50 agents
60 agents
70 agents
80 ugents
90 agents
100 agents
C-Link
3.44
4.49
7.11
10.60
14.28
18.77
24.42
30.44
GRASP
0.37
0.88
2.93
5.81
8.19
10.95
19.86
26.47
SALDAE
0.56
1.57
2,54
5.30
8.61
14.13
19.74
28.31
CSG-UCT
2.24
7.10
17.19
35,90
68.15
116.18
194.01
303.79
BRIDGE
1.09
1.98
2.83
3.62
4.90
5.67
6.84
8.72
D.3.2 ADDITIONAL GENERALIZATION ABILITY ANALYSIS
Traditional Coalition Structure Generation (CSG) baselines, such as C-Link, GRASP, and CSG-UCT, typically search-based heuristic algorithms. Their methodologies for a fixed number of agents, requiring the problem size to be predefined to construct the search space. Consequently, these methods do not possess intrinsic mechanism be trained 3-agent
inherently designed
15

---

Published as a conference paper at ICLR 2026
Optimal Gain of Different Steps
Std Different Steps
122
Sted
Agent Number (N)
Agent Number
values with std
(b) std values comparison
Optimal Gain Heatmap
Optimal Gain Distribution of Different Contigurations
Agent Number
800
1224.2
3200
1093
1259.
1350.
13725
330
-20
176.
1159
1481-9
1135-8
11150
3116
Training Steps
Agent 291
(c) value distribution
(d) value heatmap
Figure 7: This set of visualizations illustrates the variation in optimal gain across different training steps and agent numbers. Subfigure (a) shows the mean optimal gain with standard deviation, indicating a gradual increase in gain as the number of agents grows. Subfigure (b) compares the standard deviation across different training steps, revealing fluctuations in multi-agent systems of varying sizes. Subfigure (c) presents a box plot of optimal gain distributions, showing an increasing spread as the agent number rises. Finally, subfigure (d) provides heatmap representation of optimal gain evolution, where darker colors indicate higher gains. Together, these visualizations highlight the impact of training steps and agent numbers on optimal gain.
instance and then tested on a 10-agent instance: the knowledge or heuristics from one problem size is not transferable to another. In contrast, our BRIDGE framework formulates the CSG problem as Markov Decision Process (MDP) and employs a neural network approximate the optimal coalition structures. By representing the coalition structure as a consistent vector capturing coalition membership,
model learns generalizable patterns of agent interactions that remain relevant even as the number of agents changes. the following table, we present baseline results trained under the same sample budget for comparison in Appendix D)3.2
Table 3: Performance comparison with limited training budget (200 episodes) under modified normal distribution. The values represent the percentage of the optimal value achieved by each algorithm when trained from scratch on different problem sizes.
Algorithms
agents
6 agents
agents
agents
9 agents
agents
C-Link (200 episodes)
24.65%
22.85%
25.65%
32.41%
29.00%
34.70%
GRASP (200 episodes)
25.53%
29.55%
27.58%
29.46%
32.83%
36.72%
SALDAE (200 episodes)
25.54%
25.59%
30.84%
36.80%
36.27%
37.58%
CSG-UCT (200 episodes)
23.38%
21.13%
26.77%
38.72%
37.65%
40.81
BRIDGE (200 episodes)
97.20%
80.33%
78.68 %
63.52%
58.12%
48.24%
16

---

Published as a conference paper at ICLR 2026
We calculated the approximate number of samples and let the baseline algorithms train from scratch on to 10-agent instances. The table reports the percentage the achieved value relative to the optima. All baseline algorithms perform poorly under this limited budget. Their performance generally ranges from only 20% to 41% of the optimal value. For instance, in the 10-agent scenario, the best-performing baseline, CSG-UCT, only reached 40.81 % of the optimum. This result is intended to demonstrate that, unlike the BRIDGE algorithm which can leverage pre-training to adapt quickly, these traditional algorithms require much larger computational budget to find high-quality solutions when starting from scratch.
D.3.3 ABLATION STUDY ON NETWORK STRUCTURE
We provide an ablation study on the effect that the neural network size might have on the performance.
Table 4: Ablation study on neural network architecture under modified normal distribution experiment. Performance is measured across different numbers of agents. Values reported mean + standard deviation.
Network Stactare
spents
opeats
apciia
aucoia
apcista
opesti
=
1501.42
$14.4
742.28
08.57
60.45
73.76
734.22
1043.60 104.09
104.55
1434,10
105.52
1492.39 108.97
The results indicate that increasing the network width from 64 to 128 neurons (3 layers) provides a modest but consistent performance improvement, particularly in scenarios with more agents. However, further increasing the network's ' depth to 4 or 5 layers does not yield additional significant gains and can lead less stable performance across different agent counts. This suggests that the layers (128,128 architecture provides sufficient representational capacity for this problem, striking an effective balance between model expressiveness and the risk of overfitting or increased optimization difficulty.
We also provide an ablation study on the effect of the neural network size that might have on the inference AppendAppe D Table 5). We could see that the inference speed does not scale up appreciably with respect to the parameters, showing our method is efficient compared to other CSG baselines.
Time(s)
30 agents
40 agents
50 agents
60 agents
agents
agents
agents
100 agents
3 layers(64.64)
1.09
1.92
2.78
3.55
4.53
5.54
6.84
8.39
12yers(1281128)
5.67
7.02
4 layers(128,12))
1.10
1.98
2.85
3,63
4,90
5.82
7.10
9.14
5 layers(128,128)
1.12
2.01
2.85
3.67
5.12
6.02
7.12
9.86
Table 5: Comparative analysis of inference times (in seconds) for coalition structure genera- tion(modified normal distribution) using different network size of BRIDGE's leader agent across varying numbers of agents (30 100).
D.4 HYPERPARAMETERS SETTING AND COMPUTATIONAL RESOURCES
We use an actor-critic algorithm for follower policies. Followers within the same coalition share
critic parameters.
The hyper-parameters for Actor-Critic training are as follows.
Actor Learning Rate is 1 10-4
Critic Learning Rate is 1 10-4
Target Network Update Rate is 0.005
Discount Factor (7) is 0.99
Replay Buffer Size (B) x 106
Minibatch Size is 256
17

---

Published as a conference paper at ICLR 2026
For leader agent, adopt the DQN algorithm approximate the coalition structures' value. The hhper--arameterr parameters for DQN training are as follows.
The learning rate is 10 10-3
The replay buffer size is 10000.
The minibatch size is 128.
The target Network update frequency is 100 steps.
The exploration Strategy is e-greedy:
Initial c: 1.0,
Final e: 0.01,
Decay Steps: 10000 time steps.
The loss function is mean Squared Error (MSE).
The gradient clipping 40.
The optimizer is Adam.
All experiments were conducted on HPC system equipped with 128 Intel Xeon processors operating at a clock speed of 2.2 GHz and 40 gigabytes of memory.
D.5 POLICY AND VALUE NETWORK REUSE
In our implementation, the follower's policy network (the actor) is reinitialized the start of each outer-loop optimization, whereas the follower's is value network (the Q-network/critic) is persistent and parameters are reused across coalition structures.
Why We Do Not Reuse the Policy Network. This design choice is made to avoid policy inertia. When the coalition structure changes fundamentally (c.g., an agent transitions from large cooperative group to solo role), the previously learned policy may be entirely suboptimal the new context. Re-initializing the policy network ensures that the agent can freely explore without being constrained by outdated behaviors, which allows it to more effectively converge to the true optimal behavior under the new structure.
even harmful in
Why We Reuse the Critic-Network. By contrast, the Critic-network captures more generalizable value information across diverse coalition configurations. This knowledge is transferable: when newly initialized policy network begins to explore, the persistent Critic- provides immediate and informed evaluation of actions. Such guidance accelerates policy learning and stabilizes training the presence of dynamic coalition changes.
Table 6: Value/Policy reuse ablation (LBF). V=Value network, =-Polcy network.
Configuration
6a4t
6a5t
8a4t
8a5t
10a4t
10a5t
Reuse V Init
34.2+1.4
33.1+1.2
38.6:1.6
52.2+2.1
77.4+2.4
89.3+2.6
Reuse V Reuse
30.2+1.3
29.5+1.1
35.341.6
47.4+1.9
69.8+2.3
81.9+2.7
Init V / Init π Init V Reuse
17.2+1.6
18.8+1.6
26.3+1.8
35.3+2.1
55.5+2.2
60,9+2.5
28.6+1.5
30.9+1.2
33.1+1.7
45.5+2.0
65.7+2.4
78.6+2.6
E HORIZON ABLATION STUDIES
Table reports performance across horizons H E N 10, 5, - 11 on the modified normal distribution. Shortened horizons (N/2) underperform at larger scales due insufficient search depth. The full horizon N - yields the strongest values; intermediate horizons offer compute-quality tradeoffs.
18

---

Published as a conference paper at ICLR 2026
Table 7: Horizon sensitivity (Modified Normal), Format: Coalition Value std.
H
30 agents
50 agents
70 agents
100 agents
N/2
445.3=65.7
693.9479.1
956.1+106.
1187,4+117.5
N 10
447.9=65.8
726.3+80.2
994.6=83.1
1344.7=105.7
5-5
447.9=62.4
743.9+91.6
1025.62104.8
1401.9:110.3
N-1
449.4264.8
746.6+85.8
1046.3+1019
1596.2+1154
F DETAILS ON THE PROOFS
In this section, we detail the rigorous convergence analysis of the proposed bi-level optimization framework for coalition formation. First, establishes critical correspondence between the reinforcement learning objective function and the target objective of finding the optimal coalition structure. Then, we move provide definitions and proofs for the monotonicity and additive homogeneity of the leader agent's 's Bellman operator, and a central theorem providing the dynamic programming equations for the fmite-horizon Bi-level MDP. This theorem guarantees the existence and uniqueness of optimal policies for both leader and follower agents, where the follower's 's policy maximizes collective value within Nash equilibrium constraints and the leader's policy optimizes based on a modified Bellman equation incorporating follower responses, Finally, we leverage existing results to assert the global convergence policy gradient descent for this framework, demonstrating that the problem can be simplified to single MDP under optimal Nash equilibrium selection in the inner loop.
F.1 OBJECTIVE CONSISTENCY
Our theoretical investigation examines the relationship between the optimized objective function and the target objective function, where the latter is defined as finding the optimal coalition structure. Another key focus of our analysis understanding the optimal form of the leader agent's policy and the follower agents' policies under the Bi-level MDP. A critical aspect of our analysis is the formal development of a correspondence between the objective function of our reinforcement learning and its target counterpart. This correspondence serves the basis for deriving rigorous optimal form of the leader and follower agents' policies.
Lemma F.1. The oujectivvffunction in Algorithm equal to the target objective functionn.
max J1 Ji mT) m.ny
Σ
(sg.)).
CSELL(A) GECS
Proof. Considering the LHS. Fixing Tf, we have that
N
N-1
Σ mis 01)
Σ Σ
15(T8)
Σ Jf(TF)
=
te OCET
CESLAO
telescoping sum
(T
CE
Note that, given CS, Eceos vC:*(850) = Ecers max,, Jy(T)). Moreover, thanks to con- struction of for any given CS E II(),, one can construct policy x that terminates at CS. Therefore,
max Ji(TI, Ty) W2.ly
max CSEN(A))
Σ vOi*(s)o).
(3)
CECS
cornerstone of our theoretical analysis is the establishment of a precise mathematical correspon- dence between reinforcement learning objective function and its target counterpart in coalition
19

---

Published as a conference paper at ICLR 2026
formation. This lemma establishes the equivalence between two critical quantities: the expected sum of rewards Ji for leader policy и and follower agents' policies π across N steps under different system states a (left-hand side), and the maximum coalition structure value v of final actions a given the selected configurations C' (right-hand side). We establish mapping from policies to coalition structures that yields a telescoping identity (Lemma F.I.. aligning the RL objective with the target coalition value and enabling standard convergence arguments under our assumptions. Through this mapping, demonstrate that the value function VRL (T,, yT converges to the optimal coalition value Virga((C*) This correspondence enables us to establish a practical form of the optimal policies of the leader agent and follower agents. Before moving to the proof of the form of optimal policies for leader agent and follower agents, first we define the bellman operator of value function of the leader agent to be:
Definition F.2. The leader agent's Bellman operator of value function is:
(BiV)) [5) = max ai
11(811 01tt TT) Ti(o Mon
F.2 CONVERGENCE ANALYSIS
Based on the definition of the value function of the leader agent. We could further establish the proof for leader agent's monotonicity and additively homogeneity.
Lemma F.3. (Monotonicity for Leader Agent) For Vi I V22 V < B,V?
Proof. Based on previous definition of Bellman operator value function(Equation 4p. We have:
V $ V??
Ti a1.t Vi' (1.for1:7 ) S Ti a1 V
(4)
max [Ti(s a1, (S1, Tn) < max [T((SL ate, (SLLer))
The reward max., (88,t A1,o, Ff) is identical for BVV, and B, B.V. Therefore, we have:
max maxr(si,..) alt.. Ty) + max [Ti(s,,,, a.e. VV (S1, xy)] S imaxr(st,.. a1e,, TT) + max Ti(s,,,, a1, VI T Rt)
max [r(sue,) o1te RT) Ti a.,, (81,
(5)
at
I max (1ss,, + (i al Vy, (S1 VZ2 [y]]
B < V.V.
This concludes the proof.
As for the additive homogeneity for leader agent, we have: Lemma F.4. (Additive homogeneity for Leader Agent) For any constant c, the Bellman operator satisfies:
(1 =
Proof. Based Equation 4 the Bellman operator of leader agent is defined as:
(B: TT) = max r (1
Σ
Ti(S a1 Wi
(6)
81.
20

---

Published as a conference paper at ICLR 2026
In order to prove the additively homogeneous property of our Bellman operator, could further denote our Bellman operator as:
(Vi + (5),
r( (5 Olite TT) +
Σ
T(stte 11: +c)
81.t011
max
r( ( Ol,te TT) +
Σ QLs +c- E
T(stte (7)
max
r( (B 01,tt TT) +
Σ
+c
(8), Ty) +,
which concludes the proof.
Finally, based on the previous proof, we could move to the proof of the optimal form the leader agent and follower agents when the algorithm converge.
Theorem FS (Dynamic Programming Equation for Markov Decision Process with Finite Horizon). Given leader state 8t, define the optimal follower policy a as:
(9
arg max
ENE(at) CEST
Let Vÿ be the followers' value function corresponding to optimal policy τ... Let V be the optimal value functtio of the leader agent's Markov decision problem, for all time-step te {O...., N 1}:
Vite (st, 77) = -max [ruee (81, (11,01, (1,
+ Vi (Ti(s), T7);
where the maximum is taken over all strategies starting time i. The optimal leader policy nं is defined as:
पं (si) = arg max [r/- (St, at, #5) + VT (T(l)) of"), ).)})]
Proof. We denote (wi, JosisN sequence with final condition w.\ = s. Based on Definition 4 Wt. (W) We need to show that wt_ = Vt,, for all te E .o....,
. N and that V/2
1. Proof of we. VLLe and 2 V₁. For Vi,t. use policy starting time t.r the inequality Wt. Vi.. is of same type Wt. Vi,t. Therefore, only show we 2 1/2
the process associated to the strategy mi and let Tte (8L,0, dr,0, 81,1, at.1...., St,a.), for all 4, 2 0, be the history trajectory. For all S la S N, and all histories We could denote the value function as:
Let (SI, (r...)
Σ m(ooes) p(SLT))lT
VL, (T.) Bag carry
(8)
where Vi,. (Tr.) represents the expected total value starting from time step te and conditioning on history Th. Therefore, Vi, satifies the Kolmogorov equation for an additive functional:
Vr.r = Ea [rr( ar,).) + Vi,e+ (Tr, +1, )
(9)
We could further rewrite the sequence w/. (31,e.) as:
Wt. (81,1.) max (rr( (Sttte a1.e) E [We.+ 1 (81,
(10)
arー
21

---

Published as a conference paper at ICLR 2026
Let's show wy. (s, 2 Vi.e. (Tr.) by backward induction tc. This inequality is true for t. N, since Vi.r. (Tre) = (SI.T.) = wr. (st.r)).. If the inequality is true for te + 1, then from the upper
Equation and Equation I0
deduce:
(Tt,) - E [M((s a1,,)) + we, +1 (s
= E [ri(stte an,.)) + E [wr, (SLA 18,,, at..) [Tt.]
(11)
Σ
TL,,, Ie. (T. a...)) ) + E [wr, (144, a.a..l.
Based on Equation 10 proves the induction. Since Vi,((Sto) = (Sto: (1,)) = J T Tf), taking the maximum over all strategies, deduce that (L,0( S (8L.)) Since JI (T,, (y) E [Ti(st, at,t (V.o,,).onnss. s E [T )... )01,0(88.0) taking again the maximum over all strategies, we deduce Vi S w.
could deduce Vi,,, (Tx.) 2 E [wn, ($L,,, 1T, ne, wt, (st,,)), which
2. Proof of wt, Vi.e, and Vi when the maximum in F5 is attained. related to policy is defined as B Assume the maximum in
The bellman operator
Wi. max B (wt,+1): aIE
(12)
attained for some policy Ti E HI. Denote πi (TI1, Then,
Wt, B,,, (wt,+1). i= ==0,... O,...,N,
(13)
which means that k.2.).220 satisties the same Kolmogorov equation PPuterman with same final condition Wr. = = J.. Hence, Wt. = Ji, for all te O. So wt, S Vi where the value V2, is obtained as the maximum over any set of strategies. Similarly, w E [Ti a1,t,)
2014 as Ji,te
) [o S JIT.. S ViLa.
3. Proof of W/. I VLL and w S Vi in general. Assume now the maximum in 12 is not attained. We only assume that the 71 are bounded from above, for all l. S N. This condition ensures that operators BL.,, are well defined as operators from R to itself. For all >> 0, le S N and V/ E R, there exists गं E II such that
BT (V)) (si) 2 [B,,, (Vi) (si) -, Asa E St.
(14)
The inequality could be extended to all possible states:
B (Vi) 2 B1, -el.
(15)
Let Mi.t The such that Therefore, we could have
Bh (wr++1) 2 Bi,t. (wt,+1) el.
(16)
Bi (wi+t)) 2 Wt. cl. Denote 2t, wt, + (te - Telel. We have EN WN and
(17)
1,1. (2),+1) Bi, (w)++1) + (tc + Tc)e1 2 wt. + -
= -t)eeT
(18)
Based on Lemma F.4 By is additively homogeneous. Then, we shall show the inequality 2t S T
by backward induction on to. Since 2T. ip Jitr. the inequality holds for t. T., If it holds for to + 1, then
2t. < <B where the first inequality follows from Equation [8] the second one follows Lemma < Ju yo, Therefore, we could deduce:
Bi (zt.+1) S Bi
I,t. S Vi,e.
(19)
This shows
Wt. 24, + (To tc)c1 Vi, + (Te - tt)ee,
(20)
for all fo E f1....,,A. N). Since we have shown this inequality for all c > O, we deduce that Wt, S Vi,.. for all t, f1....,N N). Similarly = Tr, wh T, 20 Tee S Vi,, + Tec, and since this holds for all e > 0, we get w < Vi, which concludes the proof.
22

---

Published as a conference paper at ICLR 2026
This theorem establishes three fundamental results for hierarchical decision-makinn in coalition formation. First, guarantees the existence and uniqueness of optimal policies for both leader and follower agents through a nested optimization structure. The follower's optimal policy Tÿ maximizes the collective value across all coalitions while maintaining Nash equilibrium constraints, ensuring strategic stability within each coalition. Second, the leader's value function follows a modified Bellman equation that incorporates the followers' optimal responses, creating dynamic group structure that accounts for the hierarchical nature decision-making The leader's rewards and state transitions explicitly conditioned on the followers' optimal policy, capturing the bi-level interaction between agents. Third, the optimal leader policy emerges from maximizing the sum of immediate rewards and future values, where future values reflect both the direct consequences of leader actions and the induced changes in follower behavior through the state transition function Ti. At last, we can apply the global convergence result of policy gradient descent for finite-horizon MDPs (Klein et al. 2024) as follows:
Theorem F.6 ((Klein et al. 2024)'s Theorem 3.5). Let the number of iterations ep =
O
and let the step size be p2 s.2 Then,
Vi.0
S
2 1
(21)
1,0
As a result of Theorem F.5 given that the agent chooses the optimal Nash equilibrium in the inner loop, the problem of finding the optimal coalition can be viewed as single MDP Mi (St, Ar, Tú, ri 1).
23


Reviews:
[{"review_id": "o7O477i5Dg", "reviewer": "Reviewer_qNH2", "summary": "The paper proposed a novel algorithm called Bridge that tackles the Coalition Structure Generation (CSG) problem, which is the problem of how a group of agents should organize into subgroups to maximize collective gains. The proposed method formulates the problem as a bi-level reinforcement learning optimization problem, where an top-level leader agent aims to obtain the optimal coalition structure, and the follower agent aims to find the best strategy for each agent under the current coalition structure. The paper evaluates Bridge on three traditional CSG problems, showing superior performance than the current leading approximate methods for the CSG problem, and shows generalization capabilities with varying agent populations.", "questions": "- Are there experiments on reusing the follower’s policy network for each outer-loop optimization? In what scenarios might such inertia hinder or help performance?\n- What assumptions are required to guarantee the convergence of the proposed algorithm?\n- Since the leader agent’s actions are limited to merging coalitions, the states are not recoverable as the algorithm cannot split a coalition once formed. Would this affect the method’s overall performance?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written, with clearly stated motivation, problem formulation, and evaluation setup.\n- The use of bi-level reinforcement learning is well-justified, as the problem is naturally hierarchical.\n- Theoretical analysis is provided, including proofs demonstrating the existence and uniqueness of optimal policies under the proposed training objectives.", "weaknesses": "- For the proposed algorithm, the reward for the leader agent inherently depends on the optimization of the follower agents. This might be very computationally expensive, can potentially be unstable, and slow to converge, making the algorithm challenging to tune in practice.\n- The generalization experiments across varying numbers of agents are only demonstrated on a small scale (from 5 to 10 agents). How well does the method generalize when the number of agents changes more substantially?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m4FX5xicaP", "reviewer": "Reviewer_XJMV", "summary": "This paper tackles the problem of coalition formation games by formulating the problem as a MDP and decomposing the actions of the \"coalition structure chooser\", which plays the role of the leader, and the follower(s), whose goal is to play the right actions given the coalition it is in. The paper claims that empirically their approach performs better than existing methods and can \"generalize\" to a larger number of agents even if trained on a small number of them.", "questions": "See the weaknesses section.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "The paper is easy to follow.", "weaknesses": "- My primary consideration is that this paper's technical novelty is very light. Virtually any problem, including most combinatorial NP-hard problems can be formulated as \"a MDP\" where policies are essentially performing some kind of local search and rewards are the improvement in some objective. This includes say, problems like MAX-SAT or coloring problems, or even just a simple subset-search problem, which would seem like special cases of this coalition problem. As such, it seems to me that using RL is essentially throwing the kitchen sink at a difficult problem with little technical insights nor novelty.\n- To expand on the earlier point, while empirically \"performing better\" than existing methods is welcome, the revaluation was in my opinion too simple. It seems to me that more than BRIDGE being a generally performant method, existing evaluation benchmarks simply contain a lot of structure that the RL based approach is able to exploit. To this end, could the authors comment on how well BRIDGE performs if all $J^C_f = 0$ except for one particular $C^*$?\n- In Figure 2, how many epochs of training were performed? Could the authors give a brief classification of competing methods in the main paper? Are these heuristics or also ML based methods? How was computational cost normalized across competing methods? Was training time included in computational costs? While *inference times* were stated in appendix B3, is this not is an unfair comparison to classical methods which do not involve training? If \"training times\" were not included as part of computational costs, could one not simply precompute the solution to the fixed game and report an inference time of 0? [Note I am not referring to the \"generalization\" setting in Table 1\". \n- I found the section on mixed-motive games extremely unconvincing. The main problem here is that once the problem enters the mixed-motive (general-sum) regime, the problem becomes ill-posed. How are agents in a coalition assumed to behave? The most natural assumption is the Nash equilibrium, such that no individual agent is incentivized to deviate. But, it is well known that in general-sum games, the Nash equilibrium may not be unique and equilibrium selection must be performed. It is also rarely the case that MARL based methods (like MADDPG) converge to Nash, since even the tabular problem is PPAD hard and inapproximable. It is my understanding that the authors simply took \"convergence\" of the individual agents' policy to mean some kind of stability in the coalition-level game (see line 467, \"well-converged followers), which isn't necessarily true in general. \n- I also found the claim that BRIDGE generalizes to a larger number of agents better to be poorly supported. First, the authors show a marked performance against a random policy. This is obviously a poor baseline to compare against, and indeed, it is surprising that a random policy can even obtain 20% of the optimal, suggesting in fact, that the payoff structures are in fact quite simple to begin with.\n- Can the authors elaborate on how the utilities were practically generated? For instance, the authors use the agent based method (Rahwan, 2012), which states that $v(C) = \\sum_{i \\in C} p^i_C$, but here, $p^i_C$ is drawn from a uniform distribution (presumably, independently of all other $p^i_{C'}$). In some of the experiments, the authors claim to scale up to near 80-90 agents. This means there are approximately $2^80$ coalitions and hence that many $p^i_C$, which is obviously practically impossible to enumerate. Were these generated upfront, or on-demand?\n- This is a comparatively minor point on architecture design. In Section B1 and 4.1, the authors represent coalition structure as a NxN adjacency matrix where each edge is 1 if and only if two vertices are in the same coalition. I agree this representation is \"nice\" because of permutation invariance between agent labels. However, the representation of the \"merge\" actions (see Figure 6) does not seem to be permutation invariant, since every timestep the number of coalitions drops by one and the only actions allowed (yellow vector) are the first-#-of coalitions remaining. Wouldn't a simpler action representation be to simply have 1's on the vertices which would be merged? And if two vertices are already in the same coalition then the action does nothing. In this case, there would still be permutation invariance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4JnlerOwwJ", "reviewer": "Reviewer_z4ek", "summary": "The paper studies Coalition Formation Games (CFGs) and proposes a scalable, sample-efficient approximation method grounded in deep reinforcement learning. The authors model coalition formation as a finite MDP and train neural networks to approximate value functions over both the full and an abstracted coalition-structure space, indirectly yielding coalition partitions. They argue the approach supports dynamic, adaptive updates to coalition values and can be used in bi-level optimization settings where coalition values depend on lower-level agent policies. Empirically, the method is evaluated on both normal-form and mixed-motive Markov games.", "questions": "Please refer to the above weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The overall paper structure is clear, and the theoretical background is sufficiently motivated and well organized.\n\n2. Framing coalition formation as an MDP and learning value functions over full and abstracted spaces is interesting.\n\n3. Positioning the method for bi-level optimization problems is potentially impactful for multi-agent learning scenarios where coalition values evolve with lower-level policies.\n\n4. Claims of dynamic re-assessment over time are compelling for non-stationary or mixed-motive settings.", "weaknesses": "1. The authors have missed the discussion on a key recent baseline (SALDAE). The related-work section omits SALDAE, a 2024 state-of-the-art baseline. Please add a principled comparison clarifying (i) the fundamental differences between your approach and SALDAE, and (ii) why your method should obtain performance gains.\n\n2. Preliminaries require cleanup of notation and definitions. There are inconsistencies in symbols (e.g., the number of agents denoted as n vs. N) and missing definitions (e.g., symbol T in Equation 1). Please unify notation throughout and define all symbols on first use. A small glossary/table of notation would help readability.\n\n3. The scope is limited to disjoint coalitions, with overlapping coalitions unaddressed. The paper defines CFGs as partitioning agents into disjoint groups. Overlapping coalitions are an active subarea. Clarify whether your formulation and algorithm can be extended to overlapping settings (e.g., by modifying the state/action representation or value aggregation), and discuss expected challenges (double-counting of utility, credit assignment, or computational implications). If not applicable, state assumptions explicitly.\n\n4. Bi-level Markov Games: horizon choice and sensitivity. The horizon is set to $N-1$ without justification. Please explain the rationale (theoretical or empirical) and add an ablation showing performance vs. horizon (e.g., shorter, $N-1$, longer), including runtime and stability impacts.\n\n5. There are some issues on the choince of baselines. (i) The current baselines exclude exact methods. Since one aim of the work is to propose an approximation with quality guarantees and the authors claim the ability to derive optimal coalition structures, it is important to include one or two representative exact solvers—even if they scale only to small instances—to compare the effectiveness (e.g., solution quality) and efficiency (e.g., runtime) of the proposed approximation against optimal solutions.; (ii) Apart from the 2024 SALDAE baseline, other baselines appear dated. Please include more recent approximate/planning-based or learning-based competitors.\n\n6. Please demonstrate the value of the bi-level architecture. Add a direct comparison to a single-level decision framework (e.g., your method with the lower level removed or replaced by a fixed surrogate) to show when and why bi-level modeling is beneficial. Include both quality (final utility/return) and cost (runtime, samples) metrics.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KAna8NFV3Z", "reviewer": "Reviewer_QoQT", "summary": "This paper proposes a novel bi-level RL framework called BRIDGE to solve the CSG problem. It models CSG as a two-level hierarchy: an upper-level \"Leader\" agent uses RL to find the optimal partition of agents, while lower-level \"Follower\" agents learn policies within those coalitions to determine their value. This main contribution allows BRIDGE to jointly optimize coalition structures and agent strategies, enabling it to solve dynamic Markov games where coalition values are not fixed. The method is shown to outperform existing approximate algorithms on both classic CSG benchmarks and mixed-motive Markov games.", "questions": "1. The results for the normal-form games at N=100 in Figure 2 are impressive. Were these models trained from scratch? If so, what was the total training overhead (considering the bi-level nested loops, even for value lookups)?\n2. The paper claims the flattened adjacency matrix representation is \"equivariant,\" but also mentions that stability is ensured by \"fixing the agent ordering.\" This seems contradictory, as feeding a flattened vector into a standard MLP is not permutation equivariant. Could you please clarify this claim? Have you considered using a truly permutation-equivariant architecture, such as a Graph Neural Network (GNN), to process the coalition state?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper formulates the CSG problem as a bi-level RL task. This \"Leader-Follower\" paradigm is a significant conceptual contribution that bridges the gap between classic CSG and multi-agent RL.\n2. BRIGE solves CSG in mixed-motive Markov games (e.g., LBF environment). This extends CSG beyond normal-form games, enabling the optimization of coalition structures where the value is dynamic and dependent on learned agent strategies.\n3. The authors cleverly designed the upper-level MDP. Specifically, the action encoding for merging coalitions scales linearly with the number of agents, rather than quadratically which is crucial for tackling larger problem sizes. \n4. The approach is supported by a solid theoretical analysis in the appendix. Lemma C.1 formally proves that the leader's RL objective aligns with the CSG objective under optimal follower policies.", "weaknesses": "1. The entire framework's theoretical justification (Appendix C, Lemma C.1) relies on the lower-level \"followers\" finding the optimal policy $π_{f}^{*}$ within the optimal Nash Equilibrium (NE) set. However, the practical implementation uses a MADDPG-variant, which is well-known to have no guarantees of converging to any NE, let alone the optimal one in a multi-equilibrium setting. \n2. The paper heavily emphasizes the O(N) scalability of the leader's action space, but it largely ignores the scalability of the follower problem, which can be exponentially complex.\n\nIf the authors can address these concerns, I would be very happy to raise my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)