RECORD
Network Flow Routing under Strategic Link Disruptions
Computer Science and Game Theory · Submitted 31 Dec 2015
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim These results can be viewed as a generalization of the classical max-flow with minimum transportation cost problem to adversarial environments.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | This paper considers a 2-player strategic game for network routing under link disruptions. | contribution 0.66 | 0.63 | 0.04 | asserted 0.99 |
| s1 | Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. | contribution 0.50 | 0.31 | 0.03 | asserted 0.99 |
| s2 | Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. | contribution 0.50 | 0.35 | 0.04 | asserted 1.00 |
| s3 | This game is strategically equivalent to a zero-sum game. | result 0.81 | 0.76 | 0.13 | asserted 1.00 |
| s4 | Linear programming duality and the max-flow min-cut theorem are applied to obtain properties that are satisfied in any mixed Nash equilibrium. | method 0.98 | 0.86 | 0.09 | asserted 1.00 |
| s5 | In any equilibrium, both players achieve identical payoffs. | result 1.00 | 0.85 | 0.18 | asserted 1.00 |
| s6 | 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. | result 1.00 | 0.89 | 0.17 | asserted 1.00 |
| s7 | Interestingly, the expected amount of effective flow decreases in both these parameters. | result 0.99 | 0.90 | 0.17 | asserted 1.00 |
| s8 | These results can be viewed as a generalization of the classical max-flow with minimum transportation cost problem to adversarial environments. | interpretation 1.00 | 0.62 | 0.27 | asserted 0.52 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites
Compares with 1 paper
-
Although, in [ref] , the interdictor can disrupt several edges at the same time, she must always disrupt the same number of edges for every action, which is still a restriction of the set of actions we considered for our interdictor.
On the power of randomization in network interdiction · Introduction. · 0.97
Cites as background 1 paper
-
Another relevant line of work is by Bertsimas et al. [ref] .
On the power of randomization in network interdiction · Introduction. · 0.96
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.