Games II

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

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

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.

This entry was posted in category theory, chatter and tagged , . Bookmark the permalink.

1 Response to Games II

1. Pingback: Games I « Bosker Blog