« Home

Menu

List of Publications
Blog
Problems that haunt me

Definition [efr-U99C]

May 6, 2025
Eigil Fjeldgren Rischel

We denote by $\mathsf {Game}(\mathsf {SLens}(\mathcal {D}))$ the symmetric monoidal category of strategic equivalence classes of open games.

Context

Open games in Monoidal categories [efr-CA6T]

May 4, 2025
Eigil Fjeldgren Rischel

Definition [efr-EGK8]

May 4, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a monoidal category. A selection relation on an object $A \in \mathcal {C}$ is a relation $\epsilon \subseteq \mathcal {C}(I,A) \times \mathcal {C}(A,I)$ . We write $\epsilon (a,k)$ for the statement $(a,k) \in \epsilon$ .

Selection relations are ordered by inclusion, and so form a (posetal) category, which we denote $\mathbb {S}_\mathcal {C}(A)$ . Given $f: A \to B,$ we define the pushforward on selection relations by $f_*\epsilon = \{(fx,k) \mid (x, kf) \in \epsilon \}$ . In other words, $f_*\epsilon (y,k)$ if and only if there exists $x: I \to X$ so that $fx = y$ and $\epsilon (x, kf)$ .

It is clear that pushforward is monotone, so that this defines a functor $\mathbb {S}_\mathcal {C} : \mathcal {C} \to \mathsf {Cat}$

Remark [efr-YKR3]

May 4, 2025
Eigil Fjeldgren Rischel

Of course, there is an equally good "pull-back" operation on selection relations given by $\{(x,kf) \mid (fx, k) \in \epsilon \}$ (this is the pushforward in $\mathbb {S}_{\mathcal {C}^\mathrm {op}}$ ). These are adjoint representatives of the same profunctor, which should arguably be regarded as the primary object of interest---that is, we could work with a functor $\mathcal {C} \to \mathsf {\mathbb Cat}$ , the category of categories and profunctors, where we say two selection relations $\epsilon \in \mathbb {S}_X, \epsilon ' \in \mathbb {S}_Y$ are related by $f :X \to Y$ if $\epsilon (x, kf) \Rightarrow \epsilon '(fx, k)$ .

However, we will stick with the pushforward definition for now, since it is conceptually simpler and good enough for our purposes.

Example [efr-BNB2]

May 5, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C} = \mathsf {Optic}(\mathsf {Set})$ . There is a selection function $\mathrm {argmax}_X \in \mathbb {S}({\mathbb {R} \choose X})$ defined by $\mathrm {argmax}(x,f)$ if and only if $x$ is a maximum of $f$ . (Identifying maps $I \to {\mathbb {R} \choose X}$ with points $x \in X,$ and maps ${\mathbb {R} \choose X} \to I$ with functions $X \to \mathbb {R}$ )
In the same category, for each $r \in \mathbb {R},$ there is a selection function given by $\epsilon (x,f) \Leftrightarrow f(x) \geq r$ . This corresponds to satisficing at the value $r$ (Reference [simon-environment-satisficing])---that is, selecting any strategy which achieves this value or greater.
For $\mathcal {C} = \mathsf {Optic}(\mathcal {C}'),$ with $\mathcal {C}'$ semiCartesian, there is a selection function $\epsilon (x,k) \Leftrightarrow kx = x$ (using the same identification as above). The agents with this selection function are called predicting agents in Reference [bolt-hedges-winschel-predicting]. These agents attempt to predict the value the environment will return to them.
For $\mathcal {C} = \mathsf {Bun}^\mathrm {fop},$ the fiberwise opposite of manifolds and smooth bundles---that is, the category of lenses between smooth manifolds---there is a selection function on the tangent bundle $TX$ given by $\epsilon (x,k)$ if and only if $k(x) = 0$ ---that is, if $x$ is a fixpoint of the dynamical system identified by $k: X \to TX$ .
Let $\mathcal {A} \to \mathcal {C}$ be a dynamical systems theory and work in the category of lenses. Suppose the monoidal structure on $\mathcal {A}$ is Cartesian, so that a lens $I \to {A \choose X}$ is the same as a map $* \to X$ . Note that $I = T(*)$ has a distinguished section given by the identity. Then there is a selection function on each object $TX$ where a lens $I \to TX$ , given by $x: * \to X,$ is in equilibrium with respect to a lens $TX \leftrightarrows I$ if $x$ is a trajectory between those systems---that is, if it is an equilibrium state of the smooth dynamical system $TX \leftrightarrows I$ . This subsumes the two previous examples.

Definition The Nash Product [efr-PTAE]

May 4, 2025
Eigil Fjeldgren Rischel

Let $\epsilon \in \mathbb {S}(X), \epsilon ' \in \mathbb {S}(Y)$ be selection relations. Their Nash product $\epsilon \boxtimes \epsilon ' \in \mathbb {S}(X \otimes Y)$ is given by $\{(x \otimes y, k) \mid \epsilon (x,k(1_X \otimes y)), \epsilon '(y, k(x \otimes 1_Y))\}$

Let us unpack this very dense definition. Given a context $k: X \otimes Y \to I$ , a strategy $I \to X \otimes Y$ is in equilibrium if:

It decomposes as a tensor product of $x: I \to X, y: I \to Y$ .
Composing $k$ with $y$ , we obtain a map $X \to I$ . This is the context of the first player assuming the second player plays $y$ . $x$ must be an equilibrium strategy for this map. Simultaneously, $y$ must be an equilibrium for the analogous composite of $k$ and $x$ .

Example [efr-5E1V]

May 5, 2025
Eigil Fjeldgren Rischel

Consider the selection relation $\mathrm {argmax}_X \boxtimes \mathrm {argmax}_Y$ on ${\mathbb {R} \times \mathbb {R} \choose X \times Y}$ . A point $(x,y)$ is an equilibrium for a function $k: X \times Y \to \mathbb {R}^2$ if and only if $x$ maximizes $k_1(-,y)$ and $y$ maximizes $k_2(x,-)$ . In other words, if $x,y$ is a Nash equilibrium (Reference [nash-noncoop-games]) in the usual sense for the game with payoff matrix $k$ .

Proposition [efr-Z2BR]

May 4, 2025
Eigil Fjeldgren Rischel

The Nash product $\mathbb {S}(X) \times \mathbb {S}(Y) \to \mathbb {S}(X \otimes Y),$ along with the map $* \to \mathbb {S}(I)$ given by the full set $S(I) \times S(I)$ equips $\mathbb {S}$ with a lax monoidal structure.

Proof

May 4, 2025
Eigil Fjeldgren Rischel

It is trivial to verify associativity and unitality of the monoidal structure. The only hard part is to verify that $\boxtimes$ is actually a natural transformation. To that end, let $f: X \to Y$ and $g: X' \to Y'$ be morphisms of $\mathcal {C}$ . Let $\epsilon \in \mathbb {S}(X), \epsilon ' \in \mathbb {S}(Y)$ .

First consider the statement $(f \otimes g)_*(\epsilon \boxtimes \epsilon ')(s,k)$ . This holds if and only if $s: I \to X \otimes Y$ factors as $(f \otimes g)s'$ so that $(\epsilon \boxtimes \epsilon ')(s', k(f \otimes g))$ . This in turn means $s' = x \otimes x'$ and $\epsilon (x, k(f \otimes f')(1_X \otimes x'))$ and analogously for $\epsilon '$ .

Now consider the statement $f_*\epsilon \boxtimes g_*\epsilon '$ . This means that $s$ factors as $y \otimes y'$ so that $f_*\epsilon (y, k(1_Y \otimes y'))$ and analogously for $y'$ , which in turn means that $y$ factors as $fx$ so that $\epsilon (x, k(1_Y \otimes y')f)$ . Using the axioms of a monoidal category, it is straightforward to see that these two requirements on $x, x'$ are equivalent, hence we have our naturality.

Corollary [efr-UI90]

May 5, 2025
Eigil Fjeldgren Rischel

Since $\mathbb {S}$ is lax monoidal, its Grothendieck construction $\int \mathbb {S}_\mathcal {C}$ acquires a monoidal structure (Reference [moeller-vasilakopoulou]). We write this category $\mathcal {C}_\mathbb {S}$ ---explicitly, it is given as follows:

The objects are pairs $(X,\epsilon )$ where $X \in \mathcal {C}$ and $\epsilon \in \mathbb {S}(X)$ is a selection relation on it
The morphisms are morphisms $f: X \to Y$ so that, for every $x: I \to X, k: Y \to I$ , $\epsilon (x, kf) \Rightarrow \epsilon (fx, k)$
The monoidal structure is given by $(X,\epsilon ) \otimes (Y,\epsilon ') = (X \otimes Y, \epsilon \boxtimes \epsilon ')$

Now we are ready to make the slick definition of open games.

Definition [efr-1WGM]

May 5, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {C}$ be a semiCartesian symmetric monoidal category. The symmetric monoidal double category of open games in $\mathcal {C}$ is $\widetilde {\mathsf {Game}}(\mathcal {C}) = \mathsf {\mathbb Para}_{\mathsf {Optic}(\mathcal {C})_\mathbb {S}}(\mathsf {Optic}(\mathcal {C}))$ .

Note that in this case, $\mathsf {Optic}(\mathcal {C})(I, {A \choose X}) = \mathcal {C}(I,X),$ and $\mathsf {Optic}(\mathcal {C})({A \choose X},I) = \mathcal {C}(X,A)$ . Thus a selection function decides, for each payoff function $X \to A$ , which of the states $I \to X$ are suitable equilibria.

Before we proceed to the case of stochastic lenses, we will pause briefly to make a small modification to the preceding theory as presented in Reference [towards-cybercat]. In a game with forwards play function $\Sigma \times X \to Y,$ there are two ways to talk about the player's "choice"---we may say that the player chooses a strategy $\sigma \in \Sigma ,$ which then has some effect. Or we may say that the choice is really the $y \in Y,$ and the strategy $\sigma$ is the "precommitment" of choosing what to do given each possible $x \in X$ .

Once we introduce randomness---working in $Kl(\Delta )$ , for example---we see that there are two distinct ways for a player to make a random choice: first, his strategy $I \to \Delta (\Sigma )$ may be stochastic---that is, he is choosing a random strategy. Or the morphism $\Sigma \times X \to \Delta (Y)$ may be stochastic---this means each strategy $\sigma$ contains a specification of how to randomly choose $y$ given each possible $x$ .

In the case where $X = *$ , the distinction is between taking $\Sigma = Y$ and letting the play function be the identity, and taking $\Sigma = \Delta (Y)$ and letting the play function be the sampling map which stochastically draws an element from a distribution.

We take the view that the latter is the proper presentation of this game---this goes along with the terminology in the classical game theory literature, which would certainly regard a distribution on the set of possible moves as a (mixed) strategy. Having represented our games like this, we may restrict ourselves to considering deterministic maps $I \to \Sigma$ as strategies. This also fixes the awkwardness in the definition of the Nash product, since now every strategy in $\Sigma _1 \otimes \Sigma _2$ decomposes uniquely as a pair of strategies.

We quickly modify the preceding definitions to make sense of this. Note that we also modify the reparametrization maps to be deterministic (in the base).

Definition Open games in a stochastic module [efr-6I8U]

May 6, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {D}$ be a symmetric monoidal stochastic module fibration over the Markov category $\mathcal {C}$ . Recall that $\mathsf {SLens}(\mathcal {D})$ acquires a symmetric monoidal structure. Denote as usual $\mathsf {SLens}(\mathcal {D})|_\mathrm {det} = \mathsf {SLens}(\mathcal {D}) \times _{\mathcal {C}} \mathcal {C}_\mathrm {det}$ . Note that this is stable under the monoidal product, and acts on $\mathsf {SLens}(\mathcal {D})$ via the inclusion.

Then the category of open games in $\mathcal {D}$ is the category $\widetilde {\mathsf {Game}} = \mathsf {Para}_{(\mathsf {SLens}(\mathcal {D})|_\mathrm {det})_\mathbb {S}}(\mathsf {SLens}(\mathcal {D}))$ .

When $\mathcal {D} \to \mathcal {C}$ is a Markov prefibration, we overload the notation by writing $\widetilde {\mathsf {Game}}(\mathcal {D}) = \mathsf {Game}(\mathcal {D}|_\mathrm {det})$ .

We now introduce the notion of strategic equivalence, which identified two open games if they have the same equilibria for every costate $\overline {\Sigma } \to I$ which can actually occur as a result of pasting the game $\overline {\Sigma } \otimes \bar {X} \to \bar {Y}$ into some larger diagram.

Definition Context [efr-K0Y8]

May 6, 2025
Eigil Fjeldgren Rischel

Let $X,Y$ be objects of a symmetric monoidal category $\mathcal {C}$ . A context for $X,Y$ is a tuple $M \in \mathcal {C}, s: I \to X \otimes M, k: Y \otimes M \to I$ . We denote the set of contexts $\mathrm {Ctx}(X,Y)$ .

Given a morphism $f: P \otimes X \to Y,$ and a context $c = (M,s,k),$ the costate $k(f \otimes 1_M)(1_{P} \otimes s)$ will be called the induced costate.

Remark [efr-I1K5]

May 6, 2025
Eigil Fjeldgren Rischel

The preceding definition clearly works in a non-symmetric monoidal category as well. In this case, arguably, a context should be defined to consist of maps $I \to M_1 \otimes X \otimes M_2, M_1 \otimes Y \otimes M_2 \to I$ . However, the problem with this from our point of view is that it doesn't allow the definition of a costate on $P$ given a parametrized map (since one cannot commute the $P$ past the $M_1$ ), which is what we're interested in.

It is also worth observing that contexts are essentially the same thing as optics ${I \choose I} \to {Y \choose X}$ . We have not specified an equivalence relation on contexts (we do not need it,) but it is easy to see that for any parametrized map, two contexts that are sliding equivalent give the same induced costate.

Definition Strategic Equivalence [efr-R46X]

May 6, 2025
Eigil Fjeldgren Rischel

Let $\mathcal {D}$ be a monoidal stochastic module fibration over a Markov category $\mathcal {C}$ , and consider a 2-cell $\alpha : G_1 \to G_2: \bar {X} \to \bar {Y} \in \widetilde {\mathsf {Game}}(\mathsf {SLens}(\mathcal {D}))$ .

We say this is a strategic equivalence if the underlying map $\Sigma _1 \to \Sigma _2$ in $\mathcal {C}$ is an isomorphism, and for every context $c \in \mathrm {Ctx}(\bar {X},\bar {Y})$ , the induced costate $k$ on $\overline {\Sigma _2}$ has the same equilibria (under this isomorphism) as the composite costate $k\alpha$ on $\overline {\Sigma _1}$

Note that a game up to strategic equivalence is determined by a relation between strategies $I \to \Sigma$ and contexts. This brings us closer to Hedges' original definition of open game from Reference [hedges-etal-comp-gametheory]. The chief difference is that a game in our sense is prevented from "inspecting" the context $Y \to \bar {Y}$ for those $y \in Y$ which are not in the image of $X \times \Sigma \to Y$ , in the sense that whether a given strategy is in equilibrium or not cannot depend on this (since we only see a certain costate on $\Sigma$ ).

Proposition [efr-HLIX]

May 6, 2025
Eigil Fjeldgren Rischel

Strategic equivalence is compatible with composition and tensor in $\widetilde {\mathsf {Game}}(\mathsf {SLens}(\mathcal {D}))$ .

Proof

May 6, 2025
Eigil Fjeldgren Rischel

Let $\alpha : (G_1 \to G_1'): \bar {X} \to \bar {Y}, \beta : (G_2 \to G_2') : \bar {Y} \to \bar {Z}$ be strategic equivalences. By 2-cell composition there is a map $G_2G_1 \to G_2'G_1'$ , which we must show is a strategic equivalence.

Let $c = s,k$ be a context in $\mathrm {Ctx}(\bar {X},\bar {Z})$ . Now a pair of strategies $\sigma _1, \sigma _2$ for $G_1,G_2$ are in Nash equilibrium for the costate induced by this context if and only if $\sigma _1$ is in equilibrium for the costate induced by the context $s: I \to \bar {X} \otimes \bar {M}, k(p_2(\sigma _2) \otimes 1_{\bar {M}}),$ where $p_2$ is the play function of $G_2$ , and the analogous condition holds for $\sigma _2$ .

But if $\alpha ,\beta$ are equivalences, this is clearly equivalent to asking that $\sigma _1,\sigma _2$ be in Nash equilibrium for the costate induced by $c$ on $\overline {\Sigma _1'} \otimes \overline {\Sigma _2}'$ . This concludes the proof.

Definition [efr-U99C]

May 6, 2025
Eigil Fjeldgren Rischel

We denote by $\mathsf {Game}(\mathsf {SLens}(\mathcal {D}))$ the symmetric monoidal category of strategic equivalence classes of open games.

Note that this category of open games retains a 2-categorical structure, given by deterministic maps $\Sigma _1 \to \Sigma _2$ which preserve equilibria in every context. However, we will leave a deeper investigation of this structure for future work.