Economic Data Types

December, 1989

by
Spyros Vassilakis¹

Economics Department
University of Pittsburgh

Working Paper No. 252

Department
of Economics

<figure><img src="image_1.png" /></figure>

University of Pittsburgh

Pittsburgh, Pennsylvania 15260
# Table of Contents

## Introduction

1. Motivating Examples

1.1 Universal Beliefs Spaces

1.2 Universal Commodity Spaces

2. Facts from Category Theory

3. The Probability Functor is $\omega^{\text{OP}}$-continuous

4. Move Examples of Recursively Defined Data Types

4.1 Universal Lottery Spaces (fixpoints under a given object)

4.2 Universal Choice Spaces

4.3 Common Knowledge Functors (parametric data types)

4.4 Universal State Spaces

4.5 Universal Mechanisms

5. Some Applications of Free Constructions

5.1 Implementation Theory

5.2 (Kan) Extensions of Solution Concepts

## Conclusions
# Introduction

This paper shows that there are many interesting problems in economics and game theory that involve recursive constructions; and claims that category theory provides both the concepts that make all these constructions special cases of a few general constructions and the proof techniques that are appropriate for the study of their properties.

The paper is organized as follows: part 1 presents the motivating examples: the construction of a universal beliefs space by Mertens and Zamir (1985) and the construction of the commodity space arising from the process of division of labor that is implicit in Adam Smith (1930), and Allyn Young (1928). The choice of such strikingly different examples to motivate the mathematics is intended to convey the unifying power of the tools from category theory (including a fixpoint theorem). Part 3 proves that the Mertens - Zamir beliefs functor is continuous (this seems to be a new result) and, therefore, that it meets the conditions of the fixpoint theorem. Part 4 presents more applications of the fixpoint theorem in economics, some of them new. Finally, part 5 indicates how the mathematics of part 3 can be used to construct solution concepts and implement choice functions.
# 1. Motivating examples

## The universal beliefs space:

Consider n agents that face a common uncertainty. Let S be the set of all possible states of nature. Agents can form beliefs on S' and on each other's beliefs. Is there, for each agent i, a set $X_i$ that consists of **all** his possible beliefs (on S and on **all** beliefs of others)? Proceeding naively, let $\Delta$ be a map that assigns to each compact set X the set $\Delta(X)$ of all Borel probability measures on X. Then if $X_1, X_2, \dots, X_n$ are arbitrary compact sets for agents 1, 2, ..., n, respectively, the sets of beliefs that can be formed on these sets are respectively,

$$ \Delta(S \times X_{-1}), \Delta(S \times X_{-2}), \dots\dots\dots, \Delta(S \times X_{-n}) $$

where

$$ X_{-i} = \prod_{j \neq i j} X_j $$

Hence the n-tuple $(X_1, X_2, \dots, X_n)$ will be a universal belief space if and only if:

$$ (1) \qquad X_i \approx \Delta(S \times X_{-i}) \quad \text{for all } i $$

where $\approx$ denotes isomorphism. If CH is the collection of all compact Hauidorff sets and $CH^n$ the collection of all n-tuples of such sets, we can define:
$$F_i: CH^n \to CH$$

$$(X_1, X_2, \dots, X_n) F_i = X F_i = \Delta(S \times X_{-i}) \text{ for all } i$$

and $F = CH^{n} \to CH^{n}$

$$XF = \langle XF_1, \dots, XF_n \rangle$$

Hence, (1) is equivalent to

$$(2) \qquad X \approx XF$$

and the problem of the existence of universal belief space has been reduced to the problem of existence of solutions of equation (2). Since CH is not a set, (2) is not a conventional equation, and F is not an ordinary function. We speak of a functor F defined on the category CH, and we consider (2) as an example of a construction by the fixpoint method. The original construction of X in Mertens and Zamir (1985) involves the construction of a hierarchy of beliefs as follows:

$$X^0 = 1 = \{0\}, \{0\}, \dots, \{0\} \qquad \text{0-level beliefs}$$

$$X^1 = 1F \approx (\Delta(S), \Delta(S), \dots, \Delta(S)) \quad 1^{\text{st}} \text{-level beliefs}$$

$$X^2 = 1F^2 = (\Delta(S \times X_{-1}), \dots, \Delta(S \times X_{-n})) \text{, 2nd-level beliefs}$$
$X^t = 1F^t$ n-level beliefs

Given that 1 is a singleton, there is a unique mapping !: 1F--->1,
which "recovers 0-levels beliefs from 1st-level beliefs". The image of
! under F^t (not formally defined yet) is a map ! F^t: 1F^t +1 ---> 1F^t that
"recovers t-level beliefs from (t+1)-level beliefs". Hence, the
hierarchy of beliefs looks like an inverse sequence

$$
(3) \quad 1 \xrightarrow{!} 1F \xrightarrow{!F} 1F^2 \xrightarrow{!F^2} 1F^3 \leftarrow \dots
$$

A consistent n-tuple of beliefs sets X is defined to be an n-tuple X of
compact Hausdorff sets and, for each t, an n-tuple of functions µ_t : X-
---→1F^t such that the following diagram commutes for each t

<figure><img src="image_2.png" /></figure>

X should be thought of as a candidate universal beliefs space, and μ_t
as the map that recovers t- level beliefs from beliefs in X.
Commutativity means that all possible ways to recover t-level beliefs
from beliefs in X are identical.
The universal beliefs space is then defined to be the "optimal" candidate universal beliefs space, in the sense that if (X', μ') is any other candidate, there is a unique map from X' into X such that t-level beliefs recovered from beliefs in X' can be consistently recovered from beliefs in X. The commutativity conditions that express this are given below

<figure><img src="image_3.png" /></figure>

The construction of an object that is "optimal" among those mapping consistently into some given objects (the finite-level beliefs spaces) is an example of a construction by (taking the) limit of a functor. The interconnection between limits and fixpoints will be considered in part 2.

**_The universal commodity space:_**

Let $T$ be a set of commodity **names** (labor, land, ...) and let $TB = \{ f : T \to R_+ \}$ be the set of commodity **bundles** on $T$. Let $X$ be a set of bundles: a **production process on $X$** is a functor $g: X \to X$ (possibly subject to some restrictions) that transforms input bundles into output
bundles. Let XG be the set of production processes on X. Then each element of XG can be thought of in two ways: it is both a production process (machine, factory, ...) that transforms input commodity bundles into output commodity bundles, and a commodity, the output of some other production process. Hence, $XGB = \{ f: XG \rightarrow R \}$ is the set of bundles of machines on X: The universal commodity space should be, therefore, a space T that includes all machines on TB, plus, possibly, some basic set S of commodities. Define, therefore, F to be a map (functor) associating to each set of commodities T the set of commodities TF = TBG + S, where + denotes disjoint union. The universal commodity space should satisfy

$$ (6) \qquad T \approx TF $$

Again, the fixpoint (6) can be obtained by a limit process.

$$ (7) \qquad 1 \leftarrow ! \quad 1F \leftarrow \dots \leftarrow 1F^t \leftarrow !F^t \dots $$

where $1F^t$ is the set of t-level machines (machines that produce (t-1) level machines) and $!F^t$ "recovers t-level machines from (t+1)-level machines". Another terminology, suggested by Allyn Young, would be
that $1F^t$ represents the $t$th stage of production roundaboutness. The definitions of a candidate universal commodity space, and of an optimal candidate, are the same as in the case of the construction of the beliefs space. The question that naturally arises at this point is, under what conditions do fixpoints and limits exist?

## 2. Facts from category theory.

This chapter is not an introduction to category theory, but a list of definitions and theorems that are needed in the rest of the paper. Unless otherwise indicated, all proofs can be found in Mclane (1971).

## 1. Definition. A Category X consists of

* a class of objects: $x,y,\dots$

* a class of morphisms: $f,g,\dots$

Each morphism $f$ has a source object $x$ and a target object $y$; we write $f: x \to y$.

An associative operation on morphisms, composition, that associates to each pair of morphisms $f:x \to y, g:y \to z$ a morphism $fg:x \to z$.

For each object $x$, a morphism $\text{id}_x: x \to x$, the identity on $x$, such that

$$ \text{id}_x = f; \quad \text{id}_x g = g $$

for all morphisms $f,g$ for which the composition is defined
2. **Definition:** A **functor** $F: X \dashrightarrow Y$ from category $X$ to category $Y$ assigns to each object $x$ in $X$ an object $xF$ in $Y$ and to each morphism $f: x_1 \rightarrow x_2$ in $X$ a morphism $fF: x_1F \dashrightarrow x_2F$ in $Y$, in such a way that composition and identity are preserved i.e.

$$ (fg)F = (fF) (gF) $$

$$ (\mathrm{id}_X)F = \mathrm{id}_{xF} $$

3. **Definition:** A **natural transformation** $\lambda: F \dashrightarrow G$ from a functor $F: X \dashrightarrow Y$ to a functor $G: X \dashrightarrow Y$ is a collection of morphisms in $Y$, $\langle x\lambda: XF \dashrightarrow xG; x \in X \rangle$ such that for any two objects $x_1, x_2$ in $X$ and each morphism $f: x_1 \dashrightarrow x_2$ in $X$ the following diagram commutes

<figure><img src="image_4.png" /></figure>

4. **Definition:** A **Constant functor** $K_X : J \dashrightarrow X$ is a functor that assigns to each object $j$ in $J$ the same object $x$ in $X$ and to each morphism in $J$ the identity $\mathrm{id}_X$ on $x$.

5. **Definition:** A **limit** of a functor $T=J \dashrightarrow X$ is an object $x$ in $X$ and a natural transformation $\lambda: K_X \dashrightarrow T$ such that if $\lambda': K_X \dashrightarrow T'$
is another natural transformation there is a unique morphism
$f=x' \to x$ such that the diagram commutes for all $j$ in $J$

<figure><img src="image_5.png" /></figure>

6. **Theorem**: Limits are unique up to isomorphism

7. **Definition**: A functor $F: X \dashrightarrow Y$ preserves the limit of a functor $T: J \dashrightarrow X$ if whenever $(x, \gamma)$ is a limit of $T$, $(xF, \gamma F)$ is a limit of the composite functor $TF$. $F$ is *J-continuous* if it preserves limits of all functors defined on $J$.

8. **Definition**: The category $\omega^{\text{op}}$ is defined by
objects: all natural numbers; 0, 1, 2, ...
morphisms: if $j \ge i$, there is exactly one morphism from $j$ to $i$;
there are no other morphisms.

Composition: if $j \ge i \ge k$, the composition of $j \to i$ with $i \to k$
is (the unique morphism) $j \to k$

**Identity**: the morphisms $i \to i, i \ge 0$.

9. **Definition**: A *terminal object* in a category $X$ is an object, denoted by $1$, such that for any other object $X$ there is a unique morphism $! : X \to 1$

10. **Definition**: Let $F: X \to X$ be a functor. The **functor of iterations of** $F$ is a functor $T: \omega^{\text{op}} \dashrightarrow X$ defined by

$$
iT = 1F^i
$$

$i \ge 0$
$(i+1 \to i) T = !F^i$

11. **Theorem:** Let $X$ be a category with terminal object $1$ and $F: X \to X$ a functor. Suppose that the functor of iterations of $F$, $T: \omega^{\mathrm{OP}} \to X$, has a limit, and that this limit is preserved by $F$. Then this limit is (the greatest) fixpoint of $F$.

**Proof:** Smyth and Plotkin (1982), Arbib and Manes (1986; p. 276, theorem 14)

12. **Definition:** A **universal arrow from an object $X$ in $X$ to a functor $G: A \to X$** is a pair $(a, f)$, with $a$ on object in $A$ and $f = x \to aG$ a morphism in $X$, such that if $(a', f')$ is any other such pair there is a unique $g: a \to a'$ such that the following diagram commutes:

<figure><img src="image_6.png" /></figure>

13. **Definition:** A **universal arrow from a functor $G: A \to X$ to an object $X$ in $X$** is a pair $(a, f)$, $f: aG \to x$, such that if $(a', f')$ is any other such pair, there is a unique arrow $g: a' \to a$ such that the following diagram commutes:
<figure><img src="image_7.png" /></figure>

14. **Definition:** An **adjunction** from category X to category A is a pair of functors

<figure><img src="image_8.png" /></figure>

and a pair of natural transformations $\eta: I_X \to FG, \epsilon: GF \to I_A$ such that

(i) for each $x$ in $X$, $(xF, x\eta)$ is a universal arrow from $x$ to $G$

(ii) for each $a$ in $A$, $(aG, a\epsilon)$ is a universal arrow from $a$ to $F$. $F$ is called a left, and $G$ a right, **adjoint functor**; $\eta$ is called the **unit**, and $\epsilon$ the **counit**, of adjunction.

15. **Theorem:** Right adjoints preserve limits

16. **Theorem:** If $<F,G,\eta,\epsilon>$ is an **adjunction** from X to A and if $x\eta$, $a\epsilon$ are isomorphisms for each x in X and each a in A, then $<G,F,\epsilon^{-1},\eta^{-1}>$ is an **adjunction** from A to X; in other words, F is both a left and a right **adjoint** of G.

17. **Definition:** A morphism $f$ in a category $X$ is
monic if $\alpha f = \beta f$ implies $\alpha = \beta$ for each $\alpha, \beta$

epic if $f\alpha = \beta f$ implies $\alpha = \beta$ for each $\alpha, \beta$

18. **Theorem**: A function $f$ is

monic if and only if it is injective

epic if and only if it is surjective

19. **theorem** if $T: J \to X$ is a functor and $x \xrightarrow{\lambda} T$ a limit of $T$, then $\lambda$ has the following **monic property**: $\alpha\lambda_i = \beta\lambda_i$ for each $i$ in $J$ implies $\alpha = \beta$

### 3. The Probability Functor is Continuous

Let $CH$ be the category of compact Housdorff spaces and continuous functions. Mertens and Zamir (1985) show that the beliefs functor $F: CH^n \dashrightarrow CH^n$ defined in section 1 has a fixpoint by constructing the limit of the functor of iterates of $F$ and showing that this limit is isomorphic to its image under $F$. Theorem 11 shows that this method will work for any functor with the appropriate continuity properties. In this section it is shown that $F$ has a much stronger continuity property than that ensuring the existence of a fixpoint: it preserves **all** $\omega^{OP}$-limits. The significance of this result will be discussed at the end of this section. To attack the problem of continuity of $F$, it is necessary to show that $F$ can be obtained from elementary continuous functors by operations that preserve continuity. To do this, it is necessary to have some facts about functor categories. Let $X$ be a category.
20. **Definition:** The category of functors from $P$ to $X$ has as objects all functors $F: P \dashrightarrow X$ and as morphisms all natural transformations between such functors. Denote this category by $[P \dashrightarrow X]$ or $X^P$

21. **Definition:** The evaluation functor at $p$ is defined by $pE: [P \dashrightarrow X] \dashrightarrow X$

$$F(pE) = pF$$

22. **Theorem (MacLane, p. 111):** If $S: J \dashrightarrow [P \dashrightarrow X]$ is a functor such that $\mathrm{Lim}(\mathrm{SpE}) = pL$ for each $p$ in $P$ then there is a unique functor $L=P \dashrightarrow X$ s.t. $\mathrm{LimS} = L$. Hence, limits in functor categories can be calculated pointwise, provided the pointwise limits exist.

23. **Corollary** if $X$ has $J$-limits so does $[P \dashrightarrow X]$.

24. **Theorem:** (MacLane, p. 121) $CH$ has all limits; hence, so does $[CH \dashrightarrow CH]$.

25. **Theorem:** Constant and identity functors are continuous; Finite tuples, compositions, and limits of continuous functors are also continuous functors.

Returning to the beliefs functor $F: CH^n \dashrightarrow CH^n$ we have $F = \langle F_1, \dots, F_n \rangle$ (finite tuple) $XF_i = \Delta(SxX_{-i}) = X(K_S \times \Pi_{-i})\Delta$ where $K_S: CH \dashrightarrow CH$ is the constant functor at $S$,

$$\Pi_{-i}: CH^n \dashrightarrow CH$$

is defined by $\Pi_{-i} = X_1 \times \dots \times X_{i-1} \times X_{i+1} \times \dots \times X_n$ and $\Delta: CH \dashrightarrow CH$ assigns to each compact set the Borel probability measures on the set (equipped with the weak* topology). Since products are special cases of limits the $\Pi_{-i}$, $i = 1, \dots, n$ are continuous functors. By 25, it suffices to show that the probability functor $\Delta$ is $\omega^{op}$-continuous in order to show that the beliefs functor $F$ is $\omega^{op}$-continuous. Theorem 25
also illustrates the significance of proving that $\Delta$ is $\omega^{\text{OP}}$-continuous: any functor obtained by compositions, limits, and finite tupling from $\Delta$ and other $\omega^{\text{OP}}$-continuous functors will also be $\omega^{\text{OP}}$-continuous and, hence, will have a fixpoint. We will now define $\Delta$ rigorously and prove that it is $\omega^{\text{OP}}$-continuous.

26. **Definition:** The category $B_1$ consists of all Banach spaces and linear maps of norm less than or equal to one between them. The category $B^*$ consists of all $B^*$ algebras and linear multiplicative, unit and involution preserving maps between them. The functor $U:B^*\dashrightarrow B_1$ assigns to each $B^*$ - algebra the underlying Banach space. (for definitions, see Rudin (1973) ch. 11)

27. **Definition:** The **opposite category of** $X$, $(X^{\text{OP}})$ has the same objects as $X$; there is a morphism $h$: $A \dasharrow B$ in $(X)^{\text{OP}}$, if and only if $h: B \dashrightarrow A$ is a morphism in $X$.

28. **Definition:** The functor $C: \text{CH} \dashrightarrow (B^*)^{\text{OP}}$ is defined by $XC = \text{set of continuous complex functions on } X$, equipped with the sup-norm topology. ($g: X \dashrightarrow X'$, $C = \text{go} : XC \rightarrow X'\mathcal{C}$ where $\mathcal{C}$ denotes composition.

29. **Definition:** The **probability functor** $\Delta$: $\text{CH} \dashrightarrow \text{CH}$ is defined by $X\Delta = (m \in \text{XC}*: 1_X^m = 1; f \ge 0 = > fm \ge 0)$ - all continuous linear (complex) functionals $m$ on $\text{XF}$ such that

(a) Their value at the function $1_X: X \dashrightarrow C$ that is constantly 1 is 1 (unit probability mass)

(b) their value on positive functions $f: X \rightarrow R_+$ is positive

Hence, by the Riesz representation theorem (Rudin (1974), p. 138) $X\Delta$ is isomorphic to the set of Borel probability measures on $X$. The
definition of $\Delta$ on morphisms is given by $g\Delta = gCU_o$; $X\Delta$ is equipped with the weak* topology.

30. **Theorem** If $\mathrm{CU}$ is $\omega^{\mathrm{OP}}$-continuous, then so is $\Delta$. $\mathrm{CU}$ is $\omega^{\mathrm{OP}}$-continuous.

**Proof:** Let $T:\omega^{\mathrm{OP}} \dashrightarrow \mathrm{CH}$ be a functor with limit $X\xrightarrow{\lambda} T$; let $Y \twoheadrightarrow T\Delta$ be a natural transformation, where $Y$ is compact Hausdorff. We have to show that there is a unique continuous function $f:Y\dashrightarrow X\Delta$ such that the following diagram commutes for each $i=0,1,\dots$

<figure><img src="image_9.png" /></figure>

or, for each $y \in Y$,

<figure><img src="image_10.png" /></figure>

which is equivalent to the following commuting diagram in $\mathrm{B}_1^{\mathrm{OP}}$

<figure><img src="image_11.png" /></figure>

The existence of $yf$ for each $y \in Y$ follows from the assumption that $\mathrm{CU}$ is
ω<sup>OP</sup>- continuous, so (XCU, λCU) is a limit of TCU. We still have to show
that f maps continuously into XΔ.

Step 1: yfεXΔ for each yεy

Proof: It has to be shown that

$$
(10) \quad (1_x)yf = 1
$$

$$
(11) \ g \geq 0 \ \text{implies} \ g(yf) \geq 0
$$

Where $1_x$: X ---> C is the constant function at 1

$$
\begin{align*}
\text{For (10), } (1_x)yf &= (\lambda_i 1_{T_i})yf = (1_{T_i} \lambda_i C)yf \\
&= (1_{T_i}) (\lambda_i C U yf) = (1_{T_i}) (yv_i) = 1
\end{align*}
$$

For (11), take g≥o in XCU; they by theorems 18 and 19, there is an i in
ω<sup>OP</sup> such that for some t<sub>i</sub> ≥ o in T<sub>i</sub>CU, g = t<sub>i</sub>λ<sub>i</sub>CU. Hence gyf = t<sub>i</sub>λ<sub>i</sub>CUyf' =
t<sub>i</sub> yv<sub>i</sub> ≥ o.

Step 2: f:Y --->XΔ is continuous.

**Proof:** XΔ has the w* topology, ie the smallest topology that makes all functionals of the form δ_t: XΔ ---→ C, mδ_t = tm, tεXC, continuous.
Hence, it suffices to show that, for each tε XF, the composite Y ---f--- XΔ ---δt→ C is continuous. Fix tε XC; then t = t_i λ_i F for some i and some t_i ε T_i. Then the following diagram commutes

<figure><img src="image_12.png" /></figure>
(1) commutes because of (8)

(2) commutes by the definitions of $\lambda_i \Delta$ and the fact that $X\Delta$ and $T_i\Delta$ are subsets of $(XC)*$ and $(T_iC)*$, the continuous linear complex functionals on $XC$, $T_iC$ respectively. Finally, (3) commutes because for each $m \in (XC)*$, $m\delta_t = tm = t_i\lambda_i Cm = (\lambda_i C) m \delta_{ti} = m[(\lambda_i C o - ) \delta_t]$. We need to show that if $\delta_t$ is continuous. From the diagram $\text{finc}\delta_t = v_i$ inc $\delta_{ti}$. The RHS of this equation is a composite of continuous functions. QED.

**Step 3:** The functor $CU:CH \dashv\dashv\dashv B_1^{op}$ is $\omega^{op}$-continuous.

**Proof:** Semadeni (1971); theorems 11.8.7 and 18.8.4

**Remark:** While $C:CH \dashv\dashv\dashv (B^*)^{op}$ is continuous (as a right adjoint), $CU$ is not, because it does not preserve products. Similarly, the probability functor does not preserve products.

**31. Theorem:** Functors obtained from the probability functor $\Delta$ and other $\omega^{op}$-continuous functors by composition, limits or finite tupling are also $\omega^{op}$-continuous. (in particular, the beliefs functor is $\omega^{op}$-continuous). Hence, any such functor has a fixpoint.

# 4. More examples of recursive definitions

## 4.1. The space of temporal lotteries and fixpoints under a given object

Let $SM$ be the category of separable, metrizable spaces and continuous maps; let $\Delta: SM \dashv\dashv\dashv SM$ be the probability functor and $L:SM \dashv\dashv\dashv SM$ the temporal lottery functor defined by

$$XL = R_+ \times X\Delta$$
$$fL = id_{R_+} \times f\Delta.$$

Interpret $R_+^\infty$ as the space of deterministic consumption streams, $X_{-1} = R_+^\infty L$ as lotteries on deterministic consumption streams, and $\pi: X_{-1}L \to X_{-1}$ in SM as the mapping that reduces lotteries on $X_{-1}$ to lotteries on $R_+^\infty$. Given any set $X$ (of lotteries) in SM, a map $f: X \to X_{-1}$ can be interpreted as reducing lotteries in $X$ to lotteries in $X_{-1}$.

2. **Definition:** The category $SM \downarrow X_{-1}$ has

**Objects:** all pairs $(X, f)$ where $f: X \dashrightarrow X_{-1}$ in SM

**Morphisms:** $\alpha: (X, f) \dashrightarrow (X', f')$ if and only if $\alpha: X \dashrightarrow X'$ is in SM and the following diagram commutes

<figure><img src="image_13.png" /></figure>

composition and identity are as in SM.

33. **Definition:** The functor $L_\pi: SM \downarrow X_{-1} \dashrightarrow SM \downarrow X_{-1}$ is given by

$$(X, f)_{L_\pi} = (XL, (fL)\pi)$$

$$\alpha L_\pi = \alpha L.$$

Epstein and Zin (1989) construct a fixpoint $(X, f)$ of the functor $L_\pi$ and call it the space of temporal lotteries. Suppose $\phi: (X, f) \dashrightarrow (XL, (fL)\pi)$ is the fixpoint isomorphism. Then by definition 32, the following diagram commutes

<figure><img src="image_14.png" /></figure>
and $\phi$ is an isomorphism in SM. Hence, the set X satisfies two properties

(a) it is a fixpoint of the temporal lottery functor L ($\phi$ is an isomorphism)

(b) the reduction of lotteries in X to lotteries in $X_{-1}$ by $f$ is identical to the composition of three reductions: lotteries in X to lotteries on X, lotteries on X to lotteries on $X_{-1}$, lotteries on $X_{-1}$ to lotteries in $X_{-1}$

Given that the last reduction, namely $\pi$, is a parameter of the model, we have constructed a fixpoint X of L that maps into the space of interest $X_{-1}$ "in the same way" that $\pi$ does. Call X a fixpoint under the given object $X_{-1}$. For a general existence theorem for fixpoints under a given object, let K be a category, $X_{-1}$ in K, $L:K \dashrightarrowdot K$, $\pi: X_{-1}L \dashrightarrowdot X_{-1}$ in K and define the category. $K \downarrow X_{-1}$ and the functor $L_\pi: K \downarrow X_{-1} \dashrightarrowdot K \downarrow X_{-1}$ as in definitions 32 and 33, replacing SM by K.

**34. Theorem:** If K has a terminal object, so does $K \downarrow X_{-1}$; if the functor of iterations of L has a limit which is preserved by L, then so does $L_\pi$. Hence, if both conditions are satisfied, both L and $L_\pi$ have a fixpoint.

**Proof:** Smyth and Plotkin (1982) pp. 766-767

**35. Theorem:** The temporal lottery functor has a fixpoint under $X_{-1}$ if the probability functor $\Delta:SM\dashrightarrowdot SM$ is $\omega^{\text{OP}}$-continuous

**Proof:** Theorems 34 and 35

**36. Definition:** The functor $\mathcal{B}:SM\dashrightarrowdot (\mathcal{B}*)^{\text{OP}}$ is defined by

$\mathcal{X}\mathcal{B} = \text{all bounded continuous functions on X, equipped with the sup-norm topology}$
$fB = fo$ -

37. **Definition:** The probability functor $\Delta:SM\dashrightarrow SM$ is defined by $\Delta X\Delta$ = all positive linear functionals $m$ on $XBU$ that preserve the unit of $XBU$, have norm less than or equal to one and satisfy.

(a) for each $\epsilon>0$, there is a compact $K$ in $X$ such that if $g\in XBU$ is zero on $K$ then $|gm| \le \epsilon|g|$

(b) if $g_0 \ge g_1 \ge g_2 \ge \dots \ge o$ in $XBU$ are such that

$\lim_{n \to \infty} xg_n = 0$ for each $x \in X$, then

$\lim_{n \to -\infty} zm = 0$

On morphisms, $\Delta$ is defined by $f\Delta = fBUo$

By theorem 2 in p. 319 of Gihman and Skorohod (1974) $X\Delta$ is isomorphic to the set of all regular Borel probability measures on $X$; $X\Delta$ is equipped with the weak* topology.

38. **Theorem:** Let $\lambda: X\dashrightarrow T$ be a limit of a functor $T: \omega^{\Delta op}\dashrightarrow SM$; let $\Lambda: TBU\dashrightarrow K_C$ be a natural transformation with each $\Lambda_i: T_iBU \dashrightarrow C$ in $T_i\Delta$. Then there exists a unique $\Lambda: TBU\dashrightarrow C$ in $X\Delta$ such that the following diagram commutes for each $i$

<figure><img src="image_15.png" /></figure>

**Proof:** Dellacherie et Meyer (1974), theorem 53

39. **Theorem:** The probability functor $\Delta: SM\dashrightarrow SM$ is $\omega^{\Delta op}$-continuous

**Proof:** Let $T: \omega^{\Delta op}\dashrightarrow SM$ have limit $\lambda: X\dashrightarrow T$; let $v: Y\dashrightarrow \Delta$ be a natural transformation. It has to be shown that there is a unique continuous function $m: Y\dashrightarrow \Delta$ such that the following diagram commutes for all $i$ in $\omega^{\Delta op}$
21

<figure><img src="image_16.png" /></figure>

Equivalently, for each $i \in \omega^{OP}$ and each $y$ in $Y$, the following diagram in $B_1$ has to commute

<figure><img src="image_17.png" /></figure>

By the 38, $ym$ exists, is unique and belongs to $X\Delta$ for each $y \in Y$. To show that $m$ is continuous repeat step 2 in the proof of No. 29.

40. **Remark:** The probability functor is not continuous because it does not preserve products: in general $\Delta(X_1 \times X_2)$ in larger than $\Delta(X_1) \times \Delta(X_2)$.

## 4.2. Universal Choice Spaces

Consider an agent who has to choose an action in a set $A$. Suppose that the reasoning ability of this agent is limited; then, we cannot automatically assume that the agent chooses an action by optimizing some objective function, since $A$ might be too large or the objective function too complicated (typically, $A$ will consist of bundles of commodities defined by their physical characteristics and the time, location and state of nature of their availability). A popular response to this problem has been to assume that choices over $A$ are made by a finite automaton, where the type of automaton used is
determined by optimization over the set of finite automata. (Rubinstein (1986)). There are two obvious objections to this approach: optimization over automata might be more difficult than optimization over A; and optimization over automata that choose automata that choose actions might be a more efficient use of the agent's limited reasoning abilities. More generally, the agent can use his limited reasoning abilities in order to choose an element from *any* choice set that, directly or indirectly, leads to a choice over A. Hence, we need to model the agent as choosing over a *universal choice set*, i.e. a choice set that includes not only A but also programs that think about A, program that think about programs that think about A... and so on ad infinitum.

The usual objection that arises at this point is that the construction of a universal choice set is much more difficult than optimizing over A; hence, if an agent with limited reasoning ability cannot optimize over A, then he cannot construct the universal choice set. It is clear though, that this is a methodological misunderstanding: it is the economist who constructs the universal choice set in order to capture formally the fact that agents are free to apply their limited reasoning abilities to *any* choice problem, *including* the problems of how to choose over A, how to choose over procedures that choose over A, etc.

Let K be the base category and let A be an object in K. The object of K are to be interpreted as (abstract) sets and the morphisms as programs that transform instructions in their domain into outputs in their range. The reasoning abilities of the agent are represented by a
functor $P:K--\rightarrow K$ that assigns to each object $X$ in $K$ all programs the agent can use to think about $X$; given our interpretation of morphisms in $K$ as programs, it is clear that $XP$ ought to be (some subset of) the morphisms from $X$ to $X$; to define $L$ on morphisms precisely we will have to be more specific about the base category $K$, so we will present the definition after we have concluded the exposition of the fixpoint problem. At this point we need to define colimits, a concept dual to that of a limit.

**Definition:** A colimit of a functor $T:J--\rightarrow K$

is an object $X$ in $K$ and a natural transformation $\lambda:T--\rightarrow X$ such that if $\lambda':T--\rightarrow X'$ is any other natural transformation from $T$ to $X'$ then there is a unique morphism $f:X--\rightarrow X'$ such that the following diagram commutes

<figure><img src="image_18.png" /></figure>

**Definition:** A coproduct is a colimit of a functor $T:J--\rightarrow K$ defined on a discrete category $J$, i.e. a category with identity morphisms only. In Set, coproduct is disjoint union. The coproduct of two objects $x, y$ is denoted by $x + y$.

**Definition:** The choice functor $F:K--\rightarrow K$ is defined by $XF = A + (X \times XP)$ or $F = K_A + (I \times P)$ where $K_A$ is the constant functor at $A$ and $I$ is the identity functor. On morphisms, $F$ is defined as follows: if $f: X--\rightarrow X'$ in $K$ then $fF: XF --\rightarrow X'F$ is given by $fF = \text{id}_A + (f \times fP)$.

This definition captures precisely the idea that the agent can choose to apply his reasoning abilities at any level: given any set $X$,
the agent can either ignore it and pick an action in A directly, or
pick an instruction in X and a program on X whose outcome (interpreted)
will tell him which action in A to pick. Hence, roughly speaking, XF
is the choice set generated from X; in other words, if the economist
specified X as the choice set, then his specification is incomplete
unless X includes XF.

**Definition:** An *interpretation in A* is a pair (X, f) where X is an object in K and f: X --> A a morphism in K.

**Definition:** A morphism from interpretation (X, f) to interpretation (X', f') is a morphism g: X --> X' in K such that the following diagram commutes

<figure><img src="image_19.png" /></figure>

**Definition:** The category (K↓A) of interpretations in A consists of all interpretations in A and their morphisms (this is an example of a comma category, see MacLane (1971) p.46).

Interpretations should be thought of as translating programs
outcomes in X into actions in A.

**Definition:** An *evaluation morphism into A* is a morphism from A × AP to A.

**Definition:** The agent's evaluation morphism into A is a given morphism ev: A × AP --*-> A. In case P is defined as a function - space functor (i.e., XP = [X---->X] = morphisms from X into X), then ev is the usual
evaluation function that assigns to each object in A and each function on A the value of the function at that object. To make this applicable in general categories we need the concept of a cartesian-closed category.

**Definition:** K is cartesian-closed if

(i) K has finite products

(ii) K has a terminal object

(iii) for each $Y$ in K, the functor $-xY:K\dashrightarrow K$ has a right adjoint, which is denoted by $(-)^Y:K\dashrightarrow K$

**Remark:** If $\varepsilon_Y: (-)^Y(- \times Y) \dashrightarrow I$ is the counit of this adjunction, then for each $B$ in K and each $f: X \times Y \dashrightarrow B$ there is a unique $f': X \dashrightarrow B^Y$ such that the following diagram commutes:

<figure><img src="image_20.png" /></figure>

Hence, the counit of this adjunction behaves like an evaluation function.

**Definition:** If K is Cartesian-closed and

$P:K\dashrightarrow K$ if defined by

$$XP = X^X (= [X \dashrightarrow X])$$

then the evaluation morphism into A will always be defined as the A-component of the counit $\varepsilon_A$

$$A^A \times A \dashrightarrow A.$$
The idea is that $X^X$ behaves like an ordinary function space $[X \dashrightarrow X]$ in the category of sets and the counit behaves like an ordinary evaluation function. See Arbib and Manes (1986) Ch. 13 or MacLane (1971) p.95 for more details

**Definition:** the **interpretation functor** $R:K\downarrow A \dashrightarrow K\uparrow A$ assigns to each interpretation $(X, f)$ of $X$ in $A$ an interpretation $(XF, (fF)(i_A + ev))$ of $XF$ in $A$, and to each morphism $g$ of interpretations its image $gF$ under $F$.

**Definition:** A **universal choice space** (for the agent defined by $(A,K,P,ev)$) is a fixpoint of the interpretation functor $R$, i.e. an interpretation $(X,F)$ and an isomorphism $\phi: (X,f) \dashrightarrow (X, f)R$ in $K\downarrow A$

<figure><img src="image_21.png" /></figure>

Since $X \approx A + (X \times XP)$, $X$ satisfies the required property: it is a set isomorphic to the basic choice set union all instruction/program pairs on $X$, i.e. isomorphic to the choice set generated by $X$. Hence $X$ is a
complete description of the choices open to the agent. Moreover, $f: X \rightarrow A$ is an interpretation of $X$ in $A$ that agrees with $ev$.

**Theorem:** If $K$ is $\omega^{\text{OP}}$-complete and $F$ is $\omega^{\text{OP}}$-continuous, then $R$ has a (greatest) fixpoint, obtained as a limit of the functor of iterations:
$$ A \leftarrow \dots \leftarrow \alpha \dots \leftarrow \alpha F \dots \leftarrow F^2 \dots \leftarrow F^3 \dots \leftarrow A $$

where $\alpha = \text{id}_A + ev$

*Proof:* Smyth and Plotkin (1982) p. 766.

**Theorem:** There exists a Cartesian closed category $K$ and a subcategory $L$ of $K$ with the same objects as $K$ such that

(i) There is a functor $P:L\to L$ whose definition on objects is
$$ XP = X^X = \text{morphisms from } X \text{ to } X \text{ in } K $$

(ii) $K, L$ have $\omega^{\text{OP}}$-limits; $\omega^{\text{OP}}$-limits in $L$ are $\omega^{\text{OP}}$-limits in $K$

(iii) The terminal object of $K$ is terminal in $L$.

(iv) $P$ is $\omega^{\text{OP}}$-continuous

(v) Polynomial functors $L\to L$ and $K\to K$ are $\omega^{\text{OP}}$-continuous (a polynomial functor arises from constant and identity functors by the operations of composition, product and coproduct).

*Proof:* Arbib and Manes (1986) ch. 13, Smyth and Plotkin (1982). The original construction is due to D. Scott (1976).

**Remark:** If $P$ is $\omega^{\text{OP}}$-continuous then so is $F$, since $F = K_A + (I \times P)$ and $K_A$, $I$ are continuous functors (see No. 25)

**Remark:** The category $K$ in theorem cannot be $\text{Set}$, for obvious cardinality reasons; it is the category of domains and continuous functions. The category $L$ has the same objects as $K$ but the morphisms are continuous functions that preserve least elements and have an adjoint. For definitions, see the references above.
**Remark:** Suppose that the agent modelled by the 4-tuple <K, P, A, ev>
is able to perform calculations on the natural numbers ω and that we
want to include this fact in the modelling of his reasoning abilities
by the functor P; then define XP' = [ω + X --- → ω + X]. P' is still ω<sup>OP</sup>-continuous, since P' = (K<sub>ω</sub> + I) P and K<sub>ω</sub>, I, P are ω<sup>OP</sup>-continuous.
Similarly if V<sub>i</sub>, i ∈ I are domains on which the agent knows how to
calculate, we can include them in the specification of the reasoning
functor without affecting ω<sup>OP</sup>-continuity.

**Remark:** Lipman (1989) approaches the same problem without using
category theory, and his construction is technically different, but the two approaches are clearly in the same spirit, and Lipman's precedes mine. Another approach in the same spirit but less complete technically is Mongin et Walliser (1988).

**Remark:** A more realistic modelling of the agent's reasoning abilities would require to consider nondeterministic programs (thought processes): Such a program can be thought of as a **multifunction** $f: X \to X$, where $xf$ is the **set** of possible outcomes of program $f$ receiving instruction $x$. Hence, if $2^X$ is the set of subsets of $X$, the construction of a universal choice set involves solution of equations of the form $X \approx A + [X \to 2^X]$; this equation cannot be solved in Set, but it does have a solution in a suitable category of domains (Plotkin (1976), Smyth (1978). The details are omitted since they will be developed in a subsequent paper.

### 3. Common Knowledge functors as colimits in functor categories.

**Definition:** Let $E$ be a **category of events** and $K_i: E \dashrightarrow E$ the **knowledge functor of agent i**: $FK_i$ is interpreted as the event "i knows F".

**Definition:** Let $|\omega|$ be the category of natural numbers with no morphisms except from identities. The functor $T: |\omega|^n \dashrightarrow [E \dashrightarrow E]$ is defined by

$$ (i_1, i_2, \dots, i_n)T = K_1^{i_1} K_2^{i_2} \dots K_n^{i_n} $$

**Definition:** The functor $K: E \dashrightarrow E$ is defined as a colimit of $T$

**Theorem:** $K$ exists if $E$ has $|\omega|^n$ colimits

**Proof:** MacLane (1971) pp. 111-112

**Remark:** For each event $F$, $FK$ can be thought of as the event that includes **all** events of the form "i knows that j knows that F" (no
confusion condition) and _only_ those events (no junk condition).

Categorically, these conditions are expressed in the definition of a colimit: the no confusion condition is given by the fact that all functors $K_1^i, \dots, K_n^i$ map into K, and the no junk condition by the fact that K is the _smallest_ functor with this property, in the sense that if another functor K' satisfies the same property there is a unique natural transformation $K' \dashv\dashv\dashv K$ such that the "injections" of the functors $K_1^i, \dots, K_n^i$ into K' can be recovered by composing with v the "injections" of the functors $K_1^{i_1}, K_2^{i_2}, \dots, K_n^{i_n}$ into K'.

**Definition:** Let J be a category with

**Objects:** $|\omega|^n U_1$

**Morphisms:** for each $(i_1, i_2, \dots, i_n)$ in $|\omega|^n$

there is a unique morphism $(i_1, i_2, \dots, i_n) \to 1$.

There are no other morphisms (except identities).

**Definition:** Let $L: J \to [E \to E]$ be defined

**on objects** by $(i_1, i_2, \dots, i_n)L = \bigwedge_{1L=K} K_1^{i_1} \wedge \dots \wedge K_n^{i_n}$

**on morphisms** by $(i_1, i_2, \dots, i_n)L = K_1^{i_1} K_2^{i_2} \cdots K_n^{i_n} \stackrel{\lambda}{\dashv\dashv\dashv K}$

where $\lambda: T \to K$ is the colimit natural transformation involved in the definition of K; $\lambda_1, \dots, \lambda_n$ "injects" $K_1^i, K_2^i, \dots, K_n^i$ into K.

**Definition:** A _common knowledge functor_ $K^\infty: E \to E$ is a limit object of the functor L.

**Theorem:** $K^\infty$ exists if E has J - limits (such limits are called pullbacks)

**Remark:** $K^\infty$ attaches to each event F the event $FK^\infty$ "it is common knowledge that F". It is constructed as the "intersection" of the
functors $K_1^{i_1}, K_2^{i_2}, \dots, K_n^{i_n}$.

The procedure we have described works in general: first, minimally embed the objects of interest in an object by taking a colimit; second, construct the maximal object that can be embedded into the objects of interest and in their colimit by taking a pullback of the injections of the objects of interest into the colimit object. The maximal object obtained is the "intersection" of the objects of interest.

**Remark:** Constructions in functor categories are sometimes called constructions of *parametric* data types; an ordinary data type construction would be "it is common knowledge that F" while a parametric construction is "it is common knowledge that __" where the blank is filled with any event of interest.

## 5.4 Universal state spaces

Let S be an object in E that is taken to be the set of states of nature that exhaust extrinsic uncertainty, i.e. uncertainty that does not involve the agents' knowledge. A universal state space F should include both S and all possible states of knowledge of agents about S and F. Hence

**Definition:** A **universal state space** is the least fixpoint of the functor $M = K_S + K + K^\infty$: $E \dashrightarrow E$ that assigns to each event F the event $S + FK + FK^\infty$

**Definition:** $\phi$ is an **initial object of E** if for each object F in E there is a unique morphism $\phi: F \to S$

**Definition:** The category $\omega$ has objects and morphisms given by the following diagram $\omega \dashrightarrow 1 \dashrightarrow 2 \dashrightarrow 3 \dashrightarrow \dots$
**Definition:** The functor of iterations of M, $T:ω^→E$, is defined by the following diagram

<figure><img src="image_22.png" /></figure>

**Theorem** If E has an initial object and colimits of functors $T:ω^→E$, and if M preserves these colimits, then M has a fixpoint (the least fixpoint); this fixpoint is obtained as the limit of the functor of iterations of M.

**Proof:** Arbib and Manes (1986) ch. 11

**Theorem:** If each $K_i:E^→E$, $i = 1, 2, ..., n$ is ω-continuous then so are $K, K^∞$ and M; hence, a universal state space exists.

**Proof:** See theorem 25

**Remark:** a noncategorical construction of a universal state space is in Shin (1988); this dissertation also contains several different interpretations of the functors $K_i$ (implicitly). The continuity of these functors is an open problem.

### 5.5. Universal Mechanisms

In what follows, we discuss games of complete information in normal form, but it should be obvious that the problems, and the solutions, are valid in any class of games.

Consider a typical application of game theory in economics: oligopoly a la Cournot. The economist decides, on a priori grounds, that the strategic variables available to firms are quantities produced, and that the outcome function is the inverse demand function. Then payoff functions are defined in terms of the outcome function (profit functions) and a solution concept (Nash) is applied to generate
an equilibrium outcome. If the equilibrium outcome is considered unsatisfactory for some reason, new strategy sets and outcome functions are proposed, for the *same underlying economy*. Examples are numerous and familiar: Bertrand competition, competition in supply functions (Grossman, 1981), collusion, competition with monetary bids and physical supplied (Dubey and Shubik, 1977), competition in multistage games (Kreps and Scheinkman, 1982; Dixon (1986), competition through contracts with customers (Aghion and Bolton (1986)), etc. The sensitivity of equilibrium outcomes to the specification of strategy spaces and outcome functions (always for the *same* underlying economy) renders game theory rather ineffective as a machine generating falsifiable predictions. The difficulty lies in the fact that strategy spaces and outcome functions are *endogenous* (except at the most primitive physical level). If we try to determine strategy spaces and outcome functions as equilibrium outcomes of some game, though, we immediately have an infinite regress problem, since in *any* game strategy spaces and outcome functions are endogenous. Hence, we need to construct a game whose strategy spaces include all possible revisions of the rules of the game.

The same problem arises in mechanism design: it is always assumed that a single individual, the principal, can commit himself to a game *and* play in the game, while the remaining individuals (agents) can only play in the game announced by the principal. In most situations, however, the agents can announce mechanisms of their own: for example, the theory of the firm cannot be considered as a mechanism design problem because "agents can enter into side contracts with each other"
(Holmstrom and Tirole (1987). But if we allow all players to compete with mechanisms, we have an infinite regress problem: we need a mechanism whose outcomes are actions, a mechanism whose outcomes are mechanisms whose outcomes are actions and so on ad infinitum. (see also Crawford (1985) p. 823). Again, strategy spaces have to be *complete*, i.e. they must contain *all* strategies available to agents, including proposals for altering the rules of *any* game.

Finally, in the literature on property rights and institutions, a distinction is made between rules of the game that express physical laws and cannot be changed by human action, and rules that express legal constraints on actions and are, therefore, subject to change. In Gardner and Ostrom (1989) there is an example that illustrates the problem. In a fishing game, the physical rules are those that link outcomes (amount of fish caught) to actions (presence in a fishing area, fishing activity, damage imposed on, or suffered by, rival fishermen). The legal rules are those restricting the kind of actions fishermen can take; for example, only the highest bidder in some bidding game can fish in a given area; or, alternatively, fishing rights are allocated on a "first-in-time, first-in-right" basis. The infinite regress problem arises because we need a game in which (proposed) legal rules are strategies and (actual) legal rules are outcomes; the outcome function of this game is determined in another game where (proposed) outcome functions are strategies and (actual) outcome functions are outcomes, etc. The infinite regress problem is resolved if we can find strategy spaces that contain both the actions of the fishermen and *all* possible proposals of changing the rules that
restrict those actions and _all_ the outcome functions that can be used
to select among proposals and...

**Definition:** Let J be the category of _players_ whose objects are (names of) players and whose morphisms are to be thought of as abstract relations between agents.

**Definition:** A collection of _strategy spaces_ is a functor $S:J\dashrightarrow K$ mapping into the base category K.

The aggregate strategy space is usually defined as the product

$S_1 \times S_2 \times \dots \times S_n$; with an eye to future developments, we will define the aggregate strategy space as the limit of S (which is always a subobject of the product). To do this, we need to define the functor $\ Lim : K^J \dashrightarrow K $; since the limit is the product whenever J has only identity morphisms, we gain considerable generality without increasing the complexity of definitions or proofs.

**Theorem:** The functor $\ Lim: K^J \dashrightarrow K$ that associates to each functor $S:J \rightarrow K$ a specified limit object $SLim$ is a right adjoint to the functor $\Delta:K \rightarrow K^J$ that associates to each object $x$ in $K$ the functor $x\Delta:J \dashrightarrow K$ "constant at $x$".

*Proof:* Mac-Lane (1971) p.86.

**Definition:** The aggregate strategy space generated by $S:J \dashrightarrow K$ is $SLim$.

**Definition:** A _mechanism_ is a triple (S, f, X) where f:SLim ---*→* X; X is the outcome space and f the outcome function. (both in K)

**Definition:** The _primitive mechanism_ is a triple (A, α, O); it captures the physical laws of the situation modelled.

**Definition:** The (individual player's) _revision functor_ is
$R_i: K^J \times K \dashrightarrow K \times K$ defined by $(S, X)R_i = (S', X')$ where
$X' = [SLim ---\to X]$ = new outcome space

$S' = X' \times [X'\Delta Lim ---\to X']$. = new strategy space for each i.

R captures precisely the abilities of each player to propose
outcome functions $f:SLim ---\to X$; the player can suggest an outcome
function $h:X'\Delta Lim---\to X'$ that takes

J - tuples of proposed outcome functions (from SLim to X) and selects
one and propose an outcome function SLim ---\to X.

**Definition:** The aggregate revision functor $R:K^J \times K \dashrightarrow K^J \times K$ is defined by $(S,X)R = (S'\Delta X')$, where $(S',X') = (S, X)R_i$

**Definition:** A *universal mechanism* is a mechanism (S, f, X) such that
(S,X) ≈ (A,O) + (S,X)R.

The meaning of the fixpoint equation is that a strategy is either
a primitive or a revision strategy for each agent i

$S_i \approx A_i + X' \times [X' \Delta Lim \to X']$

$X' \approx [SLim \to X]$

and that an outcome is either a primitive outcome or an outcome of the
revision mechanism

$X = O + [SLim ---\to X]$

**Theorem:** There exists a Cartesian-closed category K and a subcategory L of K with the same objects as K such that

(i) There is a functor $\to: L \times L \to L$ defined on objects by
$\langle X, Y \rangle \to = [X \to Y] = \text{morphisms from X to Y in K.}$

(ii) K and L have $\omega^{OP}$-limits; $\omega^{OP}$-limits in L are $\omega^{OP}$-limits in K.

(iii) $\to$ is $\omega^{OP}$-continuous.

(iv) The terminal object of K is terminal in L.

(v) Polynomial functors $L \to L$ and $K \to K$ are $\omega^{OP}$-continuous.
**Proof:** Arbib and Manes (1986) ch. 13, Smyth and Plotkin (1982).

**Corollary:** A universal mechanism exists

**Proof:** $(S, X)$ is defined as a fixpoint of a functor defined by continuity-preserving operations on $\omega^{\text{op}}$-continuous functors $(\text{Lim}$ is continuous as a right adjoint). The outcome function $f:\text{SLim} \dashrightarrow X$ is arbitrary.

**Corollary:** If $(S, X, f)$ is a universal mechanism there is a unique outcome function $f': S'\text{Lim} + A \dashrightarrow X' + O, (S', X') = (S, X)R$ that is consistent with $f$, in the sense of making the following diagram commute

<figure><img src="image_23.png" /></figure>

where $\phi:S' + A \dashrightarrow S$ and $g:X' + O \dashrightarrow X$ are the fixpoint isomorphisms

**Proof:** $f' = (\phi\text{Lim})f g^{-1}$.

Hence, $f$ extends uniquely to an outcome function on the proposed revisions of $f$. The obvious way to define uniquely $f$, then, would be to define a solution concept and payoff functions and require that the equilibrium outcome of the mechanism $(S' + A, X' + O, f')$ is $f$. This is indeed possible; infact, much more is possible. One can postulate a functorthat generates a solution concept from each outcome function, in the same sense that a solution concept for $(S' + A, X' + O, f')$ generates an outcome function, and then require that **both** the outcome function and the solution concept are self-generating (i.e., they
constitute a fixpoint of the revision functor). This construction will
be presented in another paper.

5.6. <u>Universal Commodity Spaces</u>

It should be clear from the previous constructions that a
universal commodity space exists because the function - space functors
B and P are ω<sup>OP</sup>--continuous in the appropriate category K of domains
and continuous functions with an adjoint.

5. <u>Some applications of Free Constructions</u>

The material in this capter is speculative, and will be developed
in subsequent papers.

5.1.. *Implementation Theory*

Let A be a category of outcomes, M a category of mechanisms and E
a category of environments; a choice functor is a functor T = E->A; a
solution concept is a functor G:M-->A<sup>E</sup>; a mechanism TF in M minimally
impliments the choice functor T if there is a morphism Tη: T-->TFG
such that (TF, Tη) is a universal arrow from T to G and Tη is an
isomorphism, while TF in M maximally implements T if there is a
morphism Tε:TFG-->T such that (TF, Tε) is universal from G to T and Tε
is an isomorphism. To understand the terms "minimally implements" (or
"maximally implements") suppose that (TF,Tη) is universal from T to G
and that mεM is a mechanism while α: T-->mG is a natural transformation.
Then by the definition of universality, there is a unique morphism of
mechanisms f: TF -->m such that the diagram commutes

<figure><img src="image_24.png" /></figure>
The idea is that if there exists $\alpha: T \dashrightarrow mG$ then $m$ is a candidate mechanism for implementing $T$; TF actually implements $T$, since $T_\eta$ is an isomorphism, and can be mapped consistently into any candidate mechanism $m$.

## 2. (Kan) Extensions of Solution Concepts

In Harsanyi and Selten (1988) we observe the following process of constructing solution concepts: first pick a category $G$ of "primitive" games and a category $A$ of outcomes; then define a solution concept $N:G \dashrightarrow A$ which is generally acceptable for this category of games; then extend this solution concept to a large category of games $G'$ that contains $G$. Kan extensions provide a systematic method for doing this, which is applicable in categories of games not considered by Harsanyi and Selten; on the other hand, no claim is made here that their method of extension is a Kan extension, or even categorical.

Let $K:G \dashrightarrow G'$ be a functor that embeds $G$ into $G'$. Then, a left Kan extension of $N:G \dashrightarrow A$ along $K$ is a universal arrow $(NF, N_\eta)$ from $N$ to the functor $Ko::A^{G'} \dashrightarrow A^G$, i.e. a solution concept $NF:G' \dashrightarrow A$ and a natural transformation $N_\eta: N \dashrightarrow K(NF)$ such that if $\alpha:N \dashrightarrow KS$ is another natural transformation $(S:G' \dashrightarrow A)$ then there is a unique $\beta:NF \dashrightarrow S$ such that the following diagram commutes

<figure><img src="image_25.png" /></figure>

Hence

(i) $NF: G' \dashrightarrow A$ extends $N:G \dashrightarrow A$
(ii) NF is the minimal extension of N in the sense that it can be
embedded into any solution concept S:G'---A that extends N.
Similarly, the concept of right Kan extension constructs the maximal
extension of N to G'

Conclusions
---

This paper has attempted to show that economic problems that, at
first sight, seem to involve an unmanageable infinite regress can be
solved by categorical techniques: limits, adjunctions, fixpoints of
functors. The economic problems solved for the first time are the
constructions of universal commodity, choice<sup>1</sup>, state<sup>2</sup>, and strategy
spaces. Universal beliefs and lottery spaces were constructed again,
and provided the motivation for two mathematical results on the
continuity of probability functors. The insistence on proving
continuity of functors instead of adhoc constructions of fixpoints was
justified on the grounds that continuous functors can be combined by
very general continuity-preserving operations on functors (limits,
tupling, some form of colimits in some categories). Applications
mentioned in the paper include the construction and extension of
solution concepts and implementation theory. The general theme of the
paper can be summarized in a slogan: objects of interest to economists
are fixpoints or limits of functors, or universal arrows. The paper
has only scratched the surface of this large research area: the
construction and study of knowledge functors, languages with self-
reference for modelling communication (see Perlis (1985)), self-
consistency properties of solution concepts (McLennon, 1985, Peleg,
1985), self-generating sets in dynamic programming and dynamic games
(Abreu, Pearce and Stacketti, (1986) are just a few of the already published possible applications of categorical methods in the construction of fixpoints. Another subject of interest is the imposition of further restrictions on objects obtained as fixpoints of functors to obtain objects that are also fixpoints; see Epstein and Zin (1989) and Tan and Werlang (1985) for some examples. Examples of constructions that are, explicitly or implicitly, universal arrows include Sonnenschein (1974), Sinclair-Desgagne' (1989) and Green (1989) Of equal importance are constructions of morphisms (as opposed to objects) by recursive methods. Given the importance of these methods in the study of program semantics (Arbib and Manes, 1986) and programming languages (Goguen and Burstal, 1984) one can expect that they will be useful in constructing theories of bounded rationality. Noncategorical recursive constructions of morphisms have appeared in Marcet and Sargent (1989) and their references.

Finally, one can even construct categories that satisfy certain internal properties (i.e. they contain objects and morphisms that satisfy certain restrictions) as opposed to constructions by limit or fixpoint that refer to external properties (i.e. relations between the constructed category and other categories). These constructions are important in model theory (construct a mathematical model in which certain laws are satisfied, and therefore show, among other things, that these laws are consistent). For general references see Barr and Wells (1985) chapters 4 and 8; for applications in the calculus of variations see Kock (1981); for an economic application not explicitly categorical, see Green (1989).
References

1. Abreu, D. et.al. (1986): Optimal Cartel equilibria with imperfect monitoring. Jet, 39, 251-269.

2. Aghion, D. and Bolton, P. (1985) Entry Prevention through Contracts with Customers. Mimeo, MIT.

3. Arbib, M. and Manes, E. (1986): Algebraic Approaches to Program Semantics. Springer.

4. Barr, M. and Wells, C. (1984): Toposes, Triples and Theories. Springer.

5. Crawford, V. (1985): Efficient and Durable Decision Rules: A Reformulation. Econometrica, 53, 1431-1451.

6. Dellacherie, C. and Meyer, P. A. (1978): Probabilities and Potential. North Holand.

7. Dubey, P. and Shubik, M. (1977): A Closed Economic System with Production and Exchange Modelled as a Game of Strategy. Journal of Math Economics, 4, 253-287.

8. Epstein, L. and Zin, S. (1989): Substitution, Risk Aversion, and the Temporal Behavior of Consumption and Asset Returns. Econometrica, 57, 4, 937-969.

9. Gardner, R. and Ostrom, E. (1989): Rules and Games. Public Choice.

10. Gihman, I. and Skorohod, A. (1974): Theory of Stochastic Processes. Springer.

11. Green, E. (1989): "Individuals-level Randomness in a Nonatomic Population. University of Pittsburgh, W. P., 227.

12. Grossman, S. (1981): Nash equilibrium and the Industrial Organization of Markets with Large Fixed Costs. Econometrica, 49, 1149-1172.

13. Goguen, J. and Burstal, R. (1984): Some Fundamental Algebraic Tools for the Semantics of Computation. Theoretical Computer Science, 31, 175-209.

14. Harsanyi, J. and Selten, R. (1988): A Theory of Equilibrium Selection in Games. MIT Press.

15. Holmstrom, B. and Tirole, J. (1987): Theory of the Firm. Mimeo.
16. Kock, A. (1981): Synthetic Differential Geometry. London Mathematical Society, monographs.

17. Kreps, D. and Scheinkman, J. (1983): Quantity Precommitment and Bertrand Competition yield Cournot Outcomes. Rand Journal of Economics, 14, 326-337.

18. Lipman, B. (1989): How to Decide How to Decide How to ... , Mimeo. Carnegie-Mellon University.

19. MacLane, S. (1971): Categories for the Working Mathematician. Springer.

20. MacLennan, A. (1985): Subgame Form Perfection. Mimeo.

21. Marcet, A. and Sargent, T. (1989): Convergense of least Squares Learning Mechanisms in Self-Referential Linear Stochastic Models. Jet, 48, 337-368.

22. Mertens, J. F. and Zamir, S. (1985): Formulation of Bayesian analysis for Games of Incomplete Information. Int. Journal of Game Theory, 1-31.

23. Mongin, P. and Walliser, B. (1988): Infinite Regressions in the Optimizing Theory of Decision. in B. Munier (ed.): Risk, Decision and Rationality; Reidel.

24. Peleg, B. (1985): An Axiomatization of the Core of Market Games. Mimeo, Hebrew University.

25. Perlis, D. (1985): Language with Self-reference. Artificial Intelligence, 25, 301-322 and 34, 179-212.

26. Plotkin, G. (1976): A Power Domain Construction. Siam Journal of Computing, 5, 452-487.

27. Rubinstein, A. (1986): Finite Automata play the Repeated Prisoner's Dilemma. Jet, 39, 83-96.

28. Rudin (1973): Functional Analysis. McGraw-Hill.

29. Rudin (1974): Real and Complex Analysis. McGraw-Hill.

30. Scott, D. (1975): Date Types as Lattices. Siam Journal of Computing, 5, 522-587.

31. Shin, H. S. (1988): A Study of Information and Common Knowledge. D. Phil, Oxford.

32. Sinclair, Desgagne, B (1989): The Robustness of Auctions. Mimeo, INSEAD.
33. Semadeni, Z. (1971): Banach Spaces of Continuous Functions. PWN.

34. Smith, A. (1976): Wealth of Nations.

35. Smyth, M. and Plotkin, G. (1982): The Category Theoretic Solution of Rercursive Domain Equations. Siam Journal of Computing, 11, 4, 761-783.

36. Smyth, M. (1978): Power Domains. Journal of Computer and System Sciences, 23-36.

37. Sonnenschein, H. (1974): An Axiomatic Characterization of the Price Mechanism. Econometrica, 42, 425-433.

38. Tan, T. and Werlang, S. (1986): Bayesian Foundations of Solution Concepts of Games. Mimeo, Princeton University.

39. Young, A. (1928): Increasing Returns and Economic Progress. Economic Journal.