Double Oracle Algorithm for Zero-Sum Security Games on Graph

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F11%3A00183243" target="_blank" >RIV/68407700:21230/11:00183243 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Double Oracle Algorithm for Zero-Sum Security Games on Graph

Popis výsledku v původním jazyce

In response to the Mumbai attacks of 2008, the Mumbai police have started to schedule a limited number of inspection checkpoints on the road network throughout the city. Algorithms for similar security-related scheduling problems have been proposed in recent literature, but security scheduling in networked domains when targets have varying importance remains an open problem at large. In this paper, we cast the network security problem as an attacker-defender zero-sum game. The strategy spaces for both players are exponentially large, so this requires the development of novel, scal- able techniques. We first show that existing algorithms for approximate solutions can be arbitrarily bad in general settings.

Název v anglickém jazyce

Double Oracle Algorithm for Zero-Sum Security Games on Graph

Popis výsledku anglicky

In response to the Mumbai attacks of 2008, the Mumbai police have started to schedule a limited number of inspection checkpoints on the road network throughout the city. Algorithms for similar security-related scheduling problems have been proposed in recent literature, but security scheduling in networked domains when targets have varying importance remains an open problem at large. In this paper, we cast the network security problem as an attacker-defender zero-sum game. The strategy spaces for both players are exponentially large, so this requires the development of novel, scal- able techniques. We first show that existing algorithms for approximate solutions can be arbitrarily bad in general settings.

Druh

D - Stať ve sborníku

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

—

Návaznosti

V - Vyzkumna aktivita podporovana z jinych verejnych zdroju

Rok uplatnění

2011

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

AAMAS 2011

ISBN

978-0-9826571-8-8

ISSN

—

e-ISSN

—

Počet stran výsledku

8

Strana od-do

327-334

Název nakladatele

IFAAMAS

Místo vydání

County of Richland

Místo konání akce

Taipei,

Datum konání akce

2. 5. 2011

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

WRD - Celosvětová akce

Kód UT WoS článku

—