---
title: "Synthesis of Deceptive Strategies in Reachability Games with Action Misperception"
authors:
  - "Abhishek N. Kulkarni"
  - "Jie Fu"
doi: "10.24963/ijcai.2020/31"
url: "https://ijcai.org/proceedings/2020/31"
pdf: "https://ijcai.org/proceedings/2020/0031.pdf"
venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence"
year: 2020
pages: "217-223"
track: "Main track"
keywords:
  - "Agent-based and Multi-agent Systems: Algorithmic Game Theory"
  - "Knowledge Representation and Reasoning: Reasoning about Knowledge and Belief"
  - "Agent-based and Multi-agent Systems: Formal Verification, Validation and Synthesis"
---

# Synthesis of Deceptive Strategies in Reachability Games with Action Misperception

Abhishek N. Kulkarni, Jie Fu

*Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 217-223. DOI: [10.24963/ijcai.2020/31](https://doi.org/10.24963/ijcai.2020/31)

## Abstract

We consider a class of two-player turn-based zero-sum games on graphs with reachability objectives, known as reachability games, where the objective of Player 1 (P1) is to reach a set of goal states, and that of Player 2 (P2) is to prevent this. In particular, we consider the case where the players have asymmetric information about each other's action capabilities: P2 starts with an incomplete information (misperception) about P1's action set, and updates the misperception when P1 uses an action previously unknown to P2. When P1 is made aware of P2's misperception, the key question is whether P1 can control P2's perception so as to deceive P2 into selecting actions to P1's advantage? To answer this question, we introduce a dynamic hypergame model to capture the reachability game with evolving misperception of P2. Then, we present a fixed-point algorithm to compute the deceptive winning region and strategy for P1 under almost-sure winning condition. Finally, we show that the synthesized deceptive winning strategy is at least as powerful as the (non-deceptive) winning strategy in the game in which P1 does not account for P2's misperception. We illustrate our algorithm using a robot motion planning in an adversarial environment.

## Full text

## 1 Introduction

Synthesis of winning strategies in reachability games is a central problem in reactive synthesis [Pnueli and Rosner, 1989], control of discrete event systems [Ramadge and Wonham, 1989], and robotics [Fainekos et al., 2009]. In a two-player reachability game, a controllable player, P1 (pronoun "she"), plays against an uncontrollable adversarial player, P2 (pronoun "he"), to reach the goal states. These games have been extensively studied in algorithmic game theory [de Alfaro et al., 2007] and reactive synthesis [Bloem et al., 2012]. Polynomial-time algorithms are known for synthesizing surewinning and almost-sure winning strategies, when both players have complete and symmetric information. However, the solution concepts for such games under asymmetric information have not been thoroughly studied.

Information asymmetry arises when a player has some private information that are not shared with others [Rasmusen, 1989]. We consider the case when P1 has complete information about both players' action capabilities, but P2 starts with an incomplete information about P1's action capabilities. As two players interact, their information evolves. Particularly, when P1 uses an action previously unknown to P2, P2 can update his knowledge about the other's capabilities using an inference mechanism. In response, P2 would update his counter-strategy. We are interested in the following question: if P1 is made aware of the initial information known to P2 and his inference mechanism, can P1 find a strategy to control P2's information in such a way that P2's counterstrategy given his evolving information is advantageous to P1? In the context of qualitative analysis of reachability games, this could be interpreted as: froma state that is losing for P1 in a game with symmetric information, can P1 reach his goal from the same state when the information is asymmetric? We note that a strategy of P1 that controls P2's information to P1's advantage is indeed deceptive [Ettinger and Jehiel, 2010]. In this paper, we establish that such a deceptive winning strategy may exist under almost-sure winning condition and propose an algorithm to synthesize it.

We approach the question by modeling the interaction between P1 and P2 as a hypergame [Bennett, 1977]. A hypergame allows players to play different games in their minds and further allows them to model the games that others might be playing. In literature, hypergames and Bayesian games [Harsanyi, 1967] are common models to capture game-theoretic interactions with asymmetric, incomplete information. In Bayesian games, each player uses his incomplete information to define a probability distribution over the possible types of the opponent. The distributions over types are assumed to be common knowledge. In hypergames, no such probabilistic characterizations of incomplete information is used or assumed. For action deception, P2 has incomplete information about P1's capabilities but does not have a prior knowledge about the set of possible types of P1. Thus, we adopt the hypergame model to understand action deception. In the past, hypergame model has been used to study deception [Gutierrez et al., 2015; Kovach, 2016]. These papers mainly focus on extending the notion of Nash equilibrium to level-k normal form hypergames. [Gharesifard and Cort´es, 2014] use the notion of H-digraph to establish necessary and sufficient conditions for deceivability. An H-digraph models a hypergame as a graph with nodes representing different outcomes in a normal-form game. However, our game model is not a normal-form game, but instead a game on graph. A hypergame model based on a game on graph has been defined in [Kulkarni and Fu, 2019] where one player has incomplete information about the opponent's task specification. However, their model assumes the perception of P2 to remain constant, whereas in our case, the information available to both players' may evolve as the game progresses. Given this background, we state the two key contributions of the paper.

Dynamic Hypergame Model for Action Misperception. We introduce a dynamic hypergame on graph model that captures (i) the evolving information of P2, and (ii) the P1's information regarding current perception of P2, in a single graphical model.

Deceptive Almost-sure Winning Synthesis Algorithm. Given a dynamic hypergame model, we propose an algorithm to compute deceptive almost-sure winning region, and thereby a deceptive almost-sure winning strategy for P1 that effectively exploits P2's misperception. We prove that the deceptive winning region is a superset of the (non-deceptive) winning region in the symmetric information game where P1 does not account for P2's misperception. This in turn implies that the deceptive winning strategy is at least as powerful as the (non-deceptive) winning strategy.

## 2 Preliminaries

Let Σ be a finite alphabet. A sequence of symbols w = w0w1 . . . wn with wi ∈ Σ, i = 0, 1, . . . , n is called a finite word and Σ∗ is the set of finite words that can be generated with alphabet Σ. We denote by Σω , the set of ω-regular words obtained by concatenating the elements in Σ infinitely many times. Given a set X, let Dist(X) be the set of probability distributions over X. Given a distribution δ ∈ Dist(X), the set Supp(δ) = {x ∈ X | δ(x) > 0} is called the support of the distribution.

## 2.1 Games on Graph

Consider an interaction between two players; P1 with a reachability objective and P2 with an objective of preventing P1 from completing her task.

Definition 1 (Game on Graph). Let the action sets of P1 and P2 be A1 and A2, respectively. Then, a turn-based game on graph is the tuple

<!-- formula-not-decoded -->

where

- S = S1 ∪ S2 is the set of states partitioned into P1's states, S1, and P2's states, S2. P1 chooses an action when s ∈ S1 and P2 chooses an action when s ∈ S2.
- Act = A1 ∪ A2 is set of actions for P1 and P2.
- T : S ×Act → S is a deterministic transition function that maps a state and an action to a successor state.
- F ⊆ S is a set of final states.

Algorithm 1 Almost-Sure Winning Region [Mazala, 2002]

## Inputs: G, F

- 1: Z0 = F
- 2: repeat
- 3: Pre1(Zk) = {s ∈ S1 | ∃a ∈ A1 s.t. T(s, a) ∈ Zk}
- 4: Pre2(Zk) = {s ∈ S2 | ∀b ∈ A2 : T(s, b) ∈ Zk}
- 5: Zk+1 = Zk ∪Pre1(Zk) ∪Pre2(Zk)
- 6: until Zk+1 = Zk
- 7: returnWin1 = Zk

A trace in the game G is an infinite, ordered sequence of state-action pairs τ = (s0, a0), (s1, a1), (s2, a2), . . .. We write τ [n] = (sn, an) to denote n-th state-action pair. A run ρ is the projection of trace onto the state space. We denote it as the sequence ρ = τ ⇂S= s0s1s2 . . .. Similarly, the actionhistory is the projection of trace onto the action space, denoted by α = τ ⇂Act= a0a1a2 . . .. The k-th element in a run (resp. action-history) is denoted by ρk (resp. αk).

In this paper, we consider reachability objectives for P1. The set of states that occur in a run is given by Occ(ρ) = {s ∈ S | ∃k ∈ N · s = ρk}. A run ρ is said to be winning for P1 in the reachability objective if it satisfies Occ(ρ) ∩F ̸= ∅. If a run is not winning for P1, then it is winning for P2.

The memoryless stochastic or randomized strategies for P1 and P2 are defined as π : S1 → Dist(A1) and σ : S2 → Dist(A2), respectively. As the model in Def. 1 is a deterministic turn-based game model, it is sufficient to consider memoryless strategies [Mazala, 2002]. Let Ωπ,σ s be the exhaustive set of runs that result when P1 and P2 play strategies π and σ in a game starting at the state s ∈ S. The randomized strategies of P1 and P2 induce a Markov chain from G-that is, a probability distribution over the set Ωπ,σ s .

Given a state s ∈ S, a randomized strategy π is almostsure winning (ASW) for P1, if and only if for every possible randomized strategy σ of P2, the probability is one for a run that satisfies Occ(ρ) ∩ F ̸= ∅, given the distribution of runs induced by (π, σ). A state is called an almost-sure winning (ASW) state for P1, if there exists an ASW strategy for P1 from that state. The exhaustive set of almost-sure winning states for P1 is called her ASW region. The almost-sure winning region can be computed using Alg. 1.

Let us introduce a running example that we shall use to explain the concepts in this paper.

Example 1. Consider the game graph in Fig. 1. The circle states, {s1, s3}, are P1 states and the square states, {s0, s2}, are P2 states. The objective of P1 is to reach to the final state s0 from the initial state s2. P1's action set is A1 = {a1, a2}, and P2's action set is A2 = {b1, b2}.

The ASW region for P1 in the game is Win1 = {s0, s1}. This can intuitively be understood as follows. P1 can win from state s1 by choosing the action a1. However, the states s2 and s3 are losing for P1 because P2 has a strategy to indefinitely restrict the game within the states s2, s3 by choosing the action b2 at the state s2.

Figure 1: An example game on graph

![Image](https://ijcai.org/proceedings/2020/fulltext/31/image_000000_fc38969a1d9a4d363dc621afaf9425e5e2028f153209847e3c614449b0f0f872.png)

## 2.2 ActionMisperception and Information Asymmetry

In this paper, we consider the sub-class of games with asymmetric information in which P2 has incomplete information about P1's action capabilities. This is formalized in the following assumption.

Assumption 1. P1 has complete information about the players' action sets, i.e. P1 knows A1 and A2. P2 only knows his own action set A2, but (mis)perceives P1's action set to be a subset X ⊊ A1. Both players have complete information about the game state space S and the final states F .

The result of Assumption 1 is that P1 and P2, in their minds, play different games to synthesize their respective strategies. We refer to these games as the perceptual games of the players. P1's perceptual game is identical to the ground-truth game; G(A1) = 〈S, A1 ∪ A2, T, F 〉, while P2's perceptual game is a game under misperception; G(X) = 〈S,X ∪ A2, T, F〉. Let us formalize the new notation used to distinguish between the perceptual games of P1 and P2.

Notation 1. Let X ⊆ A1 be a subset of P1's action set. We denote a perceptual game in which P1's action set is X by G(X) = 〈S, X ∪ A2, T, F 〉. The winning regions for P1 and P2 in the game G(X) are denoted by Win1(X) and Win2(X), respectively.

Assuming P1 and P2 to be rational players, they would use the solution approach reviewed in Section 2.1 to compute their winning strategies in their respective perceptual games. That is, P1 will solve G(A1) in her mind to obtain π and P2 will solve G(X) in his mind to compute σ. However, P1 is likely to compute a conservative strategy because she overestimates the information available to P2. Naturally, we want to know whether P1 can improve her strategy if she is made aware of P2's current misperception X?

Before we answer the above question, recall from Section 1 that we allow P2's misperception to evolve during the game. For instance, what would happen when P2 observes P1 playing an action a ∈ A1, which P2 did not believe to be in P1's action set? We might argue that P2 will at least add a new action a to his perceived action set, X, of P1. Thus, the new perception would be X ∪ {a}. Also, P2 might be capable of complex inference. That is, on observing that P1 can perform an action a, P2 might infer that P1 must be capable of actions b and c, thus, updating his perception set to X ∪ {a, b, c}. To capture such inference capabilities, we introduce a generic perception update function for P2 as follows,

Definition 2 (Inference Mechanism). A deterministic inference mechanism is a function η : 2A1 ×A1 → 2A1 that maps a subset of actions X ⊆ A1 and an action a ∈ A1 to an updated subset of actions Y = η(X, a) such that a ∈ Y .

Figure 2: Perceptual game of P2

![Image](https://ijcai.org/proceedings/2020/fulltext/31/image_000001_135fe8d1b014946d5b32b6bab75dc63dcc644718390b9743ef8ae344d7e0183a.png)

Given the formalism of inference mechanism to capture the evolving misperception of P2 during the game, we now state our problem statement.

## 2.3 Problem Statement

When P2's misperception evolves during the game, P1 should also strategize to reveal an action that is not currently known to P2. By doing so, P1 may control the evolution of P2's misperception to her advantage. Let us revisit Example 1 to develop an intuition of how P1 might control P2's perception.

Example 2 (Example 1 contd.). Suppose that, in Example 1, P2 starts with a misperception about P1's action capabilities as X0 = {a2}. In this setup, let us understand the perceptual games of the players. P1's perceptual game; G1 = G(A1), is the same as the ground-truth game as shown in Fig. 1. P2's perceptual game, initially, is the game G2 = G(X0) that does not include edges labeled with action a1 as shown in Fig. 2. Clearly, as the final state s0 is not reachable in G2, P2 misperceives both actions b1 and b2 to be safe to play at state s2, when only the action b2 is safe in the ground-truth game.

When P1 is aware of P2's misperception, X0, a deceptive strategy should, intuitively, not use a1 unless the game state is s1. Assuming P2 uses a randomized strategy with support A2, it is easy to compute that the probability of reaching the state s1 from the initial state s2 is one. At s1, P1 can win the game by choosing a1 in one step. We note that if P1 uses a1 in state s3, then P2 will update his perception to X1 = A1, and mark the action b1 to be unsafe in state s2. Thus, P1 will never be able to win the game.

We call such a strategy of P1, where she intentionally controls P2's misperception, as an action-deceptive strategy or simply a deceptive strategy (see Def. 6 for a formal definition). We formalize our problem statement.

Problem 1. Consider a reachability game under information asymmetry in which Assumption 1 holds. If P1 is informed of the initial misperception of P2, X0, and his inference mechanism η, then determine a deceptive almost-sure winning strategy for P1 to satisfy her reachability objective.

In particular, we want to investigate whether the use of deception is advantageous for P1 or not. We say P1 gets advantage with deception if at least one game state that is not almost-sure winning for P1 in the game without deception becomes winning for her with use of deception.

## 3 Dynamic Hypergame for Action Deception

When two players play different games in their minds, their interaction is better modeled as a hypergame [Bennett, 1977]. Definition 3 (First-level Hypergame). A first-level hypergame is defined as a tuple of the perceptual games being

played by the players,

<!-- formula-not-decoded -->

where the P1 (resp. P2) solves the game G1 (resp. G2) to compute the winning strategy.

When one of the players is aware of the other player's perception, but the other player is not, we say that a second-level hypergame is being played. In line with Problem 1, we assume that P1 is aware of the P2's misperception, i.e. P1 knows the action set X ⊆ A1 as perceived by P2. If P1 knows X, then P1 can construct the perceptual game of P2, G(X), and therefore P1 knows the first-level hypergame H1 .

However, P2's perception evolves when he observes P1 using actions that are not included in X. This means that the game G(X) changes when P2's perception changes, and so does the hypergame H1 . We now define a graph to model the hypergame representing the evolving misperception of P2, called as a dynamic hypergame on graph.

Definition 4 (Dynamic Hypergame on Graph). Let Γ = 2A1 . We define the dynamic hypergame on graph with action misperception as

<!-- formula-not-decoded -->

where

- V = S ×Γ is the set of hypergame states,
- Act = A1 ∪ A2 is the set of actions of P1 and P2,
- ∆ : V ×Act → V is the transition function such that (s,X) a-→ (s′ ,X′ ) if and only if s′ = T(s, a) and X′ = η(X, a),
- F = F ×Γ is the set of final states.

For convenience, we shall refer to the dynamic hypergame on graph as simply hypergame in the remainder of the paper. Analogous to game on graph, a trace in a hypergame is an infinite, ordered sequence of state-action pairs given by τ = (v0, a0)(v1, a1) . . . and the action-history is defined as α = τ ⇂Act= a0a1a2 . . .. In contrast with the game on graphs, we distinguish between a hypergame-run (h-run) as a projection of trace onto the hypergame state space ν = τ ⇂V = v0v1v2 . . . and a game-run as a projection of trace onto game state space ρ = τ ⇂S= s0s1s2 . . ., where sk is the game state corresponding to hypergame state vk = (sk, ·). A reachability objective is said to be satisfied over the hypergame if and only if Occ(ν) ∩ F ̸= ∅, i.e. the hypergame-run ν visits a winning state in F. By definition, the following statement is always true; Occ(ρ)∩F ̸= ∅ if and only if Occ(ν) ∩ F ̸= ∅.

Example 3 (Example 1 contd.). The hypergame modeling the asymmetric information from Example 2 is shown in Fig. 3 (the figure only shows the reachable states). Every state is represented as a tuple of a game state and the current misperception of P2 at that state. Letting X1 = {a2} and X2 = {a1, a2}, the traces τ1 = ((s2,X1), b1) , ((s1,X1), a1) , (s0,X2), and τ2 = ((s2,X1), b2) , ((s3,X1), a1) , ((s2,X2), b1) , ((s1,X2), a1) , (s0,X2) are the examples of winning traces for P1 in the hypergame. However, in the next section, we will see that (a) τ2 will never be observed when both players act rationally, whereas τ1 might be observed, and (b) how to identify all rationally possible winning traces for P1.

Figure 3: The dynamic hypergame on graph

![Image](https://ijcai.org/proceedings/2020/fulltext/31/image_000002_62c37af4c7cef4ce62af23cdeff08051c1f2e61efd16d40b4afdb518c8350adc.png)

## 4 Synthesis of Deceptive Almost-Sure Winning Strategy

In this section, we present an algorithm to synthesize deceptive almost-sure winning (DASW) strategies that are rationally possible in the hypergame. To do so, we must reason about P2's perception and his subjectively rational actions. To understand this, we revisit the concept of permissive strategies in a game on graph.

Recall that an action is permissive for a player at a given state if the player can stay within the winning region by performing that action [Bernet et al., 2002]. In a game under information asymmetry, whether a state is winning or not depends on the player's perception. Hence, we define the notion of perceptually permissive actions, which extends the definition of permissive actions to model evolving perception.

Definition 5 (Perceptually Permissive Actions of P2). Let u = (s,X) ∈ V2 and v = (s′ ,X) be two hypergame states such that v = ∆(u, b) for some b ∈ A2. Then, the set M(u) = {a ∈ A2 | s′ ∈ Win2(X)} is the set of P2's perceptually permissive actions at u.

In words, the perceptually permissive actions for a given state u = (s,X) is the set of permissive actions for P2 in the perceptual game with action set X.

Remark 1. By Def. 2, P2's action does not have any effect on P2's perception. Hence, the P2's perception at v is the same as her perception at u, i.e. X.

Assumption 2. At a state v ∈ V2, P2 plays a randomized strategy, σ, defined over the perceptually permissive actions M(v) such that Supp (σ(v)) = M(v).

Now, we formalize the notion of Deceptive Almost-Sure Winning (DASW) strategy.

Definition 6 (Deceptive Almost-Sure Winning (DASW) Strategy). Given a hypergame state v ∈ V , a strategy π is said to be deceptive almost-sure winning (DASW) strategy for P1 if and only if for every P2's strategy σ satisfying Assumption 2, the probability of an h-run ν induced from H by (π, σ) satisfying Occ(ν) ∩ F ̸= ∅ is one.

The states at which P1 has a DASW strategy are called as DASW states. The exhaustive set of all DASW states is called DASW region.

Now, we discuss Alg. 2 that computes the DASW region for P1. Our algorithm is inspired by the algorithm presented in [de Alfaro et al., 2007] to compute the almost-sure winning (ASW) region in the concurrent ω-regular games. The idea behind Alg. 2 is to identify the states where P2 perceives some unsafe actions as safe due to misperception. This is achieved by modifying the definitions of SAFE-1 and SAFE2 in [de Alfaro et al., 2007] using the following definitions:

<!-- formula-not-decoded -->

The Alg. 2 works as follows. It starts with Z0 = Win1(A1) × Γ from where P1 has an ASW strategy to win the game no matter of P2's perception. Then it iteratively expands the set by invoking SAFE-2 followed by SAFE-1 until a fixed-point is reached. The SAFE-1 sub-routine computes the largest subset Y of the input set U, such that P1 has a strategy to restrict the game indefinitely within Y . SAFE-2 sub-routine computes the largest subset Y of the input set U, such that given his current (mis)perception, P2 can restrict the game indefinitely within Y . Here, it is important to note that P2 chooses his actions based on his perceptual game G(X), and not the hypergame. Only P1 knows the hypergame because she is aware of P2's misperception. As a consequence, before reaching the fixed-point, SAFE-2 might include states from which P2 may not have a strategy to indefinitely restrict P1 from reaching Z0, i.e. P1 may have a DASW strategy from these states. However, after reaching the fixed-point, say in the iteration k, we observe that all DASW states are included in Zk. A DASW strategy can then be computed based on the proof of Thm. 1. Let us now revisit the Example 3 to understand Alg. 2.

Example 4 (Example 3 contd.). Consider the hypergame graph as shown in Fig. 3. Recall from Example 1 that Almost-Sure Winning (ASW) region is Win1(A1) = {s0, s1}, therefore, we have Z0 = {(s0,X2), (s1,X2), (s1,X1)} (we omit (s0,X1) as it is unreachable). The perceptually permissive actions for P2 are M((s2,X1)) = {b1, b2} and M((s2, X2)) = {b2}.

Iteration 1 of DASW. The first step is to compute C0, i.e. the subset of V \ Z0 which P2 perceives to be safe for himself. The SAFE-2 sub-routine takes 3 iterations to reach a fixed-point, at the end of which C0 = {(s2, X2), (s3, X2)}. The next step is to compute Z1, which the largest subset of V \ C0 in which P1 can stay indefinitely. The SAFE-1 subroutine takes 2 iterations to reach a fixed point. In its first iteration, DAPre11 adds a state (s3,X1) and DAPre21 adds a state (s2,X1) to Z1. The interesting observation here is that

```
1: function DASW(H) 2: Z0 =Win1(A1) ×Γ 3: repeat 4: Ck = SAFE-2(V \ Zk) 5: Zk+1 = SAFE-1(V \ Ck) 6: until Zk+1 = Zk 7: return DASWin1 = Zk 8: end function 1: function SAFE-i(U) 2: Y0 = U 3: repeat 4: W1 = DAPre1i (Yk) 5: W2 = DAPre2i (Yk) 6: Yk+1 = Yk ∩ (W1 ∪ W2) 7: until Yk+1 = Yk 8: return Yk 9: end function
```

Algorithm 2 Deceptive Almost-Sure Winning Region for P1

(s2,X1) is added because the actions b1 and b2 are perceptually permissive actions for P2, both of which lead to a state in V \ C0.

Iteration 2 of DASW. The fixed-point of DASW algorithm is reached in this iteration with Z2 = {(s0,X2), (s1,X2), (s1,X1), (s2,X1), (s3,X1)}. The states (s2,X1) and (s3, X1) are idenitifed as the DASW states for P1.

Using intuition from Example 4 with the observation that Win1(A1) ⊆ DASWin1 ⇂S holds for every hypergame H by definition, we formalize our first key result. It establishes that using action deception could be advantageous to P1.

Proposition 1. There exists a hypergame H for which Win1(A1) ⊊ DASWin1 ⇂S .

Next, we proceed to prove the correctness of Alg. 2 by showing that from every state in DASWin1, we can construct a DASW strategy for P1 to ensure a visit to final states with probability one. We first prove two lemmas.

Lemma 1. In the i-th iteration of Alg. 2, P1 has a strategy to restrict the game indefinitely within Zi, for all states in Zi.

Proof. (v ∈ V2). For a P2's state in Zi, every state v′ = ∆(v, b) for a perceptually permissive action b ∈ µ(v) of P2 is in Zi, by definition of DAPre21 . Hence, no action of P2 at any state v ∈ Zi can lead the game state outside Zi.

(v ∈ V1). For every P1's state in Zi, there exists an action a ∈ A such that the successor v′ = ∆(v, a) is in Zi, by definition of DAPre11 . Hence, P1 always has an action, consequently a strategy, to stay within Zi.

Lemma 2. For every state v ∈ Zi+1 \ Zi added in the i-th iteration of Alg. 2, there exists an action that leads into Zi.

Proof. Given any state v ∈ V at the beginning of the i-th iteration, observe that it would belong to either Ci-1, Zi or V \(Ci-1 ∪Zi). We will prove the statement by showing that the every new state added to Zi+1 has at least one transition into Zi.

Consider i-th iteration of Alg. 2. The sub-routine SAFE-2 will add a P1 state v ∈ V1 \ Zi to Ci if all the actions of P1

stay within V \ Zi. Similarly, SAFE-2 will include a P2 state v ∈ V2 \ Zi in Ci if all perceptually permissive actions of P2 lead to a state within V \ Zi. Therefore, a state that is not included in Ci must have at least one action leading outside V \ Zi, i.e. entering Zi. In the next step, the sub-routine SAFE-1 may add new states to Zi+1 from the set V \Ci. But, all states in V \Ci have an action entering Zi. Hence, all new states added to Zi+1 satisfy the statement.

Lma. 2 shows that P1 has a strategy to reach Zi from a state added to Zi+1 in one-step. However, this is not true for P2. From a P2 state in Zi+1, there exists a positive probability to reach Zi because of Assumption 2. In the next theorem, we prove a stronger statement that from every state in Zi+1, P1 can reach not only Zi but also Z0 with probability one.

Theorem 1. From every state v ∈ DASWin1, P1 has a DASW strategy to satisfy ϕ.

Proof. For any v ∈ Zi, i &gt; 1, P1 has a strategy to stay within Zi indefinitely, by Lma. 1. Furthermore, by Lma. 2, the probability of reaching to a state v′ ∈ Zi-1 from v is strictly positive. Thus, given a run of infinite length, the probability of reaching Zi-1 fromZi is one. By repeatedly applying this argument, the probability of reaching Z0 fromZi is one. The DASW strategy can be constructed based on the proof of Thm. 1. At a P1 state v ∈ V1, if i ≥ 1 is the smallest integer such that v ∈ Zi, then π(v) = {a ∈ A1 | v′ = ∆(v, a) and v′ ∈ Zi-1} is the DASW strategy of P1 at v. Given π(v) is a set, P1 can select any action from this set. We also state the following two important corollaries (proofs

omitted due to space) that follow from Prop. 1 and Lma. 2.

Corollary 1.1. For every i ≥ 0, we have Zi ⊆ Zi+1.

Corollary 1.2. The projection of DASWregion onto the game states is a superset of the ASW region.

Following the approach used in [de Alfaro et al., 2007], we note the complexity of Alg. 2 is quadratic in the size of V .

## 5 An Illustrative Example

We present a robot motion planning example over a 4 × 4 gridworld, shown in Fig. 4, to illustrate how a robot (P1) may use action deception in presence of an adversary (P2). The objective of the robot is to visit the two cells (3, 1) and (3, 3) containing the flags, while the task of the adversary is to prevent this. The readers familiar with Linear Temporal Logic (LTL) may recognize the above objective as a co-safe LTL specification ♦G1 ∧ ♦G2. The action set of the robot is A1 = {N, E, S, W, NE, NW, SW} while that of adversary is A2 = {N, E, S, W}, where N, E, S, W stand for north, east, south and west. At the start of the game, the adversary has incomplete information about the robot's action set as X0 = {N, E, S, W}. When the adversary observes the robot performing any of the actions from {NE, NW, SW}, he updates his perception to X1 = A1.

A game on graph representing above scenario can be constructed using the product operation given in [Baier and Katoen, 2008, Def. 4.16]. Every game state is a tuple (x1, y1, x2, y2, t, q) where xi, yi for i = 1, 2 denote the cell that P1 and P2 occupy, t represents the player who chooses the next move and q denotes a state of a deterministic finite automaton that keeps track of the progress P1 has made towards completion of her objective. The resulting game has 44 × 2 × 4 = 2048 states. We mark the states where P1 or P2 collide with an obstacle or with each other as the losing states for both players and, therefore, any action that leads to such states is disabled. Given the game on graph, a hypergame graph is constructed according to Def. 4. The hypergame graph has 2048×2 = 4096 states because the adversary has two information states; X0 and X1.

Figure 4: A game between P1 (angel) and P2 (demon).

![Image](https://ijcai.org/proceedings/2020/fulltext/31/image_000003_cd7619f7d45ec3e061ce699a9739e5eac550281f6f805395230727f47d077664.png)

When Alg. 2 is applied to the above hypergame graph, 2106 out of 4096 states are identified as DASW states. The projection of DASW states onto game state space results in 1172 states, while the ASW region has the size of 934 states. This means that 1172 - 934 = 238 game states that were not almost-sure winning for P1 became winning for her, when P1 uses the DASW strategy.

## 6 Discussion and Conclusion

In this paper, we introduce a hypergame model to represent the interactions between two players with asymmetric information about their action capabilities. Given this model, we present an algorithm to synthesize action-deceptive strategies in a two-player turn-based zero-sum reachability game, where P2 starts with incomplete information about the P1's action capabilities. The synthesized strategy has two desirable properties. First, the DASW strategy is guaranteed to satisfy the reachability objective with probability one. Second, it is at least as powerful as the ASW strategy, because the DASW region is a superset of the ASW region. It worth noting that another game model of asymmetric information is Bayesian game, in which players have a Bayesian view of the types of others given their incomplete information. Our choice of hypergame model over Bayesian game model is motivated by the fact that a hypergame does not require consistency of priors that is assumed by Bayesian games [Halpern, 2002; Morris, 1995], and it also allows us to consider non-Bayesian players. Future work will focus on investigating action deception within hypergames with temporal logic payoffs and partial observations-that is, players have imperfect information about the history of games.

## Acknowledgements

This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) under Agreement No. HR00111990015.

## References

1. [Baier and Katoen, 2008] Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT press, 2008.
2. [Bennett, 1977] PG Bennett. Toward a theory of hyper- games. Omega, 5(6):749-751, jan 1977.
3. [Bernet et al., 2002] Julien Bernet, David Janin, and Igor Walukiewicz. Permissive strategies: from parity games to safety games. RAIRO -Theoretical Informatics and Ap- plications, 36(3):261-275, 2002.
4. [Bloem et al., 2012] Roderick Bloem, Barbara Jobstmann, Nir Piterman, Amir Pnueli, and Yaniv Sa'ar. Synthesis of reactive(1) designs. Journal of Computer and System Sciences, 78(3):911 -938, 2012. In Commemoration of Amir Pnueli. [de Alfaro et al., 2007] Luca de Alfaro, Thomas A Hen- zinger, and Orna Kupferman. Concurrent reachability games. Theoretical Computer Science, 386(3):188-217, 2007.
5. [Ettinger and Jehiel, 2010] David Ettinger and Philippe Je- hiel. A theory of deception. American Economic Journal: Microeconomics, 2(1):1-20, February 2010.
6. [Fainekos et al., 2009] Georgios E. Fainekos, Antoine Gi- rard, Hadas Kress-Gazit, and George J. Pappas. Tempo- ral logic motion planning for dynamic robots. Automatica, 45(2):343 -352, 2009.
7. [Gharesifard and Cortés, 2014] Bahman Gharesifard and Jorge Cortés. Stealthy deception in hypergames under informational asymmetry. IEEE Trans. Syst. Man, Cybern. Syst., 44(6):785-795, 2014.
8. [Gutierrez et al., 2015] Christopher N Gutierrez, Saurabh Bagchi, H Mohammed, and Jeff Avery. Modeling Decep- tion In Information Security As A Hypergame-A Primer. In Proc. 16th Annu. Inf. Secur. Symp., page 41. CERIAS- Purdue University, 2015.
9. [Halpern, 2002] Joseph Y. Halpern. Characterizing the com- mon prior assumption. Journal of Economic Theory, 106(2):316 -355, 2002.
10. [Harsanyi, 1967] John C. Harsanyi. Games with Incomplete Information Played by "Bayesian" Players, I-III Part I. The Basic Model. Management Science, 1967.
11. [Kovach, 2016] Nicholas S Kovach. A Temporal Framework for Hypergame Analysis of Cyber Physical Systems in Contested Environments. Technical report, Air Force In- stitute of Technology, 2016.
12. [Kulkarni and Fu, 2019] Abhishek Ninad Kulkarni and Jie Fu. Opportunistic synthesis in reactive games under in- formation asymmetry. CoRR, abs/1906.05847, 2019.
13. [Mazala, 2002] René Mazala. Infinite Games, pages 23-38. Springer Berlin Heidelberg, Berlin, Heidelberg, 2002.
14. [Morris, 1995] Stephen Morris. The common prior assump- tion in economic theory. Economics and Philosophy, 11(2):227-253, 1995.
15. [Pnueli and Rosner, 1989] A Pnueli and R Rosner. On the synthesis of a reactive module. pages 179-190, 1989.
16. [Ramadge and Wonham, 1989] P. J. G. Ramadge and W. M. Wonham. The control of discrete event systems. Proceed- ings of the IEEE, 77(1):81-98, Jan 1989.
17. [Rasmusen, 1989] Eric Rasmusen. Games and information: An introduction to game theory. Number 519.3/R22g. Blackwell Oxford, 1989.