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

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.