Computing and Approximating Equilibria in Games With Complex Strategy Spaces
Project goals
While there is an increasing number of practical applications of game theory, there are still severe computational limitations of the current models and algorithms used to find approximate optimal strategies. One such limitation is the high computational complexity of finding an equilibrium for games with large or even infinite sets of actions. Moreover, the strategy space in applications have often a complex inner structure making the equilibrium computations even more difficult. We propose advancing the state-of-the-art in the theoretical understanding of the structure of equilibria in games with complex strategy spaces, developing novel iterative strategy-generating algorithms for finding approximate solutions, investigating the computational complexity of equilibrium problem for special classes of games, and applying these fundamental results to various card games.
Keywords
game theorycontinuous gamesequilibrium computationincremental strategy generationregret minimisationdistributed algorithmic mechanism designcombinatorial gamescard games
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202400001
Main participants
České vysoké učení technické v Praze / Fakulta elektrotechnická
Contest type
VS - Public tender
Contract ID
24-12046S
Alternative language
Project name in Czech
Výpočet a aproximace ekvilibrií ve hrách se složitými prostory strategií
Annotation in Czech
Navzdory zvyšujícímu se počtu úspěšných aplikací teorie her v praxi je expresivita nasazených modelů stále limitována výpočetními možnostmi existujících algoritmů pro hledání (přibližných) řešení. Jedním z omezujících faktorů je velká výpočetní složitost hledání ekvilibrií pro hry s velkými či dokonce nekonečnými prostory akcí. Navíc prostory strategií mají v aplikacích často složitou vnitřní strukturu, což složitost výpočtu ekvilibrií dále prohlubuje. Cílem projektu je proto posunout stav poznání hledáním nových podmínek pro existenci ekvilibrií ve hrách se složitými prostory strategií, návrhem nových iterativních algoritmů pro aproximaci ekvilibrií v těchto hrách, výzkumem složitosti výpočtu ekvilibrií pro speciální třídy her a aplikovat získané poznatky na různé karetní hry.
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
Solution timeline
Realization period - beginning
Jan 1, 2024
Realization period - end
Dec 31, 2026
Project status
B - Running multi-year project
Latest support payment
Feb 27, 2024
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
CEP25-GA0-GA-R
Data delivery date
Feb 21, 2025
Finance
Total approved costs
10,559 thou. CZK
Public financial support
10,559 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
10 559 CZK thou.
Public support
10 559 CZK thou.
0%
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. 2024 - 31. 12. 2026