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

基于技能的智能体 AI 系统中的动态联盟形成与通信定价

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.

摘要： 现代智能体 AI 系统结合了多个具有异构技能的大型语言模型智能体，然而大多数架构要么预先固定通信方式，要么允许全广播。这两种方式都可能导致效率低下，因为 Token 成本、延迟、冗余和错误传播会随着活跃智能体数量和通信链路的增加而增加。

We model agent selection and communication as a cooperative game with task-conditioned net utility $U(C\mid x)=V(C\mid x)-\sum_{i\in C}c_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.

我们将智能体选择和通信建模为一个合作博弈，其任务条件净效用为 $U(C\mid x)=V(C\mid x)-\sum_{i\in C}c_i$，并将联盟层面的成本与智能体激活成本分离开来。我们提出了一种边际价值激活规则和贪婪路由算法，将模型扩展到通过每条边的成本来优化通信边，并利用估计的 Shapley 值来预测在执行前及执行过程中哪些智能体值得联系。

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.

我们将该问题与子模最大化（submodular maximization）联系起来，并证明了两个有限的保证：针对单调且基数受限的特殊情况的曲率细化界限，以及通过双重贪婪算法（double greedy）针对无约束非单调情况的紧凑 $1/2$ 近似（包含对有符号目标的修正）。这两个保证都不能直接应用于主路由算法，后者仍属于启发式方法。我们还证明了一个 Shapley-子模夹心界限，将边际价值路由的误差与每个智能体的边际收益递减量联系起来。

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.

在合成实验中，贪婪路由达到了暴力搜索最优效用的 $99.5%$，同时平均仅激活了 8 个智能体中的 1.96 个，而全广播方式仅达到 $38.8%$。该性能对激活成本和冗余权重具有鲁棒性，但在严重违反子模性或价值估计存在噪声的情况下会下降至 $66%$。我们将该框架与 Shapley 定价、享乐联盟形成和通信图剪枝进行了区分，并建议在真实的多智能体 LLM 基准测试中进行评估。