Title | Network Flow Routing under Strategic Link Disruptions |
Publication Type | Conference Papers |
Year of Publication | 2015 |
Authors | Dahan, M., and S. Amin |
Conference Name | 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton) |
Date Published | 10/2015 |
Keywords | 2-player strategic game, attacker expected attack cost, attacker marginal lost flow value, defender expected transportation cost, defender marginal effective flow value, directed graphs, duality (mathematics), effective flow value, Electronic mail, Environmental engineering, game theory, Games, linear programming, linear programming duality, max-flow min-cut theorem, minimisation, minimum transportation cost problem, mixed Nash equilibrium, Nash equilibrium, network flow routing, network theory (graphs), payoff value, Routing, strategic link disruptions, Supply and demand, Transportation, zero-sum game |
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. |
DOI | 10.1109/ALLERTON.2015.7447026 |