News & Events

New GAČR project: Abstractions and Extensive-Form Games with Imperfect Recall

Abstractions and Extensive-Form Games with Imperfect Recall

We are searching for new algorithmic solutions for finite sequential games where players do not have perfect memory and may forget either some actions they have previously played, or some information they have acquired. These games are very hard from the computational perspective, since Nash equilibrium might not exist in these games and finding strategies with guaranteed outcome is significantly harder compared to games where perfect memory of players is assumed. On the other hand, forgetting less relevant parts of the available information may lead to substantially smaller game models that may be solved faster even with the more computationally complex algorithms. 

Non-cooperative game theory provides mathematical models of behavior of rational players (or agents) in competitive scenarios. The interest of computer science and artificial intelligence researchers is in the algorithmic aspects of game theory, in designing and implementing new algorithms that improve scalability and allow solving larger scenarios. Scaling-up is an important step in the process of applying game-theoretic models into real-world conditions. The increased focus on the algorithmic aspects resulted in several successful applications of game theory -- namely in security domains, in auctions, and mechanism design (e.g., for charging electric cars), or problems of social choice applied in recommendation systems. The interaction between agents in real-world scenarios is often complex, agents perform actions to modify the state of the world, they are able to observe some effects of these modifications, and react to them accordingly. Moreover, the agents might not have a perfect information about the state of the world, or about the actions performed by other agents, the actions of agents may fail, and there can be other form of uncertainty in the environment. An example of such complex interactions can be an auction, where the goal of an agent is to acquire some item. An agent can increase her bid, can observe the bids of the other agents, however, the agent does not know the true evaluation of the other agents for this item, and may have some uncertainty about his own evaluation. Other examples include security scenarios, where members of a security team observe the current situation (e.g., monitoring a store or an airport using cameras), and then react to information according to the security protocol (e.g., there is a suspicious person near the entrance to a restricted area). This sequential reasoning and a proper response to different situations must be incorporated directly into the game-theoretic model. Otherwise it can be exploited by a strategically reasoning adversary (e.g., by using decoys or deception).

Game theory provides a model capable of representing this type of scenarios termed extensive-form games. The whole course of the scenario is represented as a game tree, where each node of the game tree corresponds to a state in the scenario, where one of the agents can execute an action that leads to a different state. Each terminal
state of the scenario corresponds to a leaf in the game tree and has assigned utility values that represent the benefit of reaching this state for each player. The class of zero-sum extensive-form games is a well established class of games of great importance. Over the years, several key algorithms were introduced that dramatically improved scalability in practical applications (e.g., in computational Poker). However, the main algorithms for solving these games assume perfect memory (or perfect recall), which causes exponentially large game tree. If parts of the information that is not likely to be relevant in the reminder of the game is forgotten by the players, it can lead to substantially smaller game models, which still capture the most important features of the game. This allows to substantially limit the exponential growth of the game tree.  In this project we are therefore interested in games, where players do not have perfect memory and may forget either some actions they have previously played, or some information they have acquired. These games are very hard from the computational perspective, since Nash equilibrium might not exist in these games and finding strategies with guaranteed outcome is significantly harder compared to games where perfect memory of players is assumed.