AI for Security Planning: A Game-Theoretic Approach

Dual Degree Project (DDP), IIT Bombay — computing optimal defender strategies for critical-infrastructure security, from static Stackelberg commitment (Phase I) to dynamic imperfect-information games solved with CFR and exact SPNE (Phase II).

Author: Anurag Deshpande · Supervisor: Prof. Swaprava Nath (CSE) · Centre for Machine Intelligence and Data Science, IIT Bombay

---

Motivation

Security of critical infrastructure and human assets — border infiltration, counter-terrorism, urban policing — demands patrol strategies that survive strategic adversaries. Conventional static or heuristic patrol plans are observable and exploitable. This project develops AI-driven security planning built on game theory: the defender commits to (or plays) a randomized strategy, and the adversary best-responds after observing it.

Methodology

Phase I — Static Stackelberg Security Games (SSGs). The defender-commitment problem is formulated as a Mixed-Integer Quadratic Program (MIQP), linearized to a MILP (DOBSS), and solved for optimal patrol plans. For the single-attacker-type case an LP-based method gives large runtime reductions. Approximation algorithms handle the general multi-type setup.

Phase II — Dynamic security games. Multi-round, simultaneous-move, zero-sum stochastic games with within-round imperfect information, represented exactly as imperfect-information extensive-form games (IIEFGs):

flowchart LR
    A[JSON game spec] --> B[EFG builder]
    B --> C[CFR solver<br/>approx. Nash eq.]
    B --> D[Backward-induction<br/>SPNE solver]
    C --> E[Comparison harness:<br/>does CFR give SPNE?]
    D --> E
    E --> F[Interactive game-tree<br/>visualizer]
    E --> G[Patrol-planning DSS<br/>+ scenario wargames]

Loading

The central theoretical question — when does CFR's equilibrium coincide with the subgame-perfect equilibrium? — is answered both theoretically and empirically: they agree on the equilibrium path and diverge off it.

Results

• DOBSS MILP solves the static SSG exactly; the single-type LP method achieves a significant runtime reduction over DOBSS at equal solution quality (report §4–5).
• The SPNE backward-induction solver runs domain-agnostically over the Markovian (state, round) lattice in sub-second time.
• CFR and SPNE agree on the equilibrium path across the calibrated scenario suite; off-path divergence is characterized (report §14).
• Four calibrated scenario wargames solved end-to-end; deployed as a tri-service decision-support demonstrator with Monte-Carlo-calibrated transitions and an interactive game-tree visualizer.

Full results with tables and equilibrium figures: addendum/main.pdf · complete 74-page report: report/main.pdf · browsable markdown version: docs/DDP_Complete_Report_PhaseI_II.md

How to run

pip install -r requirements.txt

# Phase I — DOBSS (MIQP→MILP) solver
python phase1-dobss/DOBSS_Security.py

# Phase II — JSON → EFG → CFR/SPNE pipeline
cd phase2/pipeline
python pipeline.py                 # build EFG and solve
python backward_induction_spne.py  # exact SPNE

# Naval patrol demonstrator (Streamlit app)
streamlit run phase2/naval-patrol/naval_patrol_app.py

Interactive tools (phase2/tools/*.html) are self-contained — open directly in a browser to build game JSONs or explore solved game trees.

To rebuild the documents:

cd report && pdflatex main && bibtex main && pdflatex main && pdflatex main
cd presentation && pdflatex main && pdflatex main
cd addendum && pdflatex main && pdflatex main

Repository structure

ddp-research/
├── report/            # Consolidated Phase I+II report (LaTeX + PDF, 74 pp)
├── presentation/      # Phase II Beamer talk (59 pp)
├── addendum/          # Results addendum: all tables, equilibrium figures (19 pp)
├── docs/              # Markdown version of the full report
├── phase1-dobss/      # Stackelberg/DOBSS MIQP→MILP solvers (Python + notebook)
└── phase2/
    ├── pipeline/      # JSON → EFG toolchain, CFR + SPNE, strategies, utils
    ├── cfr/           # CFR solver variants (incl. pure-Python CFR)
    ├── spne/          # Backward-induction SPNE solver + scenario JSONs
    ├── naval-patrol/  # Naval patrol demonstrator (Streamlit)
    └── tools/         # Self-contained HTML: JSON builders, game-tree visualizers

Citation

@mastersthesis{deshpande2026security,
  author  = {Deshpande, Anurag},
  title   = {Artificial Intelligence for Security Planning: A Game-Theoretic Approach},
  school  = {Indian Institute of Technology Bombay},
  year    = {2026},
  type    = {Dual Degree Thesis},
  note    = {Supervised by Prof. Swaprava Nath}
}

Contact

Anurag Deshpande · anuragdeshpande31@gmail.com · github.com/anurag-add