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 joint optimization problem) the agents can sometimes save costs compared to operating individually. A model of bounded rationality is adopted where 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 devised. The optimal coalition structure and its stability are significantly affected by the agents' algorithms' performance profiles and the cost of computation. This relationship is first analyzed theoretically. Then a domain classification including rational and bounded-rational agents is introduced. Experimental results are presented in vehicle routing with real data from five dispatch centers. This problem is NP-complete and the instances are so large that—with current technology—any agent's rationality is bounded by computational complexity.