Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: applied category theory

Topic: generalising open games

Jules Hedges (Apr 20 2020 at 15:16):

I've invited @Alexis Toumi here to explain something about open games with latex enabled, thought I might as well do it in public too in case anyone else is interested. This is the "maximum" generalisation I can think of, which exposes the levers you can pull in the definition to adjust it

Jules Hedges (Apr 20 2020 at 15:19):

The first thing you can do is replace lenses with something that behaves enough like them. Certainly any category of optics works. The maximum generality that works is the thing I called a "category with contexts" in https://arxiv.org/abs/1904.11287. That's a symmetric monoidal category $\mathcal C$ together with a "context" monoidal functor $\mathbb C : \mathcal C \times \mathcal C^{op} \to \mathbf{Set}$, plus a little bit more

Jules Hedges (Apr 20 2020 at 15:20):

Where the motivating example is $\mathcal C = \mathbf{Lens}$ with $\mathbb C ((X^+, X^-), (Y^+, Y^-)) = X^+ \times (Y^+ \to Y^-)$ on objects

Jules Hedges (Apr 20 2020 at 15:21):

That's the first of 2 levels you can pull

Jules Hedges (Apr 20 2020 at 15:24):

The second lever is to replace sets of strategy profiles with objects of a monoidal category $\mathcal M$. That needs to be equipped with a "strategy profiles" functor $\Sigma : \mathcal M \to \mathbf{Set}$ with a colaxator $\Delta : \Sigma (x \otimes y) \to \Sigma (x) \times \Sigma (y)$. It also needs a "valuation" functor $\mathcal P : \mathcal M \to \mathbf{Set}$ (or possibly $\mathcal M^{op} \to \mathbf{Set}$, I'm not sure - so far I've only needed to use it on objects!) which needs to have a laxator $\nabla : \mathcal P (x) \times \mathcal P (y) \to \mathcal P (x \otimes y)$

Jules Hedges (Apr 20 2020 at 15:25):

Where the motivating example is $\mathcal M = \mathbf{Set}$ with cartesian product, $\Sigma$ the identity functor and $\mathcal P$ powerset (I think contravariant powerset), and $\nabla$ is cartesian product of subsets

Jules Hedges (Apr 20 2020 at 15:28):

And there's a variant which I use equally often - where you just have equilibria instead of general best responses - where it's the same except $\mathcal P$ takes every set to $\mathbb B$, and $\nabla$ is logical conjunction

Jules Hedges (Apr 20 2020 at 15:29):

That's the setup. You take an object of $\mathbf{OG}$ to be an object of $\mathcal C$, and an open game $x \to y$ consists of (1) an object $a$ of $\mathcal M$, (2) a function $\Sigma (a) \to \mathcal C (x, y)$, and (3) a function $\Sigma (a) \times \mathbb C (x, y) \to \mathcal P (a)$. The rest of the structure is used to define the monoidal category structure on it

Morgan Rogers (he/him) (Apr 20 2020 at 15:33):

Jules Hedges said:

The second lever is to replace sets of strategy profiles with objects of a monoidal category $\mathcal M$. That needs to be equipped with a "strategy profiles" functor $\Sigma : \mathcal M \to \mathbf{Set}$.

Isn't it a little redundant to replace $\mathbf{Set}$ with something that's constrained to be structured over $\mathbf{Set}$? By which I mean, why not throw away sets altogether? What do you use the strategy profiles functor for?

Jules Hedges (Apr 20 2020 at 15:33):

Because then the valuations $\mathcal P$ can use information that's not present in the set of strategy profiles

Jules Hedges (Apr 20 2020 at 15:35):

Well actually, my original motivation was to fiddle with what equals means for open games, because the default one is weird and broken. My original tweak for $\mathcal M$ was a category whose objects are sets of players composing by disjoint union

Jules Hedges (Apr 20 2020 at 15:36):

There's one more obvious step of generalisation, which is to get rid of $\mathbf{Set}$ and do enriched stuff. But I don't know much about that so I'll leave it for someone else

Morgan Rogers (he/him) (Apr 20 2020 at 15:36):

Jules Hedges said:

Because then the valuations $\mathcal P$ can use information that's not present in the set of strategy profiles

Ah gotcha, you're saying "if our spaces of strategies are structured, we can lift the usual arguments up the forgetful functor $\Sigma$ into sets"

Mitchell Riley (Apr 21 2020 at 01:29):

I'll record some random thoughts here... Let's use the version of open games where strategies are sets and an open game $x \to y$ is specified by a triple $(\Sigma, p : \Sigma \to C(x,y), b : \mathbb{C}(x,y) \to Rel(\Sigma))$.

I think it might be fruitful to consider the category of games with a fixed strategy set $\Sigma$, let's call it $G_\Sigma$. The composite of two games $(p, b)$ and $(p', b')$ is then given by the play function $\sigma \mapsto p(\sigma) p'(\sigma)$ and best response relation given by $h,k \mapsto bh,kp'(\sigma) \times b'p(\sigma)h,k$

If we have a function $f : \Sigma \to \Sigma'$, then we get a pullback functor $G_{\Sigma'} \to G_\Sigma$: on $(p, b)$ we just precompose $p$ with $f$, and post-compose $b$ with $Rel(f)$, because $Rel$ acts contravariantly. If we're lucky this all fits together into a pseudofunctor $\mathrm{Set}^\mathrm{op} \to \mathrm{Cat}$, and then the Grothendieck construction should give a category of open games '$G$'.

This isn't exactly what we want though, composition in '$G$' is not the kind of composition that takes the product of the strategy sets. But we can implement that composition ourselves using the pullback functors. If we want to compose two games with strategy sets $\Sigma$ and $\Sigma'$ then we pull each of them back to $\Sigma \times \Sigma'$ along the projections, and then calculate the composite in $G_{\Sigma \times \Sigma'}$. I think this unwinds to the right kind thing in the end?

We might also be interested in cells between open games. Here we can use the fact that $Rel(\Sigma)$ is a poset under inclusion. So we might define $(p, b) \leq (p', b')$ when $p = p'$ and $b[h,k] \leq b'[h,k]$. Each $G_\Sigma$ is (hopefully) then poset-enriched, and maybe that transfers to '$G$' somehow?

I'm not sure if this is going anywhere but it could be a neat way to package up everything.

Jules Hedges (Apr 21 2020 at 10:07):

Yep. I worked out most of this, whatever I did work write down should be in https://arxiv.org/abs/1711.07059. I remember working out that [open games, morphisms of open games] is fibred over Set, and the pullback operation you wrote down is actually really useful in practice

Jules Hedges (Apr 21 2020 at 10:10):

This isn't exactly what we want though, composition in '$G$' is not the kind of composition that takes the product of the strategy sets. But we can implement that composition ourselves using the pullback functors. If we want to compose two games with strategy sets $\Sigma$ and $\Sigma'$ then we pull each of them back to $\Sigma \times \Sigma'$ along the projections, and then calculate the composite in $G_{\Sigma \times \Sigma'}$. I think this unwinds to the right kind thing in the end?

I think I missed this part though. That's compatibility between the fibred structure of the vertical category with horizontal composition. I wonder if this thing has a name.... a fibred bicategory? [technically I have a double category of open games, but morally same thing for this purposes]

Jules Hedges (Apr 21 2020 at 10:13):

The last thing you wrote is the obvious monoidal bicategory structure of open games. It turns out that in order to make it do anything useful you need to extend it to a monoidal double category. But it also turns out that there's (at least) 2 different inequivalent ways of doing that, which do different useful things. So it's fun, can't just write down the One True Answer and be done

Jules Hedges (Apr 21 2020 at 10:16):

The fact that each fibre over a fixed $\Sigma$ is posetal is quite convenient, because it means infinitely repeated decision processes are just greatest fixpoints in a poset, which are easier to handle than final coalgebras in a double category

Jules Hedges (Apr 21 2020 at 10:17):

(You get an idea of how much knowledge about open games just exists in my head because I always get distracted from writing it down......)

Mitchell Riley (Apr 21 2020 at 11:45):

I don't think the '$G$' I described is quite the same thing as $\mathrm{Game}_v$ from your paper.

In '$G$' the objects are pairs of a set $\Sigma$ and an object $x \in C$. A morphism $(\Sigma, x) \to (\Sigma', y)$ is given by a function $f : \Sigma \to \Sigma'$ and a game $x \to y$ with strategy set $\Sigma$. (Yes this is a bit silly, the $f$ and the $\Sigma'$ are not particularly involved)

In $\mathrm{Game}_v$, if I'm reading correctly, the objects are triples of $x, y \in C$ and a game $x \to y$. And a morphism $(x,y,g) \to (x',y',g')$ has a bunch of components.

Mitchell Riley (Apr 21 2020 at 11:57):

I should have been more explicit when defining $G_\Sigma$, I mean the category with objects the same objects as $C$, and morphisms $x \to y$ given by games with strategy set $\Sigma$.

Alexis Toumi (Apr 27 2020 at 06:59):

thanks for sharing this @Jules Hedges !
i remember you mentioning an "up-to-best-response" equivalence between scalars of open games and games in normal form. is there a reference where the details for this are sketched? maybe i should read your thesis directly?