CAREER: Coalition Formation Among Self-Interested Computationally Limited Agents

该奖项支持开发高效的自动联盟形成方法的研究，这些方法的目标是在具有组合特征的固有分布式情况下运行-例如。任务和资源分配以及多智能体计划和调度。特别感兴趣的是这样的情况，即代理人有不同的目标，每个代理人都试图最大化自己的利益，而不考虑全局利益。研究的第一部分将先前关于有限理性下联盟形成的工作扩展到计算和通信限制的新模型。还将研究联盟的价值受非成员行动影响的更一般的设置。为此，将使用强大的新战略解决方案概念。还将进一步研究和解决多智能体系统中的有限理性悖论。工作的第二部分将探索联盟的形成，使用协议，包括建设性的多代理搜索，通过重新谈判迭代求精，通过解除注册进行回溯，并通过特定的更强大的协议类型避免局部最优。我们将探索一系列广泛的协议。还将分析具有本地审议算法的概率和条件性能配置文件的代理之间的合谋，以及可以通过显式协调其计算与其他代理的合谋。算法将被设计和测试，并应用于两个现实世界的问题：分布式车辆路径和多企业制造。

The award supports research into the development of efficient automated coalition formation methods that are targeted to operate in inherently distributed situations with combinatorial characteristics---e.g. task and resource allocation and multi- agent planning and scheduling. Of specific interest are situations in which agents have different goals and each agent is trying to maximize its own good without concern for the global good. The first part of the research extends prior work on coalition formation under bounded rationality to new models of computation and communication limitations. More general settings will also be studied in which a coalition's value is affected by nonmembers actions. For this, powerful new strategic solution concepts will be used. A paradox of bounded rationality in multi- agent systems also will be further studied and resolved. A second part of the work will explore coalition formation, using protocols that incorporate constructive multi-agent search, iterative refinement via renegotiation, backtracking via decommitting, and avoiding local optima via specific more powerful agreement types. A broad set of protocols will be explored. Collusion will also be analyzed among agents that have probabilistic, conditional performance profiles for their local deliberation algorithms, as well as agents that can gain by explicitly coordinating their computations with others. Algorithms will be designed and tested, and applied to two real- world problems: distributed vehicle routing and multi-enterprise manufacturing.