@conference {1500313,
title = {The Price of Usability: Designing Operationalizable Strategies for Security Games },
booktitle = {27th International Joint Conference on Artificial Intelligence (IJCAI)},
year = {2018},
abstract = {We consider the problem of allocating scarce security resources among heterogeneous targets to
thwart a possible attack. It is well known that deterministic solutions to this problem being highly predictable are severely suboptimal. To mitigate this
predictability, the game-theoretic security game
model was proposed which randomizes over pure
(deterministic) strategies, causing confusion in the
adversary. Unfortunately, such mixed strategies
typically randomize over a large number of strategies, requiring security personnel to be familiar
with numerous protocols, making them hard to operationalize. Motivated by these practical considerations, we propose an easy to use approach for
computing strategies that are easy to operationalize
and that bridge the gap between the static solution
and the optimal mixed strategy. These strategies
only randomize over an optimally chosen subset of
pure strategies whose cardinality is selected by the
defender, enabling them to conveniently tune the
trade-off between ease of operationalization and efficiency using a single design parameter. We show
that the problem of computing such operationalizable strategies is NP-hard, formulate it as a mixedinteger optimization problem, provide an algorithm
for computing ✏-optimal equilibria, and an efficient
heuristic. We evaluate the performance of our approach on the problem of screening for threats at
airport checkpoints and show that the Price of Usability, i.e., the loss in optimality to obtain a strategy that is easier to operationalize, is typically not
high.},
author = {Mc Carthy, Sara Marie and Corine M. Laan and Kai Wang and Vayanos, Phebe and Sinha, Arunesh and Tambe, Milind}
}