Computing Equilibrium Strategies in Dynamic Games
Project goals
Recent years have witnessed massive deployments of algorithms and techniques of artificial intelligence (AI) into every-day life. However, AI-based decision models can be attacked or deceived by an adversary resulting in incorrect, or even dangerous behavior. Game theory and game-theoretic algorithms can provide robustness against an adversary, however, for many dynamic games with partial observations and uncertainty that naturally model many real-world situations, there are no practical algorithms. The main goal of the project is to reinforce the applicability of game-theoretic algorithms by (1) finding large subclasses of partially observable stochastic games (POSGs) that allow computing (approximate) optimal strategies and by (2) designing, implementing, and experimentally evaluating novel approximate algorithms for maxmin strategies and Stackelberg equilibrium in these classes of games.
Keywords
artificial intelligencecomputational game theorydynamic gamespartial obsevabilityequilibrium computationdomain-independent algorithms
Public support
Provider
Czech Science Foundation
Programme
Junior Grants
Call for proposals
Juniorské granty 5 (SGA0201900002)
Main participants
České vysoké učení technické v Praze / Fakulta elektrotechnická
Contest type
VS - Public tender
Contract ID
19-24384Y
Alternative language
Project name in Czech
Výpočet rovnovážných strategií v dynamických hrách
Annotation in Czech
V posledních letech lze pozorovat ohromný nárůst nasazení modelů a technik umělé inteligence do běžného života. Na druhou stranu, tyto modely a algoritmy mohou být manipulovány nebo přímo napadeny útočníkem a způsobit tak nesprávné nebo dokonce nebezpečné chování různých systémů. Teorie her může těmto modelům umělé inteligence poskytnout potřebnou robustnost v prostředí s protivníkem, avšak pro mnoho dynamických her s neurčitostí a neúplným pozorováním, které přirozeně odpovídají reálnému světu, neexistují praktické algoritmy. Tento projekt si tak klade za cíl zlepšit možnosti nasazení herně-teoretických algoritmů v praxi pomocí (1) identifikace podtříd částečně pozorovatelných stochastických her, které umožňují návrh aproximativních algoritmů a pomocí (2) návrhu, implementace a experimentální evaluace nových doménově nezávislých algoritmů pro výpočet aproximativně optimálních strategií pro hry z těchto tříd.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
The project led to a number of results in computational game theory, which became a subject of 3 journal and 9 conference papers. The most significant result, among several very interesting results of the project is an adaptation of the Heuristic Search Value Iteration algorithm to get a near-optimal strategy for a particular type of stochastic games of two players, already cited more 50 times.
Solution timeline
Realization period - beginning
Jan 1, 2019
Realization period - end
Jun 30, 2022
Project status
U - Finished project
Latest support payment
Apr 1, 2022
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
CEP23-GA0-GJ-U
Data delivery date
Jun 26, 2023
Finance
Total approved costs
5,228 thou. CZK
Public financial support
5,228 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
5 228 CZK thou.
Public support
5 228 CZK thou.
100%
Provider
Czech Science Foundation
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Solution period
01. 01. 2019 - 30. 06. 2022