## Games I

2007-07-03 § 1 Comment

When I started doing research, I mostly worked on categories of games. I even went so far as to write a first-year report that suggested — even confidently claimed — that I would write a thesis on the subject. Well, I’m writing that thesis now, and games appear only in passing in a single paragraph. But recently, one or two people have expressed some interest in some of the ideas in that first-year report, so I’d like to flesh out one of idea that is only sketched very vaguely in what I wrote.

The starting point is the idea that a simple category of games is (equivalent to) the initial model of a certain simple theory. Before I explain, I should make it clear that this observation is not original: it’s really just a different way of thinking about some of the ideas of Polarized category theory, modules, and game semantics (Cockett and Seely).

Say that a *lift operator* on a category is a functor , self-adjoint on the right. That means there is a natural isomorphism

or alternatively that there is a natural isomorphism — the unit of the adjunction — with components

such that the composite

is the identity.

Now say that an lp-category is a category equipped with a lift operator and finite products. I claim that the initial lp-category is equivalent to the category of *finite, simple games, with deterministic, winning strategies*.

There’s a little subtlety here, which perhaps is worth mentioning. Products are defined in a non-algebraic way, by a universal property, but if we want to talk about the initial model then we need our structure to be algebraic. This issue is usually glossed over, because there is an easy way of dealing with it — at least if you believe in the axiom of choice. If you *choose* a product cone for each pair of objects, and you choose a terminal object, these choices suffice to determine a unique monoidal structure representing the product; a functor strictly preserves this monoidal structure just when it takes each chosen product cone to a chosen product cone in the target. It’s actually more convenient for us to have easy access to -ary products for arbitrary finite , so we shall go further and insist that a product cone be chosen for every finite set of objects. (This gives rise to what Tom Leinster calls an *unbiased* monoidal structure on the category.)

Having found a suitably algebraic notion of lp-category, there is clearly an initial such thing, by the usual syntactic shenanigans. Let’s call it . Every object of is isomorphic to one of the form

where each is of the same form, recursively. (The recursion is grounded by the empty product, i.e. the terminal object, which we’ll write as .)

Thus the objects of correspond to finite trees. For example, the object can be drawn as

Now, the claim is that a morphism in is a total strategy for the game , where the trees and are regarded as games.

It’s pretty clear that at least *some* of the morphisms of correspond to strategies in a reasonably simple way. I’ll give a recursive definition of “strategic” morphisms:

- Given a collection of strategic morphisms, the tuple is strategic. (In particular the case where the collection is empty implies that the unique map is strategic, which constitutes a base case for the recursion.) This represents the strategy where, when the opening O-move is in component , we then play according to strategy .
- Given a collection of objects , and a strategic morphism for some , the composite
is strategic. This is the strategy in which the (unique) opening O-move is replied to in component ‘‘ on the left, and then play continues according to the strategy .

- Given a collection of objects , and a strategic morphism for some , the composite
is strategic. This corresponds to the strategy in which the opening O-move is replied to in component ‘‘ on the right, and then play continues according to .

All that remains is to show that every morphism is strategic. It’s easy enough to show that every *identity* morphism is strategic, by induction over the tree structure of the object and using rules 1 and 2. It’s also immediate that the basic morphisms and the projections are strategic and 2 implies in particular that the lift of a strategic morphism is strategic. It is trivial to show, using 1, that the strategic morphisms are closed under tupling. Hence it remains only to show that the composite of two strategic morphisms is strategic.

Now, most of the cases are trivial. The one that isn’t is the case of a tuple of 3-maps followed by a 2-map. (Of course this is the case where play continues on the hidden board, so you’d expect this to be the interesting case.) The projection extracts one of the elements of the tuple, so it amounts to considering the composite

where and are strategic. Since is a map into a product, we can go further and extract the appropriate component of , which is clearly also strategic, so it suffices to show that the composite

is strategic whenever and are. This may be proved by induction over : if is of type 2, then we have

which, by naturality of , is of type 3. If is of type 3, then we have , and the map is

for some that is simpler than . Using the naturality of and the adjunction triangle, this is

and the inductive hypothesis applies.

This is getting long, so I’ll continue the story in another post.

[…] Last time, I explained how the category of finite simple games is equivalent to the initial lift-product category. Now I want to show how this fact can be used to find nice ways of representing strategies. […]