Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems

In this paper we address game theory problems arising in the context of network se-curity. In traditional game theory problems, given a defender and an attacker, one searches formixed strategies which minimize a linear payoff functional. In the problems addressed in thispaper an additional quadratic term is added to the minimization problem. Such term representsswitching costs, i.e., the costs for the defender of switching from a given strategy to another oneat successive rounds of a Nash game. The resulting problems are nonconvex QP ones with linearconstraints and turn out to be very challenging. We will show that the most recent approaches forthe minimization of nonconvex QP functions over polytopes, including commercial solvers such as CPLEX and GUROBI, are unable to solve to optimality even test instances with n= 50 variables. Forthis reason, we propose to extend with them the current benchmark set of test instances for QPproblems. We also present a spatial branch-and-bound approach for the solution of these prob-lems, where a predominant role is played by an optimality-based domain reduction, with multiplesolutions of LP problems at each node of the branch-and-bound tree. Of course, domain reductionsare standard tools in spatial branch-and-bound approaches. However, our contribution lies in theobservation that, from the computational point of view, a rather aggressive application of thesetools appears to be the best way to tackle the proposed instances. Indeed, according to our exper-iments, while they make the computational cost per node high, this is largely compensated by therather slow growth of the number of nodes in the branch-and-bound tree, so that the proposedapproach strongly outperforms the existing solvers for QP problems.