Produced as part of the SERI ML Alignment Theory Scholars Program - Summer 2023 Cohort. My thanks to Eric Chen, Elliott Thornley, and John Wentworth for invaluable discussion and comments on earlier drafts. All errors are mine.

This article presents a few theorems about the invulnerability of agents with incomplete preferences. Elliott Thornley’s (2023) proposed approach to the AI shutdown problem relies on these preferential gaps, but John Wentworth and David Lorell have argued that they make agents play strictly dominated strategies.^[1] I claim this is false.

Summary

Suppose there exists a formal description of an agent that willingly shuts down when a certain button is pressed. Elliott Thornley’s (2023) Incomplete Preference Proposal aims to offer such a description. It’s plausible that, for it to constitute a promising approach to solving the AI shutdown problem, this description also needs to (i) permit the agent to be broadly capable and (ii) assure us that the agent will remain willing to shut down as time passes. This article formally derives a set of sufficient conditions for an agent with incomplete preferences to satisfy properties relevant to (i) and (ii).

A seemingly relevant condition for an agent to be capably goal-directed is that it avoids sequences of actions that foreseeably leave it worse off.^[2] I will say that an agent satisfying this condition is invulnerable. This is related to two intuitive conditions. The weaker one is unexploitability: that the agent cannot be forcibly money pumped (i.e., compelled by its preferences to sure loss). The stronger condition is opportunism: that the agent never accepts sure losses or foregoes sure gains.^[3]

To achieve this, I propose a dynamic choice rule for agents with incomplete preferences. This rule, Dynamic Strong Maximality (DSM), requires that the agent consider the available plans that are acceptable at the time of choosing and, among these, pick any plan that wasn’t previously strictly dominated by any other such plan. I prove in section 2 that DSM-based backward induction is sufficient for invulnerability, even under uncertainty.

Having shown that incompleteness does not imply that agents will pursue dominated strategies, I consider the issue of whether DSM leads agents to act as if their preferences were complete. Section 3 begins with a conceptual argument suggesting that DSM-based choice under uncertainty will not, even behaviourally, effectively alter the agent’s preferences over time. This argument does not apply when the agent is unaware of the structure of its decision tree, so I provide some formal results for these cases which bound the extent to which preferences can de facto be completed.

These results show that there will always be sets of options with respect to which the agent never completes its preferences. This holds no matter how many choices it faces. In particular, if no new options appear in the decision tree, then no amount of completion will occur; and if new options do appear, the amount of completion is permanently bounded above by the number of mutually incomparable options. These results apply naturally to cases in which agents are unaware of the state space, but readers sceptical of the earlier conceptual argument can re-purpose them to make analogous claims in standard cases of certainty and uncertainty. Therefore, imposing DSM as a choice rule can get us invulnerability without sacrificing incompleteness, even in the limit.

1.  Incompleteness and Choice

The aim of this brief section is to show that the results that follow in section 2 do not require transitivity. Some question the requirement of transitivity when preferences are incomplete (cf Bradley 2015, p. 3), but if that doesn’t apply to you, a quick skim of this section will provide enough context for the rest.

1.1.  Suzumura Consistency

Requiring that preferences be transitive may require that they be complete. To see this, notice that the weak preference relation $⪰$ on a set of prospects $X$ is transitive just in case $\forall \alpha ,\beta ,\gamma \in X$, $\alpha ⪰\beta$ and $\beta ⪰\gamma$ implies $\alpha ⪰\gamma$. Suppose an agent does weakly prefer $\alpha$ to $\beta$ and $\beta$ to $\gamma$ but has no preference between $\alpha$ and $\gamma$. Then transitivity is violated. Suzumura (1976) proposes a weakening of transitivity for agents with incomplete preferences, which allows for such preferences while preserving some desirable properties. We will say that a weak preference relation is strongly acyclic just in case

    (Strong Acyclicity)   $\forall {\alpha }_1,...,{\alpha }_n\in X$, ${\alpha }_1⪰...⪰{\alpha }_n$ implies ${\alpha }_n\nsucc {\alpha }_1$.

We'll say that an agent whose preferences satisfy this property is Suzumura consistent. Bossert and Suzumura (2010) show that such an agent has some noteworthy features:

1. Strong acyclicity rules out cycles containing at least one strict preference. This will make Suzumura consistent agents invulnerable to (forcing) money pumps.
2. Strong acyclicity is necessary and sufficient for the existence of a complete and transitive extension of the agent’s preference relation.
3. Any preference relation that is both strongly acyclic and complete is transitive.

Preferences that are incomplete may also be intransitive. Whether or not transitivity is a rationality condition, strong acyclicity is weaker but preserves some desirable properties. Below I will mostly just assume strong acyclicity. But since transitivity implies strong acyclicity, all the (sufficiency) results likewise apply to agents with transitive preferences.

1.2.  Strong Maximality

Bradley (2015) proposes a choice rule for Suzumura consistent agents which differs from the standard condition—Maximality—for agents with incomplete preferences.^[4] This rule—Strong Maximality—effectively asks the agent to eliminate dominated alternatives in the following way: eliminate any options that you strictly disprefer to any others, then if you are indifferent between any remaining options and any eliminated ones, eliminate those as well. To state the rule formally, we define a sequence $⟨{\overline{C}}^{\tau }\left(A\right){⟩}_{\tau =0}^{\infty }$ satisfying

${\overline{C}}^0\left(A\right)=\{\alpha \in A:\beta \succ \alpha \exists \beta \in A\}$ and ${\overline{C}}^{\tau }\left(A\right)=\{\alpha \in A:[\beta \sim \alpha ]\wedge [\beta \in {\overline{C}}^{\tau -1}\left(A\right)]\exists \beta \in A\}$ whenever $\tau \ge 1$

for any nonempty set of prospects $A$. We can then state the rule as

    (Strong Maximality)   $C^{\text{SM}}\left(A\right)=\{\alpha \in A:\alpha \notin {\bigcup }_{\tau =0}^{\infty }{\overline{C}}^{\tau }\left(A\right)\}$.

Let’s see intuitively what this rule captures. Suppose $\alpha \succ \beta$ and $\beta \sim \gamma$ but $\alpha \bowtie /\gamma$.^[5] The traditional maximality rule implies that $C\left(\right\{\alpha ,\beta ,\gamma \left\}\right)=\{\alpha ,\gamma \}$. But strong maximality simply outputs $\left\{\alpha \right\}$. This is intuitive: don’t pick an option that’s just as bad as an option you dislike. And, more importantly, Theorem 2 of Bradley (2015) shows that Suzumura consistency is both necessary and sufficient for decisive, strongly maximal choice.^[6]

2.  Uncertain Dynamic Choice

In this section I prove some theorems about the performance of agents with incomplete preferences in dynamic settings. I will amend strong maximality slightly to adapt it to dynamic choice, and show that this is sufficient to guarantee the invulnerability of these agents, broadly construed. I will say that an agent is invulnerable iff it is both unexploitable and opportunistic.

An agent is unexploitable just in case it is immune to all forcing money pumps. These are sequences of decisions through which an agent is compelled by their own preferences to sure loss. An agent is opportunistic just in case it is immune to all non-forcing money pumps. These are situations in which sure loss (or missed gain) is merely permissible, according to an agent’s preferences.

A few aspects of the broad approach are worth flagging. Normative decision theory has not settled on an ideal set of norms to govern dynamic choice. I will therefore provide results with respect to each of the following three dynamic choice principles: naivety, sophistication, and resoluteness. (More details below.) Agents will in general behave differently depending on which principle they follow. So, evaluating the behaviour resulting from an agent’s preferences should, at least initially, be done separately for each dynamic choice principle.

2.1.  Framework

The notation going forward comes from an edited version of Hammond's (1988) canonical construction of Bayesian decision trees. I will only describe the framework briefly, so I’ll refer interested readers to Rothfus (2020a) section 1.6. for discussion.

Definition 1  A decision tree is an eight-tuple $⟨N,C,N,X,N_{+}(\cdot ),n_0,S(\cdot ),\gamma (\cdot )⟩$ where

1. $N$ is a finite set of nodes partitioned into $C$, $N$, and $X$.
2. $C$ is the set of choice nodes. Here agents can pick the node’s immediate successor.
3. $N$ is the set of natural nodes. Agents have credences over their possible realisations.
4. $X$ is the set of terminal nodes. These determine the outcome of a trajectory.
5. $N_{+}:N\to P\left(N\right)$ is the immediate successor function.
6. $n_0$ is the initial node.
7. $S:N\to P\left(S\right)$ assigns the set of states that remain possible once a node is reached.
8. $\gamma \left(x\right)$ is the consequence of reaching terminal node $x$.

Definition 2  A set of plans available at node $n$ of tree $T$, denoted $\Omega (T,n)$, contains the propositions and continuations consistent with the agent being at that node. Formally,

1. $\Omega (T,n)=\left\{S\right(n\left)\right\}$ if $n\in X$.
2. $\Omega (T,n)=\left\{S\right(n^{\prime })\wedge \pi (n^{\prime }):n^{\prime }\in N_{+}(n),\pi (n^{\prime })\in \Omega (T,n^{\prime }\left)\right\}$ if $n\in C$.
3. $\Omega (T,n)=\{{\bigwedge }_{j=1}^{|N_{+}\left(n\right)|}\left[S\right(n_j)\to \pi (n_j\left)\right]:n_j\in N_{+}\left(n\right),\pi \left(n_j\right)\in \Omega (T,n_j)\}$ if $n\in N$.^[7]

I will begin the discussion below with dynamic choice under certainty, but to set up the more general results, I will now lay out the framework for uncertain choice as well and specify later what is assumed. To start, it will be useful to have a representation theorem for our incomplete agents.

Imprecise Bayesianism (Bradley 2017, Theorem 37)   Let $⪰$ be a non-trivial preference relation on a complete and atomless Boolean algebra of prospects $\Omega =⟨X,\models ⟩$, which has a minimal coherent extension on $\Omega$ that is both continuous and impartial.^[8] Then there exists a unique rationalising state of mind, $S=\{⟨P^i,V^i⟩\}$, on $\Omega$ containing all pairs of probability and desirability measures jointly consistent with these preferences, in the sense that for all $\alpha ,\beta \in \Omega \setminus \left\{\perp \right\}$,

    $\alpha ⪰\beta ⟺V^i\left(\alpha \right)\ge V^i\left(\beta \right)\forall V^i\in S$.

This theorem vindicates the claim that the state of mind of a broad class of rational agents with incomplete preferences can be represented by a set of pairs of probability and desirability functions. Although this theorem applies to imprecise credences, I’ll work with the special case of precise beliefs throughout. This will simplify the analysis. I’ll therefore use the following notation going forward: $Z=\{i\in N:V^i\in S\}$.

Next, I define some conditions that will be invoked in some of the derivations.

Definition 3  Material Planning: For a plan to specify choices across various contingencies, I formalise a planning conditional as follows. Let $n$ be a natural node and $n_j\in N_{+}\left(n\right)$ a possible realisation of it. Here, a plan

    $p\left(n\right)=S\left(n\right)\wedge {\bigwedge }_{j=1}^{|N_{+}\left(n\right)|}\left[S\right(n_j)\to S(z_j\left)\right]$

assigns a chosen continuation, $z_j\in N_{+}\left(n_j\right)$, to each possible realisation of $n$. When preferences are complete, a plan at a natural node is then evaluated as follows:

    $V_n\left(p\right)={\sum }_{j=1}^{|N_{+}\left(n\right)|}{V}_n\left(z_j\right)P\left(n_j|p\right(n\left)\right)$.

This is a natural extension of Jeffrey’s equation. And when preferences are incomplete:

    $p{⪰}_n{p}^{\prime }$ iff $V_n^i\left(p\right)\ge V_n^i\left(p^{\prime }\right)\forall i\in Z$.

This makes use of Bradley’s representation theorem for Imprecise Bayesianism.

Definition 4  Preference Stability (Incomplete): For all nodes $n_a$ and $n_b$ and plans $p$ where $p\left(n_a\right)=p\left(n_b\right)$, we have $V_{n_a}^i\left(p\right)=V_{n_b}^i\left(p\right)\forall i\in Z$.

Definition 5  Plan-Independent Probabilities (PIP): For any decision tree $T$ in which $n$ is a natural node, $n^{\prime }\in N_{+}\left(n\right)$ is a realisation of $n$, and $p\in \Omega (T,n)$, $P\left(n^{\prime }|p\right(n\left)\right)=P\left(n^{\prime }|n\right)$.

The results can now be stated. I will include proofs of the central claims in the main text; others are relegated to the appendix. I suggest scrolling past them if you aren’t particularly surprised by the result.

2.2.  Myopia

Let’s begin with the simplest case of exploitation. We can stay silent on which dynamic choice principle to employ here: even if our agent is myopic, it will never be vulnerable to forcing money pumps under certainty. This follows immediately from Suzumura consistency since this guarantees that the agent never has a strict preference in a cycle of weak preferences.

Proposition 1   Suzumura consistent agents myopically applying strong maximality are unexploitable under certainty. [Proof.]

Two points are worth noting about the simple proof. First, it relies on strict preferences. This is because, if a money pump must go through a strongly maximal choice set with multiple elements (due to indifference or appropriate incomparability), it is necessarily non-forcing. That's the topic of the next section. Second, the proof doesn't rely on foresight. Myopia is an intentionally weak assumption that lets us show that no knowledge of the future is required for Suzumura consistent agents to avoid exploitation via these forcing money pumps.

2.3.  Naive Choice

Although Suzumura consistent agents using strong maximality can't be forced into money pumps, concern remains. Such an agent might still incidentally do worse by their own lights. That is, it remains vulnerable to non-forcing money pumps and thereby fails to be opportunistic. The single-souring money pump below is a purported example of this.

The agent’s preferences satisfy $A\succ A^{-}$ and $B\bowtie /A,A^{-}$. Suppose that it’s myopic and uses strong maximality at each node. The agent begins with $A$ at node 0 (if we let ‘down’ be the default). It is permitted, though not compelled, to go ‘up’ at node 0 instead (since $B$ will become available), but also to go ‘up’ upon arrival at node 1 (since $A^{-}\bowtie /B$). Suppose it in fact goes ‘up’ at both node 0 and at node 1. This would leave it with $A^{-}$, which is strictly worse than what it began with. This money pump is ‘non-forcing’ because the agent’s preferences are also consistent with avoiding it.

The agent need not be myopic, however. It can plan ahead.^[9] To achieve opportunism for Suzumura consistent agents, I propose a choice rule which I’ll dub Dynamic Strong Maximality (DSM). DSM states that a plan $p$ is permissible at node $n$ just in case (a) it is strongly maximal at $n$ and (b) no other such plan was previously more choiceworthy than $p$.

(Dynamic Strong Maximality)   $p\in D\left(\Omega \right(T,n\left)\right)$ iff

   (a)  $p\in C^{\text{SM}}\left(\Omega \right(T,n\left)\right)$ and

   (b)  $\mathrm{\exists ̸}{p}^{\ast }\in C^{\text{SM}}\left(\Omega \right(T,n\left)\right):p^{\ast }\in C^{\text{SM}}\left(\Omega \right(T,n_0\left)\right)\ni ̸p$ .

DSM is a slight refinement of strong maximality. Condition (b) simply offers a partial tie-breaking rule whenever the agent faces multiple choiceworthy prospects. So, importantly, it never asks the agent to pick counter-preferentially. An agent following naive choice with DSM will, at each node, look ahead in the decision tree, select their favourite trajectory using DSM, and embark on it. It can continually re-evaluate its plans using naive-DSM as time progresses and, as the following result establishes, the agent will thereby never end up with something worse than what it began with.

Proposition 2 (Strong Dynamic Consistency Under Certainty via Naivety)   Let $T$ be an arbitrary tree where $n$ is a choice node, $n^{\prime }\in N_{+}\left(n\right)$, and $p\in \Omega (T,n)$ is consistent with $S\left(n^{\prime }\right)$. Then $p\left(n\right)\in D\left(\Omega \right(T,n\left)\right)$ iff $p\left(n^{\prime }\right)\in D\left(\Omega \right(T,n^{\prime }\left)\right)$. [Proof.]

Intuitively, this means that (i) if the agent now considers a trajectory acceptable, it will continue to do so as time passes, and (ii) if it at any future point considers some plan continuation acceptable, its past self would agree. It follows immediately that all and only the strongly maximal terminal nodes are reachable by agents choosing naively using DSM (derived as Corollary 1). This gives us opportunism: the agent will never pick a plan that’s strictly dominated some other available plan.

Under certainty, this result is unsurprising.^[10] What is less obvious is whether this also holds under uncertainty. I will say that a Bayesian decision tree exhibits PIP-uncertainty just in case the probability of any given event does not depend on what the agent plans to do after the event has occurred. We can now state the next result.

Proposition 3 (Strong Dynamic Consistency Under PIP-Uncertainty via Naivety)  
Let node $n$ be non-terminal in decision tree $T$, $n^{\prime }\in N_{+}\left(n\right)$, and plan $p\in \Omega (T,n)$ be consistent with $S\left(n^{\prime }\right)$. Assume Material Planning, Preference Stability, and Plan-Independent Probabilities. Then $p\in D\left(\Omega \right(T,n\left)\right)$ iff $p\in D\left(\Omega \right(T,n^{\prime }\left)\right)$.

Proof.  Lemma 3 establishes that $p\in D\left(\Omega \right(T,n\left)\right)$ implies $p\in D\left(\Omega \right(T,n^{\prime }\left)\right)$. To prove the converse, suppose that $p\in D\left(\Omega \right(T,n^{\prime }\left)\right)$. Node $n$ was either a choice node or a natural node. If it was a choice node, then it follows immediately from Proposition 2 that $p\in D\left(\Omega \right(T,n\left)\right)$.

Now let $n$ be a natural node. By Lemma 2, $C^{\text{Opt}}(\cdot )=C^{\text{SM}}(\cdot )=D(\cdot )$ under coherent extension. So by Theorem 37 of Bradley (2017),

    $V_{n^{\prime }}^i\left(p\right(n^{\prime }\left)\right)\ge V_{n^{\prime }}^i\left(p^{\prime }\right(n^{\prime }\left)\right)\exists i\in Z$ for all $p^{\prime }\in \Omega (T,n^{\prime })$.

Let $z^{\prime }\left[q\right]$ denote the continuation selected by plan $q$ upon reaching choice node $n^{\prime }$. Thus

    $V_{n^{\prime }}^i\left(z^{\prime }\right[p\left]\right)\ge V_{n^{\prime }}^i\left(z^{\prime }\right[p^{\prime }\left]\right)\exists i\in Z$ for all $p^{\prime }\in \Omega (T,n^{\prime })$.

By Preference Stability,

    $V_n^i\left(z^{\prime }\right[p\left]\right)\ge V_n^i\left(z^{\prime }\right[p^{\prime }\left]\right)\exists i\in Z$ for all $p^{\prime }\in \Omega (T,n^{\prime })$. (1)

Notice that this implies that

    $V_n^i\left(z^{\prime }\right[p\left]\right)P\left(n^{\prime }|n\right)\ge V_n^i\left(z^{\prime }\right[p^{\prime }\left]\right)P\left(n^{\prime }|n\right)\exists i\in Z$ for all $p^{\prime }\in \Omega (T,n^{\prime })$. (2)

And by Plan-Independent Probabilities, this is equivalent to

    $V_n^i\left(z^{\prime }\right[p\left]\right)P\left(n^{\prime }|p\right(n\left)\right)\ge V_n^i\left(z^{\prime }\right[p^{\prime }\left]\right)P\left(n^{\prime }|p^{\prime }\right(n\left)\right)\exists i\in Z$ for all $p^{\prime }\in \Omega (T,n^{\prime })$. (3)

By Material Planning, $p\in C^{\text{SM}}\left(\Omega \right(T,n\left)\right)$ holds iff

    ${\sum }_j{V}_n^i\left(z_j\right[p\left]\right)P\left(n_j|p\right(n\left)\right)\ge {\sum }_j{V}_n^i\left(z_j\right[p^{\prime }\left]\right)P\left(n_j|p^{\prime }\right(n\left)\right)\exists i\in Z$ for all $p^{\prime }\in \Omega (T,n^{\prime })$.

Using (2)-(3) this is equivalent to

$V_n^i\left(z^{\prime }\right[p\left]\right)P\left(n^{\prime }|n\right)+{\sum }_{j\ne j^{\prime }}{V}_n^i\left(z_j\right[p\left]\right)P\left(n_j|n\right)\ge V_n^i\left(z^{\prime }\right[p^{\prime }\left]\right)P\left(n^{\prime }|n\right)+{\sum }_{j\ne j^{\prime }}{V}_n^i\left(z_j\right[p^{\prime }\left]\right)P\left(n_j|n\right)$

for some $i\in Z$ and all $p^{\prime }\in \Omega (T,n^{\prime })$. (4)

Formally, $z^{\prime }\left[p\right]=p\left(n^{\prime }\right)$ omits description of $p\left(n_j\right)$ for all $n_j\in N_{+}\left(n\right)\setminus \left\{n^{\prime }\right\}$. So, we can let $p\left(n_j\right)=p^{\prime }\left(n_j\right)$ at all remaining realisations $n_j$. Then (4) reduces to

$V_n^i\left(z^{\prime }\right[p\left]\right)P\left(n^{\prime }|n\right)\ge V_n^i\left(z^{\prime }\right[p^{\prime }\left]\right)P\left(n^{\prime }|n\right)$

$V_n^i\left(z^{\prime }\right[p\left]\right)\ge V_n^i\left(z^{\prime }\right[p^{\prime }\left]\right)$. (The probability is nonzero as $n^{\prime }$ is realised by assumption.)

This holds via (1), so $p\in C^{\text{SM}}\left(\Omega \right(T,n\left)\right)$ and, by Lemma 2, $p\in D\left(\Omega \right(T,n\left)\right)$. $■$

We have thereby shown that a naive DSM agent is strongly dynamically consistent in a very broad class of cases. Although these results are restricted to PIP-uncertainty, this applies to agents with complete preferences too. It’s just a result of the forward-looking nature of naive choice. In the next section, I will drop the PIP restriction by employing a different dynamic choice principle.

2.4.  Sophisticated Choice

Sophistication is the standard principle in dynamic choice theory. It achieves dynamic consistency in standard cases by using backward induction to achieve the best feasible outcome. (This is also the method by which subgame perfect equilibria are found in dynamic games of perfect information.) However, backward induction is undefined whenever the prospects being compared are either incomparable or of equal value. Rabinowicz (1995) proposed a ‘splitting procedure’ to address this, and Asheim (1997) used a similar approach to refine subgame perfection in games.

According to this procedure, whenever there is a tie between multiple prospects, the agent will split the sequential decision problem into parts, where each part assumes that a particular prospect was chosen at that node. The agent then compares each part’s solution and picks its favourite as the solution to the grand decision problem. Intuitively, these agents will follow a plan as long as they lack “a positive reason for deviation” (Rabinowicz 1997). In other words, the agent will consider all the plans that would not make it locally act against their own preferences and, among those plans, proceed to pick the one with the best ex-ante outcome.

In the case of incomplete preferences, however, it turns out that strongly maximal sophisticated choice with splitting will not suffice to guarantee opportunism. The reason behind this is that strong maximality does not satisfy Set Expansion, and that backward induction makes local comparisons.^[11]

Proposition 4   Strongly maximal sophisticated choice with splitting does not guarantee opportunism for Suzumura consistent agents. [Proof.]

DSM, however, will suffice.

Proposition 5 (Strong Dynamic Consistency Under Certainty via Sophistication)
Assume certainty and Suzumura consistency. Then DSM-based backward induction with splitting reaches a strongly maximal terminal node. [Proof.]

More importantly, we can guarantee this property under uncertainty even without PIP.

Proposition 6 (Strong Dynamic Consistency Under Uncertainty via Sophistication)
Let $T$ be a Bayesian decision tree in which $n$ is a non-terminal node, $n^{\prime }\in N_{+}\left(n\right)$ is a successor, and $p\in \Omega (T,n)$ is consistent with $S\left(n^{\prime }\right)$. Assume Material Planning and Preference Stability. Then with DSM-based backward induction (DSM-BI), $p$ is permissible at $n$ iff $p$ is permissible at $n^{\prime }$.

Proof.  We begin by formalising DSM-BI. For tree $T$, let $X$ denote its terminal nodes, $C$ its choice nodes, and $N$ its natural nodes. Let $I[n,A]=\{p\in \Omega (T,n):p(n^{\prime })\in A\}$ denote the set of plans available at $n$ that are consistent with some associated plan continuation in $A$. We then define the tree’s permissible set of plans, $\Psi \left(T\right)$, recursively:

1. $\tilde{\Psi }(T,n)=\left\{S\right(n\left)\right\}$ for $n\in X$.
2. $\tilde{\Psi }(T,n)=D\left(I\right[n,\Phi \left(n\right)\left]\right)$ where $\Phi \left(n\right)={\bigcup }_{n_i\in N_{+}\left(n\right)}\tilde{\Psi }(T,n_i)$ , for $n\in C$.
3. $\tilde{\Psi }(T,n)={\bigcap }_{n_i\in N_{+}\left(n\right)}I[n,\tilde{\Psi }(T,n_i\left)\right]$ for $n\in N$.

The permissible set of plans is then given by $\Psi \left(T\right)\triangleq \tilde{\Psi }(T,n_0)$. Notice that this is the set of plans consistent with backward induction using DSM, and that splitting is implicit since each pruning of the decision tree is set-valued.

Now suppose that $p\in \tilde{\Psi }(T,n)$ for some $n\in C$.

Then $p\in D\left(I\right[n,\Phi \left(n\right)\left]\right)$ , where $\Phi \left(n\right)={\bigcup }_{n_i\in N_{+}\left(n\right)}\tilde{\Psi }(T,n_i)$.

So necessarily $p\in I[n,\Phi (n\left)\right]$. By construction of $I[\cdot ,\Phi (\cdot \left)\right]$, we know that $p\left(n^{\prime }\right)\in \Phi \left(n\right)$.

And since $\Phi \left(n\right)=\tilde{\Psi }(T,n^{\prime })\cup {\bigcup }_{n_i\ne n^{\prime }}\tilde{\Psi }(T,n_i)$, we have $p\left(n^{\prime }\right)\in \tilde{\Psi }(T,n^{\prime })$.

Next, suppose that $p\in \tilde{\Psi }(T,n)$ for some $n\in N$. Then $p\in {\bigcap }_{n_i\in N_{+}\left(n\right)}I[n,\tilde{\Psi }(T,n_i\left)\right]$ . So, for any particular $n^{\prime }\in N_{+}\left(n\right)$, $p\in I[n,\tilde{\Psi }(T,n^{\prime }\left)\right]$. Therefore $p\left(n^{\prime }\right)\in \tilde{\Psi }(T,n^{\prime })$ as needed.

Having established $p\in \tilde{\Psi }(T,n)⟹p\left(n^{\prime }\right)\in \tilde{\Psi }(T,n^{\prime })$, we proceed to the converse. ($\ast$)

Notice that the only nodes reachable via sophisticated choice are those that are consistent with some plan $p\in \Psi \left(T\right)$ which was initially permissible. Therefore, for any $n^{\prime }$ that is reached, there must be some $p\in \Omega (T,n)$, consistent with $n^{\prime }$ where $n^{\prime }\in N_{+}\left(n\right)$, which satisfies $p\in \tilde{\Psi }(T,n)$.

Suppose $p\left(n^{\prime }\right)\in \tilde{\Psi }(T,n^{\prime })$ for some reachable $n^{\prime }\in N$. Whether $n$ is a choice or a natural node, we know by construction of (2) and (3) that

    $\tilde{\Psi }(T,n)\subseteq I[n,{\bigcup }_{n_i\in N_{+}\left(n\right)}\tilde{\Psi }(T,n_i)]$.

Therefore, if $n^{\prime }$ is reached, then the permissible plans at $n^{\prime }$ must be continuations of plans that were permissible at $n$. Hence $p\left(n\right)\in \tilde{\Psi }(T,n)$.