We propose, to the best of our knowledge, the first Security Game where a Defender is supported by a spatially uncertain alarm system which non-deterministically generates signals once a target is under attack. Spatial uncertainty is common when securing large environments, e.g., for wildlife protection. We show that finding the equilibrium for this game is FNP-hard even in the zero-sum case and we provide both an exact algorithm and a heuristic algorithm to deal with it. Without false positives and missed detections, the best patrolling strategy reduces to stay in a place, wait for a signal, and respond to it at best. This strategy is optimal even with non-negligible missed detection rates.

A security game model for environment protection in the presence of an alarm system

BASILICO, NICOLA;DE NITTIS, GIUSEPPE;GATTI, NICOLA
2015-01-01

Abstract

We propose, to the best of our knowledge, the first Security Game where a Defender is supported by a spatially uncertain alarm system which non-deterministically generates signals once a target is under attack. Spatial uncertainty is common when securing large environments, e.g., for wildlife protection. We show that finding the equilibrium for this game is FNP-hard even in the zero-sum case and we provide both an exact algorithm and a heuristic algorithm to deal with it. Without false positives and missed detections, the best patrolling strategy reduces to stay in a place, wait for a signal, and respond to it at best. This strategy is optimal even with non-negligible missed detection rates.
2015
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
9783319255934
9783319255934
Computer Science (all); Theoretical Computer Science
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1005028
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 1
social impact