Bezpečnostní hry v extenzivní formě
Cíle projektu
Teorie her poskytuje teoretické a algoritmické základy oboru multiagentních systémů. Jedna z tříd problémů, kde byla obzvlášť úspěšná, jsou bezpečnostní hry. Tyto hry modelují interakce mezi obráncem, který alokuje omezené zdroje na ochranu několika cílů, a útočníkem, který se pokouší zaútočit na nechráněný cíl. Bezpečnostní hry a jejich řešení byly v poslední době důsledně teoreticky analyzovány a staly se základem několika úspěšných aplikací. I když byly bezpečnostní hry úspěšné v některých doménách,mnohá omezení znemožňují jejich aplikaci v jiných. Neumožnují modelovat útoky složené s vícero v čase navazujících akcí nebo přizpůsobení strategie obránce na základě pozorování. Pro překonání těchto omezení navrhujeme rozšířit tento model a definovat bezpečnostní hry v extenzivní formě (EFSG). Pro různé varianty těchto her určíme výpočetní složitost hledání jejich řešení. Na základě této analýzy navrhneme přesné a aproximační metody jejich řešení.
Klíčová slova
algorithmicgametheorysecuritygamesStackelbergequilibriumcomputationalcomplexity
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 15 (SGA02012GA-ST)
Hlavní účastníci
—
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
P202-12-2054
Alternativní jazyk
Název projektu anglicky
Security Games in Extensive Form
Anotace anglicky
Game theory provides theoretical and algorithmic foundations for the field of multi-agent systems. One class of problems where it proved to be very useful, are the security games. These games model interactions between a defender, which allocates limitedresources to protect a set of targets and an attacker who tries to attack an unprotected target. Security games and their solution concepts have been recently widely analyzed theoretically and constitute the core of several successfully deployed systems. While successful in some domains, it is a quite restricted model inapplicable elsewhere. It does not allow modeling attacks with multiple actions succeeding in time or defender adapting its strategy based on observations. In order to remove these limitations, we propose to extend the model and define the extensive form security games (EFSG). We will establish computational complexity bounds of finding the optimal strategies for the defender in variants of the game. Based on the analysis, we will design exact and approximative algorithms for computing these strategies.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
IN - Informatika
CEP - vedlejší obor
—
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory
(dle převodníku)10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků projektu
Projekt vyvinul nové algoritmy pro řešení konečných sekvenčních her s nulovým součtem (jak exaktní, tak aproximativní), nové algoritmy zlepšují rychlost a škálovatelnost řešení v praktických aplikacích. Projekt celkově podal velmi dobré výsledky, ve vět?
Termíny řešení
Zahájení řešení
1. 1. 2012
Ukončení řešení
31. 12. 2014
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
18. 4. 2014
Dodání dat do CEP
Důvěrnost údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Systémové označení dodávky dat
CEP15-GA0-GA-U/01:1
Datum dodání záznamu
22. 5. 2015
Finance
Celkové uznané náklady
4 581 tis. Kč
Výše podpory ze státního rozpočtu
4 581 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Uznané náklady
4 581 tis. Kč
Statní podpora
4 581 tis. Kč
0%
Poskytovatel
Grantová agentura České republiky
CEP
IN - Informatika
Doba řešení
01. 01. 2012 - 31. 12. 2014