2007-07-05 § 1 Comment
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.