Get me to my GATE on time: Efficiently solving general-sum bayesian threat screening games

Threat Screening Games (TSGs) are used in domains where there is a set of individuals or objects to screen with a limited amount of screening resources available to screen them. TSGs are broadly applicable to domains like airport passenger screening, stadium screening, cargo container screening, etc...

Full description

Saved in:
Bibliographic Details
Main Authors: SCHLENKER, Aaron, BROWN, Matthew, SINHA, Arunesh, TAMBE, Milind, MEHTA, Ruta
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2016
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/4664
https://ink.library.smu.edu.sg/context/sis_research/article/5667/viewcontent/GATE_GeneralSumTSGs_1_.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-5667
record_format dspace
spelling sg-smu-ink.sis_research-56672020-01-02T07:16:33Z Get me to my GATE on time: Efficiently solving general-sum bayesian threat screening games SCHLENKER, Aaron BROWN, Matthew SINHA, Arunesh TAMBE, Milind MEHTA, Ruta Threat Screening Games (TSGs) are used in domains where there is a set of individuals or objects to screen with a limited amount of screening resources available to screen them. TSGs are broadly applicable to domains like airport passenger screening, stadium screening, cargo container screening, etc. Previous work on TSGs focused only on the Bayesian zero-sum case and provided the MGA algorithm to solve these games. In this paper, we solve Bayesian general-sum TSGs which we prove are NP-hard even when exploiting a compact marginal representation. We also present an algorithm based upon a adversary type hierarchical tree decomposition and an efficient branch-and-bound search to solve Bayesian generalsum TSGs. With this we provide four contributions: (1) GATE, the first algorithm for solving Bayesian general-sum TSGs, which uses hierarchical type trees and a novel branch-and-bound search, (2) the Branch-and-Guide approach which combines branch-and-bound search with the MGA algorithm for the first time, (3) heuristics based on properties of TSGs for accelerated computation of GATE, and (4) experimental results showing the scalability of GATE needed for real-world domains. 2016-09-02T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/4664 info:doi/10.3233/978-1-61499-672-9-1476 https://ink.library.smu.edu.sg/context/sis_research/article/5667/viewcontent/GATE_GeneralSumTSGs_1_.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Databases and Information Systems
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Databases and Information Systems
spellingShingle Databases and Information Systems
SCHLENKER, Aaron
BROWN, Matthew
SINHA, Arunesh
TAMBE, Milind
MEHTA, Ruta
Get me to my GATE on time: Efficiently solving general-sum bayesian threat screening games
description Threat Screening Games (TSGs) are used in domains where there is a set of individuals or objects to screen with a limited amount of screening resources available to screen them. TSGs are broadly applicable to domains like airport passenger screening, stadium screening, cargo container screening, etc. Previous work on TSGs focused only on the Bayesian zero-sum case and provided the MGA algorithm to solve these games. In this paper, we solve Bayesian general-sum TSGs which we prove are NP-hard even when exploiting a compact marginal representation. We also present an algorithm based upon a adversary type hierarchical tree decomposition and an efficient branch-and-bound search to solve Bayesian generalsum TSGs. With this we provide four contributions: (1) GATE, the first algorithm for solving Bayesian general-sum TSGs, which uses hierarchical type trees and a novel branch-and-bound search, (2) the Branch-and-Guide approach which combines branch-and-bound search with the MGA algorithm for the first time, (3) heuristics based on properties of TSGs for accelerated computation of GATE, and (4) experimental results showing the scalability of GATE needed for real-world domains.
format text
author SCHLENKER, Aaron
BROWN, Matthew
SINHA, Arunesh
TAMBE, Milind
MEHTA, Ruta
author_facet SCHLENKER, Aaron
BROWN, Matthew
SINHA, Arunesh
TAMBE, Milind
MEHTA, Ruta
author_sort SCHLENKER, Aaron
title Get me to my GATE on time: Efficiently solving general-sum bayesian threat screening games
title_short Get me to my GATE on time: Efficiently solving general-sum bayesian threat screening games
title_full Get me to my GATE on time: Efficiently solving general-sum bayesian threat screening games
title_fullStr Get me to my GATE on time: Efficiently solving general-sum bayesian threat screening games
title_full_unstemmed Get me to my GATE on time: Efficiently solving general-sum bayesian threat screening games
title_sort get me to my gate on time: efficiently solving general-sum bayesian threat screening games
publisher Institutional Knowledge at Singapore Management University
publishDate 2016
url https://ink.library.smu.edu.sg/sis_research/4664
https://ink.library.smu.edu.sg/context/sis_research/article/5667/viewcontent/GATE_GeneralSumTSGs_1_.pdf
_version_ 1770574957060816896