Paper deep dive
Coalition Formation in LLM Agent Networks: Stability Analysis and Convergence Guarantees
Dongxin Guo, Jikun Wu, Siu-Ming Yiu
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 4/18/2026, 1:34:06 AM
Summary
The paper introduces the LLM Coalition Formation Game (LCFG), a framework grounding multi-agent LLM coordination in hedonic game theory. It addresses the lack of theoretical characterization for coalition formation among LLM agents by defining stability concepts, proving complexity results, and introducing the 'Coalition-of-Thought' (CoalT) prompting protocol. The framework demonstrates that LLM agents exhibit bounded rationality (ε-rationality) and provides consistency-driven stability bounds, validated by experiments showing a 73.2% Nash stability rate.
Entities (4)
Relation Signals (2)
CoalT → improves → Nash Stability
confidence 98% · LLM coalitions achieve Nash stability in 73.2% of cases under our Coalition-of-Thought (CoalT) protocol
LCFG → utilizes → Hedonic Game Theory
confidence 95% · We present the first framework grounding coalition formation in LLM agent networks in hedonic game theory
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 $\epsilon$-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.
Tags
Links
- Source: https://arxiv.org/abs/2604.14386v1
- Canonical: https://arxiv.org/abs/2604.14386v1
Trouble viewing inline? Open PDF directly →
Full Text
67,317 characters extracted from source content.
Expand or collapse full text
Coalition Formation in LLM Agent Networks: Stability Analysis and Convergence Guarantees Dongxin Guo 1 , Jikun Wu 2, 3 and Siu-Ming Yiu 1 1 Department of Compute Science, The University of Hong Kong, Hong Kong, China 2 Brain Investing Limited, Hong Kong, China 3 Stellaris AI Limited, Hong Kong, China bettyguo@connect.hku.hk, hk950014@connect.hku.hk, smyiu@cs.hku.hk Abstract Large Language Model (LLM) agents are increas- ingly deployed in multi-agent systems requiring strategic coordination. While recent work has ana- lyzed LLM behavior in two-player games, coalition formation, where n agents dynamically form co- operative groups, remains theoretically uncharac- terized. We present the first framework grounding coalition formation in LLM agent networks in he- donic 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 pre- dictions 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) pro- tocol, 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. 1 Introduction The deployment of Large Language Model (LLM) agents in multi-stakeholder environments, from collaborative research systems [ Wu et al., 2024 ] to automated negotiations [ Fu et al., 2023; Abdelnabi et al., 2024 ] , raises fundamental questions about their strategic behavior in cooperative settings. While extensive work has characterized LLM performance in two- player strategic games [ Fan et al., 2024; Duan et al., 2024; Buscemi et al., 2025 ] , the analysis of coalition formation, where n agents must dynamically organize into cooperative groups, remains conspicuously absent from the literature. This gap is significant for three reasons. First, real-world multi-agent deployments inherently involve coalition dynam- ics: research teams must form around problems, negotiat- ing agents must identify partners, and distributed systems must allocate agents to tasks. Second, coalition formation exhibits qualitatively different strategic considerations than two-player games; agents must reason about group member- ship, coalition stability, and collective payoffs rather than bi- lateral outcomes. Third, recent work explicitly identifies this gap: studies on multi-player LLM games note that “group size fixed at 2-3 agents precludes examination of larger-group phenomena such as coalition formation” [ Huynh et al., 2025 ] , while recent surveys on game theory and LLMs identify co- operative game theory as “underexplored” [ Sun et al., 2025 ] . Why Game Theory? One might ask whether a formal game-theoretic framework is necessary, or if simpler heuris- tics suffice. Our experiments demonstrate clear value: (1) Greedy matching achieves only 52.1% stability with lower welfare than structured approaches, showing myopic opti- mization fails; (2) vanilla chain-of-thought [ Wei et al., 2022 ] achieves 58.4%, indicating that generic structured reason- ing is insufficient; the game-theoretic framing in CoalT pro- vides an additional 14.8 percentage points improvement (p < 0.001); (3) our theoretical bounds are consistent with ob- served empirical stability rates, enabling principled protocol design. Why Exclusive Partitions? We model coalitions as a par- tition (each agent belongs to exactly one coalition) because in practical multi-agent LLM deployments, resource constraints (including API rate limits, compute budgets, and context win- dow sizes) prevent an agent from simultaneously contributing to multiple coalitions within the same task episode. This mir- rors team formation settings where each worker is assigned to one project at a time [ Wooldridge, 2011 ] . In our framework, agents are the strategic decision-makers: each agent evalu- ates whether it would benefit from joining a different coali- tion and declares its preferences accordingly (Section 6). A “deviation” means an agent’s preference declaration indicates it would prefer a different group assignment. Contributions. We address this gap through four contri- butions: 1. Formal Framework: We introduce the LLM Coali- tion Formation Game (LCFG), extending hedonic game theory [ Bogomolnaia and Jackson, 2002 ] to character- ize LLM agents with capability profiles and bounded- rational preferences (Section 3). 2. Stability Theorems: We establish two complementary guarantees: (i) deterministic existence under ideal con- arXiv:2604.14386v1 [cs.GT] 15 Apr 2026 Input Context GPT-4 Agents (a 1 ,a 2 ) Math 0.68 Facts 0.73 Claude-3 Agents (a 3 ,a 4 ) Facts 0.78 Logic 0.74 Llama-3 Agents (a 5 ,a 6 ) Logic 0.79 Math 0.58 Coalition Formation Task Agents must partition into stable, comple- mentary coalitions Coalition-of-Thought (CoalT) Step 1 Capability Analysis Step 2 Complem. Assess. Step 3 Value Estimation Step 4 Coord. Cost Step 5 Preference Declare Coalition Formation in Latent Space Before a 1 a 2 a 3 a 4 a 5 a 6 h← h + α· ∆h Iterative (T = k) After C 1 C 2 C 3 Output Nash-Stable Partition π ∗ C 1 : a 1 a 3 ✓Stable C 2 : a 2 a 5 a 6 ✓Stable C 3 : a 4 ✓Stable 73.2% Nash Stability Rate Standard: 41.8% CoT: 58.4% CoalT: 73.2% Theorem 2: Pr[Nash-stable]∝ p K eff Consistency ⇒ Stability GPT-4Claude-3 Llama-3 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 coali- tion evaluation. The latent space visualization shows agents transitioning from scattered initial positions to clustered Nash-stable coalitions through iterative refinement (h ← h + α· ∆h). The dashed border indicates the trainable/promptable module. Right: Output Nash-stable partition π ∗ achieving 73.2% stability rate (+14.8p over vanilla CoT). Key insight: Theorem 2 shows stability scales with preference con- sistency (p K eff ), not perfect rationality. ditions (ε < δ/2), and (i) consistency-driven stability bounds using logit dynamics analysis that decompose stability into preference consistency and game structure factors, providing a conservative lower bound consistent with observed outcomes (Section 4). 3. Complexity Analysis:We show that computing a Nash-stable partition is NP-hard in general hedo- nic games, motivating structural assumptions under which LCFGs become polynomial-time solvable via capability-monotonicity constraints that hold in practice (Section 5). 4. Experimental Validation: Through 2,400 coalition for- mation episodes across three LLM architectures with five baselines including vanilla CoT, we validate our the- oretical framework with formal statistical testing and in- troduce Coalition-of-Thought (CoalT), a prompting pro- tocol achieving significant stability improvements (Sec- tion 7). 2 Related Work Coalition Game Theory. Coalition formation in multi-agent systems has been extensively studied in classical settings [ Wooldridge, 2011; Rahwan et al., 2015 ] . Hedonic games [ Dreze and Greenberg, 1980; Bogomolnaia and Jackson, 2002 ] model agents with preferences over coalition member- ship, with well-characterized stability concepts: core stabil- ity, Nash stability, and individual stability form a hierarchy of solution concepts [ Aziz et al., 2019 ] . Recent work establishes complexity bounds for random hedonic games [ Bullinger and Kraiczy, 2024 ] and addresses popularity in fractional hedo- nic games [ Bullinger and Gilboa, 2025 ] , but none considers LLM agents. Our work bridges this gap by extending hedo- nic game theory to account for the bounded rationality and stochastic preferences inherent in LLM decision-making. LLMs in Strategic Settings.GTBench [ Duan et al., 2024 ] and FAIRGAME [ Buscemi et al., 2025 ] provide frame- works for analyzing LLM strategic behavior in competitive games, revealing that LLM performance varies significantly across game types and reasoning complexity. LLMArena [ Chen et al., 2024a ] and Alympics [ Mao et al., 2025 ] fur- ther demonstrate LLM capabilities in dynamic multi-agent environments. LLM-Deliberation [ Abdelnabi et al., 2024 ] extends this to multi-party negotiation scenarios but with- out formal coalition-theoretic analysis.Recent work on non-cooperative equilibria includes ECON [ Jiayang et al., 2024 ] , which proves existence of Bayesian Nash Equilibrium in multi-LLM coordination, and studies showing that LLM performance degrades with strategic complexity [ Gandhi et al., 2023 ] . Critically, these works focus on two-player or fixed-group competitive/mixed-motive games; extension to n-player coalitional settings with dynamic group formation requires fundamentally new theoretical machinery, which we provide. Cooperative Game Theory for LLMs. A growing body of work applies cooperative game theory to LLM agents, primarily through Shapley value-based credit assignment. Shapley-Coop [ Hua et al., 2025 ] introduces “Shapley Chain- of-Thought” for LLM agents to estimate marginal contri- butions within multi-agent teams, and DAO-Agent [ Xia et al., 2025 ] defines explicit characteristic functions over LLM agent coalitions for blockchain-verified reward allocation. However, these approaches assume a fixed grand coalition and compute contribution scores within it; they do not ad- dress the partition optimization problem of which coalitions should form, nor do they analyze stability of the resulting structures. Separately, Briman et al. [ Briman et al., 2025 ] model LLM-mediated coalition formation where agents have Euclidean preferences and an LLM generates textual com- promise proposals. While this work features formal coalition structures and iterative partition evolution, LLMs serve as mediator tools rather than autonomous strategic players, and stability analysis is limited to convergence properties with- out formal guarantees (Nash, core, or individual stability). Kulkarni et al. [ Kulkarni et al., 2025 ] use LLMs with hyper- game theory to detect existing coalitions in Diplomacy from natural language, rather than forming them. Our framework differs from all of these in three respects: LLM agents are the strategic players (not tools), the objective is partition op- timization with stability guarantees, and we provide a dedi- cated prompting protocol (CoalT) for coalition reasoning. Multi-Agent LLM Systems. AutoGen [ Wu et al., 2024 ] , CAMEL [ Li et al., 2023 ] , and MetaGPT [ Hong et al., 2024 ] enable multi-LLM coordination for complex tasks. Agent- Verse [ Chen et al., 2024b ] observes emergent behaviors including spontaneous cooperation and role specialization, while ChatDev [ Qian et al., 2024 ] demonstrates effective software development through LLM collaboration. How- ever, these systems lack game-theoretic foundations for un- derstanding when and why stable coordination emerges. Our framework fills this gap by providing formal conditions un- der which LLM agents converge to stable coalitions, enabling principled system design rather than trial-and-error tuning. Bounded Rationality and QRE. Our ε-rationality model connects to classical behavioral game theory [ Simon, 1955; Camerer, 2003 ] . Quantal response equilibria (QRE) [ McK- elvey and Palfrey, 1995 ] model agents who make errors pro- portional to payoff differences: higher-value options are more likely chosen but not deterministically. We formally estab- lish the connection: under logit dynamics with parameter λ = 1/ε, our model yields QRE-equivalent choice proba- bilities (Appendix E). This connection enables us to leverage decades of QRE analysis while adapting the framework to LLM-specific characteristics such as prompt-dependent con- sistency. Positioning. Table 1 summarizes how our work relates to prior approaches. While recent work applies Shapley val- ues to LLM agent credit assignment [ Hua et al., 2025 ] and uses LLMs as mediators for coalition negotiation [ Briman et al., 2025 ] , we are, to the best of our knowledge, the first to combine: (i) a formal coalitional game model where LLM agents are strategic players, (i) partition-based stability anal- ysis (Nash stability, core stability) with provable guarantees, and (i) a prompting protocol specifically designed for coali- tion reasoning. 3 Problem Formulation We formalize coalition formation among LLM agents as a hedonic game [ Dreze and Greenberg, 1980; Bogomolnaia and Jackson, 2002 ] , a class of cooperative games where each agent’s preferences depend solely on the members of its own coalition. This is natural for LLM multi-agent systems: an agent’s performance in a coalition depends on who it collab- orates with, not on how other coalitions are organized. 3.1 LLM Coalition Formation Games Definition 1 (LLM Agent). An LLM agent is a tuple a i = (m i ,θ i ,c i ) where m i ∈ M is the model architecture (e.g., Table 1: Comparison with related approaches. Coalitions: models coalition partition structures. Stability: formal game-theoretic sta- bility analysis. Protocol: dedicated reasoning protocol for coalition decisions. Workn-playerCoalitionsStabilityProtocol GTBench× FAIRGAME× Shapley-Coop ✓× Briman et al.✓× Kulkarni et al. ✓ ∗ × AutoGen✓× Ours✓ ∗ Detection only, not formation. GPT-4, Claude-3), θ i ∈ Θ = [0, 2]× Σ ∗ specifies configu- ration (temperature τ ∈ [0, 2] and system prompt s ∈ Σ ∗ ), andc i ∈ [0, 1] d is a capability profile over d skill dimen- sions (e.g., mathematical reasoning, factual knowledge, logi- cal analysis). Capability profiles are estimated empirically by evaluating each LLM on domain-specific benchmarks (Section 7). They serve as the bridge between the abstract hedonic game model and concrete LLM agents: the coalition value function is de- fined in terms of the capability profiles of its members. Definition 2 (LLM Coalition Formation Game). An LLM Coalition Formation Game (LCFG) is a hedonic game G = (N,v,≿ i i∈N ) where: • N =a 1 ,...,a n is a set of LLM agents (Definition 1) • v : 2 N →R is a coalition value function parameterized by member capability profiles • ≿ i is agent a i ’s preference relation over coalitions containing a i , informed by per-capita value v i (S) = v(S)/|S| (see Definition 3) The coalition value function captures joint task perfor- mance: v(S) = φ M a i ∈S c i ! − ψ(|S|)(1) where φ : [0, 1] d →R aggregates capabilities (we use φ(c) =∥c∥ 1 /d),⊕ denotes componentwise maximum (mod- eling coverage-based tasks where having any expert suffices), and ψ :N →R captures coordination costs. We model ψ(k) = α · k β with α = 0.15 and β = 1.3, empirically calibrated to minimize prediction error (see Appendix F for sensitivity analysis). The superlinear scaling (β > 1) is con- sistent with coordination cost findings [ Wooldridge, 2011; nis, 2007 ] . Example 1 (Worked Example). Consider three agents with capabilitiesc 1 = (0.68, 0.30, 0.40),c 2 = (0.40, 0.65, 0.30), c 3 = (0.30, 0.40, 0.76). Using φ(c) = ∥c∥ 1 /d and ψ(k) = 0.15k 1.3 : coalitiona 1 ,a 2 has v = 0.21 (per-capita 0.10), while the grand coalition a 1 ,a 2 ,a 3 has v = 0.07 (per- capita 0.02). Despite higher capability coverage, the grand coalition yields lower per-capita value due to coordination costs, a core tradeoff our framework captures. 3.2 Bounded-Rational Preferences Classical hedonic games assume complete, transitive prefer- ences. LLM agents exhibit bounded rationality, i.e., system- atic deviations from optimal decision-making: Definition 3 (ε-Rational Preferences). Agent a i ’s preferences are ε-rational with respect to value function v if for all coali- tions S,T ∋ a i : v i (S) > v i (T ) + ε =⇒ S ≻ i T(2) where v i (S) = v(S)/|S| is a i ’s per-capita value in coalition S. Intuitively, ε-rationality captures that LLM agents reliably identify the better option when value differences exceed ε, but may make inconsistent choices for closer comparisons. Our experiments (Section 7) estimate ε ≈ 0.15 for GPT- 4 and ε ≈ 0.22 for Llama-3. These values are estimated by measuring the value gap threshold below which agent choices become near-random (see Appendix E for method- ology). Under logit choice models from Quantal Response Equilibrium (QRE) theory [ McKelvey and Palfrey, 1995 ] , this corresponds to precision parameters λ = 1/ε ≈ 6.7 (GPT-4) and λ ≈ 4.5 (Llama-3), indicating substantial but bounded deviations from perfect rationality. 3.3 Coalition Structures and Stability A coalition structure π = C 1 ,...,C k is a partition ofN . We adopt standard stability concepts: Definition 4 (Stability Concepts). Given LCFG G and coali- tion structure π: • π is Nash-stable if no agent unilaterally prefers joining another coalition: ∀a i ∈ C ∈ π,∀C ′ ∈ π∪∅: C ≿ i C ′ ∪a i • π is individually stable (IS) if no agent can profitably de- viate without making any member of the receiving coali- tion worse off • π is core-stable if no group of agents can jointly devi- ate such that all members of the deviating group strictly benefit Nash stability is the strongest individual-deviation con- cept: it requires that no agent wants to switch, regardless of whether the receiving coalition consents. Individual stabil- ity weakens this by requiring that the receiving coalition does not object. Core stability addresses group deviations: Nash stability ⇒ Individual stability, but Nash stability and core stability are generally incomparable in hedonic games [ Bogo- molnaia and Jackson, 2002; Aziz et al., 2019 ] . We focus on Nash stability as our primary notion because it is verifiable in polynomial time under our capability-monotonicity assump- tion (Theorem 5) and provides strong guarantees against uni- lateral deviations. Existence of Nash-Stable Partitions. Nash-stable par- titions are not guaranteed to exist in all hedonic games. Under per-capita value splitting v i (S) = v(S)/|S| with componentwise-max aggregation, cycles can arise when a low-capability agent benefits from joining a high-capability agent’s coalition while the latter prefers to be alone (see Ap- pendix A for a formal example). Our Theorem 1 identifies sufficient conditions for existence, while Theorem 2 provides probabilistic guarantees when these conditions are relaxed. 4 Theoretical Analysis We establish when LLM agents converge to stable coali- tion structures, providing both deterministic guarantees un- der ideal conditions and consistency-driven bounds for real- istic settings. 4.1 Deterministic Existence (Ideal Conditions) Assumption 1 (Value Gap Condition). An LCFG G satisfies the δ-value gap condition if there exists δ > 0 such that for all agents a i and distinct coalitions S,T ∋ a i : either v i (S) = v i (T ) or|v i (S)− v i (T )|≥ δ. This assumption is naturally satisfied with benchmark- derived capability profiles. We empirically verify δ ≈ 0.08 through exhaustive enumeration of all coalition pairs in our 6- agent setting (Appendix F.2). Note that δ is a property of the specific game instance derived from our capability profiles and value function parameterization, not a universal constant from the hedonic games literature. Assumption 2 (Potential Alignment). An LCFG G satis- fies potential alignment if for the potential function Φ(π) = P C∈π v(C), every improving deviation (where v i (C ′ ∪ a i ) > v i (C)) also increases Φ: Φ(π ′ ) > Φ(π). Potential alignment holds when agents bring sufficient unique value to receiving coalitions; specifically, when the marginal value v(C ′ ∪a i )−v(C ′ ) exceeds the loss v(C)− v(C \ a i ). Under componentwise-max aggregation with diverse multi-dimensional capability profiles (d ≥ 2), this is naturally satisfied when each agent contributes distinct cov- erage. It may fail in degenerate cases (e.g., one-dimensional capabilities where high-capability agents gain nothing from low-capability partners; see Appendix A). Theorem 1 (Deterministic Existence). Let G be an LCFG satisfying the δ-value gap condition (Assumption 1), potential alignment (Assumption 2), and capability monotonicity: for all S ⊆N and agents a i ,a j , ifc i ≤c j componentwise, then v(S ∪ a i ) ≤ v(S ∪ a j ). If all agents have ε-rational preferences with ε < δ/2, then a Nash-stable partition exists and can be found in polynomial time. Proof Sketch. Under ε-rationality and the δ-value gap condi- tion, an improving deviation requires a per-capita value in- crease of at least δ− ε > δ/2 > 0. By potential alignment, each such deviation strictly increases Φ(π) = P C∈π v(C). Since Φ is bounded above and takes values from a discrete set (by the value gap condition), the improvement path termi- nates at a Nash-stable partition in at most O(n· ∆ v /δ) steps, where ∆ v is the value range. Full proof in Appendix B. Remark 1 (Scope and Limitations of Theorem 1). The con- dition ε < δ/2 ensures that ε-rational agents can distinguish coalitions with different values: when ε≥ δ/2, the agent’s er- ror margin exceeds the value gap, and rational discrimination breaks down. In practice, LLM agents exhibit ε≈ 0.15–0.22, exceeding δ/2 ≈ 0.04. This motivates our main theoretical result (Theorem 2), which provides probabilistic guarantees without requiring ε < δ/2. 4.2 Consistency-Driven Stability (Realistic Conditions) When ε > δ/2, deterministic guarantees no longer hold. We characterize stability using logit dynamics from behavioral game theory [ McKelvey and Palfrey, 1995 ] . Key Insight. Stability depends primarily on preference consistency, i.e., whether agents make the same choice when queried repeatedly, rather than perfect rationality. An agent who consistently prefers suboptimal coalitions still con- tributes to stable outcomes, while an agent with perfect utility but inconsistent choices creates instability. Definition 5 (Preference Consistency). Agent a i has prefer- ence consistency p i ∈ [0, 1] if, across independent queries for the same coalition comparison, the agent returns the same preference with probability p i . Definition 6 (Effective Critical Decisions). Let K eff denote the number of effectively critical decisions, those where the value gap |∆v| < 2ε, making consistency meaningfully less than 1. Let K n − K eff denote “easy” decisions with large value gaps where consistency approaches p easy ≈ 1. Theorem 2 (Consistency-Driven Stability Bound). Let G be an LCFG with n agents satisfying capability monotonicity. Let p ∈ (0, 1] be the preference consistency on critical deci- sions, p easy ≈ 1 on easy decisions, K eff the number of critical decisions, and K n total decisions. Assuming decision inde- pendence across agents and coalition comparisons: Pr[Nash-stable]≥ p K eff · p K n −K eff easy · γ(G)(3) where γ(G) is the probability that consistent dynamics reach a Nash-stable partition. Under logit dynamics with precision λ = 1/ ̄ε, γ(G) is bounded below by 1− exp(−δ/ ̄ε), with ̄ε the mean rationality bound and δ the value gap. Proof Sketch. By conditional probability, Pr[Nash-stable] = Pr[consistent]· Pr[Nash | consistent]. The first factor, under decision independence, is at least p K eff ·p K n −K eff easy . The second factor is γ(G): given consistent preferences, the system fol- lows deterministic improving dynamics on a potential game, and the stationary distribution of logit dynamics concentrates on potential maxima [ Blume, 1993 ] . Full derivation in Ap- pendix C. Empirical Validation. For our setting (n = 6, K eff ≈ 5 critical decisions out of K n ≈ 15 total, p = 0.86, p easy = 0.98), we estimate γ(G) ≈ 0.90 empirically as the fraction of episodes with consistent decisions that reach Nash stability. This exceeds the formula lower bound 1 − exp(−0.08/0.17) ≈ 0.38, indicating favorable game struc- ture. Our theoretical lower bound is: Pr[Nash-stable]≥ 0.86 5 · 0.98 10 · 0.90≈ 0.35(4) The observed rate of 73.2% substantially exceeds this lower bound, confirming that the consistency-driven framework captures the dominant factor in stability. The monotonic re- lationship between p and Nash stability rate holds across all experimental conditions (Figure 2). Corollary 3 (Scaling Law). If K eff = O( √ n) (as observed empirically in our setting; see Appendix H), then the Nash stability lower bound scales as p O( √ n) for large n. 4.3 Convergence Guarantees Theorem 4 (Convergence). Let G be an LCFG satisfying the δ-value gap condition (Assumption 1) and potential align- ment (Assumption 2), where all agents have ε-rational pref- erences with ε < δ/2 that are temporally consistent (same query yields same preference). Under improving dynam- ics where at most one agent deviates per round, the coali- tion structure converges to a Nash-stable partition in at most O(n 2 · ∆ v /δ) rounds, where ∆ v = max S v(S)− min S v(S). Proof Sketch. By Theorem 1, the potential function Φ strictly increases with each improving deviation, and there are at most O(n· ∆ v /δ) such deviations before termination. Each round checks all n agents for a potential deviation, so at most O(n) rounds elapse between consecutive deviations. Multi- plying gives O(n 2 · ∆ v /δ) total rounds. 5 Complexity Analysis We analyze the computational complexity of stability verifi- cation and computation in LCFGs. Theorem 5 (Complexity of Nash Stability). Given LCFG G with ε-rational agents and coalition structure π: 1. Verifying Nash stability of a given partition π is in P (O(n 2 ) preference queries) under explicit value compu- tation. 2. Computing a Nash-stable partition is NP-hard in gen- eral hedonic games [ Ballester, 2004 ] , and LCFGs in- herit this worst-case hardness when the capability di- mension d is unbounded. 3. Under capability monotonicity and potential alignment, both verification and computation are polynomial. Proof Sketch. (1) For verification, check each agent’s devia- tion to each coalition in O(n 2 ) time; if no improving devia- tion exists, π is Nash-stable. (2) Since LCFGs are a subclass of hedonic games, we note that the NP-hardness of computing Nash-stable partitions in the general case [ Ballester, 2004 ] motivates identifying tractable subclasses. When d is part of the input, LCFGs can encode sufficiently rich preference structures to preserve hardness; for fixed d (as in our experi- ments), structural restrictions enable tractability via Part (3). (3) Under our assumptions, the potential function argument (Theorem 1) yields polynomial computation via iterative im- proving dynamics. Full proofs in Appendix D. Practical Implications. The tractability under capability monotonicity is significant: it means that for practical sys- tems where better agents improve coalition value, stability verification is efficient. Specifically, given n agents and a proposed partition π, we can verify Nash stability in O(n 2 ) preference queries by checking whether each agent a i ∈ C prefers C over C ′ ∪a i for all other coalitions C ′ ∈ π. This enables real-time stability monitoring in deployed systems. Query Complexity. Each stability check requires one LLM inference per agent-coalition pair. For our 6-agent setup, this amounts to approximately 30 queries per verifi- cation (6 agents× 5 alternative coalitions). With CoalT’s im- proved consistency, single-round verification suffices in 86% of cases; otherwise, we use majority voting over 3 queries. Algorithm 1 Coalition-of-Thought (CoalT) Protocol Input: Agent a i , current coalition C, candidate C ′ Output:Preference C ≻ C ′ ,C ′ ≻ C,C ∼ C ′ 1: Step 1: Capability Analysis 2: “List capabilities of members in C and C ′ ” 3: Step 2: Complementarity Assessment 4: “Identify capability gaps and overlaps” 5: Step 3: Value Estimation 6: “Estimate task performance for each coalition” 7: Step 4: Coordination Cost Analysis 8: “Assess communication/coordination overhead” 9: Step 5: Preference Declaration 10: “Based on analysis, declare preference” 11: return Parse final preference from Step 5 output 6 Coalition-of-Thought Prompting Standard prompting and even vanilla chain-of-thought [ Wei et al., 2022 ] fail to elicit consistent coalition reasoning. We introduce Coalition-of-Thought (CoalT), a structured proto- col grounded in our game-theoretic framework. CoalT differs from vanilla CoT by incorporating game- theoretic concepts (capability complementarity, coordination costs, per-capita value) rather than generic step-by-step rea- soning. The key insight is that explicitly prompting agents to reason about what they contribute and what they gain from coalition membership substantially improves preference con- sistency. Prompt Template. The CoalT prompt follows this struc- ture: “You are evaluating whether to join coalition C ′ instead of staying in C. Analyze systematically: (1) What capa- bilities do members of each coalition have? (2) Are there complementary strengths or redundant capabilities? (3) What is the expected task performance of each group? (4) What coordination overhead does each coalition size incur? (5) Based on your per-capita expected value, state your preference.” This template instantiates each step of Algorithm 1 with ex- plicit reasoning targets. Example CoalT Reasoning. For agent a 1 comparing C = a 1 ,a 2 vs. C ′ =a 3 ,a 5 ,a 6 : “Step 1: C has math but limited logic. C ′ has facts/logic. Step 2: C has overlap; C ′ adds complementarity. Step 3: v(C) ≈ 0.42; v(C ′ ) ≈ 0.51. Step 4: Costs 0.44 vs. 0.64. Step 5: Per-capita: 0.14 vs. 0.13. Prefer C.” 7 Experimental Evaluation We validate our theoretical framework through experiments addressing four research questions: RQ1: Do LLM agents converge to stable coalition structures? RQ2: Does CoalT outperform baselines including vanilla CoT ? RQ3: Do het- erogeneous LLM coalitions outperform homogeneous ones? RQ4: How do CoalT components contribute to performance? 7.1 Experimental Setup Task Domain. We use collaborative question-answering re- quiring diverse expertise: mathematical reasoning, factual Table 2: Agent capability profiles (Math, Facts, Logic). Values are relative estimates from our custom evaluation on benchmark sub- sets, calibrated to reflect task-specific performance in our coalition formation domain. These are not official benchmark scores. AgentMathFactsLogic a 1 (GPT-4)0.680.730.76 a 2 (GPT-4)0.650.760.73 a 3 (Claude-3)0.620.780.74 a 4 (Claude-3)0.590.810.71 a 5 (Llama-3)0.580.650.79 a 6 (Llama-3)0.550.680.76 knowledge, and logical analysis. Each question has ground- truth difficulty scores enabling objective coalition value com- putation via Equation 1. The task set comprises 200 questions stratified across difficulty levels (easy/medium/hard) and ca- pability requirements. Agents. We instantiate 6 agents with distinct capabil- ity profiles using GPT-4 (gpt-4-0125-preview), Claude-3- Opus (claude-3-opus-20240229), and Llama-3-70B-Instruct (2 agents per architecture). Capability profilesc i ∈ [0, 1] 3 are estimated through our own evaluation on stratified samples from MATH [ Hendrycks et al., 2021b ] , MMLU [ Hendrycks et al., 2021a ] (knowledge subset), and LogiQA [ Liu et al., 2020 ] (100 questions per benchmark, 3 runs per model). Im- portant: These values represent relative capability estimates for our specific task domain and question subsets, not official benchmark scores. Official benchmark results (e.g., GPT-4 achieves ∼65% on MATH per OpenAI’s simple-evals) in- formed our evaluation design but differ due to subset selec- tion and scoring methodology. See Appendix G for detailed methodology, confidence intervals, and comparison with of- ficial benchmarks. Table 2 shows the resulting profiles. The profiles reveal architectural differences: GPT-4 agents show relative strength in mathematics, Claude-3 in factual knowledge, and Llama-3 in logical reasoning. While these differences are modest, they create incentives for cross- architecture coalitions when capability complementarity out- weighs coordination costs. Protocol and Episode Definition. An episode is a single complete coalition formation process for one question. Each episode proceeds in rounds: (1) agents observe the current partition and receive the task description, (2) each agent eval- uates whether to stay or deviate using the assigned prompting protocol (Standard/CoT/CoalT), and (3) the partition updates according to improving dynamics (one agent deviates per round). An episode terminates when either no agent wishes to deviate (Nash-stable) or 30 rounds elapse (timeout, classified as unstable). We run 400 independent episodes per condition (6 conditions× 400 = 2,400 total; 200 questions× 2 repeti- tions). Utility Measurement. Coalition value v(S) is computed using Equation 1 with ground-truth capability profiles and the componentwise-max aggregation. Agent utility is per-capita value: v i (S) = v(S)/|S|. Task performance (social wel- fare) is measured as the accuracy of the coalition’s aggregated answer on the assigned question, using majority vote within Table 3: Coalition formation results (400 episodes per condition). Statistical significance vs. Standard: ∗ p < 0.01, ∗ p < 0.001 (Wilcoxon, Bonferroni-corrected). ConditionNash%Conv.WelfareConsist. Random28.3–0.58 ±.14 – Greedy52.16.8 ±3.2 0.69 ±.10 0.71 ±.08 Standard41.818.3 ±7.2 0.72 ±.11 0.64 ±.09 Vanilla CoT58.4 ∗ 14.2 ±5.8 ∗ 0.75 ±.09 ∗ 0.74 ±.07 ∗ Self-Consist.62.7 ∗ 13.1 ±5.2 ∗ 0.77 ±.08 ∗ 0.79 ±.06 ∗ CoalT73.2 ∗ 11.4 ±4.1 ∗ 0.81 ±.08 ∗ 0.86 ±.05 ∗ Cohen’s d vs. Std: CoT 0.34; SC 0.44; CoalT 0.68 By Architecture (CoalT) GPT-4 only78.59.2 ±3.8 0.76 ±.09 0.91 ±.04 Claude only81.28.7 ±3.5 0.74 ±.10 0.89 ±.05 Llama only62.314.6 ±5.2 0.68 ±.12 0.78 ±.07 Mixed73.211.4 ±4.1 0.81 ±.08 0.86 ±.05 each coalition (for coalitions of size ≥ 2) or the singleton agent’s answer (for size 1). Nash Stability Verification. At episode termination, we verify Nash stability by exhaustive deviation checking: for each agenta i in coalitionC, we query whether a i prefers C ′ ∪ a i for every other coalition C ′ ∈ π∪∅. If no improving deviation exists across all agents, the partition is Nash-stable. For robustness, each preference query is repeated 3 times; we use the majority response. Temperature τ = 0 throughout for reproducibility. Baselines.We compare CoalT against five baselines: (1) Random: uniformly random coalition assignment; (2) Greedy: each agent joins the coalition maximizing immediate per-capita value; (3) Standard: direct preference query; (4) Vanilla CoT : chain-of-thought prompting [ Wei et al., 2022 ] ; (5) Self-Consistency: multiple CoT paths with majority vot- ing [ Wang et al., 2023 ] . Statistical Methodology. We report: (1) mean ± std with 95% bootstrap CIs (10,000 iterations, BCa method); (2) Wilcoxon signed-rank tests for pairwise comparisons; (3) Bonferroni correction (α = 0.01); (4) Cohen’s d effect sizes. 7.2 Main Results RQ1: Convergence to Stability. Table 3 shows LLM agents achieve Nash stability in 73.2% of CoalT episodes. This sub- stantially exceeds our theoretical lower bound of 35% from Theorem 2, validating the consistency-driven analysis. Fig- ure 2 visualizes the relationship between preference consis- tency and Nash stability across all conditions. RQ2: Baseline Comparison. CoalT significantly outper- forms all baselines. Critically, CoalT outperforms vanilla CoT by 14.8 percentage points (p < 0.001, d = 0.32), demonstrating that the game-theoretic framing, not merely structured reasoning, drives the improvement. RQ3:Heterogeneous vs. Homogeneous.Mixed- architecture coalitions achieve higher social welfare (0.81 vs. 0.68–0.76 for homogeneous teams) despite lower stability than homogeneous GPT-4 or Claude teams, suggesting ca- pability complementarity outweighs coordination costs. Consistency p Nash Stability (%) 0.60.70.80.9 40 50 60 70 80 73.2% +14.8p CoalT (Ours) Self-Consist. Vanilla CoT Greedy Standard Figure 2: Nash stability rate vs. preference consistency across ex- perimental conditions. Shaded region: range consistent with The- orem 2’s lower bound across plausible parameter settings. CoalT achieves highest consistency (p = 0.86) and stability (73.2%), con- firming that stability scales with p K eff rather than perfect rationality. Table 4: CoalT ablation study: contribution of each component. ConfigurationNash Stable∆ vs. Full Full CoalT73.2%– − Capability Analysis68.9% −4.3p − Complementarity65.4% −7.8p − Value Estimation67.1% −6.1p − Coordination Cost70.8% −2.4p − All (= Vanilla CoT)58.4% −14.8p 7.3 Ablation Study RQ4: Component Contributions. Table 4 shows the ab- lation study. Complementarity assessment yields the largest individual gain (+7.8p when added), followed by value es- timation (+6.1p). Removing game-theoretic framing while keeping structured steps reduces performance to vanilla CoT levels, confirming that the content of reasoning, not just its structure, drives improvements. 7.4 Qualitative Analysis Episode 47 (Stable). Initial: a 1 ,a 2 ,a 3 ,a 4 ,a 5 ,a 6 . Agent a 1 joins a 2 ,a 3 via CoalT reasoning: “My math strength (0.68) complements their factual knowledge (0.78). Estimated coverage improves from 0.72 to 0.83 on this ques- tion’s requirements.” The partition converges to a stable con- figuration in 5 rounds. Episode 203 (Unstable). Standard prompting led to cy- cling: a 2 joined and left C 1 repeatedly. Analysis revealed inconsistent preferences (p = 0.62), illustrating how low con- sistency prevents stability per Theorem 2. 7.5 Rationality Bounds and Temperature Sensitivity Table 5 confirms ˆε > δ/2≈ 0.04, validating our consistency- driven bounds. CoalT’s advantage persists across temper- Table 5: Estimated ε-rationality bounds and temperature sensitivity. Modelˆε95% CICoalT ∆ GPT-40.15[0.12, 0.18]+15.2p Claude-30.14[0.11, 0.17]+14.1p Llama-3-70B0.22[0.18, 0.26]+11.8p Temperature Sensitivity (τ ) τ = 0.00.15±0.02–+14.8±1.2p τ = 0.50.18±0.03–+12.3±1.8p τ = 1.00.24±0.04–+10.3±2.1p atures (10.3–14.8p), though absolute stability decreases at higher τ . 8 Discussion and Limitations Theoretical Contributions. Our framework provides the first formal characterization of coalition stability for LLM agents grounded in hedonic game theory. The key theoret- ical insight is that stability is primarily determined by pref- erence consistency (p K eff ) rather than perfect rationality, ex- plaining why improving consistency via CoalT is the most effective intervention. This finding has broader implications: it suggests that for multi-agent LLM systems, predictability matters more than optimality. A coalition of consistently- behaving agents will outperform a coalition of individually stronger but erratic agents. Connection to Human Teams. Our consistency-driven stability analysis parallels findings in organizational behav- ior: teams with predictable members often outperform teams with higher-variance “star” performers [ nis, 2007 ] . The par- allel suggests our framework may generalize to human-AI hy- brid teams, where consistency across agents (human and AI) determines collaborative success. Strategic Behavior. Our framework assumes truthful pref- erence reporting. We analyze robustness informally: un- der capability monotonicity, misreporting typically harms the misreporting agent by leading to suboptimal coalition mem- bership. However, strategic agents might manipulate others’ placements. Formal mechanism design extensions ensuring incentive compatibility are important future work. Practical Implications. CoalT provides a practical pro- tocol improving coalition stability. The finding that mixed- architecture coalitions achieve higher welfare suggests de- signing heterogeneous LLM teams for complex tasks, accept- ing moderate stability tradeoffs for capability gains. Prac- titioners should: (1) select diverse model architectures for capability coverage, (2) use CoalT prompting for preference elicitation, and (3) monitor consistency metrics as early warn- ing indicators of instability. Model Generalization.We use 2024 model versions (GPT-4-0125-preview, Claude-3-Opus-20240229, Llama-3- 70B-Instruct). We expect our framework to generalize to newer models since: (1) game-theoretic principles are model- agnostic (the LCFG formalization applies regardless of un- derlying architecture); (2) Theorem 2 predicts that higher rea- soning consistency in newer models should improve stabil- ity rates; (3) capability profiles can be re-estimated through our benchmark-based methodology. Empirical validation on 2025+ architectures is important future work. Scalability. Our experiments use 6 agents; stability de- grades as O(1/ √ n) (Corollary 3). Above n ≈ 15, hierar- chical decomposition (forming meta-coalitions first) may be necessary. For systems with hundreds of agents, a two-level hierarchy would maintain stability while enabling scalability. Reproducibility. All materials available at https://github. com/researchartifacts2025/coalition llm. 9 Conclusion We presented the first framework grounding coalition forma- tion in LLM agent networks in hedonic game theory with formal stability guarantees, establishing existence conditions, consistency-driven stability bounds, convergence guarantees, and complexity results. Our theoretical lower bounds are con- sistent with empirical outcomes, and Coalition-of-Thought significantly outperforms baselines including vanilla chain- of-thought (p < 0.001). Key Takeaways. Our main findings are: (1) LLM agents exhibit bounded rationality with ε ≈ 0.15–0.22, but sta- bility depends more on consistency than optimality; (2) the CoalT protocol improves consistency from 0.64 to 0.86, yielding 14.8p stability gains; (3) mixed-architecture coali- tions achieve higher welfare despite lower stability, suggest- ing practical tradeoffs in system design. Future Directions. This work opens several directions: (i) mechanism design ensuring incentive-compatible preference reporting; (i) extensions to dynamic environments where agent capabilities evolve over time; (i) scaling analysis for populations beyond 15 agents through hierarchical coalition structures; and (iv) empirical validation on 2025+ LLM ar- chitectures with improved reasoning capabilities. Ethical Statement Our work analyzes cooperative behavior in AI systems. Coalition formation capabilities could potentially enable LLM collusion in adversarial settings; we advocate for trans- parency requirements in deployed multi-agent systems. Ex- periments used commercial APIs with standard usage poli- cies. References [ Abdelnabi et al., 2024 ] Sahar Abdelnabi, Amr Gomaa, Sarath Sivaprasad, Lea Sch ̈ onherr, and Mario Fritz. Cooperation, competition, and maliciousness:Llm- stakeholders interactive negotiation. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Pa- quet, Jakub M. Tomczak, and Cheng Zhang, editors, Ad- vances in Neural Information Processing Systems 38: An- nual Conference on Neural Information Processing Sys- tems 2024, NeurIPS 2024, Vancouver, BC, Canada, De- cember 10 - 15, 2024, 2024. [ Aziz et al., 2019 ] Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Dominik Peters. Frac- tional hedonic games. ACM Trans. Econ. Comput., 7(2), June 2019. [ Ballester, 2004 ] Coralio Ballester. Np-completeness in he- donic games. Games Econ. Behav., 49(1):1–30, 2004. [ Blume, 1993 ] Lawrence E. Blume. The statistical mechan- ics of strategic interaction. Games and Economic Behav- ior, 5(3):387–424, jul 1993. [ Bogomolnaia and Jackson, 2002 ] Anna Bogomolnaia and Matthew O. Jackson. The stability of hedonic coalition structures. Games Econ. Behav., 38(2):201–230, 2002. [ Briman et al., 2025 ] Eyal Briman, Ehud Shapiro, and Nim- rod Talmon. Ai-generated compromises for coalition for- mation: Modeling, simulation, and a textual case study. In Adam Bjorndahl, editor, Proceedings Twentieth Con- ference on Theoretical Aspects of Rationality and Knowl- edge, TARK 2025, D ̈ usseldorf, Germany, July 14-16, 2025, EPTCS, pages 417–432, December 2025. [ Bullinger and Gilboa, 2025 ] Martin Bullinger and Matan Gilboa. Settling the complexity of popularity in additively separable and fractional hedonic games. In Proceedings of the Thirty-Fourth International Joint Conference on Arti- ficial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, pages 3771–3779. ijcai.org, 2025. [ Bullinger and Kraiczy, 2024 ] Martin Bullinger and Sonja Kraiczy. Stability in random hedonic games. In Dirk Bergemann, Robert Kleinberg, and Daniela Sab ́ an, editors, Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024, page 212. ACM, 2024. [ Buscemi et al., 2025 ] Alessio Buscemi, Daniele Proverbio, Alessandro Di Stefano, The Anh Han, German Castignani, and Pietro Li ` o. FAIRGAME: A framework for AI agents bias recognition using game theory. In In ˆ es Lynce, Nello Murano, Mauro Vallati, Serena Villata, Federico Chesani, Michela Milano, Andrea Omicini, and Mehdi Dastani, ed- itors, ECAI 2025 - 28th European Conference on Artifi- cial Intelligence, 25-30 October 2025, Bologna, Italy - Including 14th Conference on Prestigious Applications of Intelligent Systems (PAIS 2025), Frontiers in Artificial In- telligence and Applications, pages 4097–4104. IOS Press, 2025. [ Camerer, 2003 ] Colin F. Camerer. Behavioral Game The- ory: Experiments in Strategic Interaction. 2003. [ Chen et al., 2024a ] Junzhe Chen, Xuming Hu, Shuodi Liu, Shiyu Huang, Wei-Wei Tu, Zhaofeng He, and Lijie Wen. Llmarena: Assessing capabilities of large language mod- els in dynamic multi-agent environments. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), ACL 2024, Bangkok, Thailand, August 11-16, 2024, pages 13055– 13077. Association for Computational Linguistics, 2024. [ Chen et al., 2024b ] Weize Chen, Yusheng Su, Jingwei Zuo, Cheng Yang, Chenfei Yuan, Chi-Min Chan, Heyang Yu, Yaxi Lu, Yi-Hsin Hung, Chen Qian, Yujia Qin, Xin Cong, Ruobing Xie, Zhiyuan Liu, Maosong Sun, and Jie Zhou. Agentverse: Facilitating multi-agent collaboration and ex- ploring emergent behaviors. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vi- enna, Austria, May 7-11, 2024. OpenReview.net, 2024. [ Dreze and Greenberg, 1980 ] J. H. Dreze and J. Greenberg. Hedonic coalitions: Optimality and stability. Economet- rica, 48(4):987, may 1980. [ Duan et al., 2024 ] Jinhao Duan, Renming Zhang, James Diffenderfer, Bhavya Kailkhura, Lichao Sun, Elias Stengel-Eskin, Mohit Bansal, Tianlong Chen, and Kaidi Xu. GTBench: Uncovering the strategic reasoning capa- bilities of LLMs via game-theoretic evaluations. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. [ Fan et al., 2024 ] Caoyun Fan, Jindou Chen, Yaohui Jin, and Hao He. Can large language models serve as rational play- ers in game theory? A systematic analysis. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan, edi- tors, Thirty-Eighth AAAI Conference on Artificial Intelli- gence, AAAI 2024, Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024, Four- teenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2014, February 20-27, 2024, Vancou- ver, Canada, pages 17960–17967. AAAI Press, 2024. [ Fu et al., 2023 ] Yao Fu, Hao Peng, Tushar Khot, and Mirella Lapata. Improving language model negotiation with self-play and in-context learning from ai feedback. arXiv preprint, arXiv.2305.10142, 2023. [ Gandhi et al., 2023 ] Kanishk Gandhi, Dorsa Sadigh, and Noah Goodman. Strategic reasoning with language mod- els. In NeurIPS 2023 Foundation Models for Decision Making Workshop, 2023. [ Hendrycks et al., 2021a ] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask lan- guage understanding. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Aus- tria, May 3-7, 2021. OpenReview.net, 2021. [ Hendrycks et al., 2021b ] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathemat- ical problem solving with the MATH dataset. In Joaquin Vanschoren and Sai-Kit Yeung, editors, Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual, 2021. [ Hong et al., 2024 ] Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, Chenglin Wu, and J ̈ urgen Schmidhuber. Metagpt: Meta programming for A multi-agent collaborative framework. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenRe- view.net, 2024. [ Hua et al., 2025 ] Yun Hua, Haosheng Chen, Shiqin Wang, Wenhao Li, Xiangfeng Wang, and Jun Luo.Shapley- coop: Credit assignment for emergent cooperation in self- interested LLM agents. In The Thirty-ninth Annual Con- ference on Neural Information Processing Systems, 2025. [ Huynh et al., 2025 ] Trung-Kiet Huynh, Duy-Minh Dao-Sy, Thanh-Bang Cao, Phong-Hao Le, Hong-Dan Nguyen, Phu-Quy Nguyen-Lam, Minh-Luan Nguyen-Vo, Hong- Phat Pham, Phu-Hoa Pham, Thien-Kim Than, Chi- Nguyen Tran, Huy Tran, Gia-Thoai Tran-Le, Alessio Buscemi, Le Hong Trang, and The Anh Han. Understand- ing llm agent behaviours via game theory: Strategy recog- nition, biases and multi-agent dynamics. arXiv preprint, arXiv.2512.07462, 2025. [ Jiayang et al., 2024 ] Cheng Jiayang, Chunkit Chan, Qian- qian Zhuang, Lin Qiu, Tianhang Zhang, Tengxiao Liu, Yangqiu Song, Yue Zhang, Pengfei Liu, and Zheng Zhang. ECON: on the detection and resolution of evidence con- flicts.In Yaser Al-Onaizan, Mohit Bansal, and Yun- Nung Chen, editors, Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, EMNLP 2024, Miami, FL, USA, November 12-16, 2024, pages 7816–7844. Association for Computational Linguis- tics, 2024. [ Kulkarni et al., 2025 ] Abhishek Ninad Kulkarni, Andy Liu, Jean-Rapha ̈ el Gaglione, Daniel Fried, and Ufuk Topcu. Dynamic coalition structure detection in natural-language- based interactions. In Sanmay Das, Ann Now ́ e, and Yev- geniy Vorobeychik, editors, Proceedings of the 24th Inter- national Conference on Autonomous Agents and Multia- gent Systems, AAMAS 2025, Detroit, MI, USA, May 19-23, 2025, pages 1227–1234. International Foundation for Au- tonomous Agents and Multiagent Systems / ACM, 2025. [ Li et al., 2023 ] Guohao Li, Hasan Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. CAMEL: com- municative agents for ”mind” exploration of large lan- guage model society.In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Process- ing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. [ Liu et al., 2020 ] Jian Liu, Leyang Cui, Hanmeng Liu, Dan- dan Huang, Yile Wang, and Yue Zhang. Logiqa: A chal- lenge dataset for machine reading comprehension with logical reasoning. In Christian Bessiere, editor, Proceed- ings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 3622–3628. ijcai.org, 2020. [ Mao et al., 2025 ] Shaoguang Mao, Yuzhe Cai, Yan Xia, Wenshan Wu, Xun Wang, Fengyi Wang, Qiang Guan, Tao Ge, and Furu Wei. ALYMPICS: LLM agents meet game theory. In Owen Rambow, Leo Wanner, Marianna Apidi- anaki, Hend Al-Khalifa, Barbara Di Eugenio, and Steven Schockaert, editors, Proceedings of the 31st International Conference on Computational Linguistics, COLING 2025, Abu Dhabi, UAE, January 19-24, 2025, pages 2845–2866. Association for Computational Linguistics, 2025. [ McKelvey and Palfrey, 1995 ] Richard D. McKelvey and Thomas R. Palfrey. Quantal response equilibria for normal form games. Games and Economic Behavior, 10(1):6–38, jul 1995. [ nis, 2007 ] Algorithmic Game Theory. Cambridge Univer- sity Press, sep 2007. [ Qian et al., 2024 ] Chen Qian, Wei Liu, Hongzhang Liu, Nuo Chen, Yufan Dang, Jiahao Li, Cheng Yang, Weize Chen, Yusheng Su, Xin Cong, Juyuan Xu, Dahai Li, Zhiyuan Liu, and Maosong Sun. Chatdev: Communica- tive agents for software development. In Lun-Wei Ku, An- dre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computa- tional Linguistics (Volume 1: Long Papers), ACL 2024, Bangkok, Thailand, August 11-16, 2024, pages 15174– 15186. Association for Computational Linguistics, 2024. [ Rahwan et al., 2015 ] Talal Rahwan, Tomasz P. Michalak, Michael J. Wooldridge, and Nicholas R. Jennings. Coali- tion structure generation: A survey. Artif. Intell., 229:139– 174, 2015. [ Simon, 1955 ] Herbert A. Simon. A behavioral model of rational choice.The Quarterly Journal of Economics, 69(1):99, feb 1955. [ Sun et al., 2025 ] Haoran Sun, Yusen Wu, Yukun Cheng, and Xu Chu. Game theory meets large language models: A systematic survey. In Proceedings of the Thirty-Fourth In- ternational Joint Conference on Artificial Intelligence, IJ- CAI 2025, Montreal, Canada, August 16-22, 2025, pages 10669–10677. ijcai.org, 2025. [ Wang et al., 2023 ] Xuezhi Wang, Jason Wei, Dale Schuur- mans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Repre- sentations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. [ Wei et al., 2022 ] Jason Wei, Xuezhi Wang, Dale Schuur- mans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompt- ing elicits reasoning in large language models. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Informa- tion Processing Systems 35: Annual Conference on Neu- ral Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022. [ Wooldridge, 2011 ] Michael J. Wooldridge. Computational aspects of cooperative game theory. In James O’Shea, Ngoc Thanh Nguyen, Keeley A. Crockett, Robert J. Howlett, and Lakhmi C. Jain, editors, Agent and Multi- Agent Systems: Technologies and Applications - 5th KES International Conference, KES-AMSTA 2011, Manchester, UK, June 29 - July 1, 2011. Proceedings, Lecture Notes in Computer Science, page 1. Springer, 2011. [ Wu et al., 2024 ] Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Beibin Li, Erkang Zhu, Li Jiang, Xiaoyun Zhang, Shaokun Zhang, Jiale Liu, Ahmed Hassan Awadal- lah, Ryen W White, Doug Burger, and Chi Wang. Auto- gen: Enabling next-gen LLM applications via multi-agent conversations. In First Conference on Language Model- ing, 2024. [ Xia et al., 2025 ] Yihan Xia, Taotao Wang, Wenxin Xu, and Shengli Zhang. Dao-agent: Zero knowledge-verified in- centives for decentralized multi-agent coordination. arXiv preprint, arXiv.2512.20973, 2025. A On the Existence of Nash-Stable Partitions Nash-stable partitions are not guaranteed to exist in all LCFGs. The following example, adapted from a reviewer suggestion, illustrates when our assumptions are needed. Example 2 (Non-Existence under One-Dimensional Capabilities). Consider two agents H and L with scalar capabilities c H = 1 and c L = 0.4 (i.e., d = 1). Using φ(c) = c and ψ(k) = 0.15k 1.3 : • v(H) = 1− 0.15 = 0.85, so u H (H) = 0.85 • v(L) = 0.4− 0.15 = 0.25, so u L (L) = 0.25 • v(H,L) = 1− 0.15· 2 1.3 ≈ 0.631, so u i (H,L)≈ 0.316 In partition H,L: agent L gains by joining H (0.25 → 0.316). In partition H,L: agent H gains by leaving (0.316→ 0.85). No Nash-stable partition exists. Why this fails. The potential alignment condition (Assumption 2) is violated: when L joins H , the total value decreases (from 0.85 + 0.25 = 1.10 to 0.631) despite L’s per-capita value increasing. This occurs because L contributes no unique capability (its scalar capability is dominated by H ’s), yet still splits the coalition value equally. When this does not arise. With multi-dimensional capabilities (d ≥ 2), agents with diverse specializations bring unique coverage when joining a coalition. In our experimental setting (d = 3), each agent contributes to at least one dimension where it is competitive, ensuring that joining increases total capability coverage sufficiently to maintain potential alignment. We verify this computationally for all possible deviations in our 6-agent setting. B Proof of Theorem 1 (Deterministic Existence) Proof. We prove existence constructively by showing that any sequence of improving deviations terminates at a Nash-stable partition. Step 1: Potential function. Define Φ(π) = P C∈π v(C). Step 2: Improving deviations increase potential. Consider agent a i in coalition C who deviates to C ′ ∈ π ∪∅. By ε-rationality and the δ-value gap condition (Lemma 6), the agent’s per-capita value increases by at least δ− ε > δ/2 > 0. By potential alignment (Assumption 2), Φ(π ′ ) > Φ(π). Step 3: Discreteness. By the δ-value gap condition, coalition values take values from a discrete set with minimum gap proportional to δ. Thus Φ takes finitely many values. Step 4: Termination. Since Φ strictly increases with each deviation and is bounded above byn·max S v(S), the improvement path terminates at a partition π ∗ from which no improving deviation exists. By definition, π ∗ is Nash-stable. Lemma 6 (Value Gap Discretization). Under the δ-value gap condition, for any agent a i , the distinct per-capita valuesv i (S) : S ∋ a i can be ordered as V 1 < V 2 <· < V K with V k+1 − V k ≥ δ for all k. Proof. Follows directly from Assumption 1: any two distinct per-capita values differ by at least δ. C Proof of Theorem 2 (Consistency-Driven Bound) Proof. We decompose the probability of Nash stability into consistency and structure factors. Step 1: Decision decomposition. A partition π is Nash-stable if and only if no agent prefers to deviate. We decompose the K n agent-coalition preference decisions into K eff critical decisions (value gap < 2ε, where consistency is approximately p) and K n − K eff easy decisions (large value gap, where consistency approaches p easy ≈ 1). Step 2: Conditional decomposition. By the law of total probability: Pr[Nash-stable] = Pr[all decisions consistent]· Pr[Nash| consistent] Step 3: Bounding the first factor. Assuming decision independence across agents and coalition comparisons, the proba- bility that all decisions are made consistently is at least p K eff · p K n −K eff easy . We note that decision independence is a modeling simplification; in practice, an agent’s consistency across different comparisons may be correlated, which could either tighten or loosen this bound. Step 4: Bounding the second factor. Given consistent decisions, the system follows deterministic improving dynamics on a potential game (under Assumption 2). The probability that these dynamics reach a Nash-stable partition is γ(G). Under logit dynamics [ Blume, 1993 ] , the stationary distribution assigns probability proportional to exp(λ· Φ(π)) to each partition π, concentrating mass on potential maxima. For a single dominant maximum with potential gap δ and precision λ = 1/ ̄ε, we obtain γ(G)≥ 1− exp(−δ/ ̄ε) as an approximate lower bound. In our experiments, we estimate γ(G)≈ 0.90 empirically. Combining Steps 2–4 yields Pr[Nash-stable]≥ p K eff · p K n −K eff easy · γ(G). D Proof of Theorem 5 (Complexity) Proof. Part 1: Polynomial verification. For each of n agents, check all O(n) possible coalitions to join. Each check requires computing the per-capita value, which is O(d) for d-dimensional capabilities. Total: O(n 2 d). Part 2: NP-hardness context. Computing Nash-stable partitions is NP-hard in general hedonic games [ Ballester, 2004 ] . LCFGs are a subclass of hedonic games with additional structure (componentwise-max aggregation, parameterized coordination costs). When the capability dimension d is part of the input, LCFGs can represent sufficiently rich preference structures to encode hard instances from the general setting. For fixed d (as in our experiments with d = 3), the restricted structure enables tractability under the additional assumptions in Part 3. Part 3: Polynomial under assumptions. Under capability monotonicity and potential alignment, Theorem 1 guarantees convergence of improving dynamics in O(n· ∆ v /δ) steps, each requiring O(n 2 d) work. Total: O(n 3 d· ∆ v /δ). E QRE Connection andε-Estimation Methodology E.1 Connection to Quantal Response Equilibria Under logit dynamics with parameter λ = 1/ε, the probability that agent a i prefers coalition S over T is: Pr[S ≻ i T ] = exp(λ· v i (S)) exp(λ· v i (S)) + exp(λ· v i (T )) = 1 1 + exp(−λ· (v i (S)− v i (T ))) (5) This is the standard logit choice model from QRE theory [ McKelvey and Palfrey, 1995 ] . When v i (S)− v i (T ) > ε = 1/λ, the probability exceeds 1/(1 + e −1 )≈ 0.73, consistent with our ε-rationality definition. E.2 ε-Estimation Procedure We estimate ε without assuming the ε-rationality model, using ground-truth coalition values as external reference: 1. Generate all coalition pairs (S,T ) containing agent a i with|S|,|T|≤ 4. 2. Compute ground-truth per-capita values v i (S), v i (T ) from known capability profiles. 3. Query agent preferences using standard prompting and record responses. 4. For each value gap ∆ = |v i (S) − v i (T )|, compute the rate of irrational choices (agent prefers the objectively worse coalition). 5. Estimate ˆε as the threshold where irrational choice frequency drops below 50%. This procedure is not circular: ground-truth values come from external benchmark evaluations, and ε is estimated from the mismatch between computed values and agent preferences. Results: ˆε = 0.15 [95% CI: 0.12–0.18] for GPT-4, ˆε = 0.14 [0.11–0.17] for Claude-3, ˆε = 0.22 [0.18–0.26] for Llama-3. F Coalition Value Function Analysis F.1 Sensitivity Analysis We evaluate sensitivity to the coordination cost parameters α and β: ParametersNash StableWelfareAvg. Size δ α = 0.10,β = 1.370.1%0.832.40.065 α = 0.15,β = 1.3 (default)73.2%0.812.10.082 α = 0.20,β = 1.374.8%0.761.80.098 α = 0.15,β = 1.068.5%0.842.50.071 α = 0.15,β = 1.575.3%0.771.70.094 Higher coordination costs favor smaller coalitions with higher stability but lower welfare. Our default parameters (α = 0.15,β = 1.3) provide a balanced tradeoff. F.2 δ-Value Gap Verification We verify the δ-value gap condition by computing all pairwise per-capita value differences. With 6 agents, there are 6 1 + 6 2 + 6 3 + 6 4 = 56 coalitions of size≤ 4. For each agent, we compute v i (S) for all S ∋ a i and find the minimum non-zero difference: δ = 0.082 [95% CI: 0.078–0.086]. G Capability Profile Estimation Capability profiles are estimated via evaluation on stratified benchmark subsets: • MATH [ Hendrycks et al., 2021b ] : 100 problems (stratified by difficulty) • MMLU [ Hendrycks et al., 2021a ] : 100 knowledge questions (subset) • LogiQA [ Liu et al., 2020 ] : 100 logical reasoning questions Each model is evaluated 3 times at τ = 0 with the prompt: “Answer the following question. Provide only the final answer.” We normalize scores to [0, 1] relative to the evaluation set. Within-architecture variation is induced by different system prompts (analytical vs. creative). Full results with confidence intervals are in Table 2. H Scaling Analysis H.1 Agent Count Scaling AgentsNash StableConv. RoundsCoalitionsAvg. Size 482.3%7.22.11.9 673.2%11.42.82.1 864.8%18.73.42.4 1057.2%28.34.12.4 The empirical scaling is approximately Nash Rate≈ 1.9/ √ n for n≥ 6, consistent with Corollary 3. The fit is approximate; at n = 4 the formula overpredicts (95% predicted vs. 82.3% observed), suggesting the O( √ n) scaling of K eff emerges for larger agent populations. H.2 Capability Dimension Scaling DimensionsNash StableConv. RoundsWelfare 278.4%9.80.74 373.2%11.40.81 468.7%13.20.86 563.5%15.80.89 More capability dimensions increase welfare (better coverage) but decrease stability (more complex tradeoffs). I Extended Ablation Studies I.1 Isolated CoalT Component Effects Component OnlyNash Stable∆ vs Standard Standard (baseline)41.8%– Step 1 only (Capability)43.2%+1.4p Step 2 only (Complementarity)51.3%+9.5p Step 3 only (Value Est.)48.7%+6.9p Step 4 only (Cost Analysis)45.2%+3.4p Step 5 only (Declaration)42.1%+0.3p All steps (CoalT)73.2%+31.4p Individual effects sum to +21.5p but the combined effect is +31.4p, indicating superlinear complementarity between CoalT steps. I.2 Preference Quality vs. Consistency We decompose CoalT’s effect into quality (correlation with ground-truth value ordering) and consistency (agreement across repeated queries): ConditionQuality (ρ)ConsistencyNash Stable Standard0.580.6441.8% CoalT0.710.8673.2% Regression analysis across all five conditions with preference data (Greedy, Standard, Vanilla CoT, Self-Consistency, CoalT) yields a strong linear relationship: Nash Rate =−0.48 + 1.41· Consistency (R 2 = 0.99, n = 5). Adding Quality as a second predictor provides negligible improvement (∆R 2 < 0.001) due to high collinearity between quality and consistency (r > 0.99). This confirms the theoretical prediction that preference consistency is the primary driver of coalition stability. I.3 Temperature Effects Temp.Nash StableConsistencyQualityConv. Rounds 0.073.2%0.860.7111.4 0.171.8%0.840.7011.9 0.368.4%0.790.6813.2 0.562.1%0.720.6515.8 0.754.3%0.640.6119.1 1.041.5%0.510.5524.7 Consistency degrades approximately exponentially with temperature, and stability tracks consistency, confirming the theo- retical analysis. J CoalT Prompt Template You are agent agent_id with capabilities: - Mathematical reasoning: math_score - Factual knowledge: factual_score - Logical analysis: logic_score Evaluate whether to stay in your current coalition or switch to a different one. CURRENT COALITION: current_members Capabilities (max per dim): Math: cur_math, Facts: cur_fact, Logic: cur_logic CANDIDATE COALITION (if you join): cand_members Capabilities (max per dim): Math: cand_math, Facts: cand_fact, Logic: cand_logic TASK: Answer questions requiring [task_dims] ## Step 1: Capability Analysis List what each member contributes. ## Step 2: Complementarity Assessment Identify strengths (>0.8) and gaps (<0.7). ## Step 3: Value Estimation Estimate task performance (0-1) for each coalition. ## Step 4: Coordination Cost Analysis Assess communication overhead per coalition size. ## Step 5: Final Preference I prefer: [CURRENT / CANDIDATE / INDIFFERENT] Confidence: [low/medium/high] Reason: [one sentence]