Search CALO Publications:

Author and Title
Quality Guarantees on Locally Optimal Solutions for Distributed Constraint Optimization Problems. Jonathan P. Pearce and Milind Tambe.

Abstract
A distributed constraint optimization problem (DCOP) is a formalism that captures the rewards and costs of local interactions within a team of agents, each of whom is choosing an individual action. Because complete algorithms to solve DCOPs are not suitable for some dynamic or anytime domains, researchers have explored incomplete DCOP algorithms that result in a locally optimal solution. One metric for categorization of such algorithms, and the solutions they produce, is k-optimality; a k-optimal DCOP 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. These guarantees are independent of the actual costs and rewards in the DCOP, and once computed can be used for any DCOP of a given graph (or hypergraph) structure in order to determine properties of the worst-case k-optimal solution for a given value of k.We provide both a mathematical proof of the soundness and experimental analysis of the tightness of the guarantees.

Download