Law enforcement agencies frequently must allocate limited resources
to protect targets embedded in a network, such as important buildings in a city road network. Since intelligent attackers may observe
and exploit patterns in the allocation, it is crucial that the allocations be randomized. We cast this problem as an attacker-defender
Stackelberg game: the defender’s goal is to obtain an optimal mixed
strategy for allocating resources. The defender’s strategy space is
exponential in the number of resources, and the attacker’s exponential in the network size. Existing algorithms are therefore useless
for all but the smallest networks.
We present a solution approach based on two key ideas: (i) a
polynomial-sized game model obtained via an approximation of
the strategy space, solved efficiently using a linear program; (ii)
two efficient techniques that map solutions from the approximate
game to the original, with proofs of correctness under certain assumptions. We present in-depth experimental results, including an
evaluation on part of the Mumbai road network.