On the Characterization of Saddle Point Equilibrium for Security Games with Additive Utility

2020/07/28 by Emadi, HAmid, Bhattacharya, Sourabh
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2007.14478

Abstract

In this work, we investigate a security game between an attacker and a defender, originally proposed in \citeemadi2019security. As is well known, the combinatorial nature of security games leads to a large cost matrix. Therefore, computing the value and optimal strategy for the players becomes computationally expensive. In this work, we analyze a special class of zero-sum games in which the payoff matrix has a special structure which results from the \it additive property of the utility function. Based on variational principles, we present structural properties of optimal attacker as well as defender's strategy. We propose a linear-time algorithm to compute the value based on the structural properties, which is an improvement from our previous result in \citeemadi2019security, especially in the context of large-scale zero-sum games.

Related

• Additive Security Games: Structure and Optimization
• Security Game with Non-additive Utilities and Multiple Attacker Resources
• The Mysteries of Security Games: Equilibrium Computation Becomes Combinatorial Algorithm Design
• Non-additive Security Games
• Equilibrium Computation and Robust Optimization in Zero Sum Games with\n Submodular Structure