Synthesis of Deceptive Strategies in Reachability Games with Action Misperception

Abhishek Ninad Kulkarni, Jie FuIJCAI 2020 · DOI

TL;DR

This paper introduces a novel framework for synthesizing "deceptive" winning strategies in reachability games where one player (P2) has incomplete and evolving information about the other player's (P1) capabilities. They propose a dynamic hypergame model and an algorithm to find these deceptive strategies, showing they can be more powerful than standard strategies by turning losing states into winning ones.

What Problem Does This Paper Address?

In many real-world scenarios, like robotics or cybersecurity, players don't have perfect information about each other's actions or capabilities. Traditional game theory often assumes complete and symmetric information, leading to algorithms for synthesizing "winning" strategies. However, when one player (P1) knows that the other player (P2) has a limited or incorrect understanding of P1's actions (misperception), P1 might be able to exploit this to her advantage. The core problem is: can P1 strategically manipulate P2's perception to achieve her goals, even from states that would normally be losing? This paper tackles this by formalizing "action deception" in reachability games and developing methods to synthesize such strategies.

Methods

The authors introduce a dynamic hypergame model on graph to capture the evolving misperception of Player 2 (P2). This model extends standard game-on-graph representations by including states that represent not just the game's current situation but also P2's current belief about P1's actions. P1, being aware of P2's misperception and P2's inference mechanism (how P2 updates their beliefs), can then strategize within this hypergame.

They propose a fixed-point algorithm to compute the "Deceptive Almost-Sure Winning (DASW)" region. This algorithm iteratively identifies states from which P1 can guarantee a win, even considering P2's evolving misperception. The algorithm is inspired by existing methods for computing standard "Almost-Sure Winning (ASW)" regions but is adapted to account for the dynamic information asymmetry.

Datasets

Not discussed in the paper. The paper uses a running example of a game on a graph and a robot motion planning scenario on a gridworld for illustration.

Key Insights and Ideas

  • Deception as a Strategic Tool: The paper demonstrates that intentionally misleading an opponent about one's capabilities can be a powerful strategy, turning seemingly losing positions into winning ones.
  • Dynamic Misperception: The key innovation is modeling how P2's beliefs about P1's actions change over time as P1 uses previously unknown actions. This dynamic aspect is crucial for realistic adversarial scenarios.
  • Hypergame Formalism: Using hypergames allows for a formal representation of players reasoning about each other's reasoning and beliefs, which is essential for understanding deceptive strategies.
  • DASW vs. ASW: The paper shows that DASW strategies are at least as powerful as ASW strategies, meaning they can achieve wins in all states where ASW strategies can, and potentially more.

Key Results

  • The paper formally defines a dynamic hypergame model to represent reachability games with evolving action misperception.
  • They present an algorithm to compute the Deceptive Almost-Sure Winning (DASW) region and synthesize DASW strategies.
  • They prove that the DASW region is a superset of the standard ASW region, implying that deceptive strategies are at least as powerful as standard ones.
  • The paper demonstrates through an example that states that are losing for P1 under symmetric information can become winning states when P1 employs a deceptive strategy.
  • An illustrative example of a robot navigating an adversarial environment shows that incorporating deception can significantly expand the set of winning states for the robot.

Limitations and Future Work

  • Computational Complexity: While the algorithm is presented, its computational complexity for large games is not explicitly detailed, which is a common challenge in game synthesis.
  • P2's Inference Mechanism: The paper assumes a specific type of inference mechanism for P2. Exploring more complex or varied inference models could be a direction for future work.
  • Generalization: The current work focuses on reachability objectives. Extending the framework to other types of objectives (e.g., safety, liveness) would be a valuable next step.
  • Multi-player Games: The current model is for two-player games. Adapting it to scenarios with more than two players, each with potentially different information asymmetries, is a natural extension.

Summary updated

BibTeX
@inproceedings{kulkarni2020synthesis,
  author = {Abhishek Ninad Kulkarni and Jie Fu},
  title = {{Synthesis of Deceptive Strategies in Reachability Games with Action Misperception}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/31},
}
Figure