Coalition Formation in LLM Agent Networks: Stability Analysis and Convergence Guarantees

Dongxin Guo; Jikun Wu; Siu-Ming Yiu

cs.GTApr 15, 2026

Coalition Formation in LLM Agent Networks: Stability Analysis and Convergence Guarantees

Authors: Dongxin Guo, Jikun Wu, Siu-Ming Yiu

Organizations: Department of Compute Science, The University of Hong Kong, Hong Kong, China · Brain Investing Limited, Hong Kong, China · Stellaris AI Limited, Hong Kong, China

Abstract

Large Language Model (LLM) agents are increasingly deployed in multi-agent systems requiring strategic coordination. While recent work has analyzed LLM behavior in two-player games, coalition formation, where $n$ agents dynamically form cooperative groups, remains theoretically uncharacterized. We present the first framework grounding coalition formation in LLM agent networks in hedonic game theory with formal stability guarantees. We introduce the LLM Coalition Formation Game (LCFG), establish sufficient conditions for Nash-stable partitions, and prove complexity results. Our analysis reveals that LLM agents exhibit bounded rationality characterized by $ε$ -rational preferences; we provide both deterministic existence guarantees and consistency-driven stability bounds whose predictions are consistent with empirical outcomes. Experiments with GPT-4, Claude-3, and Llama-3 across 2,400 episodes validate our framework: LLM coalitions achieve Nash stability in 73.2% of cases under our Coalition-of-Thought (CoalT) protocol, compared to 58.4% under chain-of-thought and 41.8% under standard prompting ( $p < 0.001$ ). Our framework provides theoretical foundations for designing stable multi-agent LLM systems.

Figures & tables

Panel of Figure 1 — Figure 1: LCFG Framework Overview. Left : Input context with heterogeneous LLM agents showing capability profiles across Math, Facts, and Logic dimensions. Center : Coalition-of-Thought (CoalT) reasoning module, a 5-step pipeline that guides agents through structured coalition evaluation. The latent space visualization shows agents transitioning from scattered initial positions to clustered Nash-stable coalitions through iterative refinement ( $h\leftarrow h+\alpha\cdot\Delta h$ ). The dashed border indicates the trainable/promptable module. Right : Output Nash-stable partition $\pi^{*}$ achieving 73.2% stability rate (+14.8pp over vanilla CoT). Key insight : Theorem 2 shows stability scales with preference consistency ( $p^{K_{\text{eff}}}$ ), not perfect rationality.

Work	$n$ -player	Coalitions	Stability	Protocol
GTBench	×	×	×	×
FAIRGAME	×	×	×	×
Shapley-Coop	✓	×	×	×
Briman et al.	✓	✓	×	×
Kulkarni et al.	✓	✓ ∗	×	×
AutoGen	✓	×	×	×

Table 1: Comparison with related approaches. Coalitions : models coalition partition structures. Stability : formal game-theoretic stability analysis. Protocol : dedicated reasoning protocol for coalition decisions.

Agent	Math	Facts	Logic
$a_{1}$ (GPT-4)	0.68	0.73	0.76
$a_{2}$ (GPT-4)	0.65	0.76	0.73
$a_{3}$ (Claude-3)	0.62	0.78	0.74
$a_{4}$ (Claude-3)	0.59	0.81	0.71
$a_{5}$ (Llama-3)	0.58	0.65	0.79
$a_{6}$ (Llama-3)	0.55	0.68	0.76

Table 2: Agent capability profiles (Math, Facts, Logic). Values are relative estimates from our custom evaluation on benchmark subsets, calibrated to reflect task-specific performance in our coalition formation domain. These are not official benchmark scores.

Condition	Nash%	Conv.	Welfare	Consist.
Random	28.3	–	$0.58_{\pm.14}$	–
Greedy	52.1	$6.8_{\pm 3.2}$	$0.69_{\pm.10}$	$0.71_{\pm.08}$
Standard	41.8	$18.3_{\pm 7.2}$	$0.72_{\pm.11}$	$0.64_{\pm.09}$
Vanilla CoT	58.4 ∗∗	$14.2_{\pm 5.8}$ ∗	$0.75_{\pm.09}$ ∗	$0.74_{\pm.07}$ ∗∗
Self-Consist.	62.7 ∗∗	$13.1_{\pm 5.2}$ ∗∗	$0.77_{\pm.08}$ ∗∗	$0.79_{\pm.06}$ ∗∗
CoalT	73.2 ∗∗	$\mathbf{11.4}_{\pm 4.1}$ ∗∗	$\mathbf{0.81}_{\pm.08}$ ∗∗	$\mathbf{0.86}_{\pm.05}$ ∗∗

Table 3: Coalition formation results (400 episodes per condition). Statistical significance vs. Standard:

{}^{*}p<0.01

{}^{**}p<0.001

(Wilcoxon, Bonferroni-corrected).

Panel of Figure 2 — Figure 2: Nash stability rate vs. preference consistency across experimental conditions. Shaded region: range consistent with Theorem 2 ’s lower bound across plausible parameter settings. CoalT achieves highest consistency ( $p=0.86$ ) and stability (73.2%), confirming that stability scales with $p^{K_{\text{eff}}}$ rather than perfect rationality.

Configuration	Nash Stable	$\Delta$ vs. Full
Full CoalT	73.2%	–
$-$ Capability Analysis	68.9%	$-4.3$ pp
$-$ Complementarity	65.4%	$-7.8$ pp
$-$ Value Estimation	67.1%	$-6.1$ pp
$-$ Coordination Cost	70.8%	$-2.4$ pp
$-$ All (= Vanilla CoT)	58.4%	$-14.8$ pp

Table 4: CoalT ablation study: contribution of each component.

Temperature Sensitivity ( $\tau$ )
Model	$\hat{\epsilon}$	95% CI	CoalT $\Delta$
GPT-4	0.15	[0.12, 0.18]	+15.2pp
Claude-3	0.14	[0.11, 0.17]	+14.1pp
Llama-3-70B	0.22	[0.18, 0.26]	+11.8pp
$\tau=0.0$	0.15 $\pm$ 0.02	–	+14.8 $\pm$ 1.2pp
$\tau=0.5$	0.18 $\pm$ 0.03	–	+12.3 $\pm$ 1.8pp

Table 5: Estimated

\epsilon

-rationality bounds and temperature sensitivity.

Explore similar work

Competition and Cooperation of LLM Agents in Games
Apr 1, 2026Jiayi Yao, Cong Chen, Baosen ZhangLLM Agents Multi-Agent LLM Systems
Department of Electrical and Computer Engineering, University of Washington, Seattle. · Thayer School of Engineering at Dartmouth College.
Graph-theoretic Agreement Framework for Multi-agent LLM Systems
Feb 23, 2026Muhammad Umar JavedMulti-Agent LLM Systems Multi-Agent Consensus
Drivers of LLM Consensus Formation Under Competing Incentives: A Simulation Study
Oct 14, 2026Isabel Jones, Matthew Edwards, Janina A. HoffmannMulti-Agent Consensus Multi-Agent LLM Systems
University of Bristol Bristol, United Kingdom · University of Bath Bath, United Kingdom

Apr 1, 2026J/K move · Enter open · S save

Competition and Cooperation of LLM Agents in Games

Jiayi Yao, Cong Chen, Baosen Zhang

Department of Electrical and Computer Engineering, University of Washington, Seattle. · Thayer School of Engineering at Dartmouth College.

LLM Agents Multi-Agent LLM Systems Game-Playing Agents Multi-Agent Coordination Cooperative Game Theory

Open paper AskPDF arXiv

Large language model (LLM) agents are increasingly deployed in competitive multi-agent settings, raising fundamental questions about whether they converge to equilibria and how their strategic behavior can be characterized. In this paper, we study LLM agent interactions in two standard games: a network resource allocation game and a Cournot competition game. Rather than converging to Nash equilibria, we find that LLM agents tend to cooperate when given multi-round prompts and non-zero-sum context. Chain-of-thought analysis reveals that fairness reasoning is central to this behavior. We propose an analytical framework that captures the dynamics of LLM agent reasoning across rounds and explains these experimental findings.

Abstract

Explore similar work

Competition and Cooperation of LLM Agents in Games

Graph-theoretic Agreement Framework for Multi-agent LLM Systems

Drivers of LLM Consensus Formation Under Competing Incentives: A Simulation Study