A distributed constraint optimization problem
(DCOP) is a formalism that captures the rewards
and costs of local interactions within a team of
agents. Because complete algorithms to solve
DCOPs are unsuitable for some dynamic or anytime domains, researchers have explored incomplete DCOP algorithms that result in locally optimal solutions. One type of categorization of such
algorithms, and the solutions they produce, is koptimality; a k-optimal solution is one that cannot
be improved by any deviation by k or fewer agents.
This paper presents the first known guarantees on
solution quality for k-optimal solutions. The guarantees are independent of the costs and rewards in
the DCOP, and once computed can be used for any
DCOP of a given constraint graph structure.