Security games on matroids
成果类型：
Article
署名作者：
Szeszler, David
署名单位：
Budapest University of Technology & Economics
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-016-1011-9
发表日期：
2017
页码：
347-364
关键词：
摘要：
Two players, the Defender and the Attacker play the following game. A matroid , a weight function and a cost function are given. The Defender chooses a base B of the matroid M and the Attacker chooses an element of the ground set. In all cases, the Attacker pays the Defender the cost of attack c(s). Besides that, if then the Defender pays the Attacker the amount d(s); if, on the other hand, then there is no further payoff. Special cases of this two-player, zero-sum game were considered and solved in various security-related applications. In this paper we show that it is also possible to compute Nash-equilibrium mixed strategies for both players in strongly polynomial time in the above general matroid setting. We also consider a further generalization where common bases of two matroids are chosen by the Defender and apply this to define and efficiently compute a new reliability metric on digraphs.
来源URL：