Abstract
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 worth solving the problems optimally: solution quality is decision-theoretically traded off against computation cost. A normative, protocol-independent 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 unit 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.
Introduction
In classical cooperative game theory, the assumption of superadditivity suggests that "more is better." If a group of agents joins forces, they can—at worst—do exactly what they did separately, and at best, find synergies to reduce costs. However, this assumes agents are perfectly rational, possessing infinite, cost-free computational power to solve complex, NP-complete optimization problems instantly.
In reality, solving these problems takes CPU time, which translates to financial cost or operational delays. This paper by Sandholm and Lesser (1995) introduces a framework for Bounded Rational (BR) agents, where computation is a scarce, costly resource. The central question is: How does the cost of computation change which coalitions form, whether they are stable, and how they should divide their profits?
Theoretical Framework
The authors propose a model for BR agents based on two primary pillars:
- Performance Profiles (PPs): Instead of a single optimal solution, agents utilize algorithms where solution quality improves over time. A PP maps computation time ($r_s$) to the expected cost of the solution ($c_s(r_s)$).
- Cost of Deliberation: A fixed cost ($c_{Comp}$) per unit of CPU time is introduced. The value of a coalition is defined as the solution quality minus the cost of the computation required to find it.
From these pillars, the authors redefine game-theoretic concepts. BR-Superadditivity posits that a coalition is only worth forming if the combined optimization gain outweighs the extra computation cost of solving a larger, more complex problem. The Bounded Rational Core (BRC) represents payoff distributions where no sub-group has an incentive to break away, specifically accounting for the costs of their own limited "thinking" power.
Domain Classification
The paper introduces a formal classification of game domains to distinguish between classical rational agents and bounded rational agents. This taxonomy helps identify which game-theoretic properties (like the existence of a stable core) hold under different computational constraints.
Experimental Evaluation: Distributed Vehicle Routing
The theory was evaluated using a Distributed Vehicle Routing (DVR) domain with real-world data from five dispatch centers, involving 771 deliveries and 77 vehicles. Because the underlying problem is NP-hard and the instances are large, finding a truly optimal solution is computationally impossible, making it an ideal testbed for bounded rationality.
Key Insights
- The "Grand Coalition" is Not Guaranteed: While traditional theory often favors all agents working together, for BR agents, the grand coalition might be so complex to optimize that computation costs exceed the savings.
- Computation Promotes Fragmentation: As the unit cost of computation ($c_{Comp}$) increases, the optimal coalition structure shifts toward smaller groups. High costs make it more efficient to solve several small problems than one massive one.
- Stability is Cost-Dependent: A coalition structure stable when computation is cheap may become unstable if computation costs rise, as subgroups find better net returns by solving simpler problems independently.
Results and Conclusion
Empirical results in the vehicle routing domain showed that the optimal coalition structure for BR agents differed significantly from classical predictions. Notably, none of the games exhibited BR-superadditivity; the grand coalition was never the best choice when computation costs were factored in. Furthermore, the most effective coalitions for BR agents typically consisted of geographically close dispatch centers, aligning strategic domain knowledge with computational efficiency. This research highlights that for agents with limited resources, the "best" way to cooperate is fundamentally tied to the cost of thinking.
Summary updated