COALITIONS AMONG COMPUTATIONALLY BOUNDED AGENTS

This paper analyzes coalitions among self-interested agents that need to solve combinatorial optimization problems to operate efficiently in the world. By colluding (coordinating their actions by solving a join t optimization problem) the agents can sometimes save costs compared t o operating individually. A model of bounded rationality is adopted wh ere computation resources are costly. It is not worthwhile solving the problems optimally: solution quality is decision-theoretically traded off against computation cost, A normative, application- and protocol- independent theory of coalitions among bounded-rational agents is devi sed. The optimal coalition structure and its stability are significant ly affected by the agents' algorithms' performance profiles and the co st of computation, This relationship is first analyzed theoretically, Then a domain classification including rational and bounded-rational a gents is introduced, Experimental results are presented in vehicle rou ting with real data from five dispatch centers. This problem is NP-com plete and the instances are so large that-with current technology-any agent's rationality is bounded by computational complexity. (C) 1997 E lsevier Science B.V.