Timezone: »

 
Poster
Manipulating a Learning Defender and Ways to Counteract
Jiarui Gan · Qingyu Guo · Long Tran-Thanh · Bo An · Michael Wooldridge

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #224
in Theory -- Game Theory and Computational Economics »

In Stackelberg security games when information about the attacker's payoffs is uncertain, algorithms have been proposed to learn the optimal defender commitment by interacting with the attacker and observing their best responses. In this paper, we show that, however, these algorithms can be easily manipulated if the attacker responds untruthfully. As a key finding, attacker manipulation normally leads to the defender learning a maximin strategy, which effectively renders the learning attempt meaningless as to compute a maximin strategy requires no additional information about the other player at all. We then apply a game-theoretic framework at a higher level to counteract such manipulation, in which the defender commits to a policy that specifies her strategy commitment according to the learned information. We provide a polynomial-time algorithm to compute the optimal such policy, and in addition, a heuristic approach that applies even when the attacker's payoff space is infinite or completely unknown. Empirical evaluation shows that our approaches can improve the defender's utility significantly as compared to the situation when attacker manipulation is ignored.

Keywords: Game Theory and Computational Economics · Computational Complexity · Theory
[ Paper]  [ Poster] 

Author Information

Jiarui Gan (University of Oxford)
Qingyu Guo (Pinduoduo)
Long Tran-Thanh (University of Southampton)
Bo An (Nanyang Technological University)
Michael Wooldridge (Univ of Oxford)

More from the Same Authors