@conference {1500417,
	title = {Equilibrium Computation and Robust Optimization in Zero Sum Games with Submodular Structure },
	booktitle = {AAAI conference on Artificial Intelligence (AAAI-18)},
	year = {2018},
	abstract = {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{\textquoteright} 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.},
	author = {Bryan Wilder}
}
