I am trying to check that I am understanding this correctly by applying it, though probably not in a very meaningful way:
Am I right in reasoning that, for , that iff ( (C can ensure S), and (every element of S is a result of a combination of a possible configuration of the environment of C with a possible configuration of the agent for C, such that the agent configuration is one that ensures S regardless of the environment configuration)) ?
So, if S = {a,b,c,d} , then
would have , but, say
would have , because , while S can be ensured, there isn't, for every outcome in S, an option which ensures S and which is compatible with that outcome ?
Yep.
There is a single morphism from to for every world in , so means all of these morphism factor through .
A morphism from to is basically a column of and a morphism from to is basically an row in , all of whose entries are in , and these compose to the morphism corresponding to the entry where this column meets this row.
Thus if and only if when you delete all rows not entirely in , the resulting matrix has image .
I think this equivalent to what you said. I just wrote it out myself because that was the easiest way for me to verify what you said.
Given that C ◃ C, I kind of wish that the triangle had a line under it, so that I didn't think it might represent a strict relationship.
I am very experienced in category theory but not the Chu construction (or *-autonomous categories in general). There is a widely used notion of subobject of an object in a category as "equivalence class of monomorphisms with codomain ". This differs from your definition most conspicuously in the case of where there is no morphism from this frame to a typical frame.
If I'm calculating correctly, the standard notion of subobject is strictly stronger than the one you present here (as long as the world is inhabited, and even in that case I think the construction collapses enough to make it true) since monomorphisms are morphisms which are injective in their agent argument and surjective in their environment argument, and we can extend any morphism to along such a monomorphism.
Now, I notice that you refer to the concepts in this post as subagents rather than subframes, so perhaps you were deliberately avoiding this stronger concept. Intuitively, a subframe in the sense I describe above consists of an agent with a subset of the available options and who may not be able to distinguish between some of the environments present in a larger frame; the "precommitted agent" you mention early on here seems to be a special case of this which is the identity in the environment component. Incidentally, the equivalence relation corresponding to this notion of subobject corresponds to isomorphism in the finite case but is non-trivial for a similar reason to the case you described of infinite frames.
I wonder if you have any thoughts about how these notions compare? It's clear from the discussion that you chose a definition which reflected what you wanted to express, which is always good, but on the other hand the monomorphisms I described will crop up when you consider factorizations of the morphisms in your category more generally. Perhaps they could be useful to you.
Here, we introduce and discuss the concept of a subagent in the Cartesian Frames paradigm.
Note that in this post, as in much of the sequence, we are generally working up to biextensional equivalence. In the discussion, when we informally say that a frame has some property or is some object, what we'll generally mean is that this is true of its biextensional equivalence class.
1. Definitions of Subagent
1.1. Categorical Definition
Definition: Let C and D be Cartesian frames over W. We say that C's agent is a subagent of D's agent, written C◃D, if for every morphism ϕ:C→⊥ there exists a pair of morphisms ϕ0:C→D and ϕ1:D→⊥ such that ϕ=ϕ1∘ϕ0.
Colloquially, we say that every morphism from C to ⊥ factors through D. As a shorthand for "C's agent is a subagent of D's agent," we will just say "C is a subagent of D."
At a glance, it probably isn't clear what this definition has to do with subagents. We'll first talk philosophically about what we mean by "subagent", and then give an alternate definition that will make the connection more clear.
When I say "subagent," I am actually generalizing over two different relationships that may not immediately seem like they belong together.
First, there is the relationship between the component and the whole. One football player is a subagent of the entire football team.
Second, there is the relationship between an agent before and after making a precommitment or a choice. When I precommit not to take a certain action, I am effectively replacing myself with a weaker agent that has fewer options. The new agent with the commitment is a subagent of the original agent.
These are the two notions I am trying to capture with the word "subagent". I am making the philosophical claim that we should think of them primarily as one concept, and am partially backing up this claim by pointing to the simplicity of the above definition. In a future post, we will discuss the formal differences between these two kinds of subagent, but I think it is best to view them as two special cases of the one simple concept.
(My early drafts of the "Embedded Agency" sequence used the word "subagent" in the title for both the Subsystem Alignment and Robust Delegation sections.)
1.2. Currying Definition
Definition: Let C and D be Cartesian frames over W. We say that C◃D if there exists a Cartesian frame Z over Agent(D) such that C≃D∘(Z).
Assume for this discussion that we only care about frames up to biextensional equivalence. In effect, the above definition is saying that "C is a subagent of D" means "C's agent is playing a game, Z, where the stakes are to help decide what D's agent does." (And this game may or may not have multiple players, and may or may not fully cover all the options of D's agent.)
Letting C=(A,E,⋅) and D=(B,F,⋆), it turns out (as we will see later) that we can explicitly construct Z. Z=(A,X,⋄), where X is the set of all morphisms from C to D, and ⋄:A×X→B is given by a⋄(g,h)=g(a).
We will later prove the categorical and currying definitions equivalent, but let's first interpret this definition using examples.
Z is a Cartesian frame whose agent is the agent of C and whose world is the agent of D. This seems like the kind thing we would have when C is a subagent of D.
Thinking about the football example: We have the football player A as the agent in a Cartesian frame C over the world W. We also have the football team B as the agent in a Cartesian frame D over the same world W.
Z is a Cartesian frame over the football team; and the agent of this frame is again the football player A. X, the environment of Z, represents the rest of the football team: the player's effect on the team as a whole (here treated as the player's world) is a function of what the player chooses and what the rest of the team chooses. We can think of Z as representing a "zoomed-in" picture of A interacting with its local environment (the team), while C represents a "zoomed-out" picture of A interacting with its teammates and the larger world (rival teams, referees, etc.).
D∘(Z)=(A,X×F,∙), so E is equivalent to X×F, which is saying that the environment for the football player in its original frame (C) is equivalent to the Cartesian product of the rest of the team X with the team's environment F.
Thinking about the precommitment example: C has made a precommitment, so there is an inclusion morphism ι:A→B, which shows that C's agent's options are a subset of D's agent's options. Z is just CF∗({ι}), so X={ι} is a singleton. D∘(Z)=(A,X×F,∙), so E is equivalent to X×F=F, so here A is a subset of B and E is equivalent to F.
Although the word "precommitment" suggests a specific (temporal, deliberative) interpretation, formally, precommitment just looks like deleting rows from a matrix (up to biextensional equivalence), which can represent a variety of other situations.
A Cartesian frame Z=(A,X,⋄) over B is like a nondeterministic function from A to B, where X represents the the nondeterministic bits. When changing our frame from (B,F,⋆) to (A,E,⋅)≃(A,X×F,∙), we are identifying with A and externalizing the nondeterministic bits X into the environment.
1.3. Covering Definition
The categorical definition is optimized for elegance, while the currying definition is optimized to be easy to understand in terms of agency. We have a third definition, the covering definition, which is optimized for ease of use.
Definition. Let C=(A,E,⋅) and D=(B,F,⋆) be Cartesian frames over W. We say that C◃D if for all e∈E, there exists an f∈F and a (g,h):C→D such that e=h(f).
We call this the covering definition because the morphisms from C to D cover the set E.
2. Equivalence of Definitions
2.1. Equivalence of Categorical and Covering Definitions
The equivalence of the categorical and covering definitions follows directly from the fact that the morphisms from C to ⊥ are exactly the elements of Env(C).
Claim: The categorical and covering definitions of subagent are equivalent.
Proof: Let C=(A,E,⋅) and let D=(B,F,⋆). First, observe that the morphisms from C to ⊥ correspond exactly to the elements of E. For each e∈E, it is easy to see that (g,h):C→(W,{j},⋄), given by h(j)=e and g(a)=a⋅e, is a morphism, and every morphism is uniquely defined by h(j), so there are no other morphisms. Let ϕe denote the morphisms with h(j)=e.
Similarly, the morphisms from D to ⊥ correspond to the elements of F. Let ψf denote the morphisms corresponding to f∈F.
Thus, the categorical definition can be rewritten to say that for every morphism ϕe:C→⊥, there exist morphisms (g,h):C→D and ψf:D→⊥, such that ϕe=ψf∘(g,h). However, ψf∘(g,h):C→(W,{j},⋄) sends j to h(f), and so equals ϕe if and only if e=h(f). Thus the categorical definition is equivalent to the covering definition. □
2.2. Equivalence of Covering and Currying Definitions
Claim: The covering definition of subagent implies the currying definition of subagent.
Proof: Let C=(A,E,⋅) and D=(B,F,⋆) be Cartesian frames over W. Assume that C◃D according to the covering definition.
Let X be the set of all morphisms from C to D, and let Z=(A,X,⋄) be a Cartesian frame over B, with ⋄ given by a⋄(g,h)=g(a). We have that D∘(Z)=(A,X×F,∙), with
a∙((g,h),f)=(a⋄(g,h))⋆f=g(a)⋆ffor all a∈A, (g,h)∈X, and f∈F.
To show that C≃D∘(Z), we need to construct morphisms g0,h0:C→D∘(Z) and g1,h1:D∘(Z)→C which compose to something homotopic to the identity in both orders.
We will let g0 and g1 be the identity on A, and we let h0:X×F→E be given by h0((g,h),f)=h(f). Finally, we let h1(e)=((g,h),f) such that h(f)=e. We can always choose such a (g,h)∈X and f∈F by the covering definition of subagent.
We have that (g0,h0) is a morphism, since
g0(a)∙((g,h),f)=a∙((g,h),f)=g(a)⋆f=a⋅h(f)=a⋅h0((g,h),f).Similarly, we have that (g1,h1) is a morphism since h1(e)=((g,h),f), where h(f)=e, so
g1(a)⋅e=a⋅e=a⋅h(f)=g(a)⋆f=a∙((g,h),f)=a∙h1(e).It is clear that (g0,h0) and (g1,h1) compose to something homotopic to the identity in both orders, since g0 and g1 are the identity on A. Thus, C≃D∘(Z). □
Claim: The currying definition of subagent implies the covering definition of subagent.
Proof: Let C=(A,E,⋅) and D=(B,F,⋆) be Cartesian frames over W. Let Z=(Y,X,⋄) be a Cartesian frame over B, and let C≃D∘(Z). Our goal is to show that for every e∈E, there exists a (g,h):C→D and f∈F such that e=h(f). We will start with the special case where C=D∘(Z).
We have that D∘(Z)=(Y,X×F,∙), where y∙(x,f)=(y⋄x)⋆f. First, note that for every x∈X, there exists a morphism (gx,hx):D∘(Z)→D given by gx(y)=y⋄x, and hx(f)=(x,f). To see that this is a morphism, observe that
gx(y)⋆f=(y⋄x)⋆f=y∙(x,f)=f∙hx(f)for all y∈Y and f∈F.
To show that D∘(Z)◃D according to the covering definition, we need that for all (x,f)∈X×F, there exists an f′∈F and a (g,h):D∘(Z)→D such that h(f′)=(x,f). Indeed we can take (g,h)=(gx,hx) and f′=f.
Now, we move to the case where C≃D∘(Z), but C≠D∘(Z). It suffices to show that under the covering definition of subagent, if C0◃D, and C1≃C0, then C1◃D.
Let Ci=(Ai,Ei,⋅i), and let (g0,h0):C0→C1 and (g1,h1):C1→C0 compose to something homotopic to the identity in both orders. Assume that C0◃D. To show that C1◃D, let the possible environment e∈E1 be arbitrary.
h0(e)∈E0, so there exists an f∈F and (g,h):C0→D such that h(f)=h0(e). Consider the morphism (g′,h′):C1→D, where g′=g∘g1, and h′(f)=e and h′(f′)=(h1∘h)(f′) on all f′≠f. To see that this is a morphism, observe that for all a∈A1, we have
g′(a)⋆f=g(g1(a))⋆f=a⋅1h1(h(f))=a⋅1h1(h0(e))=a⋅1e=a⋅1h′(f),while for f′∈F, f′≠f, we have
g′(a)⋆f′=g(g1(a))⋆f′=a⋅1h1(h(f′))=a⋅1h′(f′).Now, notice that for our arbitrary e∈E1, (g′,h′):C1→D and f∈F satisfy h′(f)=e, so C1◃D according to the to the covering definition.
Thus, whenever C≃D∘(Z), we have C◃D according to the covering definition, so the currying definition implies the covering definition of subagent. □
3. Mutual Subagents
The subagent relation is both transitive and reflexive. Surprisingly, this relation is not anti-symmetric, even up to biextensional equivalence.
Claim: ◃ is reflexive. Further, if C≃D, then C◃D.
Proof: Let C=(A,E,⋅) and D=(B,F,⋅) be Cartesian Frames over W, with C≃D. Consider the Cartesian frame Z over B given by Z=(B,{x},⋄), where b⋄x=b. Observe that D≅D∘(Z). Thus C≃D∘(Z), so C◃D, according to the currying definition. □
Claim: ◃ is transitive.
Proof: We will use the categorical definition. Let C0◃C1 and C1◃C2. Given a morphism, ϕ0:C0→⊥, since C0◃C1, we know that ϕ0=ϕ1∘ϕ2 with ϕ1:C1→⊥ and ϕ2:C0→C1. Further, since C1◃C2, we know that ϕ1=ϕ3∘ϕ4 with ϕ3:C2→⊥ and ϕ4:C1→C2. Thus,
ϕ0=(ϕ3∘ϕ4)∘ϕ2=ϕ3∘(ϕ4∘ϕ2),with ϕ3:C2→⊥ and ϕ4∘ϕ2:C0→C2, so C0◃C2. □
As a corollary, we have that subagents are well-defined up to biextensional equivalence.
Corollary: If C0≃C1, D0≃D1, and C0◃D0, then C1◃D1.
Proof: C1◃C0◃D0◃D1. □
Sometimes, there are Cartesian frames C≄D with C◃D and D◃C. We can use this fact to define a third equivalence relation on Cartesian frames over W, weaker than both ≅ and ≃.
Definition: For Cartesian frames C and D over W, we say C⋈D if C◃D and D◃C.
Claim: ⋈ is an equivalence relation.
Proof: Reflexivity and transitivity follow from reflexivity and transitivity of ◃. Symmetry is trivial. □
This equivalence relation is less natural than ≅ and ≃, and is not as important. We discuss it mainly to emphasize that two frames can be mutual subagents without being biextensionally equivalent.
Claim: ⋈ is strictly weaker than ≃, which is strictly weaker than ≅.
Proof: We already know that ≃ is weaker than ≅. To see that ⋈ is weaker than ≃, observe that if C≃D, then C◃D and D◃C, so C⋈D.
To see that ≃ is strictly weaker than ≅, observe that ⊤⊕⊤≃⊤ (both have empty environment and nonempty agent), but ⊤⊕⊤≆⊤ (the agents have different size).
To see that ⋈ is strictly weaker than ≃, observe that ⊤⋈null (vacuous by covering definition), but ⊤≄null (there are no morphisms from null to ⊤). □
I do not have a simple description of exactly when C⋈D, but there are more cases than just the trivial ones like C≃D and vacuous cases like ⊤⋈null. As a quick example:
(xy)⋈⎛⎜⎝xxyyxy⎞⎟⎠.
To visualize this, imagine an agent that is given the choice between cake and pie. This agent can be viewed as a team consisting of two subagents, Alice and Bob, with Alice as the leader.
Alice has three choices. She can choose cake, she can choose pie, or she can delegate the decision to Bob. We represent this with a matrix where Bob is in Alice's environment, and the third row represents Alice letting the environment make the call:
⎛⎜⎝xxyyxy⎞⎟⎠.
If we instead treat Alice-and-Bob as a single superagent, then their interaction across the agent-environment boundary becomes agent-internal deliberation, and their functional relationship to possible worlds just becomes a matter of "What does the group decide?". Thus, Alice is a subagent of the Alice-and-Bob team:
⎛⎜⎝xxyyxy⎞⎟⎠◃(xy).
However, Alice also has the ability to commit to not delegating to Bob. This produces a future version of Alice that doesn't choose the third row. This new agent is a precommitment-style subagent of the original Alice, but using biextensional collapse, we can also see that this new agent is equivalent to the smaller matrix. Thus:
(xy)≃(xxyy)◃⎛⎜⎝xxyyxy⎞⎟⎠.
It is also easy to verify formally that these are mutual subagents using the covering definition of subagent.
I'm reminded here of the introduction and deletion of mixed strategies in game theory. The third row of Alice's frame is a mix of the first two rows, so we can think of Bob as being analogous to a random bit that the environment cannot see. I informally conjecture that for finite Cartesian frames, C⋈D if and only if you can pass between C and D by doing something akin to deleting and introducing mixed strategies for the agent.
However, this informal conjecture is not true for infinite Cartesian frames:
⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝zxzzz⋯zyzzz⋯zzxzz⋯zzyzz⋯zzzxz⋯zzzyz⋯zzzzx⋯zzzzy⋯⋮⋮⋮⋮⋮⋱⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠⋈⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝zyzzz⋯zzxzz⋯zzyzz⋯zzzxz⋯zzzyz⋯zzzzx⋯zzzzy⋯⋮⋮⋮⋮⋮⋱⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠.
We can see that these frames are mutual subagents by noting that one can transition back and forth by repeatedly committing not to take the top row.
I do not know of any examples of ⋈ that look qualitatively different from those discussed here, but I do not have a good understanding of exactly what the equivalence classes look like.
4. Universal Subagents and Superagents
We can view ⊤ as a universal subagent and ⊥ as a universal superagent.
Claim: ⊤◃C◃⊥ for all Cartesian frames C.
Proof: We use the categorical definition. That ⊤◃C is vacuous, since there is no morphism from ⊤ to ⊥. That C◃⊥ is also trivial, since any ϕ:C◃⊥ is equal to ϕ∘id⊥. □
Since null⋈⊤, we also have null◃C for all C.
We also have a that ⊥S is a superagent of all Cartesian frames with image in S.
Claim: C◃⊥S if and only if Image(C)⊆S.
Proof: Let C=(A,E,⋅), and let ⊥S=(S,{f},⋆), with s⋆f=s.
First, assume Image(C)⊆S. We will use the covering definition. Given an e∈E, let (g,h):C→⊥S be given by g(a)=a⋅e and h(f)=e. We have that g is well-defined because Image(C)⊆S, and (g,h) is a morphism because for all a∈A,
a⋅h(f)=a⋅e=g(a)=g(a)⋆f.Thus, there is a morphism (g,h):C→⊥S and an element f∈{f} such that h(f)=e for an arbitrary e∈E, so C◃⊥S.
Conversely, assume Image(C)⊈S, so let a∈A and e∈E be such that a⋅e∉S. If we assume for contradiction that C◃⊥S, then by the covering definition, there must be a morphism (g,h):C→⊥S such that h(f)=e. But then we have that
a⋅e=a⋅h(f)=g(a)⋆f=g(a)must be both inside and outside of S, a contradiction. □
Convention: We will usually write C◃⊥S instead of Image(C)⊆S, as it is shorter.
Corollary: S∈Obs(C) if and only if C≃C0&C1 for some C0◃⊥S and C1◃⊥W∖S.
Proof: This is just rewriting our definition of observables from "Controllables and Observables, Revisited." □
In the coming posts, we will introduce multiplicative operations on Cartesian frames, and use these to distinguish between additive and multiplicative subagents and superagents.