The authors present a model of dynamic coalition formation in multiagent systems for solving combinatorial optimization problems by coordinating the actions of the agents.

The model involves self-interested agents and bounded-rational agents. A domain-independent theory of normative coalition formation is proposed in which the bounded rationality is considered by minimizing both the solution cost and the computation cost. The theory also incorporates a second form of bounded rationality: solution quality is traded off against computational costs by using anytime algorithms (in the form of design-to-time algorithms) to refine the solution. Based on this theory, the authors analyze optimal coalition structures, coalition stability, and how the structures and stability are affected by the algorithms’ performance profiles (in terms of domain cost achievable as a function of allocated resources) and computation costs.

Experimental results in vehicle routing are presented, including real data from five dispatch centers. The authors interpret the results by giving plausible explanations for the achieved optimal coalitions.

The paper is recommended for researchers in multiagent systems, game theory, and economics. Although normative coalition formation has been widely studied in game theory, the proposed approach considers the limited deduction capability of agents, analyzes its implications, and achieves an application-independent domain classification for bounded-rational agents. The example routing problem clarifies the ideas.