  We study a class of games, in which the adversary (attacker) is to satisfy a
complex mission specified in linear temporal logic, and the defender is to
prevent the adversary from achieving its goal. A deceptive defender can
allocate decoys, in addition to defense actions, to create disinformation for
the attacker. Thus, we focus on the problem of jointly synthesizing a decoy
placement strategy and a deceptive defense strategy that maximally exploits the
incomplete information the attacker about the decoy locations. We introduce a
model of hypergames on graphs with temporal logic objectives to capture such
adversarial interactions with asymmetric information. Using the hypergame
model, we analyze the effectiveness of a given decoy placement, quantified by
the set of deceptive winning states where the defender can prevent the attacker
from satisfying the attack objective given its incomplete information about
decoy locations. Then, we investigate how to place decoys to maximize the
defender's deceptive winning region. Considering the large search space for all
possible decoy allocation strategies, we incorporate the idea of compositional
synthesis from formal methods and show that the objective function in the class
of decoy allocation problem is monotone and non-decreasing. We derive the
sufficient conditions under which the objective function for the decoy
allocation problem is submodular, or supermodular, respectively. We show a
sub-optimal allocation can be efficiently computed by iteratively composing the
solutions of hypergames with a subset of decoys and the solution of a hypergame
given a single decoy. We use a running example to illustrate the proposed
method.
