This is the twelfth and final post in the Cartesian Frames sequence. Read the first post here.

Up until now, we have (in the examples) mostly considered agents making a single choice, rather than acting repeatedly over time.

The actions, environments, and worlds we've considered might be extended over time. For example, imagine a prisoner's dilemma where "cooperating" requires pushing a button every day for five years.

However, our way of discussing Cartesian frames so far would treat "push the button every day for five years" as an atomic action, a single element $a\in A$. 

Now, will begin discussing how to use Cartesian frames to explicitly represent agents passing through time. Let us start with a basic example.

1. Partial Observability

Consider a process where two players, Yosef and Zoe, collaboratively choose a three-digit binary number. Yosef first chooses the first digit, then Zoe chooses the second digit, then Yosef chooses the third digit. The world will be represented by the three-digit number. The Cartesian frame from the perspective of Yosef looks like this:

$C_0=\left(\begin{array}{cccc}000& 010& 000& 010\\ 001& 011& 001& 011\\ 000& 011& 000& 011\\ 001& 010& 001& 010\\ 100& 110& 110& 100\\ 101& 111& 111& 101\\ 100& 111& 111& 100\\ 101& 110& 110& 101\end{array}\right)$.

Here, $C_0=(A_0,E_0,{\cdot }_0)$ is a Cartesian frame over $W_0=\{000,001,010,011,100,101,110,111\}$.

The four possible environments from left to right represent Zoe choosing 0, Zoe choosing 1, Zoe copying the first digit, and Zoe negating the first digit.

The eight possible agents can be broken up into two groups of four. In the top four possible agents, Yosef chooses 0 for the first digit, while in the bottom four, he chooses 1. Within each group, the four possible agents represent Yosef choosing 0 for the third digit, choosing 1 for the third digit, copying the second digit, and negating the second digit.

Consider the three partitions $W_1$, $W_2$, and $W_3$ of $W_0$ representing the first, second and third digits respectively. $W_i=\{w_i^0,w_i^1\}$, where $w_1^0=\{000,001,010,011\}$, $w_1^1=\{100,101,110,111\}$, $w_2^0=\{000,001,100,101\}$, $w_2^1=\{010,011,110,111\}$, $w_3^0=\{000,010,100,110\}$, and $w_3^1=\{001,011,101,111\}$.

Clearly, by the definition of observables, $W_2$ is not observable in $C_0$. But there is still a sense in which this does not tell the whole story. Yosef can observe $W_2$ for the purpose of deciding the third digit, but can't observe $W_2$ for the purpose of deciding the first digit.

There are actually many ways to express this fact, but I want to draw attention to one specific way to express this partial observability: ${\text{External}}_{W_1}\left(C_0\right)$ can observe $W_2$.

Indeed, we have 

${\text{External}}_{W_1}\left(C_0\right)\simeq C_1=\left(\begin{array}{cccc}000& 010& 100& 110\\ 000& 010& 100& 111\\ 000& 010& 101& 110\\ 000& 010& 101& 111\\ 000& 011& 100& 110\\ 000& 011& 100& 111\\ 000& 011& 101& 110\\ 000& 011& 101& 111\\ 001& 010& 100& 110\\ 001& 010& 100& 111\\ 001& 010& 101& 110\\ 001& 010& 101& 111\\ 001& 011& 100& 110\\ 001& 011& 100& 111\\ 001& 011& 101& 110\\ 001& 011& 101& 111\end{array}\right)$.

It may seem counter-intuitive that when you externalize $W_1$, and thus take some control out of the hands of the agent, you actually end up with more possible agents. This is because the agent now has to specify what the third digit is, not only as a function of the second digit, but also as a function of the first digit. The agent could have specified the third digit as a function of the first digit before, but some of the policies would have been identical to each other.

The four possible environments of $C_1$ specify the first two digits, while the 16 possible agents represent all of the ways to have the third digit be a function of those first two digits. It is clear that $W_2$ is observable in $C_1$.

This gives us a generic way to define a type of partial observability:

Definition: Given a Cartesian frame $C$ over $W$, and partitions $V$ and $T$ of $W$, we say $V$ is observable in $C$ after time $T$ if $V$ is observable in ${\text{External}}_T\left(C\right)$.

2. Partitions as Time

Built into the above definition is the fact that we are thinking of (at least some) partitions of $W$ as representing time. This makes a lot of sense when we think of $W$ as a set of possible complete world histories. For any given time, this gives a partition where world histories are in the same subset if they agree on the world history up to that point in time.

For example, the above partition $W_1$ was the partition that we got by considering a time after Yosef chooses the first digit, but before Zoe chooses the second digit.

Further, this gives us a sequence of nested partitions, since the partition associated with one time is always a refinement of the partition associated with an earlier time.

Note that this is a multiplicative/updateless view of time. There is also an additive/updateful view of time, in which time is a nested sequence of subsets. In the additive view, possible worlds are eliminated as you pass through time. In the multiplicative view, possible worlds are distinguished from each other as you pass through time. We will focus on the multiplicative view, which I consider better-motivated.

3. Nested Subagents

Let $C=(A,E,\cdot )$ be a fixed Cartesian frame over a world $W$. Let $T_0,\cdots ,T_n$ be a sequence of nested partitions of $W$, with $T_0=\left\{W\right\}$, $T_n=\left\{\right\{w\}|w\in W\}$, and $T_{i+1}$ a refinement of $T_i$.

This gives a nested sequence of multiplicative superagents $C_{T_n}{◃}_{\times }\cdots {◃}_{\times }{C}_{T_0}$, where $C_{T_i}={\text{External}}_{T_i}\left(C\right)$, which follows from the lemma below. 

Lemma: Given a Cartesian frame $C$ over $W$, if $U$ and $V$ are partitions of $W$ and $U$ is a refinement of $V$, then ${\text{External}}_U\left(C\right){◃}_{\times }{\text{External}}_V\left(C\right)$.

Proof: Let $C=(A,E,\cdot )$, and let $u:W\to U$ and $v:W\to V$ send each element of $W$ to their part in $U$ and $V$ respectively. Let ${\text{External}}_U\left(C\right)=(A/B_U,B_U\times E,{\cdot }_U)$, where $B_U=\left\{\right\{a^{\prime }\in A|\forall e\in E,u(a^{\prime }\cdot e)=u(a\cdot e)\}|a\in A\}$. Similarly, let${\text{External}}_V\left(C\right)=(A/B_V,B_V\times E,{\cdot }_V)$, where $B_V=\left\{\right\{a^{\prime }\in A|\forall e\in E,v(a^{\prime }\cdot e)=v(a\cdot e)\}|a\in A\}$. Let $b_U:A\to B_U$ and $b_V:A\to B_V$ send each element of $A$ to its part in $B_U$ and $B_V$ respectively. 

Since $U$ is a refinement of $V$, there exists a $v^{\prime }:U\to V$, such that $v^{\prime }\circ u=v$. Further, we have that $B_U$ is a refinement of $B_V$, so there exists a $b_V^{\prime }:B_U\to B_V$ such that $b_V^{\prime }\circ b_U=b_V.$

It suffices to show there exist three sets $X$, $Y$, and $Z$, and a function $f:X\times Y\times Z\to W$ such that ${\text{External}}_U\left(C\right)\simeq (X,Y\times Z,\diamond )$ and ${\text{External}}_V\left(C\right)\simeq (X\times Y,Z,\bullet )$, where $\diamond$ and $\bullet$ are given by $x\diamond (y,z)=f(x,y,z)$ and $(x,y)\bullet z=f(x,y,z)$.

We will take $X$ to be $A/B_U$ and $Z$ to be $B_V\times E$. We define $Y$ to be the set of all right inverses to $b_V^{\prime }$, $Y=\{y:B_V\to B_U|\forall b\in B_U,b_V^{\prime }(y\left(b\right))=b\}$. We will let $f(x,y,(b,e\left)\right)=x\left(y\right(b\left)\right)\cdot e$.

First, we show

We define

and

as follows. Let $g_0$ and $g_1$ be the identity on $X=A/B_U$, and let $h_0:Y\times Z\to B_U\times E$ be given by $h_0(y,(b,e\left)\right)=\left(y\right(b),e)$. Finally, let $h_1:B_U\times E\to Y\times Z$ be chosen to satisfy $h_1(b,e)=(y,(b_V^{\prime }\left(b\right),e\left)\right)$, where $y$ is such that $y\left(b_V^{\prime }\right(b\left)\right)=b$, and for $b^{\prime }\ne b_V^{\prime }\left(b\right)$, $y\left(b^{\prime }\right)$ is chosen arbitrarily to be any preimage of $b^{\prime }$ under $b_V^{\prime }$.

We have that $(g_0,h_0)$ is a morphism, because for all $x\in A/B_U$ and $(y,(b,e\left)\right)\in Y\times Z$,

Similarly, $(g_1,h_1)$ is a morphism, because for all $x\in X$ and $(b,e)\in B_U\times E$, we have

where $y$ is as given in the definition of $h_1$. Since $g_0\circ g_1$ and $g_1\circ g_0$ are both the identity, we have that $(g_0,h_0)\circ (g_1,h_1)$ and $(g_1,h_1)\circ (g_0,h_0)$ are both homotopic to the identity, so ${\text{External}}_U\left(C\right)\simeq (X,Y\times Z,\diamond )$.

Next, we show

We define

and

as follows. Let $h_2$ and $h_3$ be the identity on $Z=B_V\times E$, and let $g_3:X\times Y\to A/B_V$ be given by $g_3(x,y)=x\circ y$. To see that $x\circ y$ is in $A/B_V$, we need to verify that $b_V\circ x\circ y$ is the identity on $B_V$. Indeed,

which is the identity on $B_V$. Let $g_2:A/B_V\to X\times Y$ be given by $g_2\left(q\right)=(q^{\prime },b_U\circ q)$, where $q^{\prime }\in A/B_U$ is chosen such that for all $b\in B_V$, $q^{\prime }\left(b_U\right(q\left(b\right)\left)\right)=q\left(b\right)$, and for $b^{\prime }$ not in the image of $b_U\circ q$, $q^{\prime }\left(b^{\prime }\right)\in b^{\prime }$. We can do this simultaneously for all inputs of the form $b_U\left(q\right(b\left)\right)$, since $b_U\circ q$ is injective, since it has a left inverse, $b_V^{\prime }$.

We have that $(g_2,h_2)$ is a morphism, because for all $q\in A/B_V$ and $(b,e)\in Z$, we have

where $q^{\prime }$ is as in the definition of $g_2$. Similarly, $(g_3,h_3)$ is a morphism, because for all $(x,y)\in X\times Y$ and $(b,e)\in B_V\times E$, we have

Since $h_3\circ h_2$ and $h_2\circ h_3$ are both the identity, we have that $(g_2,h_2)\circ (g_3,h_3)$ and $(g_3,h_3)\circ (g_2,h_2)$ are both homotopic to the identity, so ${\text{External}}_V\left(C\right)\simeq (X\times Y,Z,\bullet )$, completing the proof. $\square$

The sequence $C_{T_0},\dots ,C_{T_n}$ represents the agent persisting across time, but each subagent $C_{T_i}$ does not really represent a single time-slice of the agent. Instead, $C_{T_i}$ represents an agent persisting across time starting at the time $T_i$.

I think that this is actually the more natural notion. However, if we want to think about an agent persisting across times as a sequence of single times-slices of the agent, we could also do that. Since $C_{T_{i+1}}$ is a multiplicative subagent of $C_{T_i}$, $C_{T_{i+1}}$ must have a sister $D_{T_i+1}$ in $C_{T_i}$, so we could consider the sequence $D_{T_1},\dots ,D_{T_n}$.

4. Controllables Decrease and Observables Increase Over Time

An interesting fact about these sequences $C_{T_0},\dots ,C_{T_n}$ is that controllables decrease and observables increase over time, so for $i\le j$ we have $\text{Obs}\left(C_{T_i}\right)\subseteq \text{Obs}\left(C_{T_j}\right)$ and $\text{Ctrl}\left(C_{T_i}\right)\supseteq \text{Ctrl}\left(C_{T_j}\right)$ (and $\text{Ensure}\left(C_{T_i}\right)\supseteq \text{Ensure}\left(C_{T_j}\right)$ and $\text{Prevent}\left(C_{T_i}\right)\supseteq \text{Prevent}\left(C_{T_j}\right)$), which follows directly from the following two lemmas.

Lemma: Given a Cartesian frame $C$ over $W$, if $U$ and $V$ are partitions of $W$ and $U$ is a refinement of $V$, then $\text{Ctrl}\left({\text{External}}_V\right(C\left)\right)\supseteq \text{Ctrl}\left({\text{External}}_U\right(C\left)\right)$.

Proof: Let $C_V={\text{External}}_V\left(C\right)$, and let $C_U={\text{External}}_V\left(C\right)$. We will actually only need to use the fact that $C_U{◃}_{\times }{C}_V$, and that both $C_U$ and $C_V$ have nonempty agents. $C_U$ and $C_V$ do in fact have nonempty agent, because, as we have shown, externalizing a partition of $W$ always produces nonempty agents.

It suffices to establish that $\text{Ensure}\left(C_{T_i}\right)\supseteq \text{Ensure}\left(C_{T_j}\right)$, and the result for $\text{Ctrl}$ follows trivially.

Since $C_U{◃}_{\times }{C}_V$, there exist $X$, $Y$, $Z$, and $f:X\times Y\times Z\to W$ such that $C_U\simeq (X,Y\times Z,\diamond )$ and $C_V\simeq (X\times Y,Z,\bullet )$, where $\diamond$ and $\bullet$ are given by $x\diamond (y,z)=f(x,y,z)$ and $(x,y)\bullet z=f(x,y,z)$. Let $C_U^{\prime }=(X,Y\times Z,\diamond )$, and let $C_V^{\prime }\simeq (X\times Y,Z,\bullet )$. Observe that $X$ and $Y$ are nonempty.

Since $\text{Ensure}$ is preserved by biextensional equivalence, it suffices to show that $\text{Ensure}\left(C_V^{\prime }\right)\supseteq \text{Ensure}\left(C_U^{\prime }\right)$. Let $S\in \text{Ensure}\left(C_U^{\prime }\right)$. Thus, there exists some $x_0\in X$, such that for all $(y,z)\in Y\times Z$, $x_0\diamond (y,z)=f(x_0,y,z)\in S$. Since $Y$ is nonempty, we can take an arbitrary $y_0\in Y$, and observe that for all $z\in S$, $(x_0,y_0)\bullet z=f(x_0,y_0,z)\in S$. Thus,  $S\in \text{Ensure}\left(C_V^{\prime }\right)$. $\square$

Lemma: Given a Cartesian frame $C$ over $W$, if $U$ and $V$ are partitions of $W$ and $U$ is a refinement of $V$, then $\text{Obs}\left({\text{External}}_V\right(C\left)\right)\subseteq \text{Obs}\left({\text{External}}_U\right(C\left)\right)$.

Proof: Let $C=(A,E,\cdot )$, and let $u:W\to U$ and $v:W\to V$ send each element of $W$ to their part in $U$ and $V$ respectively. Let ${\text{External}}_U\left(C\right)=(A/B_U,B_U\times E,{\cdot }_U)$, where $B_U=\left\{\right\{a^{\prime }\in A|\forall e\in E,u(a^{\prime }\cdot e)=u(a\cdot e)\}|a\in A\}$. Similarly, let${\text{External}}_U\left(C\right)=(A/B_V,B_V\times E,{\cdot }_V)$, where $B_V=\left\{\right\{a^{\prime }\in A|\forall e\in E,v(a^{\prime }\cdot e)=v(a\cdot e)\}|a\in A\}$. Let $b_U:A\to B_U$ and $b_V:A\to B_V$ send each element of $A$ to its part in $B_U$ and $B_V$ respectively. 

Since $U$ is a refinement of $V$, there exists a $v^{\prime }:U\to V$, such that $v^{\prime }\circ u=v$. Further, we have that $B_U$ is a refinement of $B_V$, so there exists a $b_V^{\prime }:B_U\to B_V$ such that $b_V^{\prime }\circ b_U=b_V.$

Let $S\in \text{Obs}\left({\text{External}}_V\right(C\left)\right).$ Thus, for every pair $q_0,q_1\in A/B_V$, there exists a $q_2\in A/B_V$ such that $q_2\in \text{if}(S,q_0,q_1)$. Thus, we can define an $f:A/B_V\times A/B_V\to A/B_V$  such that for all $q_0,q_1\in A/B_V$, $f(q_0,q_1)\in \text{if}(S,q_0,q_1)$. 

Our goal is to show that $S\in \text{Obs}\left({\text{External}}_U\right(C\left)\right)$. For this, it suffices to show that for any $q_0,q_1\in A/B_U$, there exists a $q_2\in A/B_U$ such that $q_2\in \text{if}(S,q_0,q_1)$. 

Let $q_0,q_1\in A/B_U$ be arbitrary. Given an arbitrary $b\in B_U$, let $q_i^b\in A/B_V$ be any element that satisfies $q_i^b\left(b_V^{\prime }\right(b\left)\right)=q_i\left(b\right)$. This is possible because $q_i\left(b\right)\in b\subseteq b_V^{\prime }\left(b\right)$. It does not matter what $q_i^b$ does on other inputs. Let $q_2:B_U\to A$ be such that for all $b\in B_U$, $q_2\left(b\right)=f(q_0^b,q_1^b)\left(b_V^{\prime }\right(b\left)\right)$.

To complete the proof, we need to show that $q_2\in A/B_U$ and $q_2\in \text{if}(S,q_0,q_1)$. 

To show that $q_2\in A/B_U$, we need that for all $b\in B_U$, $q_2\left(b\right)\in b$. Let $b\in B_U$ be arbitrary. Since $q_0\left(b\right)\in b$, by the definition of $B_U$, it suffices to show that for all $e\in E$, $u\left(q_2\right(b)\cdot e)=u\left(q_0\right(b)\cdot e)$. Further, since $q_1\left(b\right)\in b$, we already have that for all $e\in E$, $u\left(q_1\right(b)\cdot e)=u\left(q_0\right(b)\cdot e)$. Thus, it suffices to show that for all $e\in E$, either $q_2\left(b\right)\cdot e=q_0\left(b\right)\cdot e$ or $q_2\left(b\right)\cdot e=q_1\left(b\right)\cdot e$. Indeed, if $q_2\left(b\right)\cdot e\in S$, then

and similarly, if $q_2\left(b\right)\cdot e\notin S$, then $q_2\left(b\right)\cdot e=q_1\left(b\right)\cdot e$. Thus, we have that for all $e\in E$, $u\left(q_2\right(b)\cdot e)=u\left(q_0\right(b)\cdot e)$, so for our arbitrary $b\in B_U$, $q_0\left(b\right)\in b$, so $q_2\in A/B_U$.