Network Flow Routing under Strategic Link Disruptions
Mathieu Dahan, Saurabh Amin

Citation
Mathieu Dahan, Saurabh Amin. "Network Flow Routing under Strategic Link Disruptions". 53rd Annual Allerton Conference on Communication, Control, and Computing, 2015.

Abstract
This paper considers a 2-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. This game is strategically equivalent to a zero-sum game. Linear programming duality and the max-flow min-cut theorem are applied to obtain properties that are satisfied in any mixed Nash equilibrium. In any equilibrium, both players achieve identical payoffs. While the defender's expected transportation cost decreases in attacker's marginal value of lost flow, the attacker's expected cost of attack increases in defender's marginal value of effective flow. Interestingly, the expected amount of effective flow decreases in both these parameters. These results can be viewed as a generalization of the classical max-flow with minimum transportation cost problem to adversarial environments.

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/143.html"
  >Network Flow Routing under Strategic Link
  Disruptions</a>, 53rd Annual Allerton Conference on
  Communication, Control, and Computing, 2015.

• Plain text

  Mathieu Dahan, Saurabh Amin. "Network Flow Routing
  under Strategic Link Disruptions". 53rd Annual Allerton
  Conference on Communication, Control, and Computing, 2015.

• BibTeX

  @inproceedings{DahanAmin15_NetworkFlowRoutingUnderStrategicLinkDisruptions,
      author = {Mathieu Dahan and Saurabh Amin},
      title = {Network Flow Routing under Strategic Link
                Disruptions},
      booktitle = {53rd Annual Allerton Conference on Communication,
                Control, and Computing},
      year = {2015},
      abstract = {This paper considers a 2-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. This game is
                strategically equivalent to a zero-sum game.
                Linear programming duality and the max-flow
                min-cut theorem are applied to obtain properties
                that are satisfied in any mixed Nash equilibrium.
                In any equilibrium, both players achieve identical
                payoffs. While the defender's expected
                transportation cost decreases in attacker's
                marginal value of lost flow, the attacker's
                expected cost of attack increases in defender's
                marginal value of effective flow. Interestingly,
                the expected amount of effective flow decreases in
                both these parameters. These results can be viewed
                as a generalization of the classical max-flow with
                minimum transportation cost problem to adversarial
                environments.},
      URL = {http://cps-forces.org/pubs/143.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.