Abstract | We consider a strategic game with two classes of confronting
randomized players on a graph G(V,E): í attackers, each choosing vertices
and wishing to minimize the probability of being caught, and a
defender, who chooses edges and gains the expected number of attackers
it catches. The Price of Defense is the worst-case ratio, over all Nash
equilibria, of the optimal gain of the defender over its gain at a Nash equilibrium.
We provide a comprehensive collection of trade-offs between the
Price of Defense and the computational efficiency of Nash equilibria.
– Through reduction to a Two-Players, Constant-Sum Game, we prove
that a Nash equilibrium can be computed in polynomial time. The
reduction does not provide any apparent guarantees on the Price of
Defense.
– To obtain such, we analyze several structured Nash equilibria:
• In a Matching Nash equilibrium, the support of the defender is
an Edge Cover. We prove that they can be computed in polynomial
time, and they incur a Price of Defense of á(G), the
Independence Number of G.
• In a Perfect Matching Nash equilibrium, the support of the defender
is a Perfect Matching. We prove that they can be computed
in polynomial time, and they incur a Price of Defense of
|V |
2 .
• In a Defender Uniform Nash equilibrium, the defender chooses
uniformly each edge in its support. We prove that they incur a
Price of Defense falling between those for Matching and Perfect
Matching Nash Equilibria; however, it is NP-complete to decide
their existence.
• In an Attacker Symmetric and Uniform Nash equilibrium, all
attackers have a common support on which each uses a uniform
distribution. We prove that they can be computed in polynomial
time and incur a Price of Defense of either
|V |
2 or á(G). |