@conference {1506764,
	title = {Sensitivity analysis for distributed optimization with resource constraints },
	booktitle = {The Eighth International Conference on Autonomous Agents and Multiagent Systems},
	year = {2009},
	abstract = {Previous work in multiagent coordination has addressed the challenge of planning in domains where agents must optimize a global
goal, while satisfying local resource constraints. However, the imposition of resource constraints naturally raises the question of whether the agents could significantly improve their team performance
if a few more resources were made available. Sensitivity analysis aims to answer that question. This paper focuses on sensitivity
analysis in the context of the distributed coordination framework,
Multiply-Constrained DCOP (MC-DCOP). There are three main
challenges in performing sensitivity analysis: (i) to perform it in a
distributed fashion, (ii) to avoid re-solving an NP-hard MC-DCOP
optimization from scratch, and (iii) to avoid considering unproductive uses for extra resources. To meet these challenges, this paper
presents three types of locally optimal algorithms: link analysis,
local reoptimization and local constraint propagation. These algorithms are distributed and avoid redundant computation by ascertaining just the effects of local perturbations on the original problem. Deploying our algorithms on a large number of MC-DCOP
problems revealed several results. While our cheapest algorithm
successfully identified quality improvements for a few problems,
our more complex techniques were necessary to identify the best
uses for additional resources. Furthermore, we identified two heuristics that can help identify a priori which agents might benefit most
from additional resources: density rank, which works well when
nodes received identical resources and remaining resource rank,
which works well when nodes received resources based on the
number of neighbors they had.},
	author = {Bowring, Emma and Yin, Zhengyu and Rob Zinkov and Tambe, Milind}
}
