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

• URL: http://arxiv.org/abs/2604.14386v1
• Date: Wed, 15 Apr 2026 19:59:30 GMT
• Title: Coalition Formation in LLM Agent Networks: Stability Analysis and Convergence Guarantees
• Abstract summary: Large Language Model (LLM) agents are increasingly deployed in multi-agent systems requiring strategic coordination.<n>We present the first framework grounding coalition formation in LLM agent networks in hedonic game theory with formal stability guarantees.
• Score: 13.891522069967507
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• SENTINEL-RL: Offloading Topological Reasoning from LLM Agents in the Security Operations Center [0.0]
  Sentinel-RL is an agentic-SOC architecture that decouples topological reasoning from semantic reasoning.<n>We instantiate the system on the LANL Comprehensive, Multi-Source Cyber-Security Events dataset and the Indiana University Quartz HPC cluster.
  arXiv  Detail & Related papers  (2026-09-03T17:49:12Z)
• Does Teaming-Up LLMs Improve Secure Code Generation? A Comprehensive Evaluation with Multi-LLMSecCodeEval [22.812621042022105]
  Multi-LLMSECCODEEVAL is a framework for assessing and enhancing security across the vulnerability management lifecycle.<n>We benchmark ten pipelines spanning single model, ensemble, collaborative, and hybrid designs.
  arXiv  Detail & Related papers  (2026-03-24T02:13:31Z)
• Toward a Sustainable Federated Learning Ecosystem: A Practical Least Core Mechanism for Payoff Allocation [71.86087908416255]
  We introduce a payoff allocation framework based on the least core (LC) concept.<n>Unlike traditional methods, the LC prioritizes the cohesion of the federation by minimizing the maximum dissatisfaction.<n>Case studies in federated intrusion detection demonstrate that our mechanism correctly identifies pivotal contributors and strategic alliances.
  arXiv  Detail & Related papers  (2026-02-03T11:10:50Z)
• Distributional Clarity: The Hidden Driver of RL-Friendliness in Large Language Models [50.99097734404912]
  We show that RL-friendly models exhibit intra-class compactness and inter-class separation in their probability assignments to correct vs. incorrect responses.<n>Experiments across six mathematical benchmarks show consistent improvements across all model families, with gains up to 5.9 points on AIME24.
  arXiv  Detail & Related papers  (2026-01-11T13:34:44Z)
• Recursive Knowledge Synthesis for Multi-LLM Systems: Stability Analysis and Tri-Agent Audit Framework [0.0]
  This paper presents a tri-agent cross-validation framework for analyzing stability and explainability in large language systems.<n>The architecture integrates three heterogeneous LLMs used for semantic generation, analytical consistency checking, and transparency auditing.
  arXiv  Detail & Related papers  (2025-12-17T16:42:45Z)
• CoT-Saliency: Unified Chain-of-Thought Reasoning for Heterogeneous Saliency Tasks [96.64597365827046]
  We present the first unified framework that jointly handles three operationally heterogeneous saliency tasks.<n>We introduce a Chain-of-Thought (CoT) reasoning process in a Vision-Language Model (VLM) to bridge task heterogeneity.<n>We show our model matches or outperforms specialized SOTA methods and strong closed-source VLMs across all tasks.
  arXiv  Detail & Related papers  (2025-11-01T04:37:01Z)
• Corrupted by Reasoning: Reasoning Language Models Become Free-Riders in Public Goods Games [87.5673042805229]
  How large language models balance self-interest and collective well-being is a critical challenge for ensuring alignment, robustness, and safe deployment.<n>We adapt a public goods game with institutional choice from behavioral economics, allowing us to observe how different LLMs navigate social dilemmas.<n>Surprisingly, we find that reasoning LLMs, such as the o1 series, struggle significantly with cooperation.
  arXiv  Detail & Related papers  (2025-06-29T15:02:47Z)
• From Debate to Equilibrium: Belief-Driven Multi-Agent LLM Reasoning via Bayesian Nash Equilibrium [52.28048367430481]
  Multi-agent frameworks can boost the reasoning power of large language models (LLMs), but they typically incur heavy computational costs and lack convergence guarantees.<n>We recast multi-LLM coordination as an incomplete-information game and seek a Bayesian Nash equilibrium (BNE)<n>We introduce Efficient Coordination via Nash Equilibrium (ECON), a hierarchical reinforcement-learning paradigm that marries distributed reasoning with centralized final output.
  arXiv  Detail & Related papers  (2025-06-09T23:49:14Z)
• LLM2: Let Large Language Models Harness System 2 Reasoning [65.89293674479907]
  Large language models (LLMs) have exhibited impressive capabilities across a myriad of tasks, yet they occasionally yield undesirable outputs.<n>We introduce LLM2, a novel framework that combines an LLM with a process-based verifier.<n>LLMs2 is responsible for generating plausible candidates, while the verifier provides timely process-based feedback to distinguish desirable and undesirable outputs.
  arXiv  Detail & Related papers  (2024-12-29T06:32:36Z)
• LLM-Coordination: Evaluating and Analyzing Multi-agent Coordination Abilities in Large Language Models [23.092480882456048]
  Large Language Models (LLMs) have demonstrated emergent common-sense reasoning and Theory of Mind (ToM) capabilities.<n>This study introduces the LLM-Coordination Benchmark, a novel benchmark for analyzing LLMs in the context of Pure Coordination Settings.
  arXiv  Detail & Related papers  (2023-10-05T21:18:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.