@magazinearticle {1508523,
title = {Solving multiagent networks using distributed constraint optimization },
journal = {AI Magazine},
volume = {29},
number = {3},
year = {2008},
pages = {47-66},
abstract = {In many cooperative multiagent domains, the effect of local
interactions between agents can be compactly represented as
a network structure. Given that agents are spread across such
a network, agents directly interact only with a small group
of neighbors. A distributed constraint optimization problem
(DCOP) is a useful framework to reason about such networks
of agents. Given agents{\textquoteright} inability to communicate and collaborate in large groups in such networks, we focus on an
approach called k-optimality for solving DCOPs. In this approach, agents form groups of one or more agents until no
group of k or fewer agents can possibly improve the DCOP
solution; we define this type of local optimum, and any algorithm guaranteed to reach such a local optimum, as k-optimal.
The article provides an overview of three key results related
to k-optimality. The first set of results are worst-case guarantees on the solution quality of k-optima in a DCOP. These
guarantees can help determine an appropriate k-optimal algorithm, or possibly an appropriate constraint graph structure,
for agents to use in situations where the cost of coordination
between agents must be weighed against the quality of the
solution reached. The second set of results are upper bounds
on the number of k-optima that can exist in a DCOP. These
results are useful in domains where a DCOP must generate a
set of solutions rather than single solution. Finally, we sketch
algorithms for k-optimality and provide some experimental
results for 1-, 2- and 3-optimal algorithms for several types
of DCOPs.},
author = {Jonathan P. Pearce and Tambe, Milind and Rajiv T. Maheswaran}
}