  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. 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's pure
strategies, The defender'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$. Here, by "games over $E$" 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$.
