On Dialogue Games and Graph Games

Dialogue games were introduced by Mellies as an attempt to unify two historical paradigms of game semantics: concrete data structures and arena games. The definition of dialogue games relies on the idea that a move m of an arena game can be decomposed as a pair m = ( α , v ) consisting of a cell α and of a value v. Consequently, a dialogue game is defined as a quadripartite forest whose nodes are separated into four classes: Opponent cells, Opponent values, Player cells, Player values. Although the translation from arena games to dialogue games is essentially immediate, the relationship between dialogue games and concrete data structures is more intricate. In order to clarify it, we study the relationship between dialogue games and graph games which were introduced by Hyland and Schalk to provide a graph-theoretic account of Berry and Curien's sequential algorithm model. We construct a fully faithful functor from a category of dialogue games to the category of graph games and conflict-free strategies. This leads us to an alternative definition of conflict-free strategies in graph games as balanced and bi-invariant strategies in dialogue games.