Observation and Distinction. Representing Information in Infinite Games
share
We compare two approaches for modelling imperfect information in infinite games on finite-state systems. The standard model represents the observation received by a player in each stage as a sequential Mealy machine. As a new approach, we consider a model based on indistinguishability relations described by synchronous two-tape automata. We point out that the indistinguishability-relation model is strictly more expressive than the one based on observations. Nevertheless, we show that the basic strategy synthesis problem is effectively solvable for games where imperfect information under synchronous perfect recall is described by a regular indistinguishability relation. Further, we give an abstract characterisation of indistinguishablity relations that admit an equivalent representation by a finite-state observation function. Finally, we present an algorithm for constructing an observation function equivalent to a given indistinguishability relation, whenever this is possible.
READ FULL TEXT