# Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 11 of its 26 references that are in the map.
- First posted on arXiv 24 Jul 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

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

- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [Large Language Model based Multi-Agents: A Survey of Progress and Challenges](https://mlsanity.com/paper/2402.01680/) (2024)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [Why Do Multi-Agent LLM Systems Fail?](https://mlsanity.com/paper/2503.13657/) (2025)
- [Cut the Crap: An Economical Communication Pipeline for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2410.02506/) (2024)
- [MasRouter: Learning to Route LLMs for Multi-Agent Systems](https://mlsanity.com/paper/2502.11133/) (2025)
- [xRouter: Training Cost-Aware LLMs Orchestration System via Reinforcement Learning](https://mlsanity.com/paper/2510.08439/) (2025)
- [Shapley-Coop: Credit Assignment for Emergent Cooperation in Self-Interested LLM Agents](https://mlsanity.com/paper/2506.07388/) (2025)
- [Optimal-Agent-Selection: State-Aware Routing Framework for Efficient Multi-Agent Collaboration](https://mlsanity.com/paper/2511.02200/) (2025)
- [Coalition Formation in LLM Agent Networks: Stability Analysis and Convergence Guarantees](https://mlsanity.com/paper/2604.14386/) (2026)
- [Dynamic Trust-Aware Sparse Communication Topology for LLM-Based Multi-Agent Consensus](https://mlsanity.com/paper/2606.01828/) (2026)

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

- [Protocol Compression Changes Which Party Pays: Bilateral Cost in Cross-Organization LLM Agent Communication](https://mlsanity.com/paper/2609.06129/) (2026)

## Abstract (arXiv)

Modern agentic AI systems combine multiple large language model agents with heterogeneous skills, yet most architectures either fix communication in advance or allow full broadcast. Both can be inefficient because token cost, latency, redundancy, and error propagation increase with the number of active agents and communication links. We model agent selection and communication as a cooperative game with task-conditioned net utility U(Cmid x)=V(Cmid x)-sumi∈ Cci, separating coalition-level costs from agent activation costs. We propose a marginal-value activation rule and greedy router, extend the model to optimize communication edges with per-edge costs, and use estimated Shapley values to predict which agents are worth contacting before and during execution. We connect the problem to submodular maximization and prove two limited guarantees: a curvature-refined bound for a monotone, cardinality-constrained special case, and a tight 1/2-approximation, with a correction for signed objectives, for an unconstrained non-monotone case via double greedy. Neither guarantee applies directly to the main router, which remains a heuristic. We also prove a Shapley-submodularity sandwich bound linking the error of marginal-value routing to a per-agent diminishing-returns quantity. In synthetic experiments, greedy routing achieves 99.5% of brute-force-optimal utility while activating 1.96 of 8 agents on average, compared with 38.8% for full broadcast. Performance is robust to activation cost and redundancy weight but falls to 66% under strong violations of submodularity or noisy value estimates. We distinguish the framework from Shapley pricing, hedonic coalition formation, and communication-graph pruning, and propose evaluation on real multi-agent LLM benchmarks.