A continuous-time Markov Stackelberg security game approach for reasoning about real patrol strategies

ABSTRACT

This paper improves the classical attacker-defender Stackelberg security games providing a novel approach for handling real-world patrolling domains with spatiotemporal constraints. The solution is restricted to a class of finite, controllable, and ergodic continuous-time Markov games. First, we suggest a multi-leader-follower Stackelberg game: the game model involves leaders and followers in a non-cooperative game respectively, related to a Stackelberg game. We study the problem of computing the Stackelberg-Nash equilibrium for this game in terms of the intermediate step solver. We employ the penalty method for representing the original game formulation in terms of nonlinear programming problems. The mathematical optimisation method proposed for solving the continuous-time Markov game takes into account the average cost functions of the players and extends the c-variable method for continuous-time. In addition, we present a new continuous-time random walk model, which defines the time of the jumping events for representing continuous-time patrol strategies. Our contribution overcomes the limitations presented in previous proposals related to Stackelberg security games. We experimentally show the efficiency of our approach measuring the benefits of the continuous-time Stackelberg game for security resource allocation. These results establish a strong step toward employing game theory to solve real-world security allocation problems.

KEYWORDS:

• Stackelberg security games
• continuous-time Markov games
• continuous-time random walk
• patrolling

Acknowledgments

I take this opportunity to express my gratitude to Dr Alexander S. Poznyak who has been an excellent mentor. I would like to express my sincere thankfulness for his persistent advice, criticism, clear-thinking, constant availability, prompt feedback, rigorous standards, and immense knowledge. The joy, enthusiasm, and passion he has for his research all the time are contagious and motivational for me. I could not have imagined having a better advisor and mentor along my research life. I am sincerely grateful to him for sharing his truthful and illuminating views on a number of issues related to research and teaching that helped open my mind to new ideas and challenges. I also express my gratitude to Dr Alexander S. Poznyak for the excellent example he has provided me as a successful professor.

Disclosure statement

No potential conflict of interest was reported by the author.