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

arXiv:2608.07532 · cs.AI, cs.LG, econ.TH · Submitted 2026-07-24 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems".

Jane: The paper was written by Mojtaba Eslami from University of Calgary.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title: Tom: Welcome back to the arXiv channel, everyone. I'm Tom, and alongside me is the brilliant Jane. We've got a paper that's been making waves in the multi-agent AI world, and the title alone is a mouthful: "Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems."

Jane: Tom, I love this title because every single word is doing work. "Coalition formation" — that's the idea that you don't need every AI agent working on every task. "Communication pricing" — that's the radical part, actually putting a cost on agents talking to each other. And "skill-based" — that's the key, because not every agent is good at everything.

Tom: Right, and that's what got me hooked. The authors are essentially saying that the way we build multi-agent systems right now is backwards. We either hard-code who talks to whom, or we let every agent broadcast to every other agent. Both are wasteful.

Jane: Exactly. And the title signals that they want to treat this like an economic problem. You don't hire every contractor in town to build a house; you hire the electrician, the plumber, and the carpenter who actually add value. Same logic here.

Tom: So the implication is that we should be asking, "Does this agent earn its keep for this specific task?" Not, "Let's spin up all eight agents because we have them."

Jane: And that's a huge shift. The paper's framing suggests that more agents and more messages don't automatically mean better results. Sometimes they mean worse results, because you're paying for latency, you're paying for token costs, and you're paying for the risk that one agent's hallucination poisons everyone else's context.

Tom: It's almost like a management problem. You've got a team of specialists, and you need to decide who's on the field for this particular play.

Jane: That's the coalition part. And the communication pricing part is about the edges between them — who needs to be in the room, who can work independently, and who would just be noise.

Tom: I think the biggest implication here is that this could change how we design agentic systems from the ground up. Instead of building bigger and bigger architectures, we build smarter selection mechanisms.

Jane: And that's what we're going to dig into. Next segment, we're going to look at the actual summary of the paper and see how they propose to solve this problem. Stick around.

Summary: Tom: We're back, and we're still on "Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems." Jane, give us the elevator pitch. What's this paper actually trying to do?

Jane: So the core idea is a utility function. They define a net utility for any coalition of agents working on a task. It's the value the coalition produces, minus the costs. And the costs include things like latency, hallucination risk, redundancy, and then a separate per-agent activation cost for the token and compute.

Tom: So it's not just about quality. It's about quality minus everything you have to pay to get it.

Jane: Precisely. And then they say, the optimal coalition is the one that maximizes that net utility. Not the one with the most agents, not the one with the best single agent, but the one where the marginal benefit of adding each agent actually exceeds the marginal cost.

Tom: And that's where the greedy router comes in. They have this algorithm that starts with an empty coalition and keeps adding the agent with the highest marginal value, as long as that value is greater than the agent's cost.

Jane: Right. And the beautiful thing is, they connect this to submodular optimization. That's a fancy term for diminishing returns. Adding a second verifier agent when you already have one verifier gives you less value than adding the first one did.

Tom: So the math says, "Stop adding agents when the returns diminish below the cost."

Jane: Exactly. And they prove some nice bounds. For the unconstrained case, there's a double-greedy algorithm that gets you within half of the optimal value. And they have a curvature-based bound for the constrained case that's tighter than the classical result.

Tom: But here's what I find most exciting — they don't just stop at selecting agents. They also treat communication edges as decision variables. You don't just decide who's in the coalition; you decide who talks to whom.

Jane: And that's the "communication pricing" part of the title. Each edge has a cost, and you only keep the edges where the marginal value of the connection exceeds the cost of the connection.

Tom: So you could have a coalition of four agents where only three edges are active, because the fourth edge just isn't worth it.

Jane: Exactly. And their simulation shows this works. Greedy routing gets ninety-nine point five percent of the brute-force optimal utility while using fewer than two agents on average, versus eight for full broadcast. That's a massive efficiency gain.

Tom: And that's the headline number, but as we'll see in a later segment, the sensitivity analysis is where the real story is. But first, let's talk about what improvements this paper suggests over the status quo. That's next.

Improvements: Tom: Welcome back. We're deep in "Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems." Jane, what's the big improvement this paper is pushing for?

Jane: The biggest improvement is moving from static, hand-designed architectures to dynamic, cost-aware selection. Right now, if you build a multi-agent system, you decide upfront who the planner is, who the coder is, who the critic is, and you wire them together in a fixed graph.

Tom: And that's like designing a company org chart and never changing it, regardless of the project.

Jane: Exactly. This paper says, no, the coalition should change with every task. A simple writing task might only need one agent. A research task might need a planner, a searcher, and a critic. A deployment task might need a coder, a verifier, and a security auditor.

Tom: So the architecture becomes a function of the task, not a fixed template.

Jane: And the second improvement is treating communication as a cost, not a free resource. In most systems, agents just broadcast to everyone. This paper says every edge has a price, and you should only pay for edges that earn their keep.

Tom: That's a really practical improvement. Token costs are real money, and latency is real time.

Jane: And there's a third improvement that I think is the most intellectually interesting: using Shapley values for online routing. Shapley values are a way to fairly assign credit to each agent for the final outcome. Normally, you compute them after the task is done, to figure out who deserves what.

Tom: But this paper says, let's estimate them before and during the task, and use them to decide who to contact next.

Jane: Right. So instead of just settling accounts after the fact, you're using the predicted fair credit as a routing signal. If an agent is predicted to have a high Shapley value for this task, you contact them. If not, you don't.

Tom: And they prove a bound that connects these predicted marginal values to the actual Shapley credit. It's called the Shapley–submodularity sandwich.

Jane: It's a guarantee that the gap between your routing estimate and the fair credit is bounded by a per-agent quantity that measures how much diminishing returns that agent experiences. If an agent has low overlap with others, the gap is small, and your cheap greedy router is a safe bet.

Tom: So the improvement is not just "be more efficient." It's "be more efficient and be fair about it."

Jane: And that fairness matters, because if you're running a marketplace where agents are owned by different providers, you need to know who's actually contributing so you can pay them appropriately.

Tom: Great point. And that's a natural segue into the first page of the paper, where they lay out the core contributions. Let's look at that next.

First Page: Tom: We're back on the arXiv channel, still talking about "Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems." Jane, let's go back to the very first page. What are the core contributions the authors claim?

Jane: The first contribution is the task-conditioned net-utility formulation. That's the equation that separates coalition value — quality net of latency, risk, and redundancy — from per-agent activation cost. The point is to account for token and compute cost exactly once, not double-count it.

Tom: And that's a subtle but important accounting point. If you put token cost inside the value function and then also subtract it as an activation cost, you're penalizing agents twice.

Jane: Exactly. They're very careful about that. The second contribution is the marginal-value activation rule and the greedy router. That's Algorithm one in the paper. It's the practical tool that decides which agents to invoke.

Tom: And the third contribution is the online Shapley-based routing mechanism. That's the predictive part — using estimated Shapley values to decide who to contact before and during execution, not just after.

Jane: And they wrap it all together with two approximation guarantees. One is a curvature-refined bound for the constrained, monotone case. The other is a tight half-approximation for the unconstrained, non-monotone case via double-greedy.

Tom: But I noticed they're very careful to say that neither guarantee applies directly to their main router. It's presented as a heuristic motivated by the bounds, not proven by them.

Jane: That's intellectual honesty, and I appreciate it. They're not overclaiming. They say, "Here's the theory, here's the heuristic, and here's a simulation showing it works well in practice."

Tom: And the simulation is where the rubber meets the road. They show that greedy routing recovers ninety-nine point five percent of the brute-force optimal utility while using on average one point nine six agents out of eight candidates. Full broadcast only gets thirty-eight point eight percent of optimal utility.

Jane: So full broadcast is not just wasteful — it's actively bad. It's subtracting value through redundancy and cost.

Tom: And then the sensitivity analysis shows that this result is robust to activation cost and redundancy weight, but degrades when submodularity is violated or value estimates are noisy.

Jane: Which is exactly what the theory predicts. Greedy works when the value function has diminishing returns and when you can estimate value accurately. If either of those fails, performance drops.

Tom: So the first page sets up a really clean framework: a utility function, a greedy router, a Shapley-based credit mechanism, and honest bounds. That's a solid foundation.

Jane: And it's a foundation that could support a lot of future work. Which is exactly what we're going to talk about in our conclusion. Stay with us.

Conclusion: Tom: We're wrapping up our discussion of "Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems." Jane, give us the final take.

Jane: The core message is that agentic AI systems should treat every agent activation and every communication edge as an economic decision. You activate an agent only when its expected marginal value exceeds its cost. You open a communication channel only when the marginal value of the connection exceeds the cost of the connection.

Tom: And the paper backs this up with a clean mathematical framework, two formal approximation guarantees, and a synthetic simulation showing that a simple greedy heuristic gets within zero point five percent of the brute-force optimum while using a quarter of the agents.

Jane: But the authors are also honest about the limitations. The simulation is synthetic. The guarantees assume submodularity. The real-world validation is left to a follow-up protocol that they outline.

Tom: And that protocol is actually really well thought out. They propose using SWE-bench for coding tasks, multi-hop QA for retrieval tasks, and comparing against baselines like MasRouter and AgentPrune.

Jane: Right. And they want to measure not just task success, but token cost, latency, and the correlation between predicted and realized Shapley values.

Tom: So the impact of this paper, if it holds up in real-world validation, is that we stop building bigger and bigger agent architectures and start building smarter selection mechanisms.

Jane: And that could save real money, real time, and real frustration. Every token you don't spend is a token you keep. Every message you don't send is latency you avoid.

Tom: And the fairness angle is important too. If you're running a marketplace of agents, you need to know who's actually contributing. Shapley-based credit assignment gives you that.

Jane: So we're saying goodbye to this paper, but we're excited about the direction it points. Dynamic, cost-aware, fair agent orchestration is the future.

Tom: And with that, we're ready to move on to the next paper. Thanks for listening, everyone. This has been Tom and Jane on the arXiv channel, and we'll see you in the next episode.

Mojtaba Eslami

University of Calgary

cs.AI, cs.LG, econ.TH

Submitted: 2026-07-24

Updated: 2026-08-11

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 58/100

The gist: over-activation (invoking every available skill regardless of quality gain) and over-communication (fixed, dense communication topologies that do not adapt to marginal informativeness).

Key concepts

Coalition Formation
The idea that complex tasks do not require every AI agent working on every aspect. Instead, a system should select only the necessary specialists (e.g., plumber, electrician) who add specific value to the task.
Communication Pricing
Treating communication edges between agents as having a cost. Systems should only maintain connections where the marginal value of talking exceeds the cost of sending messages, preventing wasteful broadcasting.
Net Utility
A metric used to determine if an agent or connection is worthwhile. It is calculated by subtracting all associated costs (like latency, token costs, and hallucination risk) from the total value produced by a group of agents.
Shapley Values
A method for fairly assigning credit to each agent for a final outcome. The paper suggests using predicted Shapley values during the task to decide which agents should be contacted next.

Terminology

Summary

Summary

The paper formalizes agent coalition formation and inter-agent communication in agentic AI systems as a cooperative game with a task-conditioned net-utility function. The central claim is that an agent should be activated, and a communication edge should be used, only when the expected marginal value it creates for the task exceeds its computational, latency, privacy, and error-propagation cost. The paper addresses two failure modes: over-activation (invoking every available skill regardless of quality gain) and over-communication (fixed, dense communication topologies that do not adapt to marginal informativeness).

The core formulation defines a characteristic function V(times x): 2 N to R for a set of candidate agents N and task x, given by V(C x) = E[Q(C,x) - lambda 2 L(C,x) - lambda 3 R(C,x) - lambda 4 D(C,x)], where Q is task-success quality, L is latency, R is risk of hallucination/failure/unsafe action, and D is duplicated work or redundant communication. The per-agent activation cost c i is kept out of V and applied exactly once via the full net utility U(C x) = V(C x) - sum i in C c i. The coalition-selection problem is C*(x) = C N [V(C x) - sum i in C c i].

The paper extends this to treat communication edges as decision variables: C N, G C [U(C, G C x) - sum i,j in E C c ij], where G C = (C, E C) is the communication network restricted to C and c ij is the cost of the communication channel between agents i and j. A worked example shows a task-conditioned optimizer selecting different coalitions and sparse, task-specific communication graphs for three tasks (simple writing, factual research, software deployment), contrasted with the grand coalition fully connected with 10 edges for every task.

The paper proposes a marginal-value activation rule: agent i should be invoked if and only if E[i(C, x)] > c i, where i(C, x) = V(C i x) - V(C x). Algorithm 1 (Greedy marginal-value coalition router) implements this by iteratively adding the agent with the highest marginal gain in V if that gain exceeds the activation cost. The paper establishes the equivalence i V(C, x) > c i i U(C, x) > 0, and states that Algorithm 1 scores U, not V alone.

The paper provides two formally correct approximation guarantees. Proposition 1 (curvature-refined greedy bound) states that if Q(times, x) is monotone submodular with curvature alpha Q, greedy selection under a cardinality constraint C at most k achieves Q(C greedy, x) at least 1 over alpha Q(1 - e-alpha Q) Q(C k*, x), recovering the classical (1 - 1/e) guarantee at alpha Q = 1 and improving to 1 as alpha Q to 0. Proposition 2 (tight unconstrained bound) states that if U(times x): 2 N to R at least 0 is submodular and non-negative, Algorithm 2 (randomized double-greedy) returns a coalition C with E[U(C x)] at least 1 over 2 U(C* x), and no polynomial-query algorithm can guarantee a better ratio. Corollary 1 extends this to signed objectives via a shift argument, yielding E[U(C x)] at least 1 over 2 U(C* x) + 1 over 2 m where m = C N U(C x), explicitly noted as primarily an analytical device rather than a practical algorithm because computing m is itself combinatorial and the bound can be vacuous when m is substantially negative. The paper is explicit that neither guarantee applies directly to Algorithm 1, which is presented as a heuristic motivated by, but not proven equal to, these bounds.

For online credit assignment, the paper proposes using predicted Shapley values i,t(U) estimated from features available at routing time to decide whether to contact agent i at stage t: P(i contacted at time t) = sigma(i,t(U)), where sigma is a monotone squashing function centered so sigma(0) = 1 over 2. The Shapley value is computed on the full net-utility game U, not V, so credit already accounts for activation cost. Proposition 3 (Shapley–submodularity sandwich) proves that if U(times x) is submodular, then for every agent i and every coalition C with i C, U(N x) - U(N i x) at most i U(C, x) at most U(i x) - U(x), and the Shapley value itself satisfies the same sandwich. Corollary 2 defines the diminishing-returns gap i(x) = [U(i x) - U(x)] - [U(N x) - U(N i x)] at least 0 and proves i U(C, x) - phi i(U) at most i(x), bounding the gap between any marginal-value routing estimate and fair Shapley credit in terms of a single per-agent quantity.

The paper discusses coalition stability via core, Nash-stable, and pairwise-stability concepts from hedonic game theory, but explicitly notes that the classical Shapley-in-the-core theorem does not transfer because the framework assumes submodularity (diminishing returns) rather than the supermodularity (increasing returns) that theorem requires. The only case where core stability is immediate is the degenerate modular case where U(C) = sum i in C U(i) for every C. The paper sketches a VCG-style incentive alignment target but does not claim the idealized guarantee transfers to noisy, estimated Shapley-based contributions. A dynamic extension using multi-agent reinforcement learning is flagged as future work.

The controlled synthetic simulation uses N = 8 candidate agents with competence vectors over K = 6 latent skill dimensions, 500 synthetic tasks with random skill-demand vectors, coalition quality Q(C, x) = 1 - (-2.2 times coverage(C, x)), redundancy term lambda 4 D(C, x) = 0.16 times 2 / 2, and uniform activation cost c i = 0.05. Results show greedy marginal-value routing recovers 99.5% of brute-force-optimal utility while activating on average 1.96 of 8 candidate agents, versus 38.8% of optimal utility for full broadcast (which activates all 8 agents). The greedy router selects the exact brute-force-optimal coalition on 74.0% of tasks. Exact Shapley values agree with Monte Carlo estimates (3,000 random-permutation samples) to within 0.005 for every agent (mean absolute error 0.0028, max 0.0046). The sandwich bound held with zero violations across all 8 tested agents, with realized gaps ranging from 0.014 to 0.496 against bounds ranging from 0.463 to 0.653.

The sensitivity analysis sweeps five parameters (holding 500 → 200 tasks per setting). Three parameters — skill overlap, activation cost, and redundancy weight — leave greedy performance essentially unchanged (all ≥ 99.5% of optimal). The two informative failure modes are: (a) injecting a pairwise synergy bonus that violates submodularity degrades performance from 99.6% to as low as 66–70% of optimal; (b) adding noise to value estimates degrades performance smoothly from 99.5% at zero noise to 79.2% at noise standard deviation 0.4, with exact-match rate with the optimum collapsing much faster (87.5% → 3.5%) than utility. The paper states these two sweeps are the more informative characterization of the method than the single headline number.

The paper explicitly limits its claims: the simulation is "a synthetic, controlled instantiation of the framework – it demonstrates that the optimization problem we pose is well behaved and that a cheap greedy heuristic is competitive with the true optimum under conditions the sensitivity analysis makes explicit, not that the framework improves real LLM agent pipelines." It proposes a concrete empirical validation protocol using real multi-agent LLM benchmarks (SWE-bench-style software engineering tasks and multi-hop question answering), with baselines including fixed dense-communication, fixed hand-designed pipeline, MasRouter, and AgentPrune-style edge pruning, and metrics including task success rate, total token cost, wall-clock latency, and correlation between predicted and realized Shapley values. The paper concludes: More agents, and more messages, do not automatically create more net intelligence; the goal of this framework is to make that trade-off explicit and optimizable.

Improvements for AI systems

Based on the paper, here are the specific improvements I can implement in an AI system, along with what the improved system can do:

  • Implementation: Add a pre-execution module that evaluates each candidate agent's expected marginal contribution Δi(C, x) = V(C ∪ i x) − V(C x) against its activation cost ci, and only activates agents where Δi > ci.

  • What it does: The system automatically decides which specialized agents (planner, coder, critic, retriever) to invoke for a given task, rather than activating all available agents. It stops adding agents once no marginal gain clears the cost threshold.

  • Implementation: Treat each communication channel i,j as a decision variable with cost ciⱼ. The system evaluates whether establishing a channel between two agents yields net utility U(C, G C x) − Σciⱼ > 0 before connecting them.

  • What it does: The system builds sparse, task-specific communication topologies (e.g., planner-coordinated star graphs) instead of fully-connected broadcast networks, reducing token cost and error propagation.

  • Implementation: Train a lightweight predictor ϕ̂i,t(U) that estimates each agent's Shapley value in the net-utility game (already net of activation cost) from task embeddings, agent track records, and partial coalition state. Use this to set contact probability: P(i contacted at time t) = σ(ϕ̂i,t(U)).

  • What it does: The system predicts which agents will be most valuable before and during execution, not just after. It can route to a high-value critic early, or skip a redundant verifier, based on predicted fair credit rather than raw marginal value alone.

  • Implementation: Compute the curvature α Q of the quality function (Equation 7) from historical data, and use it to decide between Algorithm 1 (add-only greedy) and Algorithm 2 (double-greedy with add/remove). If α̂ Q is close to 1 (high skill overlap), switch to the double-greedy fallback.

  • What it does: The system adapts its selection strategy based on measured redundancy in the agent pool, avoiding the worst-case performance degradation when agents are highly overlapping.

  • Implementation: For each agent, compute the diminishing-returns gap Γi(x) = [U(i) − U(∅)] − [U(N) − U(Ni)]. Log the sum ΣiΓi(x) per task family.

  • What it does: The system flags when its greedy routing is likely to deviate from Shapley-fair credit assignment. If ΣiΓi(x) is large, it switches to more expensive but fairer Shapley-based routing; if small, it trusts the cheap marginal-value rule.

  • Implementation: When value estimates are noisy (standard deviation σ), widen the activation threshold from Δi > ci to Δi > ci + κσ where κ is a safety margin (e.g., 1.5). This prevents near-tie decisions from flipping due to estimation error.

  • What it does: The system avoids activating agents whose marginal value is only marginally above cost when estimates are uncertain, preserving utility under noisy conditions (the paper shows utility degrades from 99.5% to 79.2% at σ=0.4 without this safeguard).

  • Reduce token/compute cost by 75%: Activates on average 1.96 of 8 candidate agents instead of all 8, while recovering 99.5% of optimal utility (vs. 38.8% for full broadcast).

  • Adapt communication topology per task: Automatically builds sparse graphs (e.g., coordinator-centric) rather than dense all-to-all connections, cutting communication overhead.

  • Route agents predictively: Uses pre-task and mid-task Shapley estimates to contact high-value agents early and skip redundant ones, improving both efficiency and fairness of credit assignment.

  • Self-diagnose failure modes: Monitors submodularity violations and estimation noise, and switches strategies (e.g., to double-greedy or wider thresholds) before performance collapses.

  • Provide interpretable credit allocation: Each agent receives a Shapley value in the net-utility game, so expensive but high-quality agents are credited fairly net of their own cost, enabling transparent reward distribution across providers.

The system is particularly effective for heterogeneous agent pools (planner/coder/critic/security) on tasks with varying skill demands, where it avoids both over-activation and over-communication.

Abstract

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(C x)=V(C x)-sum i in Cc i, 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.

Sources

Related papers