Solving Stackelberg security Markov games employing the bargaining Nash approach: Convergence analysis

摘要

This paper proposes a new approach for the Stackelberg security Markov games' solution, by computing a cooperative approach for the defenders employing the bargaining Nash solution, while the attackers play in a non-cooperative manner. The bargaining Nash solution forces the defenders to negotiate in order to improve their position. A fundamental element of such a game is the disagreement point (status quo), which plays a role of a deterrent. A bargaining solution is defined as a single-valued function that selects an outcome from among the feasible payoffs for each bargaining problem, which in turn is the result of cooperation by the defenders involved in the game. The agreement reached in the game is the most desirable alternative within the set of feasible outcomes. The attackers, playing non-cooperatively, compute the Nash equilibrium point. We employ the Lagrange principle to represent the original game formulation as a nonlinear programming problem. To compute the equilibrium point of the Stackelberg security Markov game, we use an iterative proximal gradient approach. This way, the problem is transformed into a system of equations, which represents an optimization problem for which the necessary condition of a minimum is solved by the projection gradient method. An analysis of the convergence to the Stackelberg security equilibrium point is presented, as well as a random walk solution for planning the patrol schedule which incorporates additional information about the targets using the entropy. The usefulness of the method is successfully demonstrated by a numerical example.