2020/02/28 by Giampaolo Liuzzi, Marco Locatelli, Liuzzi, Giampaolo +5 · 1 citation
Decision Sciences · Engineering · #FOS: Mathematics #Game Theory and Applications #Guidance and Control Systems #Infrastructure Resilience and Vulnerability Analysis #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2002.12599
openalex publication_date 2020/02/28 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
In this paper we address game theory problems arising in the context of\nnetwork security. In traditional game theory problems, given a defender and an\nattacker, one searches for mixed strategies which minimize a linear payoff\nfunctional. In the problems addressed in this paper an additional quadratic\nterm is added to the minimization problem. Such term represents switching\ncosts, i.e., the costs for the defender of switching from a given strategy to\nanother one at successive rounds of a Nash game. The resulting problems are\nnonconvex QP ones with linear constraints and turn out to be very challenging.\nWe will show that the most recent approaches for the minimization of nonconvex\nQP functions over polytopes, including commercial solvers such as CPLEX and\nGUROBI, are unable to solve to optimality even test instances with n = 50\nvariables. For this reason, we propose to extend with them the current\nbenchmark set of test instances for QP problems. We also present a spatial\nbranch-and-bound approach for the solution of these problems, where a\npredominant role is played by an optimality-based domain reduction, with\nmultiple solutions of LP problems at each node of the branch-and-bound tree. Of\ncourse, domain reductions are standard tools in spatial branch-and-bound\napproaches. However, our contribution lies in the observation that, from the\ncomputational point of view, a rather aggressive application of these tools\nappears to be the best way to tackle the proposed instances. Indeed, according\nto our experiments, while they make the computational cost per node high, this\nis largely compensated by the rather slow growth of the number of nodes in the\nbranch-and-bound tree, so that the proposed approach strongly outperforms the\nexisting solvers for QP problems.\n