# Choice Structures in Games

Paolo Galeazzi and Johannes Marti

###### Abstract

Following the decision-theoretic approach to game theory, we extend the
analysis of [EW96] and [DT08] from hierarchies of preference relations to
hierarchies of choice functions. We then construct the universal choice
structure containing all these choice hierarchies, and show how the universal
preference structure from [DT08] is embedded in it.

##  1 Introduction

The present work focuses on the foundations of that part of the theory of
games that deals with the players’ interactive beliefs and subjective
preferences. We work here in the broadest setup, where the players’ beliefs
and preferences are expressed in terms of choice functions with no further
properties assumed. This generalizes the existing approaches in the
literature, where the players’ beliefs and preferences are represented by
probability and utility functions or by preference relations. We show that
even in our general setup it is possible to build a universal type structure -
which we call universal choice structure - containing all the coherent
hierarchies of choice functions. By being universal, we mean that such
structure is terminal, in the sense of category theory, and complete, in the
sense of [Bra03]. Furthermore, the universal choice structure is non-redundant
(in the sense of [MZ85]) and topology-free (in the sense of [HS98]). All these
notions are discussed in more detail in Section 5.

The motivation for the present work comes from the limitations imposed by
employing order relations to represent the players’ preferences, as already
recognized by [Eps97]. Generalizations of probabilistic type structures,
called preference structures, have been introduced in [EW96, DT08] and
[GHL16], where types are defined as hierarchies of interactive preference
relations rather than as hierarchies of interactive probabilistic beliefs.
However, not all important decision criteria are representable by order
relations and, consequently, preference structures are of no help to the study
of the behavioral implications when rationality is defined in terms of such
criteria. A famous example is regret minimization, which violates the
principle of independence of irrelevant alternatives and hence transitivity
too (see Section 1.2 below). As a consequence, regret-minimizing preferences
cannot be represented by order relations and have been axiomatized by means of
choice functions (see [Hay08] and [Sto11]).

The present paper aims to build the interactive epistemic structures required
to take into account cases of decision criteria like regret minimization,
where preference orders are insufficient to represent the players’
rationality. Such motivation justifies the shift from hierarchies of
interactive preference orders to hierarchies of interactive choice functions.

In addition to the conceptual motivation of this work, choice structures turn
out to be the most general models for interactive epistemology and epistemic
game theory introduced so far. As preference orders are special cases of
choice functions, the universal choice structure embeds the universal
preference structure, which in turn embeds the universal probabilistic type
structure.

On a more technical side, we prove the formal results of this paper using
notions from the theory of coalgebras and category theory. This allows for a
modular approach, which may also shed new light on the construction of both
the universal probabilistic type structure and the universal preference
structure.

The paper is structured as follows. The following two Subsections 1.1 and 1.2
survey the related literature and provide a motivational example for this
work, respectively. Section 2 introduces the setting and the preliminary
notions that are used in Section 3 to construct hierarchies of choice
functions and the universal choice structure. Section 4 shows how the
universal preference structure is embedded into the universal choice
structure, and Section 5 concludes.

###  1.1 Related literature

As already pointed out above, [EW96] generalize the notion of a type from a
hierarchy of probabilistic beliefs to a hierarchy of interactive preference
relations and introduce preference structures accordingly. [Che10] then proves
that any structure à la [EW96] can be embedded into their preference structure
by a morphism which is unique. Starting from different premises than [EW96],
[DT08] also constructs a preference structure which he shows to be universal
and non-redundant. In the same spirit as [EW96] and [DT08], [GHL16] show the
existence of the universal structure for a larger class of preferences than in
[EW96]. Our results are thus a further generalization from preference
structures to choice structures tout court, in order to be even more liberal
about the players’ rationality and decision criteria.

Other related work, more for the formal techniques employed than in the
spirit, is [Hei14]. There, the author provides the construction of a universal
type structure with unawareness by means of tools from category theory.
Different from our case, however, for his construction to succeed it suffices
to prove that his type structures with unawareness are coalgebras for an
appropriately defined functor, for which the results of [Hei14] directly
follow from those in [MV04, Vig05]. In our case, instead, a more extensive use
of category theory is necessary, as our choice structures are coalgebras for a
new different functor, whose categorical properties have not been investigated
yet.

This last observation also relates our results to the work by [MV04, Vig05],
in that they are the first to formulate classic probabilistic type structures
as coalgebras for the probability measure functor and to show that the
universal type structure is the terminal coalgebra in the category of
probabilistic type structures appropriately defined. We show here that the
terminal coalgebra also exists for choice structures.

###  1.2 A motivational example

Consider the following game, that Ida is playing as the row player and Joe as
the column player.

| $l$ | $r$
---|---|---
$u$ | 5;1 | 0;0
$m$ | 3;2 | 0;1
$c$ | 1;1 | 3;0
$d$ | 1;2 | 2;3

Ida has two dominated actions: $m$ and $d$. Specifically, the mixed action
$pu+(1-p)c$ strongly dominates $m$ for $p\in(1/2,1)$ and $d$ for
$p\in(0,1/3)$. Therefore, no probabilistic belief on Joe’s actions can justify
the choice of either $m$ or $d$ in terms of expected utility maximization: For
every probabilistic belief of Ida, either $u$ or $c$ will have higher expected
utility than $m$ as well as $d$. This is evident from Figure 1a, where the
horizontal axis represents the probability of Joe playing $r$ and the vertical
axis represents Ida’s expected utility.

-00$P(r)$-1-2-3$m$-4-5$u$-1--$d$-$c$-- (a)

--50$P(r)$--4$d$--3$c$--2$m$--1$u$-0-1----- (b)

Figure 1: On the left, the representation of Ida’s expected utilities
associated with the actions in the game above. On the right, the
representation of Ida’s expected negative regrets associated with the same
actions.

Actions that are consistent with the players’ rationality and common belief in
rationality are called rationalizable. In the example, the only action profile
that is rationalizable with expected utility maximization is $(u,l)$, since
action $r$ is no longer rational when $d$ is eliminated.

When, in the wake of decision-theoretic developments, classic probabilistic
beliefs are generalized to possibly non-probabilistic beliefs (e.g. [GS89,
Sch89]), the game-theoretic notions of rationality, dominance and equilibrium
have to be reconsidered accordingly. Examples of these advancements in game
theory can be found e.g. in [Kli96, Lo96, Mar00, KU05, RS10, HP12, BCVMM15,
Tro19]. For the sake of explanation, let us take the case where beliefs are
represented by sets of probability distributions as in the multiple-prior (MP,
henceforth) model of [GS89]. In this case, each action is associated with a
set of expected utilities, and a natural notion of rational choice consists in
picking an action with the highest minimal expected utility. When maxmin
expected utility is substituted for expected utility maximization as the
notion of rationality in the presence of non-probabilistic beliefs, a question
naturally arises: How is dominance defined in this setting?

An answer is offered by [Eps97], who establishes a correspondence between
iterated elimination of MP-dominated actions and MP-rationalizability. To
exemplify, consider again the game above between Ida and Joe, and suppose that
both players are expected utility maximinimizers: What are then the behavioral
implications of rationality and common belief in rationality? Figure 1a shows
that actions $u,c$ and $d$ are justifiable for Ida: $u$ and $c$ are still best
replies to some probabilistic belief, while $d$ is now a possible best reply
to some non-probabilistic belief, e.g., the set of probability distributions
that coincides with the simplex over Joe’s actions. The MP-rationalizable
action profiles are therefore the members of the Cartesian product
$\\{u,c,d\\}\times\\{l,r\\}$.

The results about MP-dominance and MP-rationalizability in [Eps97] are based
on preference structures, i.e., type structures whose elements consist in
hierarchies of interactive, reflexive and transitive preference relations over
Savage-style acts. The space of all coherent preference hierarchies, i.e., the
universal preference structure, is thus foundational to the results about
iterated dominance and rationalizability for decision criteria that are
representable by reflexive and transitive preference relations over acts, such
as maxmin expected utility and all other noteworthy criteria in [Eps97]. As
mentioned above, universal preference structures have been constructed by both
[EW96] and [DT08].

Once multiple decision criteria are introduced for single-agent problems, it
is also natural to think of situations where different individuals adhere to
different criteria in playing games. In such cases, we may have for instance
Ida playing the game and choosing actions according to criterion A, while Joe
is making his choices according to criterion B. Uncertainty about the
opponent’s criterion therefore enters the players’ epistemic state and spreads
to higher-order levels too: Ida may be uncertain about Joe’s criterion and
about Joe’s uncertainty relative to her criterion, and so on. Preference
structures provide a formal framework to express such interactive higher-order
uncertainty about the players’ decision criteria.

Consider the game above again, but now suppose that both Ida and Joe are
regret minimizers. Figure 1b helps picture the situation, where each action is
plotted in terms of its expected negative regret. Taking advantage of the fact
that the minimization of the maximal (positive) regret is equivalent to maxmin
negative regret, Figure 1b shows that action $m$ is now a possible best reply
(e.g., to the set of probability distributions coinciding with the simplex
over Joe’s actions), whereas action $d$ is no longer a best reply to any
possible belief of Ida. Joe would consequently not play action $r$, and the
only regret-rationalizable profile is thus $(u,l)$.

As already pointed out, however, regret minimization violates the independence
of irrelevant alternatives and is therefore not representable by a preference
relation. To see it, we can make use of the game above again. Suppose for
instance that Ida is a regret minimizer and her belief is represented by a
convex compact set of probability distributions assigning action $r$ a lower
probability of 0.25 and an upper probability of 1 (see Figure 2).

--50$P(r)$--4$d$--3$c$--2$m$--1$u$-0-1-----.25 (a)

--50$P(r)$--4--3--2$c$$d$--1$m$-0-1-----.25 (b)

Figure 2: On the left, the representation of Ida’s expected negative regrets
associated with the actions in the game above. On the right, the
representation of Ida’s expected negative regrets associated with the actions
in the game above, when action $u$ is no longer available.

For this specific belief, Ida is then indifferent between actions $u,m$ and
$c$, when she can choose among her four original actions (Figure 2a). However,
when action $u$ is no longer available, Ida will go for action $c$ (Figure
2b): actions $m$ and $c$ are no longer equivalent, in violation of the
independence of irrelevant alternatives. This choice pattern cannot be encoded
by a preference order, and a choice function $C$ such that

$\begin{array}[]{ccc}C(\\{u,m,c,d\\})=\\{u,m,c\\}&&C(\\{m,c,d\\})=\end{array}\\{c\\}$

has instead to be employed. These cases never arise for maxmin expected
utility, in that the relative order among possible alternatives does not
change when actions are added or removed. This is essentially the reason why
criteria such as maxmin expected utility can be axiomatized by preference
orders ([GS89]), while context-dependent criteria like regret minimization
require the use of choice functions ([Hay08] and [Sto11]). In interactive
contexts, this motivates the generalization from preference structures to
choice structures.

##  2 Preliminaries

In this section we introduce the mathematical notions that will be employed in
game-theoretic contexts in the following sections.

###  2.1 Uncertainty spaces

We are working with _uncertainty spaces_ , or simply _spaces_ ,
$(X,\mathcal{B})$, where $X$ is any set, whose elements are called _states_ ,
and $\mathcal{B}\subseteq\mathbb{P}X$ is an algebra of subsets of $X$, where
we denote by $\mathbb{P}X$ the powerset of $X$. The elements of $\mathcal{B}$
are called _measurable sets_ or _events_.111That $\mathcal{B}$ is an algebra
means that it is closed under finite intersections and complements. Thus, an
uncertainty space $(X,\mathcal{B})$ is almost a measurable space, but without
requiring closure under countable intersections. We often write just $X$ for
an uncertainty space $(X,\mathcal{B})$. Any set $X$ can be considered as a
trivial uncertainty space $(X,\mathcal{B})$ in which every subset is
measurable, meaning that $\mathcal{B}=\mathbb{P}X$ is the _discrete algebra_
containing all subsets of $X$.

A morphism $\varphi$ from an uncertainty space $X$ to an uncertainty space $Y$
is any function $\varphi:X\to Y$ that is _measurable_ , meaning that
$\varphi^{-1}[E]=\\{x\in X\mid\varphi(x)\in E\\}$ is measurable in $X$
whenever $E$ is measurable in $Y$. For every uncertainty space
$X=(X,\mathcal{B})$ we use $\mathsf{id}_{X}$ to denote the measurable identity
function on $X$, that is, $\mathsf{id}_{X}:X\to X,x\mapsto x$.

Two uncertainty spaces $X$ and $Y$ are _isomorphic_ , written as $X\simeq Y$,
if there is a bijective function $\varphi:X\to Y$ such that both $\varphi$ and
its inverse $\varphi^{-1}:Y\to X$ are measurable, and
$\varphi\circ\varphi^{-1}=\mathsf{id}_{Y}$ and
$\varphi^{-1}\circ\varphi=\mathsf{id}_{X}$.

Given two uncertainty spaces $X$ and $Y$ we can define their product to be the
uncertainty space $X\times Y$ whose states are all pairs $(x,y)$ where the
first component is a state in $X$ and the second component is a state in $Y$.
The measurable sets of states are generated by taking finite unions and
complements of cylinders, that is, sets of the form $U\times Y$ and $X\times
V$ for measurable $U$ in $X$ and $V$ measurable in $Y$. It is clear that with
this algebra the projections $\pi_{1}:X\times Y\to X,(x,y)\mapsto x$ and
$\pi_{2}:X\times Y\to Y,(x,y)\mapsto y$ are measurable functions. Moreover
given two measurable functions $\varphi:X\to X^{\prime}$ and $\psi:Y\to
Y^{\prime}$ we use $\varphi\times\psi:X\times Y\to X^{\prime}\times
Y^{\prime}$ to denote the measurable function, which is defined such that
$(\varphi\times\psi)(x,y)=(\varphi(x),\psi(y))$ for all $(x,y)\in X\times Y$.
It is not hard to check that this $\varphi\times\psi$ is indeed measurable.

###  2.2 Savage acts

Fix a non-empty set $Z$ of _outcomes_. A _Savage act_ , or just _act_ , for an
uncertainty space $X$ is a measurable finite step function $f:X\to Z$. That
$f$ is a finite step function means that its range $f[X]=\\{f(x)\in Z\mid x\in
X\\}$ is finite. We also assume that the set $Z$ carries the discrete algebra
in which all sets are measurable. Using that the measurable sets in $X$ are
closed under finite unions, one easily checks that a finite step function
$f:X\to Z$ is measurable precisely if $f^{-1}[\\{z\\}]$ is measurable for all
$z\in Z$. We write $FX$ for the set of all acts for some uncertainty space
$X$. For every measurable function $\varphi:X\to Y$ we obtain a function
$F\varphi:FY\to FX,f\mapsto f\circ\varphi$.

Our notion of a Savage act, where $Z$ is any set and $f:X\to Z$ is a finite
step function, is then compatible with the settings from both [DT08] and
[Sto11]. In the work on preference structures from [DT08], it is assumed that
$Z$ is finite and thus all acts are automatically finite step functions. In
the framework from [Sto11], acts are measurable finite step functions
$f:X\to\Delta\mathcal{Z}$, where $\Delta\mathcal{Z}$ is the set of all
probability distributions with finite support over a set $\mathcal{Z}$ of
outcomes. This approach can be recovered in our setting by instantiating the
set $Z$ with $\Delta\mathcal{Z}$.

In the following we are making the assumption that $Z$ is finite, following
[DT08]. However, our results on the existence of the universal choice
structure hold also for arbitrary, possibly infinite, sets $Z$. We address
this matter in more detail with Remark 3 in Section D.2 of the appendix.

###  2.3 Choice functions

A _choice function_ over a set $X$ is a function $C$ that maps every finite
subset $F\subseteq X$ to one of its subsets $C(F)\subseteq F$. For any set $X$
we write $\mathcal{C}X$ for the set of all choice functions over $X$. Even if
$X$ is just a set, without a notion of measurable subset, we take
$\mathcal{C}X$ to be the uncertainty space in which a set is measurable if it
can be generated by taking finite intersections and complements of sets of the
form

$B^{K}_{L}=\\{C\in\mathcal{C}X\mid C(K)\subseteq L\\},$

for some finite $K,L\subseteq X$ with $L\subseteq K$.

Given any function $f:X\to Y$ we define the function
$\mathcal{C}f:\mathcal{C}Y\to\mathcal{C}X$ by setting $\mathcal{C}f(C)=C^{f}$,
where $C^{f}$ is the choice function mapping a finite $K\subseteq X$ to

$C^{f}(K)=f^{-1}[C(f[K])]\cap K.$

We use $f[K]\subseteq Y$ to denote the direct image $f[K]=\\{f(x)\in Y\mid
x\in K\\}$ of $K$. One can show that the function
$\mathcal{C}f:\mathcal{C}Y\to\mathcal{C}X$ is measurable. To see this one
first checks that for all measurable sets of the form $B^{K}_{L}$ with
$K\subseteq L$

$\displaystyle(\mathcal{C}f)^{-1}[B^{K}_{L}]$
$\displaystyle=\\{C\in\mathcal{C}Y\mid f^{-1}[C(f[K])]\cap K\subseteq L\\}$
$\displaystyle=\\{C\in\mathcal{C}Y\mid
C(f[K])\subseteq\hat{L}\\}=B^{f[K]}_{\hat{L}},$

where $\hat{L}=\\{y\in f[K]\mid f^{-1}[\\{y\\}]\cap K\subseteq L\\}$. This
then extends to arbitrary measurable sets because intersections and
complements are preserved under taking inverse images.

###  2.4 Choice functions over Savage acts

We then consider choice functions over Savage acts for some uncertainty space
$X$. For every uncertainty space $X$ we define the uncertainty space $\Gamma
X=\mathcal{C}FX$ to be the uncertainty space of all choice functions over
Savage acts for $X$. Moreover, for every measurable function $\varphi:X\to Y$
we can define the measurable function
$\Gamma\varphi=\mathcal{C}F\varphi:\Gamma X\to\Gamma Y$. By unfolding the
definitions of $\mathcal{C}$ and $F$, we can describe the choice function
$\Gamma\varphi(C)=C^{\varphi}$ for any $C\in\Gamma X$ more concretely: It maps
a finite set of Savage acts $K\subseteq FY$ to the set

$C^{\varphi}(K)=\\{f\in K\mid f\circ\varphi\in C(\\{g\circ\varphi\mid g\in
K\\})\\}.$

##  3 Choice structures

In this section, the notions introduced above are applied to the game-
theoretic context that we are interested in. To keep things notationally
simple, we focus here on interactive situations with only two players, Ida and
Joe. It is straightforward to adapt our setting to more than two players, but
this would introduce additional notational complications.

###  3.1 Choice structures

As we are working with two-player games, the basic uncertainty of Ida is just
over the fixed finite set $A_{j}$ of Joe’s actions and, similarly, the basic
uncertainty of Joe is over the fixed finite set of Ida’s actions $A_{i}$. We
thus obtain the following definition of a choice structure:

######  Definition 1.

A _choice structure_ is a tuple
$\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$ consisting of:

  * •

uncertainty spaces $T_{i}$ and $T_{j}$ of _types_ for Ida and Joe, and

  * •

measurable functions $\theta_{i}:T_{i}\to\Gamma(A_{j}\times T_{j})$ and
$\theta_{j}:T_{j}\to\Gamma(A_{i}\times T_{i})$.

A _morphism_ $\alpha:\mathcal{X}\to\mathcal{X}^{\prime}$ from a choice
structure $\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$ to a choice
structure
$\mathcal{X}^{\prime}=(T^{\prime}_{i},T^{\prime}_{j},\theta^{\prime}_{i},\theta^{\prime}_{j})$
consists of two measurable functions $\alpha_{i}:T_{i}\to T^{\prime}_{i}$ and
$\alpha_{j}:T_{j}\to T^{\prime}_{j}$ such that

$\theta^{\prime}_{i}\circ\alpha_{i}=\Gamma(\mathsf{id}_{A_{j}}\times\alpha_{j})\circ\theta_{i}\text{
and
}\theta^{\prime}_{j}\circ\alpha_{j}=\Gamma(\mathsf{id}_{A_{i}}\times\alpha_{i})\circ\theta_{j}.$

A _state_ in $\mathcal{X}$ is a tuple $(a_{i},a_{j},t_{i},t_{j})\in
A_{i}\times A_{j}\times T_{i}\times T_{j}$. We also say that a _state of Ida_
is a pair $(a_{i},t_{i})\in A_{i}\times T_{i}$ and a _state of Joe_ is a pair
$(a_{j},t_{j})\in A_{j}\times T_{j}$. Notice that the actions specified by
Ida’s choice function $\theta_{i}(t_{i})$ at state $(a_{i},a_{j},t_{i},t_{j})$
may be completely unrelated to the action $a_{i}$ actually played by Ida at
that state (and likewise for Joe). In the example from Section 1, for
instance, it is possible that at a given state Ida’s type prescribes to choose
$u$, whereas Ida’s actual choice is $d$ (see Example 1 below for more
details). This is a feature that choice structures have in common with
preference structures. Without delving into interpretational issues, here we
just think of both choice hierarchies and preference hierarchies as expressing
choice attitudes or mental states rather than actual behavior. A state of a
player therefore consists of an action that she is actually playing and a type
that represents her mental attitude.222[BDV21] make a similar point in the
context of a different framework, where players have beliefs about their own
actions.

A _Savage act of Ida_ is then a map $f:A_{j}\times T_{j}\to Z$ from states of
Joe to outcomes, and similarly for Joe. We hence model the type of a player by
her choices between Savage acts, whose outcome depends on the state of the
other player, but not on her own state. This modelling assumes that the
players do not have uncertainty about their own type. This is different from
the setting of [DT08], who allows players to be uncertain about their own
type. We discuss this difference in modelling more extensively in Section 5.3.

######  Example 1.

We provide an example of a choice structure
$\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$ for the game from the
introduction. In this example Ida has a single type $T_{i}=\\{t_{i}\\}$, while
Joe has two possible types $T_{j}=\\{t_{Mm},t_{EU}\\}$. Here, we interpret
Ida’s type $t_{i}$ as a regret minimizer with belief represented as in Figure
2, i.e., a convex compact set of probability distributions assigning action
$r$ lower probability of 0.25 and upper probability of 1, while Joe’s type
$t_{Mm}$ is a maximinimizer with full uncertainty, i.e., not excluding any
probability distribution over Ida’s actions, and Joe’s type $t_{EU}$ is an
expected utility maximizer assigning probability $1/2$ to Ida playing $u$ and
$1/2$ to Ida playing $d$. The states of the choice structure are given by the
Cartesian set $A_{i}\times A_{j}\times T_{i}\times T_{j}$, i.e.,

$\\{u,m,c,d\\}\times\\{l,r\\}\times\\{t_{i}\\}\times\\{t_{Mm},t_{EU}\\}.$

Ida’s states are then members of the set $\\{u,m,c,d\\}\times\\{t_{i}\\}$ and
Joe’s states are members of the set $\\{l,r\\}\times\\{t_{Mm},t_{EU}\\}$. The
set of outcomes $Z$ is naturally given by the outcomes of the game,

$Z=\\{(5,1),(3,2),(1,1),(1,2),(0,0),(0,1),(3,0),(2,3)\\}.$

The map $\theta_{i}$ then associates each of Ida’s types with a choice
function over Savage acts defined on Joe’s states. In the running example,
such Savage acts are

$\begin{array}[]{ccccc}f_{u}(l,t)=(5,1)&&f_{u}(r,t)=(0,0)&&\text{for both
}t\in T_{j}\\\ f_{m}(l,t)=(3,2)&&f_{m}(r,t)=(0,1)&&\text{for both }t\in
T_{j}\\\ f_{c}(l,t)=(1,1)&&f_{c}(r,t)=(3,0)&&\text{for both }t\in T_{j}\\\
f_{d}(l,t)=(1,2)&&f_{d}(r,t)=(2,3)&&\text{for both }t\in T_{j}\end{array}$

Similarly, Joe’s Savage acts are the following:

$\begin{array}[]{ccc}f_{l}(u,t_{i})=(5,1)&&f_{r}(u,t_{i})=(0,0)\\\
f_{l}(m,t_{i})=(3,2)&&f_{r}(m,t_{i})=(0,1)\\\
f_{l}(c,t_{i})=(1,1)&&f_{r}(c,t_{i})=(3,0)\\\
f_{l}(d,t_{i})=(1,2)&&f_{r}(d,t_{i})=(2,3)\end{array}$

When Ida’s type $t_{i}$ is a regret minimizer as described above, the choice
function $C_{i}=\theta_{i}(t_{i})$ associated with $t_{i}$ maps subsets of the
set of Savage acts defined above as follows:

$\begin{array}[]{ccc}C_{i}(\\{f_{u},f_{m},f_{c},f_{d}\\})=\\{f_{u},f_{m},f_{c}\\}&&C_{i}(\\{f_{m},f_{d}\\})=\\{f_{d}\\}\\\
C_{i}(\\{f_{u},f_{m},f_{c}\\})=\\{f_{u},f_{m}\\}&&C_{i}(\\{f_{c},f_{d}\\})=\\{f_{c}\\}\\\
C_{i}(\\{f_{u},f_{m},f_{d}\\})=\\{f_{u},f_{m}\\}&&C_{i}(\\{f_{u},f_{m}\\})=\\{f_{u}\\}\\\
C_{i}(\\{f_{u},f_{c},f_{d}\\})=\\{f_{u}\\}&&C_{i}(\\{f_{u},f_{d}\\})=\\{f_{u}\\}\\\
C_{i}(\\{f_{m},f_{c},f_{d}\\})=\\{f_{c}\\}&&C_{i}(\\{f_{u},f_{c}\\})=\\{f_{u},f_{c}\\}\\\
C_{i}(\\{f_{m},f_{c}\\})=\\{f_{c}\\}\end{array}$

where we dispense with specifying the choice function in trivial cases such as
singletons. The definition of a choice structure would also require $C_{i}$ to
be defined on all other subsets of $F(A_{j}\times T_{j})$. For brevity we give
the definition of $C_{i}$ only on subsets of $\\{f_{u},f_{m},f_{c},f_{d}\\}$,
which are the Savage acts corresponding to actions in the game. As for Joe, we
have that type $t_{Mm}$ is associated with the choice function

$C_{Mm}(\\{f_{l},f_{r}\\})=\\{f_{l}\\}$

and type $t_{EU}$ with the choice function

$C_{EU}(\\{f_{l},f_{r}\\})=\\{f_{l},f_{r}\\}.$

Again, we omit the definition of the choice functions on sets of Savage acts
which do not correspond to actions in the game.

###  3.2 Choice hierarchies and the universal choice structure

We now introduce hierarchies of choice functions that represent the higher-
order attitudes of the players. To this aim we define uncertainty spaces
representing the players’ $n$-th order attitudes by a mutual induction on $i$
and $j$. In the base case we set $\Omega_{i,1}=\Gamma A_{j}$ and
$\Omega_{j,1}=\Gamma A_{i}$, and for the inductive step
$\Omega_{i,n+1}=\Gamma(A_{j}\times\Omega_{j,n})$ and
$\Omega_{j,n+1}=\Gamma(A_{i}\times\Omega_{i,n})$. The intuition is that the
players’ first order attitudes are represented by their choices between Savage
acts whose outcome depends just on the actual action played by the opponent.
Players’ $(n+1)$-th order attitudes are represented by their choices between
acts, whose outcome depends on the actual action played by the opponent and
the $n$-th order attitudes of the opponent.

Note that the players’ $(n+1)$-th order attitudes determine their $n$-th order
attitudes. At the first level this means that the agent’s choices in
$\Omega_{i,1}$ between Savage acts that depend on the opponent’s action are
the same as her choices between Savage acts in $\Omega_{i,2}$, when they are
taken as additionally depending trivially on the opponent’s first-order
attitudes. This can be made precise with a measurable _coherence morphism_
$\xi_{i,1}=\Gamma\pi_{1}:\Omega_{i,2}\to\Omega_{i,1}$, where
$\pi_{1}:A_{j}\times\Omega_{j,1}\to A_{j}$ is the projection onto the first
component. When $o_{2}\in\Omega_{i,2}$ represents Ida’s second-order attitudes
then $\xi_{i,1}(o_{2})\in\Omega_{i,1}$ represents her first-order attitudes.

Analogously, we define a coherence morphism for Joe, by setting
$\xi_{j,1}=\Gamma\pi_{1}:\Omega_{j,2}\to\Omega_{j,1}$, where
$\pi_{1}:A_{j}\times\Omega_{j,1}\to A_{j}$. From now on we will not bother
with writing every equation explicitly for Ida and Joe. We just write the
version for Ida and then write “and similarly for Joe”, thereby meaning that
the equation also holds with $i$ and $j$ interchanged.

By induction we can extend the idea of coherence to the higher levels. Choices
between acts depending on the opponent’s action and $n$-th order attitudes of
the opponent are determined by choices between the same acts taken as
depending on the opponent’s actions and their $(n+1)$-th order attitudes.
Hence, we define by mutual induction

$\xi_{i,n+1}=\Gamma(\mathsf{id}_{A_{j}}\times\xi_{j,n}):\Gamma(A_{j}\times\Omega_{j,n+1})\to\Gamma(A_{j}\times\Omega_{j,n})$

and similarly for Joe
$\xi_{j,n+1}=\Gamma(\mathsf{id}_{A_{i}}\times\xi_{i,n})$.

In the limit one can then consider countable sequences
$o=(o_{1},o_{2},\dots,o_{n},\dots)$ with $o_{n}\in\Omega_{i,n}$ for all
$n\in\mathbb{N}$. Moreover, we require these sequences to be coherent in the
sense that $\xi_{i,n}(o_{n+1})=o_{n}$ for all $n$. One such sequence
completely describes a coherent state of Ida’s higher-order attitudes at all
levels. Let $\Omega_{i}$ be the infinite set of all such coherent sequences.
There are projections $\zeta_{i,n}:\Omega_{i}\to\Omega_{i,n}$ for every level
$n\in\mathbb{N}$. The set $\Omega_{i}$ becomes an uncertainty space when
endowed with the algebra generated from all the subsets of the form
$(\zeta_{i,n})^{-1}[O_{n}]$ for $n\in\mathbb{N}$ and measurable
$O_{n}\subseteq\Omega_{i,n}$. All these notions can also be defined
analogously for Joe.

In the appendix we prove the central result about this construction, which is
that there exist the following isomorphisms:

######  Theorem 1.

$\Omega_{i}\simeq\Gamma(A_{j}\times\Omega_{j})$ and
$\Omega_{j}\simeq\Gamma(A_{i}\times\Omega_{i})$.

Using the isomorphisms $\mu_{i}:\Omega_{i}\to\Gamma(A_{j}\times\Omega_{j})$
and $\mu_{j}:\Omega_{j}\to\Gamma(A_{i}\times\Omega_{i})$ from Theorem 1, we
then define the universal choice structure:

######  Definition 2.

The _universal choice structure_
$\mathcal{U}=(\Omega_{i},\Omega_{j},\mu_{i},\mu_{j})$ consists of the
uncertainty spaces $\Omega_{i}$ and $\Omega_{j}$ of all coherent sequences of
choice attitudes, together with the measurable functions
$\mu_{i}:\Omega_{i}\to\Gamma(A_{j}\times\Omega_{j})$ and
$\mu_{j}:\Omega_{j}\to\Gamma(A_{i}\times\Omega_{i})$ from Theorem 1.

There is a technical difference between our presentation and the approach that
is usually taken in the literature, such as for instance [MZ85, BD93, EW96,
DT08]. It is common to define the $(n+1)$-th level $\Omega_{i,n+1}$ as
consisting of all pairs $(x,y)\in\Omega_{i,n}\times\Gamma\Omega_{j,n}$ that
are coherent in the sense that the attitudes represented by $x$ are consistent
with the attitudes represented by $y$, in a sense similar to our coherence
morphisms $\xi_{i,n}$. In the limit $\Omega_{i}$ one then considers sequences
$(o_{1},o_{2},\dots)\in\Omega_{i}$ such that $o_{n}\in\Gamma\Omega_{j,n}$ for
all $n\in\mathbb{N}$. Our approach is equivalent to this approach, once
coherence of the whole infinite sequences is taken into account.

###  3.3 Universality of the universal choice structure

Every type $t\in T_{i}$ in any choice structure
$\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$ generates a coherent
sequence of attitudes in $\Omega_{i}$. To see it, let us define first
$\upsilon_{i,1}=\Gamma\pi_{1}\circ\theta_{i}:T_{i}\rightarrow\Omega_{i,1},t\mapsto\Gamma\pi_{1}(\theta_{i}(t))$,
where $\pi_{1}:A_{j}\times T_{j}\to A_{j}$ is the projection. Similarly we
define $\upsilon_{j,1}:T_{j}\to\Omega_{j,1}$. We can then continue by mutual
induction and set

$\upsilon_{i,n+1}=\Gamma(\mathsf{id}_{A_{j}}\times\upsilon_{j,n})\circ\theta_{i}:T_{i}\to\Omega_{i,n+1}$
$t\mapsto\Gamma(\mathsf{id}_{A_{j}}\times\upsilon_{j,n})(\theta_{i}(t)).$

Similarly we define $\upsilon_{j,n+1}:T_{j}\to\Omega_{j,n+1}$.

One can easily verify that $\upsilon_{i,n}=\xi_{i,n}\circ\upsilon_{i,n+1}$ for
all $n$. Hence, for each $t\in T_{i}$ the infinite sequence
$(\upsilon_{i,1}(t),\upsilon_{i,2}(t),\dots)$ is coherent and we obtain a
measurable map $\upsilon_{i}:T_{i}\to\Omega_{i}$. Similarly we also obtain a
measurable map $\upsilon_{j}:T_{j}\to\Omega_{j}$. In the appendix we show that
$\upsilon_{i}$ and $\upsilon_{j}$ together define a unique morphism $\upsilon$
into the universal choice structure:

######  Theorem 2.

For every choice structure $\mathcal{X}$ there is a unique morphism of choice
structures $\upsilon:\mathcal{X}\to\mathcal{U}$ from $\mathcal{X}$ to the
universal choice structure $\mathcal{U}$.

###  3.4 Non-redundancy of the universal choice structure

We can also show that our universal choice structure is non-redundant. The
notion of non-redundancy goes back to [MZ85], who prove that their universal
type space has this property. Our definition of non-redundancy is an
adaptation of Definition 3 in [DT08].

For the definition of non-redundancy we consider situations in which we want
to endow the sets of types $T_{i}$ and $T_{j}$ in a choice structure
$\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$ with an algebra that is
possibly distinct from the algebra they have as type spaces in $\mathcal{X}$.
To this aim we need to clarify our notation. Recall that we write an
uncertainty space $X$ as $(X,\mathcal{B})$, where the symbol $X$ is used for
both the underlying set of points and the uncertainty space itself, including
the algebra $\mathcal{B}$. Given an algebra
$\mathcal{B}^{\prime}\subseteq\mathbb{P}X$, which might be distinct from
$\mathcal{B}$, we write $(X,\mathcal{B}^{\prime})$ for the uncertainty space
that has the set $X$ as its underlying set and the algebra
$\mathcal{B}^{\prime}$ as its algebra.

######  Definition 3.

Let $\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$ be some choice
structure. Define the _algebras of observable events_
$\mathcal{B}^{ob}_{\mathcal{X},i}\subseteq\mathbb{P}T_{i}$ and
$\mathcal{B}^{ob}_{\mathcal{X},j}\subseteq\mathbb{P}T_{j}$ to be the smallest
algebras such that $\mathcal{B}^{ob}_{\mathcal{X},i}$ contains the sets
$B^{ob}_{\mathcal{X},i}(K,L)$ for all finite $K,L\subseteq
F(A_{j}\times(T_{j},\mathcal{B}^{ob}_{\mathcal{X},j}))$ and
$\mathcal{B}^{ob}_{\mathcal{X},j}$ contains the sets
$B^{ob}_{\mathcal{X},j}(K,L)$ for all finite $K,L\subseteq
F(A_{i}\times(T_{i},\mathcal{B}^{ob}_{\mathcal{X},i}))$, where we write

$B^{ob}_{\mathcal{X},i}(K,L)=\\{t\in T_{i}\mid\theta_{i}(t)(K)\subseteq
L\\}\quad\mbox{and}\quad B^{ob}_{\mathcal{X},j}(K,L)=\\{t\in
T_{j}\mid\theta_{j}(t)(K)\subseteq L\\}.$

In Appendix D.4.1 we explain more carefully why these algebras of observable
events are well-defined.

######  Definition 4.

An algebra $\mathcal{B}\subseteq\mathbb{P}X$ on the set $X$ is _separating_ on
$X$ if for any $x,y\in X$ with $x\neq y$ there is a $E\in\mathcal{B}$ such
that $x\in E$ and $y\notin E$. The choice structure $\mathcal{X}$ is _non-
redundant_ if $\mathcal{B}^{ob}_{\mathcal{X},i}$ is separating on $T_{i}$ and
$\mathcal{B}^{ob}_{\mathcal{X},j}$ separating on $T_{j}$.

In the appendix we prove that a choice structure $\mathcal{X}$ is non-
redundant if and only if the unique morphism $\upsilon$ from $\mathcal{X}$ to
the universal choice structure $\mathcal{U}$ is injective in both components.
Proposition 2.5 in [MZ85], Proposition 2 in [Liu09] and Proposition 2 in
[DT08] contain analogous results for probabilistic type spaces and preference
structures.

######  Proposition 1.

A choice structure $\mathcal{X}$ is non-redundant if and only if both
components $\upsilon_{i}$ and $\upsilon_{j}$ of the unique morphism of choice
structures $\upsilon$ from $\mathcal{X}$ to the universal choice structure
$\mathcal{U}$ are injective.

Because the unique morphism from the universal choice structure $\mathcal{U}$
to itself has the identity function in both components, which is injective, it
follows immediately from Proposition 1 that $\mathcal{U}$ is non-redundant.

######  Corollary 1.

The universal choice structure $\mathcal{U}$ is non-redundant.

##  4 Embedding preference structures

In this section we discuss how our hierarchies of choice functions relate to
the hierarchies of preference relations introduced in [DT08].

###  4.1 Di Tillio’s preference structures

We start by reviewing the approach by [DT08] in our notation. The fundamental
notion of [DT08] is that of a preference relation over a set $X$. In the
following a _preference relation_ ${\preccurlyeq}$ over $X$ is a poset, that
is, a reflexive, transitive and anti-symmetric relation, over the set $X$. We
require preference relations to be anti-symmetric. This is different from
[DT08], who requires preference relations to be just preorders, that means
reflexive and transitive, but not necessarily anti-symmetric relations. We
justify this apparent loss of generality in Remark 1 below. In most of our
arguments anti-symmetry does not play a role and hence they also work for
preorders. Our reason to require anti-symmetry is that in the case of
preorders the embedding from preference relations into choice functions need
not be injective.

Write $\mathcal{P}X$ for the set of all preference relations over the set $X$.
The set $\mathcal{P}X$ can be turned into an uncertainty space by generating
the algebra of measurable events from sets of the form $B_{x_{1}\preccurlyeq
x_{2}}=\\{{\preccurlyeq}\in\mathcal{P}X\mid x_{1}\preccurlyeq x_{2}\\}$ for
some $x_{1},x_{2}\in X$.

Every function $f:X\to Y$ gives rise to the measurable function
$\mathcal{P}f:\mathcal{P}Y\to\mathcal{P}X$, where a preference relation
$\preccurlyeq$ over $Y$ maps to the preference relation
$\mathcal{P}f(\preccurlyeq)={\preccurlyeq}^{f}$ over $X$ that is defined by

$x_{1}\preccurlyeq^{f}x_{2}\qquad\mbox{iff}\qquad f(x_{1})\preccurlyeq
f(x_{2}).$ (1)

We can then redo all the constructions from Section 3 using $\mathcal{P}$
instead of $\mathcal{C}$. Let us sketch how this works. One considers
preference relations over acts by considering for every uncertainty space $X$
the space $\Pi X=\mathcal{P}FX$. For every measurable function $\varphi:X\to
Y$ we obtain the measurable function $\Pi\varphi=\mathcal{P}F\varphi:\Pi
X\to\Pi Y$ which maps a preference relation $\preccurlyeq$ over $FX$ to the
preference relation $\preccurlyeq^{\varphi}$ over $FY$ that is defined such
that $f\preccurlyeq^{\varphi}g$ if and only if $f\circ\varphi\preccurlyeq
g\circ\varphi$.

Lastly, define a _preference structure_ to be a tuple
$\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$ where
$\theta_{i}:T_{i}\to\Pi(A_{j}\times T_{j})$ and
$\theta_{j}:T_{j}\to\Pi(A_{i}\times T_{i})$ are measurable functions. A
_morphism_ $\alpha:\mathcal{X}\to\mathcal{X}^{\prime}$ from a preference
structure $\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$ to a preference
structure
$\mathcal{X}^{\prime}=(T^{\prime}_{i},T^{\prime}_{j},\theta^{\prime}_{i},\theta^{\prime}_{j})$
consists of two measurable functions $\alpha_{i}:T_{i}\to T^{\prime}_{i}$ and
$\alpha_{j}:T_{j}\to T^{\prime}_{j}$ such that

$\theta^{\prime}_{i}\circ\alpha_{i}=\Pi(\mathsf{id}_{A_{j}}\times\alpha_{j})\circ\theta_{i}\text{
and
}\theta^{\prime}_{j}\circ\alpha_{j}=\Pi(\mathsf{id}_{A_{i}}\times\alpha_{i})\circ\theta_{j}.$

Note that this definition of a preference structure differs from the one given
in [DT08] with respect to the assumption of introspection mentioned in Section
3.1.

The universal preference structure
$\mathcal{U}^{\prime}=(\Omega^{\prime}_{i},\Omega^{\prime}_{j},\mu^{\prime}_{i},\mu^{\prime}_{j})$
can be defined from the limits $\Omega^{\prime}_{i}$ and $\Omega^{\prime}_{j}$
of sequences $(\Omega^{\prime}_{i,n},\xi^{\prime}_{i,n})_{n\in\mathbb{N}}$ and
$(\Omega^{\prime}_{j,n},\xi^{\prime}_{j,n})_{n\in\mathbb{N}}$ analogous to
those that are used to approximate the universal choice structure in the
previous section. Hence, set $\Omega^{\prime}_{i,1}=\Pi A_{j}$,
$\Omega^{\prime}_{j,1}=\Pi A_{j}$ and then inductively
$\Omega^{\prime}_{i,n+1}=\Pi(A_{j}\times\Omega^{\prime}_{j,n})$ and
$\Omega^{\prime}_{j,n+1}=\Pi(A_{i}\times\Omega^{\prime}_{i,n})$. The coherence
morphism are such that $\xi^{\prime}_{i,1}=\Pi\pi_{1}$,
$\xi^{\prime}_{j,1}=\Pi\pi_{2}$ and inductively
$\xi^{\prime}_{i,n+1}=\Pi(\mathsf{id}_{A_{j}}\times\xi^{\prime}_{j,n})$ and
$\xi^{\prime}_{j,n+1}=\Pi(\mathsf{id}_{A_{i}}\times\xi^{\prime}_{i,n})$. The
existence of suitable $\mu^{\prime}_{i}$ and $\mu^{\prime}_{j}$ and
universality properties of $\mathcal{U}^{\prime}$ then follow from a
construction that is analogous to the one given in Appendix D, using $\Pi$ in
place of $\Gamma$. The properties of $\Pi$ that are required for this
construction to succeed are stated in Section 3 of [DT08].

###  4.2 Maximization

We use maximization to map preference orders to choice functions. Given a
finite set of alternatives, a player with a given preference relation chooses
the most preferred alternatives of the set. Formally, this means that given a
preference relation ${\preccurlyeq}\in\mathcal{P}X$ over a set $X$ we map it
to the choice function $m_{X}({\preccurlyeq})\in\mathcal{C}X$ that assigns to
a finite set $K\subseteq X$ the set $m_{X}({\preccurlyeq})(K)$ of its maximal
elements, which is defined as follows:

$m_{X}({\preccurlyeq})(K)=\\{m\in K\mid\mbox{there is no }k\in K\mbox{ with
}m\prec k\\},$

where $x\prec y$ is defined to hold if and only if $x\preccurlyeq y$ and not
$y\preccurlyeq x$. This definition yields a measurable function
$m_{X}:\mathcal{P}X\to\mathcal{C}X$ for every set $X$. To prove that it is
measurable it suffices to show that for every basic event
$B^{K}_{L}=\\{C\in\mathcal{C}X\mid C(K)\subseteq L\\}$ of $\mathcal{C}X$ its
preimage $m_{X}^{-1}[B^{K}_{L}]$ is measurable in $\mathcal{P}X$. To see that
this is the case first observe that the set of maximal elements of a set $K$
in a preference relation $\preccurlyeq$ is a subset of $L$ if and only if for
every element $k\in K\setminus L$ there is some $l\in L$ such that
$k\preccurlyeq l$ and not $l\preccurlyeq k$. Thus we can write

$m_{X}^{-1}[B^{K}_{L}]=\bigcap_{k\in K\setminus L}\bigcup_{l\in
L}\left(B_{k\preccurlyeq l}\setminus B_{l\preccurlyeq k}\right).$

Since $K$, $L$ and hence also $K\setminus L$ are finite the right side of the
above equality is a finite intersection of finite unions of intersections of
basic events with complements of basic events.

######  Remark 1.

With our definition of the choice function $m_{X}({\preccurlyeq})$ from the
preference relation $\preccurlyeq$ we do not lose any generality by
restricting to posets instead of preorders. For every preorder
${\preccurlyeq}$ we can define the poset $\preccurlyeq^{\prime}$ by setting
$x\preccurlyeq^{\prime}x^{\prime}$ iff $x=x^{\prime}$ or, $x\preccurlyeq
x^{\prime}$ and not $x^{\prime}\preccurlyeq x$. One can show that
$\preccurlyeq^{\prime}$ is anti-symmetric and that the maximal elements of any
finite set $K\subseteq X$ in $\preccurlyeq^{\prime}$ are the same as the
maximal elements of $K$ in $\preccurlyeq$, meaning that
$m_{X}({\preccurlyeq^{\prime}})(K)=m_{X}({\preccurlyeq})(K)$. It follows from
this that any choice function that arises from maximization in some preorder
also arises from maximization in some poset. Hence, the restriction to posets
does not lose any generality in the class of choice behaviors that we can
account for.

There are examples in which the preorders $\preccurlyeq$ and
$\preccurlyeq^{\prime}$ are distinct. For instance, we might take
$X=\\{x_{1},x_{2}\\}$ to be a two element set and $\preccurlyeq$ the total
relation, in which the two elements of $X$ are equally preferred, meaning that
$x_{1}\preccurlyeq x_{2}$ and $x_{2}\preccurlyeq x_{1}$. Applying the
definition of $\preccurlyeq^{\prime}$ from above shows that
$\preccurlyeq^{\prime}$ is then the poset in which $x_{1}$ and $x_{2}$ are
incomparable, meaning that neither $x_{1}\preccurlyeq^{\prime}x_{2}$ nor
$x_{2}\preccurlyeq^{\prime}x_{1}$. We have then that
$m_{X}({\preccurlyeq})(K)=K=m_{X}({\preccurlyeq^{\prime}})(K)$ for every
$K\subseteq X$. Hence, there exist two preorders that account for the same
choice behavior. We show in the following proposition that this redundancy
disappears if one restricts to posets.

The next proposition shows that any two distinct preference relations give
rise via maximization to distinct choice functions. We prove this proposition
in the appendix. It relies on our assumption that preference relations are
anti-symmetric.

######  Proposition 2.

The measurable function $m_{X}:\mathcal{P}X\to\mathcal{C}X$ is injective for
all sets $X$.

We can extend maximization to preference relations and choice functions over
acts by defining for every space $X$ the measurable function
$\lambda_{X}=m_{FX}:\Pi X\to\Gamma X$. A crucial property of $\lambda_{X}$ is
stated in the following proposition, which we prove in the appendix:

######  Proposition 3.

The mapping $\lambda_{X}$ is natural in $X$. This means that for every
measurable function $\varphi:X\to Y$ we have that
$\lambda_{Y}\circ\Pi\varphi=\Gamma\varphi\circ\lambda_{X}$.

###  4.3 Embedding preference structures into choice structures

We can use the mappings $\lambda_{X}$ to turn preference structures into
choice structures. For every preference structure
$\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$ define the choice structure
$\lambda({\mathcal{X}})=(T_{i},T_{j},\lambda_{A_{j}\times
T_{j}}\circ\theta_{i},\lambda_{A_{i}\times T_{i}}\circ\theta_{j})$. It is an
easy consequence of Proposition 3 that this embedding preserves morphisms in
the sense that whenever $\chi:\mathcal{X}\to\mathcal{X}^{\prime}$ is a
morphism of preference structures then the same pair of measurable functions
is also a morphism of choice structures
$\chi:\lambda({\mathcal{X}})\to\lambda({\mathcal{X}^{\prime}})$.

It is also possible to characterize the class of choice structures
$\lambda({\mathcal{X}})=(T_{i},T_{j},\lambda_{A_{j}\times
T_{j}}\circ\theta_{i},\lambda_{A_{i}\times T_{i}}\circ\theta_{j})$ arising
from some preference structure
$\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$. To this end, one can use
any of the axiomatizations of the class $\mathbb{P}$ of choice functions that
arise from the maximization in a poset. Such an axiomatization is given for
instance in Theorem 2.9 of [ABM07]. We then have that a choice structure
$\mathcal{X}^{\prime}=(T^{\prime}_{i},T^{\prime}_{j},\theta^{\prime}_{i},\theta^{\prime}_{j})$
is equal to $\lambda({\mathcal{X}})$ for some preference structure
$\mathcal{X}$ if and only if for all types $t_{i}\in T^{\prime}_{i}$ and
$t_{j}\in T^{\prime}_{j}$ the choice functions
$\theta^{\prime}_{i}(t_{i})\in\Gamma(A_{j}\times T^{\prime}_{j})$ and
$\theta^{\prime}_{j}(t_{j})\in\Gamma(A_{i}\times T^{\prime}_{i})$ are in
$\mathbb{P}$.

Because $\lambda_{X}$ is injective for every space $X$, it follows that
whenever $\lambda({\mathcal{X}})=\lambda({\mathcal{X}^{\prime}})$ for
preference structures $\mathcal{X}$ and $\mathcal{X}^{\prime}$ then
$\mathcal{X}=\mathcal{X}^{\prime}$. Therefore, any difference between
preference structures is preserved in choice structures. One can also define
an injective embedding of the universal preference structure into the
universal choice structure. Consider the unique morphism of choice structures
$\upsilon$ from $\lambda(\mathcal{U}^{\prime})$ to $\mathcal{U}$ that exists
by Theorem 2. This morphism consists of two measurable functions
$\upsilon_{i}:\Omega^{\prime}_{i}\to\Omega_{i}$ and
$\upsilon_{j}:\Omega^{\prime}_{j}\to\Omega_{j}$ for which we argue in the
appendix that it is injective if $A_{i}$ and $A_{j}$ are finite. Hence, we
obtain the following theorem:

######  Theorem 3.

The uncertainty spaces $\Omega^{\prime}_{i}$ and $\Omega^{\prime}_{j}$ of all
preference hierarchies are isomorphic to two subspaces of the spaces of all
choice hierarchies $\Omega_{i}$ and $\Omega_{j}$ respectively.

##  5 Discussion

###  5.1 Universality of the universal choice structure

The universal choice structure that is defined in this paper has all of the
properties that have been associated with the term “universality” in the
literature. It is terminal in the categorical sense, meaning that for every
choice structure there is a unique morphism to the universal one. It is
complete in the sense that the measurable functions $\mu_{i}$ and $\mu_{j}$ of
the universal choice structure are onto. The universal choice structure is
also non-redundant, as we discussed above. In particular, because we are
working in a category of coalgebras, completeness and non-redundancy follow
directly from terminality.

###  5.2 Topological assumptions and coherence

Our construction of the universal choice structure is based on hierarchies of
choice functions, where the levels in the hierarchies are linked by what we
call coherence morphisms. We use this terminology in analogy to the
construction of coherent probabilistic hierarchies by the use of
marginalization. However, our result is topology-free, in that we do not need
to impose topological assumptions on the spaces. This is different from the
classic probabilistic setting, where without additional topological
assumptions the universal structure can not be built from coherent hierarchies
of beliefs [HS98, HS99, Vig05]. Different from [HS98] and [HS99], the
construction of the universal structure directly from coherent choice
hierarchies in a topology-free setup succeeds in our case because, like in
[DT08], all the sets we deal with are endowed with an algebra, not a
$\sigma$-algebra, of subsets. We therefore do not incur in the same problem as
in [HS99], because the space of all the choice hierarchies is endowed with an
algebra, not a $\sigma$-algebra, of subsets and the extension of the coherent
choice hierarchies to such a space is thus unproblematic.

###  5.3 Introspection

An important difference between the definitions of type structure in the
literature is how they account for a player’s knowledge about her own type.
Similar to [EW96], we follow an approach in the spirit of [BD93], where a
player has no uncertainty about her own type. This treatment is different from
the one in [DT08], who allows for players to be uncertain about their own
type. We could use an analogous approach by considering choice structures
based on just one uncertainty space $X$, whose elements should be thought of
as the equivalent of the states from Section 3.1, and then define a choice
structure with measurable functions $\sigma:X\to A_{i}\times A_{j}$ and
$\vartheta:X\to\Gamma X\times\Gamma X$. The first component of
$\vartheta(x)=(\vartheta_{i}(x),\vartheta_{j}(x))$ specifies the type of Ida,
and the second the type of Joe. As for our proofs, this would mean that we
would consider coalgebras for the endofunctor in $\mathsf{Unc}$ that maps an
uncertainty space $X$ to the product $(A_{i}\times A_{j})\times(\Gamma
X\times\Gamma X)$, and with the obvious behavior on arrows.

To avoid confusion it should be mentioned that the approach of [DT08] is
different from the one by [MZ85], even though both settings use analogous
mathematical structures. The difference is that [MZ85] impose an introspection
condition that requires the players to be certain about their own type,
whereas [DT08] does not. As discussed in [Vig05, sec. 7.4], it is unclear how
this condition can be formulated in coalgebraic terms for the structures from
[MZ85] and [DT08].

###  5.4 The coalgebraic approach

For the technical proofs in the appendix we make extensive use of concepts
from coalgebra, which in turn uses notions from category theory such as the
base category, the coalgebraic functor, terminal objects and natural
transformations between functors. The coalgebraic approach provides us with a
modular language in which to describe the construction of the universal choice
structure. This comes with the following advantages: First, it is easier to
adapt the theory to a new representation of uncertainty. Because the general
construction of the terminal coalgebra is parametric in the functor, it
suffices to define the appropriate functor and check that it preserves limits
of suitable diagrams. Second, category theory provides an encompassing
language that can be used to compare properties between different kinds of
type structures, such as the concepts of completeness, non-redundancy and the
like. Third, the coalgebraic approach allows to abstract away from notational
complications such as for instance the indexing that is involved in
representing games with multiple players. When formulating the terminal-
sequence construction, the indexing is conveniently taken care of in the base
category and the coalgebraic functor.

###  5.5 Interpretation of the framework

A point deserving further investigation is the interpretation of both choice
hierarchies and preference hierarchies. As a strict behavioral interpretation
of such hierarchies seems to conflict with the specification of the players’
actual behavior at a state, for now we viewed hierarchies as choice attitudes
rather than choice behavior. Deeper analysis on this point is left to more
philosophical research in the future, while here we have been primarily
concerned with building the necessary technical apparatus introducing
hierarchies of choice functions in situations of interactive epistemology.

## References

  * [ABM07] Fuad Aleskerov, Denis Bouyssou, and Bernard Monjardet.  Utility Maximization, Choice and Preference.  Springer-Verlag, Berlin Heidelberg, 2007.
  * [Awo06] S. Awodey.  Category Theory.  Oxford University Press, 2006.
  * [BCVMM15] Pierpaolo Battigalli, Simone Cerreia-Vioglio, Fabio Maccheroni, and Massimo Marinacci.  Self-confirming equilibrium and model uncertainty.  American Economic Review, 105:2:646–677, 2015.
  * [BD93] A. Brandenburger and E. Dekel.  Hierarchies of beliefs and common knowledge.  Journal of Economic Theory, 59:189–198, 1993.
  * [BdRV02] Patrick Blackburn, Maarten de Rijke, and Yde Venema.  Modal Logic.  Cambridge University Press, 2002.
  * [BDV21] Pierpaolo Battigalli and Nicodemo De Vito.  Beliefs, plans, and perceived intentions in dynamic games.  Journal of Economic Theory, page 105283, 2021.
  * [Bra03] Adam Brandenburger.  On the existence of a ‘complete’ possibility structure.  Cognitive processes and economic behavior, pages 30–34, 2003.
  * [Che10] Yi-Chun Chen.  Universality of the Epstein–Wang type structure.  Games and Economic Behavior, 68(1):389–402, 2010.
  * [DT08] Alfredo Di Tillio.  Subjective expected utility in games.  Theoretical Economics, 3(3), 2008.
  * [Eps97] Larry Epstein.  Preference, rationalizability and equilibrium.  Journal of Economic Theory, 73(1):1–29, 1997.
  * [EW96] Larry Epstein and Tan Wang.  ”Beliefs about Beliefs” without Probabilities.  Econometrica, 64(6):1343–73, 1996.
  * [FHMV03] Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi.  Reasoning About Knowledge.  MIT Press, 2003.
  * [GHL16] Jayant Ganguli, Aviad Heifetz, and Byung Soo Lee.  Universal interactive preferences.  Journal of Economic Theory, 162:237–260, 2016.
  * [GS89] Itzhak Gilboa and David Schmeidler.  Maxmin Expected Utility with Non-unique Prior.  Journal of Mathematical Economics, 18:141–153, 1989.
  * [Hay08] Takashi Hayashi.  Regret aversion and opportunity dependence.  Journal of Economic Theory, 139(1):242–268, March 2008.
  * [Hei14] Sander Heinsalu.  Universal type structures with unawareness.  Games and Economic Behavior, 83:255–266, 2014.
  * [HP12] Joseph Y. Halpern and Rafael Pass.  Iterated Regret Minimization: a New Solution Concept.  Games and Economic Behavior, 74:1:194–207, 2012.
  * [HS98] A. Heifetz and D. Samet.  Knowledge spaces with arbitrarily high rank.  Games and Economic Behavior, 22:260–273, 1998.
  * [HS99] Aviad Heifetz and Dov Samet.  Coherent beliefs are not always types.  Journal of Mathematical Economics, 32(4):475–488, 1999.
  * [Jac16] Bart Jacobs.  Introduction to Coalgebra, volume 59 of Cambridge Tracts in Theoretical Computer Science.  Cambridge University Press, 2016.
  * [Kli96] Peter Klibanoff.  Uncertainty, decision, and normal form games, 1996.  Manuscript.
  * [KU05] Atsushi Kajii and Takashi Ui.  Incomplete Information Games with Multiple Priors.  The Japanese Economic Review, 56:332–351, 2005.
  * [Lan98] Saunders Mac Lane.  Categories for the Working Mathematician.  Springer, 1998.
  * [Liu09] Qingmin Liu.  On redundant types and Bayesian formulation of incomplete information.  Journal of Economic Theory, 144(5):2115–2145, 2009.
  * [Lo96] Kin Chung Lo.  Equilibrium in beliefs under uncertainty.  Journal of Economic Theory, 71(2):443 – 484, 1996.
  * [Mar00] Massimo Marinacci.  Ambiguous games.  Games and Economic Behavior, 31(2):191–219, 2000.
  * [MV04] 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\.
  * [MZ85] J. F. Mertens and S. Zamir.  Formulation of Bayesian analysis for games with incomplete information.  International Journal of Game Theory, 14:1–29, 1985.
  * [RS10] Ludovic Renou and Karl H. Schlag.  Minimax regret and strategic uncertainty.  Journal of Economic Theory, 145(1):264 – 286, 2010.
  * [Rut00] J.J.M.M. Rutten.  Universal coalgebra: A theory of systems.  Theoretical Computer Science, 249(1):3–80, 2000.
  * [Sch89] David Schmeidler.  Subjective Probability and Expected Utility Without Additivity.  Econometrica, 57:571–589, 1989.
  * [Sto11] Jörg Stoye.  Axioms for minimax regret choice correspondences.  Journal of Economic Theory, 146:2226–2251, 2011.
  * [Tro19] Michael Trost.  On the equivalence between iterated application of choice rules and common belief of applying these rules.  Games and Economic Behavior, 116:1–37, 2019.
  * [Vig05] Ignacio Darío Viglizzo.  Coalgebras on Measurable Spaces.  PhD thesis, Indiana University, 2005.
  * [Wor99] James Worrell.  Terminal sequences for accessible endofunctors.  Electronic Notes in Theoretical Computer Science, 19:24–38, 1999\.

##  Appendix A Overview of the appendix

This appendix contains the technical proofs about the constructions of the
universal choice structure from Section 3 and the embedding of the universal
preference structure into the universal choice structure from Section 4. We
view these constructions as instances of more general constructions from the
theory of coalgebras. Thereby, we follow the approach laid out in [MV04,
Vig05], who show how classical probabilistic type spaces can be seen as
coalgebras. The theory of coalgebras itself makes use of notions from category
theory. We review all relevant concepts from category theory in Section B of
this appendix. For the interested reader, more in-depth expositions of
category theory can be found in [Lan98] and [Awo06]. For a treatment of the
theory of coalgebras we refer to [Jac16] or the classic introduction [Rut00].

The cornerstones for the results in this appendix are as follows:

Choice structures as coalgebras: The first insight is that choice structures
are coalgebras and morphisms of choice structures are coalgebra morphisms. The
definition of a coalgebra is parametric in a fixed endofunctor $G$ on a
category $\mathcal{D}$. The category $\mathcal{D}$ is called the “base
category” and the functor $G$ is often called the “type functor”, but we call
it the “coalgebraic” functor in order to avoid confusion. We explain the
definition of a category and the notion of a functor in Sections B.1 and B.2.
Most relevant for us are the category $\mathsf{Unc}$ of uncertainty spaces and
measurable functions and the functor $\Gamma$ on $\mathsf{Unc}$, which we have
already implicitly defined in Section 2.4. However, for technical reasons
having to do with the fact that choice structures represent the uncertainty of
two players, instead of just one, we have to use $\mathsf{Unc}^{2}$ as our
base category, which essentially captures situations involving two uncertainty
spaces at once, instead of just one as in $\mathsf{Unc}$. One also has to work
with the functor ${\Gamma}^{\heartsuit}$, which is an adaptation of $\Gamma$
to $\mathsf{Unc}^{2}$ that captures the dependence of a player’s uncertainty
on the uncertainty of the other player.

Existence of the terminal coalgebra: The next observation is that the
universal choice structure corresponds to what is called the terminal
coalgebra in the theory of coalgebras. Our aim is then to use a general
coalgebraic construction to show the existence of the terminal coalgebra in
the category of choice structures. This construction, called the terminal
sequence construction and discussed in [Wor99], can be seen as a coalgebraic
counterpart of the construction of the universal type space from the space of
coherent hierarchies of beliefs. It can be performed in all categories of
coalgebras for a given functor and under certain rather mild conditions on the
coalgebraic functor it is guaranteed to yield the terminal coalgebra. There
are different versions of these sufficient conditions, but mostly they require
that the coalgebraic functor preserves the limits of certain diagrams in the
base category. We review the required notion of limits in Section B.5. In the
case of the functor ${\Gamma}^{\heartsuit}$, whose coalgebras are choice
structures, we can only show the preservation of a limit for a particular kind
of diagram, which we call epic countable cochains. In Section D we review the
terminal sequence construction to check that the preservation of limits for
epic countable cochains suffices for it to yield the terminal coalgebra.

Preservation of limits of countable epic cochains: To guarantee the existence
of the terminal coalgebra we then show in Section C.3 that the functor
${\Gamma}^{\heartsuit}$ preserves limits of epic countable cochains. It is
relatively easy to see that this reduces to showing that $\Gamma$ preserves
these limits. The functor $\Gamma$ can be seen as the composition of two
simpler functors, the functor $F$, which maps an uncertainty space $X$ to the
set $FX$ of all Savage acts over $X$, and the functor $\mathcal{C}$, which
maps a set $X$ to the uncertainty space $\mathcal{C}X$ of all choice functions
over $X$. We then show that both $F$ and $\mathcal{C}$ preserve suitable
limits such that their composition $\Gamma$ preserves limits of countable epic
cochains. For $F$ this is a relatively easy observation that is already
implicitly part of the proofs in [DT08]. That $\mathcal{C}$ preserves limits
of the right kind is Theorem 4, which is the central technical contribution of
this paper.

Embedding of preference structures: We also use the coalgebraic approach to
prove the results from Section 4 about the embedding of the universal
preference structure of [DT08] into the universal choice structure. The
setting of preference structures can also be reformulated in the coalgebraic
terminology simply by replacing the functor $\mathcal{C}$ mentioned above by a
functor $\mathcal{P}$ that captures preference relations. The embedding of
preference structures into choice structures then follows from the observation
that there is a natural transformation from $\mathcal{C}$ to $\mathcal{P}$
that is injective at all components. We discuss the notion of a natural
transformation in Section B.6. In Section E we explain how the existence of
such a natural transformation from $\mathcal{P}$ to $\mathcal{C}$ gives rise
to an embedding of the universal preference structure into the universal
choice structure.

##  Appendix B Preliminaries

We start by reviewing the basics from category theory and the theory of
coalgebras.

###  B.1 Categories

A _category_ $\mathcal{D}$ is a collection of objects, possibly a proper
class, together with a collection of morphisms, written as $f:X\to Y$, between
any two objects $X$ and $Y$ such that for every object $X$ in $\mathcal{D}$
there is an _identity_ morphism $\mathsf{id}_{X}:X\to X$ and for all objects
$X$, $Y$ and $Z$, and morphisms $f:X\to Y$ from $X$ to $Y$ and $g:Y\to Z$ from
$Y$ to $Z$ their _composition_ $g\circ f:X\to Z$ is a morphism in
$\mathcal{D}$ from $X$ to $Z$. The identities and compositions are required to
satisfy the identity law that $f\circ\mathsf{id}_{X}=f=\mathsf{id}_{Y}\circ f$
for all morphism $f:X\to Y$ and the associativity law that $(h\circ g)\circ
f=h\circ(g\circ f)$ for all $f:X\to Y$, $g:Y\to Z$ and $h:Z\to U$. For a
morphism $f:X\to Y$ in $\mathcal{D}$ we call the object $X$ the _domain_ of
$f$ and the object $Y$ the _codomain_ of $f$.

Examples of categories, which we use in this paper, are the category of sets
$\mathsf{Set}$, which has all the sets as its objects and functions between
them as morphisms, and the category of uncertainty spaces $\mathsf{Unc}$,
which has uncertainty spaces as objects and measurable functions as morphisms.
These clearly satisfy the identity and composition laws if one uses the
standard identity functions as identity morphisms and the standard
compositions of functions for the composition. A different kind of example is
the category $\mathsf{CS}$ of all choice structures as defined in Section 3
with morphisms of choice structures between them. The results of this paper
mostly concern the structure of this category $\mathsf{CS}$.

A more technical example of a category is $\mathsf{Unc}^{2}$, which has pairs
$X=(X_{0},X_{1})$ of uncertainty spaces $X_{0}$ and $X_{1}$ as objects and in
which the morphisms from $X=(X_{0},X_{1})$ to $Y=(Y_{0},Y_{1})$ are pairs of
measurable functions $\varphi=(\varphi_{0},\varphi_{1})$. One can check that
this is a category, when one gives the obvious component-wise definition of
identities and composition. We use the category $\mathsf{Unc}^{2}$ as a
convenient abstraction for the technical results of this appendix because it
concisely represents situations that concern the uncertainty of two players.
In an object $X=(X_{0},X_{1})$ of $\mathsf{Unc}^{2}$, the uncertainty space
$X_{0}$ represents the uncertainty of Ida, whereas $X_{1}$ represents the
uncertainty of Joe.

###  B.2 Functors

A _functor_ $G$ from a category $\mathcal{D}$ to a category $\mathcal{E}$ is
an assignment of an object $GX$ in $\mathcal{E}$ to every object $X$ of
$\mathcal{D}$ and an assignment of a morphism $Gf:GX\to GY$ in $\mathcal{E}$
to every morphism $f:X\to Y$ in $\mathcal{D}$ that preserves identities and
compositions, meaning that $G\mathsf{id}_{X}=\mathsf{id}_{GX}$ for all $X$ and
$G(g\circ f)=Gg\circ Gf$ for all $g$ and $f$. If $G$ is a functor from a
category $\mathcal{D}$ to the same category $\mathcal{D}$ one also calls $G$
an _endofunctor_.

A simple example of a functor is the powerset functor $\mathbb{P}$ from
$\mathsf{Set}$ to $\mathsf{Set}$. It maps a set $X$ to its powerset
$\mathbb{P}X$ and a function $f:X\to Y$ to the direct image map
$\mathbb{P}f:\mathbb{P}X\to\mathbb{P}Y$, which is defined such that
$\mathbb{P}f(U)=f[U]=\\{f(x)\in Y\mid x\in U\\}$ for all $U\subseteq X$. The
functor $\mathbb{P}$ is an endofunctor on the category of sets.

Another example of an endofunctor in $\mathsf{Set}$ is the finite distribution
functor $\mathbb{D}$. It maps a set $X$ to the set $\mathbb{D}X$ of all
probability distributions over $X$ that have finite support. A function
$f:X\to Y$ is mapped to the function $\mathbb{D}f:\mathbb{D}X\to\mathbb{D}Y$
which is such that $\mathbb{D}f(\mu)=\mu^{f}$ is the probability distribution
$\mu^{f}$ on $Y$ such that $\mu^{f}(V)=\sum_{x}\mu(x)$ for $x\in f^{-1}[V]$.

A _contravariant functor_ from $\mathcal{D}$ to $\mathcal{E}$ is a functor
from $\mathcal{D}$ to $\mathcal{E}^{\mathsf{op}}$, where
$\mathcal{E}^{\mathsf{op}}$ is just like $\mathcal{E}$, but the direction of
all morphisms is turned around. When $G$ is a contravariant functor from
$\mathcal{D}$ to $\mathcal{E}$, one usually just thinks of it as turning
morphisms around, in the sense that $Gf:GY\to GX$ for all $f:X\to Y$. If one
wants to emphasize that a functor $G$ from $\mathcal{D}$ to $\mathcal{E}$ is
not contravariant, one calls $G$ _covariant_.

An example of a contravariant functor from this paper is the mapping $F$
sending an uncertainty space $X$ to the set $FX$ of Savage acts for $X$ and a
measurable function $\varphi:X\to Y$ to the function $Ff:FY\to FX$. This is a
contravariant functor from the category of uncertainty spaces to the category
of sets.

Another example of a contravariant functor is the mapping $\mathcal{C}$ from
Section 2.3, which sends a set $X$ to the uncertainty space $\mathcal{C}X$ of
choice functions over that set and a function $f:X\to Y$ to the measurable
function $\mathcal{C}f:\mathcal{C}Y\to\mathcal{C}X$. This defines a
contravariant functor from the category of sets to the category of uncertainty
spaces. It is straightforward to check that it preserves identities. To see
that $\mathcal{C}$ preserves the composition of morphisms, one sees from the
definitions that this amounts to checking the following equality:

$f^{-1}[g^{-1}[C(g[f[K]])]]\cap K=f^{-1}[g^{-1}[C(f[g[K]])]\cap g[K]]\cap K,$

for all finite sets $K\subseteq Y$, and functions $f:X\to Y$ and $g:Y\to W$.

The mapping $\Gamma$ from Section 2.4 is a covariant endofunctor on the
category of uncertainty spaces that results from first applying the
contravariant functor $F$ from uncertainty spaces to sets and then the
contravariant functor $\mathcal{C}$ to get back to uncertainty spaces.
Formally, this means that $\Gamma$ maps an uncertainty space $X$ to the space
$\Gamma X=\mathcal{C}FX$ and a measurable function $\varphi:X\to Y$ to the
measurable function $\Gamma\varphi=\mathcal{C}F\varphi:\Gamma X\to\Gamma Y$.
Because the effects of the two contravariant functors $F$ and $\mathcal{C}$
cancel out, this means that $\Gamma$ is a covariant functor.

The mappings $\mathcal{P}$ and $\Pi$ from [DT08], which we survey in Section
4.1, can also be seen as functors analogous to $\mathcal{C}$ and $\Gamma$.
That is, $\mathcal{P}$ is a contravariant functor from $\mathsf{Set}$ to
$\mathsf{Unc}$ and $\Pi$ is the covariant endofunctor on $\mathsf{Unc}$ that
results from first applying the contravariant functor $F$ from $\mathsf{Unc}$
to $\mathsf{Set}$ and then the functor $\mathcal{P}$.

###  B.3 Coalgebras

We now explain how choice structures can be seen as an instance of the more
general notion of a coalgebra for an endofunctor in some category.

To define the notion of a coalgebra we need to fix a category $\mathcal{D}$
and an endofunctor $G$ on $\mathcal{D}$, that is, a functor $G$ from
$\mathcal{D}$ to $\mathcal{D}$. A _$G$ -coalgebra_ $(X,\xi)$ is an object $X$
of $\mathcal{D}$ together with a morphism $\xi:X\to GX$ in $\mathcal{D}$. The
class of all $G$-coalgebras can be turned into a category by taking as
morphisms from a $G$-coalgebra $(X,\xi)$ to a $G$-coalgebra $(Y,\upsilon)$ all
morphisms $f:X\to Y$ in the category $\mathcal{D}$ that satisfy the property
that $\upsilon\circ f=Gf\circ\xi$.

A relatively simple example of a category of coalgebras for the powerset
functor $\mathbb{P}$ in the category $\mathsf{Set}$. One can see that
$\mathbb{P}$-coalgebras are essentially the same as Kripke frames [FHMV03,
BdRV02]. For any Kripke frame $(W,R)$, with a set $W$ and relation $R\subseteq
W^{2}$, we can define a $\mathbb{P}$-coalgebra $(W,\alpha)$ where
$\alpha:W\to\mathbb{P}W$ is such that $\alpha(w)=R[\\{w\\}]=\\{v\in
W\mid(w,v)\in R\\}$ for all $w\in W$. Conversely, every $\mathbb{P}$-coalgebra
$(W,\alpha)$ also defines a Kripke frame $(W,R)$ such where $R=\\{(w,v)\mid
v\in\alpha(w)\\}$. One can also verify that the coalgebra morphisms between
$\mathbb{P}$-coalgebras correspond precisely to the morphisms between Kripke
frames.

Choice structures for fixed sets $A_{i}$ and $A_{j}$ of actions can be defined
as coalgebras for a particular functor ${\Gamma}^{\heartsuit}$ over the
category $\mathsf{Unc}^{2}$. The functor ${\Gamma}^{\heartsuit}$ maps an
object $(X_{0},X_{1})$ to the object $(\Gamma(A_{j}\times
X_{1}),\Gamma(A_{i}\times X_{0}))$. The change of indices in the components is
intentional, as it corresponds to encoding attitudes about the opponent’s
attitudes. For morphisms, the functor ${\Gamma}^{\heartsuit}$ sends a pair of
measurable functions $(\varphi_{0},\varphi_{1})$ from $(X_{0},X_{1})$ to
$(Y_{0},Y_{1})$ to the pair of measurable functions
$(\Gamma(\mathsf{id}_{A_{j}}\times\varphi_{1}),\Gamma(\mathsf{id}_{A_{i}}\times\varphi_{0}))$
from $(\Gamma(A_{j}\times X_{1}),\Gamma(A_{i}\times X_{0}))$ to
$(\Gamma(A_{j}\times Y_{1}),\Gamma(A_{i}\times Y_{0}))$.

We can view every choice structure
$\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$, defined according to
Definition 1, as a ${\Gamma}^{\heartsuit}$-coalgebra
$((T_{i},T_{j}),(\theta_{i},\theta_{j}))$ on the object $(T_{i},T_{j})$ of
$\mathsf{Unc}^{2}$ with the morphism
$(\theta_{i},\theta_{j}):(T_{i},T_{j})\to{\Gamma}^{\heartsuit}(T_{i},T_{j})$.
Conversely, every ${\Gamma}^{\heartsuit}$-coalgebra
$((X_{0},X_{1}),(\xi_{0},\xi_{1}))$ contains measurable functions
$\xi_{0}:X_{0}\to\Gamma(A_{j}\times X_{1})$ and
$\xi_{1}:X_{1}\to\Gamma(A_{i}\times X_{0})$ and thus gives rise to a choice
structure $(X_{0},X_{1},\xi_{0},\xi_{1})$. One can also check that the
morphisms of choice structures, as defined in Definition 1, correspond
precisely to the coalgebra morphisms between
${\Gamma}^{\heartsuit}$-coalgebras.

Analogous to choice structures, one can view preference structures as
coalgebras for a functor. To this aim one considers the functor
${\Pi}^{\heartsuit}$ from $\mathsf{Unc}^{2}$ to $\mathsf{Unc}^{2}$ that is
defined by replacing all occurrences of $\Gamma$ in the definition of
${\Gamma}^{\heartsuit}$ with $\Pi$. This means that ${\Pi}^{\heartsuit}$ sends
an object $(X_{0},X_{1})$ to $(\Gamma(A_{j}\times X_{1}),\Gamma(A_{i}\times
X_{0}))$ and a morphism $(\varphi_{0},\varphi_{1})$ to
$(\Pi(\mathsf{id}_{A_{j}}\times\varphi_{1}),\Pi(\mathsf{id}_{A_{i}}\times\varphi_{0}))$.

###  B.4 Isomorphisms and epic or monic morphisms

A morphism $f:X\to Y$ in a category $\mathcal{D}$ is an _isomorphism_ if there
exists a morphism $g:Y\to X$ such that $g\circ f=\mathsf{id}_{X}$ and $f\circ
g=\mathsf{id}_{Y}$. One writes $X\simeq Y$ in case there exists an isomorphism
$f:X\to Y$. One can check that in the category of sets the isomorphisms are
precisely the bijective functions and in the category $\mathsf{Unc}$ they are
the bijective measurable functions whose inverse is also measurable,
analogously to the homeomorphism between topological spaces. The isomorphisms
in $\mathsf{Unc}^{2}$ are those pairs $(\varphi_{0},\varphi_{1})$ of morphisms
such that both $\varphi_{0}$ and $\varphi_{1}$ are isomorphisms in
$\mathsf{Unc}$.

A morphism $f:X\to Y$ is _epic_ if for all further morphisms $g,h:Y\to T$ it
holds that if $g\circ f=h\circ f$ then already $g=h$. A morphism $f:X\to Y$ is
_monic_ if for all further morphisms $g,h:T\to X$ it holds that if $f\circ
g=f\circ h$ then already $g=h$. One can check that in the category of sets
epic morphisms are precisely the surjective functions and monic morphisms
precisely the injective functions. Similarly, in the category of uncertainty
spaces the epic and monic morphisms are the surjective and injective
measurable functions, respectively. Epic and monic morphisms in
$\mathsf{Unc}^{2}$ are epic and monic in both components. That is,
$(\varphi_{0},\varphi_{1})$ is epic if both $\varphi_{0}$ and $\varphi_{1}$
are epic, and analogously for monic.

A functor $F$ from $\mathcal{D}$ to $\mathcal{E}$ _preserves_ an epic morphism
$f$ of $\mathcal{D}$ if $Ff$ is epic in $\mathcal{E}$, and $F$ _preserves_ a
monic morphism $f$ if $Ff$ is monic. Note that, because an epic morphism in
$\mathcal{E}^{\mathsf{op}}$ is monic in $\mathcal{E}$, a contravariant functor
$F$ from $\mathcal{D}$ to $\mathcal{E}$ preserves an epic morphism $f$ if $Ff$
is monic in $\mathcal{E}$, and analogously for the preservation of monic
morphisms.

We show in Sections C.1 and C.2 that $\Gamma$ preserves all epic morphisms and
that it preserves all monic morphisms $\varphi:X\to Y$ for which $Y$ is a
discrete space.

###  B.5 Terminal objects, products and limits of chains

We make use of three different instances of the notion of a limit: terminal
objects, products and limits of chains. We define these three concepts
separately in the following, but to the interested reader it should be noted
that they are all instances of the more general concept of a limit for a
diagram, which is discussed in all of the texts on category theory cited
above.

A _terminal object_ in a category $\mathcal{D}$ is any object $\top$ with the
property that for every object $T$ of $\mathcal{D}$ there exists a unique
morphism $\mathord{!}_{T}:T\to\top$. It follows directly from this definition
that any two terminal objects in some category need to be isomorphic. To see
this assume that we have a second terminal object $\top^{\prime}$. Because
$\top^{\prime}$ is terminal we have the morphism
$\mathord{!}^{\prime}_{\top}:\top\to\top^{\prime}$. Because $\top$ is
universal there is the morphism
$\mathord{!}_{\top^{\prime}}:\top^{\prime}\to\top$. We have that
$\mathsf{id}_{\top}=\mathord{!}_{\top}=\mathord{!}_{\top^{\prime}}\circ\mathord{!}^{\prime}_{\top}$
because $\mathord{!}_{\top}$ is the unique morphism from $\top$ to $\top$. A
similar argument shows that
$\mathsf{id}_{\top^{\prime}}=\mathord{!}^{\prime}_{\top}\circ\mathord{!}_{\top^{\prime}}$.
As a consequence one can assume that if a category has a terminal object then
it is unique, at least if one only cares about the identity of objects up-to
isomorphism.

The terminal object in the category $\mathsf{Unc}$ can be defined as the
uncertainty space $\top=(\\{\star\\},\\{\emptyset,\\{\star\\}\\})$ which
contains just one point. The terminal object in the category
$\mathsf{Unc}^{2}$ can be defined componentwise as the object $(\top,\top)$
where $\top$ is the terminal object of $\mathsf{Unc}$. A more interesting
example of a terminal object is the universal choice structure. The
universality property from Theorem 2 expresses precisely that the universal
choice structure is the terminal object in the category of choice structures.

Given two objects $X$ and $Y$ of a category $\mathcal{D}$, a _product_ of $X$
and $Y$ is an object of $\mathcal{D}$, written as $X\times Y$, together with
two morphisms $\pi_{1}:X\times Y\to X$ and $\pi_{2}:X\times Y\to Y$, which
have the following universal property: For every object $T$ and morphisms
$f:T\to X$ and $g:T\to Y$ there is a morphism $u:T\to X\times Y$, often
written as $(f,g)$, that is unique for having the property that
$f=\pi_{1}\circ u$ and $g=\pi_{2}\circ u$.

Similar as for terminal objects, one can see that any two objects with this
universal property, relative to fixed $X$ and $Y$, need to be isomorphic.
Hence, one often speaks of the product of $X$ and $Y$ as if it was unique.

In the category $\mathsf{Unc}$ one can define the product $X\times Y$ of two
uncertainty spaces $X$ and $Y$ to be an uncertainty space whose states are all
pairs $(x,y)$, where $x$ is a state of $X$ and $y$ is a state of $Y$. The
measurable sets of states are generated by taking finite unions and
complements of cylinders, that is, sets of the form $U\times Y$ and $X\times
V$ for measurable $U$ in $X$ and $V$ measurable in $Y$. It is clear that with
this algebra the projections $\pi_{1}:X\times Y\to X,(x,y)\mapsto x$ and
$\pi_{2}:X\times Y\to Y,(x,y)\mapsto y$ are measurable functions. Moreover,
one can check that this definition of the product has the universal property
that for each space $T$ together with measurable functions $\varphi:T\to X$
and $\psi:T\to Y$ there is a unique measurable function $\mu:T\to X\times
Y,t\mapsto(\varphi(t),\psi(t))$ such that $\varphi=\pi_{1}\circ\mu$ and
$\psi=\pi_{2}\circ\mu$.

We need a further piece of notation related to the product: Given $f:X\to Z$
and $g:Y\to U$ we write $f\times g:X\times Y\to Z\times U$ for the morphism
$f\times g=(f\circ\pi_{1},g\circ\pi_{2})$. It is easy to check that this
definition generalizes our earlier definition of $\varphi\times\psi$ for
measurable functions $\varphi$ and $\psi$ from Section 2.1.

A crucial categorical notion for the construction of the universal choice
structure is that of the limit of a countable cochain. A _countable cochain_
$(X_{n},f_{n})_{n\in\omega}$ in a category $\mathcal{D}$ consists of an object
$X_{n}$ of $\mathcal{D}$ for every natural number $n\in\omega$ and a morphism
$f_{n}:X_{n+1}\to X_{n}$ for every $n\in\omega$. Here, and in the following we
use $\omega$ to denote the set of all natural numbers including $0$. The
$f_{n}$ are also called the _coherence morphism_ of the cochain.

It is clear that we can compose the morphisms $f_{n}$ to obtain a morphisms
$f^{m}_{n}=f_{n}\circ\dots\circ f_{m-1}:X_{m}\to X_{n}$ for all $n,m\in\omega$
with $n\leq m$, where $f^{n}_{n}=\mathsf{id}_{X_{n}}:X_{n}\to X_{n}$ is just
the identity on $X_{n}$. We call the countable cochain
$(X_{n},f_{n})_{n\in\omega}$ _epic_ , if all the morphisms $f_{n}$ are epic.

A _limit_ of the countable cochain $(X_{n},f_{n})_{n\in\omega}$ is an object
$X_{\omega}$ together with projection morphisms $p_{n}:X_{\omega}\to X_{n}$
such that $p_{n}=f_{n}\circ p_{n+1}$ for all $n\in\omega$ which satisfies the
following universal property: For every object $T$ together with morphisms
$g_{n}:T\to X_{n}$, satisfying $g_{n}=f_{n}\circ g_{n+1}$ for all
$n\in\omega$, there is a morphism $u:T\to X_{\omega}$ that is unique for
having the property that $g_{n}=p_{n}\circ u$ for all $n\in\omega$. As for the
product and the terminal object, one can show with this universal property
that any two limits of a given cochain are isomorphic.

For every cochain $(X_{n},\xi_{n})_{n\in\omega}$ in the category
$\mathsf{Unc}$ we can define its limit $X_{\omega}$ to be the uncertainty
space that has as its states all sequences
$x=(x_{0},x_{1},\dots,x_{n},\dots)$, where $x_{n}$ is a state from $X_{n}$ for
all $n\in\omega$, which are coherent in the sense that
$x_{n}=\xi_{n}(x_{n+1})$ for all $n\in\omega$. We can then consider the
projections $\zeta_{n}:X_{\omega}\to X_{n},x\mapsto x_{n}$ for each
$n\in\omega$. The measurable sets of the limit $X_{\omega}$ are defined to be
all sets of the form $\zeta_{n}^{-1}[E]$ for some $n\in\omega$ and measurable
set $E$ of $X_{n}$. It is clear that this definition turns the projections
$\zeta_{n}:X_{\omega}\to X_{n}$ into measurable functions. Moreover, using
that all $\xi_{n}$ are measurable, one can show that the measurable sets
defined in this way are closed under finite unions and intersections. To check
that this definition of the limit has the universal property observe that for
any measurable space $T$ with measurable functions $\varphi_{n}:T\to X_{n}$,
such that $\varphi_{n}=\xi_{n}\circ\varphi_{n+1}$ for each $n\in\omega$, we
can define the unique morphism $\mu:T\to X_{\omega}$ such that
$\mu(t)=(\varphi_{0}(t),\varphi_{1}(t),\dots,\varphi_{n}(t),\dots)$ for all
$t\in T$.

One can also define the limit for every cochain
$((X_{0,n},X_{1,n}),(\xi_{0,n},\xi_{1,n}))_{n\in\omega}$ in
$\mathsf{Unc}^{2}$. This can be done componentwise, meaning that for each of
the components of the pairs representing objects and morphisms in
$\mathsf{Unc}^{2}$ we can just use the construction for $\mathsf{Unc}$,
described in the previous paragraph. For instance the limit itself is just the
object $(X_{0,\omega},X_{1,\omega})$ such that $X_{0,\omega}$ and
$X_{1,\omega}$ are the limits of $(X_{0,n},\xi_{0,n})_{n\in\omega}$ and
$(X_{1,n},\xi_{1,n})_{n\in\omega}$ in $\mathsf{Unc}$. It is not hard to see
that this again has the required universal property.

A functor $G$ from $\mathcal{D}$ to $\mathcal{E}$ _preserves_ a limit
$X_{\omega}$ of a countable cochain $(X_{n},f_{n})_{n\in\omega}$ if
$GX_{\omega}$ is the limit for the countable cochain
$(GX_{n},Gf_{n})_{n\in\omega}$. The main technical result in this appendix is
that the functor $\Gamma$ preserves limits of countable epic cochains. In the
proof of this claim in Section C.3 we investigate the preservation of limits
of cochains under the contravariant functors $F$ from $\mathsf{Unc}$ to
$\mathsf{Set}$ and $\mathcal{C}$ from $\mathsf{Set}$ to $\mathsf{Unc}$. For
this purpose we need to understand limits of cochains in
$\mathsf{Set}^{\mathsf{op}}$. Because morphisms in
$\mathsf{Set}^{\mathsf{op}}$ are just morphisms from $\mathsf{Set}$ with
swapped domain and codomain we have that a countable cochain
$(X_{n},f_{n})_{n\in\omega}$ in $\mathsf{Set}^{\mathsf{op}}$ is just what is
called a countable chain in $\mathsf{Set}$, meaning that the $X_{n}$ are all
sets and the $f_{n}:X_{n}\to X_{n+1}$ are functions that now go from $X_{n}$
to $X_{n+1}$. Moreover the limit $X_{\omega}$ of this cochain in
$\mathsf{Set}^{\mathsf{op}}$ is what is actually called a colimit of chain in
$\mathsf{Set}$. The colimit $X_{\omega}$ of a chain
$(X_{n},f_{n})_{n\in\omega}$ in $\mathsf{Set}$ can be described concretely as
the disjoint union of all the $X_{n}$ modulo the equivalence relation that
identifies an $x_{n}$ from $X_{n}$ with an $x_{m}$ from $X_{m}$ if there is
some $k\geq n,m$ such that $f^{n}_{k}(x_{n})=f^{m}_{k}(x_{m})$. Clearly, we
can then define inclusions $p^{n}_{\omega}:X_{n}\to X_{\omega}$ for all
$n\in\omega$. The universal property of this colimit is just the same as the
universal property of limit in $\mathsf{Set}^{\mathsf{op}}$ with all morphisms
turned around: For every set $T$ with functions $h_{n}:X_{n}\to T$ such that
$h_{n}=h_{n+1}\circ f_{n}$ for each $n\in\omega$, there is a unique function
$u:X_{\omega}\to T$ such that $h_{n}=u\circ p^{n}_{\omega}$ for all
$n\in\omega$.

###  B.6 Natural transformations

Let $F$ and $G$ be functors that both go from a category $\mathcal{D}$ to a
category $\mathcal{E}$. Then a _natural transformation_ $\eta$ from $F$ to $G$
is an assignment of a morphism $\eta_{X}:FX\to GX$ in $\mathcal{E}$ to every
object $X$ in $\mathcal{D}$ such that for all morphisms $f:X\to Y$ in
$\mathcal{D}$ it holds that $Gf\circ\eta_{X}=\eta_{Y}\circ Ff$, where
$\eta_{Y}$ is the morphism that $\eta$ assigns to the object $Y$.

An example of a natural transformation from the discrete distribution functor
to the powerset functor is mapping a finite distribution to its support set.
More formally, we have for every set $X$ a function
$\mathsf{supp}_{X}:\mathbb{D}X\to\mathbb{P}X$ that maps a discrete
distribution $\mu$ over $X$ to the support set $\mathsf{supp}_{X}(\mu)$ of
$\mu$. The naturality condition that
$\mathbb{P}f\circ\mathsf{supp}_{X}=\mathsf{supp}_{Y}\circ\mathbb{D}f$ for all
functions $f:X\to Y$ amounts to the fact that for every discrete distribution
$\mu$ over $X$ there is some $x\in X$ with $f(x)=y$ and $\mu(x)\neq 0$ if and
only if $\mu^{f}(y)\neq 0$, where $\mu^{f}=\mathbb{D}f(\mu)$.

An example of natural transformation from this paper is the measurable
function $\lambda_{X}:\Pi X\to\Gamma X$ that is defined for every uncertainty
space $X$. Proposition 3, which is proven in Section E.3, shows that $\lambda$
is a natural transformation from the functor $\Pi$ to the functor $\Gamma$.

##  Appendix C Properties of $\Gamma$

In this part of the appendix we prove crucial properties of the functor
$\Gamma$ which are needed for the coalgebraic construction of the universal
choice structure. In case the reader tries to get an overview of the
construction of the universal choice structure, they might skip this section
and then refer back as needed when reading Sections D and E.

###  C.1 $\Gamma$ preserves epic morphisms

We show that $\Gamma$ preserves epic morphisms, which in $\mathsf{Unc}$ are
just surjective measurable functions. Because $\Gamma$ is the composition of
$F$ and $\mathcal{C}$ it suffices to show that $F$ maps surjective measurable
functions to injective functions in $\mathsf{Set}$ and that $\mathcal{C}$ maps
injective functions to surjective measurable functions. It is easy to check
the former using the definition of $F$ and the cancellation property of epic
morphism. That $\mathcal{C}$ maps injective functions to surjective measurable
functions is shown in the following lemma:

######  Lemma 1.

If $f:X\to Y$ is injective then $\mathcal{C}f:\mathcal{C}Y\to\mathcal{C}X$ is
surjective.

###### Proof.

It is easy to see that as $f$ is injective then $f^{-1}[f[U]]=U$ holds for all
$U\subseteq X$. To check that $\mathcal{C}f$ is surjective consider any
$C\in\mathcal{C}X$. We have to find a $C^{\prime}\in\mathcal{C}Y$ such that
$\mathcal{C}f(C^{\prime})=C$. Define $C^{\prime}$ such that
$C^{\prime}(K)=f[C(f^{-1}[K])]$ for all finite $K\subseteq Y$. The following
equality then follows for all $L\subseteq X$:

$\displaystyle\mathcal{C}f(C^{\prime})(L)$
$\displaystyle=f^{-1}[C^{\prime}(f[L])]\cap L$
$\displaystyle=f^{-1}[f[C(f^{-1}[f[L]])]]\cap L$ $\displaystyle=C(L)\cap
L=C(L).$

∎

###  C.2 $\Gamma$ preserves monic morphisms to discrete spaces

We show that $\Gamma$ preserves monic morphisms, if the codomain has the
discrete algebra. We again split the problem into two steps. First we show
that $F$ maps every surjective measurable function with a discrete codomain to
an injective functions and then we show that $\mathcal{C}$ maps injective
functions to surjective measurable functions.

######  Lemma 2.

If the measurable function $\varphi:X\to Y$ is injective and $Y$ has the
discrete algebra then the function $F\varphi:FY\to FX$ is surjective.

###### Proof.

Pick any $f\in FX$. We want to find a $f^{\prime}\in FY$ such that
$f=f^{\prime}\circ\varphi$. We define $f^{\prime}(y)=f(x)$, if there is some
$x\in X$ such that $\varphi(x)=y$, and $f^{\prime}(y)=z^{\prime}$ for an
arbitrary $z^{\prime}\in Z$ otherwise. This is well-defined because $\varphi$
is injective. The function $f^{\prime}$ is trivially measurable because $Y$
has the discrete algebra and $f=f^{\prime}\circ\varphi$ by definition of
$f^{\prime}$. ∎

######  Lemma 3.

If $f:X\to Y$ is surjective then $\mathcal{C}f:\mathcal{C}Y\to\mathcal{C}X$ is
injective.

###### Proof.

It is easy to see that as $f$ is surjective it holds for all $U\subseteq Y$
that $f[f^{-1}[U]]=U$. To check that $\mathcal{C}f$ is injective consider any
two $C,C^{\prime}\in\mathcal{C}Y$ such that
$\mathcal{C}f(C)=\mathcal{C}f(C^{\prime})$. We have to show that then
$C(K)=C^{\prime}(K)$ for all finite $K\subseteq Y$. Using that
$f[f^{-1}[U]]=U$, we can compute:

$\displaystyle\mathcal{C}f(C)(f^{-1}[K])$
$\displaystyle=f^{-1}[C(f[f^{-1}[K]])]\cap f^{-1}[K]$
$\displaystyle=f^{-1}[C(K)]\cap f^{-1}[K]=f^{-1}[C(K)\cap K]=f^{-1}[C(K)]$

Similarly we obtain also for $C^{\prime}$ that
$\mathcal{C}f(C^{\prime})(f^{-1}[K])=f^{-1}[C^{\prime}(K)]$. From the
assumption that $\mathcal{C}f(C)=\mathcal{C}f(C^{\prime})$ it follows that
$f^{-1}[C(K)]=f^{-1}[C^{\prime}(K)]$. Because $f$ is surjective it follows
that $C(K)=C^{\prime}(K)$. ∎

###  C.3 $\Gamma$ preserves limits of countable epic cochains

In this section we prove the main technical result of this paper:

######  Theorem 4.

$\Gamma$ preserves limits of countable epic cochains. This means that whenever
we have a limit $X_{\omega}$, with projections $\zeta_{n}:X_{\omega}\to X_{n}$
for all $n\in\omega$, of a countable cochain $(X_{n},\xi_{n})_{n\in\omega}$ in
which the coherence morphisms $\xi_{n}$ are epic for all $n$, then $\Gamma
X_{\omega}$, with projections $\Gamma\zeta_{n}:\Gamma X_{\omega}\to\Gamma
X_{n}$, satisfies the universal property of the limit of the cochain $(\Gamma
X_{n},\Gamma\xi_{n})_{n\in\omega}$, i.e., for every uncertainty space $T$
together with measurable functions $\varphi_{n}:T\to\Gamma X_{n}$ for all
$n\in\omega$ with $\varphi_{n}=\Gamma\xi_{n}\circ\varphi_{n+1}$ there is a
unique measurable function $\mu:T\to\Gamma X_{\omega}$ such that
$\varphi_{n}=\Gamma\zeta_{n}\circ\mu$ for all $n\in\omega$.

For the proofs from later sections in this appendix we need the following
corollary of Theorem 4.

######  Corollary 2.

${\Gamma}^{\heartsuit}$ preserves limits of countable epic cochains.

We split the proof of Theorem 4 into two steps. First, we show that $F$ turns
limits of epic cochains in $\mathsf{Unc}$ into colimits of chains in
$\mathsf{Set}$. Second, we show that $\mathcal{C}$ turns colimits of chains
$\mathsf{Set}$ into limits of cochains in $\mathsf{Unc}$. It follows that
$\Gamma$ preserves limits of epic cochains because $\Gamma$ is defined as the
composition of $F$ and $\mathcal{C}$.

To prove the preservation result about $F$ we need two technical lemmas. The
first relates acts and measurable functions. It crucially relies on our
assumptions that acts are finite step functions.

######  Lemma 4.

Let $\varphi:X\to Y$ be a measurable function and $f\in FX$ an act with range
$f[X]=\\{z_{1},\dots,z_{k}\\}$ such that for every $n\in\\{1,\dots,k\\}$ there
is some measurable set $E_{n}$ in $Y$ such that
$f^{-1}[\\{z_{n}\\}]=\varphi^{-1}[E_{n}]$. Then there is an act $f^{\prime}\in
FY$ such that $f=f^{\prime}\circ\varphi$.

###### Proof.

We use an induction to define $H_{1}=E_{1}$ and
$H_{n+1}=E_{n+1}\setminus\bigcup_{m=1}^{n}H_{m}$ for $n\in\\{1,\dots,k-1\\}$.
We also define $H_{0}=Y\setminus\bigcup_{m=1}^{k}H_{k}$. It is clear that all
these sets $H_{0},H_{1},\dots,H_{k}$ are measurable in $Y$. Moreover, it is
also obvious from the definition that they partition the set $Y$. Let
$z_{0}\in Z$ be an arbitrary element of the non-empty set of outcomes. Define
the act $f^{\prime}\in FY$ such that $f^{\prime}(y)=z_{n}$ if $y\in H_{n}$.
Because the sets $H_{0},H_{1},\dots,H_{k}$ partition $Y$ this is well-defined
as a function. It is a measurable function because the sets
$H_{0},H_{1},\dots,H_{k}$ are measurable. To see that
$f=f^{\prime}\circ\varphi$, fix any $x\in X$ and let $n$ be such that
$f(x)=z_{n}$. Because $f^{-1}[\\{z_{n}\\}]=\varphi^{-1}[E_{n}]$ we then have
that $x\in\varphi^{-1}[E_{n}]$. Also, for every $m\neq n$ the sets
$f^{-1}[\\{z_{n}\\}]$ and $f^{-1}[\\{z_{m}\\}]=\varphi^{-1}[E_{m}]$ are
disjoint and hence $x\notin\varphi^{-1}[E_{m}]$. It follows that
$\varphi(x)\in H_{n}$ and thus $f^{\prime}(\varphi(x))=z_{n}=f(x)$. ∎

The next lemma states a property that also plays an important role in
Proposition 1 of [DT08]:

######  Lemma 5.

Consider a countable cochain $(X_{n},\xi_{n})_{n\in\omega}$, with coherence
morphisms $\xi_{n}:X_{n+1}\to X_{n}$, and let $X_{\omega}$, with projections
$\zeta_{n}:X_{\omega}\to X_{n}$, be its limit. Then, for every act $f\in
FX_{\omega}$ there is a natural number $n\in\omega$ such that for every
natural number $m\geq n$ there is an act $f^{\prime}\in FX_{m}$ such that
$f=f^{\prime}\circ\zeta_{m}$.

###### Proof.

Because $f:X_{\omega}\to Z$ is a finite step function we can enumerate its
range as $f[X]=\\{z_{1},\dots,z_{k}\\}$. Then observe that for every
$i\in\\{1,\dots,k\\}$ the set $f^{-1}[\\{z_{i}\\}]$ is measurable in
$X_{\omega}$, since $f$ is a measurable and $Z$ has the discrete algebra. By
the definition of the algebra on $X_{\omega}$ this means that for every
$i\in\\{1,\dots,k\\}$ there is some $n_{i}\in\omega$ such that
$f^{-1}[\\{z_{i}\\}]=\zeta_{n_{i}}^{-1}[E_{i}]$ for some measurable set
$E_{i}$ in $X_{n_{i}}$. Let $n$ be the maximum of all $n_{i}$ for
$i\in\\{1,\dots,k\\}$.

Consider then any $m\geq n$ and for all $i\in\\{1,\dots,k\\}$ define
$E^{m}_{i}=(\xi^{m}_{n_{i}})^{-1}[E_{i}]\subseteq X_{m}$. These $E^{m}_{i}$
are measurable in $X_{m}$ because $\xi^{m}_{n_{i}}$ is a measurable function.
By the definition of the limit of a cochain we also have that
$\zeta_{n_{i}}=\xi^{m}_{n_{i}}\circ\zeta_{m}$ for every $i\in\\{1,\dots,k\\}$.
Hence
$f^{-1}[\\{z_{i}\\}]=\zeta_{n_{i}}^{-1}[E_{i}]=(\xi^{m}_{n_{i}}\circ\zeta_{m})^{-1}[E_{i}]=\zeta_{m}^{-1}[(\xi^{m}_{n_{i}})^{-1}[E_{i}]]=\eta_{m}^{-1}[E^{m}_{i}]$.
It thus follows with Lemma 4 that there is an act $f^{\prime}\in X_{m}$ such
that $f=f^{\prime}\circ\zeta_{m}$. ∎

######  Proposition 4.

$F$ preserves limits of countable epic cochains. That is, it maps limits of
cochains of uncertainty spaces to colimits of chains of sets.

###### Proof.

Consider a cochain $(X_{n},\xi_{n})_{n\in\omega}$ of uncertainty spaces and
let $X_{\omega}$, together with projections $\zeta_{n}:X_{\omega}\to X_{n}$,
be its limit. We show that $FX_{\omega}$, together with the inclusions
$F\zeta_{n}:FX_{n}\to FX_{\omega}$ has the universal property of the colimit
of the chain $(FX_{n},F\xi_{n})_{n\in\omega}$. For this purpose consider any
set $T$ together with functions $h_{n}:X_{n}\to T$ such that
$h_{n}=h_{n+1}\circ F\xi_{n}$ for each $n\in\omega$. We need to define the
function $u:FX_{\omega}\to T$ such that $h_{n}=u\circ F\zeta_{n}$ for all
$n\in\omega$ and show that it is unique with that property.

To define $u(f)$ for some act $f\in FX_{\omega}$ we use Lemma 5. From this
lemma it follows that there is some $k$ and act $f^{\prime}\in FX_{k}$ such
that $f=f^{\prime}\circ\zeta_{k}=F\zeta_{k}(f^{\prime})$. We then set
$u(f)=h_{k}(f^{\prime})$. To check that this satisfies $h_{n}(g)=u\circ
F\zeta_{n}(g)$ for all $n\in\omega$ and $g\in FX_{n}$ consider the act
$F\zeta_{n}(g)\in FX_{\omega}$. By definition of $u$ we have that
$u(F\zeta_{n}(g))=h_{k}(f^{\prime})$ for some $f^{\prime}\in FX_{k}$ such that
$F\zeta_{n}(g)=F\zeta_{k}(f^{\prime})$. We need to show that
$h_{k}(f^{\prime})=h_{n}(g)$. Assume that $n\leq k$. This is without loss of
generality because we are only using the completely symmetric fact that
$F\zeta_{n}(g)=F\zeta_{k}(f^{\prime})$. Because
$\zeta_{n}=\xi^{k}_{n}\circ\zeta_{k}$, it follows from
$F\zeta_{n}(g)=F\zeta_{k}(f^{\prime})$ that
$f^{\prime}\circ\zeta_{k}=g\circ\zeta_{n}=g\circ\xi^{k}_{n}\circ\zeta_{k}$. We
obtain that $f^{\prime}=g\circ\xi^{k}_{n}=F\xi^{k}_{n}(g)$ because $\zeta_{k}$
is epic. From this we can then conclude that $h_{k}(f^{\prime})=h_{n}(g)$
since $h_{k}=h_{n}\circ F\xi^{k}_{n}$.

That $u$ is unique also follows from Lemma 5. The possible values of $u(f)$
are completely determined because $f=F\zeta_{n}(f^{\prime})$ for some $n$ and
$f^{\prime}\in X_{n}$ and we need to ensure that $h_{n}(f^{\prime})=u\circ
F\zeta_{n}(f^{\prime})$. ∎

######  Lemma 6.

Consider a chain $(X_{n},\xi_{n})_{n\in\omega}$ of sets and let $X_{\omega}$,
with inclusions $\iota_{n}:X_{n}\to X_{\omega}$ for all $n$, be its colimit.
Then for each finite $K\subseteq X_{\omega}$ there is an $m\in\omega$ and a
$K^{\prime}\subseteq X_{m}$ such that $\iota_{m}[K^{\prime}]=K$.

###### Proof.

By the definition of the colimit of a countable chain we have that for every
$k\in X_{\omega}$ there exists some $k^{\prime}\in X_{m_{k}}$ such that
$\iota_{m_{k}}(k^{\prime})=k$. Let $m$ be the maximum of the finitely many
$m_{k}$ for all $k\in K$ and let then
$K^{\prime}=\\{\xi^{m_{k}}_{m}(k^{\prime})\in X_{m}\mid k\in K\\}$. It then
holds that $\iota_{m}[K^{\prime}]=K$ because
$\iota_{m}\circ\xi^{m_{k}}_{m}(k^{\prime})=\iota_{m_{k}}(k^{\prime})=k$ for
every $k\in K$. ∎

######  Theorem 5.

$\mathcal{C}$ preserves colimits of countable chains. That is, it maps
colimits of chains of sets onto limits of cochains of uncertainty spaces.

###### Proof.

Consider a chain $(X_{n},\xi_{n})_{n\in\omega}$ of sets and let $X_{\omega}$,
with inclusions $\iota_{n}:X_{n}\to X_{\omega}$ for all $n$, be its colimit.
We show that $\mathcal{C}X_{\omega}$, with the
$\mathcal{C}\iota_{n}:\mathcal{C}X_{\omega}\to\mathcal{C}X_{n}$ as the
projections, has the universal property of the limit of the cochain
$(\mathcal{C}X_{n},\mathcal{C}\xi_{n})_{n\in\omega}$. Hence, consider any
uncertainty space $T$ together with measurable functions
$\varphi_{n}:T\to\mathcal{C}X_{n}$, satisfying
$\varphi_{n}=\mathcal{C}\xi_{n}\circ\varphi_{n+1}$, for all $n\in\omega$. We
need to show that there is a unique measurable function
$\mu:T\to\mathcal{C}X_{\omega}$ such that
$\mathcal{C}\iota_{n}\circ\mu=\varphi_{n}$ for all $n\in\omega$.

We first describe how to define the choice function
$\mu(t)\in\mathcal{C}X_{\omega}$ on a finite set $K\subseteq X_{\omega}$. Let
$m\in\omega$ be the least number such that there exists a $K^{\prime}\subseteq
X_{m}$ such that $\iota_{m}[K^{\prime}]=K$. Such a number exists because of
Lemma 6. Also observe that the choice of $m$ and $K^{\prime}$ only depends on
$K$ but not on $t$. This is a property which we exploit below to show that
$\mu$ is measurable. We then set the value of the choice function $\mu(t)$ on
$K$ to be

$\mu(t)(K)=\iota_{m}[\varphi_{m}(t)(K^{\prime})],$ (2)

where $\varphi_{m}(t)(K^{\prime})\subseteq K^{\prime}$ denotes the elements of
$K^{\prime}$ selected by the choice function
$\varphi_{m}(t)\in\mathcal{C}X_{m}$. This is well-defined because we have
$\iota_{m}[\varphi_{m}(t)(K^{\prime})]\subseteq\iota_{m}[K^{\prime}]=K$

To see that $\mu$ is measurable it suffices to check that the preimage
$\mu^{-1}[B^{K}_{L}]\subseteq T$ of a basic measurable set
$B^{K}_{L}=\\{C\in\mathcal{C}X_{\omega}\mid C(K)\subseteq L\\}$ is measurable
in $T$. Hence, fix finite $K$ and $L$ with $L\subseteq K$ and let $m\in\omega$
and $K^{\prime}$ be defined from $K$ as explained above. We are now going to
show that $\mu^{-1}[B^{K}_{L}]=\varphi_{m}^{-1}[B^{K^{\prime}}_{L^{\prime}}]$,
where $L^{\prime}=\iota_{m}^{-1}[L]$. Because $\varphi_{m}:T\to\Gamma X_{m}$
is assumed to be measurable, it then follows that $\mu^{-1}[B^{K}_{L}]$ is
measurable too. By unfolding the definitions one sees that the claim that
$\mu^{-1}[B^{K}_{L}]=\varphi_{m}^{-1}[B^{K^{\prime}}_{L^{\prime}}]$ is
equivalent to the claim that for all $t\in T$

$\mu(t)(K)\subseteq
L\qquad\mbox{iff}\qquad\varphi_{m}(t)(K^{\prime})\subseteq\iota_{m}^{-1}[L].$

By the definition of $\mu(t)$ above we see that the left side of this
equivalence is the same as $\iota_{m}[\varphi_{m}(t)(K^{\prime})]\subseteq L$,
which is clearly equivalent to
$\varphi_{m}(t)(K^{\prime})\subseteq\iota_{m}^{-1}[L]$.

We need to verify that $\varphi_{n}=\mathcal{C}\iota_{n}\circ\mu$ for all
$n\in\omega$. This requires that for every $t\in T$ the choice functions
$\varphi_{n}(t)$ and $\mathcal{C}\iota_{n}\circ\mu(t)$ are the same. Hence,
they need to have the same value on every finite set $L^{\prime}\subseteq
X_{n}$.

First let $K=\iota_{n}[L^{\prime}]$ and recall the definitions to see that

$(\mathcal{C}\iota_{n}\circ\mu(t))(L^{\prime})=\iota_{n}^{-1}[\mu(t)(\iota_{n}[L^{\prime}])]\cap
L^{\prime}=\iota_{n}^{-1}[\iota_{m}[\varphi_{m}(t)(K^{\prime})]]\cap
L^{\prime},$ (3)

for the $m\in\omega$ and the finite set $K^{\prime}\subseteq X_{m}$ that are
defined from $K$ as described above. Our choice of $K^{\prime}$ above ensures
that $\iota_{m}[K^{\prime}]=K=\iota_{n}[L^{\prime}]$. Hence for every
$k^{\prime}\in K^{\prime}$ there is some $l^{\prime}\in L^{\prime}$ such that
$\iota_{m}(k^{\prime})=\iota_{n}(l^{\prime})$ and conversely for every
$l^{\prime}\in L^{\prime}$ there is a $k^{\prime}\in K^{\prime}$ such that
$\iota_{m}(k^{\prime})=\iota_{n}(l^{\prime})$. By the definition of identity
for elements in the colimit $X_{\omega}$ it follows that for each such pair
$k^{\prime}\in X_{m}$ and $l^{\prime}\in X_{n}$ with
$\iota_{m}(k^{\prime})=\iota_{n}(l^{\prime})$ there is some $j\in\omega$ such
that $\xi^{m}_{j}(k^{\prime})=\xi^{n}_{j}(l^{\prime})$. Let $i$ be the maximum
of all those $j\in\omega$, which exists because there are finitely many pairs
$(k^{\prime},l^{\prime})\in K^{\prime}\times L^{\prime}$. It then clearly
holds that $\xi^{m}(k^{\prime})=\xi^{n}(l^{\prime})$, whenever
$\iota_{m}(k^{\prime})=\iota_{n}(l^{\prime})$ for $(k^{\prime},l^{\prime})\in
K^{\prime}\times L^{\prime}$. Define then $L\subseteq X$ to be the finite set

$L=\xi^{m}[K^{\prime}]=\xi^{n}[L^{\prime}].$

Because $\varphi_{n}=\mathcal{C}\xi^{n}\circ\varphi$ we obtain that

$\varphi_{n}(t)(L^{\prime})=(\xi^{n})^{-1}[\varphi(t)(\xi^{n}_{i}[L^{\prime}])]\cap
L^{\prime}=(\xi^{n})^{-1}[\varphi(t)(L)]\cap L^{\prime}.$

Similarly, because $\varphi_{m}=\mathcal{C}\xi^{m}\circ\varphi$ we obtain

$\varphi_{m}(t)(K^{\prime})=(\xi^{m})^{-1}[\varphi_{m}(t)(\xi^{m}[K^{\prime}])]\cap
K^{\prime}=(\xi^{m})^{-1}[\varphi(t)(L)]\cap K^{\prime}.$

To prove
$\varphi_{n}(t)(L^{\prime})=(\mathcal{C}\iota_{n}\circ\mu(t))(L^{\prime})$ it
thus suffices by (3) to show that

$(\xi^{n})^{-1}[U]\cap
L^{\prime}=\iota_{n}^{-1}[\iota_{m}[(\xi^{m})^{-1}[U]\cap K^{\prime}]]\cap
L^{\prime}$ (4)

for the set $U=\varphi(t)(L)\subseteq L$.

For the left-to-right inclusion of (4) consider any $l^{\prime}\in L^{\prime}$
such that $\xi^{n}(l^{\prime})\in U$. We need that
$l^{\prime}\in\iota_{n}^{-1}[\iota_{m}[(\xi^{m})^{-1}[U]\cap K^{\prime}]]$.
From the definition of $L$ we get that there is then some $k^{\prime}\in
K^{\prime}$ such that $\xi^{m}(k^{\prime})=\xi^{n}(l^{\prime})$. Hence
$k^{\prime}\in(\xi^{m})^{-1}[U]\cap K^{\prime}$ and
$\iota_{n}(l^{\prime})=\iota_{m}(k^{\prime})$. The latter two directly entail
that $l^{\prime}\in\iota_{n}^{-1}[\iota_{m}[(\xi^{m})^{-1}[U]\cap
K^{\prime}]]$.

For the right-to-left inclusion of (4) consider any $l^{\prime}\in L^{\prime}$
such that $\iota_{n}(l^{\prime})=\iota_{m}(k^{\prime})$ for some
$k^{\prime}\in(\xi^{m})^{-1}[U]\cap K^{\prime}$. With the definition of $i$
above it then follows from $\iota_{n}(l^{\prime})=\iota_{m}(k^{\prime})$ that
$\xi^{n}(l^{\prime})=\xi^{m}(k^{\prime})\in U$. Hence,
$l^{\prime}\in(\xi^{m})^{-1}[U]$ and we are done.

Lastly, we show that $\mu(t)$ is completely determined by the requirement that
$\varphi_{n}(t)=\mathcal{C}\iota_{n}\circ\mu(t)$ for all $n\in\omega$.
Consider any $\nu:T\to\mathcal{C}X_{\omega}$ such that
$\varphi_{n}(t)=\mathcal{C}\iota_{n}\circ\nu(t)$ for all $n\in\omega$. We
argue that then $\nu(t)(K)=\mu(t)(K)$ for the $\mu$ defined as above and all
finite $K\subseteq X_{\omega}$. Let $m\in\omega$ and $K^{\prime}\subseteq
X_{m}$ as in the definition of $\mu$ above, i.e., such that
$\iota_{m}[K^{\prime}]=K$. The requirement that
$\varphi_{m}(t)=\mathcal{C}\iota_{m}\circ\nu(t)$ means that

$\varphi_{m}(t)(K^{\prime})=\iota_{m}^{-1}[\nu(t)(\iota_{m}[K^{\prime}])]\cap
K^{\prime}=\iota_{m}^{-1}[\nu(t)(K)]\cap K^{\prime}.$

One can see that this entails that

$\iota_{m}[\varphi_{m}(t)(K^{\prime})]=\nu(t)(K).$

The left-to-right inclusion is trivial and the other inclusion follows because
$\nu(t)(K)\subseteq K$ and $\iota_{m}[K^{\prime}]=K$. Therefore, we have shown
that $\nu(t)(K)$ equals the expression that we use in (2) to define
$\mu(t)(K)$. ∎

As an immediate consequence of the previous two propositions we obtain the
main result of this section.

##  Appendix D Proofs for Section 3

Theorems 1 and 2 follow from the results about $\Gamma$ together with well-
known results [Wor99] about the terminal coalgebra. In the following, we
sketch how these results from the general theory of coalgebras apply to the
setting of choice structures.

###  D.1 Preliminary observations

Theorems 1 and 2 concern the universal choice structure that is obtained from
the choice hierarchies as described in Section 3.2. Let us first see how this
fits into the coalgebraic set-up.

One can view the two uncertainty spaces $\Omega_{i,n}$ and $\Omega_{j,n}$ on
the $n$-th level in the choice hierarchy as defining an object
$\Omega_{n}=(\Omega_{i,n},\Omega_{j,n})$ in the category $\mathsf{Unc}^{2}$.
In fact one can define these objects directly, just using the functor
${\Gamma}^{\heartsuit}$ as follows: We start with $\Omega_{0}=\top$, where
$\top$ is the terminal object in $\mathsf{Unc}^{2}$, and then define
inductively $\Omega_{n+1}={\Gamma}^{\heartsuit}\Omega_{n}$. It is easy to see
that with the exception of the $0$-th level, which is omitted from the
discussion in the main text, this yields the same sequence of pairs of
uncertainty spaces as defined in Section 3.2. Similarly, the coherence
morphism $\xi_{i,n}$ and $\xi_{j,n}$ can also be defined directly in
$\mathsf{Unc}^{2}$ with
$\xi_{0}=\mathord{!}_{{\Gamma}^{\heartsuit}\top}:{\Gamma}^{\heartsuit}\top\to\top$
and inductively
$\xi_{n+1}={\Gamma}^{\heartsuit}\xi_{n}:{\Gamma}^{\heartsuit}\Omega_{n+1}\to{\Gamma}^{\heartsuit}\Omega_{n}$.
Thus, the sequence $(\Omega_{n},\xi_{n})_{n\in\Omega}$ forms a countable
cochain in $\mathsf{Unc}^{2}$.

The definition of the uncertainty spaces $\Omega_{i}$ and $\Omega_{j}$ of
types in the universal choice structures from Section 3.2 is such that these
are precisely the limits of the countable cochains
$(\Omega_{i,n},\xi_{i,n})_{n\in\omega}$ and
$(\Omega_{j,n},\xi_{j,n})_{n\in\omega}$ in $\mathsf{Unc}$. Because limits in
$\mathsf{Unc}^{2}$ are computed component-wise it follows that the object
$\Omega=(\Omega_{i},\Omega_{j})$ in $\mathsf{Unc}^{2}$ is the limit of the
countable cochain $(\Omega_{n},\xi_{n})_{n\in\omega}$. Also recall that the
limit comes with projections
$\zeta_{n}=(\zeta_{i,n},\zeta_{j,n}):\Omega\to\Omega_{n}$ back into the chain
such that $\zeta_{n}=\xi_{n}\circ\zeta_{n+1}$.

The crucial observation behind Theorems 1 and 2 is then that the functor
${\Gamma}^{\heartsuit}$ on $\mathsf{Unc}^{2}$ preserves the limit of the epic
cochain $(\Omega_{n},\xi_{n})$. This follows from Corollary 2, which states
that ${\Gamma}^{\heartsuit}$ preserves limits of countable epic cochains. To
apply Corollary 2 to the cochain $(\Omega_{n},\xi_{n})_{n\in\omega}$ we need
to check that the coherence morphisms $\xi_{n}$ for all $n\in\omega$ are epic.
This can be checked directly by an induction over the definition of the
$\xi_{n}$. In the base step $\xi_{0}=(\xi_{i,0},\xi_{j,0})$, and
$\xi_{i,0}=\Gamma\pi_{1}$, where $\pi_{1}$ is the projection out of a product.
Because this projection is epic, and by the argument in Section C.1 the
functor $\Gamma$ preserves epic morphisms, it follows that $\xi_{i,0}$ is
epic. We reason analogously for $\xi_{j,0}$. That
$\xi_{n+1}=(\xi_{i,n+1},\xi_{j,n+1})=(\Gamma(\mathsf{id}_{A_{j}}\times\xi_{j,n}),\Gamma(\mathsf{id}_{A_{i}}\times\xi_{i,n}))$
is epic, also follows easily because $\Gamma$ preserves epic morphisms.

###  D.2 Theorem 1

Next consider the object ${\Gamma}^{\heartsuit}\Omega$ of $\mathsf{Unc}^{2}$.
For this object we can define morphisms into the cochain
$(\Omega_{n},\xi_{n})_{n\in\omega}$ by setting
$\tau_{0}=\mathord{!}_{{\Gamma}^{\heartsuit}\Omega}:{\Gamma}^{\heartsuit}\Omega\to\Omega_{0}$
and
$\tau_{n+1}={\Gamma}^{\heartsuit}\zeta_{n}:{\Gamma}^{\heartsuit}\Omega\to{\Gamma}^{\heartsuit}\Omega_{n}$,
which satisfy $\tau_{n}=\xi_{n}\circ\tau_{n+1}$ for all $n$. From Theorem 4 it
follows that ${\Gamma}^{\heartsuit}\Omega$ together with the projections
${\Gamma}^{\heartsuit}\zeta_{n}=\tau_{n+1}$ is a colimit of the cochain
$({\Gamma}^{\heartsuit}\Omega_{n},{\Gamma}^{\heartsuit}\xi_{n})_{n\in\omega}$,
which by definition is the same as the chain
$(\Omega_{n+1},\xi_{n+1})_{n\in\omega}$. We can use this observation to show
that ${\Gamma}^{\heartsuit}\Omega$ together with the $\tau_{n}$ also satisfies
the universal property of the limit of the cochain
$(\Omega_{n},\xi_{n})_{n\in\omega}$. To this aim take any further object $T$
of $\mathsf{Unc}^{2}$ together with morphisms $g_{n}:T\to\Omega_{n}$ such that
$g_{n}=\xi_{n}\circ g_{n+1}$ for all $n\in\omega$. We now just consider this
$g_{n}$ without $g_{0}$ as morphism into the chain
$({\Gamma}^{\heartsuit}\Omega_{n},{\Gamma}^{\heartsuit}\xi_{n})_{n\in\omega}$
satisfying that $g_{n+1}=\xi_{n+1}\circ
g_{n+2}={\Gamma}^{\heartsuit}\xi_{n}\circ g_{n+1}$ for all $n\in\omega$.
Because ${\Gamma}^{\heartsuit}\Omega$ is a limit of this chain there must be
then a unique morphism $u:T\to{\Gamma}^{\heartsuit}\Omega$ such that
$g_{n+1}={\Gamma}^{\heartsuit}\zeta_{n}\circ u=\tau_{n+1}\circ u$ for all
$n\in\omega$. Additionally, we have that $g_{0}=\tau_{0}\circ u$ holds
trivially because on both sides of the equation we have a morphism into the
terminal object $\top=\Omega_{0}$ of $\mathsf{Unc}^{2}$.

We have now seen that both $\Omega$ and ${\Gamma}^{\heartsuit}\Omega$ satisfy
the universal property of limit for the cochain
$(\Omega_{n},\xi_{n})_{n\in\omega}$. Theorem 1 then follows because there can
be only one such object up to isomorphism.

More precisely, the isomorphism is given by the unique morphism
$\mu=(\mu_{i},\mu_{j}):\Omega\to{\Gamma}^{\heartsuit}\Omega$ such that
$\zeta_{n}=\tau_{n}\circ\mu$ for all $n\in\omega$, which exists because
$\Omega$ is a limit. If one considers the components of this morphism one
obtains the isomorphism $\mu_{i}:\Omega_{i}\to\Gamma(A_{j}\times\Omega_{j})$
and $\mu_{j}:\Omega_{j}\to\Gamma(A_{i}\times\Omega_{i})$ that are referred to
in the formulation of Theorem 1.

######  Remark 2.

One can generate a topology on $\Omega_{i}$, using the algebra of events as
the basis. Because of our assumption that $Z$, $A_{i}$ and $A_{j}$ are finite
it follows that all the $\Omega_{i,n}$ are finite. Thus, $\Omega_{i}$ is what
is called a filtered limit of finite spaces, which is well-know to be a Stone
space, meaning that it is compact, Hausdorff and has a basis of clopen sets.
One can also show also that this topology has a countable basis, because for
every of the countably many spaces $\Omega_{i,n}$ there are only finitely many
events in $\Omega_{i}$ that are preimages of sets in $\Omega_{i,n}$. Compact
Hausdorff spaces with a countable basis are called simple spaces in [DT08].

######  Remark 3.

For the result of this section, and the universality of the universal choice
structure proved in the next section, it is not needed that the uncertainty
spaces $Z$, $A_{i}$, and $A_{j}$ are finite. The preservation of limits of
epic cochains, which is at the core of these results, holds for arbitrary
uncertainty spaces. However, for our proof of Lemma 4 we need that acts are
defined as finite step functions and that $Z$ carries the discrete algebra.
The finiteness of $Z,A_{i}$ and $A_{j}$ is required for the results about non-
redundancy from Section 3.4 and the embedding of the universal preference
structure from Section 4.3.

###  D.3 Theorem 2

We now prove Theorem 2. Consider an arbitrary choice structure
$\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$, presented as a coalgebra
$(T,\theta)=((T_{i},T_{j}),(\theta_{i},\theta_{j}))$ for
${\Gamma}^{\heartsuit}$. We need to show that there is a unique morphism
$\upsilon$ from $(T,\theta)$ to the universal choice structure $(\Omega,\mu)$.

To prove the existence of $\upsilon$ first consider the measurable functions
$\upsilon_{0}=\mathord{!}_{T}:T\to\Omega_{0}$ and the inductively defined
$\upsilon_{n+1}={\Gamma}^{\heartsuit}\upsilon_{n}\circ\theta:T\to\Omega_{n+1}$.
By an induction over $n$ we can show that these measurable functions satisfy
$\upsilon_{n}=\xi_{n}\circ\upsilon_{n+1}$. In the base case this is clear
because there is only one morphism from $T$ to the terminal object
$\Omega_{0}=\top$. For the inductive step we calculate as follows:

$\displaystyle\upsilon_{n+1}$
$\displaystyle={\Gamma}^{\heartsuit}\upsilon_{n}\circ\theta={\Gamma}^{\heartsuit}(\xi_{n}\circ\upsilon_{n+1})={\Gamma}^{\heartsuit}\xi_{n}\circ{\Gamma}^{\heartsuit}\upsilon_{n+1}\circ\theta=\xi_{n+1}\circ\upsilon_{n+2}.$

Because $\Omega$ is defined as the limit of the sequence
$(\Omega_{n},\xi_{n})_{n\in\Omega}$ it follows that there is a unique morphism
$\upsilon:T\to\Omega$ with the property that for all $n\in\omega$

$\upsilon_{n}=\zeta_{n}\circ\upsilon.$ (5)

It remains to be seen that $\upsilon$ is a morphism of choice structures and
that it is unique with this property.

To show that $\upsilon:T\to\Omega$ is a morphism from $(T,\theta)$ to
$(\Omega,\mu)$ we need to verify that
$\mu\circ\upsilon={\Gamma}^{\heartsuit}\upsilon\circ\theta$. We show this by
proving that $\upsilon_{n}=\tau_{n}\circ\mu\circ\upsilon$ and
$\upsilon_{n}=\tau_{n}\circ{\Gamma}^{\heartsuit}\upsilon\circ\theta$ hold for
all $n\in\omega$. The equality
$\mu\circ\upsilon={\Gamma}^{\heartsuit}\upsilon\circ\theta$ then follows from
the universal property for the limit ${\Gamma}^{\heartsuit}\Omega$ of
$(\Omega_{n},\xi_{n})_{n\in\omega}$, with projections
$\tau_{n}:{\Gamma}^{\heartsuit}\Omega\to\Omega_{n}$.

To see that $\upsilon_{n}=\tau_{n}\circ\mu\circ\upsilon$ we use that by its
definition in Section D.2 $\mu$ satisfies $\tau_{n}\circ\mu=\zeta_{n}$. The
claim then reduces to (5).

To see that
$\upsilon_{n}=\tau_{n}\circ{\Gamma}^{\heartsuit}\upsilon\circ\theta$ we
distinguish two cases. If $n=0$ we have that both $\upsilon_{0}$ and
$\tau_{0}\circ{\Gamma}^{\heartsuit}\upsilon\circ\theta$ are morphisms from $T$
to the terminal object $\Omega_{0}=\top$ of $\mathsf{Unc}^{2}$. By the
universal property of the terminal object they must be equal.

If $n$ is strictly positive we can unfold the definition of $\upsilon_{n+1}$,
use (5) and then unfold the definition of $\tau_{n+1}$ to obtain the following
computation

$\upsilon_{n+1}={\Gamma}^{\heartsuit}\upsilon_{n}\circ\theta={\Gamma}^{\heartsuit}(\zeta_{n}\circ\upsilon)\circ\theta={\Gamma}^{\heartsuit}\zeta_{n}\circ{\Gamma}^{\heartsuit}\upsilon\circ\theta=\tau_{n+1}\circ{\Gamma}^{\heartsuit}\upsilon\circ\theta.$

To prove that $\upsilon$ is the only morphism of choice structures from
$(T,\theta)$ to $(\Omega,\mu)$ consider any other morphism
$\upsilon^{\prime}:T\to\Omega$ in $\mathsf{Unc}^{2}$ such that
$\mu\circ\upsilon^{\prime}={\Gamma}^{\heartsuit}\upsilon^{\prime}\circ\theta$.
We show that then $\upsilon_{n}=\zeta_{n}\circ\upsilon^{\prime}$ for all
$n\in\omega$, from which is follows that $\upsilon^{\prime}=\upsilon$ because
$\upsilon$ is defined as the unique morphism with the property (5). To prove
$\upsilon_{n}=\zeta_{n}\circ\upsilon^{\prime}$ we use an induction on $n$. In
the base case we again have that $\upsilon_{0}$ and
$\zeta_{0}\circ\upsilon^{\prime}$ must be equal because they are both morphism
from $T$ to the terminal object $\Omega_{0}=\top$ of $\mathsf{Unc}^{2}$. In
the inductive step we use the following computation:

$\displaystyle\upsilon_{n+1}$
$\displaystyle={\Gamma}^{\heartsuit}\upsilon_{n}\circ\theta$
$\displaystyle\mbox{definition of }\upsilon_{n+1}$
$\displaystyle={\Gamma}^{\heartsuit}(\zeta_{n}\circ\upsilon^{\prime})\circ\theta$
induction hypothesis
$\displaystyle={\Gamma}^{\heartsuit}\zeta_{n}\circ{\Gamma}^{\heartsuit}\upsilon^{\prime}\circ\theta$
$\displaystyle{\Gamma}^{\heartsuit}\mbox{ functor}$
$\displaystyle=\tau_{n+1}\circ{\Gamma}^{\heartsuit}\upsilon^{\prime}\circ\theta$
$\displaystyle\mbox{definition of }\tau_{n+1}$
$\displaystyle=\tau_{n+1}\circ\mu\circ\upsilon^{\prime}$
$\displaystyle\mbox{assumption on }\upsilon^{\prime}$
$\displaystyle=\zeta_{n+1}\circ\upsilon^{\prime}$
$\displaystyle\mbox{uniqueness property of }\mu$

###  D.4 Results for Section 3.4

In this part of the appendix we prove our results about non-redundancy.

####  D.4.1 Well-definedness of Definition 3

To explain the definition of the algebra of observable events more
extensively, fix the choice structure
$\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$ and consider pairs of
algebras $(\mathcal{B}_{i},\mathcal{B}_{j})$ such that $\mathcal{B}_{i}$ is an
algebra over the set $T_{i}$ and $\mathcal{B}_{j}$ is an algebra over the set
$T_{j}$. Define an order $\leq$ over such pairs of algebras such that
$(\mathcal{B}_{i},\mathcal{B}_{j})\leq(\mathcal{B}^{\prime}_{i},\mathcal{B}^{\prime}_{j})$
iff $\mathcal{B}_{i}\subseteq\mathcal{B}^{\prime}_{i}$ and
$\mathcal{B}_{j}\subseteq\mathcal{B}^{\prime}_{j}$. Definition 3 then defines
$(\mathcal{B}^{ob}_{\mathcal{X},i},\mathcal{B}^{ob}_{\mathcal{X},j})$ as the
least element $(\mathcal{B}_{i},\mathcal{B}_{j})$ in this order $\leq$ which
satisfies that

  1. 1.

$B^{ob}_{\mathcal{X},i}(K,F)\in\mathcal{B}_{i}$ for all finite $K,L\subseteq
F(A_{j}\times(T_{j},\mathcal{B}_{j}))$, and

  2. 2.

$B^{ob}_{\mathcal{X},j}(K,F)\in\mathcal{B}_{i}$ for all finite $K,L\subseteq
F(A_{i}\times(T_{i},\mathcal{B}_{i}))$.

Let $O$ be the set of all pairs of algebras that satisfy these two conditions.
The well-definedness of
$(\mathcal{B}^{ob}_{\mathcal{X},i},\mathcal{B}^{ob}_{\mathcal{X},j})$ now
amounts to the following claim:

######  Proposition 5.

$O$ contains a (unique) least element.

###### Proof.

Define the pair of families of sets $(\mathcal{L}_{i},\mathcal{L}_{j})$ where
$\mathcal{L}_{i}=\bigcap\\{\mathcal{B}_{i}\mid(\mathcal{B}_{i},\mathcal{B}_{j})\in
O\\}$ and
$\mathcal{L}_{j}=\bigcap\\{\mathcal{B}_{j}\mid(\mathcal{B}_{i},\mathcal{B}_{j})\in
O\\}$. It is relatively easy to see that
$(\mathcal{L}_{i},\mathcal{L}_{j})\leq(\mathcal{B}_{i},\mathcal{B}_{j})$ for
all $(\mathcal{B}_{i},\mathcal{B}_{j})\in O$. We argue that
$(\mathcal{L}_{i},\mathcal{L}_{j})$ is again a pair of algebras and it is in
$O$. Thus, $(\mathcal{L}_{i},\mathcal{L}_{j})$ is the least element of $O$. We
leave it to the reader to check that $(\mathcal{L}_{i},\mathcal{L}_{j})$ is
again a pair of algebras. This essentially reduced to the well-known fact that
the arbitrary intersection of algebras is again an algebra.

To show that $(\mathcal{L}_{i},\mathcal{L}_{j})\in O$ we need to show that it
satisfies the two conditions of the list above. We only check the first one
that $B^{ob}_{\mathcal{X},i}(K,F)\in\mathcal{L}_{i}$ for all finite
$K,L\subseteq F(A_{j}\times(T_{j},\mathcal{L}_{j}))$. To this aim fix any
finite $K,L\subseteq F(A_{j}\times(T_{j},\mathcal{L}_{j}))$. To show that
$B^{ob}_{\mathcal{X},i}(K,F)\in\mathcal{L}_{i}$ we need to show that
$B^{ob}_{\mathcal{X},i}(K,F)\in\mathcal{B}_{i}$ for all
$(\mathcal{B}_{i},\mathcal{B}_{j})\in O$. This would follow because
$(\mathcal{B}_{i},\mathcal{B}_{j})$ also satisfies the first item in the list
above, provided that we can show that $K,L\subseteq
F(A_{j}\times(T_{j},\mathcal{B}_{j}))$. To obtain the latter we argue that
$F(A_{j}\times(T_{j},\mathcal{L}_{j}))\subseteq
F(A_{j}\times(T_{j},\mathcal{B}_{j}))$. Because
$\mathcal{L}_{j}\subseteq\mathcal{B}_{j}$ it follows that every measurable set
in $A_{j}\times(T_{j},\mathcal{L}_{j})$ is also measurable in
$A_{j}\times(T_{j},\mathcal{B}_{j})$. Hence, a function that is measurable for
the domain $A_{j}\times(T_{j},\mathcal{L}_{j})$ is also measurable for the
domain $A_{j}\times(T_{j},\mathcal{B}_{j})$. ∎

####  D.4.2 Proof of Proposition 1

To prove Proposition 1 we need to perform another inductive argument over the
definition of the terminal sequence from which the universal choice structure
$\mathcal{U}$ was defined. Let us first recall relevant facts from Sections
D.1 and D.3 that will be used in the following arguments. For every $n$ we had
an approximant $\Omega_{n}$ in $\mathsf{Unc}^{2}$ such that $\Omega_{0}$ is
the terminal object of $\mathsf{Unc}^{2}$ and
$\Omega_{n+1}={\Gamma}^{\heartsuit}\Omega_{n}$. Concretely, this meant that
$\Omega_{i,0}=\top$ is the one element uncertainty space and
$\Omega_{i,n+1}=\Gamma(A_{j}\times\Omega_{j,n})$, and similarly with $i$ and
$j$ swapped. Given any choice structure $\mathcal{X}=(T,\theta)$, where
$T=(T_{i},T_{j})$ and $\theta=(\theta_{i},\theta_{j})$ are in
$\mathsf{Unc}^{2}$, we then defined the maps $\upsilon_{n}:T\to\Omega_{n}$
such that $\upsilon_{0}=\mathord{!}_{T}$ is the unique morphism into the
terminal object $\Omega_{0}$ of $\mathsf{Unc}^{2}$ and
$\upsilon_{n+1}={\Gamma}^{\heartsuit}\upsilon_{n}\circ\theta$. If we spell out
the latter in terms of measurable functions we have that

$\upsilon_{i,n+1}=\Gamma(\mathsf{id}_{A_{j}}\times\upsilon_{j,n})\circ\theta_{i}\quad\mbox{and}\quad\upsilon_{j,n+1}=\Gamma(\mathsf{id}_{A_{i}}\times\upsilon_{i,n})\circ\theta_{j}.$
(6)

We then used the properties of the limit $\Omega$ to obtain a the morphism
$\upsilon:T\to\Omega$, which is unique for the property that
$\upsilon_{n}=\zeta_{n}\circ\upsilon$. Here, $\zeta_{n}:\Omega\to\Omega_{n}$
is the projection from the limit into the cochain. For measurable functions
this property means that

$\upsilon_{i,n}=\zeta_{i,n}\circ\upsilon_{i}\quad\mbox{and}\quad\upsilon_{j,n}=\zeta_{j,n}\circ\upsilon_{j}.$
(7)

######  Lemma 7.

Let $\mathcal{X}=(T_{i},T_{j},\theta_{i},\theta_{j})$ be any choice structure
and for every $n\in\omega$ consider $\upsilon_{i,n}:T_{i}\to\Omega_{i,n}$ as
defined above. Then it holds for every set $A\subseteq\Omega_{i,n}$ that
$\upsilon_{i,n}^{-1}[A]\in\mathcal{B}^{ob}_{\mathcal{X},i}$. The same holds
with $j$ in place of $i$.

###### Proof.

The proof is an induction on $n$. In the base case we have that $\Omega_{i,0}$
is the one element uncertainty space. Thus, $\upsilon_{i,0}^{-1}[A]$ is either
the empty set or the whole set of all types in $T_{i}$. Thus, it is in the
algebra $\mathcal{B}^{ob}_{\mathcal{X},i}$.

To prove the inductive step we show below that
$\upsilon_{i,n+1}^{-1}[B^{K}_{L}]\in\mathcal{B}^{ob}_{\mathcal{X},i}$ holds
for for all $K,L\subseteq F(A_{j}\times\Omega_{j,n})$, where
$B^{K}_{L}=\\{C\in\Omega_{j,n+1}\mid C(K)\subseteq L\\}$. Let us see first how
from this it then follows that
$\upsilon_{i,n+1}^{-1}[A]\in\mathcal{B}^{ob}_{\mathcal{X},i}$ holds for every
arbitrary set $A\subseteq\Omega_{n+1,i}$: Because $\Omega_{i,n+1}$ is finite
and any two distinct choice functions in
$\Omega_{i,n+1}=\Gamma(A_{j}\times\Omega_{j,n})$ can be separated by some such
set $B^{K}_{L}$, it follows from a standard argument that every set
$A\subseteq\Omega_{n+1,i}$ can be written as a finite union of intersections
of sets of the form $B^{K}_{L}$ and complements of such sets. Because these
unions, intersections and complements are preserved under taking preimages and
$\mathcal{B}^{ob}_{\mathcal{X},i}$ is an algebra it follows that
$\upsilon_{i,n}^{-1}[A]\in\mathcal{B}^{ob}_{\mathcal{X},i}$.

We now prove that
$\upsilon_{i,n+1}^{-1}[B^{K}_{L}]\in\mathcal{B}^{ob}_{\mathcal{X},i}$ holds
for for all $K,L\subseteq F(A_{j}\times\Omega_{j,n})$. First, observe that by
the induction hypothesis we have that if $f\in F(A_{j}\times\Omega_{j,n})$
then $f\circ(\mathsf{id}_{A_{j}}\times\upsilon_{j,n})\in
F(A_{j}\times(\Omega_{j},\mathcal{B}^{ob}_{\mathcal{X},j}))$. This holds
because by the inductive hypothesis the preimage of any set at $\Omega_{j,n}$
under $\upsilon_{j,n}$ is measurable in the uncertainty space
$(T_{j},\mathcal{B}^{ob}_{\mathcal{X},j})$. Thus, the function
$f\circ(\mathsf{id}_{A_{j}}\times\upsilon_{j,n})$ is measurable even when we
take its domain to be $A_{j}\times(T_{j},\mathcal{B}^{ob}_{\mathcal{X},j})$.
Then, fix the sets $K,L\subseteq F(A_{j}\times\Omega_{j,n})$ and define the
finite sets

$K^{\prime}=\\{f\circ(\mathsf{id}_{A_{j}}\times\upsilon_{j,n})\mid f\in
K\\}\quad\mbox{and}\quad
L^{\prime}=\\{f\circ(\mathsf{id}_{A_{j}}\times\upsilon_{j,n})\mid f\in L\\}.$

From the observation in the beginning of the paragraph it follows that that
$K^{\prime},L^{\prime}\subseteq
F(A_{j}\times(T_{j},\mathcal{B}^{ob}_{\mathcal{X},j}))$.

To show that
$\upsilon_{i,n+1}^{-1}[B^{K}_{L}]\in\mathcal{B}^{ob}_{\mathcal{X},i}$, it
suffices by the definition of $\mathcal{B}^{ob}_{\mathcal{X},i}$ to show that
$\upsilon_{i,n+1}^{-1}[B^{K}_{L}]=B^{ob}_{\mathcal{X},i}(K^{\prime},L^{\prime})$.
Unfolding the definitions shows that this amounts to the claim that for all
$t\in T_{i}$ we have $\upsilon_{i,n+1}(t)(K)\subseteq L$ iff
$\theta_{i}(t)(K^{\prime})\subseteq L^{\prime}$. To see that this is the case
consider the following chain of equivalences:

$\displaystyle\upsilon_{i,n+1}(t)(K)\subseteq L$ $\displaystyle\mbox{ iff
}(\Gamma(\mathsf{id}_{A_{j}}\times\upsilon_{j,n})\circ\theta_{i}(t))(K)\subseteq
L$ by (6) $\displaystyle\mbox{ iff }\\{f\in K\mid