# A Compositional Coalgebraic Semantics for Strategic Games111We thank David
Colander, Samson Abramsky, Alexander Kurz, Dusko Pavlovic, Paulo Oliva and
Jules Hedges for discussions as well as the participants at the Games for
Logic and Programming Languages VIII Workshop 2013 in London, the 19th
International Conference on Computing in Economics and Finance in Vancouver
2013 and the Dagstuhl Seminar Coalgebraic Semantics of Reflexive Economics,
2015.

Achim Blumensath  Faculty of Informatics, Masaryk University, Czech Republic
<EMAIL_ADDRESS>and  Viktor Winschel  OICOS GmbH, Mannheim
<EMAIL_ADDRESS>
###### Abstract.

We provide a compositional coalgebraic semantics for strategic games. In our
framework, like in the semantics of functional programming languages,
coalgebras represent the observable behaviour of systems derived from the
behaviour of the parts over an unobservable state space. We use coalgebras to
describe and program stage games, finitely and potentially infinitely repeated
hierarchical or parallel games with imperfect and incomplete information based
on deterministic, non-deterministic or probabilistic decisions of learning
agents in possibly endogenous networks. Our framework is compositional in that
arbitrarily complex network of games can be composed. The coalgebraic approach
allows to represent self-referential or reflexive structures like
institutional dynamics, strategic network formation from within the network,
belief formation, learning agents or other self-referential phenomena that
characterise complex social systems of cognitive agents. And finally our games
represent directly runnable code in functional programming languages that can
also be analysed by sophisticated verification and logical tools of software
engineering.

##  1\. Introduction

We provide a coalgebraic semantic for strategic games based on categorical
methods [15, 1, 21, 9]. The first formulation of games in terms of coalgebraic
semantics appeared in [19], later work comprise [8, 13, 3]. In addition to
these approaches we provide operations in order to compose arbitrarily
complicated games from more basic ones. We allow the players to decide based
on deterministic, non-deterministic or probabilistic algorithms given their
epistemic state that arises from observations, i.e. we feature econometric or
learning agents.

The coalgebraic approach to semantics has evolved for programming languages
that are modelled as abstract unobservable state transition systems [22, 20,
21, 9]. Being build on this mathematical framework our games are directly
implementable for example in Haskell. The key idea that we want to exploit in
this paper is an analogy to bialgebraic theories [10] covering the behaviour
of programming languages. The first usage of bialgebras for a semantic of
cellular automatons for multi-agent systems was developed in [24]. We extend
these ideas to game theory with the operations in the cellular automatons
being players and the cellular grid being a network of players. The semantics
of cellular automatons is here then a semantics of the overall game played by
the coalgebraic players.

The coalgebraic constructions allow not only for infinite horizons or
repetitions of games but also for infinite reflexive structures like beliefs
of beliefs and so on that arise in economic game theory as Harsanyi type
spaces [4, 5, 6, 16, 7]. This structure has been formulated coalgebraically in
computer science [18, 17]. Reflexive structures may also arise as games within
networks that are played over the very structure of the network itself.
Reflexivity naturally arise in systems of cognitive agent who reason about the
system they are part of, see for a socialogical account thereof in [14]. The
resulting mathematical paradoxes are discussed in [12, 25, 2].

Finally, the coalgebraic approach interfaces to the program verification tools
or specification languages like modal logics [11] that can be used to analyse
the strategic games in our framework.

##  2\. Framework

In order to keep the category theoretical overhead to a minimum, we will
introduce all category theoretical notions only in the special case of the
category of sets where the objects are sets and the arrows are total
functions. Other examples of categories contain sets and relations, measurable
spaces and measurable functions, or topological spaces and continuous
functions.

The main concepts we will need are those of a category, functor and natural
transformation.

######  Definition 2.1.

A _category_ $\mathcal{C}$ consists of a class $\mathcal{C}^{\mathrm{obj}}$ of
_objects_ , a class $\mathcal{C}^{\mathrm{arr}}$ of _arrows,_ and a
_composition operation_ $\circ$ on arrows. Each arrow
$f\in\mathcal{C}^{\mathrm{arr}}$ has a _domain_
$X\in\mathcal{C}^{\mathrm{obj}}$ and a _codomain_
$Y\in\mathcal{C}^{\mathrm{obj}}$. We write $f:X\to Y$ to indicate that $f$ is
an arrow with domain $X$ and codomain $Y$. The composition operation is
assumed to satisfy the following two conditions:

  1. (1)

The composition $f\circ g$ of two arrows is defined if, and only if, the
domain of $f$ is equal to the codomain of $g$.

  2. (2)

The composition operation is associative, i.e., for all arrows $f:X\to Y$,
$g:Y\to Z$, $h:Z\to W$,

$\displaystyle(h\circ g)\circ f=h\circ(g\circ f)\,.$

  3. (3)

For each object $X$, there is an _identity arrow_ $\mathrm{id}_{X}:X\to X$
such that

$\displaystyle f\circ\mathrm{id}_{X}=f\quad\text{and}\quad\mathrm{id}_{X}\circ
g=g\,,$

for all arrows $f:X\to Y$ and $g:Z\to X$.

######  Definition 2.2.

A _functor_ $\mathbb{F}$ (from the category of sets to itself) is an operation
assigning

  * •

to each set $X$ a new set $\mathbb{F}(X)$ and

  * •

to each function $g:X\to Y$ a function
$\mathbb{F}(g):\mathbb{F}(X)\to\mathbb{F}(Y)$

such that

$\displaystyle\mathbb{F}(\mathrm{id}_{X})=\mathrm{id}_{\mathbb{F}(X)}\quad\text{and}\quad\mathbb{F}(f\circ
g)=\mathbb{F}(f)\circ\mathbb{F}(g)\,,$

for all sets $X$ and all functions $f:Y\to Z$ and $g:X\to Y$.

As an example, let us introduce three functors that will be used below.

  1. (1)

The _identity functor_ $\mathrm{id}$ maps every set $X$ and every function
$f:X\to Y$ to itself.

  2. (2)

The _finite power-set functor_ $\mathcal{P}_{\mathrm{fin}}$ maps every set $X$
to the set $\mathcal{P}_{\mathrm{fin}}(X)$ of its finite subsets, and it maps
a function $f:X\to Y$ to the function

$\displaystyle\mathcal{P}_{\mathrm{fin}}(f):\mathcal{P}_{\mathrm{fin}}(X)\to\mathcal{P}_{\mathrm{fin}}(Y):S\mapsto\\{\,{\textstyle
f(s)}\mathrel{|}{\textstyle s\in S}\,\\}\,.$

  3. (3)

The _finite probability functor_ $\mathbb{D}_{\mathrm{fin}}$ maps a set $X$ to
the set of all finite probability distributions on $X$, i.e., all maps
$d:X\to[0,1]$ such that only finitely many elements of $X$ are mapped to non-
zero values. For a function $f:X\to Y$, it returns the function

$\displaystyle\mathbb{D}_{\mathrm{fin}}(f):\mathbb{D}_{\mathrm{fin}}(X)\to\mathbb{D}_{\mathrm{fin}}(Y):d\mapsto
d_{f}\,,$

where

$\displaystyle d_{f}(y):=\sum_{x\in f^{-1}(y)}d(x)\,.$

Beside the notion of a functor, we also need those of a natural transformation
and a distributive law.

######  Definition 2.3.

(a) A _natural transformation_ $\eta:\mathbb{F}\Rightarrow\mathbb{G}$ from a
functor $\mathbb{F}$ to a functor $\mathbb{G}$ is a family
$\eta=(\eta_{X})_{X}$ of functions

$\displaystyle\eta_{X}:\mathbb{F}(X)\to\mathbb{G}(X)\,,$

indexed by sets $X$, satisfying

$\displaystyle\eta_{Y}\circ\mathbb{F}(f)=\mathbb{G}(f)\circ\eta_{X}\,,\quad\text{for
every function }f:X\to Y\,.$

(b) A _distributive law_ between two functors $\mathbb{F}$ and $\mathbb{G}$ is
a natural transformation
$\eta:\mathbb{F}\circ\mathbb{G}\Rightarrow\mathbb{G}\circ\mathbb{F}$.

Examples of natural transformations will appear in Section 2.2 below.

###  2.1. Processes

Before introducing games, let us define the simpler notion of a process, which
corresponds to a game with a single player. Processes will provide the
technical machinery our framework is based on.

A process is a state based system transforming an input sequence into an
output sequence. In each step it receives an input value and, depending on its
current state, it produces an output value and changes its state.
Alternatively, a process can decide to terminate. Formally, a _process_ is
given by

  * •

a set $S$ of _states,_

  * •

a set $I$ of _inputs,_

  * •

a set $O$ of _outputs,_

  * •

a set $R$ of _results,_ and

  * •

a function $\pi:S\times I\to\mathbb{C}(R+S\times O)$, for some functor
$\mathbb{C}$.

The function $\pi$ describes one step of the process. When in state $s\in S$
and given the input $i\in I$, the process chooses a possible continuation that
consists in either terminating with a result $r\in R$, or in continuing in a
state $s^{\prime}\in S$ and producing an output value $c\in O$.

In the above definition, the _choice functor_ $\mathbb{C}$ determines which
kind of process we are dealing with. Important examples for choice functors
are the following ones.

  1. (1)

The _deterministic choice functor_ $\mathbb{C}_{\mathrm{det}}=\mathrm{id}$ is
the identity functor. It can be used if the input uniquely determines what
happens next.

  2. (2)

The _non-deterministic choice functor_
$\mathbb{C}_{\mathrm{ndet}}=\mathcal{P}_{\mathrm{fin}}$ is the finite power-
set functor. It can be used if, for a given input, there might be several
possible continuations of the process.

  3. (3)

The _probabilistic choice functor_
$\mathbb{C}_{\mathrm{prob}}=\mathbb{D}_{\mathrm{fin}}$ is the finite
probability functor. It can be used if the continuation of the process is
random.

To apply the category theoretical machinery it will be convenient to write the
function $\pi$ in the form

$\displaystyle\pi:S\to(\mathbb{C}(R+S\times O))^{I}.$

In category theoretical terms, such functions can be seen as so-called
coalgebras.

######  Definition 2.4.

Let $\mathbb{F}$ be a functor. An _$\mathbb{F}$ -coalgebra_ is a function
$h:X\to\mathbb{F}(X)$, for some set $X$.

Hence, a process $\pi$ becomes a $\Pi_{0}$-coalgebra $\pi:S\to\Pi_{0}(S)$,
where $\Pi_{0}$ is the _process_ functor

$\displaystyle\Pi_{0}(X):=\mathbb{C}(R+X\times O)^{I}\,.$

We denote by

$\displaystyle\Pi(S;I,O,R):=\Pi_{0}(S)^{S}$

the set of all processes with states $S$, inputs $I$, outputs $O$, and results
$R$.

###  2.2. Transformations of choice functors

In this section we present several natural transformations between choice
functors that will be needed in the next section.

  1. (1)

For two choice functors $\mathbb{C}_{1}$ and $\mathbb{C}_{2}$, we define a
natural transformation

$\displaystyle\mu_{1,2}:\mathbb{C}_{1}\circ\mathbb{C}_{2}\Rightarrow\mathbb{C}_{1,2}$

that combines a choice of $\mathbb{C}_{1}$ followed by a choice of
$\mathbb{C}_{2}$ into a single choice with respect to a combined functor
$\mathbb{C}_{1,2}$.

  2. (2)

For a choice functor $\mathbb{C}$ and fixed sets $A,B$, we define a
distributive law

$\displaystyle\delta:A+B\times\mathbb{C}(X)\Rightarrow\mathbb{C}(A+B\times
X)\,.$

  3. (3)

For two choice functors $\mathbb{C}_{1}$ and $\mathbb{C}_{2}$, we define a
natural transformation

$\displaystyle\lambda_{1,2}:\mathbb{C}_{1}(X)\times\mathbb{C}_{2}(Y)\Rightarrow\mathbb{C}_{1,2}(X\times
Y)\,.$

The definitions of all three natural transformations are the ones you would
expect from looking at the respective types. We encourage the reader to skip
the formal definitions below, which are only included for the sake of
completeness.

(1.) For $\mathbb{C}_{2}=\mathbb{C}_{\mathrm{det}}$, we can use
$\mathbb{C}_{1,2}:=\mathbb{C}_{1}$ and the identity function

$\displaystyle\mu_{1,\mathrm{det}}:\mathbb{C}_{1}(X)\to\mathbb{C}_{1}(X)\,.$

Analogously, we can define $\mu_{1,2}$ for
$\mathbb{C}_{1}=\mathbb{C}_{\mathrm{det}}$. For
$\mathbb{C}_{1}=\mathbb{C}_{2}=\mathbb{C}_{\mathrm{ndet}}$, we use
$\mathbb{C}_{1,2}:=\mathbb{C}_{\mathrm{ndet}}$ and the functions

$\displaystyle\mu_{\mathrm{ndet},\mathrm{ndet}}:\mathcal{P}_{\mathrm{fin}}(\mathcal{P}_{\mathrm{fin}}(X))\to\mathcal{P}_{\mathrm{fin}}(X):\textstyle
U\mapsto\bigcup_{Z\in U}Z$

mapping a set $U\subseteq\mathcal{P}_{\mathrm{fin}}(X)$ to its union. For
$\mathbb{C}_{1}=\mathbb{C}_{2}=\mathbb{C}_{\mathrm{prob}}$, we use
$\mathbb{C}_{1,2}:=\mathbb{C}_{\mathrm{prob}}$ and the functions

$\displaystyle\mu_{\mathrm{prob},\mathrm{prob}}:\mathbb{D}_{\mathrm{fin}}(\mathbb{D}_{\mathrm{fin}}(X))\to\mathbb{D}_{\mathrm{fin}}(X)$

mapping a distribution $d$ over $\mathbb{D}_{\mathrm{fin}}(X)$ to the
distribution

$\displaystyle x\mapsto\sum_{d^{\prime}\in\mathbb{D}(X)}d(d^{\prime})\cdot
d^{\prime}(x)\,.$

The case where one of $\mathbb{C}_{1}$ and $\mathbb{C}_{2}$ equals
$\mathbb{C}_{\mathrm{ndet}}$ and the other one equals
$\mathbb{C}_{\mathrm{prob}}$ is more involved. We omit the definitions.

(2.) We define $\delta$ as follows. If $\mathbb{C}=\mathbb{C}_{\mathrm{det}}$,
we can use the identity map

$\displaystyle\delta_{\mathrm{det}}:A+B\times X\to A+B\times X\,.$

If $\mathbb{C}=\mathbb{C}_{\mathrm{ndet}}$, we use the map

$\displaystyle\delta_{\mathrm{ndet}}:A+B\times\mathcal{P}_{\mathrm{fin}}(X)\to\mathcal{P}_{\mathrm{fin}}(A+B\times
X)\,,$

defined by

$\displaystyle\delta_{\mathrm{ndet}}(x):=\begin{cases}\\{x\\}&\text{for }x\in
A\,,\\\ \\{\,{\textstyle(b,u)}\mathrel{|}{\textstyle u\in U}\,\\}&\text{for
}x=(b,U)\in B\times\mathcal{P}_{\mathrm{fin}}(X)\,.\end{cases}$

If $\mathbb{C}=\mathbb{C}_{\mathrm{prob}}$, we use the map

$\displaystyle\delta_{\mathrm{prob}}:A+B\times\mathbb{D}_{\mathrm{fin}}(X)\to\mathbb{D}_{\mathrm{fin}}(A+B\times
X)\,,$

defined by

$\displaystyle\delta_{\mathrm{prob}}(x):=\begin{cases}d_{x}&\text{for }x\in
A\,,\\\ d_{b,e}&\text{for }x=(b,e)\in
B\times\mathbb{D}_{\mathrm{fin}}(X)\,,\end{cases}$

where

$\displaystyle d_{x}(y):=\begin{cases}1&\text{for }y=x\,,\\\
0&\text{otherwise}\,.\end{cases}\quad\text{and}\quad
d_{b,e}(y):=\begin{cases}e(c)&\text{for }y=(b,c)\,,\\\
0&\text{otherwise}\,.\end{cases}$

(3.) For $\mathbb{C}_{1}=\mathbb{C}_{\mathrm{det}}$, we can use for

$\displaystyle\lambda_{\mathrm{det},\mathrm{det}}:X\times\mathbb{C}_{2}(Y)\Rightarrow\mathbb{C}_{2}(X\times
Y)$

the distributive law $\delta$ from (2.) (setting $A:=\emptyset$ and $B:=X$).
The case where $\mathbb{C}_{2}=\mathbb{C}_{\mathrm{det}}$ is handled
symmetrically. For $\mathbb{C}_{1}=\mathbb{C}_{2}=\mathbb{C}_{\mathrm{ndet}}$,
we define

$\displaystyle\lambda_{\mathrm{ndet},\mathrm{ndet}}:\mathcal{P}_{\mathrm{fin}}(X)\times\mathcal{P}_{\mathrm{fin}}(Y)\to\mathcal{P}_{\mathrm{fin}}(X\times
Y):(U,V)\mapsto U\times V\,.$

For $\mathbb{C}_{1}=\mathbb{C}_{2}=\mathbb{C}_{\mathrm{prob}}$, we define

$\displaystyle\lambda_{\mathrm{prob},\mathrm{prob}}:\mathbb{D}_{\mathrm{fin}}(X)\times\mathbb{D}_{\mathrm{fin}}(Y)\to\mathbb{D}_{\mathrm{fin}}(X\times
Y):(d,d^{\prime})\mapsto e_{d,d^{\prime}}$

where

$\displaystyle e_{d,d^{\prime}}(x,y):=d(x)\cdot d^{\prime}(y)\,.$

Again, we omit the cases mixing $\mathbb{C}_{\mathrm{ndet}}$ and
$\mathbb{C}_{\mathrm{prob}}$.

###  2.3. Operations on processes

Before introducing games, let us present several operations intended to
construct processes from simpler ones. We start with sums and products of
processes.

(a) The _sum_ of two processes is a process where, depending on the state,
either the first process takes a step, or the second one does. We only support
the case where both processes use the same choice functor. Formally, the sum
$+$ is the operation

$\displaystyle{+}:\Pi(S_{0};I,O_{0},R_{0})+\Pi(S_{1};I,O_{1},R_{1})\to\Pi(S_{0}+S_{1};I,O_{0}+O_{1},R_{0}+R_{1})$

defined by

$\displaystyle(\pi_{0}+\pi_{1})(s):=\begin{cases}\pi_{0}(s)&\text{if }s\in
S_{0}\,,\\\ \pi_{1}(s)&\text{if }s\in S_{1}\,.\end{cases}$

(b) The _product_ $\pi_{1}\times\pi_{2}$ of two processes is a process where
both components take steps simultaneously. We support the case where $\pi_{1}$
and $\pi_{2}$ use different choice functors. Suppose that $\pi_{1}$ uses
$\mathbb{C}_{1}$, while $\pi_{2}$ uses $\mathbb{C}_{2}$. Formally, the product
$\times$ is the operation

$\displaystyle{\times}$
$\displaystyle:\Pi(S_{0};I_{0},O_{0},R_{0})+\Pi(S_{1};I_{1},O_{1},R_{1})\to{}$
$\displaystyle\qquad\Pi(S_{0}\times S_{1};\ I_{0}\times I_{1},\ O_{0}\times
O_{1},\ R_{0}\times R_{1}+R_{0}+R_{1})$

defined by

$\displaystyle(\pi_{0}\times\pi_{1})(s_{0},s_{1})(i_{0},i_{1}):=(\mathbb{C}_{1,2}(f)\circ\lambda_{1,2})(\pi_{0}(s_{0})(i_{0}),\pi_{1}(s_{1})(i_{1}))\,,$

where $\lambda$ is the natural transformation from Section 2.2 and

$\displaystyle f:{}$ $\displaystyle(R_{0}+S_{0}\times
O_{0})\times(R_{1}+S_{1}\times O_{1})\to{}$ $\displaystyle\quad(R_{0}\times
R_{1}+R_{0}+R_{1}+S_{0}\times S_{1}\times O_{0}\times O_{1})$

is the function

$\displaystyle f(x_{0},x_{1}):=\begin{cases}(x_{0},x_{1})&\text{if }x_{0}\in
R_{0}\text{ and }x_{1}\in R_{1}\,,\\\ x_{0}&\text{if }x_{0}\in R_{0}\text{ and
}x_{1}\notin R_{1}\,,\\\ x_{1}&\text{if }x_{0}\notin R_{0}\text{ and }x_{1}\in
R_{1}\,,\\\ (s_{0},s_{1},c_{0},c_{1})&\text{if }x_{0}=(s_{0},c_{0})\text{ and
}x_{1}=(s_{1},c_{1})\,,\end{cases}$

(c) We also introduce two operations to modify the inputs and outputs. Given a
process $\pi$ and a function $f$, we define new processes $\pi\triangleright
f$ and $f\triangleright\pi$ as follows.

For a function $f:S\times O\to S\times O^{\prime}$ and a process
$\pi\in\Pi(S;I,O,R)$, the process $\pi\triangleright f$ applies, after each
step, the function $f$ to the returned state-output pair. Formally, we define
$\pi\triangleright f\in\Pi(S;I,O^{\prime},R)$ by

$\displaystyle(\pi\triangleright
f)(s)(i):=\mathbb{C}(\mathrm{id}+f)\bigl{(}\pi(s)(i)\bigr{)}\,.$

For a function $f:I^{\prime}\to I$ and a process $\pi\in\Pi(S;I,O,R)$, the
process $f\triangleright\pi$ applies, before each step, the function $f$ to
the given input value. Formally, we define
$f\triangleright\pi\in\Pi(S;I^{\prime},O,R)$ by

$\displaystyle(f\triangleright\pi)(s)(i):=\pi(s)(f(i))\,.$

(d) Finally, we introduce two more complicated operations on processes. The
_feedback operation_ takes a process $\pi$ and feeds back its output as an
additional input. That is, given a process $\pi\in\Pi(S;I\times O,O,R)$ we
construct a new process $\pi^{\circlearrowleft}\in\Pi(S\times O;I,O,R)$ which,
at each step, calls the process $\pi$ with its current input value and the
output of the previous turn. We define

$\displaystyle\pi^{\circlearrowleft}(s,c)(i):=\mathbb{C}(\mathrm{id}_{R}+f)(\pi(s)(i,c))\,,$

where

$\displaystyle f:S\times O\to(S\times O)\times O:(s,c)\mapsto((s,c),c)\,.$

(e) The _cascading operation_ takes two processes $\pi$ and $\varrho$, runs
them in parallel, and uses the outputs of the first process as inputs of the
second one. We support the case where $\pi$ and $\varrho$ use different choice
functors. Suppose that $\pi$ uses $\mathbb{C}_{1}$, while $\varrho$ uses
$\mathbb{C}_{2}$. Given $\pi\in\Pi(S;I,M,P)$ and $\varrho\in\Pi(T;M,O,R)$, we
define $\pi\triangleright\varrho\in\Pi(S\times T;I,O,P+R)$ as follows. Let

$\displaystyle\varrho^{\prime}$ $\displaystyle:T\times
M\to\mathbb{C}_{2}(R+T\times O):(t,m)\mapsto\varrho(t)(m)\,,$
$\displaystyle\pi^{\prime}$ $\displaystyle:S\times T\times
I\to\mathbb{C}_{1}(P+S\times T\times
M):(s,t,i)\mapsto\mathbb{C}_{1}(\mathrm{id}_{P}+f_{t})\bigl{(}\pi(s)(i)\bigr{)}\,,$

where

$\displaystyle f_{t}:S\times M\to S\times T\times M:(s,m)\mapsto(s,t,m)\,.$

We set

$\displaystyle(\pi\triangleright\varrho)(s,t)(i):=\bigl{(}\mathbb{C}_{1,2}(g)\circ\mu\circ\delta\circ\mathbb{C}_{1}(\mathrm{id}_{P}+\mathrm{id}_{S}\times\varrho^{\prime})\bigr{)}\bigl{(}\pi^{\prime}(s,t,i)\bigr{)}\,,$

where $\mu$ and $\delta$ are the natural transformations from Section 2.2 and

$\displaystyle g:P+S\times(R+T\times O)\to P+R+S\times T\times O$

is the function

$\displaystyle g(x):=\begin{cases}x&\text{if }x\in P\,,\\\ r&\text{if
}x=(s,r)\in S\times R\,,\\\ (s,t,c)&\text{if }x=(s,(t,c))\in S\times T\times
O\,.\end{cases}$

###  2.4. Games

We consider games between several players that can consist of finitely many or
infinitely many rounds. The game starts in a certain state and, in each round,
every player chooses an action to perform. These actions determine the state
the game enters next. To determine the outcome of a game, we assume that it
produces an output value with each turn and that, at the end of the game, it
returns some result. Together, the produced sequence of output values and the
final result will determine the outcome. Formally, a game is therefore given
by

  * •

a set $N$ of _players,_

  * •

for each player $p\in N$, a set $A_{p}$ of _actions_ for player $p$,

  * •

a set $S$ of _states_ of the game,

  * •

a set $R$ of _results,_

  * •

a set $O$ of _output values,_ and

  * •

a function

$\displaystyle\gamma:S\times\prod_{p\in N}A_{p}\to\mathbb{C}(R+S\times O)\,.$

Thus, a game is a process where the input has the special form $\prod_{p\in
N}A_{p}$. In particular, a game $\gamma$ is a $\Gamma$-coalgebra

$\displaystyle\gamma:S\to\Gamma(S)\,,$

where $\Gamma$ is the _game_ functor

$\displaystyle\Gamma(S):=\mathbb{C}(R+S\times O)^{\prod_{p\in N}A_{p}}\,.$

######  Example 2.5.

To formalize the Prisoner’s Dilemma in our framework we use two players
$N:=\\{1,2\\}$, each with two actions $A_{p}:=\\{c,d\\}$ (‘confess’ and
‘deny’). The game needs only one state $S:=\\{{*}\\}$, no outputs
$O:=\emptyset$, and results $R:=\mathbb{R}\times\mathbb{R}$. The deterministic
game function $\gamma:S\to R^{A_{1}\times A_{2}}$ is defined by

$\displaystyle\gamma({*})(a_{1},a_{2}):=\begin{cases}(1,1)&\text{if
}(a_{1},a_{2})=(c,c)\,,\\\ (2,-1)&\text{if }(a_{1},a_{2})=(d,c)\,,\\\
(-1,2)&\text{if }(a_{1},a_{2})=(c,d)\,,\\\ (0,0)&\text{if
}(a_{1},a_{2})=(d,d)\,.\end{cases}$

######  Example 2.6.

Let us also formalize the Repeated Prisoner’s Dilemma. Again, there are two
players $N:=\\{1,2\\}$ with two actions $A_{p}:=\\{c,d\\}$ each. We still have
only one state $S:=\\{{*}\\}$, but now use outputs
$O:=\mathbb{R}\times\mathbb{R}$ and no results $R:=\emptyset$. The
deterministic game function $\gamma:S\to(S\times O)^{A_{1}\times A_{2}}$ is
defined by

$\displaystyle\gamma({*})(a_{1},a_{2}):=\begin{cases}({*},(1,1))&\text{if
}(a_{1},a_{2})=(c,c)\,,\\\ ({*},(2,-1))&\text{if }(a_{1},a_{2})=(d,c)\,,\\\
({*},(-1,2))&\text{if }(a_{1},a_{2})=(c,d)\,,\\\ ({*},(0,0))&\text{if
}(a_{1},a_{2})=(d,d)\,.\end{cases}$

######  Example 2.7.

For a more involved example, we consider a social game using endogenous
networks. Given a group $N$ of players, we model their social interactions as
a graph $\langle N,E\rangle$ where the edge relation $E$ connects two players
if they are friends. In each turn of the game, new friendships may form and
old ones may end. Thus, the graph changes in the course of the game. We can
model this game in our framework by using as set of states $S$ the set of all
possible edge relations $E$. Each player $p$ has two possible actions: he can
befriend another player $q$, or he can end an existing friendship with some
player. The game function $\gamma:S\to\Gamma(S)$ takes the current network $E$
as an input and modifies it according to the actions of all players.

###  2.5. Players and strategies

Let $\gamma:S\to\Gamma(S)$ be a game. A _strategy_ for a player $p\in N$ is a
function telling him which action to choose in a given turn of the game. The
player has access to his current observations and his knowledge of the play so
far. Thus, formally a strategy is a function

$\displaystyle\sigma:E_{p}\times B_{p}\to\mathbb{C}(E_{p}\times A_{p})\,,$

where $E_{p}$ is the _epistemic state_ of player $p$ and $B_{p}$ is the set of
possible _observations._ Again, we write $\sigma$ as a coalgebra

$\displaystyle\sigma:E_{p}\to\mathbb{C}(E_{p}\times A_{p})^{B_{p}}\,,$

that is, a process with inputs $B_{p}$, outputs $A_{p}$, and results
$R=\emptyset$.

The observations of a player depend on the current input, the output of the
previous turn, and the actions of all players during the previous turn. To
specify what exactly player $p$ can observe, we use a function

$\displaystyle\beta_{p}:O\times\prod_{p\in N}A_{p}\to B_{p}\,,$

which we assume to be a part of the description of the game.

######  Example 2.8.

Suppose we are playing the Repeated Prisoner’s Dilemma. A probabilistic
strategy for player $1$ would be to copy the previous action of the other
player with probability $2/3$, and to choose the other action with probability
$1/3$. We use only one state $E_{1}:=\\{*\\}$ and the observations
$B_{1}:=\\{c,d\\}$ are the previous actions of player $2$.

$\displaystyle\sigma_{1}:\\{{*}\\}\to\mathbb{D}_{\mathrm{fin}}(\\{*\\}\times\\{c,d\\})^{\\{c,d\\}}:{*}\mapsto
d$

where

$\displaystyle d(x)({*},y):=\begin{cases}2/3&\text{if }x=y\,,\\\ 1/3&\text{if
}x\neq y\,.\end{cases}$

If, in a game $\gamma$, we fix strategies $(\sigma_{p})_{p\in N_{0}}$ for a
subset $N_{0}\subseteq N$ of the players, we obtain a new game with players
$N\setminus N_{0}$. We denote this game by $\gamma[\sigma_{p}]_{p\in N_{0}}$.
The formal definition is as follows. For players $p\in N\setminus N_{0}$ where
no strategy is provided, we introduce a non-deterministic dummy strategy that,
independently of the input, always tells the player to play some action from
$A_{p}$ without restricting his choice. This strategy uses only one state. Its
formal definition is

$\displaystyle\sigma_{p}:1\to\mathcal{P}_{\mathrm{fin}}(1\times
A_{p})^{B_{p}}:i\mapsto A_{p}\,.$

With the help of these dummy strategies, we can define the desired game as

$\displaystyle\gamma[\sigma_{p}]_{p\in
N_{0}}:=\Bigl{[}\Bigl{[}f\triangleright\prod_{p\in
N}\sigma_{p}\Bigr{]}^{\circlearrowleft}\triangleright\gamma\Bigr{]}^{\circlearrowleft}\in\Pi\bigl{(}\textstyle
S\times\prod_{p\in N}E_{p}\times O\times\prod_{p\in
N}A_{p},\emptyset,O,R\bigr{)}\,,$

where the function

$\displaystyle f:O\times\prod_{p\in N}A_{p}\to\prod_{p\in
N}B_{p}:(c,\bar{a})\mapsto(\beta_{p}(c,\bar{a}))_{p\in N}\,,$

computes the observations of each player. The states of this new game are
tuples

$\displaystyle(s,\bar{e},c,\bar{a})\in S\times\prod_{p\in N}E_{p}\times
O\times\prod_{p\in N}A_{p}$

consisting of a state $s$ of the old game, the epistemic states $\bar{e}$ of
the players, the output $c$ of the last turn, and the actions $\bar{a}$ the
players chose last turn.

###  2.6. Game trees

Given a game $\gamma$ and strategies $\sigma_{p}$ for each player, we would
like to compute the result of the game if each player follows her strategy.
Besides the techniques from the previous section, we need one more definition:
that of a _game tree._ Informally, a game tree is a tree containing all
possible sequences of events allowed in the game. The formal definition is
based on the notion of a _final_ coalgebra.

######  Definition 2.9.

Let $\mathbb{F}$ be a functor. An $\mathbb{F}$-coalgebra
$\omega:\Omega\to\mathbb{F}(\Omega)$ is _final_ if, for every
$\mathbb{F}$-coalgebra $h:X\to\mathbb{F}(X)$, there exists a unique morphism
$\varphi:X\to\Omega$ such that the diagram

commutes.

For the process functors

$\displaystyle\Pi_{0}(X)=\mathbb{C}(R+X\times O)^{I}$

there exist final $\Pi_{0}$-coalgebras $\omega:\Omega\to\Pi_{0}(\Omega)$,
provided that the choice functor $\mathbb{C}$ is sufficiently well-behaved. In
particular, this is the case for the three choice functors
$\mathbb{C}_{\mathrm{det}}$, $\mathbb{C}_{\mathrm{ndet}}$, and
$\mathbb{C}_{\mathrm{prob}}$.

Let us describe the final $\Pi_{0}$-coalgebras for the choice functors
$\mathbb{C}$ introduced above. The elements of these final coalgebras are
_trees,_ which are directed acyclic graphs such that there exists one vertex,
the _root_ of the tree, with the property that every other vertex can be
reached by a unique path from the root. A tree is _$(A,B,C)$ -labelled_ if it
has more than one vertex and

  * •

the root is unlabelled,

  * •

every other inner vertex is labelled by an element of $B$,

  * •

every leaf is labelled by an element of $A\cup B$,

  * •

every edge is labelled by an element of $C$.

If there is an edge with label $c$ from a vertex $x$ to a vertex $y$, we call
$y$ the _$c$ -successor_ of $x$.

(a) We start with the functor

$\displaystyle\Pi_{0}(X):=(A+X\times B)^{C}$

for $\mathbb{C}=\mathbb{C}_{\mathrm{det}}$. In this case the final
$\Pi_{0}$-coalgebra $\omega:\Omega\to\Pi_{0}(\Omega)$ takes the following
form. The set $\Omega$ consists of all $(A,B,C)$-labelled trees that are
_deterministic,_ that is, such that every leaf has a label in $A$ and every
inner vertex has exactly one $c$-successor, for each $c\in C$. The function
$\omega$ is defined as follows: given a tree $T$ and a value $c\in C$, we
distinguish two cases depending on the label of the $c$-successor $x$ of the
root. If $x$ is labelled by an element $a\in A$, we set $\omega(T)(c):=a$. If
$x$ is labelled by an element $b\in B$, we set $\omega(T)(c):=\langle
T^{\prime},b\rangle$ where $T^{\prime}$ is the subtree of $T$ rooted at $x$.

To see that this is indeed the final $\Pi_{0}$-coalgebra, consider an
arbitrary $\Pi_{0}$-coalgebra $\pi:S\to\Pi_{0}(S)$. The required unique
function $\varphi:S\to\Omega$ is given by

$\displaystyle\varphi(s):=T_{s}\,,\quad\text{for }s\in S\,,$

where the tree $T_{s}$ is defined as follows: we first construct a graph
$\langle V,E\rangle$ with set of vertices $V:=A+S\times B$ and the following
edges. For every $\langle s,b\rangle\in S\times B$, there is a $c$-labelled
edge from $\langle s,b\rangle$ to $\pi(s)(c)$. The elements of $A$ have no
outgoing edges. The vertex labelling is the natural one: a vertex $a\in A$
gets the label $a$ and a vertex $\langle s,b\rangle$ gets the label $b\in B$.

The tree $T_{s}$ is now obtained from the unravelling of this graph starting
at a vertex $\langle s,b\rangle$, for an arbitrary $b\in B$, by forgetting the
label $b$ of the root. Formally, the _unravelling_ of a graph $\langle
V,E\rangle$ starting at a vertex $s$ is defined as the tree consisting of all
finite paths through the graph that start at $s$. There is an edge between two
such paths if the second one is obtained from the first one by appending a
single edge. This edge also determines the label of the edge label. The vertex
labelling of the tree is obtained by labelling each path with the label of its
end-vertex.

######  Example 2.10.

Let $\pi\in\Pi(\\{s_{a},s_{b}\\};\\{0,1\\},\\{a,b\\},\emptyset)$ be the
deterministic process defined by

$\displaystyle\pi(s_{x})(y):=\begin{cases}(s_{a},x)&\text{if }y=0\,,\\\
(s_{b},x)&\text{if }y=1\,.\end{cases}$

The (top of the) tree $\varphi(s_{a})$ has the following form:

To see that the function $\varphi$ defined in this way has the required
property we need to check that

$\displaystyle\Pi_{0}(\varphi)\circ\pi=\omega\circ\varphi\,.$

For $s\in S$ and $c\in C$, suppose that

$\displaystyle\pi(s)(c)=\langle s^{\prime},b\rangle\in S\times B\,.$

Let $T:=\varphi(s)$ and $T^{\prime}:=\varphi(s^{\prime})$. Note that
$T^{\prime}$ is equal to the subtree of $T$ rooted at the $c$-successor of the
root and that this $c$-successor is labelled by $b$. Hence,

$\displaystyle(\Pi_{0}(\varphi)\circ\pi)(s)(c)=\Pi_{0}(\varphi)(\langle
s^{\prime},b\rangle)=\langle
T^{\prime},b\rangle=\omega(T)(c)=(\omega\circ\varphi)(s)(c)\,.$

In the case where $\pi(s)(c)=a\in A$ we argue similarly.

(b) Consider the functor

$\displaystyle\Pi_{0}(X):=\mathcal{P}_{\mathrm{fin}}(A+X\times B)^{C}$

for non-deterministic games. In this case the final $\Pi_{0}$-coalgebra
$\omega:\Omega\to\Pi_{0}(\Omega)$ takes the following form. The set $\Omega$
consists of all $(A,B,C)$-labelled trees where each vertex has only finitely
many $c$-successors, for every $c\in C$. The function $\omega$ is defined as
follows. Given a tree $T$ and a value $c\in C$, let $S$ be the set of all
$c$-successors of the root of $T$. Then $\omega(T)(c)$ returns the set

$\displaystyle\\{\,{\textstyle a\in A}\mathrel{|}{\textstyle\text{some }x\in
S\text{ has label }a}\,\\}\cup\\{\,{\textstyle\langle
T_{x},b\rangle}\mathrel{|}{\textstyle x\in S\text{ has label }b\in B}\,\\}\,,$

where $T_{x}$ is the subtree of $T$ rooted at $x$.

Given an arbitrary $\Pi_{0}$-coalgebra $\pi:S\to\Pi_{0}(S)$, the required
unique function $\varphi:S\to\Omega$ is defined similarly as in (a). We set

$\displaystyle\varphi(s):=T_{s}\,,\quad\text{for }s\in S\,,$

where $T_{s}$ is the unravelling of the following graph $\langle V,E\rangle$.
Again the set of vertices is $V:=A+S\times B$ and the vertex labelling is the
natural one. For each $\langle s,b\rangle\in S\times B$, there is a
$c$-labelled edge from $\langle s,b\rangle$ to $x$, for every $x\in\pi(s)(c)$.

As above, a straightforward calculation shows that the function $\varphi$
defined in this way has the required properties.

######  Example 2.11.

Let $\pi\in\Pi(\\{*\\};\\{0,1\\},\\{a,b\\},\emptyset)$ be the non-
deterministic process defined by

$\displaystyle\pi({*})(x):=\\{({*},a),({*},b)\\}\,.$

The tree $\varphi({*})$ has the following form:

(c) Finally, consider the functor

$\displaystyle\Pi_{0}(X):=\mathbb{D}_{\mathrm{fin}}(A+X\times B)^{C}$

for probabilistic games. In this case the final $\Pi_{0}$-coalgebra
$\omega:\Omega\to\Pi_{0}(\Omega)$ takes the following form: the set $\Omega$
consists of all $(A,B,C\times[0,1])$-labelled trees where, for every $c\in C$
and every vertex $v$,

  * •

$v$ has only finitely many outgoing edges labelled $\langle c,p\rangle$, for
some $p\in[0,1]$,

  * •

the sum of all values $p$ such that there is an outgoing edge with label
$\langle c,p\rangle$ equals $1$, and

  * •

$v$ does not have two outgoing edges with labels $\langle c,p\rangle$ and
$\langle c,p^{\prime}\rangle$ where $p,p^{\prime}\in[0,1]$ and such that the
subtrees rooted at the corresponding successors are isomorphic.

The function $\omega$ is defined as follows: given a tree $T$, a value $c\in
C$, $a\in A$, and $\langle T^{\prime},b\rangle\in\Omega\times B$, we set

$\displaystyle\omega(T)(c)(a):=p$

if the root of $T$ has an outgoing edge with label $\langle c,p\rangle$ that
leads to a leaf with label $a$, and we set

$\displaystyle\omega(T)(c)(\langle T^{\prime},b\rangle):=p$

if the root of $T$ has an outgoing edge with label $\langle c,p\rangle$ that
leads to an inner vertex $x$ with label $b$ such that the subtree of $T$
rooted at $x$ is equal to $T^{\prime}$. In all other cases, we set

$\displaystyle\omega(T)(c)(x):=0\,.$

Given an arbitrary $\Pi_{0}$-coalgebra $\pi:S\to\Pi_{0}(S)$, the required
unique function $\varphi:S\to\Omega$ is defined similarly as in (a). We set

$\displaystyle\varphi(s):=T_{s}\,,\quad\text{for }s\in S\,,$

where $T_{s}$ is the unravelling of the following graph $\langle V,E\rangle$:
again the set of vertices is $V:=A+S\times B$ and the vertex labelling is the
natural one. For each $\langle s,b\rangle\in S\times B$ and every $x\in
A+S\times B$, there is a $\langle c,\pi(s)(c)(x)\rangle$-labelled edge from
$\langle s,b\rangle$ to $x$.

As above, a straightforward calculation shows that the function $\varphi$
defined in this way has the required properties.

######  Example 2.12.

Let $\pi\in\Pi(\\{*\\};\\{0,1\\},\\{a,b\\},\emptyset)$ be the probabilistic
process defined by

$\displaystyle\pi({*})(x)(s,c):=1/2\,.$

The tree $\varphi({*})$ has the following form:

(Due to space considerations we have omitted some edge labels.)

We have seen that the final coalgebras consist of trees describing all
possible sequences in the game. Given a game $\gamma:S\to\Gamma(S)$ and the
unique morphism $\varphi:S\to\Omega$ into the final $\Gamma$-coalgebra, we
call the tree $\varphi(s)$ the _game tree_ of $\gamma$ when starting in state
$s\in S$.

###  2.7. The outcome of a game

After these preparations we can determine the outcome of a game. Given a game
$\gamma$ and strategies $\sigma_{p}$ for each player, we can compute a game
$\gamma[\sigma_{p}]_{p}$ without players and determine its game tree $T$.
Hence, it remains to define how to read off the outcome from a game tree.

Let $\gamma:S\to\Gamma(S)$ be a game without players and let
$\omega:\Omega\to\Gamma(\Omega)$ be the final $\Gamma$-coalgebra. To define
the outcome $\gamma$ we specify a set $U$ of _outcomes_ and two functions
$\varrho:\Omega\to U$ and $\tau:\Gamma(U)\to U$ such that

Intuitively, $\varrho$ maps a game tree to its outcome, while $\tau$ computes
the outcome of a game from the outcomes of its subgames. Hence, $\tau$
performs a local computation, while $\varrho$ is needed to compute the limit
of an infinite sequence of turns. Ideally, the function $\tau$ uniquely
determines $\varrho$. This is the case, for instance, for discounted pay-off
games, where the value of a game mostly depends on an initial segment of the
game tree.

######  Example 2.13.

Consider a deterministic two player game with $R=\mathbb{R}\times\mathbb{R}$
and $O=\mathbb{R}\times\mathbb{R}$. Fixing deterministic strategies for both
players, we obtain a deterministic zero-player game, the game tree of which is
either an infinite sequence over $O$ or a finite sequence where the last
element is from $R$ and the remaining ones are from $O$.

Choosing a discount factor $\lambda\in(0,1)$, we can define the outcome by the
functions

$\displaystyle\tau:R+U\times O\to U\quad\text{and}\quad\varrho:\Omega\to U\,,$

where $U:=\mathbb{R}\times\mathbb{R}$ and

$\displaystyle\tau(x,y)$ $\displaystyle:=(x,y)\,,$
$\displaystyle\quad\text{for }(x,y)\in R\,,$ $\displaystyle\tau((x,y),(u,v))$
$\displaystyle:=(\lambda x+u,\lambda y+v)\,,$ $\displaystyle\quad\text{for
}((x,y),(u,v))\in U\times O\,.$

The function $\varrho$ is uniquely determined by $\tau$. An explicit
definition is

$\displaystyle\textstyle\varrho(x_{n},y_{n})_{n<\alpha}:=\bigl{(}\sum_{n<\alpha}\lambda^{n}x_{n},\sum_{n<\alpha}\lambda^{n}y_{n}\bigr{)}\,.$

###  2.8. Nash equilibria

Having defined the outcome of a game, we can introduce equilibria. Consider a
game $\gamma$ with set of players $N$ and set of outcomes $U:=\mathbb{R}^{N}$.
We fix an output value $\hat{c}\in O$ and actions $\hat{a}\in\prod_{p}A_{p}$
that will serve as imaginary outcome of the ‘first game turn’. Let
$\tau:\Gamma(U)\to U$ and $\varrho:\Omega\to U$ be the functions to compute
the outcome of $\gamma$. For a tuple $\bar{\sigma}=(\sigma_{p})_{p\in N}$ of
strategies, we denote by $\varphi[\bar{\sigma}]:S\to\Omega$ the function from
the reduced game $\gamma[\bar{\sigma}]$ to the final coalgebra.

Given strategies $\sigma_{p}$, for each $p\in N$, initial states $s_{0}\in S$
and $e_{p}\in E_{p}$, for $p\in N$, and a player $q\in N$, we say that
$\langle\sigma_{q},e_{q}\rangle$ is a _best response_ to
$\langle\sigma_{p},e_{p}\rangle_{p\in N\setminus\\{q\\}}$ in the game
$\langle\gamma,s_{0}\rangle$ if

$\displaystyle\varrho(\varphi[\bar{\sigma}](s_{0},\bar{e},\hat{c},\hat{a}))\geq\varrho(\varphi[\bar{\sigma}^{\prime}](s_{0},\bar{e}^{\prime},\hat{c},\hat{a}))\,,$

for all tuples $\bar{\sigma}^{\prime}$ and $\bar{e}^{\prime}$ that differ
from, respectively, $\bar{\sigma}$ and $\bar{e}$ only in the $p$-th component.

We say that $\langle\bar{\sigma},\bar{e}\rangle$ is a _Nash equilibrium_ of
$\langle\gamma,s_{0}\rangle$ if, for every player $q\in N$,
$\langle\sigma_{q},e_{q}\rangle$ is a best response to
$\langle\sigma_{p},e_{p}\rangle_{p\in N\setminus\\{q\\}}$ in
$\langle\gamma,s_{0}\rangle$.

There exist especially well-behaved Nash equilibria called _subgame perfect
equilibria._ In order to define them, we need the notion of an _$n$
-modification_ of a strategy $\sigma:E\to\mathbb{C}(E\times A)^{B}$.
Intuitively, an $n$-modification of $\sigma$ is a new strategy that coincides
with $\sigma$, except for the first $n$ turns of the game. Formally, we define
it as a strategy

$\displaystyle\sigma^{\prime}:E+[n]\to\mathbb{C}((E+[n])\times A)^{B}$

(where $[n]:=\\{0,\dots,n-1\\}$) that satisfies the following conditions:

$\displaystyle\sigma^{\prime}(e)$ $\displaystyle=\sigma(e)\,,$
$\displaystyle\quad\text{for }e\in E\,,$ $\displaystyle\sigma^{\prime}(k)$
$\displaystyle\in\mathbb{C}(\\{k+1\\}\times A)^{B}$
$\displaystyle\quad\text{for }k\in[n],\ k<n-1\,,$
$\displaystyle\sigma^{\prime}(k)$ $\displaystyle\in\mathbb{C}(E\times A)^{B}$
$\displaystyle\quad\text{for }k=n-1\,.$

We say that a Nash equilibrium $\langle\bar{\sigma},\bar{e}\rangle$ is
_subgame perfect_ if, for every $n\in\mathbb{N}$, all $n$-modifications
$\bar{\sigma}^{\prime}$ of $\bar{\sigma}$, and every player $q\in N$,
$\langle\sigma^{\prime}_{q},0\rangle$ is a best response to
$\langle\sigma^{\prime}_{p},0\rangle_{p\in N\setminus\\{q\\}}$ in
$\langle\gamma,s_{0}\rangle$, where we restrict the notion of a best response
only to consider strategies coinciding with the given one in the first $n$
turns.

######  Example 2.14.

Consider the Repeated Prisoner’s Dilemma introduced in Example 2.6. To define
the outcome of the game we use a discounted sum with discount factor
$\lambda<1$.

We take a look at two strategies: (i) a simple strategy $\sigma$ that always
denies and (ii) a ‘tit-for-tat’ strategy $\sigma^{\prime}$ which mirrors the
last move of the opponent. We can define these two strategies as follows. Both
strategies use no epistemic states $E_{p}:=\\{*\\}$ and as observations
$B_{p}:=\\{c,d\\}$ the last action of the opponent.

$\displaystyle\sigma(*)(x):=d\quad\text{and}\quad\sigma^{\prime}(*)(x):=x\,.$

The pair $\langle\sigma,\sigma\rangle$ of simple strategies is a Nash
equilibrium with outcome $\langle 0,0\rangle$, since every change of one
strategy results in a negative outcome for that player. The equilibrium is
subgame perfect, as both the strategies and the game do not depend on the
history of the play.

The pair $\langle\sigma^{\prime},\sigma^{\prime}\rangle$ of ‘tit-for-tat’
strategies is also a Nash equilibrium. Its outcome is $\langle
2/(1-\lambda),2/(1-\lambda)\rangle$. This time the equilibrium is not subgame
perfect. Consider the $1$-modification
$\langle\sigma^{\prime}_{c},\sigma^{\prime}_{d}\rangle$ of
$\langle\sigma^{\prime},\sigma^{\prime}\rangle$ where in the first turn,
player 1 plays $c$ while player 2 plays $d$. This leads to the play
$(c,d)(d,c)(c,d)(d,c)\dots$ with outcome $\frac{2-\lambda}{1-\lambda^{2}}$
(for the first player). If, instead of $\sigma^{\prime}_{d}$, the second
player chooses the strategy of always playing $d$, we obtain the play
$(c,d)(d,d)(d,d)(d,d)\dots$ with outcome $2$. Since $0<\lambda<1$, this is
larger than $\frac{2-\lambda}{1-\lambda^{2}}$.

###  2.9. Summary

Summing up the preceding sections, we have seen that we can specify a game by
the following data:

  * •

a set $N$ of _players,_

  * •

for each $p\in N$, a set $A_{p}$ of _actions_ for player $p$,

  * •

for each $p\in N$, a set $B_{p}$ of _observations_ for player $p$,

  * •

a set $S$ of _states_ of the game,

  * •

a set $R$ of _results,_

  * •

a set $O$ of _output values,_

  * •

a set $U$ of _outcomes,_

  * •

a function

$\displaystyle\gamma:S\to\mathbb{C}(R+S\times O)^{\prod_{p\in N}A_{p}}$

computing a single step of the game,

  * •

for each $p\in N$, a function

$\displaystyle\beta_{p}:O\times\prod_{p\in N}A_{p}\to B_{p}$

computing the observations of player $p$, and

  * •

two functions $\varrho:\Omega\to U$ and $\tau:\Gamma(U)\to U$ that satisfy

$\displaystyle\varrho=\tau\circ\Gamma(\varrho)\circ\omega$

and thus compute the outcome of a play.

##  3\. Examples

In this section we present the formulations of two basic games in our
framework. The first game is one with imperfect information as imperfect
monitoring. The second game is the one with incomplete information [23].

The usual approach in game theory is to reduce incomplete information to
imperfect one. Incomplete information denotes situations where the type of
agents is not known while imperfect information denotes situations where the
state of the game is not known. In our framework this differentiation is not
important since both kinds of information deficiencies are captured by
unobservable state spaces.

###  3.1. Imperfect Public Monitoring

The imperfect information game with imperfect monitoring and a noisy signal
considers games where the agents’ actions may not be directly observable. The
state of the game is driven by a probabilistic state transition and may be
either “good” or “bad”. This information is publicly observed by the agents,
i.e. all players observe the same signal. The payoff is a function of this
public outcome.

Again we have two players with two actions each: $N=\\{1,2\\}$ and
$A_{p}=\\{c,d\\}$. There are no results $R=\emptyset$ since the game never
ends. The output values are $O=\mathbb{R}\times\mathbb{R}\times Y$ with
$Y:=\\{G,B\\}$ that encode the payoffs in the stage games and the public
signal. The game has a single state $S=\\{*\\}$.

The game for the probabilistic functor
$\mathbb{C}_{\gamma}=\mathbb{C}_{\mathrm{prob}}$, is the function

$\displaystyle\gamma:S$ $\displaystyle\to\mathbb{C}_{\mathrm{prob}}(S\times
O)^{A_{1}\times A_{2}}$ $\displaystyle({*},a_{1},a_{2})$
$\displaystyle\mapsto({*},(r_{1},r_{2},y))$

where

$\displaystyle r_{p}$ $\displaystyle=\begin{cases}1+\frac{2-2k}{k-m}&\text{if
}(a_{p},y)=(c,G)\\\ 1-\frac{2k}{k-m}&\text{if }(a_{p},y)=(c,B)\\\
\frac{2-2n}{m-n}&\text{if }(a_{p},y)=(d,G)\\\ \frac{-2n}{m-n}&\text{if
}(a_{p},y)=(d,B)\\\ \end{cases}$ $\displaystyle y$
$\displaystyle=\begin{cases}G\text{ with probability }k&\text{if
}(a_{1},a_{2})=(c,c)\\\ G\text{ with probability }m&\text{if
}(a_{1},a_{2})=(c,d)\lor(a_{1},a_{2})=(d,c)\\\ G\text{ with probability
}n&\text{if }(a_{1},a_{2})=(d,d)\\\ B\text{ with probability }1-k&\text{if
}(a_{1},a_{2})=(c,c)\\\ B\text{ with probability }1-m&\text{if
}(a_{1},a_{2})=(c,d)\lor(a_{1},a_{2})=(d,c)\\\ B\text{ with probability
}1-n&\text{if }(a_{1},a_{2})=(d,d)\end{cases}$

The probabilities of the state transition are characterized by the parameters
$k>m>n$. The parameters are chosen so that the expected value of the payoffs
is given by the prisoner’s dilemma matrix:

$\displaystyle\begin{array}[]{|c|c|c|}\hline\cr&c&d\\\ \hline\cr
c&(1,1)&(-1,2)\\\ \hline\cr d&(2,-1)&(0,0)\\\ \hline\cr\end{array}$

The game has imperfect information so that the epistemic state of the players
is not the state of the game. Each player knows the history of his actions and
the history of the public signals

$\displaystyle E_{p}=(A_{p}\times Y)^{*}.$

The observation function is

$\displaystyle\beta_{p}:O\times A_{1}\times A_{2}$ $\displaystyle\to B_{p}$
$\displaystyle((r_{1},r_{2},y),a_{1},a_{2})$
$\displaystyle\mapsto(r_{p},y,a_{p}).$

We consider deterministic strategies with choice functor
$\mathbb{C}_{\sigma}=\mathbb{C}_{\mathrm{det}}$. An example of always
(unconditionally) playing $d$ for a player $p$ is given by

$\displaystyle\sigma_{1}:E_{1}$ $\displaystyle\to(E_{1}\times A_{1})^{B_{1}}$
$\displaystyle(h,(r_{1},y,a_{1}))$ $\displaystyle\mapsto(h(a_{1},y),d)$

where $h(a_{p},y)$ denotes that the history $h$ of the epistemic state is
extended by the action $a_{p}$ and the public signal $y$.

###  3.2. Incomplete Information

In a Bayesian game of incomplete information types of agents are not common
knowledge. In the simplest case we take types of agents to be represented as
different payoff functions of the game and each agent knows his own type but
not the one of his opponent.

In the following example we define that the game is played only once. However,
our framework is rich enough to easily extend the game to be played finitely,
infinitely or potentially infinitely often. The types of agents can be drawn
repeatedly or as in the following example only once. The agents can use
Bayesian updating or in fact any kind of a learning rule.

We define a Bayesian game of four $2\times 2$ games: Matching Pennies (MP),
Prisoner’s Dilemma (PD), Coordination Game (CG) and Battle of the Sexes (BS)
with equivalence classes $I_{i,j}$ for players $i$ and types $j$. Player 1, if
of type 1, knows that the payoff is either MP or PD and if of type 2, that the
payoff is either CG or BS. Player 2, if of type 1, knows that the payoff is
either MP or CG and if of type 2, that the payoff is either PD or BS. The
probabilities are given by $p_{MP}=0.3,p_{PD}=0.1,p_{CG}=0.2$ and
$p_{BS}=0.4$.

MP2,00,20,22,0$p=0.3$PD2,20,33,01,1$p=0.1$CG2,00,00,01,1$p=0.2$BS2,10,00,01,2$p=0.4$$I_{1,1}$$I_{1,2}$$I_{2,1}$$I_{2,2}$

The state space of the game is $S=\\{*,MP,PD,CG,BS\\}$. The output space of
the game is $O=S$ and the result space is $R=\mathbb{R}\times\mathbb{R}$. The
action spaces are $A_{1}=\\{U,D\\}$ and $A_{2}=\\{L,R\\}$ and the epistemic
state spaces have a single state $E_{1}=E_{2}=\\{*\\}$. We formalize this game
in two rounds.

  1. (1)

In the first round the game is in state $*$ and nature realizes the types of
the players, the actions of the players are irrelevant.

$\displaystyle\gamma:S$ $\displaystyle\to\mathbb{C}_{\mathrm{prob}}(R+S\times
O)^{A_{1}\times A_{2}}$ $\displaystyle{(*,a_{1},a_{2})}$
$\displaystyle\mapsto\begin{cases}(MP,MP)&\text{ with }p_{MP}=0.3\\\
(PD,PD)&\text{ with }p_{PD}=0.1\\\ (CG,CG)&\text{ with }p_{CG}=0.2\\\
(BS,BS)&\text{ with }p_{BS}=0.4\\\ \end{cases}$

In the second round the game yields a result.

$\displaystyle(MP,a_{1},a_{2})$ $\displaystyle\mapsto\begin{cases}(2,0)&\text{
if }a_{1}=U,a_{2}=L\\\ (0,2)&\text{ if }a_{1}=U,a_{2}=R\\\ (0,2)&\text{ if
}a_{1}=D,a_{2}=L\\\ (2,0)&\text{ if }a_{1}=D,a_{2}=R\\\ \end{cases}$

An analogous definition has to be given for the other type realizations
$PD,CG,BS$.

  2. (2)

The observation function of the first player is

$\displaystyle\beta_{1}:O\times A_{1}\times A_{2}$ $\displaystyle\to B_{1}$
$\displaystyle{(o,a_{1},a_{2})}$ $\displaystyle\mapsto\begin{cases}*&\text{ if
}o=*\\\ \\{MP,PD\\}&\text{ if }o=MP\lor o=PD\\\ \\{CG,BS\\}&\text{ if
}o=CG\lor o=BS\\\ \end{cases}$

The observation function of player 2 is defined analogously.

  3. (3)

The strategies for both players are given by

$\displaystyle\sigma_{p}:\\{*\\}$ $\displaystyle\to\mathbb{C}(\\{*\\}\times
A_{p})^{B_{p}}$

For example, the strategy of player 1 who plays $U$ if he is of type 1 and $D$
if he is of type 2 is given by

$\displaystyle(*,b_{1})$ $\displaystyle\mapsto\begin{cases}U\text{ if
}b_{1}=\\{MP,PD\\}\\\ D\text{ if }b_{1}=\\{CG,BS\\}\\\ \end{cases}$

In the first round when nature chooses the types, the strategy of the players
is irrelevant since it does not matter in the game function.

## References

  * [1] S. Abramsky and N. Tzevelekos.  Introduction to categories and categorical logic.  In Bob Coecke, editor, New Structures for Physics. Springer, Berlin, 2011.
  * [2] S. Abramsky and J. Zvesper.  From Lawvere to Brandenburger-Keisler: Interactive Forms of Diagonalization and Self-reference.  In Dirk Pattinson and Lutz Schröder, editors, CMCS, number 7399 in Lecture Notes in Computer Science, pages 1–19. Springer, 2012.
  * [3] Samson Abramsky and Viktor Winschel.  Coalgebraic analysis of subgame-perfect equilibria in infinite games without discounting.  arXiv:1210.4537, 2012.
  * [4] John C. Harsanyi.  Games with incomplete information played by ”Bayesian” players, i-III. part i. the basic model.  Management Science, 14(3):159–182, 1967.
  * [5] John C. Harsanyi.  Games with incomplete information played by ”Bayesian” players, i-III. part II. bayesian equilibrium points.  Management Science, 14(5):320–334, 1968.
  * [6] John C. Harsanyi.  Games with incomplete information played by ”Bayesian” players, i-III. part III. the basic probability distribution of the game.  Management Science, 14(7):486–502, 1968.
  * [7] Aviad Heifetz and Dov Samet.  Topology-free typology of beliefs.  Journal of Economic Theory, 82(2):324–341, 1998.
  * [8] F. Honsell, M. Lenisa, and R. Redamalla.  Conway games, algebraically and coalgebraically.  Logical Methods in Computer Science, 7(3:08):1–30, 2011.
  * [9] Bart Jacobs.  Introduction to Coalgebra. Towards Mathematics of States and Observations.  2012\.
  * [10] B. Klin.  Bialgebras for structural operational semantics: An introduction.  Theoretical Computer Science, 412(38):5043–5069, 2011.
  * [11] A. Kurz.  Coalgebras and their logics.  ACM SIGACT News, 37(2):57–77, 2006.
  * [12] F. William Lawvere.  Diagonal arguments and cartesian closed categories.  In Category Theory, Homology Theory and their Applications II, volume 92, pages 134–145. Springer Berlin Heidelberg, 1969.
  * [13] Pierre Lescanne and Matthieu Perrinel.  “Backward” coinduction, nash equilibrium and the rationality of escalation.  Acta Informatica, 49(3):117–137, 2012.
  * [14] Niklas Luhmann.  Die Gesellschaft der Gesellschaft.  Suhrkamp Verlag, 7th edition, 1998.
  * [15] Saunders Mac Lane.  Categories for the Working Mathematician.  Springer, 2nd edition, 1998.
  * [16] Jean-François Mertens and Shmuel Zamir.  Formulation of bayesian analysis for games with incomplete information.  International Journal of Game Theory, 14(1):1–29, 1985.
  * [17] L Moss and I Viglizzo.  Final coalgebras for functors on measurable spaces.  Information and Computation, 204(4):610–636, 2006.
  * [18] Lawrence S. Moss and Ignacio D. Viglizzo.  Harsanyi type spaces and final coalgebras constructed from satisfied theories.  Electronic Notes in Theoretical Computer Science, 106:279–295, 2004\.
  * [19] Dusko Pavlovic.  A semantical approach to equilibria and rationality.  In Alexander Kurz, Marina Lenisa, and Andrzej Tarlecki, editors, Algebra and Coalgebra in Computer Science, number 5728 in Lecture Notes in Computer Science, pages 317–334. Springer Berlin Heidelberg, 2009.
  * [20] Gordon Plotkin.  A structural approach to operational semantics.  The Journal of Logic and Algebraic Programming, 60–61(0):17–139, 2004.
  * [21] J. J. M. M. Rutten.  Universal coalgebra: a theory of systems.  Theoretical Computer Science, 249(1):3–80, 2000.
  * [22] D. A Schmidt.  Denotational Semantics: A Methodology for Language Development.  Allyn and Bacon, Inc., 1986.
  * [23] Yoav Shoham and Kevin Leyton-Brown.  Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations.  Cambridge University Press, 2008.
  * [24] Baltasar Trancon y Widemann and Michael Hauhs.  Distributive-law semantics for cellular automata and agent-based models.  In Proceedings of the 4th international conference on Algebra and coalgebra in computer science, pages 344–358. Springer Berlin Heidelberg, 2011.
  * [25] N. S Yanofsky.  A universal approach to self-referential paradoxes, incompleteness and fixed points.  Bulletin of Symbolic Logic, 9(3):362–386, 2003.