Open Games with External Choice [efr-SREZ]

Let \mathcal {C} be an extensive Markov category. Let \mathcal {D} be a monoidal stochastic module fibration with Markov structure, which has coproducts which are preserved by the pullbacks. Recall that \mathsf {SLens}(\mathcal {D}) acquires two monoidal structures: one from dualizing the given monoidal structure on \mathcal {D}, which we simply denote \otimes ,I, and one from taking the coCartesian monoidal structure in the fiber (which is Cartesian after taking the fiberwise dual, of course), which we denote \&, \top . Note that (\mathsf {SLens}(\mathcal {D}), \&) is a Markov category. For the rest of this section, fix \mathcal {D}, \mathcal {C} like this.

Lemma [efr-Y2ZN]

Let \bar {X},\bar {Y} be objects in \mathsf {SLens}(\mathcal {D}), and let I \to I + I be a morphism in \mathcal {C}. Then there is a canonical map \bar {X} \& \bar {Y} \to \bar {X} + \bar {Y}, so that the underlying map is X \otimes Y \to (X \otimes Y) \otimes (I + I) \cong X \otimes Y + X \otimes Y \to X + Y

Proof

The first map in the factorization has a deterministic retract (deleting the I+I component,) and using the coproduct-preservation, the coproduct over X + Y and \bar {X} \& \bar {Y} pull back to the same object over X \otimes Y \otimes (I + I). Composing the induced stochastic-Cartesian map and the Cartesian map gives the canonical map we wanted.

With the interpretation that \overline {X} \& \overline {Y} is the object \overline {X}_x + \overline {Y}_y indexed over X \otimes Y, this map simply selects one branch randomly and marginalizes to that coordinate in X \otimes Y, then includes the returned value into the coproduct.

Definition [efr-98DR]

When \mathcal {C}, \mathcal {D} as above, \widetilde {\mathsf {Game}}(\mathsf {SLens}(\mathcal {D})) acquires a monoidal structure which we call external choice, and write \oplus , given on objects by the coproduct + in \mathsf {SLens}(\mathcal {D}), and on morphisms by the following formula:

Given two open games G_1 = (\overline {\Sigma _A} \otimes \overline {A_1} \to \overline {A_2}, \epsilon _A), G_2 = (\overline {\Sigma _B} \otimes \overline {B_1} \to \overline {B_2}, \epsilon _B), their external choice is has parameter \Sigma _A \& \Sigma _B. The play map is given by (\Sigma _A \& \Sigma _B) \otimes (A_1 + B_1) \cong (\Sigma _A \& \Sigma _B) \otimes A_1 + (\Sigma _A \& \Sigma _B) \otimes B_1 \to \Sigma _A \otimes A_1 + \Sigma _B \otimes B_1 \to A_2 + B_2 The selection relation \epsilon _A \oplus \epsilon _A is given (up to equivalence) as follows: Given a context k: \overline {\Sigma _A} \& \overline {\Sigma _B} \to I, and a deterministic state I \to \overline {\Sigma _A} \& \overline {\Sigma _B}, they are in equilibrium if

  1. k factors over the canonical \overline {\Sigma _A} \& \overline {\Sigma _B} \to \overline {\Sigma _A} + \overline {\Sigma _B} for some c: I \to I + I.
  2. The factorization being given by k_A, k_B : \overline {\Sigma _A}, \overline {\Sigma _B} \to I ,and I \to \overline {\Sigma _A} \& \overline {\Sigma _B} being given by \sigma _A, \sigma _B : I \to \overline {\Sigma _A}, \overline {\Sigma _B}, we have \epsilon _A(\sigma _A,k_A), \epsilon _B(\sigma _B, k_B)

The idea behind the external choice operator is that, for all the contexts which can actually occur as a result of pasting a game G \oplus G' into a larger string diagram, the map X \times X' \to \overline {X} + \overline {X}' has the given form---that is, the probability of landing in each of the two fibers does not depend on the chosen x,x' and the conditional distributions on the \overline {X} component of the fiber depend only on x \in X. Hence we need only concern ourselves with which states are equilibria for contexts of this form. The choice of the empty set of equilibria for other contexts is merely a convention.

[efr-VB6A]

Given a state I \to A + B in a Markov category with coproducts, we say a pair I \to A, I \to B form a pair of conditionals if the copairing I + I \to A + B is a Bayesian inverse of the map A + B \to I + I.

Given a state I \to \bar {X} + \bar {Y} in \mathsf {SLens}(\mathcal {D}), we say a pair of maps I \to \bar {X}, I \to \bar {Y} form a pair of conditionals if the underlying maps do.

Theorem [efr-MLF1]

As defined above, \oplus is a symmetric monoidal structure on \widetilde {\mathsf {Game}}(\mathsf {SLens}(\mathcal {D})).

Proof

The monoidal coherences come from the monoidal structure of +, and it is trivial to see that they preserve the selection relations. The only nontrivial part is proving that \oplus is functorial. Hence let G_1: A_1 \to B_1, G_1' : B_1 \to C_1, G_2: A_2 \to B_2, G_2' : B_2 \to C_2 be games. The strategy set of (G_1' \oplus G_2')\circ (G_1 \oplus G_2) is given by (\Sigma _1 \& \Sigma _2) \otimes (\Sigma _1' \otimes \Sigma _2') For (G_1' \circ G_1) \oplus (G_2' \circ G_2), by (\Sigma _1 \otimes \Sigma _1') \& (\Sigma _2 \otimes \Sigma _2').

In the base, these are the same object \Sigma _1 \otimes \Sigma _2 \otimes \Sigma _1' \otimes \Sigma _2'. In the fiber, they are given respectively by (\overline {\Sigma _1} + \overline {\Sigma _2}) \otimes (\overline {\Sigma _1}' + \overline {\Sigma _2'}) and (\overline {\Sigma _1} \otimes \overline {\Sigma _1'}) + (\overline {\Sigma _2} \otimes \overline {\Sigma _2}'). Note the coproducts here are the fiberwise ones. There is an obvious lens from the former to the latter (given by the identity map on the base, and the inclusion of two summands in a fourfold coproduct---note that lenses go backwards in the fiber). Letting I \to (A_1 \oplus A_2) \otimes M, (C_1 \oplus C_2) \otimes M \to I be a context, and going through the definitions, it is clear that the resulting contexts for the former game factors as this lens followed by the context for the latter game. In other words, this lens is a reparametrization map between the two games. It suffices to verify it is an equivalence.

Unpacking the equivalence relation on (G_1' \oplus G_2')(G_1 \oplus G_2), note that (in all the possible contexts,) the signal to G_1 does not depend on the action of G_2' and vice versa, and so for G_1' and G_2. Hence they are in equilibrium if and only if they are in equilibrium in G_1'G_1 for the given context (conditioned on that branch), and similarly the other two. This proves the desired equivalence.

Example [efr-4CSL]

Consider the (Grothendieck) fibration \mathsf {Set}^\to \to \mathsf {Set}, which can be viewed as a Markov fibration. Let f: {\mathbb {R} \choose \Sigma } \otimes {\bar {X} \choose X} \leftrightarrows {\bar {Y} \choose Y} be a parameterized lens. Denote by \mathrm {argmax}_f the open game {\bar {X} \choose X} \to {\bar {Y} \choose Y} with parameters {\mathbb {R} \choose \Sigma }, underlying parameterized lens f, and equilibrium relation given by \mathrm {argmax}.

Then if g: {\mathbb {R} \choose \Sigma '} \otimes {\overline {X'} \choose X'} \leftrightarrows {\overline {Y'} \choose Y'} is another parameterized lens, we have \mathrm {argmax}_f \oplus \mathrm {argmax}_g \cong \mathrm {argmax}_{f \oplus g}, where by an abuse of notation f \oplus g denotes the paramterized lens {\mathbb {R} \choose \Sigma \times \Sigma '} \otimes ({\overline {X} \choose X} \oplus {\overline {X'} \choose X'}) \to {\overline {Y} \choose Y} \oplus {\overline {Y'} \choose Y'} given by distributing into the coproduct, then projecting into the relevant factor of the product \Sigma \times \Sigma ' and applying either f or g

A context for either of these games consists of an element of X + X' and a function k: Y + Y' \to \mathbb {R}. The external choice game can be seen as having two players, one who gets to play if the context chooses an element in X, who must output an element y \in Y and optimize k(y) (according to his private utility function \Sigma \times X \times \bar {Y} \to \mathbb {R}), the other playing when the input is in X' and who must choose an element in y'. The single argmax game can be seen as a single player, who is constrained to play inside the same "branch" of the game as the input (this constraint is encoded in the lens f \oplus g), and whose utility function is given by the first players' in the first branch, and the second players' in the second branch.x

Example [efr-BNT1]

Let G: {* \choose X} \to {R \choose Y} be a game, representing an agent who is optimizing the return value r \in R in some sense. Then G \otimes (1_I \oplus 1_I = 1_{I + I}) represents the same agent, whose payoff may now depend on an additional bit (a value in I + I), but whose decisions may not depend on that bit (his selection function may still depend on its distribution).

On the other hand, G \oplus G (\cong G \otimes 1_I \oplus G \otimes 1_I) represents the same situation, but where the player's strategy may depend on the bit---he provides two strategies \sigma _1,\sigma _2, one for each possibility.

This proves that \otimes does not distribute over \oplus

Context

Open Games with external choice in Markov Fibrations [efr-GFG0]

Introduction [efr-7EHV]

Game theory is a field of economics which studies mathematical models of human decisionmaking. Classically, game theory is particularly interested in the behavior resulting from individual agents optimizing simple objectives (such as the expected value of some real-valued function of each players' decision) when multiple such players interact. Although the analysis of games, obviously, has a long prehistory, the field was put on its modern theoretical footing by Von Neumann in 1928 (Reference [neumann-games], see also Reference [neumann-morgenstern-games] for a more thorough treatment from this era). The basic problem studied here is this: given two finite sets \Sigma _1, \Sigma _2 of strategies---that is, the choices available to the two players---and a function f: \Sigma _1 \times \Sigma _2 \to \mathbb {R} which assigns to a pair of such choices a score, which player 1 seeks to maximize and player 2 seeks to minimize, what can be said about the rational decisionmaking of each player?

Suppose each player has access to some source of randomness, so that they may each choose a distribution on their respective strategy set to play. This is called a mixed strategy. Suppose player 2 has the opportunity to move knowing the distribution chosen by player 1 (but not the value drawn from it), and suppose he prefers to minimize the expected outcome of the game. Writing f(\mu _1,\mu _2) for E_{x \sim \mu _1, y \sim \mu _2}f(x,y) for brevity, if player 1 selects the distribution \mu _1, clearly player 2 must select the distribution \mathrm {argmin}_{\mu _2} f(\mu _1,\mu _2). Knowing this, player 1 will select the distribution \mathrm {argmax}_{\mu _1} \min _{\mu _2} f(\mu _1,\mu _2), and the expected score of the game will be \max _{\mu _1} \min _{\mu _2} f(\mu _1,\mu _2).

If the selection happens in the other order, of course, the result will be \min _{\mu _2} \max _{\mu _1} f(\mu _1,\mu _2). Clearly choosing knowing your opponent's (mixed) strategy can not be a disadvantage compared to choosing with no information, and so we have \min _{\mu _2} \max _{\mu _1} f(\mu _1,\mu _2) \leq \max _{\mu _1} \min _{\mu _2} f(\mu _1,\mu _2). Von Neumann's great minimax theorem is that these values agree, and this implies that by choosing as if your opponent would know your (mixed) strategy, you obtain a result as good as you could have obtained if you knew your opponents' strategy---hence neither player could improve their outcome, even if they had the advantage of greater information.

This is a strong argument for the optimality of such decisions. The key assumption is that the players are perfectly opposed, that is, player 2 seeks to minimize precisely the value that player 1 seeks to maximize. Nash in Reference [nash-noncoop-games] extended the theory to the more general class of games where players simply each have their own utility function, although it should be noted that Nash merely proved the existence of equilibria---that is, strategy sets where no player can improve their situation by switching strategies. It is computationally intractable (Reference [nash-complexity]) to identify Nash equilibria in an arbitrary game, and so to apply the theory we're forced to analyze each game in an ad hoc way.

We will not go intro a serious review of game theory here, we mention the above details mainly to contextualize our future definitions. For a modern reference on game theory see eg Reference [game-theory-maschler-textbook], or Reference [osborne-intro-gametheory] for a textbook treatment.

In his thesis (Reference [hedges-towards-compositional-thesis]), Hedges introduced a novel approach to game theory which he named compositional game theory, studying objects called open games. The idea of open games is to describe a type of "partial" game which has an interface to the world---some part of the payoff function being dependent on an undetermined environment, into which hole can be inserted another game. This is the sense in which they are open. Based on these, one can build a complex game up out of simpler subparts, as well as leverage a string diagramattical syntax to analyze games.

The original definition of open game cannot help but seem somewhat ad hoc. It was quickly realized that a large part of the definition can be understood to say that a game is a function \Sigma \to \mathsf {Lens}({S \choose X},{R \choose Y}) from a strategy set into a set of lenses, and this part of the game composes by lens composition.

The additional data of an open game is a so-called equilibrium relation, which determines which strategies are equilibria in a given situation (each strategy really represents a set of strategies, one for each player). In Reference [towards-cybercat], the author, Capucci, Gavranovic and Hedges demonstrated that this can be further simplified by realizing an open game as a parametrized map in lenses---a morphism in \mathsf {Para}(\mathsf {Lens}(\mathcal {C})) (in fact, one often wants to consider \mathsf {Optic}(\mathcal {C}) for, for example, Markov categories \mathcal {C}, to account for mixed strategies) along with a notion of equilibrium relation defined on the parameter object {\Omega \choose \Sigma }. We will begin this chapter by recapping this idea.

On a conceptual level, there is a natural operation on games, called external choice, which assigns to two open games {A_1 \choose X_1} \to {B_1 \choose Y_1}, {A_2 \choose X_2} \to {B_2 \choose Y_2} a new game, whose environment begins by making a choice between one of these games, lets that one happen, then provides some payoff for it at the end. The natural type for the interface of this operation is {A_1 \choose X_1} + {A_2 \choose X_2} \to {B_1 \choose Y_1} + {B_2 \choose Y_2}, but unfortunately the category of optics doesn't have coproducts. The category of lenses can be extended with coproducts (into dependent lenses), but the analysis of mixed strategies makes probability an absolute necessity for a useful theory of games.

The introduction of Markov fibrations provides a solution to this problem, and in the second half of this chapter, we provide such an external choice operation on open games. Although the approach based on Markov fibrations is novel, the approach to defining the external choice operator is otherwise very similar to one appearing in presently unpublished work by the author, Braithwaite, Hedges and Videla (this paper used a more specialized approach to adding coproducts to \mathsf {Optic}).

Open games in Monoidal categories [efr-CA6T]

Definition [efr-EGK8]

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]

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]
  1. 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})
  2. 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.
  3. 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.
  4. 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.
  5. 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]

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:

  1. It decomposes as a tensor product of x: I \to X, y: I \to Y.
  2. 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]

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]

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

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]

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:

  1. The objects are pairs (X,\epsilon ) where X \in \mathcal {C} and \epsilon \in \mathbb {S}(X) is a selection relation on it
  2. 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)
  3. 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]

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]

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]

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]

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]

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]

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

Proof

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]

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.

Open Games with External Choice [efr-SREZ]

Let \mathcal {C} be an extensive Markov category. Let \mathcal {D} be a monoidal stochastic module fibration with Markov structure, which has coproducts which are preserved by the pullbacks. Recall that \mathsf {SLens}(\mathcal {D}) acquires two monoidal structures: one from dualizing the given monoidal structure on \mathcal {D}, which we simply denote \otimes ,I, and one from taking the coCartesian monoidal structure in the fiber (which is Cartesian after taking the fiberwise dual, of course), which we denote \&, \top . Note that (\mathsf {SLens}(\mathcal {D}), \&) is a Markov category. For the rest of this section, fix \mathcal {D}, \mathcal {C} like this.

Lemma [efr-Y2ZN]

Let \bar {X},\bar {Y} be objects in \mathsf {SLens}(\mathcal {D}), and let I \to I + I be a morphism in \mathcal {C}. Then there is a canonical map \bar {X} \& \bar {Y} \to \bar {X} + \bar {Y}, so that the underlying map is X \otimes Y \to (X \otimes Y) \otimes (I + I) \cong X \otimes Y + X \otimes Y \to X + Y

Proof

The first map in the factorization has a deterministic retract (deleting the I+I component,) and using the coproduct-preservation, the coproduct over X + Y and \bar {X} \& \bar {Y} pull back to the same object over X \otimes Y \otimes (I + I). Composing the induced stochastic-Cartesian map and the Cartesian map gives the canonical map we wanted.

With the interpretation that \overline {X} \& \overline {Y} is the object \overline {X}_x + \overline {Y}_y indexed over X \otimes Y, this map simply selects one branch randomly and marginalizes to that coordinate in X \otimes Y, then includes the returned value into the coproduct.

Definition [efr-98DR]

When \mathcal {C}, \mathcal {D} as above, \widetilde {\mathsf {Game}}(\mathsf {SLens}(\mathcal {D})) acquires a monoidal structure which we call external choice, and write \oplus , given on objects by the coproduct + in \mathsf {SLens}(\mathcal {D}), and on morphisms by the following formula:

Given two open games G_1 = (\overline {\Sigma _A} \otimes \overline {A_1} \to \overline {A_2}, \epsilon _A), G_2 = (\overline {\Sigma _B} \otimes \overline {B_1} \to \overline {B_2}, \epsilon _B), their external choice is has parameter \Sigma _A \& \Sigma _B. The play map is given by (\Sigma _A \& \Sigma _B) \otimes (A_1 + B_1) \cong (\Sigma _A \& \Sigma _B) \otimes A_1 + (\Sigma _A \& \Sigma _B) \otimes B_1 \to \Sigma _A \otimes A_1 + \Sigma _B \otimes B_1 \to A_2 + B_2 The selection relation \epsilon _A \oplus \epsilon _A is given (up to equivalence) as follows: Given a context k: \overline {\Sigma _A} \& \overline {\Sigma _B} \to I, and a deterministic state I \to \overline {\Sigma _A} \& \overline {\Sigma _B}, they are in equilibrium if

  1. k factors over the canonical \overline {\Sigma _A} \& \overline {\Sigma _B} \to \overline {\Sigma _A} + \overline {\Sigma _B} for some c: I \to I + I.
  2. The factorization being given by k_A, k_B : \overline {\Sigma _A}, \overline {\Sigma _B} \to I ,and I \to \overline {\Sigma _A} \& \overline {\Sigma _B} being given by \sigma _A, \sigma _B : I \to \overline {\Sigma _A}, \overline {\Sigma _B}, we have \epsilon _A(\sigma _A,k_A), \epsilon _B(\sigma _B, k_B)

The idea behind the external choice operator is that, for all the contexts which can actually occur as a result of pasting a game G \oplus G' into a larger string diagram, the map X \times X' \to \overline {X} + \overline {X}' has the given form---that is, the probability of landing in each of the two fibers does not depend on the chosen x,x' and the conditional distributions on the \overline {X} component of the fiber depend only on x \in X. Hence we need only concern ourselves with which states are equilibria for contexts of this form. The choice of the empty set of equilibria for other contexts is merely a convention.

[efr-VB6A]

Given a state I \to A + B in a Markov category with coproducts, we say a pair I \to A, I \to B form a pair of conditionals if the copairing I + I \to A + B is a Bayesian inverse of the map A + B \to I + I.

Given a state I \to \bar {X} + \bar {Y} in \mathsf {SLens}(\mathcal {D}), we say a pair of maps I \to \bar {X}, I \to \bar {Y} form a pair of conditionals if the underlying maps do.

Theorem [efr-MLF1]

As defined above, \oplus is a symmetric monoidal structure on \widetilde {\mathsf {Game}}(\mathsf {SLens}(\mathcal {D})).

Proof

The monoidal coherences come from the monoidal structure of +, and it is trivial to see that they preserve the selection relations. The only nontrivial part is proving that \oplus is functorial. Hence let G_1: A_1 \to B_1, G_1' : B_1 \to C_1, G_2: A_2 \to B_2, G_2' : B_2 \to C_2 be games. The strategy set of (G_1' \oplus G_2')\circ (G_1 \oplus G_2) is given by (\Sigma _1 \& \Sigma _2) \otimes (\Sigma _1' \otimes \Sigma _2') For (G_1' \circ G_1) \oplus (G_2' \circ G_2), by (\Sigma _1 \otimes \Sigma _1') \& (\Sigma _2 \otimes \Sigma _2').

In the base, these are the same object \Sigma _1 \otimes \Sigma _2 \otimes \Sigma _1' \otimes \Sigma _2'. In the fiber, they are given respectively by (\overline {\Sigma _1} + \overline {\Sigma _2}) \otimes (\overline {\Sigma _1}' + \overline {\Sigma _2'}) and (\overline {\Sigma _1} \otimes \overline {\Sigma _1'}) + (\overline {\Sigma _2} \otimes \overline {\Sigma _2}'). Note the coproducts here are the fiberwise ones. There is an obvious lens from the former to the latter (given by the identity map on the base, and the inclusion of two summands in a fourfold coproduct---note that lenses go backwards in the fiber). Letting I \to (A_1 \oplus A_2) \otimes M, (C_1 \oplus C_2) \otimes M \to I be a context, and going through the definitions, it is clear that the resulting contexts for the former game factors as this lens followed by the context for the latter game. In other words, this lens is a reparametrization map between the two games. It suffices to verify it is an equivalence.

Unpacking the equivalence relation on (G_1' \oplus G_2')(G_1 \oplus G_2), note that (in all the possible contexts,) the signal to G_1 does not depend on the action of G_2' and vice versa, and so for G_1' and G_2. Hence they are in equilibrium if and only if they are in equilibrium in G_1'G_1 for the given context (conditioned on that branch), and similarly the other two. This proves the desired equivalence.

Example [efr-4CSL]

Consider the (Grothendieck) fibration \mathsf {Set}^\to \to \mathsf {Set}, which can be viewed as a Markov fibration. Let f: {\mathbb {R} \choose \Sigma } \otimes {\bar {X} \choose X} \leftrightarrows {\bar {Y} \choose Y} be a parameterized lens. Denote by \mathrm {argmax}_f the open game {\bar {X} \choose X} \to {\bar {Y} \choose Y} with parameters {\mathbb {R} \choose \Sigma }, underlying parameterized lens f, and equilibrium relation given by \mathrm {argmax}.

Then if g: {\mathbb {R} \choose \Sigma '} \otimes {\overline {X'} \choose X'} \leftrightarrows {\overline {Y'} \choose Y'} is another parameterized lens, we have \mathrm {argmax}_f \oplus \mathrm {argmax}_g \cong \mathrm {argmax}_{f \oplus g}, where by an abuse of notation f \oplus g denotes the paramterized lens {\mathbb {R} \choose \Sigma \times \Sigma '} \otimes ({\overline {X} \choose X} \oplus {\overline {X'} \choose X'}) \to {\overline {Y} \choose Y} \oplus {\overline {Y'} \choose Y'} given by distributing into the coproduct, then projecting into the relevant factor of the product \Sigma \times \Sigma ' and applying either f or g

A context for either of these games consists of an element of X + X' and a function k: Y + Y' \to \mathbb {R}. The external choice game can be seen as having two players, one who gets to play if the context chooses an element in X, who must output an element y \in Y and optimize k(y) (according to his private utility function \Sigma \times X \times \bar {Y} \to \mathbb {R}), the other playing when the input is in X' and who must choose an element in y'. The single argmax game can be seen as a single player, who is constrained to play inside the same "branch" of the game as the input (this constraint is encoded in the lens f \oplus g), and whose utility function is given by the first players' in the first branch, and the second players' in the second branch.x

Example [efr-BNT1]

Let G: {* \choose X} \to {R \choose Y} be a game, representing an agent who is optimizing the return value r \in R in some sense. Then G \otimes (1_I \oplus 1_I = 1_{I + I}) represents the same agent, whose payoff may now depend on an additional bit (a value in I + I), but whose decisions may not depend on that bit (his selection function may still depend on its distribution).

On the other hand, G \oplus G (\cong G \otimes 1_I \oplus G \otimes 1_I) represents the same situation, but where the player's strategy may depend on the bit---he provides two strategies \sigma _1,\sigma _2, one for each possibility.

This proves that \otimes does not distribute over \oplus

Backlinks

Example [efr-IMZ3]

Consider the Markov prefibration \mathsf {TychDiffStoch}^\to \to \mathsf {TychDiffStoch}. Equip this with the section T(X) = X \otimes X \xrightarrow {\pi _0} X - this described discrete-time systems (whose update is required to be smooth in the input and present state). This is clearly a symmetric monoidal functor and thus defines a systems theory. Note that this is completely different from the ordinary tangent bundle, despite the coincidence of notation.

Let m_1: TS_2 \otimes X_1 \leftrightarrows Y_1 and m_2: TS_2 \otimes X_2 \leftrightarrows Y_2 be two bisystems in this theory. As in § [efr-SREZ], we may define a parameterized lens (TS_1 \& TS_2) \otimes (X_1 \oplus X_2) \leftrightarrows (Y_1 \oplus X_2), denoting by \oplus the coproduct in lenses, and by \& the Markov structure defined in Corollary [efr-FT8J]. Observe that TS_1 \& TS_2 is simply the indexed set (S_1 \coprod S_2) \otimes S_1 \otimes S_2 \to S_1\otimes S_2. There is an obvious indexed map from this to T(S_1 \otimes S_2) = S_1 \otimes S_2 \otimes S_1 \otimes S_2, given by (\operatorname {inl} s_1', s_1,s_2) \mapsto (s_1', s_2, s_1, s_2) and (\operatorname {inr} s_2', s_1, s_2) \mapsto (s_1,s_2',s_1,s_2). In words, we receive an update either to the S-state or to the S'-state. We apply this update to the relevant state and leave the other alone. This defines a lens T(S_1 \otimes S_2) \leftrightarrows T(S_1) \& T(S_2), which we may compose with the above to obtain a bisystem T(S_1 \otimes S_2) \otimes (X_1 \oplus X_2) \leftrightarrows Y_1 \oplus Y_2. Let us denote this by m_1 \oplus m_2.

This has very much the same flavor as the external choice for open games, although we will not develop the theory of this operation in detail here.

Now, given a smooth (deterministic) map F: P \times X \to Y, where P,X,Y are smooth manifolds (not merely diffeo-toplogical spaces), we obtain a lens T^*(F): {T^*P \choose P} \otimes {T^*X \choose X} \leftrightarrows {T^*Y \choose Y}, where T^*(-) denotes the cotangent bundle. (This does not, prima facie, make sense for a general diffeo-topological space).

Let us take as given some family of lenses T(S) = {S \otimes S \choose S} \leftrightarrows {T^*S \choose S} for various S. Such an operation amounts to choosing a way of updating s \in S given a cotangent vector---hence we can see it as an optimization algorithm. One example of such would be gradient descent, which given a choice of Riemann structure on S, takes a step of a given length in the direction which most quickly decreases the given covector.

(It should be noted that there are more complicated optimization strategies which don't fit this particular pattern - for example, momentum algorithms have to maintain some extra internal state other than s \in S. But let's stick with this pattern for this example). Note also that we're not assuming the optimizers are a natural transformation or anything like that.

Now we are ready to build the neural network architecture known as a generative adversarial network, or GAN (Reference [gan-paper]). Let us first describe the idea. Our goal is to generate additional samples from some distribution, given a set of existing samples---for example, our goal may be to generate more pictures in the same style as an existing corpus. Suppose our data is of type X, and let d: I \to X be the data distribution. We fix some latent distribution \lambda : I \to L, where L is any space of our choice---usually, L is \mathbb {R}^n and \lambda is a Gaussian. Finally we choose two neural networks, the generator G: P_G \otimes L \to X, and the discriminator D: P_D \otimes X \to \mathbb {R}. The goal of the discriminator is to discriminate real samples from the data from generated samples, by providing a low value on the generated samples and a high value on the true samples.

The training process now goes as follows: for each step of training, we either sample from the latent distribution, and have the generator use this to generate a sample, or draw a sample from the data distribution (choosing between these with some probability p). Then in either case, we have the discriminator score the generated sample. If the sample was generated by the generator, the discriminator's loss is equal to its output, otherwise it is equal to -1 times its output. We update the discriminator according to the gradient of this loss (minimizing it), and update the generator (if we are in the branch where it was run) according to the negative of the gradient of this loss with respect to the generator parameters---this amounts to doing a gradient descent update on the generator for the negative of the discriminator loss.

We can represent this schematically using the following tape diagram (see Reference [tape-diags-monoidal-monads]):

The two "tapes" branching off at the start represent two maps (bisystems) composed by \oplus , while the backwards wires indicate the flow of the gradients. The ground symbol indicates a value being discarded. Note that the theory of tape diagrams has only been developed formally for distributive categories, and for essentilly the same reason as in § [efr-SREZ], we do not have distributivity in this case. However, the interpretation of this diagram is still unambiguous---distributivity is required to make tape diagrams complete, not to make them sound. Concretely, if we tried to represent the tensoring of this system with another system, we would have no way of doing it, but if the category was distributive we could do so by adding this additional system to each of the branches. Still, the figure is best viewed as a visual aid rather than a formal representation.