Sub-Sums and Sub-Tensors

post by Scott Garrabrant · 2020-11-05T18:06:44.421Z · LW · GW · 4 comments

Contents

  1. Motivating Examples
  2. Deleting Spurious Environments
  3. Properties of Sub-Sums and Sub-Tensors
    3.1. Sub-Sums and Sub-Tensors Are Commutative
    3.2. Tensors Need Not Be Sub-Tensors
    3.3. Sub-Sums and Sub-Tensors Are Superagents
    3.4. Biextensional Equivalence
None
4 comments

This is the eighth post in the Cartesian frames [LW · GW] sequence. Here, we define new versions of the sum [LW · GW] and tensor [LW · GW] of Cartesian frames that can delete spurious possible environments from the frame.

 

1. Motivating Examples

The sum $C\oplus D$ of $C$ and $D$ is supposed to represent an agent that can do anything either $C$ or $D$ can do, while the tensor, $C\otimes D$, is supposed to represent an agent that can do anything $C$ and $D$ can do working freely together on a team. However, sometimes these operations produce Cartesian frames with more environments than we would expect.

Consider two players, Alice and Bob, in a prisoner's dilemma. We will let $W=\{0,1,2,3\}$ be the space of utilities for Alice. The Cartesian frame for Alice looks like

$C_0=\left(\begin{array}{cc}2& 0\\ 3& 1\end{array}\right)$,

where the top row represents Alice cooperating, and the left column represents Bob cooperating.

Let $C_1=\left(\begin{array}{cc}2& 0\end{array}\right)$ represent Alice committed to cooperating, and let $C_2=\left(\begin{array}{cc}3& 1\end{array}\right)$ represent Alice committed to defecting. Since the real Alice can either cooperate or defect, one might expect that Alice ($C_0$) would equal the sum ($C_1\oplus C_2$) of Alice cooperating with Alice defecting. However,

$C_1\oplus C_2=\left(\begin{array}{cccc}2& 0& 2& 0\\ 3& 1& 1& 3\end{array}\right)$.

The last two columns are spurious environments that represent Bob copying Alice's move, and Bob doing the opposite of Alice's move. However, since Bob cannot see Alice's move, Bob should not be able to implement these policies: Bob can only choose to cooperate or defect.

Next, consider a unilateralist's curse game where two players each have access to a button that destroys the Earth. If either player pushes the button, the Earth is destroyed. Otherwise, the Earth is not destroyed. $W=\{0,1\}$, where $0$ represents the world being destroyed and $1$ represents the world not being destroyed.

Here, both players have the Cartesian frame

$D_1=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$,

where the first row represents pressing the button, and the first column represents the other player pressing the button.

The two players together can be expressed with the Cartesian frame

$D_2=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right)$,

where the rows in order represent: both players pressing the button; the first player pressing the button; the second player pressing the button; and neither player pressing the button.

One might expect that $D_1\otimes D_1$ would be $D_2$, but in fact,

$D_1\otimes D_1=\left(\begin{array}{cc}0& 0\\ 0& 0\\ 0& 0\\ 1& 0\end{array}\right)$.

The second possible environment, in which the earth is just destroyed regardless of what the players do, is spurious.

In both of the above examples, the spurious environments are only spurious because of our interpretation. In the prisoner's dilemma case, $C_1\oplus C_2$ would be correct if Alice and Bob were playing a modified dilemma where Bob can see Alice's choice. In the unilateralist's curse example, $D_1\otimes D_1$ would be correct if there were three people playing the game. The problem is that the $\oplus$ and $\otimes$ operations do not see our interpretation, and so include all possible environments.

 

2. Deleting Spurious Environments

We introduce two new concepts, called sub-sum and sub-tensor, which represents sum and tensor with some (but not too many) spurious environments removed.

Definition: Let $C=(A,E,\cdot )$, and let $D=(B,F,\star )$. A sub-sum of C and D is a Cartesian frame of the form $(A\bigsqcup B,X,\diamond )$, where $X\subseteq \text{Env}(C\oplus D)$ and $\diamond$ is $\text{Eval}(C\oplus D)$ restricted to $(A\bigsqcup B)\times X$, such that $C\simeq (A,X,{\diamond }_C)$ and $D\simeq (B,X,{\diamond }_D)$, where ${\diamond }_C$ is $\diamond$ restricted to $A\times X$ and ${\diamond }_D$ is $\diamond$ restricted to $B\times X$. Let $C⊞D$ denote the set of all sub-sums of $C$ and $D$.

Definition: Let $C=(A,E,\cdot )$, and let $D=(B,F,\star )$. A sub-tensor of $C$ and $D$ is a Cartesian frame of the form $(A\times B,X,\bullet )$, where $X\subseteq \text{Env}(C\otimes D)$ and $\bullet$ is $\text{Eval}(C\otimes D)$ restricted to $(A\times B)\times X$, such that $C\simeq (A,B\times X,{\bullet }_C)$ and $D\simeq (B,A\times X,{\bullet }_D)$, where ${\bullet }_C$ and ${\bullet }_D$ are given by $a{\bullet }_C(b,x)=(a,b)\bullet x$ and $b{\bullet }_D(a,x)=(a,b)\bullet x$. Let $C⊠D$ denote the set of all sub-tensors of $C$ and $D$.

Thus, we define $C⊞D$ and $C⊠D$ to be sets of Cartesian frames that can be obtained by deleting columns from from $C\oplus D$ and $C\otimes D$, respectively, but we have an extra restriction to ensure that we do not delete too many columns.

We will discuss later how to interpret the extra restriction, but first let us go back to our above examples.

If $C_1=\left(\begin{array}{cc}2& 0\end{array}\right)$ and $C_2=\left(\begin{array}{cc}3& 1\end{array}\right)$, then $C_1⊞C_2$ has 7 elements:

$\left(\begin{array}{cccc}2& 0& 2& 0\\ 3& 1& 1& 3\end{array}\right),\left(\begin{array}{ccc}2& 0& 2\\ 3& 1& 1\end{array}\right),\left(\begin{array}{ccc}2& 0& 0\\ 3& 1& 3\end{array}\right),\left(\begin{array}{ccc}2& 2& 0\\ 3& 1& 3\end{array}\right),\left(\begin{array}{ccc}0& 2& 0\\ 1& 1& 3\end{array}\right),\left(\begin{array}{cc}2& 0\\ 3& 1\end{array}\right),\left(\begin{array}{cc}2& 0\\ 1& 3\end{array}\right)$

The 9 Cartesian frames that can be obtained by deleting columns from $C\oplus D$ that are not in $C_1⊞C_2$ are:

$\left(\begin{array}{cc}2& 2\\ 3& 1\end{array}\right),\left(\begin{array}{cc}2& 0\\ 3& 3\end{array}\right),\left(\begin{array}{cc}0& 2\\ 1& 1\end{array}\right),\left(\begin{array}{cc}0& 0\\ 1& 3\end{array}\right),\left(\begin{array}{c}2\\ 3\end{array}\right),\left(\begin{array}{c}0\\ 1\end{array}\right),\left(\begin{array}{c}2\\ 1\end{array}\right),\left(\begin{array}{c}0\\ 3\end{array}\right),\left(\begin{array}{c}\\ \end{array}\right)$.

The Cartesian frames above in $C_1⊞C_2$ are exactly those with all four entries, $0$, $1$, $2$, and $3$. This is because the extra restriction to be in $C_1⊞C_2$ is exactly that if you delete the bottom row, you get an object biextensionally equivalent to $\left(\begin{array}{cc}2& 0\end{array}\right)$, and if you delete the top row, you get an object biextensionally equivalent to $\left(\begin{array}{cc}3& 1\end{array}\right)$.

Similarly, from the unilateralist's curse example,

$D_1⊠D_1=\{\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right),\left(\begin{array}{cc}0& 0\\ 0& 0\\ 0& 0\\ 1& 0\end{array}\right)\}$.

It is easy to see that there are no other Cartesian frames in $D_1⊠D_1$, since there are only four subsets of the two element environment of $D_1\otimes D_1$, and the Cartesian frames corresponding to the other two subsets do not have 1 in their image, so we cannot build anything biextensionally equivalent to $D_1$ out of them.

Conversely, let $C=(A,E,\cdot )$ and $D=(B,F,\star )$ both be $D_1$, and notice that if

$(A\times B,X,\bullet )=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right)$,

then $(A,B\times X,{\bullet }_C)$ and $(B,A\times X,{\bullet }_D)$ are both two-by-two matrices with a single $1$ entry and three $0$ entries, and so must be isomorphic to $D_1$. Similarly, if

$(A\times B,X,\bullet )=\left(\begin{array}{cc}0& 0\\ 0& 0\\ 0& 0\\ 1& 0\end{array}\right)$,

then $(A,B\times X,{\bullet }_C)$ and $(B,A\times X,{\bullet }_D)$ are both two-by-four matrices with a single $1$ entry and seven $0$ entries, and so must by biextensionally equivalent to $D_1$.

 

3. Properties of Sub-Sums and Sub-Tensors

3.1. Sub-Sums and Sub-Tensors Are Commutative

Claim: For any Cartesian frames $C_0$ and $C_1$, there is a bijection between $C_0⊞C_1$ and $C_1⊞C_0$ that preserves Cartesian frames up to isomorphism. Similarly, there is a bijection between $C_0⊠C_1$ and $C_1⊠C_0$ that preserves Cartesian frames up to isomorphism.

Proof: Trivial. $\square$

 

3.2. Tensors Need Not Be Sub-Tensors

For any Cartesian frames $C$ and $D$ with nonempty environments, we have that $C\oplus D\in C⊞D$. However, sometimes $C\otimes D\notin C⊠D$. Indeed, sometimes $C⊠D=\left\{\right\}$.

For example, if $C$ and $D$ both have nonempty image, but there are no morphisms from $C$ to $D^{\ast }$, then $C\otimes D$ has no environments, and it is easy to see that $C⊠D$ must be empty.

 

3.3. Sub-Sums and Sub-Tensors Are Superagents

Claim: For any Cartesian frames $C_0$ and $C_1$, and for any $D_0\in C_0⊞C_1$, we have $C_0◃D_0$ and $C_1◃D_0$. Similarly, for any $D_1\in C_0⊠C_1$, we have $C_0◃D_1$ and $C_1◃D_1$.

Proof: Let $C_i=(A_i,E_i,{\cdot }_i)$ and $D_i=(B_i,F_i,{\star }_i)$. First, we show $C_0◃D_0$ using the currying definition [LW · GW] of subagent. Observe $B_0=A_0\bigsqcup A_1$. Consider the Cartesian frame $(A_0,\{e\},\diamond )$ over $B_0$, where $\diamond$ is given by $a\diamond e=a$. Observe that the definition of sub-sum says that $C_0\simeq D_0^{\circ }(A_0,\{e\},\diamond )$, so $C_0◃D_0$. Therefore, $C_0◃D_0$, and by commutativity, we also have $C_1◃D_0$ .

Similarly, we show $C_0◃D_1$ using the currying definition of subagent. Observe that $B_1=A_0\times A_1$. Consider the Cartesian frame $(A_0,A_1,\bullet )$ over $B_1$, where $\bullet$ is given by $a_0\bullet a_1=(a_0,a_1)$. Observe that the definition of sub-tensor says that $C_0\simeq D_1^{\circ }(A_0,A_1,\bullet )$. Therefore, $C_0◃D_1$, and by commutativity, we also have $C_1◃D_1$. $\square$

Observe that in the above proof, the Cartesian frame over $B_0$ we constructed to show that sub-sums are superagents had a singleton environment, and the Cartesian frame over $B_1$ we constructed to show that sub-tensors are superagents had a surjective evaluation function. The relevance of this observation will become clear later.

 

3.4. Biextensional Equivalence

As we do with most of our definitions, we will now show that sub-sums and sub-tensors are well-defined up to biextensional equivalence.

Claim: Given two Cartesian frames over $W$, $C_0$ and $C_1$, and given any $D\in C_0⊞C_1$, we have that for all $C_0^{\prime }\simeq C_0$ and $C_1^{\prime }\simeq C_1$, there exists a $D^{\prime }\simeq D$, with $D^{\prime }\in C_0^{\prime }⊞C_1^{\prime }$.

Proof: Let $C_0=(A_0,E_0,{\cdot }_0)$, let $C_1=(A_1,E_1,{\cdot }_1)$, and let $D=(A_0\bigsqcup A_1,X,\star )$ be an element of $C_0⊞C_1$, so $X\subseteq E_0\times E_1$, and $a\star (e_0,e_1)=a{\cdot }_0{e}_0$ if $a\in A_0$, and $a\star (e_0,e_1)=a{\cdot }_1{e}_1$ if $a\in A_1$.

The fact that $D\in C_0⊞C_1$ tells us that for $i\in \{0,1\}$, $D_i\simeq C_i$, where $D_i=(A_i,X,{\star }_i)$ with ${\star }_i$ given by $a{\star }_0(e_0,e_1)=a{\cdot }_0{e}_0$ and $a{\star }_1(e_0,e_1)=a{\cdot }_0{e}_1$.

For $i\in \{0,1\}$, let $C_i^{\prime }=(A_i^{\prime },E_i^{\prime },{\cdot }_i^{\prime })$ satisfy $C_i^{\prime }\simeq C_i$. Thus, there exist morphisms $(g_i,h_i):C_i\to C_i^{\prime }$, and $(g_i^{\prime },h_i^{\prime }):C_i^{\prime }\to C_i$, such that $(g_0,h_0)\circ (g_0^{\prime },h_0^{\prime })$, $(g_0^{\prime },h_0^{\prime })\circ (g_0,h_0)$, $(g_1,h_1)\circ (g_1^{\prime },h_1^{\prime })$, and $(g_1^{\prime },h_1^{\prime })\circ (g_1,h_1)$ are all homotopic to the identity.

We define a function $f:E_0\times E_1\to E_0^{\prime }\times E_1^{\prime }$ by $f(e_0,e_1)=\left(h_0^{\prime }\right(e_0),h_1^{\prime }(e_1\left)\right)$. Then, we define $X^{\prime }\subseteq E_0^{\prime }\times E_1^{\prime }$ by $X^{\prime }=\left\{f\right(x)|x\in X\}$, and let $D^{\prime }=(A_0^{\prime }\bigsqcup A_1^{\prime },X^{\prime },{\star }^{\prime })$, where $a{\star }^{\prime }(e_0,e_1)=a{\cdot }_0^{\prime }{e}_0$ if $a\in A_0^{\prime }$, and $a{\star }^{\prime }(e_0,e_1)=a{\cdot }_1^{\prime }{e}_1$ if $a\in A_1^{\prime }$. We need to show $D^{\prime }\in C_0^{\prime }⊞C_1^{\prime }$, and that $D^{\prime }\simeq D$.

To show that $D^{\prime }\simeq D$, we will construct a pair of morphisms $(j,k):D\to D^{\prime }$ and $(j^{\prime },k^{\prime }):D^{\prime }\to D$ that compose to something homotopic to the identity in both orders. We define $j:A_0\bigsqcup A_1\to A_0^{\prime }\bigsqcup A_1^{\prime }$ by $j\left(a\right)=g_0\left(a\right)$ if $a\in A_0$, and $j\left(a\right)=g_1\left(a\right)$ if $a\in A_1$. We similarly define $j^{\prime }:A_0^{\prime }\bigsqcup A_1^{\prime }\to A_0\bigsqcup A_1$ by $j^{\prime }\left(a\right)=g_0^{\prime }\left(a\right)$ if $a\in A_0^{\prime }$, and $j^{\prime }\left(a\right)=g_1^{\prime }\left(a\right)$ if $a\in A_1^{\prime }$. We define $k^{\prime }:X\to X^{\prime }$ by $k^{\prime }\left(x\right)=f\left(x\right)$, which is clearly a function into $X^{\prime }$, by the definition of $X^{\prime }$. Further, $k^{\prime }$ is surjective, and thus has a right inverse. We choose $k:X^{\prime }\to X$ to be any right inverse to $k^{\prime }$, so $f\left(k\right(x\left)\right)=x$ for all $x\in X^{\prime }$.

To see that $(j^{\prime },k^{\prime })$ is a morphism, observe that for $a\in A_0^{\prime }\bigsqcup A_1^{\prime }$, and $(e_0,e_1)\in X$, if $a\in A_i^{\prime },$ then

$$\begin{array}{cc}{j}^{\prime }\left(a\right)\star (e_0,e_1)& =g_i^{\prime }\left(a\right){\cdot }_i{e}_i\\ & =a{\cdot }_i^{\prime }{h}_i^{\prime }\left(e_i\right)\\ & =a{\star }^{\prime }\left(h_0^{\prime }\right(e_0),h_1^{\prime }(e_1\left)\right)\\ & =a{\star }^{\prime }{k}^{\prime }(e_0,e_1)).\end{array}$$

To see that $(j,k)$ is a morphism, consider an arbitrary $a\in A_0\bigsqcup A_1$ and $(e_0^{\prime },e_1^{\prime })\in X^{\prime }$, and let $(e_0,e_1)=k(e_0^{\prime },e_1^{\prime })$. Then, if $a\in A_i$, we have

$$\begin{array}{cc}j\left(a\right){\star }^{\prime }(e_0^{\prime },e_1^{\prime })& =j\left(a\right){\star }^{\prime }f(e_0,e_1)\\ & =j\left(a\right){\star }^{\prime }\left(h_0^{\prime }\right(e_0),h_1^{\prime }(e_1\left)\right)\\ & =g_i\left(a\right){\cdot }_i^{\prime }{h}_i^{\prime }\left(e_i\right)\\ & =g_i^{\prime }\left(g_i\right(a\left)\right){\cdot }_i{e}_i\\ & =a{\cdot }_i{e}_i\\ & =a\star (e_0,e_1)\\ & =a\star k(e_0^{\prime },e_1^{\prime }).\end{array}$$

To see that $(j^{\prime },k^{\prime })\circ (j,k)$ is homotopic to the identity on $D$, observe that for all $a\in A_0\bigsqcup A_1$ and $(e_0,e_1)\in X$, we have that if $a\in A_i$,

$$\begin{array}{cc}{j}^{\prime }\left(j\right(a\left)\right)\star (e_0,e_1)& =g_i^{\prime }\left(g_i\right(a\left)\right){\cdot }_i{e}_i\\ & =a{\cdot }_i{e}_i\\ & =a\star (e_0,e_1).\end{array}$$

Similarly, to see that $(j,k)\circ (j^{\prime },k^{\prime })$ is homotopic to the identity on $D^{\prime }$, observe that for all $a\in A_0^{\prime }\bigsqcup A_1^{\prime }$ and $(e_0,e_1)\in X^{\prime }$, we have that if $a\in A_i^{\prime }$,

$$\begin{array}{cc}j\left(j^{\prime }\right(a\left)\right){\star }^{\prime }(e_0,e_1)& =g_i\left(g_i^{\prime }\right(a\left)\right){\cdot }_i^{\prime }{e}_i\\ & =a{\cdot }_i^{\prime }{e}_i\\ & =a{\star }^{\prime }(e_0,e_1).\end{array}$$

Thus, $D^{\prime }\simeq D$.

To see $D^{\prime }\in C_0^{\prime }⊞C_1^{\prime }$, we need to show that $D_i^{\prime }\simeq C_i^{\prime }$, where $D_i^{\prime }=(A_i^{\prime },X^{\prime },{\star }_i^{\prime })$ with ${\star }_i^{\prime }$ given by $a{\star }_0^{\prime }(e_0,e_1)=a{\cdot }_0^{\prime }{e}_0$ and $a{\star }_1^{\prime }(e_0,e_1)=a{\cdot }_1^{\prime }{e}_1$. It suffices to show that $D_i^{\prime }\simeq D_i$, since $D_i\simeq C_i\simeq C_i^{\prime }$.

For $i\in \{0,1\}$, we construct morphisms $(j_i,k_i):D_i\to D_i^{\prime }$, and $(j_i^{\prime },k_i^{\prime }):D_i^{\prime }\to D_i$. We define $j_i=g_i$, $j_i^{\prime }=g_i^{\prime }$, $k_i=k$, and $k_i^{\prime }=k^{\prime }$.

To see that $(j_i,k_i)$ is a morphism, observe that for all $a\in A_i$ and $x\in X^{\prime }$, we have

$$\begin{array}{cc}{j}_i\left(a\right){\star }_i^{\prime }x& =g_i\left(a\right){\star }_i^{\prime }x\\ & =j\left(a\right){\star }^{\prime }x\\ & =a\star k\left(x\right)\\ & =a{\star }_i{k}_i\left(x\right),\end{array}$$

and to see that $(j_i^{\prime },k_i^{\prime })$ is a morphism, observe that for all $a\in A_i^{\prime }$, and $x\in X$, we have

$$\begin{array}{cc}{j}_i^{\prime }\left(a\right){\star }_{i}x& =g_i^{\prime }\left(a\right){\star }_{i}x\\ & =j^{\prime }\left(a\right)\star x\\ & =a{\star }^{\prime }{k}^{\prime }\left(x\right)\\ & =a{\star }_i^{\prime }{k}_i^{\prime }\left(x\right).\end{array}$$

To see $(j_i^{\prime },k_i^{\prime })\circ (j_i,k_i)$ is homotopic to the identity on $D_i$, observe that for all $a\in A_i$ and $x\in X$, we have

$$\begin{array}{cc}{j}_i^{\prime }\left(j_i\right(a\left)\right){\star }_{i}x& =g_i^{\prime }\left(g_i\right(a\left)\right){\star }_{i}x\\ & =j^{\prime }\left(j\right(a\left)\right)\star x\\ & =a\star x\\ & =a{\star }_{i}x,\end{array}$$

and similarly, to show that $(j_i,k_i)\circ (j_i^{\prime },k_i^{\prime })$ is homotopic to the identity on $D_i^{\prime }$, observe that for all $a\in A_i^{\prime }$ and $x\in X^{\prime }$, we have

$$\begin{array}{cc}{j}_i\left(j_i^{\prime }\right(a\left)\right){\star }_i^{\prime }x& =g_i\left(g_i^{\prime }\right(a\left)\right){\star }_i^{\prime }x\\ & =j\left(j^{\prime }\right(a\left)\right){\star }^{\prime }x\\ & =a{\star }^{\prime }x\\ & =a{\star }_i^{\prime }x.\end{array}$$

Thus, we have that $D_i^{\prime }\simeq D_i$, completing the proof. $\square$

We have a similar result for sub-tensors, whose proof directly mirrors the proof for sub-sums:

Claim: Given two Cartesian frames over $W$, $C_0$ and $C_1$, and any $D\in C_0⊠C_1$, we have that for all $C_0^{\prime }\simeq C_0$ and $C_1^{\prime }\simeq C_1$, there exists a $D^{\prime }\simeq D$, with $D^{\prime }\in C_0^{\prime }⊠C_1^{\prime }$.

Proof: Let $C_0=(A_0,E_0,{\cdot }_0)$, let $C_1=(A_1,E_1,{\cdot }_1)$, and let $D=(A_0\times A_1,X,\star )$ be an element of $C_0⊠C_1$, so $X\subseteq \text{hom}(C_0,C_1^{\ast })$, and

$$\begin{array}{cc}(a,b)\star (g,h)& =a{\cdot }_{0}h\left(b\right)\\ & =b{\cdot }_{1}g\left(a\right).\end{array}$$

The fact that $D\in C_0⊠C_1$ tells us that for $i\in \{0,1\}$, $D_i\simeq C_i$, where $D_i=(A_i,A_{1-i}\times X,{\star }_i)$ with ${\star }_i$ given by

$$\begin{array}{cc}a{\star }_0(b,(g,h\left)\right)& =b{\star }_1(a,(g,h\left)\right)\\ & =(a,b)\star (g,h).\end{array}$$

For $i\in \{0,1\}$, let $C_i^{\prime }=(A_i^{\prime },E_i^{\prime },{\cdot }_i^{\prime })$ satisfy $C_i^{\prime }\simeq C_i$. Thus, there exist morphisms $(g_i,h_i):C_i\to C_i^{\prime }$, and $(g_i^{\prime },h_i^{\prime }):C_i^{\prime }\to C_i$, such that $(g_0,h_0)\circ (g_0^{\prime },h_0^{\prime })$, $(g_0^{\prime },h_0^{\prime })\circ (g_0,h_0)$, $(g_1,h_1)\circ (g_1^{\prime },h_1^{\prime })$, and $(g_1^{\prime },h_1^{\prime })\circ (g_1,h_1)$ are all homotopic to the identity.

We define a function $f:\text{hom}(C_0,{C_1}^{\ast })\to \text{hom}(C_0^{\prime },{C_1^{\prime }}^{\ast })$ by $f(g,h)=(h_1^{\prime },g_1^{\prime })\circ (g,h)\circ (g_0^{\prime },h_0^{\prime })$. This function is well-defined, since $(h_1^{\prime },g_1^{\prime })=(g_1^{\prime },h_1^{\prime }{)}^{\ast }\in \text{hom}(C_1^{\ast },{C_1^{\prime }}^{\ast })$ and $(h_0^{\prime },g_0^{\prime })\in \text{hom}(C_0^{\prime },C_0)$.

Then, we define $X^{\prime }\subseteq \text{hom}(C_0^{\prime },{C_1^{\prime }}^{\ast })$ by $X^{\prime }=\left\{f\right(g,h\left)|\right(g,h)\in X\}$, and let $D^{\prime }=(A_0^{\prime }\times A_1^{\prime },X^{\prime },{\star }^{\prime })$, where

$$\begin{array}{cc}(a,b){\star }^{\prime }(g,h)& =a{\cdot }_0^{\prime }h\left(b\right)\\ & =b{\cdot }_1^{\prime }g\left(a\right).\end{array}$$

We need to show that $D^{\prime }\in C_0^{\prime }⊠C_1^{\prime }$, and that $D^{\prime }\simeq D$.

To show that $D^{\prime }\simeq D$, we will construct a pair of morphisms $(j,k):D\to D^{\prime }$ and $(j^{\prime },k^{\prime }):D^{\prime }\to D$ that compose to something homotopic to the identity in both orders. We define $j:A_0\times A_1\to A_0^{\prime }\times A_1^{\prime }$ by $j(a,b)=\left(g_0\right(a),g_1(b\left)\right)$, and we similarly define $j^{\prime }:A_0^{\prime }\times A_1^{\prime }\to A_0\times A_1$ by $j^{\prime }(a,b)=\left(g_0^{\prime }\right(a),g_1^{\prime }(b\left)\right)$. We define $k^{\prime }:X\to X^{\prime }$ by $k^{\prime }\left(x\right)=f\left(x\right)$, which is clearly a function into $X^{\prime }$, by the definition of $X^{\prime }$. Further, $k^{\prime }$ is surjective, and thus has a right inverse. We choose $k:X^{\prime }\to X$ to be any right inverse to $k^{\prime }$, so $f\left(k\right(x\left)\right)=x$ for all $x\in X^{\prime }$.

To see $(j^{\prime },k^{\prime })$ is a morphism, observe that for $(a,b)\in A_0^{\prime }\times A_1^{\prime }$, and $(g,h)\in X$, we have

$$\begin{array}{cc}{j}^{\prime }(a,b)\star (g,h)& =\left(g_0^{\prime }\right(a),g_1^{\prime }(b\left)\right)\star (g,h)\\ & =g_1^{\prime }\left(b\right){\cdot }_{1}g\left(g_0^{\prime }\right(a\left)\right)\\ & =b{\cdot }_1^{\prime }{h}_1^{\prime }\left(g\right(g_0^{\prime }\left(a\right)\left)\right)\\ & =(a,b){\star }^{\prime }(h_1^{\prime }\circ g\circ g_0^{\prime },h_0^{\prime }\circ h\circ g_1^{\prime })\\ & =(a,b){\star }^{\prime }{k}^{\prime }(g,h).\end{array}$$

To see that $(j,k)$ is a morphism, consider an arbitrary $(a,b)\in A_0\times A_1$ and $(g^{\prime },h^{\prime })\in X^{\prime }$, and let $(g,h)=k(g^{\prime },h^{\prime })$. Then, we have:

$$\begin{array}{cc}j(a,b){\star }^{\prime }(g^{\prime },h^{\prime })& =\left(g_0\right(a),g_1(b\left)\right){\star }^{\prime }f(g,h)\\ & =\left(g_0\right(a),g_1(b\left)\right){\star }^{\prime }(h_1^{\prime },h_1^{\prime })\circ (g,h)\circ (g_0^{\prime },h_0^{\prime })\\ & =g_1\left(b\right){\cdot }_1^{\prime }{h}_1^{\prime }\left(g\right(g_0^{\prime }\left(g_0\right(a\left)\right)\left)\right)\\ & =g_1^{\prime }\left(g_1\right(b\left)\right){\cdot }_{1}g\left(g_0^{\prime }\right(g_0\left(a\right)\left)\right)\\ & =b{\cdot }_{1}g\left(g_0^{\prime }\right(g_0\left(a\right)\left)\right)\\ & =g_0^{\prime }\left(g_0\right(a\left)\right){\cdot }_{0}h\left(b\right)\\ & =a{\cdot }_{0}h\left(b\right)\\ & =(a,b)\star (g,h)\\ & =(a,b)\star k(g^{\prime },h^{\prime }).\end{array}$$

To see that $(j^{\prime },k^{\prime })\circ (j,k)$ is homotopic to the identity on $D$, observe that for all $(a,b)\in A_0\times A_1$ and $(g,h)\in X$, we have:

$$\begin{array}{cc}{j}^{\prime }\left(j\right(a,b\left)\right)\star (g,h)& =\left(g_0^{\prime }\right(g_0\left(a\right)),g_1^{\prime }(g_1\left(b\right)\left)\right)\star (g,h)\\ & =g_1^{\prime }\left(g_1\right(b\left)\right){\cdot }_{1}g\left(g_0^{\prime }\right(g_0\left(a\right)\left)\right)\\ & =b{\cdot }_{1}g\left(g_0^{\prime }\right(g_0\left(a\right)\left)\right)\\ & =g_0^{\prime }\left(g_0\right(a\left)\right){\cdot }_{0}h\left(b\right)\\ & =a{\cdot }_{0}h\left(b\right)=(a,b)\star (g,h).\end{array}$$

Similarly, to see that $(j,k)\circ (j^{\prime },k^{\prime })$ is homotopic to the identity on $D^{\prime }$, observe that for all $(a,b)\in A_0^{\prime }\times A_1^{\prime }$ and $(g,h)\in X$, we have:

$$\begin{array}{cc}j\left(j^{\prime }\right(a,b\left)\right){\star }^{\prime }(g,h)& =\left(g_0\right(g_0^{\prime }\left(a\right)),g_1(g_1^{\prime }\left(b\right)\left)\right){\star }^{\prime }(g,h)\\ & =g_1\left(g_1^{\prime }\right(b\left)\right){\cdot }_1^{\prime }g\left(g_0\right(g_0^{\prime }\left(a\right)\left)\right)\\ & =b{\cdot }_1^{\prime }g\left(g_0\right(g_0^{\prime }\left(a\right)\left)\right)\\ & =g_0\left(g_0^{\prime }\right(a\left)\right){\cdot }_0^{\prime }h\left(b\right)\\ & =a{\cdot }_0^{\prime }h\left(b\right)\\ & =(a,b){\star }^{\prime }(g,h).\end{array}$$

Thus, $D^{\prime }\simeq D$.

To see $D^{\prime }\in C_0^{\prime }⊠C_1^{\prime }$, we need to show that $D_i^{\prime }\simeq C_i^{\prime }$, where $D_i^{\prime }=(A_i^{\prime },A_{1-i}^{\prime }\times X^{\prime },{\star }_i^{\prime })$ with ${\star }_i^{\prime }$ given by

$$\begin{array}{cc}a{\star }_0^{\prime }(b,(g,h\left)\right)& =b{\star }_1^{\prime }(a,(g,h\left)\right)\\ & =(a,b){\star }^{\prime }(g,h).\end{array}$$

It suffices to show that $D_i^{\prime }\simeq D_i$, since $D_i\simeq C_i\simeq C_i^{\prime }$.

For $i\in \{0,1\}$, we construct morphisms $(j_i,k_i):D_i\to D_i^{\prime }$, and $(j_i^{\prime },k_i^{\prime }):D_i^{\prime }\to D_i$. We define $j_i=g_i$ and $j_i^{\prime }=g_i^{\prime }$. We define $k_i:(A_{1-i}^{\prime }\times X^{\prime })\to (A_{1-i}\times X)$ by $k_i(a,x)=\left(g_{1-i}^{\prime }\right(a),k(x\left)\right)$, and similarly define $k_i^{\prime }:(A_{1-i}\times X)\to (A_{1-i}^{\prime }\times X^{\prime })$ by $k_i^{\prime }(a,x)=\left(g_{1-i}\right(a),k^{\prime }(x\left)\right)$.

To see that $(j_0,k_0)$ is a morphism, observe that for all $a\in A_0$ and $(a_1,(g,h\left)\right)\in A_1^{\prime }\times X^{\prime }$, we have:

$$\begin{array}{cc}a{\star }_0{k}_0(b,(g,h\left)\right)& =a{\star }_0\left(g_1^{\prime }\right(b),k(g,h\left)\right)\\ & =(a,g_1^{\prime }(b\left)\right)\star k(g,h)\\ & =j(a,g_1^{\prime }(b\left)\right){\star }^{\prime }(g,h)\\ & =\left(g_0\right(a),g_1(g_1^{\prime }\left(b\right)\left)\right){\star }^{\prime }(g,h)\\ & =g_1\left(g_1^{\prime }\right(b\left)\right){\cdot }_1^{\prime }g\left(g_0\right(a\left)\right)\\ & =b{\cdot }_1^{\prime }g\left(g_0\right(a\left)\right)\\ & =\left(g_0\right(a),b){\star }^{\prime }(g,h)\\ & =j_0\left(a\right){\star }_0^{\prime }(b,(g,h\left)\right).\end{array}$$

To see that $(j_1,k_1)$, $(j_0^{\prime },k_0^{\prime })$, and $(j_1^{\prime },k_1^{\prime })$ are morphisms is similar. 

To see $(j_0^{\prime },k_0^{\prime })\circ (j_0,k_0)$ is homotopic to the identity on $D_0$, observe that for all $a\in A_0$ and $(b,(g,h\left)\right)\in A_1\times X$, we have

$$\begin{array}{cc}{j}_i^{\prime }\left(j_i\right(a\left)\right){\star }_{i}x& =\left(g_i^{\prime }\right(g_i\left(a\right)),b)\star (g,h)\\ & =g_i^{\prime }\left(g_i\right(a\left)\right){\cdot }_{0}h\left(b\right)\\ & =a{\cdot }_{0}h\left(b\right)\\ & =(a,b)\star (g,h)\\ & =a{\star }_0(b,(g,h\left)\right),\end{array}$$

and seeing that $(j_1^{\prime },k_1^{\prime })\circ (j_1,k_1)$, $(j_0,k_0)\circ (j_0^{\prime },k_0^{\prime })$, and $(j_1,k_1)\circ (j_1^{\prime },k_1^{\prime })$ are homotopic to the identity is similar.

Thus, we have that $D_i^{\prime }\simeq D_i$, completing the proof. $\square$

 

In our next post, we will use sub-sum and sub-tensor to define additive subagents, which are like agents that have committed to restrict their class of options; and multiplicative subagents, which are like agents that are contained inside other agents. We will also introduce the concept of sub-environments.

4 comments

Comments sorted by top scores.