Web of War
A screenshot of the SCARE software featured in Nature. IED attacks are in red, while predicted cache locations are in yellow.
The static asset protection problem (SAP) in a road network is that of allocating resources to protect vertices, given any possible behavior by an adversary determined to attack those assets. The dynamic asset protection (DAP) problem is a version of SAP where the asset is following a fixed and widely known route (e.g., a parade route) and needs to be protected. We formalize what it means for a given allocation of resources to be "optimal" for protecting a desired set of assets, and show that randomly allocating resources to a single edge cut in the road network solves this problem. Unlike SAP, we show that DAP is not only an NP-complete problem, but that approximating DAP is also NP-hard. We provide the GreedyDAP heuristic algorithm to solve DAP and show experimentally that it works well in practice, using road network data for real cities.
Military planners have long used war games to plan for future conflicts. Beginning in the 1950s, defense analysts began to develop computer-based models to predict the outcomes of military battles that incorporated elements of game theory. Such models were often restricted to two opposing forces, and often had a strict win-lose resolution. Today, defense analysts face situations that are more complex, not only in that conflicts may involve several opposing groups within a region, but also in that military actions are only part of an array of options available in trying to foster stable, peaceful conditions. For example, in the current conflict in Afghanistan, analysts must try to estimate how particular actions by their forces—building schools, burning drug crops, or performing massive security sweeps—will affect interactions between the many diverse ethnic groups in the region. We discuss one approach to addressing this prediction problem in which possible outcomes are explored through computer-based virtual-world environments.