  Many relevant applications from diverse areas such as marketing, wildlife
conservation, or defending critical infrastructure can be modeled as
interdiction games. In this work, we introduce interdiction games whose
objective is a monotone and submodular set function. Given a ground set of
items, the leader interdicts the usage of some of the items of the follower in
order to minimize the objective value achievable by the follower, who seeks to
maximize a submodular set function over the uninterdicted items subject to
knapsack constraints.
  We propose an exact branch-and-cut algorithm for these kind of interdiction
games. The algorithm is based on interdiction cuts which allow to capture the
follower's objective function value for a given interdiction decision of the
leader and exploit the submodularity of the objective function. We also present
extensions and liftings of these cuts and discuss additional preprocessing
procedures.
  We test our solution framework on the weighted maximal covering interdiction
game and the bipartite inference interdiction game. For both applications, the
improved variants of our interdiction cut perform significantly better than its
basic version. For the weighted maximal covering interdiction game for which a
mixed-integer bilevel linear programming (MIBLP) formulation is available, we
compare the results with those of a state-of-the-art MIBLP solver. While the
MIBLP solver yields a minimum of 54% optimality gap within one hour, our best
branch-and-cut setting solves all but 4 of 108 instances to optimality with a
maximum of 3% gap among unsolved ones.
