  Deception plays a crucial role in strategic interactions with incomplete
information. Motivated by security applications, we study a class of two-player
turn-based deterministic games with one-sided incomplete information, in which
player 1 (P1) aims to prevent player 2 (P2) from reaching a set of target
states. In addition to actions, P1 can place two kinds of deception resources:
"traps" and "fake targets" to disinform P2 about the transition dynamics and
payoff of the game. Traps "hide the real" by making trap states appear normal,
while fake targets "reveal the fiction" by advertising non-target states as
targets. We are interested in jointly synthesizing optimal decoy placement and
deceptive defense strategies for P1 that exploits P2's misinformation. We
introduce a novel hypergame on graph model and two solution concepts: stealthy
deceptive sure winning and stealthy deceptive almost-sure winning. These
identify states from which P1 can prevent P2 from reaching the target in a
finite number of steps or with probability one without allowing P2 to become
aware that it is being deceived. Consequently, determining the optimal decoy
placement corresponds to maximizing the size of P1's deceptive winning region.
Considering the combinatorial complexity of exploring all decoy allocations, we
utilize compositional synthesis concepts to show that the objective function
for decoy placement is monotone, non-decreasing, and, in certain cases, sub- or
super-modular. This leads to a greedy algorithm for decoy placement, achieving
a $(1 - 1/e)$-approximation when the objective function is sub- or
super-modular. The proposed hypergame model and solution concepts contribute to
understanding the optimal deception resource allocation and deception
strategies in various security applications.
