Parametrically Retargetable Decision-Makers Tend To Seek Power — part 7/13

Cleaned-text code points [92906, 108618). Bibliography omitted here; source.md includes it.

Item 4 . Holds because f f is increasing under joint permutation on all of its inputs X , θ ′ X,\theta^{{}^{\prime}} , and definition B.8 shows that ϕ i ⋅ B j ⋆ = B j ⋆ \phi_{i}\cdot B^{\star}_{j}=B^{\star}_{j} when i ≠ j i\neq j . Combining these two steps of reasoning, for all θ ′ ∈ Θ \theta^{\prime}\in\Theta , it is true that f ⁡ ( B j ⋆ ∣ θ ′ ) ≤ f ⁡ ( ϕ i ⋅ B j ⋆ ∣ ϕ i ⋅ θ ′ ) ≤ f ⁡ ( B j ⋆ ∣ ϕ i ⋅ θ ′ ) f\left(B_{j}^{\star}\mid\theta^{\prime}\right)\leq f\left(\phi_{i}\cdot B_{j}^{\star}\mid\phi_{i}\cdot\theta^{\prime}\right)\leq f\left(B_{j}^{\star}\mid\phi_{i}\cdot\theta^{\prime}\right) .

Then apply Lemma B.7 . ∎

###### Lemma B.10 (Hiding an argument which is invariant under certain permutations) .

Let 𝐄 1 \mathbf{E}_{1} , 𝐄 2 \mathbf{E}_{2} , Θ \Theta be subsets of sets which are acted on by S d S_{d} . Let A ∈ 𝐄 1 A\in\mathbf{E}_{1} , C ∈ 𝐄 2 C\in\mathbf{E}_{2} . Suppose there exist ϕ 1 , … , ϕ n ∈ S d \phi_{1},\ldots,\phi_{n}\in S_{d} such that ϕ i ⋅ C = C \phi_{i}\cdot C=C . Suppose h : 𝐄 1 × 𝐄 2 × Θ → ℝ h\mathrel{\mathop{\ordinarycolon}}\mathbf{E}_{1}\times\mathbf{E}_{2}\times\Theta\to\mathbb{R} satisfies ∀ i : h ⁡ ( A , C ∣ θ ) ≤ h ⁡ ( ϕ i ⋅ A , ϕ i ⋅ C ∣ ϕ i ⋅ θ ) \forall i\mathrel{\mathop{\ordinarycolon}}h(A,C\mid\theta)\leq h(\phi_{i}\cdot A,\phi_{i}\cdot C\mid\phi_{i}\cdot\theta) . For any X ∈ 𝐄 1 X\in\mathbf{E}_{1} , let f ⁡ ( X ∣ θ ) ≔ h ⁡ ( X , C ∣ θ ) f(X\mid\theta)\coloneqq h(X,C\mid\theta) . Then f ⁡ ( A ∣ θ ) f(A\mid\theta) is increasing under joint permutation by ϕ i \phi_{i} .

Furthermore, if h h is invariant under joint permutation by ϕ i \phi_{i} , then so is f f .

###### Proof.

f ⁡ ( X ∣ θ ) \displaystyle f(X\mid\theta) ≔ h ⁡ ( X , C ∣ θ ) \displaystyle\coloneqq h(X,C\mid\theta) (40) ≤ h ⁡ ( ϕ i ⋅ X , ϕ i ⋅ C ∣ ϕ i ⋅ θ ) \displaystyle\leq h(\phi_{i}\cdot X,\phi_{i}\cdot C\mid\phi_{i}\cdot\theta) (41) = h ⁡ ( ϕ i ⋅ X , C ∣ ϕ i ⋅ θ ) \displaystyle=h(\phi_{i}\cdot X,C\mid\phi_{i}\cdot\theta) (42) ≕ f ⁡ ( ϕ i ⋅ X ∣ ϕ i ⋅ θ ) . \displaystyle\eqqcolon f(\phi_{i}\cdot X\mid\phi_{i}\cdot\theta). (43) Equation 41 holds by assumption. Equation 42 follows because we assumed ϕ i ⋅ C = C \phi_{i}\cdot C=C . Then f f is increasing under joint permutation by the ϕ i \phi_{i} .

If h h is invariant , then eq. 41 is an equality, and so ∀ i : f ⁡ ( X ∣ θ ) = f ⁡ ( ϕ i ⋅ X ∣ ϕ i ⋅ θ ) \forall i\mathrel{\mathop{\ordinarycolon}}f(X\mid\theta)=f(\phi_{i}\cdot X\mid\phi_{i}\cdot\theta) . ∎

#### B.2.1 EU-determined functions

Lemma B.11 and Lemma B.5 together extend Turner et al. [2021] ’s lemma E.17 beyond functions of max 𝐱 ∈ X i \max_{\mathbf{x}\in X_{i}} , to any functions of cardinalities and of expected utilities of set elements. See A.12

###### Lemma B.11 (EU-determined functions are invariant under joint permutation) .

Suppose that f : ∏ i = 1 m 𝒫 ⁡ ( ℝ d ) × ℝ d → ℝ f\mathrel{\mathop{\ordinarycolon}}\prod_{i=1}^{m}\mathcal{P}\left(\mathbb{R}^{d}\right)\times\mathbb{R}^{d}\to\mathbb{R} is an EU-determined function. Then for any ϕ ∈ S d \phi\in S_{d} and X 1 , … , X m , 𝐮 X_{1},\ldots,X_{m},\mathbf{u} , we have f ⁡ ( X 1 , … , X m ∣ 𝐮 ) = f ⁡ ( ϕ ⋅ X 1 , … , ϕ ⋅ X m ∣ ϕ ⋅ 𝐮 ) f(X_{1},\ldots,X_{m}\mid\mathbf{u})=f(\phi\cdot X_{1},\ldots,\phi\cdot X_{m}\mid\phi\cdot\mathbf{u}) .

###### Proof.

f ⁡ ( X 1 , … , X m ∣ 𝐮 ) \displaystyle f(X_{1},\ldots,X_{m}\mid\mathbf{u}) (44) = g | X 1 | , … , | X m | ​ ( [ 𝐱 1 ⊤ ​ 𝐮 ] 𝐱 1 ∈ X 1 , … , [ 𝐱 m ⊤ ​ 𝐮 ] 𝐱 m ∈ X m ) \displaystyle=g^{|X_{1}|,\ldots,|X_{m}|}\left(\left[\mathbf{x}_{1}^{\top}\mathbf{u}\right]_{\mathbf{x}_{1}\in X_{1}},\ldots,\left[\mathbf{x}_{m}^{\top}\mathbf{u}\right]_{\mathbf{x}_{m}\in X_{m}}\right) (45) = g | ϕ ⋅ X 1 | , … , | ϕ ⋅ X m | ​ ( [ 𝐱 1 ⊤ ​ 𝐮 ] 𝐱 1 ∈ X 1 , … , [ 𝐱 m ⊤ ​ 𝐮 ] 𝐱 m ∈ X m ) \displaystyle=g^{\left|\phi\cdot X_{1}\right|,\ldots,\left|\phi\cdot X_{m}\right|}\left(\left[\mathbf{x}_{1}^{\top}\mathbf{u}\right]_{\mathbf{x}_{1}\in X_{1}},\ldots,\left[\mathbf{x}_{m}^{\top}\mathbf{u}\right]_{\mathbf{x}_{m}\in X_{m}}\right) (46) = g | ϕ ⋅ X 1 | , … , | ϕ ⋅ X m | ​ ( [ ( 𝐏 ϕ ​ 𝐱 1 ) ⊤ ​ ( 𝐏 ϕ ​ 𝐮 ) ] 𝐱 1 ∈ X 1 , … , [ ( 𝐏 ϕ ​ 𝐱 m ) ⊤ ​ ( 𝐏 ϕ ​ 𝐮 ) ] 𝐱 m ∈ X m ) \displaystyle=g^{\left|\phi\cdot X_{1}\right|,\ldots,\left|\phi\cdot X_{m}\right|}\left(\left[(\mathbf{P}_{\phi}\mathbf{x}_{1})^{\top}(\mathbf{P}_{\phi}\mathbf{u})\right]_{\mathbf{x}_{1}\in X_{1}},\ldots,\left[(\mathbf{P}_{\phi}\mathbf{x}_{m})^{\top}(\mathbf{P}_{\phi}\mathbf{u})\right]_{\mathbf{x}_{m}\in X_{m}}\right) (47) = f ⁡ ( ϕ ⋅ X 1 , … , ϕ ⋅ X m ∣ ϕ ⋅ 𝐮 ) . \displaystyle=f(\phi\cdot X_{1},\ldots,\phi\cdot X_{m}\mid\phi\cdot\mathbf{u}). (48) Equation 46 holds because permutations ϕ \phi act injectively on ℝ d \mathbb{R}^{d} . Equation 47 follows because 𝐈 = 𝐏 ϕ − 1 ​ 𝐏 ϕ = 𝐏 ϕ ⊤ ​ 𝐏 ϕ \mathbf{I}=\mathbf{P}_{\phi}^{-1}\mathbf{P}_{\phi}=\mathbf{P}_{\phi}^{\top}\mathbf{P}_{\phi} by the orthogonality of permutation matrices, and 𝐱 ⊤ ​ 𝐏 ϕ ⊤ = ( 𝐏 ϕ ​ 𝐱 ) ⊤ \mathbf{x}^{\top}\mathbf{P}_{\phi}^{\top}=(\mathbf{P}_{\phi}\mathbf{x})^{\top} , so 𝐱 ⊤ ​ 𝐮 = 𝐱 ⊤ ​ 𝐏 ϕ ⊤ ​ 𝐏 ϕ ​ 𝐮 = ( 𝐏 ϕ ​ 𝐱 ) ⊤ ​ ( 𝐏 ϕ ​ 𝐮 ) \mathbf{x}^{\top}\mathbf{u}=\mathbf{x}^{\top}\mathbf{P}_{\phi}^{\top}\mathbf{P}_{\phi}\mathbf{u}=(\mathbf{P}_{\phi}\mathbf{x})^{\top}(\mathbf{P}_{\phi}\mathbf{u}) . ∎

See A.13

###### Proof.

By assumption, there exists a family of functions { g i , | C | } \left\{g^{i,|C|}\right\} such that for all X ⊆ ℝ d X\subseteq\mathbb{R}^{d} , h ⁡ ( X , C ∣ 𝐮 ) = g | X | , | C | ​ ( [ 𝐱 ⊤ ​ 𝐮 ] 𝐱 ∈ X , [ 𝐜 ⊤ ​ 𝐮 ] 𝐜 ∈ C ) h(X,C\mid\mathbf{u})=g^{|X|,|C|}\left(\left[\mathbf{x}^{\top}\mathbf{u}\right]_{\mathbf{x}\in X},\left[\mathbf{c}^{\top}\mathbf{u}\right]_{\mathbf{c}\in C}\right) . Therefore, Lemma B.11 shows that h ⁡ ( A , C ∣ 𝐮 ) h(A,C\mid\mathbf{u}) is invariant under joint permutation by the ϕ i \phi_{i} . Letting Θ ≔ ℝ d \Theta\coloneqq\mathbb{R}^{d} , apply Lemma B.10 to conclude that f ⁡ ( X ∣ 𝐮 ) f(X\mid\mathbf{u}) is invariant under joint permutation by the ϕ i \phi_{i} .

Since f f returns a probability of selecting an element of X X , f f obeys the monotonicity probability axiom: If X ′ ⊆ X X^{\prime}\subseteq X , then f ⁡ ( X ′ ∣ 𝐮 ) ≤ f ⁡ ( X ∣ 𝐮 ) f(X^{\prime}\mid\mathbf{u})\leq f(X\mid\mathbf{u}) . Then f ( B ∣ 𝐮 ) ≥ most : ℝ d n f ( A ∣ 𝐮 ) f(B\mid\mathbf{u})\geq_{\text{{most}}\text{: }\mathbb{R}^{d}}^{n}f(A\mid\mathbf{u}) by Lemma B.9 . ∎

### B.3 Particular results on retargetable functions

###### Definition B.12 (Quantilization, closed form) .

Let the expected utility q q -quantile threshold be M q , P ​ ( C ∣ 𝐮 ) ≔ inf { M ∈ ℝ ∣ ℙ 𝐱 ∼ P ( 𝐱 ⊤ ​ 𝐮 > M ) ≤ q } . M_{q,P}(C\mid\mathbf{u})\coloneqq\inf\left\{M\in\mathbb{R}\mid\Prb_{\mathbf{x}\sim P}\left(\mathbf{x}^{\top}\mathbf{u}>M\right)\leq q\right\}. (49) Let C > M q , P ​ ( C ∣ 𝐮 ) ≔ { 𝐜 ∈ C ∣ 𝐜 ⊤ ​ 𝐮 > M q , P ​ ( C ∣ 𝐮 ) } C_{>M_{q,P}(C\mid\mathbf{u})}\coloneqq\left\{\mathbf{c}\in C\mid\mathbf{c}^{\top}\mathbf{u}>M_{q,P}(C\mid\mathbf{u})\right\} . C = M q , P ​ ( C ∣ 𝐮 ) C_{=M_{q,P}(C\mid\mathbf{u})} is defined similarly. Let 𝟙 L ⁡ ( x ) \mathbbm{1}_{L(x)} be the predicate function returning 1 1 if L ⁡ ( x ) L(x) is true and 0 0 otherwise. Then for X ⊆ C X\subseteq C , Q q , P ​ ( X ∣ C , 𝐮 ) ≔ ∑ 𝐱 ∈ X P ⁡ ( 𝐱 ) q ​ ( 𝟙 𝐱 ∈ C > M q , P ​ ( C ∣ 𝐮 ) + 𝟙 𝐱 ∈ C = M q , P ​ ( C ∣ 𝐮 ) P ⁡ ( C = M q , P ​ ( C ∣ 𝐮 ) ) ​ ( q − P ⁡ ( C > M q , P ​ ( C ∣ 𝐮 ) ) ) ) , \displaystyle Q_{q,P}(X\mid C,\mathbf{u})\coloneqq\sum_{\mathbf{x}\in X}\frac{P(\mathbf{x})}{q}\left(\mathbbm{1}_{\mathbf{x}\in C_{>M_{q,P}(C\mid\mathbf{u})}}+\frac{\mathbbm{1}_{\mathbf{x}\in C_{=M_{q,P}(C\mid\mathbf{u})}}}{P\left(C_{=M_{q,P}(C\mid\mathbf{u})}\right)}\left(q-P\left(C_{>M_{q,P}(C\mid\mathbf{u})}\right)\right)\right), (50) where the summand is defined to be 0 0 if P ⁡ ( 𝐱 ) = 0 P(\mathbf{x})=0 and 𝐱 ∈ C = M q , P ​ ( C ∣ 𝐮 ) \mathbf{x}\in C_{=M_{q,P}(C\mid\mathbf{u})} .

###### Remark .

Unlike Taylor [2016] ’s or Carey [2019] ’s definitions, definition B.12 is written in closed form and requires no arbitrary tie-breaking. Instead, in the case of an expected utility tie on the quantile threshold, eq. 50 allots probability to outcomes proportional to their probability under the base distribution P P .

Thanks to Theorem A.13 , we straightforwardly prove most items of Proposition A.11 by just rewriting each decision-making function as an EU-determined function. Most of the proof’s length comes from showing that the functions are measurable on 𝐮 \mathbf{u} , which means that the results also apply for distributions over utility functions 𝒟 any ∈ 𝔇 any \mathcal{D}_{\text{any}}\in\mathfrak{D}_{\text{any}} .

See A.11

###### Proof.

Item 1 . Consider h ⁡ ( X , C ∣ 𝐮 ) \displaystyle h(X,C\mid\mathbf{u}) ≔ 𝟙 ∃ 𝐱 ∈ X : ∀ 𝐜 ∈ C : 𝐱 ⊤ ​ 𝐮 ≥ 𝐜 ⊤ ​ 𝐮 \displaystyle\coloneqq\mathbbm{1}_{\exists\mathbf{x}\in X\mathrel{\mathop{\ordinarycolon}}\forall\mathbf{c}\in C\mathrel{\mathop{\ordinarycolon}}\mathbf{x}^{\top}\mathbf{u}\geq\mathbf{c}^{\top}\mathbf{u}} (51) = min ⁡ ( 1 , ∑ 𝐱 ∈ X ∏ 𝐜 ∈ C 𝟙 ( 𝐱 − 𝐜 ) ⊤ ​ 𝐮 ≥ 0 ) . \displaystyle=\min\left(1,\sum_{\mathbf{x}\in X}\prod_{\mathbf{c}\in C}\mathbbm{1}_{(\mathbf{x}-\mathbf{c})^{\top}\mathbf{u}\geq 0}\right). (52) Since halfspaces are measurable, each indicator function is measurable on 𝐮 \mathbf{u} . The finite sum of the finite product of measurable functions is also measurable. Since min \min is continuous (and therefore measurable), h ⁡ ( X , C ∣ 𝐮 ) h(X,C\mid\mathbf{u}) is measurable on 𝐮 \mathbf{u} .

Furthermore, h h is an EU-determined function: h ⁡ ( X , C ∣ 𝐮 ) \displaystyle h(X,C\mid\mathbf{u}) = g ⁡ ( [ 𝐱 ⊤ ​ 𝐮 ] 𝐱 ∈ X ⏞ V X , [ 𝐜 ⊤ ​ 𝐮 ] 𝐜 ∈ C ⏞ V C ) \displaystyle=g\left(\overbrace{\left[\mathbf{x}^{\top}\mathbf{u}\right]_{\mathbf{x}\in X}}^{V_{X}},\overbrace{\left[\mathbf{c}^{\top}\mathbf{u}\right]_{\mathbf{c}\in C}}^{V_{C}}\right) (53) ≔ 𝟙 ∃ v x ∈ V X : ∀ v c ∈ V C : v x ≥ v c . \displaystyle\coloneqq\mathbbm{1}_{\exists v_{x}\in V_{X}\mathrel{\mathop{\ordinarycolon}}\forall v_{c}\in V_{C}\mathrel{\mathop{\ordinarycolon}}v_{x}\geq v_{c}}. (54) Then by Lemma B.11 , h h is invariant to joint permutation by the ϕ i \phi_{i} . Since ϕ i ⋅ C = C \phi_{i}\cdot C=C , Lemma B.10 shows that h ′ ​ ( X ∣ 𝐮 ) ≔ h ⁡ ( X , C ∣ 𝐮 ) h^{\prime}(X\mid\mathbf{u})\coloneqq h(X,C\mid\mathbf{u}) is also invariant under joint permutation by the ϕ i \phi_{i} . Since h h is a measurable function of 𝐮 \mathbf{u} , so is h ′ h^{\prime} . Then since h ′ h^{\prime} is bounded, Lemma B.5 shows that f ⁡ ( X ∣ 𝒟 any ) ≔ 𝔼 𝐮 ∼ 𝒟 any [ h ′ ​ ( X ∣ 𝐮 ) ] f(X\mid\mathcal{D}_{\text{any}})\coloneqq\opE_{\mathbf{u}\sim\mathcal{D}_{\text{any}}}\left[h^{\prime}(X\mid\mathbf{u})\right] is invariant under joint permutation by ϕ i \phi_{i} .

Furthermore, if X ′ ⊆ X X^{\prime}\subseteq X , f ⁡ ( X ′ ∣ 𝒟 any ) ≤ f ⁡ ( X ∣ 𝒟 any ) f(X^{\prime}\mid\mathcal{D}_{\text{any}})\leq f(X\mid\mathcal{D}_{\text{any}}) by the monotonicity of probability. Then by Lemma B.9 , f ( B ∣ 𝒟 any ) ≔ IsOptimal ( B ∣ C , 𝒟 any ) ≥ most : 𝔇 any n IsOptimal ( A ∣ C , 𝒟 any ) ≕ f ( A ∣ 𝒟 any ) . f(B\mid\mathcal{D}_{\text{any}})\coloneqq\mathrm{IsOptimal}\left(B\mid C,\mathcal{D}_{\text{any}}\right)\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}^{n}\mathrm{IsOptimal}\left(A\mid C,\mathcal{D}_{\text{any}}\right)\eqqcolon f(A\mid\mathcal{D}_{\text{any}}).

Item 2 . Because X , C X,C are finite sets, the denominator of FracOptimal ⁡ ( X ∣ C , 𝐮 ) \mathrm{FracOptimal}\left(X\mid C,\mathbf{u}\right) is never zero, and so the function is well-defined. FracOptimal ⁡ ( X ∣ C , 𝐮 ) \mathrm{FracOptimal}\left(X\mid C,\mathbf{u}\right) is an EU-determined function: FracOptimal ⁡ ( X ∣ C , 𝐮 ) \displaystyle\mathrm{FracOptimal}\left(X\mid C,\mathbf{u}\right) = g ⁡ ( [ 𝐱 ⊤ ​ 𝐮 ] 𝐱 ∈ X ⏞ V X , [ 𝐜 ⊤ ​ 𝐮 ] 𝐜 ∈ C ⏞ V C ) \displaystyle=g\left(\overbrace{\left[\mathbf{x}^{\top}\mathbf{u}\right]_{\mathbf{x}\in X}}^{V_{X}},\overbrace{\left[\mathbf{c}^{\top}\mathbf{u}\right]_{\mathbf{c}\in C}}^{V_{C}}\right) (55) ≔ | [ v ∈ V X ∣ v = max v ′ ∈ V C ⁡ v ′ ] | | [ arg ​ max v ′ ∈ V C ⁡ v ′ ] | , \displaystyle\coloneqq\frac{\left|\left[v\in V_{X}\mid v=\max_{v^{\prime}\in V_{C}}v^{\prime}\right]\right|}{\left|\left[\argmax_{v^{\prime}\in V_{C}}v^{\prime}\right]\right|}, (56) with the [ ⋅ ] \left[\cdot\right] denoting a multiset which allows and counts duplicates. Then by Lemma B.11 , FracOptimal ⁡ ( X ∣ C , 𝐮 ) \mathrm{FracOptimal}\left(X\mid C,\mathbf{u}\right) is invariant to joint permutation by the ϕ i \phi_{i} .

We now show that FracOptimal ⁡ ( X ∣ C , 𝐮 ) \mathrm{FracOptimal}\left(X\mid C,\mathbf{u}\right) is a measurable function of 𝐮 \mathbf{u} . FracOptimal ⁡ ( X ∣ C , 𝐮 ) \displaystyle\mathrm{FracOptimal}\left(X\mid C,\mathbf{u}\right) ≔ | { arg ​ max 𝐜 ′ ∈ C ⁡ 𝐜 ′ ⁣ ⊤ ​ 𝐮 } ∩ X | | { arg ​ max 𝐜 ′ ∈ C ⁡ 𝐜 ′ ⁣ ⊤ ​ 𝐮 } | \displaystyle\coloneqq\frac{\left|\left\{\argmax_{\mathbf{c}^{\prime}\in C}\mathbf{c}^{\prime\top}\mathbf{u}\right\}\cap X\right|}{\left|\left\{\argmax_{\mathbf{c}^{\prime}\in C}\mathbf{c}^{\prime\top}\mathbf{u}\right\}\right|} (57) = ∑ 𝐱 ∈ X 𝟙 𝐱 ∈ arg ​ max 𝐜 ′ ∈ C ⁡ 𝐜 ′ ⁣ ⊤ ​ 𝐮 ∑ 𝐜 ∈ C 𝟙 𝐜 ∈ arg ​ max 𝐜 ′ ∈ C ⁡ 𝐜 ′ ⁣ ⊤ ​ 𝐮 \displaystyle=\frac{\sum_{\mathbf{x}\in X}\mathbbm{1}_{\mathbf{x}\in\argmax_{\mathbf{c}^{\prime}\in C}\mathbf{c}^{\prime\top}\mathbf{u}}}{\sum_{\mathbf{c}\in C}\mathbbm{1}_{\mathbf{c}\in\argmax_{\mathbf{c}^{\prime}\in C}\mathbf{c}^{\prime\top}\mathbf{u}}} (58) = ∑ 𝐱 ∈ X ∏ 𝐜 ′ ∈ C 𝟙 ( 𝐱 − 𝐜 ′ ) ⊤ ​ 𝐮 ≥ 0 ∑ 𝐜 ∈ C ∏ 𝐜 ′ ∈ C 𝟙 ( 𝐜 − 𝐜 ′ ) ⊤ ​ 𝐮 ≥ 0 . \displaystyle=\frac{\sum_{\mathbf{x}\in X}\prod_{\mathbf{c}^{\prime}\in C}\mathbbm{1}_{\left(\mathbf{x}-\mathbf{c}^{\prime}\right)^{\top}\mathbf{u}\geq 0}}{\sum_{\mathbf{c}\in C}\prod_{\mathbf{c}^{\prime}\in C}\mathbbm{1}_{\left(\mathbf{c}-\mathbf{c}^{\prime}\right)^{\top}\mathbf{u}\geq 0}}. (59) Equation 59 holds because 𝐱 \mathbf{x} belongs to the arg ​ max \argmax iff ∀ 𝐜 ∈ C : 𝐱 ⊤ ​ 𝐮 ≥ 𝐜 ⊤ ​ 𝐮 \forall\mathbf{c}\in C\mathrel{\mathop{\ordinarycolon}}\mathbf{x}^{\top}\mathbf{u}\geq\mathbf{c}^{\top}\mathbf{u} . Furthermore, this condition is met iff 𝐮 \mathbf{u} belongs to the intersection of finitely many closed halfspaces; therefore, { 𝐮 ∈ ℝ d ∣ ∏ 𝐜 ∈ C 𝟙 ( 𝐱 − 𝐜 ) ⊤ ​ 𝐮 ≥ 0 = 1 } \left\{\mathbf{u}\in\mathbb{R}^{d}\mid\prod_{\mathbf{c}\in C}\mathbbm{1}_{\left(\mathbf{x}-\mathbf{c}\right)^{\top}\mathbf{u}\geq 0}=1\right\} is measurable. Then the sums in both the numerator and denominator are both measurable functions of 𝐮 \mathbf{u} , and the denominator cannot vanish. Therefore, FracOptimal ⁡ ( X ∣ C , 𝐮 ) \mathrm{FracOptimal}\left(X\mid C,\mathbf{u}\right) is a measurable function of 𝐮 \mathbf{u} .

Let g ⁡ ( X ∣ 𝐮 ) ≔ FracOptimal ⁡ ( X ∣ C , 𝐮 ) g(X\mid\mathbf{u})\coloneqq\mathrm{FracOptimal}\left(X\mid C,\mathbf{u}\right) . Since ϕ i ⋅ C = C \phi_{i}\cdot C=C , Lemma B.10 shows that g ⁡ ( X ∣ 𝐮 ) g(X\mid\mathbf{u}) is also invariant to joint permutation by ϕ i \phi_{i} . Since g g is measurable and bounded [ 0 , 1 ] [0,1] , apply Lemma B.5 to conclude that f ⁡ ( X ∣ 𝒟 any ) ≔ 𝔼 𝐮 ∼ 𝒟 any [ g ⁡ ( X ∣ C , 𝐮 ) ] f(X\mid\mathcal{D}_{\text{any}})\coloneqq\opE_{\mathbf{u}\sim\mathcal{D}_{\text{any}}}\left[g(X\mid C,\mathbf{u})\right] is also invariant to joint permutation by ϕ i \phi_{i} .

Furthermore, if X ′ ⊆ X ⊆ C X^{\prime}\subseteq X\subseteq C , then f ⁡ ( X ′ ∣ 𝒟 any ) ≤ f ⁡ ( X ∣ 𝒟 any ) f(X^{\prime}\mid\mathcal{D}_{\text{any}})\leq f(X\mid\mathcal{D}_{\text{any}}) . So apply Lemma B.9 to conclude that FracOptimal ( B ∣ C , 𝒟 any ) ≕ f ( B ∣ 𝒟 any ) ≥ most : 𝔇 any n f ( A ∣ 𝒟 any ) ≔ FracOptimal ( A ∣ C , 𝒟 any ) \mathrm{FracOptimal}\left(B\mid C,\mathcal{D}_{\text{any}}\right)\eqqcolon f(B\mid\mathcal{D}_{\text{any}})\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}^{n}f(A\mid\mathcal{D}_{\text{any}})\coloneqq\mathrm{FracOptimal}\left(A\mid C,\mathcal{D}_{\text{any}}\right) .