# Imitative Follower Deception in Stackelberg Games

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2019.

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

- [Auctions Between Regret-Minimizing Agents](https://mlsanity.com/paper/2110.11855/) (2021)
- [How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agents](https://mlsanity.com/paper/2112.07640/) (2021)
- [Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions](https://mlsanity.com/paper/2408.08272/) (2024)
- [Learning to Manipulate a Commitment Optimizer](https://mlsanity.com/paper/2302.11829/) (2023)
- [Optimal Private Payoff Manipulation against Commitment in Extensive-form Games](https://mlsanity.com/paper/2206.13119/) (2022)
- [Commitment with Signaling under Double-sided Information Asymmetry](https://mlsanity.com/paper/2212.11446/) (2022)
- [The Art of Manipulation: Threat of Multi-Step Manipulative Attacks in Security Games](https://mlsanity.com/paper/2202.13424/) (2022)
- [Mixed Strategies for Security Games with General Defending Requirements](https://mlsanity.com/paper/2204.12158/) (2022)
- [Decentralized Online Learning in General-Sum Stackelberg Games](https://mlsanity.com/paper/2405.03158/) (2024)

## Abstract (arXiv)

Information uncertainty is one of the major challenges facing applications of game theory. In the context of Stackelberg games, various approaches have been proposed to deal with the leader's incomplete knowledge about the follower's payoffs, typically by gathering information from the leader's interaction with the follower. Unfortunately, these approaches rely crucially on the assumption that the follower will not strategically exploit this information asymmetry, i.e., the follower behaves truthfully during the interaction according to their actual payoffs. As we show in this paper, the follower may have strong incentives to deceitfully imitate the behavior of a different follower type and, in doing this, benefit significantly from inducing the leader into choosing a highly suboptimal strategy. This raises a fundamental question: how to design a leader strategy in the presence of a deceitful follower? To answer this question, we put forward a basic model of Stackelberg games with (imitative) follower deception and show that the leader is indeed able to reduce the loss due to follower deception with carefully designed policies. We then provide a systematic study of the problem of computing the optimal leader policy and draw a relatively complete picture of the complexity landscape; essentially matching positive and negative complexity results are provided for natural variants of the model. Our intractability results are in sharp contrast to the situation with no deception, where the leader's optimal strategy can be computed in polynomial time, and thus illustrate the intrinsic difficulty of handling follower deception. Through simulations we also examine the benefit of considering follower deception in randomly generated games.