# Deceptive Labeling: Hypergames on Graphs for Stealthy Deception

arXiv: https://arxiv.org/abs/2004.05213 · HTML: https://mlsanity.com/paper/2004.05213/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Apr 2020.

## Built on by (most cited first, 6 of 6)

- [Deceptive Decision-Making Under Uncertainty](https://mlsanity.com/paper/2109.06740/) (2021)
- [Dynamic Coalition Structure Detection in Natural Language-based Interactions](https://mlsanity.com/paper/2502.16339/) (2025)
- [Deceptive Planning for Resource Allocation](https://mlsanity.com/paper/2206.01306/) (2022)
- [A Survey on Hypergame Theory: Modelling Misaligned Perceptions and Nested Beliefs for Multi-Agent Systems](https://mlsanity.com/paper/2507.19593/) (2025)
- [Game-Theoretic and Machine Learning-based Approaches for Defensive Deception: A Survey](https://mlsanity.com/paper/2101.10121/) (2021)
- [Optimal sensor deception in stochastic environments with partial observability to mislead a robot to a decoy goal](https://mlsanity.com/paper/2503.05972/) (2025)

## Abstract (arXiv)

With the increasing sophistication of attacks on cyber-physical systems, deception has emerged as an effective tool to improve system security and safety by obfuscating the attacker's perception. In this paper, we present a solution to the deceptive game in which a control agent is to satisfy a Boolean objective specified by a co-safe temporal logic formula in the presence of an adversary. The agent intentionally introduces asymmetric information to create payoff misperception, which manifests as the misperception of the labeling function in the game model. Thus, the adversary is unable to accurately determine which logical formula is satisfied by a given outcome of the game. We introduce a model called hypergame on graph to capture the asymmetrical information with one-sided payoff misperception. Based on this model, we present the solution of such a hypergame and use the solution to synthesize stealthy deceptive strategies. Specifically, deceptive sure winning and deceptive almost-sure winning strategies are developed by reducing the hypergame to a two-player game and one-player stochastic game with reachability objectives. A running example is introduced to demonstrate the game model and the solution concept used for strategy synthesis.