CAREER: Coalition Formation Among Self-Interested Computationally Limited Agents

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.