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.

Context

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.

Related

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))\}