  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.

Computer Science and Game Theory;Formal Languages and Automata Theory