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.