A Stackelberg security Markov game based on partial information for strategic decision making against unexpected attacks

Silvia E. Albarran, Julio B. Clempner

Research output: Contribution to journalArticleResearchpeer-review

Abstract

© 2019 Elsevier Ltd This paper considers an important class of Stackelberg security problems, which is characterized by the fact that defenders and attackers have incomplete information at each stage about the value of the current state. The inability to observe the exact state is motivated by the fact that it is impossible to measure exactly the state variables of the defenders and attackers. Most existing approaches for computing Stackelberg security games provide no guarantee if the estimated model is inaccurate. In order to solve this drawback, this paper presents several important results. First, it provides a novel solution for computing the Stackelberg security games for multiple players, considering finite resource allocation in domains with incomplete information. This new model is restricted to a partially observable Markov model. Next, we suggest a two-step iterative proximal/gradient method for computing the Stackelberg equilibrium for the security game: in each step, the algorithm solves an independent convex nonlinear programming problem implementing a regularized penalty approach. Regularization ensures the convergence to one (unique) of the possible equilibria of the Stackelberg game. To make the problem computationally tractable, we define the c-variable method for partially observable Markov games. Third, we show by simulation that our proposed model overcomes the disadvantages of previous Stackelberg security games solvers. Hence, as our final contribution, we present a new random walk method based on partial information. A numerical example for protecting airports terminals suggests the effectiveness of the proposed method, presenting the resulting patrolling strategies and two different realizations of the Stackelberg security game employing the partially observable random walk algorithm.
Original languageAmerican English
Pages (from-to)408-419
Number of pages366
JournalEngineering Applications of Artificial Intelligence
DOIs
StatePublished - 1 May 2019

Fingerprint

Decision Making
Decision making
Airports
Gradient methods
Resource Allocation
Nonlinear programming
Resource allocation

Cite this

@article{91277d575d8c459d8b8cf30e1a6fbcc4,
title = "A Stackelberg security Markov game based on partial information for strategic decision making against unexpected attacks",
abstract = "{\circledC} 2019 Elsevier Ltd This paper considers an important class of Stackelberg security problems, which is characterized by the fact that defenders and attackers have incomplete information at each stage about the value of the current state. The inability to observe the exact state is motivated by the fact that it is impossible to measure exactly the state variables of the defenders and attackers. Most existing approaches for computing Stackelberg security games provide no guarantee if the estimated model is inaccurate. In order to solve this drawback, this paper presents several important results. First, it provides a novel solution for computing the Stackelberg security games for multiple players, considering finite resource allocation in domains with incomplete information. This new model is restricted to a partially observable Markov model. Next, we suggest a two-step iterative proximal/gradient method for computing the Stackelberg equilibrium for the security game: in each step, the algorithm solves an independent convex nonlinear programming problem implementing a regularized penalty approach. Regularization ensures the convergence to one (unique) of the possible equilibria of the Stackelberg game. To make the problem computationally tractable, we define the c-variable method for partially observable Markov games. Third, we show by simulation that our proposed model overcomes the disadvantages of previous Stackelberg security games solvers. Hence, as our final contribution, we present a new random walk method based on partial information. A numerical example for protecting airports terminals suggests the effectiveness of the proposed method, presenting the resulting patrolling strategies and two different realizations of the Stackelberg security game employing the partially observable random walk algorithm.",
author = "Albarran, {Silvia E.} and Clempner, {Julio B.}",
year = "2019",
month = "5",
day = "1",
doi = "10.1016/j.engappai.2019.03.010",
language = "American English",
pages = "408--419",
journal = "Engineering Applications of Artificial Intelligence",
issn = "0952-1976",
publisher = "Elsevier Ltd",

}

A Stackelberg security Markov game based on partial information for strategic decision making against unexpected attacks. / Albarran, Silvia E.; Clempner, Julio B.

In: Engineering Applications of Artificial Intelligence, 01.05.2019, p. 408-419.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A Stackelberg security Markov game based on partial information for strategic decision making against unexpected attacks

AU - Albarran, Silvia E.

AU - Clempner, Julio B.

PY - 2019/5/1

Y1 - 2019/5/1

N2 - © 2019 Elsevier Ltd This paper considers an important class of Stackelberg security problems, which is characterized by the fact that defenders and attackers have incomplete information at each stage about the value of the current state. The inability to observe the exact state is motivated by the fact that it is impossible to measure exactly the state variables of the defenders and attackers. Most existing approaches for computing Stackelberg security games provide no guarantee if the estimated model is inaccurate. In order to solve this drawback, this paper presents several important results. First, it provides a novel solution for computing the Stackelberg security games for multiple players, considering finite resource allocation in domains with incomplete information. This new model is restricted to a partially observable Markov model. Next, we suggest a two-step iterative proximal/gradient method for computing the Stackelberg equilibrium for the security game: in each step, the algorithm solves an independent convex nonlinear programming problem implementing a regularized penalty approach. Regularization ensures the convergence to one (unique) of the possible equilibria of the Stackelberg game. To make the problem computationally tractable, we define the c-variable method for partially observable Markov games. Third, we show by simulation that our proposed model overcomes the disadvantages of previous Stackelberg security games solvers. Hence, as our final contribution, we present a new random walk method based on partial information. A numerical example for protecting airports terminals suggests the effectiveness of the proposed method, presenting the resulting patrolling strategies and two different realizations of the Stackelberg security game employing the partially observable random walk algorithm.

AB - © 2019 Elsevier Ltd This paper considers an important class of Stackelberg security problems, which is characterized by the fact that defenders and attackers have incomplete information at each stage about the value of the current state. The inability to observe the exact state is motivated by the fact that it is impossible to measure exactly the state variables of the defenders and attackers. Most existing approaches for computing Stackelberg security games provide no guarantee if the estimated model is inaccurate. In order to solve this drawback, this paper presents several important results. First, it provides a novel solution for computing the Stackelberg security games for multiple players, considering finite resource allocation in domains with incomplete information. This new model is restricted to a partially observable Markov model. Next, we suggest a two-step iterative proximal/gradient method for computing the Stackelberg equilibrium for the security game: in each step, the algorithm solves an independent convex nonlinear programming problem implementing a regularized penalty approach. Regularization ensures the convergence to one (unique) of the possible equilibria of the Stackelberg game. To make the problem computationally tractable, we define the c-variable method for partially observable Markov games. Third, we show by simulation that our proposed model overcomes the disadvantages of previous Stackelberg security games solvers. Hence, as our final contribution, we present a new random walk method based on partial information. A numerical example for protecting airports terminals suggests the effectiveness of the proposed method, presenting the resulting patrolling strategies and two different realizations of the Stackelberg security game employing the partially observable random walk algorithm.

UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85063210277&origin=inward

UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85063210277&origin=inward

U2 - 10.1016/j.engappai.2019.03.010

DO - 10.1016/j.engappai.2019.03.010

M3 - Article

SP - 408

EP - 419

JO - Engineering Applications of Artificial Intelligence

JF - Engineering Applications of Artificial Intelligence

SN - 0952-1976

ER -