New decidable classes for distributed strategy synthesis

Infinite games with imperfect information tend to be undecidable unless the information flow is severely restricted. One fundamental decidable case occurs when there is a total ordering among players, such that each player has access to all the information that the following ones receive. In this talk, we present two information patterns that lead to new decidable classes for which the distributed synthesis problem is solvable with finite-state strategies. One generalises the hierarchical principle by allowing information hierarchies to change along the play, and by admitting transient phases without hierarchical information. The second pattern is orthogonal, it asserts that players attain common knowledge about the actual state of the game over and over again along every play. Joint work with Anup Basil Mathew and Marie van den Bogaard. http: //lsv. fr/~dwb/rec. pdf http: //lsv. fr/~dwb/hi. pdf

Authors

• Dietmar Berwanger

Keywords

No keywords are indexed for this paper.