20 September 2010, Public communication in games of imperfect information, Sunil Simon

Abstract: The standard way of modelling imperfect information in games is in terms of information partitions for players. In this view, each player is associated with an equivalence relation over the set of game positions. For multi-player games of imperfect information defined in this manner it turns out that most of the interesting algorithmic questions like determining the winning strategy and synthesis of an equilibrium profile are undecidable. The crucial element which yields undecidability is the ability of the game model to implicitly encode arbitrary private communication between players. In this light, we propose a model where the players' information partitions are generated explicitly by means of communication. We define a notion of locally consistent equilibrium and suggest that this better captures the intuition of stable behaviour of players. We show that when communication is by means of public announcements, it is decidable to check whether locally consistent equilibrium profile exists.

This work is joint with R. Ramanujam (IMSc., Chennai).

For more information, contact Krzysztof Apt at apt at cwi.nl.