Quickest Detection of Adversarial Attacks Against Correlated Equilibria

Abstract

We consider correlated equilibria in an adversarial environment, where an adversary can compromise the public signal used by the players for choosing their strategies, while players aim at detecting a potential attack as soon as possible to avoid loss of utility. We model the interaction between the adversary and the players as a zero-sum game and we derive the maxmin strategies for both the defender and the attacker using the framework of quickest change detection. We define a class of adversarial strategies that achieve the optimal trade-off between the impact and the detectability of the attack for the adversary and show that a generalized CUSUM scheme is asymptotically optimal for their detection. Our numerical results on the Sioux-Falls benchmark traffic routing game show that the proposed detection scheme can effectively limit the utility loss by a potential adversary.