---
title: "Efficiently Solving Joint Activity Based Security Games"
authors:
  - "Eric Anyung Shieh"
  - "Manish Jain"
  - "Albert Xin Jiang"
  - "Milind Tambe"
doi: ""
url: "https://ijcai.org/proceedings/2013/59"
pdf: "https://ijcai.org/proceedings/2013/0059.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "346-351"
track: ""
keywords:
---

# Efficiently Solving Joint Activity Based Security Games

Eric Anyung Shieh, Manish Jain, Albert Xin Jiang, Milind Tambe

*Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence*, pages 346-351.

## Abstract

Despite recent successful real-world deployments of Stackelberg Security Games (SSGs), scale-up remains a fundamental challenge in this field. The latest techniques do not scale-up to domains where multiple defenders must coordinate time-dependent joint activities. To address this challenge, this paper presents two branch-and-price algorithms for solving SSGs, SMARTO and SMARTH, with three novel features: (i) a column-generation approach that uses an ordered network of nodes (determined by solving the traveling salesman problem) to generate individual defender strategies; (ii) exploitation of iterative reward shaping of multiple coordinating defender units to generate coordinated strategies; (iii) generation of tighter upper-bounds for pruning by solving security games that only abide by key scheduling constraints. We provide extensive experimental results and formal analyses.