All
All

What are you looking for?

All
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Algorithms for Playing Massive Imperfect-Information Games

Project goals

Game theory is a formal framework that allows computing optimal behavior in situations where multiple agents interact in a shared environment. The computational branch of the field provides algorithms for approximating optimal strategies applicable in competitive real-world problems (e.g., physical or cyber security), recreational games (e.g., poker, computer games), or safety-critical robust optimization (e.g., healthcare, autonomous driving). While there was considerable progress in this field in recent years, the existing algorithms applicable in large games either pose very particular assumptions on problem structure, which severely limits their applicability (e.g., an abundance of available information, finite horizon), or lack any performance guarantees. In this project, we aim to develop novel theory and algorithms that will allow guaranteed convergence to optimal strategies in large imperfect-information games with more general information structure, longer horizon, and weaker assumptions on opponent’s rationality than previously possible.

Keywords

Imperfect-information gamessequential decision makingdepth-limited solvingbounded rationalityreinforcement learning

Public support

  • Provider

    Czech Science Foundation

  • Programme

    Standard projects

  • Call for proposals

    SGA0202200004

  • Main participants

    České vysoké učení technické v Praze / Fakulta elektrotechnická

  • Contest type

    VS - Public tender

  • Contract ID

    22-26655S

Alternative language

  • Project name in Czech

    Algoritmy pro hraní masivních her s neúplnou informací

  • Annotation in Czech

    Teorie her je vědní obor který umožňuje nalézt optimální chování v interakcích vícero agentů. Výpočetní odnož teorie her pak přichází s algoritmy, které aproximují optimální chování v množství důležitých aplikací jako reálné konflikty (např. fyzická a kybernetická bezpečnost), rekreační hry (např. poker či počítačové hry) nebo optimalizační problémy vyžadující důraz na bezpečnost (např. zdravotnictví či autonomní vozidla). Podobor který se zabývá řešením velkých her s neúplnou informací sice nedávno zaznamenal značné pokroky, současné algoritmy pro tyto hry však stále trpí řadou omezení. Současné algoritmy totiž buď vyžadují velmi specifické předpoklady (jako velké množství veřejné informace, což omezuje jejich uplatnitelnost) nebo nenabízejí žádné teoretické záruky (což omezuje jejich spolehlivost). Cílem navrhovaného projektu je tedy vyvinout teorii velkých her s neúplnou informací a navrhnout algoritmy které budou zaručeně konvergovat k optimálnímu řešení ve výrazně více hrách (co do jejich délky, předpokladů na racionalitu protivníka a struktury informace ve hře) než doposud.

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, 2022

  • Realization period - end

    Dec 31, 2024

  • Project status

  • Latest support payment

    Feb 29, 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

    Mar 12, 2025

Finance

  • Total approved costs

    9,747 thou. CZK

  • Public financial support

    9,747 thou. CZK

  • Other public sources

    0 thou. CZK

  • Non public and foreign sources

    0 thou. CZK

Basic information

Recognised costs

9 747 CZK thou.

Public support

9 747 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. 2022 - 31. 12. 2024