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.
By definition, for every lp-category 
there is a unique functor
that strictly preserves the lp-structure. Where this functor is faithful, the morphisms of the target category can be used to represent strategies. So we’d like to find some (at least sufficient) conditions under which this functor is faithful.
Before I continue, perhaps I should give some examples of lp-categories. While categories with finite products are generally recognised to abound, the lift structure is probably less familiar. However, there is no shortage of them. In a symmetric monoidal closed category, every object 
induces a lift operator 
, since we have
For example, the contravariant powerset functor 
on 
is a lift operator, as is the dual space operator on the category of vector spaces. Many natural examples — with the notable exception of the lift operator on 
itself — are of this form.
An example that will be important in a moment is the category 
of pointed sets and point-reflecting relations. An object of is a pair 
of a set and a chosen element 
. A morphism 
is a relation 
such that 
implies 
. Alternatively, we could define a morphism to be a relation 
. This category is symmetric monoidal closed: the tensor is defined as 
with unit 
. The internal hom is a semi-coalesced product:
We’re particularly interested in the lift operator 
, which adds a single element to the set and points to the new element.
Actually, there is a general recipe for constructing new lp-categories from old, of which the above is an example. Take an lp-category , and a ‘lifting’ object 
. Consider the comonad 
, and pass to its co-Kleisli category 
. This has products given as in , and a lift operator given as 
, where 
is the lift operator of . This construction may be used to construct non-trivial lp-categories from trivial ones. In the above, we started with 
, which has a trivial lift given by the equivalence between and 
, and took the one-element set (tensor unit) as the lifting object.
Proposition. Let be an lp-category. If:
- The lift functor is faithful,
- For every span
, the diagram
does not commute.
- Given finite collections
and 
of objects,
indices 
and 
, and maps 
and 
, the diagram
does not commute.
then the canonical functor is faithful.
Proof. Recall from Games I the recursive construction of the morphisms of . We’ll show that, in a category satisfying the conditions above, this construction produces distinct morphisms of . Since the tupling operation is automatically faithful, it suffices to consider morphisms whose target is a lift, i.e. morphisms
Such a morphism is either
for some and 
, or
for some and 
. We shall write the former as 
, and the latter as 
. Notice that 
corresponds, under the lifting adjunction, to 
. Now, condition 1 implies that 
whenever 
, and similarly 
whenever . Condition 2 implies that 
whenever 
, and similarly for 
. And finally, condition 3 implies that 
for all suitable 
, 
, 
and 
.
For example, with the powerset lift fails condition 2. On the other hand, does satisfy all three. Therefore strategies may be faithfully represented by relations, in such a way that composition of strategies corresponds to relational composition. This is the standard relational interpretation of games, where a strategy 
is represented by a relation between the positions of and the positions of 
.
More refined interpretations are possible, along the same lines. For example, there is a category 
of pointed coherence spaces, built from 
in the same way as is built from . In other words, is the co-Kleisli category of 
in . This category also satisfies the conditions of the proposition above — clearly so, since it has a faithful lp-functor to that forgets the coherence structure. Therefore the set of positions of a game may be given the structure of a coherence space in such a way that strategies are represented by coherent relations. This is more or less obvious in the present setting, though it takes some real work to prove by hand.
In a similar way, one can start instead with Melliès’s category of hypergraphs, to obtain an even more refined interpretation. Although it’s getting closer, this interpretation is still not full, though we can characterise its image without too much trouble: a relation lies in the image just when it is ‘downward complete’ in the sense of Definition 2.10 of my report. This is not as easy as the faithfulness proofs above, but it’s not hard either. Games I shows that the image consists of those morphisms that satisfy the conditions of my Lemma 2.8, and then we can appeal to Propositions 2.11, 2.12 and 2.19 from the report. With the exception of those three results, I think all the other material of Chapter 2 is subsumed by the approach presented here.
Like this:
Like Loading...
Tagged: categories, games
Leave a Reply
[...] This is getting long, so I’ll continue the story in another post. [...]