Choice Structures in Games

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.

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

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).

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

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.

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.¹¹1That $\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.

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.

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

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

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$

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.

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

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:

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.²²2[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.

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

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:

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:

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.

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

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:

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.

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.

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.

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

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

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].

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:

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

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.

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.

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:

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}$.