Network Flow Routing under Strategic Link Disruptions

TitleNetwork Flow Routing under Strategic Link Disruptions
Publication TypeConference Paper
Year of Publication2015
AuthorsDahan, M., and S. Amin
Conference Name2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)
Date Published10/2015
Keywords2-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

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.