  We define a class of zero-sum games with combinatorial structure, where the
best response problem of one player is to maximize a submodular function. For
example, this class includes security games played on networks, as well as the
problem of robustly optimizing a submodular function over the worst case from a
set of scenarios. The challenge in computing equilibria is that both players'
strategy spaces can be exponentially large. Accordingly, previous algorithms
have worst-case exponential runtime and indeed fail to scale up on practical
instances. We provide a pseudopolynomial-time algorithm which obtains a
guaranteed $(1 - 1/e)^2$-approximate mixed strategy for the maximizing player.
Our algorithm only requires access to a weakened version of a best response
oracle for the minimizing player which runs in polynomial time. Experimental
results for network security games and a robust budget allocation problem
confirm that our algorithm delivers near-optimal solutions and scales to much
larger instances than was previously possible.
