On the characterization of saddle point equilibrium for security games with additive utility

DOI10.1007/978-3-030-64793-3_19zbMATHOpenAlexMaRDI QIDQ2056958FDO

Authors Yanyan Li

Publication date 8 December 2021

Full work available at URL https://arxiv.org/abs/2007.14478

zbMATH Keywords

computational complexityNash equilibriumzero-sum gamesecurity game

Mathematics Subject Classification ID

Noncooperative games (91A10) 2-person games (91A05) Combinatorial games (91A46)

Abstract: In this work, we investigate a security game between an attacker and a defender, originally proposed in cite{emadi2019security}. 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 cite{emadi2019security}, especially in the context of large-scale zero-sum games.

Recommendations

• On equilibrium existence in payoff secure games
• On the saddle-point stability for a class of dynamic games
• A study of general and security Stackelberg game formulations
• On minimax and Pareto optimal security payoffs in multicriteria games
• Stackelberg vs. Nash in security games: an extended investigation of interchangeability, equivalence, and uniqueness
• Uniform payoff security and Nash equilibrium in compact games
• Existence of secure equilibrium in multi-player games with perfect information
• Saddle-point properties and Nash equilibria for channel games
• Weakly continuous security and Nash equilibrium
• Remarks on sensitive equilibria in stochastic games with additive reward and transition structure

Cites work

• scientific article; zbMATH DE number 1243371 (Why is no real title available?)
• Computing optimal randomized resource allocations for massive security games
• Designing Virus-Resistant, High-Performance Networks: A Game-Formation Approach
• Game theory meets network security and privacy
• Minimizing the sum of the \(k\) largest functions in linear time.
• On the relative leadership property of Stackelberg strategies
• Stackelberg vs. Nash in security games: an extended investigation of interchangeability, equivalence, and uniqueness
• Uncertainty in interdependent security games

Cited in

(1)

• Iterative computation of security strategies of matrix games with growing action set

This page was built for publication: On the characterization of saddle point equilibrium for security games with additive utility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2056958)