Coalition Formation among Bounded Rational Agents

Abstract

This paper analyzes coalition formation 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 worth solving the problems optimally: solution quality is decision-theoretically traded off against computation cost. A normative theory of coalitions among bounded rational (BR) agents is devised. The optimal coalition structure and its stability are significantly affected by the agents' algorithms' performance profiles (PPs) and the cost of computation. This relationship is first analyzed theoretically. A domain classification including rational and BR agents is introduced. Experimental results are presented in the distributed vehicle routing domain using real data from 5 dispatch centers; the optimal coalition structure for BR agents differs significantly from the one for rational agents. These problems are NP-complete and the instances are so large that, with current technology, any agent's rationality is bounded by computational complexity.