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

arXiv: https://arxiv.org/abs/2604.14386 · HTML: https://mlsanity.com/paper/2604.14386/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Social simulation and multi-agent debate, one of 16 directions in LLM agents and tool use.
- Builds on 23 of its 41 references that are in the map.
- First posted on arXiv 15 Apr 2026.

## Placed in

- LLM agents and tool use / [Social simulation and multi-agent debate](https://mlsanity.com/agents/social-simulation-and-multi-agent-debate/)

## Builds on (most cited first, 23 of 23)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023)
- [CAMEL: Communicative Agents for "Mind" Exploration of Large Language Model Society](https://mlsanity.com/paper/2303.17760/) (2023)
- [ChatDev: Communicative Agents for Software Development](https://mlsanity.com/paper/2307.07924/) (2023)
- [AgentVerse: Facilitating Multi-Agent Collaboration and Exploring Emergent Behaviors](https://mlsanity.com/paper/2308.10848/) (2023)
- [Improving Language Model Negotiation with Self-Play and In-Context Learning from AI Feedback](https://mlsanity.com/paper/2305.10142/) (2023)
- [Cooperation, Competition, and Maliciousness: LLM-Stakeholders Interactive Negotiation](https://mlsanity.com/paper/2309.17234/) (2023)
- [Can Large Language Models Serve as Rational Players in Game Theory? A Systematic Analysis](https://mlsanity.com/paper/2312.05488/) (2023)
- [Strategic Reasoning with Language Models](https://mlsanity.com/paper/2305.19165/) (2023)
- [LLMArena: Assessing Capabilities of Large Language Models in Dynamic Multi-Agent Environments](https://mlsanity.com/paper/2402.16499/) (2024)
- [ECon: On the Detection and Resolution of Evidence Conflicts](https://mlsanity.com/paper/2410.04068/) (2024)
- [FAIRGAME: a Framework for AI Agents Bias Recognition using Game Theory](https://mlsanity.com/paper/2504.14325/) (2025)
- [Shapley-Coop: Credit Assignment for Emergent Cooperation in Self-Interested LLM Agents](https://mlsanity.com/paper/2506.07388/) (2025)
- [Understanding LLM Agent Behaviours via Game Theory: Strategy Recognition, Biases and Multi-Agent Dynamics](https://mlsanity.com/paper/2512.07462/) (2025)
- [Fractional Hedonic Games](https://mlsanity.com/paper/1705.10116/) (2017)
- [Dynamic Coalition Structure Detection in Natural Language-based Interactions](https://mlsanity.com/paper/2502.16339/) (2025)
- [AI-Generated Compromises for Coalition Formation](https://mlsanity.com/paper/2506.06837/) (2025)
- [DAO-Agent: Zero Knowledge-Verified Incentives for Decentralized Multi-Agent Coordination](https://mlsanity.com/paper/2512.20973/) (2025)
- [Stability in Random Hedonic Games](https://mlsanity.com/paper/2406.01373/) (2024)
- [Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games](https://mlsanity.com/paper/2411.05713/) (2024)

## Built on by (most cited first, 2 of 2)

- [Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems](https://mlsanity.com/paper/2608.07532/) (2026)
- [Symbolic Reasoning Frameworks Trigger Memory-Mediated Ecosystem Dynamics in Multi-Agent LLM Systems](https://mlsanity.com/paper/2606.07552/) (2026)

## Abstract (arXiv)

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.