Topology Design Games and Dynamics in Adversarial Environments

摘要

We study the problem of network topology design within a set 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 the set of policy compliant topologies with respect to a desired network property. Simultaneously, the adversary counters the designer trying to force operation in a suboptimal topology. Specifically, if the designer and the attacker choose the same link in the current topology to defend/grow and attack, respectively, then the latter is thwarted. However, if the defender does not correctly guess where the attacker is going to attack, and, hence, acts elsewhere, the topology reverts to the best policy-compliant configuration after a successful attack. We show the existence of various mixed strategy equilibria in this game and systematically study its structural properties. We study the effect of parameters, such as probability of a successful attack, and characterize the steady state behavior of the underlying Markov chain. While the intuitive adversarial strategy here is to attack the most important links, the Nash equilibrium strategy is for the designer to defend the most crucial links and for the adversary to focus attack on the lesser crucial links. We validate these properties through two use cases with example sets of network topologies. Next, we consider a multi-stage framework where the designer is not only interested in the instantaneous network property costs but a discounted sum of costs over many time instances. We establish structural properties of the equilibrium strategies in the multi-stage setting, and also demonstrate that applying algorithms based on the Q-Learning and Rollout methods can result in significant benefits for the designer compared with strategies resulting from a one-shot based game.