Interaction Structure and Dimensionality in Decentralized Problem Solving

Martin Allen and Marek Petrik and Shlomo Zilberstein. Interaction Structure and Dimensionality in Decentralized Problem Solving. Technical Report 08-11, Computer Science Department, University of Massachusetts Amherst, 2008.

Abstract

Decentralized Markov Decision Processes are a powerful general model of decentralized, cooperative multi-agent problem solving. The high complexity of the general problem leads to a focus on restricted models. While the worst-case hardness of such reduced problems is often better, less is known about the actual expected difficulty of given instances. We show tight connections between the structure of agent interactions and the essential dimensionality of various problems. Bounds can be placed on the difficulty of solving problems, based upon restrictions on the type and number of interactions between agents. These bounds arise from a bilinear programming formulation of the problem; from such a formulation, a more compact reduced form can be automatically generated, and the original problem can be rewritten to take advantage of the reduction. These results are of theoretical and practical importance, improving our understanding of multi-agent problem domains, and paving the way for methods that reduce the complexity of such problems by limiting the degree of interaction between agents.

Bibtex entry:

@techreport{APZtr0811,
  author	= {Martin Allen and Marek Petrik and Shlomo Zilberstein},
  title         = {Interaction Structure and Dimensionality in Decentralized
                   Problem Solving},
  year          = {2008},
  number        = {08-11},
  institution   = {Computer Science Department, University of Massachussetts Amherst},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/APZtr0811.html}
}

shlomo@cs.umass.edu