Recently, game theory has been shown to be useful for reasoning about real-world security settings where security forces must protect critical assets from potential adversaries. In fact, there
have been a number of deployed real-world applications of game theory for security (e.g., ARMOR at Los Angeles International Airport and IRIS for the Federal Air Marshals Service). Here,
the objective is for the security force to utilize its limited resources to best defend their critical
An important factor in these real-world security settings is that the adversaries involved are
humans who may not behave according to the standard assumptions of game-theoretic models.
There are two key shortcomings of the approaches currently employed in these recent applications. First, human adversaries may not make the predicted rational decision. In such situations,
where the security force has optimized against a perfectly rational opponent, a deviation by the
human adversary can lead to adverse affects on the security force’s predicted outcome. Second,
human adversaries are naturally creative and security domains are highly dynamic, making enumeration of all potential threats a practically impossible task and solving the resulting game, with
current leading approaches, would be intractable.
My thesis contributes to a very new area that combines algorithmic and experimental gametheory. Indeed, it examines a critical problem in applying game-theoretic techniques to situations where perfectly rational solvers must address human adversaries. In doing so it advances the
study and reach of game theory to domains where software agents and humans may interact.
More specifically, to address the first shortcoming, my thesis presents two separate algorithms
to address potential deviations from the predicted rational decision by human adversaries. Experimental results, from a simulation that is motivated by a real-world security domain at Los
Angeles International airport, demonstrated that both of my approaches outperform the currently
deployed optimal algorithms which utilize standard game-theoretic assumptions and additional
alternative algorithms against humans. In fact, one of my approaches is currently under evaluation in a real-world application to aid in resource allocation decisions for the United States Coast
Towards addressing the second shortcoming of enumeration of a large number of potential
adversary threat capabilities, I introduce a new game-theoretic model for efficiency, which additionally generalizes the previously accepted model for security domains. This new game-theoretic
model for addressing human threat capabilities has seen real-world deployment and is under evaluation to aid the United States Transportation Security Administration in their resource allocation