A convenient category for games and interaction (Q1306712): Difference between revisions

This paper seeks to study games in an order enriched setting by using the category \({\mathcal R}el\) of sets and relations as a model. \({\mathcal R}el\) is a fundamental example of a quantaloid, a category enriched in \({\mathcal S}{\mathcal I}\), the autonomous category of sup-lattices, and the author's construction in fact leads to a quantaloid of games, denoted \({\mathcal G}am\). [For more on quantaloids, see the reviewer's book, \textit{K. I. Rosenthal}, ``The theory of quantaloids'', Pitman Res. Notes Math. 348 (1996; Zbl 0845.18003).] The first step taken is to define a notion of tree composition using composition in \({\mathcal R}el\) as a model. This tree composition is associative and does preserve suprema, however identity morphisms do not exist for it. This leads to a modification of th set-up basically looking at non-empty down-sets of strictly alternating sequences of ``moves'' resulting in the category \({\mathcal G} am\), which now has identities and is in fact a quantaloid. Work of Abramsky, Blass and others involving games as a means of looking at linear logic required games to form a symmetric monoidal category. The natural notion of tensor product of games turns out to be unsatisfactory in \({\mathcal G}am\) for several reasons, and the rest of the paper deals with constructing an extension of \({\mathcal G}am\) by considering the Kleisli category induced by the functor \(\pm 1\) on \({\mathcal G}am\). This leads to a category with a good intrinsic description of the tensor product and also allows for an effective approach to looking at the associated residuation operation. The paper closes with some remarks on the connection of this operation to strategies.