UvA Logo

(Verzamelingstheoretische Modelvorming voor Oneindige Spelen van Imperfecte Informatie)
NWO Project

Project Description

Our goal: Developing a structure theory for Infinite Imperfect Information games.

Imperfect Information games: Imperfect Information Games are of increasing importance in many areas of applications. On the other hand, it seems that their logical strength, their computational complexity and power and their set-theoretic structure is more subtle than those of perfect information games, and that they are far less understood.

In order to actively use imperfect information games in some of the applications they seem to be fit for and in order to do justice to the importance of imperfect information games, the mathematical and computational analysis of imperfect information games needs to be refined.

Infinite Games: Based on work of Polish topologists, infinite games entered modern Set Theory and invoked interest in questions (a) whether given sets A of infinite sequences are determined (i.e., allow a winning strategy for one of the two players in the zero-sum perfect information games with payoff set A) and (b) how a set-theoretic universe in which all sets are determined would look like. These two questions were investigated using a variety of tools from Mathematical Logic from 1962 to the late 1980s by the a group of predominantly Californian Mathematical Logicians known under the name of the Cabal Seminar (Addison, Kechris, Martin, Moschovakis, Solovay, Steel, Woodin, and others). Since the late 1980s, Mathematical Logicians have a rather clear understanding of the theory of determinacy of infinite perfect information games and the set-theoretic and logical strength of determinacy assumptions of this type.

Our goal in more detail:

Imperfect information games come in two different yet deeply related forms: Finite imperfect information games (with many computational applications) and infinite imperfect information games. In both cases, although we have a lot of theory on these games in special situations and under certain assumptions, a fundamental and general theory of imperfect information games is still a desideratum.

For finite imperfect information games, the development of a fundamental theory is the goal of our NWO sponsored project InIGMA "Imperfect Information Games; Models and Analysis". The goal of the project VMOSII is the development of such a fundamental theory for infinite imperfect information games. Therefore, VMOSII can be seen as an infinite version of InIGMA, and the two projects are closely linked in their visions and personnel.

In Set Theory, imperfect information games have been investigated in a very special form: Blackwell games. These infinite stochastic games have been investigated by the statistician David Blackwell and set-theoretically investigated by Tony Martin (Los Angeles CA), Itay Neeman (Los Angeles CA), Marco Vervoort (Amsterdam) and Benedikt Löwe. In Blackwell games, imperfect information is modelled by probabilistic moves. Of course, there are other situations in which the information about the state of the game could be imperfect - e.g., the players could lack the complete information about the configuration of the game.

We intend to investigate infinite games of this second kind of imperfect information and develop a structure theory for games of this kind.

Last changed: March 5th, 2003