Order Effects in Sequential Dominance Elimination

Why Deletion Order Is Worth Checking

When a decision class contains rules that are no better, and sometimes worse, than other available rules, removing them can simplify comparisons without losing risk performance. In a finite class, however, the deletion path can depend on which available dominator is chosen first. The important question is whether that path dependence changes what remains at the end.

For pointwise comparison over a fixed parameter space, strict risk dominance has a useful transitivity property. It implies that different valid deletion orders can produce different intermediate classes, but not different terminal classes. This conclusion relies on keeping the full parameter space fixed and using the same strict-dominance convention at every step. Optional removal of rules with identical risks is a separate convention and can leave different rule labels behind.

Definitions for Sequential Elimination

Definition: Let $\mathcal D$ be a finite set of decision rules, with risk function $R_\delta(\theta)$ for rule $\delta$ at parameter value $\theta\in\Theta$. A rule $\delta'$ strictly dominates $\delta$ if $$ R_{\delta'}(\theta)\leq R_\delta(\theta)\quad\text{for every }\theta\in\Theta, $$ and the inequality is strict for at least one $\theta\in\Theta$. A valid deletion step removes a rule only when another rule still in the current class strictly dominates it. A class is terminal if no rule in it is strictly dominated by another rule in it.

The inequalities compare risks over the entire parameter space, not just at selected parameter values. Strict dominance is irreflexive: no rule strictly dominates itself. It is also transitive. If $\delta_1$ dominates $\delta_2$, and $\delta_2$ dominates $\delta_3$, then for every $\theta$, $$ R_{\delta_1}(\theta)\leq R_{\delta_2}(\theta)\leq R_{\delta_3}(\theta). $$ At a parameter value where the first inequality is strict, $R_{\delta_1}(\theta)<R_{\delta_3}(\theta)$. Thus $\delta_1$ strictly dominates $\delta_3$.

Worked Example: Two Paths Through the Same Risk Table

Suppose the parameter space has three values, and the available rules have these risk vectors, listed in the order $(\theta_1,\theta_2,\theta_3)$:

A=(0,3,3),\quad B=(1,1,3),\quad C=(3,1,1),\quad E=(2,3,3),\quad D=(3,3,3).

Rule $A$ strictly dominates $E$, since $0\leq2$, $3\leq3$, and $3\leq3$, with a strict inequality in the first coordinate. Rule $E$ strictly dominates $D$, since $2\leq3$, $3\leq3$, and $3\leq3$, again with a strict inequality in the first coordinate. Also, $A$ strictly dominates $D$ directly.

One valid sequence deletes $D$ using $E$, then deletes $E$ using $A$. Another deletes $E$ using $A$, then deletes $D$ using $A$. The intermediate classes differ: the first retains $E$ after its first deletion, while the second does not. Both finish with $\{A,B,C\}$.

No remaining pair among $A,B,C$ is comparable by strict dominance. For instance, $A$ has lower risk than $B$ at $\theta_1$, but higher risk at $\theta_2$; analogous coordinate checks show that $B$ and $C$, and $A$ and $C$, are also incomparable. The two paths therefore reach the same terminal class, despite taking different steps.

The Terminal Class Does Not Depend on Deletion Order

Theorem: For a finite class $\mathcal D$ with fixed risk functions on a fixed parameter space, any sequence of valid strict-dominance deletions terminates at the set of rules in $\mathcal D$ that are not strictly dominated by any rule in $\mathcal D$. In particular, the terminal set is independent of deletion order.

Proof. First, a rule that is not dominated by any rule in the original class cannot be deleted: every possible dominator at a later step would also belong to the original class. Thus every such rule remains in every deletion sequence.

Now take a rule $\delta$ that is strictly dominated by some rule in $\mathcal D$. If that dominator is itself dominated, follow the chain of dominators. Strict dominance is transitive and irreflexive, so a chain cannot revisit a rule. Because $\mathcal D$ is finite, the chain must end at a rule $\gamma$ that is not dominated by any rule in $\mathcal D$. Transitivity gives that $\gamma$ strictly dominates $\delta$. The rule $\gamma$ cannot be deleted, by the first part of the proof. Therefore, $\delta$ cannot belong to a terminal class: at that stage $\gamma$ is still present and dominates it. So every terminal class contains exactly the rules that were undominated in the original class. $\square$

The theorem concerns the terminal set, not the sequence of classes along the way. A deletion order may change which dominator is available when a particular rule is removed, and it may change how many steps are needed. It cannot make an originally undominated rule deletable or leave an originally dominated rule in a terminal class.

What Risk Properties Survive Deletion?

Every removed rule has a replacement among the terminal rules whose risk is no greater at any parameter value. To see why, follow the chain of dominators from the deleted rule as in the proof. The chain ends at an originally undominated rule that remains in the terminal class, and transitivity ensures that this terminal rule dominates the deleted one.

Takeaway: In a finite class, strict pointwise dominance deletion preserves the property that every original rule has a terminal rule with no greater risk anywhere in $\Theta$. Consequently, if the original class provides a no-worse-risk representative for each rule in a larger class, the terminal class does too: replace the original representative by a terminal rule that dominates it.

Worked Example: Replacing a Deleted Rule Along a Chain

Consider three rules with risk vectors over two parameter values:

P=(0,2),\qquad Q=(1,3),\qquad S=(2,4).

For $P$ and $Q$, the coordinate comparisons are $0\leq1$ and $2\leq3$, with strict inequalities in both coordinates. Thus $P$ dominates $Q$. Similarly, $1\leq2$ and $3\leq4$, so $Q$ dominates $S$. Transitivity, or direct comparison of $P$ with $S$, shows $0\leq2$ and $2\leq4$, with strict inequalities in both coordinates: $P$ dominates $S$.

If $S$ is deleted first using $Q$, then $Q$ is deleted using $P$. At the end, $P$ remains and has risk no greater than either deleted rule at both parameter values. If $Q$ is deleted first using $P$, then $S$ can be deleted using $P$ directly. In either order, the terminal rule $P$ replaces all the original rules without increasing risk anywhere.

Equivalent Rules and Different Survivor Labels

Strict dominance requires a strict improvement somewhere. Consequently, two distinct rules with identical risk functions do not strictly dominate each other. Under the theorem’s convention, both remain if neither has another strict dominator. Some reduction procedures also permit deletion of a rule when another has equal risk everywhere. This can be useful for avoiding redundant labels, but it is not strict-dominance elimination, and it can produce different surviving rule sets.

Worked Example: Choosing Between Risk-Equivalent Rules

Let $\Theta=\{\theta_1,\theta_2\}$, and suppose three rules have risks $$ U=(1,2),\qquad V=(1,2),\qquad W=(2,3). $$

Both $U$ and $V$ strictly dominate $W$: at each parameter value their risks, $1$ and $2$, are lower than $W$'s risks, $2$ and $3$. But neither $U$ nor $V$ strictly dominates the other, because their risks are equal at both parameter values. Under strict-dominance deletion, $W$ is removed and both $U$ and $V$ remain.

If the procedure additionally allows deletion of a rule with an exactly risk-equivalent alternative, it may delete $V$ in favor of $U$, leaving $\{U\}$. Or it may delete $U$ in favor of $V$, leaving $\{V\}$. These are different rule sets, but they have the same available risk function and both replace $W$ without increasing risk. The different labels reflect a redundancy convention, not an order effect for strict dominance.

Common Mistake: Changing the Comparison While Pruning

A common error is to compare risks only at parameter values currently under attention, then treat the resulting deletion as valid over the full problem. Pointwise dominance requires the no-greater-risk inequality at every parameter value. If the comparison set changes, so does the relation being used, and the order-invariance theorem no longer applies.

Worked Example: A Deletion That Fails at an Unchecked Parameter

Suppose $\Theta=\{\theta_1,\theta_2\}$, with risk vectors $J=(0,3)$ and $K=(1,1)$. At $\theta_1$, $J$ has lower risk than $K$, since $0<1$. But at $\theta_2$, $J$ has higher risk, since $3>1$. Therefore, neither rule strictly dominates the other over $\Theta$.

Deleting $K$ because $J$ is better at $\theta_1$ would lose a rule with lower risk at $\theta_2$; deleting $J$ because $K$ is better at $\theta_2$ would lose a rule with lower risk at $\theta_1$. The correct comparison keeps both. The deletion-order result applies only when every step uses the same full-parameter-space dominance relation.

Check Your Understanding

Use full pointwise risk comparisons unless a question explicitly says otherwise.

Why can different valid deletion orders produce different intermediate classes but the same terminal class?
State the transitivity property of strict pointwise risk dominance and explain where strictness is preserved.
If two rules have identical risk functions, can either strictly dominate the other? What additional convention could allow one to be removed?
What risk-replacement property does the terminal class retain for rules deleted earlier?
For risk vectors $M=(1,4)$ and $N=(2,3)$, determine whether either rule strictly dominates the other, and justify the conclusion coordinate by coordinate.