@conference {1504601,
	title = {The Deployment-to-Saturation Ratio in Security Games },
	booktitle = {Conference on Artificial Intelligence (AAAI)},
	year = {2012},
	abstract = {Stackelberg security games form the backbone of systems like
ARMOR, IRIS and PROTECT, which are in regular use by the
Los Angeles International Police, US Federal Air Marshal Service and the US Coast Guard respectively. An understanding
of the runtime required by algorithms that power such systems
is critical to furthering the application of game theory to other
real-world domains. This paper identifies the concept of the
deployment-to-saturation ratio in random Stackelberg security
games, and shows that problem instances for which this ratio
is 0.5 are computationally harder than instances with other
deployment-to-saturation ratios for a wide range of different
equilibrium computation methods, including (i) previously
published different MIP algorithms, and (ii) different underlying solvers and solution mechanisms. This finding has at
least two important implications. First, it is important for new
algorithms to be evaluated on the hardest problem instances.
We show that this has often not been done in the past, and
introduce a publicly available benchmark suite to facilitate
such comparisons. Second, we provide evidence that this computationally hard region is also one where optimization would
be of most benefit to security agencies, and thus requires significant attention from researchers in this area. Furthermore,
we use the concept of phase transitions to better understand
this computationally hard region. We define a decision problem related to security games, and show that the probability
that this problem has a solution exhibits a phase transition
as the deployment-to-saturation ratio crosses 0.5. We also
demonstrate that this phase transition is invariant to changes
both in the domain and the domain representation, and that
the phase transition point corresponds to the computationally
hardest instances.},
	author = {Jain, Manish and Leyton-Brown, Kevin and Tambe, Milind}
}
