Defender Stackelberg Game with Inverse Geodesic Length as Utility Metric

The inverse geodesic length (IGL) is a well-known and widely used measure of network performance. It equals the sum of the inverse distances of all pairs of vertices in the network. A Stackelberg game is a strategic game in which one player commits to a strategy while taking into account that other players will respond accordingly. We propose a natural defender-attacker Stackelberg game on a network in which the defender wants to maximize the IGL level of the network and commits to protecting parts of the network while having knowledge of the strength of an attacker that wants to weaken the network. We present several algorithmic and complexity results concerning the problem of nding the optimal commitment for the defender. Some of our computational hardness results also answer open problems posed in prior work on IGL.