Ensuring that AI systems make strategic decisions aligned with the specified preferences in adversarial sequential interactions is a critical challenge for developing trustworthy AI systems, especially when the environment is stochastic and players' incomplete preferences leave some outcomes unranked. We study the problem of synthesizing preference-satisfying strategies in two-player stochastic games on graphs where players have opposite (possibly incomplete) preferences over a set of temporal goals. We represent these goals using linear temporal logic over finite traces (LTLf), which enables modeling the nuances of human preferences where temporal goals need not be mutually exclusive and comparison between some goals may be unspecified. We introduce a solution concept of non-dominated almost-sure winning, which guarantees to achieve a most preferred outcome aligned with specified preferences while maintaining robustness against the adversarial behaviors of the opponent. Our results show that strategy profiles based on this concept are Nash equilibria in the game where players are risk-averse, thus providing a practical framework for evaluating and ensuring stable, preference-aligned outcomes in the game. Using a drone delivery example, we demonstrate that our contributions offer valuable insights not only for synthesizing rational behavior under incomplete preferences but also for designing games that motivate the desired behavior from the players in adversarial conditions.

In this paper, we study planning in stochastic systems, modeled as Markov decision processes (MDPs), with preferences over temporally extended goals. Prior work on temporal planning with preferences assumes that the user preferences form a total order, meaning that every pair of outcomes are comparable with each other. In this work, we consider the case where the preferences over possible outcomes are a partial order rather than a total order. We first introduce a variant of deterministic finite automaton, referred to as a preference DFA, for specifying the user's preferences over temporally extended goals. Based on the order theory, we translate the preference DFA to a preference relation over policies for probabilistic planning in a labeled MDP. In this treatment, a most preferred policy induces a weak-stochastic nondominated probability distribution over the finite paths in the MDP. The proposed planning algorithm hinges on the construction of a multi-objective MDP. We prove that a weak-stochastic nondominated policy given the preference specification is Pareto-optimal in the constructed multi-objective MDP, and vice versa. Throughout the paper, we employ a running example to demonstrate the proposed preference specification and solution approaches. We show the efficacy of our algorithm using the example with detailed analysis, and then discuss possible future directions.

In this paper, we study the use of deception for strategic planning in adversarial environments. We model the interaction between the agent (player 1) and the adversary (player 2) as a two-player concurrent stochastic game in which the adversary has incomplete information about the agent’s task specification given as a temporal logic formula. During the interaction, the adversary can infer the agent’s intention from observations and adapt its strategy so as to prevent the agent from satisfying the objective. To plan against such an adaptive opponent, the agent must leverage its knowledge about the adversary’s incomplete information to influence the behavior of the opponent, and thereby be deceptive. To synthesize a deceptive strategy, we introduce a class of hypergame models that capture the interaction between the agent and its adversary given asymmetric, incomplete information. We develop a solution concept for this class of hypergames and show that the subjectively rationalizable strategy for the agent is deceptive and maximizes the probability of satisfying the task in temporal logic. Such a deceptive strategy is obtained by modeling the opponent’s evolving perception of the agent’s objective and integrating it into planning. This allows the agent to manipulate the opponent’s perception so as to induce the opponent into taking actions that benefit the agent. We demonstrate the effectiveness of our deceptive planning algorithm using robot motion planning examples with temporal logic objectives and design a detection mechanism to notify the agent of potential errors in modeling the adversary’s behavior. Note to Practitioners—Many security and defense applications employ deception mechanisms for strategic advantages. This work presents a game-theoretic framework for planning deceptive strategies in stochastic environments and shows that the opponent modeling plays a key role in the design of effective deception mechanisms. For applications to cyber-physical security, the practitioners can employ temporal logic for specifying security properties in the system and analyze defense with deception using the proposed methods.

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.