Distributed Multi-Criteria Coordination: Privacy vs. Efficiency
Emma Bowring, Milind Tambe and Makoto Yokoo
Abstract
Distributed constraint optimization (DCOP) has emerged as a
key technique for multiagent coordination. Unfortunately, while previous
work in DCOP focuses on optimizing a single team objective, domains often
require satisfying additional criteria. This paper provides a novel multi-criteria
DCOP algorithm, based on two key ideas: (i) transforming multi-criteria problems
via virtual variables to harness single-criterion DCOP algorithms; (ii) revealing
bounds on criteria to neighbors. These ideas result in interleaved multi-criteria
searches, illustrated by modifying Adopt, one of the most efficient DCOP
algorithms. Our Multi-Criteria Adopt al-gorithm (MCA) tailors its performance
to whether individual constraints are to be kept private or exploited for
efficiency.