Abstract: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.
| Comments: | Submitted to Conference on Decision and Control (CDC) 2026 |
| Subjects: | Systems and Control (eess.SY); Computer Science and Game Theory (cs.GT) |
| Cite as: | arXiv:2605.23129 [eess.SY] |
| (or arXiv:2605.23129v1 [eess.SY] for this version) | |
| https://doi.org/10.48550/arXiv.2605.23129 arXiv-issued DOI via DataCite (pending registration) |
From: Violetta Rostobaya [view email]
[v1]
Fri, 22 May 2026 01:07:14 UTC (1,761 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。