# A categorical representation of games

Fernando Tohmé and Ignacio Viglizzo

###### Abstract

Strategic games admit a multi-graph representation, in which two kinds of
relations, accessibility, and preferences, are used to describe how the
players compare the possible outcomes. A category of games with a fixed set of
players $\mathbf{Gam}_{I}$ is built from this representation, and a more
general category $\mathbf{Gam}$ is defined with games having different sets of
players, both being complete and cocomplete. The notion of Nash equilibrium
can be generalized in this context. We then introduce two subcategories of
$\mathbf{Gam}$, $\mathbf{NE}$ and $\mathbf{Gam}^{NE}$ in which the morphisms
are equilibria-preserving. We illustrate the expressivity and usefulness of
this framework with some examples.

##  1 Introduction

Game Theory constitutes one of the main foundations of modern analyses of
interaction among agents (human and otherwise). Large swaths of Economics and
Evolutionary Biology are game-theoretically characterized. Curiously enough,
games have not been categorified until recently. Some previous approaches can
be found in [Vor94], [Lap99], [Jim14], [SD15] and [Str18]. The theory of open
games ([Hed18] [GHWZ18]) pinpoints on one of the main obstacles for a
categorical treatment of games. Namely, compositionality is hard to achieve
without retrofitting the notion of game with an approach based on lenses and
other concepts of the recently developed field of categorical optics [Hed17].

Our goal here differs from the current applied category theory treatments of
games in the literature. Instead of only focusing on the composition of games
as a way of building up new ones, we abstract away payoffs and actions
representing them through binary relations on the sets of possible outcomes of
the game. Then each game becomes a multigraph with relations indexed by the
set of players. The vertices correspond to the outcomes, and for each player,
we consider two sorts of edges, one representing the preferences, and another
indicating which outcomes are effectively reachable through the actions
(accessibility relation). While actions are not explicitly included in the
model, this presentation provides a more flexible and expressive framework for
some aspects of game theory.

We think that our representation of strategic games is at the same time close
enough to the one commonly used by game theory practitioners, yet flexible
enough to allow us to build the basic category-theoretic constructions. The
key for the categorical constructions in this paper are the properties of the
accessibility and preference relations. These relations suffice to define Nash
equilibria and thus facilitate the characterization of a category in which
morphisms among their objects preserve the equilibria.

In the next section, we introduce the representation of strategic games we
will use in the paper. In section 3 we introduce two categories in which these
representations of games are the objects, one with a fixed set of players,
GamI, and another including games with different sets of players, Gam. We
prove that both these categories are complete, cocomplete, and have
exponentials. In section 4 we define subgames and give a generalization of the
notion of Nash equilibrium arising from the interaction between the preference
and accessibility relations. Finally, in section 5 we investigate two
subcategories of Gam in which the morphisms preserve Nash equilibria.

##  2 Multi-Graph Representation of Strategic Games

We are going to consider a category whose objects model some aspects of
strategic games ([OR94]):

######  Definition 2.1.

A strategic game is a structure of the form $G=\langle I,\\{A_{i}\\}_{i\in
I},\\{\pi_{i}\\}_{i\in I}\rangle$ where $I=\\{1,\ldots,n\\}$ is a set of
players and $A_{i},i\in I$ is a finite set of strategies for each player, and
$\pi_{i}:\prod_{i\in I}A_{i}\rightarrow\mathbb{R}$ is player $i$’s payoff.

The critical step in the definition of a category is the specification of the
class of morphisms among its objects. In the case of the category of games,
this requires an alternative definition of game. More specifically, our
approach is based on replacing profiles $a=(a_{1},\ldots,a_{n})\in\prod_{i\in
I}A_{i}$ by the outcomes $o$ obtained when all the players play their actions
in $a$. Even so, we need to be able to preserve in the representation the fact
that individual agents may change the outcome of a game as well as prefer an
outcome over others.

This alternative representation of a game can be seen as defining a
multigraph. That is, as a set of nodes with multiple edges between them
(including loops at the nodes [Tut98]). More specifically, each node
corresponds to an outcome of the game and between any pair of nodes there can
exist, for each player, two types of edges. One type is undirected,
corresponding to the possibility that the player to which it belongs may
change from one outcome to the other. The second type is directed and
represents that one outcome is preferred by the player over the other.

More formally, and similarly to what is observed in [Sch02], we have:

######  Definition 2.2.

A game is $G=\langle I,O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in
I}\rangle$, where $I=\\{1,\ldots,n\\}$ is a set of players and $O$ is a finite
set of outcomes. For each $i\in I$, $R_{i}$ is an accessibility relation, a
subset of $O\times O$. In turn, $\preceq_{i}\subseteq O\times O$ is a preorder
representing player $i$’s preferences over outcomes.

To see how games defined in this way have some of the same properties as those
in the more standard approach in Game Theory above, take as set $O$ of
outcomes the list of the combined actions of all the players, that is, the
profiles of actions $(a_{1},\ldots,a_{i},\ldots,a_{n})$ in $\prod_{i\in
I}A_{i}=O$. Then, given any outcome $o=(a_{1},\ldots,a_{i},\ldots,a_{n})$, an
unilateral change of the action chosen by $i$ (while all other players stay
put), say from $a_{i}$ to $a^{\prime}_{i}$, yields
$o^{\prime}=(a_{1},\ldots,a^{\prime}_{i},\ldots,a_{n})$. We can understand
this as indicating that the pair $\langle o,o^{\prime}\rangle$ belongs to a
relation of accessibility $R_{i}$, indicating how unilateral choices of a
player $i$ can lead from an outcome to other ones. In this way, $R_{i}$
captures the result of exerting the actions of $A_{i}$.111Alternatively we
could have introduced a relation defined by each action of player $i$. That
is, $o$ is related to $o^{\prime}$ if and only if
$o=(a_{1},\ldots,a^{\prime}_{i},\ldots,a_{n})$ and
$o=(a_{1},\ldots,a_{i},\ldots,a_{n})$.

We assume that the relation $R_{i}$ is reflexive, i.e. $\langle o,o\rangle\in
R_{i}$. Again, this can be justified by considering the case of strategic
games: if $o=(\ldots,a_{i},\ldots)$ and $i$ does not change her choice
$a_{i}$, the result is again $o$. Analogously, we assume that $R_{i}$ is
symmetric. In the context of strategic games, this is justified by the fact
that from $o=(a_{1},\ldots,a_{i},\ldots,a_{n})$, a unilateral change from
$a_{i}$ to $a^{\prime}_{i}$ yields
$o^{\prime}=(a_{1},\ldots,a^{\prime}_{i},\ldots,a_{n})$ just as $o^{\prime}$ a
unilateral change from $a^{\prime}_{i}$ to $a_{i}$ yields $o$. That is, if
$\langle o,o^{\prime}\rangle\in R_{i}$ then $\langle o^{\prime},o\rangle\in
R_{i}$. We can illustrate the characterization of accessibility relations in a
strategic game using the following example.

######  Example 2.3.

Let us consider the well-known Prisoner’s Dilemma (PD) as a strategic game
given by the matrix:

| C | D
---|---|---
C | (-1,-1) | (-3,0)
D | (0,-3) | (-2,-2)

In this game ${PD}$, $I=\\{1,2\\}$, where 1 chooses rows and 2 columns. Here
$O_{PD}=\\{(C,C),(C,D),$ $(D,C),(D,D)\\}$, where $C$ stands for ‘Cooperate’
and $D$ stands for ‘Defect’ . Figure 1 presents the corresponding multi-graph
representation of this game. We can see, for instance, that player 1 can
change unilaterally from $D$ to $C$, so $(D,C)$ is accessible from $(C,C)$ and
vice-versa, and the same for $(D,D)$ and $(C,D)$. The preferences are such
that for instance $(C,C)\preceq_{1}(C,D)$ since $\pi_{1}(C,C)=-1$ and
$\pi_{1}(C,D)=0$.

DCDDCDCC Figure 1: Multi-graph representing the Prisoner’s Dilemma in Example
2.3. Blue and red lines correspond to players 1 and 2, respectively. Full
(undirected) lines correspond to accessibility relations while dashed ones
(directed) represent preferences.

Notice that in this standard interpretation of the game, each $R_{i}$ is
transitive. Lifting this requirement allows us to model other situations:

######  Example 2.4.

Consider the following strategic game

| L | R
---|---|---
T | (0,0) | (-1,2)
D | (2,-1) | (0,0)

where again player 1 chooses rows and 2 columns. In this game, the outcomes
$(T,L)$ and $(D,R)$ both lead to the same payoff of $0$ for both players. We
could represent this as a single outcome $o$. Let us call $p$ the outcome
corresponding to $(D,L)$ and $q$ to that of $(T,R)$. Figure 2 represents this
game.

pqo Figure 2: Multi-graph representing the game $G_{1}$ with set of outcomes
$O_{1}=\\{o,p,q\\}$ from Example 2.4, in which the accessibility relation is
not transitive. Red and blue lines correspond to players 1 and 2,
respectively. Full lines correspond to accessibility relations and dashed ones
to preferences.

As said, the representation of games as multigraphs is intended to facilitate
the specification of a category of games. This is based on the properties of
the two types of edges or relations among outcomes.

For each player $i$, the pair $\langle O,R_{i}\rangle$ can be regarded as an
object in the category $\bf EndoRel$, which is the category of sets endowed
with a binary relation on them (an endorelation), with morphisms the set
functions that preserve the relation. That is, $f:\langle A,R\rangle\to\langle
B,S\rangle$ is a morphism in $\bf EndoRel$ if for every $a,a^{\prime}\in A$,
if $\langle a,a^{\prime}\rangle\in R$ then $\langle
f(a),f(a^{\prime})\rangle\in S$. We have chosen for our representation to be a
bit more specific, asking that the binary relations are reflexive and
symmetric. This can also be interpreted as a category of undirected graphs.

On the other hand, the pairs $\langle O,\preceq_{i}\rangle$ can be seen as
objects in $\bf PreOrd$, the category of preordered sets with monotone
functions as morphisms.

In the next section we define different categories in which the objects are
multi-graph versions of strategic games and the morphisms preserve the
accessibility and the preference relations, acting as morphisms in EndoRel and
PreOrd, respectively.

##  3 Categories of Multi-Graph Representation of Games

###  3.1 Games with a fixed set of players

As a first approach to the categorification of the class of multi-graph
representations of strategic games presented in Definition 2.2, we consider
the subclass of them in which the set of players is the same set $I$ and
define the category $\mathbf{Gam}_{I}$:

######  Definition 3.1.

Each object in the category GamI is $G=\langle O,\\{R_{i}\\}_{i\in
I},\\{\preceq_{i}\\}_{i\in I}\rangle$ and if $G^{\prime}=\langle
O^{\prime},\\{R^{\prime}_{i}\\}_{i\in I},\\{\preceq^{\prime}_{i}\\}_{i\in
I}\rangle$ is also an object, a morphism $f:G\to G^{\prime}$ is a function
$f:O\to O^{\prime}$ such that for all $i\in I$, $o^{\prime},p^{\prime}\in
O^{\prime}$, $f$ preserves $R_{i}$ and $\preceq_{i}$, that is:

$oR_{i}p\text{ implies }f(o)R_{i}^{\prime}f(p),$

and

$o\preceq_{i}p\text{ implies }f(o)\preceq^{\prime}_{i}f(p).$

In other words, $f$ is a morphism in GamI if and only if for each $i\in I$,
$f:\langle O,R_{i}\rangle\to\langle O^{\prime},R^{\prime}_{i}\rangle$ and
$f:\langle O,\preceq_{i}\rangle\to\langle
O^{\prime},\preceq^{\prime}_{i}\rangle$ are EndoRel and PreOrd morphisms,
respectively.

######  Example 3.2.

The games ${PD}$ from Example 2.3 and $G_{1}$ of Example 2.4 are objects in
the category $\mathbf{Gam}_{\\{1,2\\}}$. For each outcome $y$ in $O_{1}$, the
set of outcomes of $G_{1}$, there is a constant morphism $\bm{y}$ with
$\bm{y}(x)=y$ for every $x\in O_{PD}$. It is easy to check that since all the
relations are reflexive, $\bm{y}$ preserves $R_{1},R_{2},\preceq_{1}$ and
$\preceq_{2}$.

A non-constant morphism is given by $g(C,C)=o=g(D,D)$, $g(D,C)=p$ and
$g(C,D)=q$. Again, we can easily check that $g$ preserves
$R_{1},R_{2},\preceq_{1}$, and $\preceq_{2}$.

It is clear that the composition of morphisms is a morphism, and that the
identity functions over the sets of outcomes are morphisms. Also, the
composition is associative, since it is just the composition of set functions
preserving relations. Thus we have a category GamI of games with a fixed set
of players $I$.

One of the advantages of the categorical approach is that we can determine (up
to isomorphism) the objects with desirable universal properties in GamI. These
objects can be obtained as in the categories $\bf EndoRel$ and $\bf PreOrd$.
For those categories, the proofs are worked out in [Vig23], and can be easily
adapted to the case we deal with here of symmetric and reflexive relations.

As a first example we have:

  * •

Product: given games $G=\langle O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in
I}\rangle$ and $G^{\prime}=\langle O^{\prime},\\{R^{\prime}_{i}\\}_{i\in
I},\\{\preceq^{\prime}_{i}\\}_{i\in I}\rangle$, a product can be constructed
as

$G\times_{I}G^{\prime}=\langle O\times
O^{\prime},\\{R^{\times_{I}}_{{i}}\\}_{i\in
I},\\{\preceq^{\times_{I}}_{i}\\}_{i\in I}\rangle$

where

$\langle\langle o,o^{\prime}\rangle,\langle p,p^{\prime}\rangle\rangle\in
R^{\times_{I}}_{i}\text{ iff }\langle o,p\rangle\in R_{i}\text{ and }\langle
o^{\prime},p^{\prime}\rangle\in R^{\prime}_{i}$

and

$\langle o,o^{\prime}\rangle\preceq^{\times_{I}}_{i}\langle
p,p^{\prime}\rangle\text{ iff }o\preceq_{i}p\text{ and
}o^{\prime}\preceq^{\prime}_{i}p^{\prime}.$

$R^{\times_{I}}_{i}$ is reflexive and symmetric, since both $R_{i}$ and
$R^{\prime}_{i}$ are reflexive and symmetric relations. By the same token,
$\preceq_{i}^{\times_{I}}$ is a reflexive and transitive relation.

The natural projection functions $\pi_{1}:O\times O^{\prime}\to G$ and
$\pi_{2}:O\times O^{\prime}\to O^{\prime}$ provide the projection morphisms.
For instance, if $\langle\langle o,o^{\prime}\rangle,\langle
p,p^{\prime}\rangle\rangle\in R^{\times_{I}}_{i}$ then $\langle\pi_{1}\langle
o,o^{\prime}\rangle,\pi_{1}\langle p,p^{\prime}\rangle\rangle\in R_{i}$, that
is, $\langle o,p\rangle\in R_{i}$.

The product $G\times_{I}G^{\prime}$ can be understood as a game in which the
players in $I$ are playing simultaneously the games $G$ and $G^{\prime}$.

A fundamental colimit can be constructed in GamI:

  * •

Coproduct: if we denote with $X+Y$ the disjoint union of the sets $X$ and $Y$,
and identify the elements in $X$ and $Y$ with their inclusion in $X+Y$, given
$G=\langle O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in I}\rangle$ and
$G^{\prime}=\langle O^{\prime},\\{R^{\prime}_{j}\\}_{j\in
J},\\{\preceq^{\prime}_{j}\\}_{j\in J}\rangle$, a coproduct can be constructed
as

$G+_{I}G^{\prime}=\langle O+O^{\prime},\\{R_{i}+R^{\prime}_{i}\\}_{i\in
I},\\{\preceq_{i}+\preceq^{\prime}_{i}\\}_{i\in I}\rangle,$

where $R_{i}+R^{\prime}_{i}$ is a reflexive and symmetric relation since
$R_{i}$ and $R^{\prime}_{i}$ are reflexive and symmetric relations for every
$i\in I$. Similarly, $\preceq_{i}+\preceq^{\prime}_{i}$ is a reflexive and
transitive relation, since $\preceq_{i}$ and $\preceq^{\prime}_{i}$ are
reflexive and transitive relations. The definitions of these relations ensure
that the set inclusions $i_{O}:O\to O+O^{\prime}$ and
$i_{O^{\prime}}:O^{\prime}\to O+O^{\prime}$ correspond to the inclusion
morphisms $i_{G}:G\to G+_{I}G^{\prime}$ and $i_{G^{\prime}}:G^{\prime}\to
G+_{I}G^{\prime}$ respectively.

An interpretation of the game $G+_{I}G^{\prime}$ is that the agents in the set
$I$ are presented with all the possible outcomes of both $G$ and $G^{\prime}$.

Besides products, two other limit objects can be defined in GamI, namely
terminal objects and equalizers:

  * •

Terminal object: let $\mathbb{T}_{I}=\langle
O_{\mathbb{T}},\\{R^{\mathbb{T}_{I}}_{i}\\}_{i\in
I},\\{\preceq^{\mathbb{T}_{I}}_{i}\\}_{i\in I}\rangle$ be the game in which
$O_{\mathbb{T}}$ is a singleton, while all the relations
$R^{\mathbb{T}_{I}}_{i}$ and $\preceq^{\mathbb{T}_{I}}_{i}$ are the identity
on $O_{\mathbb{T}}$. Given any other $I$-game $G=\langle O,\\{R_{i}\\}_{i\in
I},\\{\preceq_{i}\\}_{i\in I}\rangle$ there is a unique function $!_{O}:O\to
O_{\mathbb{T}}$, and it determines the unique game morphism from $G$ to
$\mathbb{T}_{I}$.

In words: there exists a game $\mathbb{T}_{I}$ in GamI such that for each game
$G$ there exists a unique morphism from $G$ to $\mathbb{T}_{I}$. This is a
constant morphism as those from Example 3.2.

With respect to the next construction, given two morphisms from $G$ to
$G^{\prime}$, their equalizer is a subgame in which the outcomes are a subset
of those of $G$ on which the two morphisms coincide.

  * •

Equalizer: let $f$ and $g$ be two morphisms from $G$ to $G^{\prime}$. Then we
can define a game $E=\langle O_{E},\\{R^{E_{I}}_{i}\\}_{i\in
I},\\{\preceq^{E_{I}}_{i}\\}_{i\in I}\rangle$, where $O_{E}=\\{o\in
O:f(o)=g(o)\\}$, $R^{E_{I}}_{i}=R_{i}|_{O_{E}}$, and
$\preceq^{E_{I}}_{i}=\preceq_{i}|_{O_{E}}$. Since $R^{E_{I}}_{i}$ is a
restriction of $R_{i}$, it is also reflexive and symmetric, while
$\preceq^{E_{I}}_{i}$, being a restriction of $\preceq_{i}$ it is also a
preorder for every $i\in I$. The equalizing morphism $e:E\to G$ is given by
the inclusion map $e:O_{E}\to O$.

Analogously, the corresponding colimits, i.e. initial objects and
coequalizers, also exist in GamI:

  * •

Initial object: consider the empty game $\bm{\emptyset}_{I}$, where the set of
outcomes is the empty set, and for each $i\in I$, all the relations $R_{i}$
and $\preceq_{i}$ are the empty set as well. There exists a unique morphism
from $\bm{\emptyset}_{I}$ to any game $G$.

  * •

Coequalizer: in the category of sets the coequalizer of two functions
$f,g:X\to Y$ can be constructed as a quotient by a relation $\sim$, the
smallest equivalence relation on the set $Y$ such that the pairs $\langle
f(x),g(x)\rangle$ are in the relation for every $x\in X$. Recall that, if we
denote by $[y]$ the elements of $Y/_{\sim}$, for any relation $R$, and
equivalence relation $\sim$ over $Y$, $R/_{\sim}$ is the relation
$\\{\langle[y],[y^{\prime}]\rangle:\langle y,y^{\prime}\rangle\in R\\}$.

Accordingly, if $f$ and $g$ are two morphisms from $G$ to $G^{\prime}$ let
${\sim}$ be the equivalence relation on $O^{\prime}$ generated by the pairs
$\langle f(o),g(o)\rangle$ for all the $o\in O$. Thus we can define a game

$G^{\prime}/_{\sim}=\langle
O^{\prime}/_{\sim},\\{R^{\prime}_{j}/_{\sim}\\}_{j\in
J},\\{(\preceq^{\prime}_{j}/_{\sim})^{t}\\}_{j\in J}\rangle$

where by $(\preceq^{\prime}_{j}/_{\sim})^{t}$ we denote the transitive closure
of the relation $\preceq^{\prime}_{j}/_{\sim}$.

It can be proved that $[\cdot]:G^{\prime}\rightarrow G^{\prime}/_{\sim}$ is a
morphism in GamI and that $G^{\prime}/_{\sim}$ has the universal mapping
property: $[\cdot]\circ f=[\cdot]\circ g$ and if there is a morphism
$m:G^{\prime}\to G^{\prime\prime}$ such that $m\circ f=m\circ g$, then there
is a unique morphism $u:G^{\prime}/_{\sim}\to G^{\prime\prime}$ such that
$u\circ[\cdot]=m$.

Recalling that a category is complete if it has small products and equalizers
and it is cocomplete if it has all the small coproducts and coequalizers we
have shown that:

######  Theorem 3.3.

GamI is a complete and cocomplete category.

Another construction of interest is that of exponential object. The game
$G^{\prime G}$ has as outcomes the different ways that the outcomes in $G$ can
be mapped to the outcomes in $G^{\prime}$ while preserving the accessibility
and preference relations. We have:

######  Proposition 3.4.

Given games $G,G^{\prime}$ in GamI, there exists an exponential object
$G^{\prime G}$.

###### Proof.

Given two games $G=\langle O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in
I}\rangle$ and $G^{\prime}=\langle O^{\prime},\\{R^{\prime}_{i}\\}_{i\in
I},\\{\preceq^{\prime}_{i}\\}_{i\in I}\rangle$, we define a game:

$G^{\prime G}=\langle\mathcal{O},\\{R^{\prime\prime}_{i}\\}_{i\in
I},\\{\preceq^{\prime\prime}_{i}\\}_{i\in I}\rangle$

where $\mathcal{O}=\\{f\in O^{\prime O}:f\ \mbox{is a morphism from }G\text{
to }G^{\prime}\\}$, and the relations $R^{\prime\prime}_{i}$ and
$\preceq^{\prime\prime}_{i}$ are defined by: for all $f,g\in\mathcal{O}$,

$fR^{\prime\prime}_{i}g\text{ if and only if for all }o,p\in O,oR_{i}p\text{
implies }f(o)R_{i}^{\prime}g(p),$

and

$(*)\ \ \ \ \ f\preceq^{\prime\prime}_{i}g\text{ if and only if for all }o\in
O,f(o)\preceq^{\prime}_{i}g(o).$

The condition in the definition of $\preceq^{\prime\prime}_{i}$ may seem
simpler than the one for $R^{\prime\prime}_{i}$, but given that $\preceq_{i}$
and $\preceq^{\prime}_{i}$ are preorders, one can derive a similar condition:
if $o\preceq_{i}p$, then by ($*$), $f(o)\preceq^{\prime}_{i}g(o)$, and since
$g$ is a morphism, $g(o)\preceq^{\prime}_{i}g(p)$ so
$f(o)\preceq^{\prime}_{i}g(p)$ by the transitivity of $\preceq^{\prime}_{i}$.

With these definitions, we can prove that $R^{\prime\prime}_{i}$ is reflexive
and symmetric. Indeed, since for each morphism $f:G\to G^{\prime}$, every
$i\in I$ and every $o,p\in O$, $oR_{i}p$ implies $f(o)R^{\prime}_{i}f(p)$, we
have that $fR^{\prime\prime}_{i}f$. For symmetry, assume that
$fR^{\prime\prime}_{i}g$. Then, if $oR_{i}p$, by the symmetry of
$R_{i},pR_{i}o$ so $f(p)R^{\prime}_{i}g(o)$ and by the symmetry of
$R^{\prime}_{i}$, $g(o)R^{\prime}_{i}f(p)$, which proves
$gR^{\prime\prime}_{i}f$.

Similarly, it can be proved that $\preceq^{\prime\prime}_{i}$ is a preorder.
Reflexivity is immediate, since for all $o\in O$,
$f(o)\preceq^{\prime}_{i}f(o)$ and thus $f\preceq^{\prime\prime}_{i}f$. For
transitivity assume that $f\preceq^{\prime\prime}_{i}g$ and
$g\preceq^{\prime\prime}_{i}h$. Then, for all $o\in O$ we have that
$f(o)\preceq^{\prime}_{i}g(o)$ and $g(o)\preceq^{\prime}_{i}h(o)$. By
transitivity of $\preceq^{\prime}_{i}$ we have $f(o)\preceq^{\prime}_{i}h(o)$
for all $o\in O$. That is, $f\preceq^{\prime\prime}_{i}h$.

For any other game $G^{\prime\prime}=\langle
O^{\prime\prime},\\{S_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in I}\rangle$,
given a morphism $h:G^{{}^{\prime\prime}}\times G\rightarrow G^{\prime}$, we
can define as in the category of sets $\psi:G^{\prime\prime}\rightarrow
G^{\prime G}$ by $\psi(o^{\prime\prime})(o)=h(o^{\prime\prime},o)$. First, we
need to check that for every $o^{\prime\prime}\in O^{\prime\prime}$,
$\psi(o^{\prime\prime})$ is a morphism from $G$ to $G^{\prime}$, and then that
$\psi$ itself is a morphism from $G^{\prime\prime}$ to $G^{\prime G}$.

To see the first part, fix $o^{\prime\prime}\in O^{\prime\prime}$, and suppose
that $o,p\in O$ are such that $oR_{i}p$. Then, as $\langle
o^{\prime\prime},o\rangle S_{i}{\times_{I}}R_{i}\langle
o^{\prime\prime},p\rangle$, it follows that
$h({o^{\prime\prime},o})R^{\prime}_{i}h({o^{\prime\prime},p})$, that is,
$\psi(o^{\prime\prime})(o)R^{\prime}_{i}\psi(o^{\prime\prime})(p)$.

To show that $\psi$ is a morphism, take now
$o^{\prime\prime},p^{\prime\prime}\in O^{\prime\prime}$ such that
$o^{\prime\prime}S_{i}p^{\prime\prime}$. For any $o,p\in O$ such that
$oR_{i}p$, we have that $\langle o^{\prime\prime},o\rangle
S_{i}{\times_{I}}R_{i}\langle p^{\prime\prime},p\rangle$, and thus
$h({o^{\prime\prime},o})R^{\prime}_{i}h({p^{\prime\prime},p})$ so
$\psi(o^{\prime\prime})(o)R^{\prime}_{i}\psi(p^{\prime\prime})(p)$. This
implies that
$\psi(o^{\prime\prime})R^{\prime\prime}_{i}\psi(p^{\prime\prime})$.

Thus $\psi$ is a morphism that makes the following diagram commute, and its
uniqueness follows from its definition on the corresponding sets.

$\textstyle{G^{\prime\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi}$$\textstyle{G^{\prime\prime}\times
G\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi\times
id_{G}}$$\scriptstyle{{h}}$$\textstyle{G^{\prime G}}$$\textstyle{G^{\prime
G}\times
G\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{eval}$$\textstyle{G^{\prime}}$

∎

Therefore, as a consequence of Theorem 3.3 and Proposition 3.4:

######  Theorem 3.5.

GamI is a cartesian complete category.

######  Proposition 3.6.

If $G\neq\bm{\emptyset}$, then there is an injection $\psi:G^{\prime}\to
G^{\prime G}$.

###### Proof.

Define for each $o^{\prime}\in O^{\prime}$,
$\psi(o^{\prime})=\bm{o^{\prime}}$, where $\bm{o^{\prime}}$ is the constant
function defined by $\bm{o^{\prime}}(o)=o^{\prime}$ for every $o\in O$.
Clearly $\psi$ is injective. Now, if we have that for some player $i\in I$,
$o^{\prime}R^{\prime}_{i}p^{\prime}$, then
$\psi({o^{\prime}})R^{\prime\prime}_{i}\psi({p^{\prime}})$: indeed, if $o,p\in
O$ and $oR_{i}p$, then $\bm{o^{\prime}}(o)R^{\prime}_{i}\bm{p^{\prime}}(p)$. A
simpler argument works for the preferences. ∎

A particular case of GamI is the category of “games” with a single player
$\mathbf{1}$, denoted Gam1. It is immediate to see that Theorem 3.3 and
Proposition 3.4 apply to Gam1, where $I=\\{\mathbf{1}\\}$. In this category
the objects represent decision problems. The accessibility relation
$R_{\mathbf{1}}$ can be understood as the feasibility of changing from a
possible outcome to another, while $\preceq_{\mathbf{1}}$ represents the
preferences over the outcomes.

We also have Gam∅, in which the games have no players and therefore no
relations are given over the sets of outcomes. Thus, each game in this
category can be identified with the set of its outcomes and the morphisms
among games in this category with the corresponding set functions.

######  Proposition 3.7.

Given a morphism $f:G\to G^{\prime}$ in GamI,

  1. 1.

$f$ is monic iff $f:O\to O^{\prime}$ is injective.

  2. 2.

$f$ is epic iff $f:O\to O^{\prime}$ is surjective.

###### Proof.

  1. 1.

If $f:O\to O^{\prime}$ is not injective, there exists outcomes $o\neq p\in O$
such that $f(o)=f(p)$. Consider the game $\bm{1}$ with a single outcome $*$ in
which all the relations $R_{i}$ and $\preceq_{i}$ are the identity on the
singleton. Let $x$ and $y$ be the functions that send $*$ to $o$ and $p$
respectively. It is easy to check that $x$ and $y$ are morphisms and $f\circ
x=f\circ y$ but $x\neq y$, so $f$ cannot be monic.

In the other direction, assume that $f$ is injective, and $x$ and $y$ are
morphisms from a game $G^{\prime\prime}$ to $G$ such that $f\circ x=f\circ y$.
Then for every outcome $o^{\prime\prime}$ of $O^{\prime\prime}$ we have that
$f(x(o^{\prime\prime}))=f(y(o^{\prime\prime}))$, and since $f$ is injective,
$x(o^{\prime\prime})=y(o^{\prime\prime})$, so $x=y$.

  2. 2.

If $f$ is not surjective, then there exists an outcome $o^{\prime}$ that is
not in the image of $f$. Consider a game $G^{\prime\prime}$ with two different
outcomes, $O^{\prime\prime}=\\{a,b\\}$ and the relations
$R^{\prime\prime}_{i}$ and $\preceq^{\prime\prime}_{i}$ on them are all equal
to $O^{\prime\prime}\times O^{\prime\prime}$. Now consider the constant
morphism $\bm{a}$ and a morphism $g$ that sends all the outcomes in
$O^{\prime}$ to $a$, except for $o^{\prime}$ that goes to $b$. Since all
elements are related in $G^{\prime\prime}$, $g$ is a morphism and different
from $\bm{a}$, with $\bm{a}\circ f=g\circ f$.

If we assume that $f$ is surjective and $g,h:G^{\prime}\to G^{\prime\prime}$
are such that $g\circ f=h\circ f$, then for every $o^{\prime}\in O^{\prime}$
we have that $o^{\prime}=f(o)$ for some $o\in O$. Therefore
$g(o^{\prime})=g(f(o))=h(f(o))=h(o^{\prime})$ which proves that $g=h$ and
therefore $f$ is epic. ∎

###  3.2 Games with different sets of players

We now generalize GamI by considering all the components presented in
Definition 2.2. Since the sets of players $I$ and $J$ may differ between a
given pair of games $G$ and $G^{\prime}$, a morphism $f:G\rightarrow
G^{\prime}$ should indicate how $I$ maps onto $J$ and how it preserves the
relations defining the games. More precisely:

######  Definition 3.8.

Each object in the category Gam is $G=\langle I,O,\\{R_{i}\\}_{i\in
I},\\{\preceq_{i}\\}_{i\in I}\rangle$ and if $G^{\prime}=\langle
J,O^{\prime},\\{R^{\prime}_{i}\\}_{i\in I},\\{\preceq^{\prime}_{i}\\}_{i\in
I}\rangle$ is also an object, a morphism $f:G\to G^{\prime}$ consists of a
pair of functions $f_{p}:I\rightarrow J$ and $f_{O}:O\to O^{\prime}$, such
that given $o,p\in O$, for each $i\in I$:

  * •

if $\langle o,p\rangle\in R_{i}$ then $\langle f_{O}(o),f_{O}(p)\rangle\in
R^{\prime}_{f_{p}(i)}$

  * •

if $o\preceq_{i}p$, then $f_{O}(o)\preceq_{f_{p}(i)}^{\prime}f_{O}(p)$.

That is, for each $i\in I$, $f_{O}:\langle O,R_{i}\rangle\to\langle
O^{\prime},R^{\prime}_{f_{p}(i)}\rangle$ and $f_{O}:\langle
O,\preceq_{i}\rangle\to\langle O^{\prime},\preceq^{\prime}_{f_{p}(i)}\rangle$
are EndoRel and PreOrd morphisms, respectively. We write $f=(f_{p},f_{O})$.

These objects and morphisms define a category $\mathbf{Gam}$, since similarly
to the case of GamI the composition of morphisms yields a morphism and each
$G$ has an associated identity morphism (consisting of the identities on the
set of players and on the set of outcomes). Composition is also associative.

The following definitions highlight two particular kinds of games:

######  Definition 3.9.

A _set of players_ is a game $G_{p}(I)=\langle
I,\emptyset,\\{\emptyset\\}_{i\in I},\\{\emptyset\\}_{i\in I}\rangle$, with an
empty set of outcomes and empty accessibility and preference relations. If the
set $I=\\{i\\}$ is a singleton, we refer to this game as _player_ $G_{p}(i)$.

######  Definition 3.10.

A _set of outcomes_ is a game
$G_{O}(O)=\langle\emptyset,O,\emptyset,\emptyset\rangle$, with an empty set of
players and no accessibility nor preference relations.

We abuse somewhat the terminology by naming these games players and outcomes,
but it is useful to have them as objects in the category Gam. Furthermore,
$G_{p}$ and $G_{O}$ are easily checked to be functors from the category of
sets to Gam.

######  Proposition 3.11.

For each game $G=\langle I,O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in
I}\rangle$, $S\subseteq I$, and $T\subseteq O$ there is a unique morphism $f$
from $G_{p}(S)$ to $G$ such that $f_{p}=i_{S}$, the inclusion map
$S\hookrightarrow I$ , and also there is a unique $g$ from $G_{O}(T)$ to $G$
such that $g_{O}=i_{T}:T\hookrightarrow O$.

###### Proof.

The morphisms are $f=(i_{S},\emptyset)$ and $g=(\emptyset,i_{T})$,
respectively. ∎

######  Theorem 3.12.

$\mathbf{Gam}$ is a complete and cocomplete category.

###### Proof.

To prove this claim we have to obtain the same constructions as in the proof
of Theorem 3.3, but this time taking into account the interaction between the
components $f_{p}$ and $f_{O}$ of morphisms $f$:

  * •

Products: given games $G=\langle I,O,\\{R_{i}\\}_{i\in
I},\\{\preceq_{i}\\}_{i\in I}\rangle$ and $G^{\prime}=\langle
J,O^{\prime},\\{R^{\prime}_{j}\\}_{j\in J},\\{\preceq^{\prime}_{j}\\}_{j\in
J}\rangle$, a product can be constructed as

$G\times G^{\prime}=\langle I\times J,O\times O^{\prime},\\{R_{\langle
i,j\rangle}\\}_{\langle i,j\rangle\in I\times J},\\{\preceq_{\langle
i,j\rangle}\\}_{\langle i,j\rangle\in I\times J}\rangle$

where

$\langle\langle o,o^{\prime}\rangle,\langle p,p^{\prime}\rangle\rangle\in
R_{\langle i,j\rangle}\text{ iff }\langle o,p\rangle\in R_{i}\text{ and
}\langle o^{\prime},p^{\prime}\rangle\in R^{\prime}_{j}$

and

$\langle o,o^{\prime}\rangle\preceq_{\langle i,j\rangle}\langle
p,p^{\prime}\rangle\text{ iff }o\preceq_{i}p\text{ and
}o^{\prime}\preceq_{j}p^{\prime}.$

$R_{\langle i,j\rangle}$ is reflexive and symmetric, since $R_{i}$ and
$R^{\prime}_{j}$ are reflexive and symmetric relations. By the same token,
$\preceq_{\langle i,j\rangle}$ is a reflexive and transitive relation.

The natural projections $\pi_{1}:G\times G^{\prime}\to G$ and $\pi_{2}:G\times
G^{\prime}\to G^{\prime}$ are easily checked to be morphisms.

  * •

Terminal object: let $\mathbb{T}=\langle
I_{\mathbb{T}},O_{\mathbb{T}},\\{R^{\mathbb{T}}\\},\\{\preceq^{\mathbb{T}}\\}\rangle$
be the game in which $I_{\mathbb{T}}$ and $O_{\mathbb{T}}$ are singletons,
while $R^{\mathbb{T}}$ and $\preceq^{\mathbb{T}}$, are the identity on
$O^{\mathbb{T}}$. Given any other game $G=\langle I,O,\\{R_{i}\\}_{i\in
I},\\{\preceq_{i}\\}_{i\in I}\rangle$ there are two unique functions,
$!_{Gp}:I\rightarrow I_{\mathbb{T}}$ and $!_{GO}:O\to O_{\mathbb{T}}$, and
they determine the unique game morphism from $G$ to $\mathbb{T}$.

  * •

Equalizers: let $f$ and $g$ be two morphisms from $G$ to $G^{\prime}$. Then we
can define $E=\langle I_{E},O_{E},\\{R_{i}^{E}\\}_{i\in
I_{E}},\\{\preceq_{i}^{E}\\}_{i\in I_{E}}\rangle$, where $I_{E}=\\{i\in
I:f_{p}(i)=g_{p}(i)\\}$, $O_{E}=\\{o\in O:f_{O}(o)=g_{O}(o)\\}$, and for every
$i\in I_{E}$, $R_{i}^{E}=R_{i}|_{O_{E}}$, and
$\preceq_{i}^{E}=\preceq_{i}|_{O_{E}}$. Since $R_{i}^{E}$ is a restriction of
$R_{i}$, it is also reflexive and symmetric, while $\preceq_{i}^{E}$, being a
restriction of $\preceq_{i}$ it is also a reflexive and transitive relation
for each $i\in I$. The equalizing morphism $e:E\to G$ is given by the
inclusion maps $e_{p}:I_{E}\to I$ and $e_{O}:O_{E}\to O$.

  * •

Coproducts: Let $\Delta_{X}$ be the set of pairs $\langle x,x\rangle$ for
$x\in X$. Given games $G=\langle I,O,\\{R_{i}\\}_{i\in
I},\\{\preceq_{i}\\}_{i\in I}\rangle$ and $G^{\prime}=\langle
J,O^{\prime},\\{R^{\prime}_{j}\\}_{j\in J},\\{\preceq^{\prime}_{j}\\}_{j\in
J}\rangle$, a coproduct can be constructed as

$G+G^{\prime}=\langle I+J,O+O^{\prime},\\{R^{+}_{k}\\}_{k\in
I+J},\\{\preceq^{+}_{k}\\}_{k\in I+J}\rangle$

where

$R^{+}_{i}=R_{i}\cup\Delta_{O^{\prime}}\text{ if }i\in I,\text{ and
}R^{+}_{j}=R^{\prime}_{j}\cup\Delta_{O},\text{ if }j\in J$

and similarly,

$\preceq^{+}_{i}=\preceq_{i}\cup\Delta_{O^{\prime}}\text{ if }i\in I,\text{
and }\preceq^{+}_{j}=\preceq^{\prime}_{j}\cup\Delta_{O},\text{ if }j\in J.$

Here we need to add the identity relations to make sure both $R_{k}^{+}$ and
$\preceq_{k}^{+}$ are reflexive. Thus, $R_{k}^{+}$ is a reflexive and
symmetric relation since $R_{i}$ and $R_{j}$ for $i\in I$ and $j\in J$, as
well as $\Delta_{O}$ and $\Delta_{O^{\prime}}$ are reflexive and symmetric
relations. In turn, and $\preceq_{k}^{+}$ is a reflexive and transitive
relation, since $\preceq_{i}$, $\preceq_{j}$, $\Delta_{O}$ and
$\Delta_{O^{\prime}}$ are reflexive and transitive relations.

Let $i_{O}$ and $i_{O^{\prime}}$ be the injections from $O$ and $O^{\prime}$
into $O+O^{\prime}$ respectively. To see that adding the identity relations on
the outcomes preserves the universal property of the coproduct, consider
morphisms $f:G\to G^{\prime\prime}$ and $g:G^{\prime}\to G^{\prime\prime}$. We
can build the set functions $[f,g]_{p}$ and $[f,g]_{O}$ as usual. If $\langle
x,y\rangle\in R_{k}^{+}$, with $k\in I$, we consider two cases:

    * –

$x,y\in O$, then $[f,g]_{O}(i_{O}(x))=f_{O}(x)$ and
$[f,g]_{O}(i_{O}(y))=f_{O}(y)$ so, since $f$ is a morphism, $\langle
f_{O}(x),f_{O}(y)\rangle\in R^{\prime\prime}_{f_{p}(k)}$.

    * –

$x,y\in O^{\prime}$ then we must have $x=y$ so
$[f,g]_{O}(i_{O^{\prime}}(x))=g_{O}(x)=g_{O}(y)=[f,g]_{O}(i_{O^{\prime}}(y))$.
In this case, we know that since $R^{\prime\prime}_{f_{p}(k)}$ is reflexive,
$\langle g_{O}(x),g_{O}(y)\rangle\in R^{\prime\prime}_{f_{p}(k)}$.

$\textstyle{O\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i_{O}}$$\scriptstyle{f_{O}}$$\textstyle{O+O^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[f,g]_{O}}$$\textstyle{O^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i_{O^{\prime}}}$$\scriptstyle{g_{O}}$$\textstyle{O^{\prime\prime}}$

Thus $i_{G}=(i_{I},i_{O}):G\to G+G^{\prime}$ and
$i_{G^{\prime}}=(i_{J},i_{O^{\prime}}):G^{\prime}\to G+G"$ are the inclusion
morphisms, where $i_{I}$ and $i_{J}$ are the natural inclusion functions into
$I+J$.

  * •

Initial object: consider the empty game $\bm{\emptyset}$, where the set of
players, the set of outcomes, and the corresponding families of relations are
all the empty set. There exists a unique morphism from $\bm{\emptyset}$ to any
game $G$. Notice that $\bm{\emptyset}=G_{p}(\emptyset)=G_{O}(\emptyset)$.

  * •

Coequalizers: if $f$ and $g$ are two morphisms from $G$ to $G^{\prime}$ we
must now consider an equivalence relation on the set $J$ of players of the
game $G^{\prime}$, generated by the pairs $\langle f_{p}(i),g_{p}(i)\rangle$
for all $i\in I$. We call this equivalence relation $\sim_{p}$. At the same
time, we have the equivalence relation on $O^{\prime}$ that we defined for
coequalizers in GamI, which we now denote by $\sim_{O}$. The game

$G^{\prime}/_{\sim}=\langle
J/_{\sim_{p}},O^{\prime}/_{\sim_{O}},\\{R^{\prime}_{[j]}\\}_{[j]\in
J/_{\sim_{p}}},\\{\preceq^{\prime}_{[j]}\\}_{[j]\in J/_{\sim_{p}}}\rangle$

where $[{o}^{\prime}]R^{\prime}_{[j]}[p^{\prime}]$ if and only if there exist
some $k\in[j]$, $q\in[o^{\prime}]$ and $r\in[p^{\prime}]$ such that
$qR^{\prime}_{k}r$. Then, $R^{\prime}_{[j]}$ is reflexive and symmetric, since
$R^{\prime}_{j}$ is reflexive and symmetric for every $j\in J$.

In turn, for each $[j]$, $\preceq_{[j]}$ is defined as the smallest reflexive
transitive relation on $O^{\prime}/_{\sim}$ that contains
$\preceq_{k}/{\sim_{O}}$ for each $k\in[j]$. The required morphism is
$h=([\cdot],[\cdot]):G^{\prime}\to G^{\prime}/_{\sim}$. It is easy to check
that $h$ preserves the relations $R^{\prime}_{j}$ and $\preceq^{\prime}_{j}$
for all $j\in J$. ∎

######  Definition 3.13.

For each set of players $I$ we define a functor $F_{I}:\text{\bf
Gam}_{I}\to\text{\bf Gam}$ by putting $F_{I}(\langle O,\\{R_{i}\\}_{i\in
I},\\{\preceq_{i}\\}_{i\in I}\rangle)=\langle I,O,\\{R_{i}\\}_{i\in
I},\\{\preceq_{i}\\}_{i\in I}\rangle$ on the objects and $F_{I}(f)=(1_{I},f)$
on the morphisms.

Notice that this functor does not preserve products or coproducts. For
example, a product of games in GamI will have $I$ as its sets of players, but
when performed in Gam, the number of players will be the square of the number
of players in $I$.

######  Proposition 3.14.

In $\mathbf{Gam}$, given games $G,G^{\prime}$ there exists an exponential
object $G^{\prime G}$.

###### Proof.

: Given two games $G=\langle I,O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in
I}\rangle$ and $G^{\prime}=\langle J,O^{\prime},\\{R^{\prime}_{j}\\}_{j\in
J},\\{\preceq^{\prime}_{j}\\}_{j\in J}\rangle$, we define a game:

$G^{\prime G}=\langle K,\mathcal{O},\\{R_{\kappa}\\}_{\kappa\in
K},\\{\preceq_{\kappa}\\}_{\kappa\in K}\rangle$

where

$K=\\{\kappa:I\rightarrow J|\mbox{ there exists }\rho:O\to O^{\prime}\text{
such that }\ (\kappa,\rho)\in{Hom}_{\mathbf{Gam}}(G,G^{\prime})\\}$

and

$\mathcal{O}=\\{\rho:O\rightarrow O^{\prime}|\mbox{ there exists }\kappa:I\to
J\text{ such that }(\kappa,\rho)\in{Hom}_{\mathbf{Gam}}(G,G^{\prime})\\}.$

For each $\kappa\in K$,

${R}_{\kappa}=\\{(\rho,\rho^{\prime}):(\kappa,\rho),(\kappa,\rho^{\prime})\in\mbox{Hom}_{\mathbf{Gam}}(G,G^{\prime})\
\mbox{and for all}\ o,p\in O\ \mbox{and for all}\ i\in I$ $(o,p)\in
R_{i}\Rightarrow\rho(o)R^{\prime}_{\kappa(i)}\rho^{\prime}(p)\\}\cup\Delta_{\mathcal{O}}.$

With this specification, $R_{\kappa}$ is trivially reflexive and we can check
that it is symmetric as well: Suppose that
$(\rho,\rho^{\prime})\in{R}_{\kappa}$. By definition, for all $o,p\in O$ and
$i\in I$, if $oR_{i}p$, then, since $R_{i}$ is symmetric, $pR_{i}o$ and thus
$\rho(p)R^{\prime}_{\kappa(i)}\rho^{\prime}(o)$. By the symmetry of
$R^{\prime}_{\kappa(i)}$, $\rho^{\prime}(o)R^{\prime}_{\kappa(i)}\rho(p)$, and
this proves that $(\rho^{\prime},\rho)\in{R}_{\kappa}$.

In the case of the preference relations, for each $\kappa\in K$,
$\rho\preceq_{\kappa}\rho^{\prime}$ if and only if for all $o\in O$ and $i\in
I$, $\rho(o)\preceq_{\kappa(i)}\rho^{\prime}(o)$.

While the reflexivity of $\preceq_{\kappa}$ is trivially satisfied,
transitivity can be proven as follows. Assume that
$\rho\preceq_{\kappa}\rho^{\prime}$ and
$\rho^{\prime}\preceq_{\kappa}\rho^{\prime\prime}$. This means that for all
$i\in I$ and all $o\in O$, $\rho(o)\preceq_{\kappa(i)}\rho^{\prime}(o)$ and
$\rho^{\prime}(o)\preceq_{\kappa(i)}\rho^{\prime\prime}(o)$. Since
$\preceq_{\kappa(i)}$ is transitive for each $i\in I$, it follows that
$\rho\preceq_{\kappa}\rho^{\prime\prime}$. Thus, $\preceq_{\kappa}$ is a
preorder.

For any other game $G^{\prime\prime}=\langle
L,O^{\prime\prime},\\{S_{l}\\}_{l\in L},\\{\preceq_{l}\\}_{l\in L}\rangle$,
given a morphism $h:G^{{}^{\prime\prime}}\times G\rightarrow G^{\prime}$, we
define maps $\Psi_{p}$ and $\Psi_{O}$ as follows: given $l\in L$, $i\in I$,
$o^{\prime\prime}\in O^{\prime\prime}$, and $o\in O$,

  * •

$\Psi_{p}(l)(i)=h_{p}(l,i)$

  * •

$\Psi_{O}(o^{\prime\prime})(o)=h_{O}(o^{\prime\prime},o)$,

We need to check that for every $l\in L$ and $o^{\prime\prime}\in
O^{\prime\prime}$, $(\Psi_{p}(l),\Psi_{O}(o^{\prime\prime}))$ is a morphism
from $G$ to $G^{\prime}$, and then that $\Psi=(\Psi_{p},\Psi_{O})$ itself is a
morphism from $G^{\prime\prime}$ to $G^{\prime G}$.

To see the first part, fix $l\in L$ and $o^{\prime\prime}\in
O^{\prime\prime}$, and suppose that $o,p\in O$ are such that $oR_{i}p$. Then,
as $\langle o^{\prime\prime},o\rangle S_{l}{\times}R_{i}\langle
o^{\prime\prime},p\rangle$, it follows that
$h({o^{\prime\prime},o})R^{\prime}_{h_{p}(l,i)}h({o^{\prime\prime},p})$, that
is,
$\Psi_{O}(o^{\prime\prime})(o)R^{\prime}_{\Psi_{p}(l)(i)}\Psi_{O}(o^{\prime\prime})(p)$.
Similarly, we can check that the preferences are preserved.

To show that $\Psi$ is a morphism, take $l\in L$ and
$o^{\prime\prime},p^{\prime\prime}\in O^{\prime\prime}$ such that
$o^{\prime\prime}S_{l}p^{\prime\prime}$. For any $o,p\in O$ satisfying
$oR_{i}p$, we have that $\langle o^{\prime\prime},o\rangle
S_{l}{\times}R_{i}\langle p^{\prime\prime},p\rangle$, and thus
$h({o^{\prime\prime},o})R^{\prime}_{h_{p}(l,i)}h({p^{\prime\prime},p})$ so
$\Psi_{O}(o^{\prime\prime})(o)R^{\prime}_{\Psi_{p}(l)(i)}\Psi_{O}(p^{\prime\prime})(p)$.
This implies that
$\Psi_{O}(o^{\prime\prime})R_{\Psi_{p}(l)}\Psi_{O}(p^{\prime\prime})$.

Thus $\Psi$ is a morphism that makes the following diagram commute, and its
uniqueness follows from its definition on the corresponding sets.

$\textstyle{G^{\prime\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Psi}$$\textstyle{G^{\prime\prime}\times
G\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Psi\times
id_{G}}$$\scriptstyle{\mathbf{h}}$$\textstyle{G^{\prime
G}}$$\textstyle{G^{\prime G}\times
G\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{eval}$$\textstyle{G^{\prime}}$

∎

Analogously to what we saw in Proposition 3.6, we have the following result:

######  Proposition 3.15.

If $G\neq\bm{\emptyset}$, then there is an embedding $\psi$ of $G^{\prime}$ in
$G^{\prime G}$.

###### Proof.

Let $\psi_{p}:J\to J^{I}$ and $\psi_{O}:O^{\prime}\to O^{\prime O}$, where for
every $i\in I$ and $j\in J$, $\psi_{p}(j)(i)=j$, and for every $o\in O$ and
$o^{\prime}\in O^{\prime}$, $\psi_{O}(o^{\prime})(o)=o^{\prime}$. We denote
with $\bm{j}$ and $\bm{o^{\prime}}$ these constant functions. Furthermore,
notice that for any $\kappa:I\to J$, the pair
$\langle\kappa,\bm{o^{\prime}}\rangle$ is a morphism from $G$ to $G^{\prime}$.
Indeed, if $oR_{i}p$, then
$\bm{o^{\prime}}(o)R^{\prime}_{\kappa(i)}\bm{o^{\prime}}(p)$ for any $o,p\in
O$ and $i\in I$. This proves that in particular $(\bm{j},\bm{o}^{\prime})$ is
a morphism, so $\bm{j}\in K$ and $\bm{o^{\prime}}\in\mathcal{O}$.

Finally, we can show that $\psi=(\psi_{p},\psi_{O})$ is a morphism. Consider
$o^{\prime},p^{\prime}\in O^{\prime}$ such that $\langle
o^{\prime},p^{\prime}\rangle\in R^{\prime}_{j}$ for some $j\in J$. We want to
show that $\langle\psi_{O}(o^{\prime}),\psi_{O}(p^{\prime})\rangle\in
R_{\psi_{p}(j)}$. By definition, this means that
$\langle\bm{o^{\prime}},\bm{p^{\prime}}\rangle\in R_{\bm{j}}$. We already know
that $(\bm{j},\bm{o^{\prime}})$ and $(\bm{j},\bm{p^{\prime}})$ are morphisms
from $G$ to $G^{\prime}$, and for all $i\in I$ and $o,p\in O$, $\langle
o,p\rangle\in R_{i}$ it should be the case that
$\langle\bm{o^{\prime}}(o),\bm{p^{\prime}}(p)\rangle\in
R^{\prime}_{\bm{j}(i)}$, but this is equivalent to the hypothesis $\langle
o^{\prime},p^{\prime}\rangle\in R^{\prime}_{j}$. ∎

The following proposition illustrates the flexibility and expressivity of this
formalism:

######  Proposition 3.16.

Each set function $f:I\to J$ induces a functor $F_{f}:\text{\bf
Gam}_{I}\to\text{\bf Gam}_{J}$ such that for every set of outcomes $O$ of a
game in $\text{\bf Gam}_{I}$, $(f,1_{O})$ is a morphism in Gam.

###### Proof.

For each $G=\langle O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in
I}\rangle\in\text{\bf Gam}_{I}$, we put $F_{f}(G)=\langle
O,\\{R^{f}_{j}\\}_{j\in J},\\{\preceq^{f}_{j}\\}_{j\in J}\rangle\in\text{\bf
Gam}_{J}$, where

$\langle o,p\rangle\in R^{f}_{j}\text{ iff there exists }i\in I\text{ such
that }f(i)=j\text{ and }\langle o,p\rangle\in R_{i}.$

For a morphism $g:G\to G^{\prime}$ in GamI, $F_{f}(g):F_{f}(G)\to
F_{f}(G^{\prime})$ is given by the same function $g:O\to O^{\prime}$. We can
see that $F_{f}(g)$ is a morphism: if $\langle o,p\rangle\in R^{f}_{j}$, then
for some $i\in I$ such that $f(i)=j$, $\langle o,p\rangle\in R_{i}$.
Therefore, $\langle g(o),g(p)\rangle\in R^{\prime}_{i}$, so $\langle
g(o),g(p)\rangle\in R^{\prime f}_{j}$. It follows from the definition that
$F_{f}$ preserves compositions and identities.

If we now consider a game $G$ in GamI, we have that $F_{f}(G)$ is in GamJ, and
we can apply the functors $F_{I}$ and $F_{J}$ (see Definition 3.13),
respectively. The pair $(f,1_{O}):F_{I}(G)\to F_{J}(F_{f}(G))$ is a morphism
in Gam: if $\langle o,p\rangle\in R_{i}$, then $\langle o,p\rangle\in
R^{f}_{f(i)}$. ∎

It is well known that if a category has coproducts and coequalizers, then it
has pushouts. The following example shows an application of this construction.

######  Example 3.17.

Consider these two games
$G=\langle\\{1,2\\},O,\\{R_{1},R_{2}\\},\\{\preceq_{1},\preceq_{2}\\}\rangle$
and
$G^{\prime}=\langle\\{2,3\\},O^{\prime},\\{R^{\prime}_{2},R^{\prime}_{3}\\},\\{\preceq^{\prime}_{2},\preceq^{\prime}_{3}\\}\rangle$.
Since player $2$ participates in both games, we want to amalgamate $G$ and
$G^{\prime}$ in a way that reflects this situation. For this, we use the
player game
$G_{p}(2)=\langle\\{2\\},\emptyset,\\{\emptyset\\},\\{\emptyset\\}\rangle$,
and the morphisms $f$ from $G_{p}(2)$ to $G$ and $f^{\prime}$ from $G_{p}(2)$
to $G^{\prime}$ given by proposition 3.11.

The pushout of $G$ and $G^{\prime}$ is obtained by building their coproduct
and then finding the quotient under the relation $\sim_{2}$ that identifies
player 2 in each game.

$\textstyle{G_{p}(2)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{f^{\prime}}$$\textstyle{G\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i_{G}}$$\textstyle{G^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i_{G^{\prime}}}$$\textstyle{G+G^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{G+G^{\prime}/_{\sim_{2}}}$

The set of players of $G+G^{\prime}$ can be written as $\\{\langle
1,0\rangle,\langle 2,0\rangle,\langle 2,1\rangle,\langle 3,1\rangle\\}$ (the
second component in each pair indicates to which game corresponds to: $0$ for
$G$ and $1$ for $G^{\prime}$). The relation $\sim_{2}$ identifies $\langle
2,0\rangle$ and $\langle 2,1\rangle$.

We can now describe the components of this pushout $G+G^{\prime}/_{\sim_{2}}$.
The set of players is composed by the equivalence classes $[\langle
1,0\rangle]$, $[\langle 2,0\rangle,\langle 2,1\rangle]$, $[\langle
3,1\rangle]$. The set of outcomes is $O+O^{\prime}$ since there is no
restriction imposed by the morphisms from $G_{p}(2)$. The accessibility
relations are: $R^{+}_{[\langle 1,0\rangle]}=R^{+}_{\langle
1,0\rangle}=R_{1}\cup\Delta_{O^{\prime}}$, $R^{+}_{[\langle
3,1\rangle]}=R^{+}_{\langle 3,1\rangle}=\Delta_{O}\cup R^{\prime}_{3}$, and
for $R^{+}_{[\langle 2,0\rangle,\langle 2,1\rangle]}$ we have that $\langle
x,y\rangle\in R^{+}_{[\langle 2,0\rangle,\langle 2,1\rangle]}$ if and only if
$\langle x,y\rangle\in R^{+}_{\langle 2,0\rangle}$ or $\langle x,y\rangle\in
R^{+}_{\langle 2,1\rangle}$. That is, if and only if $\langle x,y\rangle\in
R_{2}+R^{\prime}_{2}$.

Analogously, $\preceq^{+}_{[\langle
1,0\rangle]}=\preceq_{1}\cup\Delta_{O^{\prime}}$, $\preceq^{+}_{[\langle
3,1\rangle]}=\Delta_{O}\cup\preceq^{\prime}_{3}$, and $\preceq^{+}_{[\langle
2,0\rangle,\langle 2,1\rangle]}=\preceq_{2}+\preceq^{\prime}_{2}$.

Notice that in the new game players $1$ and $3$ keep their original
preferences and accessibility relations on the outcomes of their games, and
have trivial ones over those of the other one. On the other hand, player $2$
extends their relations to include both of the games in which they
participated.

##  4 Subgames and equilibria

As usual, we can say that $G$ is a subgame of a game $G^{\prime}$ if the
inclusion map is a morphism in the category Gam, or GamI. We can spell out
what this means in detail:

######  Definition 4.1.

In GamI, a game $G=\langle O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in
I}\rangle$ is a subgame of $G^{\prime}=\langle
O^{\prime},\\{R^{\prime}_{i}\\}_{i\in I},\\{\preceq^{\prime}_{i}\\}_{i\in
I}\rangle$ if $O\subseteq O^{\prime}$ and for each $i\in I$, $R_{i}$ is a
subset of the restriction of $R^{\prime}_{i}$ to $O$, while each $\preceq_{i}$
is a preorder on $O$ that is included in $\preceq^{\prime}_{i}$.

In Gam, a game $G=\langle I,O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in
I}\rangle$ is a subgame of $G^{\prime}=\langle
J,O^{\prime},\\{R^{\prime}_{j}\\}_{j\in J},\\{\preceq^{\prime}_{j}\\}_{j\in
J}\rangle$ if $I\subseteq J$, $O\subseteq O^{\prime}$ and for each $i\in I$,
$R_{i}$ is a subset of the restriction of $R^{\prime}_{i}$ to $O$, while each
$\preceq_{i}$ is a preorder on $O$ that is included in $\preceq^{\prime}_{i}$.

The goal of Game Theory is to postulate solution concepts for games,
indicating what results should be expected if players exhibit different ways
of making decisions [OR94]. In the case of games represented by multi-graphs
we capture the notion of a solution as a selection of a subset of the set of
outcomes on which we keep all the relations of accessibility and preferences
among those outcomes:

######  Definition 4.2.

A solution concept is a mapping $\phi$ such that given a game $G=\langle
I,O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in I}\rangle$ yields a game

$\phi(G)=\langle I,O_{\phi},\\{R^{\phi}_{i}\\}_{i\in
I},\\{\preceq^{\phi}_{i}\\}_{i\in I}\rangle$

such that $O_{\phi}\subseteq O$ and for each $i\in I$, $R^{\phi}_{i}$ and
$\preceq^{\phi}_{i}$ are the restrictions of $R_{i}$ and $\preceq_{i}$ to
$O_{\phi}$.

Notice that the set of players of $\phi(G)$ is the same as in $G$, so this
definition works both in GamI and Gam. The game $\phi(G)$ is the graph induced
by the selected outcomes. The definition of $\phi$ captures which outcomes can
be recommended (under some criterion).

In the case of Gam1, the notion of solution for a decision problem consists of
a subgame in which each outcome $o^{*}\in O_{\phi}$ is an optimal solution.
That is, for every $p\in O$, if $o^{*}R_{\mathbf{1}}p$,
$p\preceq_{\mathbf{1}}o^{*}$. An optimal solution is actually a maximal
element of $\preceq_{\mathbf{1}}$ among those accessible through
$R_{\mathbf{1}}$.

The literature presents several alternative solution concepts, but the most
widely used one is Nash equilibrium, which we adapt to our representation of
games:

######  Definition 4.3.

An outcome $o^{*}\in O$ is a _Nash equilibrium_ if for each $i$, and for each
$p$ such that $\langle o^{*},p\rangle\in R_{i}$, $p\preceq_{i}o^{*}$.

For each game $G=\langle I,O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in
I}\rangle$, then, $\phi^{NE}(G)$ is the subgame of $G$ with the same set of
players $I$, the set of outcomes $O_{\phi^{NE}}\subseteq O$ of all the Nash
equilibria in the game, and the restrictions of $R_{i}$ and $\preceq_{i}$ to
$O_{\phi^{NE}}$.

For simplicity, we will write $o^{*}\in\phi^{NE}(G)$ instead of $o^{*}\in
O_{\phi^{NE}(G)}$.

######  Example 4.4.

Consider a game $G_{BoS}$ which can be seen as a multi-graph representation of
the following strategic game (known as the Battle of the Sexes):

| C | D
---|---|---
A | (2,1) | (0,0)
B | (0,0) | (1,2)

in $G_{BoS}$, $I=\\{1,2\\}$ and $O=\\{r,s,t\\}$, where $r$ can be identified
with $(A,C)$, $s$ with $(B,D)$ and $t$ with both $(A,D)$ and $(B,C)$. The
accessibility and preference relations are represented in Figure 3. Notice the
difference with Figure 2, in which the preferences of both players
(represented by dashed curves) go in different directions between $p$ and $o$
and $q$ and $o$. Here, instead, the preferences of both players are the same
between $r$ and $t$ and between $s$ and $t$.

We can see (recall that the accessibility relations are not transitive) that
both $r,s\in{\phi^{NE}(G_{BoS})}$.

rst Figure 3: Multi-graph of $G_{BoS}$. Red and blue lines correspond to
players 1 and 2, respectively. Full lines correspond to accessibility
relations and dashed ones to preferences.

While game morphisms typically do not preserve equilibria, it is possible to
identify equilibria in products, coproducts, and exponents by building upon
the equilibria of the original games.

######  Theorem 4.5.

Given games $G$ and $G^{\prime}$ in GamI, with $I\neq\emptyset$,then

  1. 1.

$o^{*}\in\phi^{NE}(G)$ and $o^{\prime*}\in\phi^{NE}(G^{\prime})$ if and only
if $\langle o^{*},o^{\prime*}\rangle\in\phi^{NE}(G\times_{I}G^{\prime})$.

  2. 2.

$o^{*}\in\phi^{NE}(G)$ if and only if
$i_{G}(o^{*})\in\phi^{NE}(G+_{I}G^{\prime})$. A similar result applies to
equilibria in $\phi^{NE}(G^{\prime})$

  3. 3.

$o^{\prime*}\in\phi^{NE}(G^{\prime})$ if and only if
$\bm{o}^{\prime\bm{*}}\in\phi^{NE}(G^{\prime G})$, where
$\bm{o}^{\prime\bm{*}}$ is the constant function with value $o^{\prime*}$.

###### Proof.

  1. 1.

Assume that $o^{*}\in\phi^{NE}(G)$, $o^{\prime*}\in\phi^{NE}(G^{\prime})$ and
that for some $i\in I$, $\langle\langle o^{*},o^{\prime*}\rangle,\langle
p,p^{\prime}\rangle\rangle\in R^{\times_{I}}_{i}$. Then, by the definition of
$R^{\times_{I}}_{i}$, $\langle o^{*},p\rangle\in R_{i}$ and $\langle
o^{\prime*},p^{\prime}\rangle\in R^{\prime}_{i}$. Since $o^{*}$ and
$o^{\prime*}$ are equilibria, it turns out that $p\preceq_{i}o^{*}$ and
$p^{\prime}\preceq_{i}o^{\prime*}$, from where $\langle
p,p^{\prime}\rangle\preceq_{i}^{\times_{I}}\langle o^{*},o^{\prime*}\rangle$.

To prove the converse implication, consider $\langle
o^{*},o^{\prime*}\rangle\in\phi^{NE}(G\times_{I}G^{\prime})$ and that for some
$i\in I$, $\langle o^{*},p\rangle\in R_{i}$. Then, since $R^{\prime}_{i}$ is
reflexive, $\langle\langle o^{*},o^{\prime*}\rangle,\langle
p,o^{\prime*}\rangle\rangle\in R^{\times_{I}}_{i}$, therefore
$p\preceq_{i}o^{*}$. The same argument proves that
$o^{\prime*}\in\phi(G^{\prime})$.

  2. 2.

Assume that $o^{*}\in\phi^{NE}(G)$. If we assume that for some $i\in I$,
$\langle i_{O}({o^{*}}),x\rangle\in R_{i}+R^{\prime}_{i}$, then we must have
$x=i_{O}(p)$ for some $p\in O$. Then $\langle{o^{*}},p\rangle\in R_{i}$. By
the hypothesis, $p\preceq_{i}o^{*}$ and thus
$o^{*}\in\phi^{NE}(G+G^{\prime})$.

If now we assume that $i_{O}(o^{*})\in\phi^{NE}(G+G^{\prime})$ and for some
$i\in I$ and $p\in O$, $o^{*}R_{i}p$, then $\langle
i_{O}(o^{*}),i_{O}(p)\rangle\in R_{i}+R^{\prime}_{i}$, so by hypothesis
$i_{O}(p)(\preceq_{i}+\preceq^{\prime}_{i})i_{O}(o^{*})$. It follows that
$p\preceq_{i}o^{*}$, so $o^{*}\in\phi^{NE}(G)$.

  3. 3.

Assume that $o^{\prime*}\in\phi^{NE}(G^{\prime})$. Consider for a fixed $i\in
I$, $f\in\mathcal{O}$ such that $\langle f,\bm{o}^{\prime\bm{*}}\rangle\in
R^{\prime\prime}_{i}$. This means that for every $o,p\in O$, if $\langle
o,p\rangle\in R_{i}$ then $\langle f(o),\bm{o}^{\prime\bm{*}}(p)\rangle\in
R^{\prime}_{i}$. In particular, since $\langle o,o\rangle\in R_{i}$ we have by
hypothesis that $f(o)\preceq^{\prime}_{i}o^{\prime*}$. Thus
$f\preceq^{\prime\prime}_{i}\bm{o}^{\prime\bm{*}}$.

For the converse, consider $o^{\prime*}\in O^{\prime}$ such that
$\bm{o}^{\prime\bm{*}}\in\phi^{NE}(G^{\prime G})$. Then for any $i\in
I,f\in\mathcal{O}$, if $\langle f,\bm{o}^{\prime\bm{*}}\rangle\in
R^{\prime\prime}_{i}$ then $f\preceq^{\prime\prime}_{i}\bm{o}^{\prime\bm{*}}$.
We want to show that $o^{\prime*}\in\phi^{NE}(G^{\prime})$. For this suppose
that $p^{\prime}\in O^{\prime}$ is such that $\langle
p^{\prime},o^{\prime*}\rangle\in R^{\prime}_{i}$. Therefore, for the constant
function $\bm{p^{\prime}}$,
$\langle\bm{p^{\prime}},\bm{o}^{\prime\bm{*}}\rangle\in R^{\prime\prime}_{i}$
also holds, so by hypothesis,
$\bm{p^{\prime}}\preceq^{\prime\prime}_{i}\bm{o}^{\prime\bm{*}}$. This means
that for all $o\in O$,
$\bm{p^{\prime}}(o)\preceq^{\prime}_{i}\bm{o}^{\prime\bm{*}}(o)$, i.e.
$p^{\prime}\preceq^{\prime}_{i}o^{\prime*}$.

∎

######  Theorem 4.6.

Given games $G$ and $G^{\prime}$ in Gam with non-empty sets of players, then

  1. 1.

$o^{*}\in\phi^{NE}(G)$ and $o^{\prime*}\in\phi^{NE}(G^{\prime})$ if and only
if $\langle o^{*},o^{\prime*}\rangle\in\phi^{NE}(G\times G^{\prime})$.

  2. 2.

$o^{*}\in\phi^{NE}(G)$ if and only if
$i_{G}(o^{*})\in\phi^{NE}(G+G^{\prime})$. Similarly for equilibria in
$\phi^{NE}(G^{\prime})$.

  3. 3.

$o^{\prime*}\in\phi^{NE}(G^{\prime})$ if and only if
$\bm{o}^{\prime\bm{*}}\in\phi^{NE}(G^{\prime G})$, where
$\bm{o}^{\prime\bm{*}}$ is the constant function with value $o^{\prime*}$.

###### Proof.

  1. 1.

Assume that $o^{*}\in\phi^{NE}(G)$, $o^{\prime*}\in\phi^{NE}(G^{\prime})$.
Thus for every $i\in I$, $p\in O$, if $\langle o^{*},p\rangle\in R_{i}$, then
$p\preceq_{i}o^{*}$, and for all $j\in J$, $p^{\prime}\in O^{\prime}$, if
$\langle o^{\prime*},p^{\prime}\rangle\in R^{\prime}_{j}$, then
$p^{\prime}\preceq^{\prime}_{i}o^{\prime*}$. Now consider any pair $\langle
i,j\rangle\in I\times J$ such that $\langle\langle
o^{*},o^{\prime*}\rangle,\langle p,p^{\prime}\rangle\rangle\in R_{\langle
i,j\rangle}$. Then, by the definition of $R_{\langle i,j\rangle}$, $\langle
o^{*},p\rangle\in R_{i}$ and $\langle o^{\prime*},p^{\prime}\rangle\in
R^{\prime}_{i}$. Since $o^{*}$ and $o^{\prime*}$ are equilibria, it turns out
that $p\preceq_{i}o^{*}$ and $p^{\prime}\preceq^{\prime}_{j}o^{\prime*}$, from
where $\langle p,p^{\prime}\rangle\preceq_{\langle i,j\rangle}\langle
o^{*},o^{\prime*}\rangle$.

To prove the converse implication, consider $\langle
o^{*},o^{\prime*}\rangle\in\phi^{NE}(G\times G^{\prime})$ and that for some
$i\in I$, $\langle o^{*},p\rangle\in R_{i}$. Then, since for any $j\in J$,
$R^{\prime}_{j}$ is reflexive, $\langle\langle
o^{*},o^{\prime*}\rangle,\langle p,o^{\prime*}\rangle\rangle\in R_{\langle
i,j\rangle}$, so $\langle p,o^{\prime*}\rangle\preceq_{\langle
i,j\rangle}\langle o^{*},o^{\prime*}\rangle$ therefore $p\preceq_{i}o^{*}$.
The same argument proves that $o^{\prime*}\in\phi^{NE}(G^{\prime})$.

  2. 2.

Assume that $o^{*}\in\phi^{NE}(G)$. If we assume that for some $k\in I+J$,
$\langle i_{O}({o^{*}}),x\rangle\in R^{+}_{k}$, then we must have $k\in I$,
and $x=i_{O}(p)$ for some $p\in O$. Then $\langle{o^{*}},p\rangle\in R_{k}$.
By the hypothesis, $p\preceq_{k}o^{*}$, so $x\preceq^{+}_{k}i_{O}(o^{*})$ and
thus $o^{*}\in\phi^{NE}(G+G^{\prime})$.

If now we assume that $i_{O}(o^{*})\in\phi^{NE}(G+G^{\prime})$ and for some
$i\in I$ and $p\in O$, $o^{*}R_{i}p$, then $i_{O}(o^{*})R^{+}_{i}i_{O}(p)$, so
by hypothesis $i_{O}(p)\preceq^{+}_{i}i_{O}(o^{*})$. It follows that
$p\preceq_{i}o^{*}$, so $o^{*}\in\phi^{NE}(G)$.

  3. 3.

Assume that $\langle f,\bm{o}^{\prime\bm{*}}\rangle\in R_{\kappa}$, for some
$\kappa:I\to J$. Then $(\kappa,f)$ and $(\kappa,\bm{o}^{\prime\bm{*}})$ are
morphisms from $G$ to $G^{\prime}$ in Gam, and for all $i\in I,o,p\in O$, if
$\langle o,p\rangle\in R_{i}$, then $\langle
f(o),\bm{o}^{\prime\bm{*}}(p)\rangle\in R^{\prime}_{\kappa(i)}$. By the
hypothesis that $o^{\prime*}\in\phi^{NE}(G^{\prime})$, it turns out that
$f(o)\preceq^{\prime}_{\kappa(i)}\bm{o}^{\prime\bm{*}}(p)$, so
$f\preceq_{\kappa}\bm{o}^{\prime\bm{*}}$.

If $\bm{o}^{\prime\bm{*}}$ is a Nash equilibrium in $G^{\prime G}$, and
$\langle p^{\prime},o^{\prime*}\rangle\in R^{\prime}_{j}$ for some $j\in J$,
then consider the constant functions $\bm{p^{\prime}}$ and $\bm{j}$. By an
argument similar to that in Proposition 3.15, we know that
$(\bm{j},\bm{p}^{\prime})$ and $(\bm{j},\bm{o}^{\prime\bm{*}})$ are morphisms.
Furthermore, $\langle\bm{p}^{\prime},\bm{o}^{\prime\bm{*}}\rangle\in
R_{\bm{j}}$, so by hypothesis,
$\bm{p}^{\prime}\preceq_{\bm{j}}\bm{o}^{\prime\bm{*}}$. Therefore, for all
$i\in I$ and $o\in O$,
$\bm{p}^{\prime}(o)\preceq^{\prime}_{\bm{j}(i)}\bm{o}^{\prime\bm{*}(o)}$,
proving that $p^{\prime}\preceq^{\prime}_{j}o^{\prime*}$ as required. ∎

Furthermore, we can also find the Nash equilibria in coproducts of games in
which we identify some subset of players:

######  Proposition 4.7.

Given games $G=\langle I,O,\\{R_{i}\\}_{i\in I},\\{\preceq_{i}\\}_{i\in
I}\rangle$ and $G^{\prime}=\langle J,O^{\prime},\\{R^{\prime}_{j}\\}_{j\in
J},\\{\preceq^{\prime}_{j}\\}_{j\in J}\rangle$, such that $I\cap
J=S\neq\emptyset$, let $G+G^{\prime}/_{\sim_{S}}$ be the pushout based on
$G_{p}(S)$ as in Example 3.17. Then $o^{*}\in\phi^{NE}(G)$ if and only if
$i_{G}(o^{*})\in\phi^{NE}(G+G^{\prime}/_{\sim_{S}})$.

###### Proof.

Because of the way we defined the pushout, the equivalence classes of outcomes
are singletons and therefore we just identify them with their single element.
Assume that $o^{*}\in\phi^{NE}(G)$ and $\langle i_{G}(o^{*}),p\rangle\in
R^{+}_{[i]}$ for some $i\in I+J$. This means that there exists some $j\in[i]$
such that $\langle i_{G}(o^{*}),p\rangle\in R^{+}_{j}$. It follows that $p$
must be the inclusion of some outcome $p^{\prime}\in O$ and thus $\langle
i_{G}(o^{*}),i_{G}(p^{\prime})\rangle\in R^{+}_{j}$, so $\langle
o^{*},p^{\prime}\rangle\in R_{j}$. Then $p^{\prime}\preceq_{j}o^{*}$ and
therefore $p\preceq^{+}_{j}i_{G}(o^{*})$. In other words
$p\preceq^{+}_{[i]}i_{G}(o^{*})$.

For the converse, assume that $\langle o^{*},p\rangle\in R_{k}$ for some $k\in
I$. Then $\langle i_{G}(o^{*}),i_{G}(p)\rangle\in R^{+}_{[k]}$. Since by
hypothesis $i_{G}(o^{*})\in\phi^{NE}(G+G^{\prime}/_{\sim_{S}})$, we have two
cases:

  * •

if $k\in I\setminus S$, $[k]=\\{\langle k,0\rangle\\}$ and thus $\langle
i_{G}(o^{*}),i_{G}(p)\rangle\in R^{+}_{\langle k,0\rangle}$ so
$i_{G}(p)\preceq^{+}_{\langle k,0\rangle}i_{G}(o^{*})$ and therefore
$p\preceq_{k}o^{*}$.

  * •

if $k\in S$, $[k]=\\{\langle k,0\rangle,\langle k,1\rangle\\}$ but since
$i_{G}(o^{*}),i_{G}(p)\in i_{G}(O)$ this means that $\langle
i_{G}(o^{*}),i_{G}(p)\rangle\in R^{+}_{\langle k,0\rangle}$ so
$p\preceq_{k}o^{*}$ as before.

∎

##  5 Categories with equilibria-preserving morphisms

We can regard $\phi^{NE}$ as an operator taking games to games, but in
general, it is not a functor in Gam. To see this, we observe that even though
game morphisms preserve the accessibility relations and preferences of the
players, this is not enough to make sure that Nash equilibria will be
preserved:

######  Example 5.1.

Consider two simple two-player games: $G$ with $O=\\{a,b\\}$ and
$R_{1}=R_{2}=\preceq_{1}=\preceq_{2}=1_{O}$ and $G^{\prime}$ with
$O^{\prime}=O$, $R^{\prime}_{1}=R^{\prime}_{2}=1_{O}\cup\\{\langle
a,b\rangle,\langle b,a\rangle\\}$, $\preceq^{\prime}_{1}=1_{O}\cup\\{\langle
a,b\rangle\\}$, and $\preceq^{\prime}_{2}=1_{O}\cup\\{\langle b,a\rangle\\}$.
The identity function on $O$ gives a morphism. Both outcomes are Nash
equilibria in $G$ but there is no equilibrium in $G^{\prime}$.

We see in the example above that $1_{O}$ is a morphism from $G\to G^{\prime}$,
but since there are no outcomes in $\phi^{NE}(G^{\prime})$, there is no way to
pick a morphism from $\phi^{NE}(G)$ to $\phi^{NE}(G^{\prime})$ to fulfill the
role of $\phi^{NE}(1_{O})$.

Notice that this negative result applies to both Gam and $\mathbf{Gam}_{I}$. A
way of addressing this issue is by taking hints from [Lap99] and [GHWZ18] in
which the idea of preservation of equilibria is built in the definition of
morphism. In this spirit, we look at some subcategories of $\mathbf{Gam}$ with
equilibria-preserving morphisms.

######  Definition 5.2.

Let NE be the category of games in which all the outcomes are Nash equilibria.
This is a full subcategory of Gam, meaning that all the morphisms in Gam
between two objects in NE are also morphisms in NE.

Notice that if $G$ is a game in NE, $\phi^{NE}({G})={G}$. That is, objects in
NE are fixed points under $\phi^{NE}$.

######  Definition 5.3.

We say that a morphism $f:G\to G^{\prime}$ in Gam _preserves Nash equilibria_
if $f_{O}(\phi^{NE}(O))\subseteq\phi^{NE}(O^{\prime})$.

All the morphisms in NE trivially preserve Nash equilibria. Motivated by this,
we can also define another subcategory of Gam with equilibria preserving
morphisms:

######  Definition 5.4.

Let GamNE be the subcategory of Gam with all the same objects, but only the
equilibria-preserving morphisms.

It can be easily checked that GamNE is a category since identities and
compositions of equilibria-preserving morphisms are equilibria-preserving.
Furthermore, NE is a subcategory of GamNE since as pointed out before, all its
morphisms trivially preserve equilibria.

As a consequence of Theorem 4.6 and Proposition 4.7 we have:

######  Corollary 5.5.

Products, coproducts and pushouts based on player games can be constructed in
GamNE.

A sufficient requirement ensuring that a morphism preserves Nash equilibrium
is as follows:

######  Lemma 5.6.

Let $f:G\to G^{\prime}$ in $\mathbf{Gam}$ be such that $f_{p}:I\rightarrow J$
and $f_{O}:O\to O^{\prime}$ are surjective and for each $i\in I$ and every
pair $o,p\in O$:

  * •

$\langle o,p\rangle\in R_{i}$ iff $\langle f_{O}(o),f_{O}(p)\rangle\in
R^{\prime}_{f_{p}(i)}$

  * •

$o\preceq_{i}p$, iff $f_{O}(o)\preceq_{f_{p}(i)}^{\prime}f_{O}(p)$.

Then, if $o^{*}$ is a Nash equilibrium in $G$, $f_{O}(o^{*})$ is a Nash
equilibrium in $G^{\prime}$. That is, $f$ is a morphism in GamNE.

###### Proof.

Assume that $f_{O}(o^{*})$ is not a Nash equilibrium. Then, there exist $j\in
J$ and $o^{\prime}\in O^{\prime}$ such that

$f_{O}(o^{*})R^{\prime}_{j}o^{\prime},\ \text{ while }\
o^{\prime}\not\preceq^{\prime}_{j}f_{O}(o^{*}).$

Since $f_{p}$ and $f_{O}$ are surjective, there exists $i\in I$ and $o\in O$
such that $f_{p}(i)=j$ and $f_{O}(o)=o^{\prime}$, respectively. Then, we have
that $f_{O}(o^{*})R^{\prime}_{f_{p}(i)}f_{O}(o)$ and
$f_{O}(o)\not\preceq^{\prime}_{f_{p}(i)}f_{O}(o^{*})$. By the assumptions on
$f$, we get that $o^{*}R_{i}o$ and since $o^{*}$ is a Nash equilibrium,
$o\preceq_{i}o^{*}$, so $f_{O}(o)\preceq^{\prime}_{f_{p}(i)}f_{O}(o^{*})$,
which is a contradiction. ∎

Example: Consider the games of examples 2.3 and 4.4, taking the players of
game ${PD}$ to be $I_{PD}=\\{1,2\\}$ while those of $G_{BoS}$ are,
$I_{BoS}=\\{2,3\\}$. That is, $2$ plays both games. The pushout game as
defined in Example 3.17, can be denoted $G_{PD}+_{2}G_{BoS}$, and depicted as
follows:

$1$$2$$3$$G_{BoS}+_{2}G_{PD}$$G_{PD}$$G_{BoS}$

By the result in Theorem 4.6, 2, the Nash equilibria of $G_{PD}$ and
$G_{BoS}$, namely $(D,D),r$ and $s$ are included in the coproduct. Since in
the construction of the pushout the equivalence classes of the outcomes are
all singletons, those are the equilibria of $G_{PD}+_{2}G_{BoS}$. The output
in this graph can be understood as the Nash equilibria, that is, a game in NE.

## References

  * [GHWZ18] Neil Ghani, Jules Hedges, Viktor Winschel, and Philipp Zahn.  Compositional game theory.  In LICS ’18—33rd Annual ACM/IEEE Symposium on Logic in Computer Science, page [10 pp.]. ACM, New York, 2018.
  * [Hed17] Jules Hedges.  Coherence for lenses and open games, 2017.  Preprint at: https://arxiv.org/abs/1704.02230.
  * [Hed18] Jules Hedges.  Morphisms of open games.  In Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV), volume 341 of Electron. Notes Theor. Comput. Sci., pages 151–177. Elsevier Sci. B. V., Amsterdam, 2018.
  * [Jim14] Alfie Jiménez.  Game theory from the category theory point of view.  Universidad Distrital Francisco José de Caldas, Colombia, 2014\.
  * [Lap99] Victor Lapitsky.  On some categories of games and corresponding equilibria.  International Game Theory Review, 1(2):169–185, 1999.
  * [OR94] M.J. Osborne and A. Rubinstein.  A course in game theory.  MIT Press, Cambridge, MA, 1994.
  * [Sch02] Burkhard Schipper.  How undergraduates compute pure nash equilibria in strategic games.  Unpublished notes, Dpt. Economics, UC Davis, http://board.dklevine.com/archive/notes/um268014000000000222.pdf, 2002.
  * [SD15] Nevema Serafimova and Donco Dimovski.  Categorical modeling of learning in games.  International Journal of Mathematics, Game Theory and Algebra, 23(4):21–36, 2015.
  * [Str18] Peter A. Streufert.  The category of node-and-choice preforms for extensive-form games.  Studia Logica, 106(5):1001–1064, 2018.
  * [Tut98] William T. Tutte.  Graph Theory As I Have Known It.  Oxford University Press, NY, 1998.
  * [Vig23] Ignacio Viglizzo.  Basic constructions in the categories of sets, sets with a binary relation on them, preorders, and posets, 2023.  Preprint at: https://arxiv.org/abs/2302.10321.
  * [Vor94] Nicolai N. Vorob’ev.  Foundations of game theory.  Birkhäuser Verlag, Basel, 1994.  Noncooperative games, Translated from the 1984 Russian original by Ralph P. Boas.