A Game Theoretic Approach to Network Reliability Assessment

This paper evaluates the network reliability from a game theory perspective. We formulate a network game consisting of two players - router and attacker, where the router seeks to minimize his total expected trip cost, while the attacker attempts to maximize the expected trip cost by undermining some of the network links. Each link has a probabilistic cost in accordance with its state (normal or damaged). Two different scenarios are considered: link cost independent of the flow and link cost dependent on the flow. We are interested in the link use and damage probabilities at system equilibrium for both cases, and these probabilities are derived in a four-step procedure. First, for the router, Dijkstra and the Frank-Wolfe (FW) algorithms are used to optimize his strategy under the two scenarios, respectively. Second, we model the attacker's problem as a constrained optimization problem, in which all the decision variables are binary. A probabilistic solution discovery algorithm (PSDA) is integrated with stochastic ranking to determine the attacker's optimal strategy. Third, we leverage the Method of Successive Averages (MSA) to approximate the router's link use probabilities and attacker's link damage probabilities at the mixed Nash equilibrium of the game. Finally, given the router's probability of traveling through each link and attacker's probability of undermining each link, we use Monte Carlo Simulations (MCS) to estimate the network reliability as the router arriving the destination node within a prescribed time. Two numerical examples are used to illustrate the procedures and effectiveness of the proposed method.