🤖 AI

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

This paper proposes a cooperative game-theoretic framework for dynamic coalition formation and communication pricing in skill-based agentic AI systems that uses marginal-value activation and Shapley-value estimation to optimize agent selection and communication links, achieving near-optimal utility with significantly reduced costs while providing theoretical approximation guarantees under specific submodularity conditions.

Original authors: Mojtaba Eslami

Published 2026-08-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mojtaba Eslami

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the conductor of a massive, chaotic orchestra where every musician is a super-smart robot. In the world of artificial intelligence, these robots are called "agents," and they are designed to solve complex problems by talking to each other. But here's the catch: in many current systems, the conductor just tells everyone to start playing at once, no matter what the song is. It's like asking a violinist, a drummer, and a tuba player to all blast their instruments simultaneously just to hear a simple melody. This creates a huge mess of noise, wastes a ton of energy (or in the robot world, expensive computer power and time), and often makes the final result worse because the robots start arguing or repeating each other.

To fix this, scientists use a branch of math called "game theory," which is basically the study of how groups make decisions to get the best result for everyone. A key idea in this field is the "Shapley value," a fancy way of figuring out exactly how much credit each person deserves for a group success. Think of it like splitting a pizza fairly: if one person brought the dough, another brought the cheese, and a third just watched, the pizza cutter knows who gets the biggest slice. The big question this paper asks is: Can we use these fair-splitting math tools to decide before the music starts, exactly which robots should play, who they should talk to, and who should stay silent, so we don't waste resources on a noisy, expensive disaster?

This paper, titled "Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems," proposes a new way to run these robot teams. The author suggests treating the selection of robots like a smart shopping list. Instead of buying every tool in the store, the system calculates the "net utility"—the value a robot adds minus the cost of hiring it. They found that simply turning on every available robot is incredibly inefficient. In their tests, a "full broadcast" approach (where everyone talks to everyone) only recovered about 38.8% of the possible value, while wasting resources.

The paper introduces a "greedy router," which is a simple, fast rule that acts like a savvy manager. This manager asks, "If I add this specific robot to the team right now, will the extra value it brings be greater than the cost of paying it?" If the answer is yes, the robot is hired; if not, it stays home. The researchers proved mathematically that this method works very well when the robots' skills don't overlap too much (a concept called "submodularity," or diminishing returns). In their controlled computer simulations, this smart manager managed to find the perfect team 99.5% of the time compared to a super-slow computer that checked every single possible combination, but it did so by using only about 2 robots on average instead of all 8 available.

However, the author is very careful not to overhype their results. They explicitly state that this is a theoretical framework tested in a "synthetic simulation," meaning it was run in a made-up digital world, not on real-world robots yet. They warn that their method relies on two big assumptions: that adding more robots always gives less and less extra help (diminishing returns), and that the system can accurately guess how good a robot will be. When they tested what happens if these assumptions break—like if two robots suddenly become super powerful only when working together, or if the system guesses their skills wrong—the performance dropped significantly, sometimes down to 66% of the best possible result.

The paper also tackles the tricky issue of "credit assignment." Once the team finishes a task, how do you know who actually did the work? The author suggests using "Shapley values" not just after the fact to pay the robots, but during the process to predict who is worth contacting. They proved a mathematical "sandwich bound," which essentially says that if the robots' skills are distinct, a simple guess about who is helpful is very close to the perfectly fair credit score. But if the robots are very similar (redundant), that simple guess can be far off, and the system needs more complex math to get it right.

Ultimately, this paper doesn't claim to have solved the problem of AI teamwork for the real world yet. Instead, it provides a solid blueprint and a set of rules for how to think about the problem. It argues that more agents and more messages do not automatically equal better intelligence; in fact, they often equal more waste. The author proposes a future path where real-world tests are run on actual AI systems to see if this "smart manager" approach can save money and time while getting better answers, but for now, the proof is in the simulation, not the real world.

Technical Summary: Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems

Problem Statement

Modern agentic AI systems decompose complex tasks among multiple specialized Large Language Model (LLM) agents (e.g., planners, coders, critics). However, current deployed architectures suffer from two primary inefficiencies:

Over-activation: Systems often invoke every available skill or tool regardless of marginal utility, inflating token costs and latency without commensurate quality gains, and sometimes degrading performance through redundancy or conflict.
Over-communication: Architectures frequently rely on fixed, dense communication topologies (e.g., fully connected graphs) that do not adapt to the marginal informativeness of messages for specific tasks.

The paper argues that both issues stem from a lack of economic rigor in agent orchestration. The core problem is reframed as an economic allocation problem: an agent should be activated, and a communication edge established, only when the expected marginal value created for the task exceeds the associated computational, latency, privacy, and error-propagation costs.

Methodology

1. Formalization as a Cooperative Game

The author formalizes agent coalition formation and communication as a cooperative game with a task-conditioned net-utility function:
$U(C | x) = V(C | x) - \sum_{i \in C} c_i$

$V(C | x)$ : Represents the coalition's expected net value (quality minus latency, hallucination risk, and redundancy costs) dependent on how agents collaborate, not just who is present.
$c_i$ : Represents the specific activation cost (token/compute) of agent $i$ .
Separation of Costs: A deliberate accounting choice separates coalition-level costs (in $V$ ) from per-agent activation costs (in the summation) to prevent double-counting token costs.

The optimization goal is to find the coalition $C^*$ that maximizes $U(C | x)$ . This framework is extended to include communication edges as decision variables, optimizing the communication graph $G_C$ alongside coalition membership to minimize edge costs ( $c_{ij}$ ) while maintaining connectivity.

2. Greedy Activation and Routing

The paper proposes a marginal-value activation rule: an agent $i$ is invoked if and only if its expected marginal contribution to the coalition's value exceeds its activation cost ( $E[\Delta_i(C, x)] > c_i$ ).

Algorithm 1 (Greedy Router): A streaming algorithm that iteratively adds the agent with the highest positive marginal gain until no further agent satisfies the threshold.
Theoretical Guarantees: The author connects this to submodular set-function maximization.
- For cardinality-constrained, monotone cases, they cite a curvature-refined bound (Conforti and Cornuélols, 1984).
- For unconstrained, non-monotone cases (the actual setting of $U$ ), they present a tight $1/2$ -approximation guarantee via a "double-greedy" procedure (Algorithm 2, Buchbinder et al., 2015).
- Crucial Distinction: The author explicitly states that Algorithm 1 (the practical router) is a heuristic motivated by these bounds but does not strictly inherit their guarantees, as it is unconstrained and add-only.

3. Online Credit Assignment and Shapley Values

To determine fair credit and future routing probabilities, the paper proposes using Shapley values calculated on the net-utility game $U$ (not just quality $V$ ).

Predictive Routing: Unlike prior work that uses Shapley values only for post-hoc pricing, this framework uses estimated Shapley values ( $\hat{\phi}_{i,t}$ ) at routing time to decide whether to contact an agent.
Shapley–Submodularity Sandwich Bound: The author proves a theoretical bound showing that the gap between a raw marginal-value estimate (used by the greedy router) and the fair Shapley credit is bounded by a single per-agent "diminishing-returns" quantity, $\Gamma_i(x)$ . This provides a diagnostic for when the cheap greedy heuristic is a safe proxy for fair routing.

Key Contributions

Task-Conditioned Net-Utility Formulation: A unified objective function that jointly optimizes coalition selection, communication topology, and activation costs, separating coalition-level collaboration costs from individual agent activation costs.
Marginal-Value Activation Rule & Greedy Router: A practical algorithm (Algorithm 1) for selecting agents and a theoretical extension (Algorithm 2) with formal approximation guarantees for unconstrained, signed submodular maximization.
Predictive Shapley-Based Routing: An online mechanism that extends post-hoc credit assignment to real-time routing decisions, supported by a "sandwich bound" that quantifies the deviation between marginal estimates and fair Shapley credits.

Results

The paper validates the framework using a controlled synthetic simulation (500 tasks, 8 agents) rather than real-world LLM benchmarks, explicitly positioning this as a proof of concept for the optimization structure.

Utility Recovery: The greedy marginal-value router recovered 99.5% of the brute-force optimal utility.
Efficiency: It activated an average of 1.96 agents per task, compared to 8.00 for a full-broadcast baseline and 1.97 for the true optimum. The full broadcast achieved only 38.8% of the optimal utility due to redundancy and cost penalties.
Sensitivity Analysis:
- The method is robust to variations in activation costs and redundancy weights.
- Performance degrades significantly (to ~66% of optimal) when the submodularity assumption is violated (e.g., via pairwise synergy bonuses) or when value estimates are noisy. This aligns with the theoretical failure modes predicted by the paper.
Theoretical Bounds: The "Shapley–submodularity sandwich" bound held with zero violations across all tested agents, confirming that marginal contributions are bounded by the diminishing-returns gap.

Significance and Claims

The paper positions itself as a theoretical framework and controlled-simulation study, not a claim of validated improvement on real-world multi-agent LLM systems.

Narrow Novelty: The author claims novelty not in individual components (Shapley pricing, hedonic games, or graph pruning exist separately) but in the joint formulation that links coalition selection, communication costs, and predictive routing via a net-utility function, alongside the specific diagnostic bounds connecting marginal contributions to Shapley credits.
Honest Scope: The author explicitly acknowledges that the simulation is synthetic. They state that real-world validation requires a protocol (outlined in Section 10.2) involving real LLM benchmarks, learned quality estimators, and comparisons against existing learned routers (e.g., MasRouter).
Future Work: The paper identifies several open directions, including:
- Proving coalition stability (Core/Nash) for submodular games (noting that classical convex-game results do not transfer).
- Developing incentive-aligned mechanisms (VCG-style) for noisy, self-interested agents.
- Extending the framework to dynamic coalition formation where coalitions change during task execution via reinforcement learning.

In summary, the paper argues that "more agents and more messages do not automatically create more net intelligence." Its primary contribution is making the trade-off between marginal value and cost explicit and optimizable through cooperative game theory, providing a rigorous foundation for future empirical work in efficient agentic AI.