Security games on a plane
Jiarui Gan, Bo An, Yevgeniy Vorobeychik, Brian Gauch

Citation
Jiarui Gan, Bo An, Yevgeniy Vorobeychik, Brian Gauch. "Security games on a plane". AAAI Conference on Artificial Intelligence, 2017.

Abstract
Most existing models of Stackelberg security games ignore the underlying topology of the space in which targets and defence resources are located. As a result, allocation of resources is restricted to a discrete collection of exogenously defined targets. However, in many practical security settings, defense resources can be located on a continuous plane. Better defense solutions could therefore be potentially achieved by placing resources in a space outside of actual targets (e.g., between targets). To address this limitation, we propose a model called Security Game on a Plane (SGP) in which targets are distributed on a 2-dimensional plane, and security resources, to be allocated on the same plane, protect targets within a certain effective distance. We investigate the algorithmic aspects of SGP. We find that computing a strong Stackelberg equilibrium of an SGP is NP-hard even for zerosum games, and these are inapproximable in general. On the positive side, we find an exact solution technique for general SGPs based on an existing approach, and develop a PTAS (polynomial-time approximation scheme) for zero-sum SGP to more fundamentally overcome the computational obstacle. Our experiments demonstrate the value of considering SGP and effectiveness of our algorithms.

Electronic downloads

Internal. This publication has been marked by the author for use only by the author.

Citation formats

• HTML

  Jiarui Gan, Bo An, Yevgeniy Vorobeychik, Brian Gauch. <a
  href="http://www.cps-forces.org/pubs/255.html"
  >Security games on a plane</a>, AAAI Conference on
  Artificial Intelligence, 2017.

• Plain text

  Jiarui Gan, Bo An, Yevgeniy Vorobeychik, Brian Gauch.
  "Security games on a plane". AAAI Conference on
  Artificial Intelligence, 2017.

• BibTeX

  @inproceedings{GanAnVorobeychikGauch17_SecurityGamesOnPlane,
      author = {Jiarui Gan and Bo An and Yevgeniy Vorobeychik and
                Brian Gauch},
      title = {Security games on a plane},
      booktitle = {AAAI Conference on Artificial Intelligence},
      year = {2017},
      abstract = {Most existing models of Stackelberg security games
                ignore the underlying topology of the space in
                which targets and defence resources are located.
                As a result, allocation of resources is restricted
                to a discrete collection of exogenously defined
                targets. However, in many practical security
                settings, defense resources can be located on a
                continuous plane. Better defense solutions could
                therefore be potentially achieved by placing
                resources in a space outside of actual targets
                (e.g., between targets). To address this
                limitation, we propose a model called Security
                Game on a Plane (SGP) in which targets are
                distributed on a 2-dimensional plane, and security
                resources, to be allocated on the same plane,
                protect targets within a certain effective
                distance. We investigate the algorithmic aspects
                of SGP. We find that computing a strong
                Stackelberg equilibrium of an SGP is NP-hard even
                for zerosum games, and these are inapproximable in
                general. On the positive side, we find an exact
                solution technique for general SGPs based on an
                existing approach, and develop a PTAS
                (polynomial-time approximation scheme) for
                zero-sum SGP to more fundamentally overcome the
                computational obstacle. Our experiments
                demonstrate the value of considering SGP and
                effectiveness of our algorithms. },
      URL = {http://cps-forces.org/pubs/255.html}
  }
  

Posted by Waseem Abbas on 2 Mar 2017.
Groups: forces
For additional information, see the Publications FAQ or contact webmaster at cps-forces org.