动态组建技能型智能体团队,智能分配沟通成本与角色。
Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems
- 用合作博弈建模智能体选组与通信,分离团队收益与激活开销。
- 贪心路由仅激活2个智能体却达99.5%最优性能,比全广播节省61%开销。
- 基于边际价值预判谁该参与,适合高成本、多智能体协作场景。
现代智能体型AI系统由具备异质技能的多个大语言模型智能体组成,但现有架构要么固定通信模式,要么允许全量广播,均易导致令牌开销、延迟、冗余和错误传播随活跃智能体与通信链路增加而上升。本文将智能体选择与通信建模为任务条件下的合作博弈,定义净效用 $U(Cig|x) = V(Cig|x) - igsum_{iigin C} c_i$,分离联盟级收益与个体激活成本。提出边际值激活规则与贪心路由算法,扩展模型以支持每条通信边的独立成本,并利用估计的Shapley值预测执行前/中哪些智能体值得联系。将问题关联至子模最大化,证明两类保证:单调、基数约束情形下的曲率修正界,以及无约束非单调情形下的紧致 $1/2$-近似(通过双贪心修正符号目标)。主路由仍为启发式方法,未获直接理论保证。进一步建立Shapley-子模夹逼界,关联边际值路由误差与个体递减回报量。合成实验显示,贪心路由在平均激活1.96个智能体(共8个)时达到99.5%的暴力最优效用,全广播则需激活3.88个;性能对激活成本和冗余权重稳健,但在严重违背子模性或噪声估值下降至66%。区分本框架与Shapley定价、享乐型联盟形成及通信图剪枝,主张在真实多智能体LLM基准上评估。
原文摘要 · Abstract (English)
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\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. 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。