The Category of Node-and-Choice Preforms for Extensive-Form Games
Peter A. Streufert · Studia Logica · 2017
It would be useful to have a category of extensive-form games whose isomorphisms specify equivalences between games. Since working with entire games is too large a project for a single paper, I begin here with preforms, where a “preform” is a rooted tree together with choices and information sets. In particular, this paper first defines the category $$\mathbf {Tree}$$ , whose objects are “functioned trees”, which are specially designed to be incorporated into preforms. I show that $$\mathbf {Tree}$$ is isomorphic to the full subcategory of $$\mathbf {Grph}$$ whose objects are converging arborescences. Then the paper defines the category $$\mathbf {NCP}$$ , whose objects are “node-and-choice preforms”, each of which consists of a node set, a choice set, and an operator mapping node-choice pairs to nodes. I characterize the $$\mathbf {NCP}$$ isomorphisms, define a forgetful functor from $$\mathbf {NCP}$$ to $$\mathbf {Tree}$$ , and show that $$\mathbf {Tree}$$ is equivalent to the full subcategory of $$\mathbf {NCP}$$ whose objects are perfect-information preforms. The paper also shows that many game-theoretic entities can be derived from preforms, and that these entities are well-behaved with respect to $$\mathbf {NCP}$$ morphisms and isomorphisms.