Coordinating strategies with imperfect information

Dietmar Berwanger
LSV - ENS Cachan, France
Friday, 7 May, 2010 - 14:00
NO Building, 9th Floor

A classical paper of Reif on games with imperfect information shows that games for one player against nature can be solved by a power-set construction yielding larger games of perfect information. Similar in spirit to the determinisation of automata, the construction represents (an abstraction of) the knowledge that a player has about the play history. In the same paper, it is shown that the problem of deciding whether a coalition of players can coordinate to win with finite-state strategies is in general undecidable, essentially because players need to keep track of an infinite amount of information.

In this talk, we aim to shed light on the notion of knowledge needed by players in a coalition to coordinate against nature. As a multi-player variant of the basic construction of Reif, we propose a game representation that keeps track of the information acquired by a player during a play, and discuss conditions under which this representation is finite. On basis of this, we outline a semi-decision algorithm for deciding whether there exist distributed winning strategies in n-player safety games with imperfect information.