Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

10-2018

Abstract

Stackelberg Security Games (SSGs) have been adopted widely for modeling adversarial interactions, wherein scalability of equilibrium computation is an important research problem. While prior research has made progress with regards to scalability, many real world problems cannot be solved satisfactorily yet as per current requirements; these include the deployed federal air marshals (FAMS) application and the threat screening (TSG) problem at airports. We initiate a principled study of approximations in zero-sum SSGs. Our contribution includes the following: (1) a unified model of SSGs called adversarial randomized allocation (ARA) games, (2) hardness of approximation for zero-sum ARA, as well as for the FAMS and TSG sub-problems, (3) an approximation framework for zero-sum ARA with instantiations for FAMS and TSG using intelligent heuristics, and (4) experiments demonstrating the significant 1000x improvement in runtime with an acceptable loss.

Discipline

Programming Languages and Compilers | Software Engineering

Research Areas

Data Science and Engineering

Publication

Proceedings of the 9th Conference on Decision and Game Theory for Security: GameSec 2018, Seattle, USA, October 29-31

Volume

11199

First Page

432

Last Page

452

ISBN

978-3-030-01553-4

Identifier

10.1007/978-3-030-01554-1_25

Publisher

Springer Link

City or Country

Seattle, USA

Additional URL

https://doi.org/10.1007/978-3-030-01554-1_25

Download

Share

COinS