Overview
Research published on arXiv investigates the computational complexity of various fortification-interdiction games, specifically their completeness within the Polynomial Hierarchy. Fortification-interdiction games are characterized as tri-level adversarial scenarios where two opponents engage in successive actions: one to protect an infrastructure, another to disrupt it, and a third to utilize it for a specific purpose. While algorithmic solutions for these games are common, the rigorous location of these problems within the Polynomial Hierarchy has received limited investigation.
This study establishes the completeness status for several known fortification problems. The findings indicate that these problems are complete either for the $\Sigma^p_2$ or the $\Sigma^p_3$ class of the Polynomial Hierarchy. Furthermore, the Multi-level Fortification-Interdiction Knapsack Problem, when considering an arbitrary number of protection and interdiction rounds and unit fortification and attack weights, is shown to be complete for any level of the Polynomial Hierarchy. This latter result is identified as a foundational basis for future efforts to prove the completeness of other protection-interdiction games across different levels of the hierarchy.
Research Context
Fortification-interdiction games involve multiple adversarial agents interacting sequentially. Specifically, they are structured as tri-level games, where one entity fortifies an infrastructure, another interdicts or disrupts it, and a third uses the infrastructure. Existing literature contains numerous formulations and algorithmic approaches for these games. However, a gap in understanding their precise computational complexity, particularly their completeness within the Polynomial Hierarchy, has been noted.
Approach
The research adopted a theoretical approach to determine the completeness status of the selected fortification-interdiction problems. This involved proving their membership and hardness for specific complexity classes within the Polynomial Hierarchy. The methodology focused on analyzing the structural properties of these problems to rigorously place them within this hierarchy.
Findings
- The Tri-level Interdiction Knapsack Problem with unit fortification and attack weights was proven complete for either the $\Sigma^p_2$ or the $\Sigma^p_3$ class of the polynomial hierarchy.
- The Max-flow Interdiction Problem with Fortification was proven complete for either the $\Sigma^p_2$ or the $\Sigma^p_3$ class of the polynomial hierarchy.
- The Shortest Path Interdiction Problem with Fortification was proven complete for either the $\Sigma^p_2$ or the $\Sigma^p_3$ class of the polynomial hierarchy.
- The Multi-level Critical Node Problem with unit weights was proven complete for either the $\Sigma^p_2$ or the $\Sigma^p_3$ class of the polynomial hierarchy.
- A well-studied electric grid defense planning problem was proven complete for either the $\Sigma^p_2$ or the $\Sigma^p_3$ class of the polynomial hierarchy.
- The Multi-level Fortification-Interdiction Knapsack Problem, characterized by an arbitrary number of protection and interdiction rounds and unit fortification and attack weights, was proven complete for any level of the polynomial hierarchy.
These completeness proofs rigorously locate the specified fortification problems within the Polynomial Hierarchy.
Why This Matters
The establishment of completeness status for these fortification-interdiction games provides a rigorous understanding of their inherent computational difficulty. For instance, demonstrating that the Multi-level Fortification-Interdiction Knapsack Problem is complete for any level of the polynomial hierarchy offers a foundational basis. This can inform subsequent research aimed at proving the completeness of other protection-interdiction games across various levels of the Polynomial Hierarchy, thereby contributing to the theoretical understanding of complex adversarial problems.