@conference {1504828,
	title = {Analysis of Heuristic Techniques for Controlling Contagion },
	booktitle = {AAAI Fall Symposium},
	year = {2012},
	abstract = {Many strategic actions carry a {\textquoteleft}contagious{\textquoteright} component beyond the immediate locale of the effort itself. Viral marketing
and peacekeeping operations have both been observed to have
a spreading effect. In this work, we use counterinsurgency as
our illustrative domain. Defined as the effort to block the
spread of support for an insurgency, such operations lack the
manpower to defend the entire population and must focus on
the opinions of a subset of local leaders. As past researchers
of security resource allocation have done, we propose using
game theory to develop such policies and model the interconnected network of leaders as a graph.
Unlike this past work in security games, actions in these domains possess a probabilistic, non-local impact. To address
this new class of security games, recent research has used
novel heuristic oracles in a double oracle formulation to generate mixed strategies. However, these heuristic oracles were
evaluated only on runtime and quality scaling with the graph
size. Given the complexity of the problem, numerous other
problem features and metrics must be considered to better
inform practical application of such techniques. Thus, this
work provides a thorough experimental analysis including
variations of the contagion probability average and standard
deviation. We extend the previous analysis to also examine
the size of the action set constructed in the algorithms and the
final mixed strategies themselves. Our results indicate that
game instances featuring smaller graphs and low contagion
probabilities converge slowly while games with larger graphs
and medium contagion probabilities converge most quickly.},
	author = {Tsai, Jason and Weller, Nicholas and Tambe, Milind}
}
