@conference {1502025,
	title = {The Mysteries of Security Games: Equilibrium Computation Becomes Combinatorial Algorithm Design },
	booktitle = {The 17 ACM Conference on Economics and Computation (ACM-EC)},
	year = {2016},
	abstract = {The security game is a basic model for resource allocation in adversarial environments. Here there are
two players, a defender and an attacker. The defender wants to allocate her limited resources to defend
critical targets and the attacker seeks his most favorable target to attack. In the past decade, there has been
a surge of research interest in analyzing and solving security games that are motivated by applications
from various domains. Remarkably, these models and their game-theoretic solutions have led to real-world
deployments in use by major security agencies like the LAX airport, the US Coast Guard and Federal Air
Marshal Service, as well as non-governmental organizations. Among all these research and applications,
equilibrium computation serves as a foundation.
This paper examines security games from a theoretical perspective and provides a unified view of various security game models. In particular, each security game can be characterized by a set system E which
consists of the defender{\textquoteright}s pure strategies; The defender{\textquoteright}s best response problem can be viewed as a combinatorial optimization problem over E. Our framework captures most of the basic security game models in the
literature, including all the deployed systems; The set system E arising from various domains encodes standard combinatorial problems like bipartite matching, maximum coverage, min-cost flow, packing problems,
etc. Our main result shows that equilibrium computation in security games is essentially a combinatorial
problem. In particular, we prove that, for any set system E, the following problems can be reduced to each
other in polynomial time: (0) combinatorial optimization over E; (1) computing the minimax equilibrium for
zero-sum security games over E; (2) computing the strong Stackelberg equilibrium for security games over
E; (3) computing the best or worst (for the defender) Nash equilibrium for security games over E. Therefore,
the hardness [polynomial solvability] of any of these problems implies the hardness [polynomial solvability]
of all the others. Here, by {\textquotedblleft}games over E{\textquotedblright} we mean the class of security games with arbitrary payoff structures, but a fixed set E of defender pure strategies. This shows that the complexity of a security game is
essentially determined by the set system E. We view drawing these connections as an important conceptual
contribution of this paper.},
	author = {Haifeng Xu}
}
