Deception and Counter Deception in Adversarial Graph Traversal Game
For researchers in multi-agent systems and security, this work addresses the problem of deception under incomplete information in adversarial traversal, but the contribution is incremental as it extends an existing algorithm.
The paper models adversarial graph traversal as a game with two-sided incomplete information and develops an adapted Extensive-Form Double Oracle algorithm that terminates in finite time to compute an epsilon-Nash equilibrium, using Value of Information to characterize deceptive and counter-deceptive behaviors.
We study deception in adversarial graph traversal, where a mobile agent seeks to reach a goal with minimum cost while an adversary alters edge costs to increase the total traversal cost. Unlike prior works that assume fixed observer-deceiver roles, we model this problem with two-sided incomplete information in which both players possess private information and update beliefs from observed actions. To solve the resulting indefinite-horizon game, we develop an adaptation of the Extensive-Form Double Oracle (XDO) algorithm. While the standard XDO algorithm is designed for finite games, the proposed adaptation ensures bounded computation despite endogenous game termination. We show that the proposed algorithm terminates in finite time and returns an epsilon-Nash equilibrium. Finally, we use Value of Information to characterize the deceptive and counter-deceptive behaviors that emerge from equilibrium strategies.