论文标题
关于使用添加剂实用程序的安全游戏的马鞍点平衡的表征
On the Characterization of Saddle Point Equilibrium for Security Games with Additive Utility
论文作者
论文摘要
在这项工作中，我们研究了攻击者与后卫之间的安全游戏，该游戏最初在\ cite {emadi2019security}中提出。众所周知，安全游戏的组合性质导致了巨大的成本矩阵。因此，计算玩家的价值和最佳策略在计算上变得昂贵。在这项工作中，我们分析了一类零和游戏的特殊类别，其中收益矩阵具有特殊的结构，该结构是由实用程序函数的{\ it添加属性}产生的。根据变异原则，我们介绍了最佳攻击者以及防御者策略的结构性。我们提出了一种线性时间算法来根据结构属性计算值，这比我们先前在\ cite {emadi2019security}中的结果有所改善，尤其是在大型零和零和游戏的背景下。
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.
