Visible to the public Security Games in Network Flow ProblemsConflict Detection Enabled

TitleSecurity Games in Network Flow Problems
Publication TypeJournal Article
Year of Publication2015
AuthorsMathieu Dahan, Saurabh Amin
KeywordsFoundations, Resilient Systems, science of security, SURE Project

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.

Citation KeyDBLP:journals/corr/DahanA15