A Game Theoretic Approach to Network Reliability Assessment

Xiaoge Zhang, Sankaran Mahadevan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

26 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number7968295
Pages (from-to)875-892
Number of pages18
JournalIEEE Transactions on Reliability
Volume66
Issue number3
DOIs
Publication statusPublished - Sep 2017
Externally publishedYes

Keywords

  • Game theory
  • network reliability
  • probabilistic solution discovery algorithm (PSDA)
  • resource allocation
  • stochastic networks

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A Game Theoretic Approach to Network Reliability Assessment'. Together they form a unique fingerprint.

Cite this