Imitative Follower Deception in Stackelberg Games

Jiarui Gan, Haifeng Xu, Qingyu Guo, Long Tran-Thanh, Zinovi Rabinovich, Michael J. Wooldridge

Abstract

In Stackelberg games, a leader commits to a strategy, and a follower responds optimally. Traditional models assume that the leader knows the follower's payoffs or can learn them through truthful interaction. This paper introduces the concept of imitative follower deception, where a strategic follower misrepresents their payoff structure (type) to manipulate the leader into choosing a strategy that benefits the follower. We demonstrate that while finding the optimal leader policy under such deception is NP-hard, the leader can mitigate utility losses by employing "menus" of mixed strategies.

Introduction: The Vulnerability of Commitment

Stackelberg games are foundational to applications ranging from airport security scheduling to economic contract design. In these settings, the "leader" (e.g., a security agency) commits to a randomized strategy, and the "follower" (e.g., a potential poacher or smuggler) observes this commitment before acting. A critical assumption in existing Bayesian Stackelberg Game (BSG) models is that the follower's type—representing their specific payoffs—is either known or will be revealed truthfully during interaction.

Payoff matrices for a defender and two poacher types (A and B) in a Bayesian Stackelberg game.

However, a strategic follower has a clear incentive to lie. By imitating a different type, they can trick the leader into a suboptimal commitment. For instance, a poacher might pretend to be a type that is easily deterred by a specific patrol pattern, leading the defender to shift resources away from the poacher's actual target. This paper formalizes this "imitative deception" and explores robust defense mechanisms.

Methodology: Menus and Mixed Policies

The authors model the interaction as a game where the follower’s type is drawn from a finite set. Instead of a single strategy, the leader commits to a policy (or "menu"): a mapping that assigns a specific strategy to every type the follower might report.

Complexity and Computation

The research provides a rigorous complexity analysis, proving that finding the optimal leader policy is NP-hard to even approximate within any meaningful ratio. This hardness stems from a reduction from the MAX-INDEPENDENT-SET problem. To address this, the authors propose:

  1. Mixed Integer Linear Programming (MILP): A formulation to compute optimal pure policies for general cases.
  2. Mixed Policies with Incentive Compatibility (IC): By allowing the leader to prescribe a distribution of outcomes for each reported type, the problem becomes more tractable. Surprisingly, while the pure strategy problem is NP-hard, the optimal mixed policy with IC constraints can be computed in polynomial time.

Experimental Evaluation

The proposed models were evaluated using simulations based on the covariance game model. The researchers varied parameters such as the number of actions, the number of follower types, and the correlation between leader and follower payoffs (ranging from zero-sum to uncorrelated).

The results indicate that ignoring the possibility of deception leads to significant utility losses for the leader. However, the "Deception-Aware" policies developed in this work significantly outperformed the standard Bayesian Stackelberg Equilibrium (BSE). The gap between the leader's utility in a "truthful" scenario versus a "deceptive" one narrowed considerably when optimized menus were employed.

Key Insights

  • The High Price of Deception: Failure to account for strategic misinformation can lead to unbounded losses.
  • The Power of Randomization: Mixed policies do more than just improve utility; they shift the computational complexity of the IC-constrained problem from NP-hard to polynomial time.
  • Counterintuitive Outcomes: In specific scenarios, such as certain variations of the Prisoner's Dilemma, follower deception can actually lead to a "win-win" where the leader's utility increases compared to a truthful interaction.

Conclusion and Future Directions

This work highlights a critical security flaw in standard Stackelberg models and provides a framework for robust decision-making. Future research should address the limitations of the current model, such as the assumption of a finite type space and the requirement for a known prior distribution of types. Transitioning these models into "online" settings, where the leader learns the follower's distribution while defending against active deception, remains a promising frontier for strategic game theory.

Summary updated

Abstract

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.
BibTeX
@inproceedings{gan2019imitative,
  author = {Jiarui Gan and Haifeng Xu and Qingyu Guo and Long Tran-Thanh and Zinovi Rabinovich and Michael J. Wooldridge},
  title = {{Imitative Follower Deception in Stackelberg Games}},
  booktitle = {EC},
  year = {2019},
  doi = {10.1145/3328526.3329629},
}
Figure