Security Games in Network Flow Problems
Mathieu Dahan, Saurabh Amin

Citation
Mathieu Dahan, Saurabh Amin. "Security Games in Network Flow Problems". submitted to Math of OR, 2016.

Abstract
This article considers a two-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. Linear programming duality in zero-sum games and the Max-Flow Min-Cut Theorem are applied to obtain properties that are satisfied in any Nash equilibrium. A characterization of the support of the equilibrium strategies is provided using graph-theoretic arguments. Finally, conditions under which these results extend to budget-constrained environments are also studied. These results extend the classical minimum cost maximum flow problem and the minimum cut problem to a class of security games on flow networks.

Electronic downloads

Internal. This publication has been marked by the author for FORCES-only distribution, so electronic downloads are not available without logging in.

Citation formats

• HTML

  Mathieu Dahan, Saurabh Amin. <a
  href="http://www.cps-forces.org/pubs/144.html"
  >Security Games in Network Flow Problems</a>,
  <i>submitted to Math of OR</i>,  2016.

• Plain text

  Mathieu Dahan, Saurabh Amin. "Security Games in Network
  Flow Problems". <i>submitted to Math of
  OR</i>,  2016.

• BibTeX

  @article{DahanAmin16_SecurityGamesInNetworkFlowProblems,
      author = {Mathieu Dahan and Saurabh Amin},
      title = {Security Games in Network Flow Problems},
      journal = {submitted to Math of OR},
      year = {2016},
      abstract = {This article considers a two-player strategic game
                for network routing under link disruptions. Player
                1 (defender) routes flow through a network to
                maximize her value of effective flow while facing
                transportation costs. Player 2 (attacker)
                simultaneously disrupts one or more links to
                maximize her value of lost flow but also faces
                cost of disrupting links. Linear programming
                duality in zero-sum games and the Max-Flow Min-Cut
                Theorem are applied to obtain properties that are
                satisfied in any Nash equilibrium. A
                characterization of the support of the equilibrium
                strategies is provided using graph-theoretic
                arguments. Finally, conditions under which these
                results extend to budget-constrained environments
                are also studied. These results extend the
                classical minimum cost maximum flow problem and
                the minimum cut problem to a class of security
                games on flow networks.},
      URL = {http://cps-forces.org/pubs/144.html}
  }
  

Posted by Saurabh Amin on 16 Apr 2016.
Groups: forces
For additional information, see the Publications FAQ or contact webmaster at cps-forces org.