Safe Delivery of Critical Services in Areas with Volatile Security Situation via a Stackelberg Game Approach

Tien Mai, Arunesh SinhaarXiv 2022 · OpenReview

Abstract

Vaccine delivery in under-resourced locations with security risks is not just challenging but also life-threatening. The current COVID pandemic and the need to vaccinate have added even more urgency to this issue. Motivated by this problem, we propose a general framework to set up limited temporary (vaccination) centers that balance physical security and desired (vaccine) service coverage with limited resources. We set up the problem as a Stackelberg game between the centers' operator (defender) and an adversary, where the set of centers is not fixed a priori but is part of the decision output. This results in a mixed combinatorial and continuous optimization problem. As part of our scalable approximation of this problem, we provide a fundamental contribution by identifying general duality conditions of switching max and min when both discrete and continuous variables are involved. We perform detailed experiments to show that the solution proposed is scalable in practice.

Introduction

In conflict zones or under-resourced areas, setting up vaccination clinics is a double-edged sword. While essential for public health, these centers can become targets for insurgents or criminals. Existing security models usually assume the "targets" (like airports or infrastructure) are fixed. However, for mobile services like vaccine drives, the operator (the Defender) must choose a subset of locations to open from a large pool of candidates. This creates a "mixed" optimization challenge: a combinatorial problem (which centers to pick?) layered on top of a continuous one (how much security budget to give each center?). Furthermore, the model must account for fairness, ensuring that different geographical regions receive service and that security isn't unfairly concentrated in one spot.

Methodology

The authors frame this as a Stackelberg Security Game. In this setup, the Defender commits to a strategy first, and an Adversary observes and reacts.

Quantal Response (QR) Model

Instead of assuming the attacker is a perfect "robot" who always picks the absolute best target, the authors use a QR model. This assumes the attacker is "boundedly rational"—they are more likely to attack high-value targets but occasionally make "noisy" or suboptimal choices.

Piecewise Linear Approximation (PWLA)

To handle the complex math of the defender's utility, the authors break the continuous variables into segments to create a Mixed-Integer Linear Program (MILP). This approximation is crucial for transforming the non-linear objective into a solvable form.

Visualization of function approximations used in the PWLA approach.

The "Switched" Heuristic and Hybrid Algorithm

MILPs are notoriously slow for large-scale problems. The authors propose a "Switched" version of the problem using Lagrangian duality. To justify this, they provide a fundamental technical contribution: identifying specific conditions under which "max-min" equals "min-max" even when some variables are discrete (binary).

They combine the speed of this heuristic with the rigor of the MILP in a Hybrid Algorithm. The heuristic provides a fast, near-optimal solution, and the MILP is only used to "tighten" the solution if certain error bounds aren't met.

Algorithm 1: Binary Search Template for the BOPT solution.

Key Insights and Ideas

  • The Power of Selection: Choosing where to go is just as vital as how to defend. Experiments showed that selecting a smart subset of centers provides significantly higher rewards (up to 142% better) than trying to operate everywhere at once.
  • Minimax Equality for Discrete Variables: In optimization, swapping the order of "max" and "min" usually requires everything to be continuous and convex. The authors proved that for this specific class of security games, you can often swap them even with discrete "open/close" decisions. This theoretical win enables their fast heuristic.
  • Fairness Doesn't Have to Break the System: By adding "Fairness in Security Allocation" (FSA) constraints, the model prevents the system from "sacrificing" high-risk regions. The math ensures a baseline level of protection across all active zones without tanking overall efficiency.

Key Results

  • Immense Scalability: While standard MILP approaches struggle as the number of locations grows, the authors' hybrid algorithm solved problems with 5,000 potential centers in about 70 seconds.
  • Superior Performance: The Hybrid/Switched approach consistently outperformed "Two-Step" baselines (which pick centers first and then allocate security separately), providing 85%–96% larger rewards.
  • Heuristic Accuracy: The "Switched" heuristic produced the exact same results as the more complex Hybrid model in 178 out of 180 test cases, proving that their theoretical minimax assumptions hold up in practice.

Limitations and Future Work

The current model assumes the adversary perfectly observes the defender's marginal coverage. In reality, attackers might have imperfect information. Future work could explore online versions where the defender adapts as they learn more about the attacker's behavior over time. Additionally, the paper abstracts away fine-grained logistics like truck routes and cold-chain requirements; integrating these physical constraints would be the next step toward a field-ready tool.

Summary updated

Abstract

Vaccine delivery in under-resourced locations with security risks is not just challenging but also life threatening. The current COVID pandemic and the need to vaccinate have added even more urgency to this issue. Motivated by this problem, we propose a general framework to set-up limited temporary (vaccination) centers that balance physical security and desired (vaccine) service coverage with limited resources. We set-up the problem as a Stackelberg game between the centers operator (defender) and an adversary, where the set of centers is not fixed a priori but is part of the decision output. This results in a mixed combinatorial and continuous optimization problem. As part of our scalable approximation of this problem, we provide a fundamental contribution by identifying general duality conditions of switching max and min when both discrete and continuous variables are involved. We perform detailed experiments to show that the solution proposed is scalable in practice.
BibTeX
@misc{mai2022safe,
  author = {Tien Mai and Arunesh Sinha},
  title = {{Safe Delivery of Critical Services in Areas with Volatile Security Situation via a Stackelberg Game Approach}},
  year = {2022},
  eprint = {2204.11451},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2204.11451},
}
Figure