多智能体合约

《Journal of the ACM》：Multi-Agent Contracts

研究单主多智能体合同设计问题，核心为补集自由层级下的奖励函数。提出常数因子近似算法，适用于子模态和XOS函数，并证明子模态最佳近似比为常数，子可加性函数存在Ω(√n)近似不可能性。

　　

摘要AI摘要

要查看此由AI生成的摘要，您必须具有高级访问权限。

了解更多登录

摘要

摘要

我们研究了一个自然组合型的单一主体多代理人合同设计问题，在这个问题中，主体激励一组代理人为完成特定任务而付出努力。我们模型的核心是一个奖励函数，它将代理人的努力与主体预期的奖励相对应。我们致力于设计计算效率高的算法，以找到属于无互补层次结构的奖励函数的最优（或接近最优）线性合同。

我们的第一个主要结果为次模和XOS奖励函数提供了常数因子近似算法，这些算法分别依赖于价值预言机（对于次模奖励函数）以及价值和需求预言机（对于XOS奖励函数）。该算法创造性地使用了“价格”和（近似的）需求查询来选择主体应与之签订合同的代理人集合，并利用了XOS函数及其边际的新颖缩放属性，这些属性可能具有独立的学术价值。

作为我们的第二个主要结果，我们证明了即使使用价值和需求预言机，对于次模奖励函数，我们也只能获得常数因子近似。对于更大的次加性奖励函数类别，我们在有n个代理人的情况下证明了\(\Omega (\sqrt {n})\)的不可能性。这一不可能性的显著特点是，它也适用于那些与次模函数仅有常数因子差异的次加性函数。这种快速的性能下降与以往的文献结果形成鲜明对比，例如在组合拍卖领域，近似保证的性能下降通常更为平缓。

AI摘要

AI生成的摘要（实验性）

此摘要是由自动化工具生成的，并非由文章作者撰写或审核的。它旨在帮助发现新知识、帮助读者评估文章的相关性，并协助来自相关研究领域的读者理解本文内容。它旨在补充作者提供的摘要，后者仍然是论文的官方总结。完整文章才是权威版本。点击此处了解更多。

点击此处对摘要的准确性、清晰度和实用性进行评论。您的反馈将有助于改进未来的版本。

要查看此由AI生成的通俗语言摘要，您必须具有高级访问权限。