To step beyond the first-generation deployments of attacker-defender
security games – for LAX Police, US FAMS and others – it is critical that we relax the assumption of perfect rationality of the human
adversary. Indeed, this assumption is a well-accepted limitation of
classical game theory and modeling human adversaries’ bounded
rationality is critical. To this end, quantal response (QR) has provided very promising results to model human bounded rationality.
However, in computing optimal defender strategies in real-world
security games against a QR model of attackers, we face difficulties
including (1) solving a nonlinear non-convex optimization problem
efficiently for massive real-world security games; and (2) addressing constraints on assigning security resources, which adds to the
complexity of computing the optimal defender strategy.
This paper presents two new algorithms to address these difficulties: GOSAQ can compute the globally optimal defender strategy against a QR model of attackers when there are no resource
constraints and gives an efficient heuristic otherwise; PASAQ in
turn provides an efficient approximation of the optimal defender strategy with or without resource constraints. These two novel algorithms are based on three key ideas: (i) use of a binary
search method to solve the fractional optimization problem efficiently, (ii) construction of a convex optimization problem through
a non-linear transformation, (iii) building a piecewise linear approximation of the non-linear terms in the problem. Additional
contributions of this paper include proofs of approximation bounds, detailed experimental results showing the advantages of GOSAQ
and PASAQ in solution quality over the benchmark algorithm (BRQR)
and the efficiency of PASAQ. Given these results, PASAQ is at the
heart of the PROTECT system, which is deployed for the US Coast
Guard in the port of Boston, and is now headed to other ports.