When Players Affect Target Values: Modeling and Solving Dynamic Partially Observable Security Games

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F19%3A00339904" target="_blank" >RIV/68407700:21230/19:00339904 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-32430-8_32" target="_blank" >https://doi.org/10.1007/978-3-030-32430-8_32</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

When Players Affect Target Values: Modeling and Solving Dynamic Partially Observable Security Games

Popis výsledku v původním jazyce

Most of the current security models assume that the values of targets/areas are static or the changes (if any) are scheduled and known to the defender. Unfortunately, such models are not sufficient for many domains, where actions of the players modify the values of the targets. Examples include wildlife scenarios, where the attacker can increase value of targets by secretly building supporting facilities. To address such security game domains with player-affected values, we first propose DPOS3G, a novel partially observable stochastic Stackelberg game where target values are determined by the players’ actions; the defender can only partially observe these targets’ values, while the attacker can fully observe the targets’ values and the defender’s strategy. Second, we propose RITA (Reduced game Iterative Transfer Algorithm), which is based on the heuristic search value iteration algorithm for partially observable stochastic game (PG-HSVI) and introduces three key novelties: (a) building a reduced game with only key states (derived from partitioning the state space) to reduce the numbers of states and transitions considered when solving the game; (b) incrementally adding defender’s actions to further reduce the number of transitions; (c) providing novel heuristics for lower bound initialization of the algorithm. Third, extensive experimental evaluations of the algorithms show that RITA significantly outperforms the baseline PG-HSVI algorithm on scalability while allowing for trade off in scalability and solution quality.

Název v anglickém jazyce

When Players Affect Target Values: Modeling and Solving Dynamic Partially Observable Security Games

Popis výsledku anglicky

Most of the current security models assume that the values of targets/areas are static or the changes (if any) are scheduled and known to the defender. Unfortunately, such models are not sufficient for many domains, where actions of the players modify the values of the targets. Examples include wildlife scenarios, where the attacker can increase value of targets by secretly building supporting facilities. To address such security game domains with player-affected values, we first propose DPOS3G, a novel partially observable stochastic Stackelberg game where target values are determined by the players’ actions; the defender can only partially observe these targets’ values, while the attacker can fully observe the targets’ values and the defender’s strategy. Second, we propose RITA (Reduced game Iterative Transfer Algorithm), which is based on the heuristic search value iteration algorithm for partially observable stochastic game (PG-HSVI) and introduces three key novelties: (a) building a reduced game with only key states (derived from partitioning the state space) to reduce the numbers of states and transitions considered when solving the game; (b) incrementally adding defender’s actions to further reduce the number of transitions; (c) providing novel heuristics for lower bound initialization of the algorithm. Third, extensive experimental evaluations of the algorithms show that RITA significantly outperforms the baseline PG-HSVI algorithm on scalability while allowing for trade off in scalability and solution quality.

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

<a href="/cs/project/GJ19-24384Y" target="_blank" >GJ19-24384Y: Výpočet rovnovážných strategií v dynamických hrách</a><br>

Návaznosti

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

Rok uplatnění

2019

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

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ISBN

9783030324292

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

21

Strana od-do

542-562

Název nakladatele

Springer

Místo vydání

Wien

Místo konání akce

Stockholm

Datum konání akce

30. 10. 2019

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

WRD - Celosvětová akce

Kód UT WoS článku

—