New Models of Games with Imperfect Information
Explore new approaches to modeling imperfect information in infinite games using finite-state automata in this lecture by Laurent Doyen from CNRS. Compare the standard observation-based method with a novel indistinguishability-relation approach, discovering how the latter offers greater expressiveness. Learn about the characterization of indistinguishability relations representable as finite-state observation functions and the decision procedure for constructing corresponding Mealy machines. Delve into strategy synthesis for imperfect-information games modeled with indistinguishability relations through a reduction to perfect-information games. Examine an application of full-information protocols in synchronous settings with explicit communication actions, and understand how these protocols induce automata-describable indistinguishability relations. Uncover the strict hierarchy in expressiveness and complexity induced by the number of passive observers in full-information protocols, with insights into the (n+1)-EXPTIME-complete nature of the strategy-synthesis problem for n observers. Read more