Imitative Follower Deception in Stackelberg Games
Imitative Follower Deception in Stackelberg Games
复制标题
DOI：
10.1145/3328526.3329629
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Jiarui Gan;Haifeng Xu;Qingyu Guo;Long Tran-Thanh;Zinovi Rabinovich;M. Wooldridge
中科院分区：
文献类型：
--
作者：
Jiarui Gan;Haifeng Xu;Qingyu Guo;Long Tran-Thanh;Zinovi Rabinovich;M. Wooldridge
信息不确定性是博弈论应用面临的主要挑战之一。在Stackelberg博弈的背景下，已经提出了各种方法来处理领导者对追随者收益的不完整知识，通常是通过收集领导者与追随者的互动信息。不幸的是，这些方法主要依赖于以下假设，即追随者不会战略性地利用这种信息不对称，即，跟随者在互动过程中根据他们的实际收益表现真实。正如我们在本文中所展示的，追随者可能有强烈的动机去欺骗性地模仿不同类型的追随者的行为，并且在这样做的过程中，从诱导领导者选择高度次优的策略中获益匪浅。这就提出了一个根本性的问题：在一个欺骗性的追随者面前，如何设计一个领导者的策略？为了回答这个问题，我们提出了一个基本模型的Stackelberg游戏（模仿）的追随者欺骗，并表明领导者确实能够减少损失，由于追随者欺骗精心设计的政策。然后，我们提供了一个系统的研究问题的计算最优的领导者的政策，并绘制了一个相对完整的图片的复杂性景观，基本上匹配的积极和消极的复杂性的结果提供了自然的变种的模型。我们的棘手的结果形成鲜明对比的情况下，没有欺骗，领导者的最优策略可以在多项式时间内计算，从而说明处理追随者欺骗的内在困难。通过模拟，我们还研究了随机生成的游戏中考虑追随者欺骗的好处。
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.