Dinkelbach-Type Algorithm for Computing Quantal Stackelberg Equilibrium

Dinkelbach-Type Algorithm for Computing Quantal Stackelberg Equilibrium

Jakub Cerny, Viliam Lisý, Branislav Bošanský, Bo An

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 246-253. https://doi.org/10.24963/ijcai.2020/35

Stackelberg security games (SSGs) have been deployed in many real-world situations to optimally allocate scarce resource to protect targets against attackers. However, actual human attackers are not perfectly rational and there are several behavior models that attempt to predict subrational behavior. Quantal response is among the most commonly used such models and Quantal Stackelberg Equilibrium (QSE) describes the optimal strategy to commit to when facing a subrational opponent. Non-concavity makes computing QSE computationally challenging and while there exist algorithms for computing QSE for SSGs, they cannot be directly used for solving an arbitrary game in the normal form. We (1) present a transformation of the primal problem for computing QSE using a Dinkelbach's method for any general-sum normal-form game, (2) provide a gradient-based and a MILP-based algorithm, give the convergence criteria, and bound their error, and finally (3) we experimentally demonstrate that using our novel transformation, a QSE can be closely approximated several orders of magnitude faster.
Keywords:
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Noncooperative Games
Humans and AI: Cognitive Modeling