Article ID Journal Published Year Pages File Type
4959121 Computers & Operations Research 2017 26 Pages PDF
Abstract
This paper investigates efficient computation schemes for allocating two defensive resources to multiple sites to protect against possible attacks by an adversary. The availability of the two resources is constrained and the effectiveness of each may vary over the sites. The problem is formulated as a two-person zero-sum game with particular piecewise linear utility functions: the expected damage to a site that is attacked linearly decreases in the allocated resource amounts up to a point that a site is fully protected. The utility of the attacker, equivalently the defender's disutility, is the total expected damage over all sites. A fast algorithm is devised for computing the game's Nash equilibria; it is shown to be more efficient in practice than both general purpose linear programming solvers and a specialized method developed in the mid-1980s. To develop the algorithm, optimal solution properties are explored.
Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, , ,