Security Games in Extensive Form
Project goals
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.
Keywords
algorithmicgametheorysecuritygamesStackelbergequilibriumcomputationalcomplexity
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 15 (SGA02012GA-ST)
Main participants
—
Contest type
VS - Public tender
Contract ID
P202-12-2054
Alternative language
Project name in Czech
Bezpečnostní hry v extenzivní formě
Annotation in Czech
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í.
Scientific branches
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
The project has developed new algorithms for solving finite sequential zero-sum games (both exact and approximation), the new algorithms improve speed and scalability in practical applications. Overall, the project delivered very good results in most ofthe proposed research domains, the results were published at top tier conferences.
Solution timeline
Realization period - beginning
Jan 1, 2012
Realization period - end
Dec 31, 2014
Project status
U - Finished project
Latest support payment
Apr 18, 2014
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP15-GA0-GA-U/01:1
Data delivery date
May 22, 2015
Finance
Total approved costs
4,581 thou. CZK
Public financial support
4,581 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
4 581 CZK thou.
Public support
4 581 CZK thou.
0%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2012 - 31. 12. 2014