Abstract:

This work considers a generic network security game on flow networks. In this game, a routing entity sends its (illegal) flow through the network while facing transportation costs, and an interdictor simultaneously interdicts multiple edges while facing interdiction costs. We first derive a combinatorial algorithm to prove the existence of a probability distribution on a partially ordered set (poset) that satisfies a set of constraints involving marginal probabilities of the poset’s elements and maximal chains. We then utilize this existence result to show that the Nash equilibria of the security game can be fully described using primal and dual solutions of a minimum-cost circulation problem. Our analysis leads to a polynomial-time approach for equilibrium computation and provides a new characterization of the critical network components in strategic flow interdiction problems. This work is joint with Saurabh Amin and Patrick Jaillet.

For further information please contact simone.zani@unibocconi.it