Hitting a path: a generalization of weighted connectivity via game theory

Applying game-theoretical tools for measuring the reliability of a network has become very common. The basic idea is very natural: analyzing an appropriately defined attacker–defender game might give rise to a relevant security metric. In this paper we consider a very natural set of games: the Defender chooses a path P between two given nodes and the Attacker chooses a network element a (that is, an edge or a node). In all cases, the Attacker has to pay a given cost of attack c(a); if, however, a is on P then he also gains a given profit of d(a). We determine the value of various versions of this game and show that the thus arising reliability metrics provide a generalization of weighted connectivity of graphs. We also prove that the values of the games and optimum mixed strategies for both players can be computed in strongly polynomial time.