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.

References

Reference Towards Foundations of Categorical Cybernetics [towards-cybercat]

Abstract

We propose a categorical framework for processes which interact bidirectionally with both an environment and a “controller”. Examples include open learners, in which the controller is an optimiser such as gradient descent, and an approach to compositional game theory closely related to open games, in which the controller is a composite of game-theoretic agents. We believe that “cybernetic” is an appropriate name for the processes that can be described in this framework. 

@article
{towards-cybercat, title={Towards Foundations of Categorical Cybernetics}, volume={372}, ISSN={2075-2180}, DOI={10.4204/EPTCS.372.17}, url={https://arxiv.org/abs/2105.06332}, journal={Electronic Proceedings in Theoretical Computer Science}, author={Capucci, Matteo and Gavranović, Bruno and Hedges, Jules and Rischel, Eigil Fjeldgren}, year={2022}, month={Nov}, pages={235–248} }

Reference Monoidal Grothendieck Construction [moeller-vasilakopoulou]

  • July 22, 2020
  • Joe Moeller, Christina Vasilakopoulou
 
 @article
{moeller-vasilakopoulou, title={Monoidal Grothendieck Construction}, volume={35}, number={31}, journal={Theory and Applications of Categories}, author={Moeller, Joe and Vasilakopoulou, Christina}, year={2020}, month={Jul}, pages={1159-1207},language={en} }

Reference The algebra of predicting agents [bolt-hedges-winschel-predicting]

Abstract

  • March 27, 2018
  • J. Bolt, Jules Hedges, Viktor Winschel

The category of open games, which provides a strongly compositional foundation of economic game theory, is intermediate between symmetric monoidal and compact closed. More precisely it has counits with no corresponding units, and a partially defined duality. There exist open games with the same types as unit maps, given by agents with the strategic goal of predicting a future value. Such agents appear in earlier work on selection functions. We explore the algebraic properties of these agents via the symmetric monoidal bicategory whose 2-cells are morphisms between open games, and show how the resulting structure approximates a compact closed category with a family of lax commutative bialgebras. 

 @article
{bolt-hedges-winschel-predicting, title={The algebra of predicting agents}, url={https://www.semanticscholar.org/paper/The-algebra-of-predicting-agents-Bolt-Hedges/3dfd6ac5f10eb0a1bf83f61ccda940df86b5ce5c}, abstractNote={The category of open games, which provides a strongly compositional foundation of economic game theory, is intermediate between symmetric monoidal and compact closed. More precisely it has counits with no corresponding units, and a partially defined duality. There exist open games with the same types as unit maps, given by agents with the strategic goal of predicting a future value. Such agents appear in earlier work on selection functions. We explore the algebraic properties of these agents via the symmetric monoidal bicategory whose 2-cells are morphisms between open games, and show how the resulting structure approximates a compact closed category with a family of lax commutative bialgebras.}, journal={ArXiv}, author={Bolt, J. and Hedges, Jules and Winschel, Viktor}, year={2018}, month={Mar} }

Reference Compositional game theory [hedges-etal-comp-gametheory]

Abstract

  • February 15, 2018
  • Neil Ghani, Jules Hedges, Viktor Winschel, Philipp Zahn

We introduce open games as a compositional foundation of economic game theory. A compositional approach potentially allows methods of game theory and theoretical computer science to be applied to large-scale economic models for which standard economic tools are not practical. An open game represents a game played relative to an arbitrary environment and to this end we introduce the concept of coutility, which is the utility generated by an open game and returned to its environment. Open games are the morphisms of a symmetric monoidal category and can therefore be composed by categorical composition into sequential move games and by monoidal products into simultaneous move games. Open games can be represented by string diagrams which provide an intuitive but formal visualisation of the information flows. We show that a variety of games can be faithfully represented as open games in the sense of having the same Nash equilibria and off-equilibrium best responses. 

 @article
{hedges-etal-comp-gametheory, title={Compositional game theory}, url={http://arxiv.org/abs/1603.04641}, DOI={10.48550/arXiv.1603.04641}, number={arXiv:1603.04641}, publisher={arXiv}, author={Ghani, Neil and Hedges, Jules and Winschel, Viktor and Zahn, Philipp}, year={2018}, month={Feb} }

Reference Rational choice and the structure of the environment [simon-environment-satisficing]

Abstract

  • 1956
  • H. A. Simon

In this paper I have attempted to identify some of the structural characteristics that are typical of the psychological environments of organisms. We have seen that an organism in an environment with these characteristics requires only very simple perceptual and choice mechanisms to satisfy its several needs and to assure a high probability of its survival over extended periods of time. In particular, no utility function needs to be postulated for the organism, nor does it require any elaborate procedure for calculating marginal rates of substitution among different wants. 

 @article
{simon-environment-satisficing, address={US}, title={Rational choice and the structure of the environment}, volume={63}, ISSN={1939-1471}, DOI={10.1037/h0042769}, number={2}, journal={Psychological Review}, publisher={American Psychological Association}, author={Simon, H. A.}, year={1956}, pages={129-138} }

Reference Non-Cooperative Games [nash-noncoop-games]

 
 @article
{nash-noncoop-games, title={Non-Cooperative Games}, volume={54}, ISSN={0003-486X}, DOI={10.2307/1969529}, number={2}, journal={Annals of Mathematics}, publisher={[Annals of Mathematics, Trustees of Princeton University on Behalf of the Annals of Mathematics, Mathematics Department, Princeton University]}, author={Nash, John}, year={1951}, pages={286-295} }

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