Using One-Sided Partially Observable Stochastic Games for Solving Zero-Sum Security Games with Sequential Attacks

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00344453" target="_blank" >RIV/68407700:21230/20:00344453 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1007/978-3-030-64793-3_21" target="_blank" >https://doi.org/10.1007/978-3-030-64793-3_21</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-64793-3_21" target="_blank" >10.1007/978-3-030-64793-3_21</a>

Result language

angličtina

Original language name

Using One-Sided Partially Observable Stochastic Games for Solving Zero-Sum Security Games with Sequential Attacks

Original language description

Security games are a defender-attacker game-theoretic model where the defender determines how to allocate scarce resources to protect valuable targets against the attacker. A majority of existing work has focused on the one-shot game setting in which the attacker only attacks once. However, in many real-world scenarios, the attacker can perform multiple attacks in a sequential manner and leverage observable e_ects of these attacks for better attack decisions in the future. Recent work shows that in order to provide e_ective protection over targets, the defender has to take the prospect of sequential attacks into consideration. The algorithm proposed by existing work to handle sequential attacks, however, can only scale up to two attacks at most. We extend this line of work and focus on developing new scalable algorithms for solving the zero-sum variant of security games.We formulate security games with sequential attacks as a one-sided partially observable stochastic games. We show that the uncertainty about the state in the game can be modeled compactly and we can use variants of heuristic search value iteration algorithm for solving these games. We give two variants of the algorithm { an exact one and a heuristic formulation where the resource reallocation possibilities of the defender are simpli_ed. We experimentally compare these two variants of the algorithm and show that the heuristic variant is typically capable of _nding high-quality strategies while scaling to larger scenarios compared to the exact variant.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Decision and Game Theory for Security

ISBN

978-3-030-64792-6

ISSN

0302-9743

e-ISSN

—

Number of pages

20

Pages from-to

385-404

Publisher name

Springer International Publishing

Place of publication

Cham

Event location

Maryland

Event date

Oct 26, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—