@conference {1506361,
	title = {Asynchronous Algorithms for Approximate Distributed Constraint Optimization with Quality Bounds },
	booktitle = {International Conference on Autonomous Agents and Multiagent Systems (AAMAS)},
	year = {2010},
	abstract = {Distributed Constraint Optimization (DCOP) is a popular framework for cooperative multi-agent decision making. DCOP is NPhard, so an important line of work focuses on developing fast incomplete solution algorithms for large-scale applications. One of
the few incomplete algorithms to provide bounds on solution quality is k-size optimality, which defines a local optimality criterion
based on the size of the group of deviating agents. Unfortunately,
the lack of a general-purpose algorithm and the commitment to
forming groups based solely on group size has limited the use of
k-size optimality.
This paper introduces t-distance optimality which departs from
k-size optimality by using graph distance as an alternative criteria
for selecting groups of deviating agents. This throws open a new research direction into the tradeoffs between different group selection
and coordination mechanisms for incomplete DCOP algorithms.
We derive theoretical quality bounds for t-distance optimality that
improve known bounds for k-size optimality. In addition, we develop a new efficient asynchronous local search algorithm for finding both k-size and t-distance optimal solutions {\textemdash} allowing these
concepts to be deployed in real applications. Indeed, empirical results show that this algorithm significantly outperforms the only existing algorithm for finding general k-size optimal solutions, which
is also synchronous. Finally, we compare the algorithmic performance of k-size and t-distance optimality using this algorithm. We
find that t-distance consistently converges to higher-quality solutions in the long run, but results are mixed on convergence speed;
we identify cases where k-size and t-distance converge faster.},
	author = {Kiekintveld, Christopher and Yin, Zhengyu and Kumar, Atul and Tambe, Milind}
}
