Publication - Agent Interaction in Distributed MDPs and its Implications on Complexity

Authors: Shen, Jiaying; Becker, Raphen; and Lesser, Victor
Title: Agent Interaction in Distributed MDPs and its Implications on Complexity
Abstract: The ability to coordinate effectively is critical for agents to accomplish their goals in a multi-agent system. A number of researchers have modeled the coordination problem for multi-agent systems using decision theory. The most general models have proven to be extremely complex to solve optimally (NEXP-complete). Some of the more restricted models have been much more tractable, though still difficult (NP-complete). What is missing is an understanding about why some models are much easier than others. This work fills this gap by providing a condition that distinguishes between problems in NP and those strictly harder than NP. This condition is whether the information contained in the history of interaction between the agents can be represented by a mapping that is polynomial in the number of states. We also show that the class of problems that satisfy this condition is NP-complete. We illustrate this condition by showing two interaction protocols in which the interaction history is polynomial. We give two examples of problems that do not satisfy this condition and demonstrate how this theoretical result can be used to generate an NP approximation of the original problem.
Keywords: Agent Control, Communication, Communication Protocol, Coordination, Distributed MDP, Multi-Agent Systems
Publication: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems, pp. 529 - 536
Location: Japan
Publisher: ACM
Date: 2006
Sources: HTML: http://mas.cs.umass.edu/~jyshen/papers/aamas06-pe.pdf
Reference: Shen, Jiaying; Becker, Raphen; and Lesser, Victor. Agent Interaction in Distributed MDPs and its Implications on Complexity. Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems, ACM, pp. 529-536. 2006.
bibtex: 
@inproceedings{Shen-405,
  author    = "Jiaying Shen and Raphen Becker and Victor Lesser",
  title     = "{Agent Interaction in Distributed MDPs and its
               Implications on Complexity}",
  booktitle = "Proceedings of the Fifth International Joint
               Conference on Autonomous Agents and Multi-Agent
               Systems",
  publisher = "ACM",
  pages     = "529-536",
  year      = "2006",
  address   = "Japan",
  url       = "http://mas.cs.umass.edu/paper/405",
}