Oberseminar Mengenlehre

Sommersemester 2002

Imperfect Information Games; looking for the right model.

Peter van Emde Boas
ILLC-FNWI-University of Amsterdam &
Bronstee.com Software & Services B.V., Heemstede

The theory relating the endgame analysis of "reasonable games" with the complexity class PSPACE, which was developed 25 years ago breaks down for imperfect information games. This creates also an open slot in the otherwise smooth relation between game models and modes of computation.

Analysis of Imperfect information games is relevant grace to the fact that the recent applications of game models in computer science frequently involve imperfect information as one of their essential ingredients. Similarly, imperfect information versions of games used in the logic and games field have been introduced as well.

The forthcoming NWO supported project nicknamed InIGMA (Imperfect Information Games, Models and Analysis) which was submitted by Johan van Benthem and myself, was approved last year and will start this september is an attempt to extend the existing theory to cope with imperfect information games as well.

In the talk I will indicate the few results available in the literature, what we know about this problem, and how we hope to solve it.

Last changed: April 10th, 2002