2021/04/23 by Abhishek N. Kulkarni, Jie Fu, Kulkarni, Abhishek N. +1
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.2104.11676
openalex publication_date 2021/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Strategic deception is an act of manipulating the opponent's perception to gain strategic advantages. In this paper, we study synthesis of deceptive winning strategies in two-player turn-based zero-sum reachability games on graphs with one-sided incomplete information of action sets. In particular, we consider the class of games in which Player 1 (P1) starts with a non-empty set of private actions, which she may 'reveal' to Player 2 (P2) during the course of the game. P2 is equipped with an inference mechanism using which he updates his perception of P1's action set whenever a new action is revealed. Under this information structure, the objective of P1 is to reach a set of goal states in the game graph while that of P2 is to prevent it. We address the question: how can P1 leverage her information advantages to deceive P2 into choosing actions that in turn benefit P1? To this end, we introduce a dynamic hypergame model to capture the reachability game with evolving misperception of P2. Analyzing the game qualitatively, we design algorithms to synthesize deceptive sure and almost-sure winning regions, and establish two key results: (1) under sure-winning condition, deceptive winning strategy is equivalent to the non-deceptive winning strategy - i.e. use of deception has no advantages, (2) under almost-sure winning condition, the deceptive winning strategy could be more powerful than the non-deceptive strategy. We illustrate our algorithms using a capture-the-flag game, and demonstrate the use of proposed approach to a larger class of games with temporal logic objectives.