B An, D Kempe, C Kiekintveld, E Shieh, S Singh, M Tambe, Y Vorobeychik
In Conference on Artificial Intelligence (AAAI 2012).
This is the author's version of the work.
Download
Abstract
Randomized first-mover strategies of Stackelberg games
are used in several deployed applications to allocate
limited resources for the protection of critical infrastructure.
Stackelberg games model the fact that a strategic attacker can
surveil and exploit the defender's strategy, and randomization
guards against the worst effects by making the defender less
predictable. In accordance with the standard game-theoretic
model of Stackelberg games, past work has typically assumed
that the attacker has perfect knowledge of the defender's
randomized strategy and will react correspondingly. In light
of the fact that surveillance is costly, risky, and delays an
attack, this assumption is clearly simplistic: attackers will
usually act on partial knowledge of the defender's strategies.
The attacker's imperfect estimate could present opportunities
and possibly also threats to a strategic defender.
In this paper, we therefore begin a systematic study of
security games with limited surveillance. We propose
a natural model wherein an attacker forms or updates a
belief based on observed actions, and chooses an optimal
response. We investigate the model both theoretically and
experimentally. In particular, we give mathematical programs
to compute optimal attacker and defender strategies for a
fixed observation duration, and show how to use them to
estimate the attacker's observation durations. Our experimental
results show that the defender can achieve significant
improvement in expected utility by taking the attacker's
limited surveillance into account, validating the motivation
of our work.
