Topology design under adversarial dynamics

Abstract

We study the problem of network topology design within a sequence of policy-compliant topologies as a game between a designer and an adversary. At any time instant, the designer aims to operate the network in an optimal topology within this policy compliant sequence with respect to a desired network property. Simultaneously, the adversary counters the designer trying to force operation in a suboptimal topology. We show the existence of various mixed strategy equilibria in this game and systematically study its structural properties. We study the effect of parameters, and characterize the steady state behavior of the underlying Markov chain. While the intuitive adversarial strategy here is to attack links appearing early in the topology sequence, the Nash Equilibrium strategy is for the designer to defend the earlier links and for the adversary to attack the later links. We validate these properties through two use cases with example sets of network topologies.