Publication - Coalitions Among Computationally Bounded Agents

Authors: Sandholm, Tuomas; and Lesser, Victor
Title: Coalitions Among Computationally Bounded Agents
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 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.
Keywords: Coalition Formation, Coordination, Organizational Design, Self-Interested Negotiation
Publication: Artificial Intelligence, Special Issue on Economic Principles of Multi-Agent Systems, Vol: 94, Num: 1, pp. 99 - 137
Date: January 1997
Sources: PS: /Documents/Sandholm/coalitions_97.ps
PDF: /Documents/coalitions_97.pdf
Reference: Sandholm, Tuomas; and Lesser, Victor. Coalitions Among Computationally Bounded Agents. Artificial Intelligence, Special Issue on Economic Principles of Multi-Agent Systems, Volume 94, Number 1, pp. 99-137. January 1997.
bibtex: 
@article{Sandholm-97,
  author    = "Tuomas Sandholm and Victor Lesser",
  title     = "{Coalitions Among Computationally Bounded Agents}",
  journal   = "Artificial Intelligence, Special Issue on Economic
               Principles of Multi-Agent Systems",
  volume    = "94",
  number    = "1",
  pages     = "99-137",
  month     = "January",
  year      = "1997",
  url       = "http://mas.cs.umass.edu/paper/97",
}