Games II

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 \mathbb{C} there is a unique functor

\mathbf{LP}\to\mathbb{C}

that strictly preserves the lp-structure. Where this functor is faithful, the morphisms of the target category \mathbb{C} 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 X induces a lift operator (-\multimap X), since we have

\mathbb{C}(A, B\multimap X) \cong \mathbb{C}(A\otimes B, X)\cong\mathbb{C}(B\otimes A, X)\cong\mathbb{C}(B, A\multimap X).

For example, the contravariant powerset functor 2^- on \mathrm{Set} 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 \mathbf{LP} itself — are of this form.

An example that will be important in a moment is the category \mathrm{Rel}* of pointed sets and point-reflecting relations. An object of \mathrm{Rel}* is a pair (X, *) of a set X and a chosen element *\in X. A morphism R: (X,*)\to(Y,*) is a relation X\mathrel{\rlap{\(\;\,+\)}\mathord{\longrightarrow}} Y such that (x,*)\in R implies x=*. Alternatively, we could define a morphism to be a relation X-\{*\} \mathrel{\rlap{\(\;\,+\)}\mathord{\longrightarrow}} Y. This category is symmetric monoidal closed: the tensor is defined as (X,*)\otimes(Y,*) = (X\times Y, \langle *,*\rangle) with unit I=(\{*\},*). The internal hom is a semi-coalesced product:

(X,*)\multimap(Y,*) = (X\times(Y-\{*\})+\{*\}, *).

We’re particularly interested in the lift operator \mathop\uparrow X = X\multimap I, which adds a single element to the set X 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 \mathbb{C}, and a ‘lifting’ object L\in\mathbb{C}. Consider the comonad L\times-, and pass to its co-Kleisli category \mathbb{C}_{L\times-}. This has products given as in \mathbb{C}, and a lift operator given as \mathop\uparrow(L\times-), where \mathop\uparrow is the lift operator of \mathbb{C}. This construction may be used to construct non-trivial lp-categories from trivial ones. In the above, we started with \mathrm{Rel}, which has a trivial lift given by the equivalence between \mathrm{Rel} and \mathrm{Rel}^{\mathrm{op}}, and took the one-element set (tensor unit) as the lifting object.

Proposition. Let \mathbb{C} be an lp-category. If:

  1. The lift functor is faithful,
  2. For every span X \mathrel{\mathop{\longleftarrow}\limits^{f}} B \mathrel{\mathop{\longrightarrow}\limits^{g}} Y, the diagram

    Square diagram

    does not commute.

  3. Given finite collections (X_i | i\in I) and (Y_j | j\in J) of objects,
    indices m\in I and n\in J, and maps f: \prod_j \mathop\uparrow Y_j \to X_m
    and g: \prod_i \mathop\uparrow X_i \to Y_n, the diagram

    Pentagon diagram

    does not commute.

then the canonical functor \mathbf{LP}\to\mathbb{C} is faithful.

Proof. Recall from Games I the recursive construction of the morphisms of \mathbf{LP}. We’ll show that, in a category satisfying the conditions above, this construction produces distinct morphisms of \mathbb{C}. Since the tupling operation is automatically faithful, it suffices to consider morphisms whose target is a lift, i.e. morphisms

\prod_i\mathop\uparrow X_i\to\mathop\uparrow\prod_j\mathop\uparrow Y_j.

Such a morphism is either

\prod_i\mathop\uparrow X_i \mathrel{\mathop{\longrightarrow}\limits^{\pi_m}} \mathop\uparrow X_m \mathrel{\mathop{\longrightarrow}\limits^{\mathop\uparrow f}} \mathop\uparrow\prod_j\mathop\uparrow Y_j

for some m\in I and f: \prod_j\mathop\uparrow Y_j\to X_n, or

\prod_i\mathop\uparrow X_i \mathrel{\mathop{\longrightarrow}\limits^{g}} Y_n \mathrel{\mathop{\longrightarrow}\limits^{\eta_{Y_n}}}\mathop\uparrow\mathop\uparrow Y_n \mathrel{\mathop{\longrightarrow}\limits^{\mathop\uparrow\pi_n}} \mathop\uparrow\prod_j\mathop\uparrow Y_j

for some n\in J and g: \prod_i\mathop\uparrow X_i \to Y_n. We shall write the former as L_m(f), and the latter as R_n(g). Notice that L_n(f) corresponds, under the lifting adjunction, to R_n(f). Now, condition 1 implies that L_m(f)\neq L_m(g) whenever f\neq g, and similarly R_n(f)\neq R_n(g) whenever f\neq g. Condition 2 implies that L_m(f)\neq L_n(g) whenever m\neq n, and similarly for R. And finally, condition 3 implies that L_m(f)\neq R_n(g) for all suitable m, n, f and g.

For example, \mathrm{Set} with the powerset lift fails condition 2. On the other hand, \mathrm{Rel}* 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 X\to Y is represented by a relation between the positions of X and the positions of Y.

More refined interpretations are possible, along the same lines. For example, there is a category \mathrm{Coh}* of pointed coherence spaces, built from \mathrm{Coh} in the same way as \mathrm{Rel}* is built from \mathrm{Rel}. In other words, \mathrm{Coh}* is the co-Kleisli category of I\times- in \mathrm{Coh}. This category also satisfies the conditions of the proposition above — clearly so, since it has a faithful lp-functor to \mathrm{Rel}* 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.

Tagged: ,

§ One Response to Games II

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading Games II at Bosker Blog.

meta

Follow

Get every new post delivered to your Inbox.

Join 779 other followers

%d bloggers like this: