A tri-level approach for computing Stackelberg Markov game equilibrium: Computational analysis

Tri-level game-theory problems have been drawing serious interest because of their applicability to a broad range of real applications. It is considered a hierarchical game (min-min-min) in which multiple leaders and followers compete restricted to finite, controllable and ergodic Markov games. We determine the relationship involving the Nash and Stackelberg equilibrium notions and typify the circumstances under which the proximal/gradient method converges to a Stackelberg equilibrium: the hierarchical structure considers that leaders and followers are in a Nash framework with a Stackelberg constraint model. Despite recent considerable progress, the literature to date has focused mostly on solutions based on linear programming. This paper introduces a new proximal/gradient method for computing the equilibrium point for a tri-level Stackelberg game played between multiple leaders and followers. This procedure guaranteed the convergence to a Stackelberg equilibrium. We also provide the analysis of the convergence and the rate of convergence to Stackelberg equilibrium point. Finally, we prove the effectiveness and utility of the proposed method using a numerical example.