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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2020

Kód důvěrnosti údajů

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

Název statě ve sborníku

Decision and Game Theory for Security

ISBN

978-3-030-64792-6

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

20

Strana od-do

385-404

Název nakladatele

Springer International Publishing

Místo vydání

Cham

Místo konání akce

Maryland

Datum konání akce

26. 10. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—