Dependent-input Shapley effects are nonnegative and sum to one

Fix $S\subseteq T\subseteq [d]$, and write $m_S=\mathbb{E}[Y\mid {\mathcal{G}}_S]$ and $m_T=\mathbb{E}[Y\mid {\mathcal{G}}_T]$. The subspaces of ${\mathcal{G}}_S$- and ${\mathcal{G}}_T$-measurable $L^2$ functions are nested. For every $h$ in the smaller subspace, $⟨m_T-Y,h⟩=0$ because $h$ also belongs to the larger subspace. Thus $m_T$ and $Y$ have the same orthogonal projection onto the smaller subspace, namely $m_S$, so $m_T-m_S\perp m_S-\mathbb{E}Y$. Pythagoras gives $v(T)-v(S)=\mathrm{\parallel }{m}_T-m_S{\mathrm{\parallel }}_2^2\ge 0$.

For any permutation $\pi$, sum the successive increments $v(P_i^{\pi }\cup \{i\})-v(P_i^{\pi })$ in the order of that permutation. Every intermediate coalition value appears once positively and once negatively, leaving $v([d])-v(\mathrm{\varnothing })$. The projection in [F1] fixes $Y$, so $v([d])=V$; the empty-set projection is constant $\mathbb{E}Y$, so $v(\mathrm{\varnothing })=0$. Step 1.1 gives monotonicity, so these endpoint values imply $0\le v(S)\le V$ for every coalition. Thus the increments sum to $V$.

Each increment in step 2.1 is nonnegative by step 1.1. Average over the finite set of $d!$ permutations and divide by $V>0$. The resulting effects are nonnegative and their sum is $V\mathrm{/}V=1$.

In the procedure [F3], before each entry $i$ of a permutation $\pi$, the current set $S$ is exactly $P_i^{\pi }$: it starts empty and each preceding entry is added once. Thus the increment added to $A_i$ is $v(P_i^{\pi }\cup \{i\})-v(P_i^{\pi })$. There are $d!$ permutations with $d$ entries each, so the loops perform finitely many iterations and at most $2dd!$ exact coalition-value calls; every queried value is available by the stated oracle input. Summing the increments gives $A_i={\sum }_{\pi \in {\mathfrak{S}}_d}(v(P_i^{\pi }\cup \{i\})-v(P_i^{\pi }))$, and division by $d!V$ returns exactly ${\varphi }_i$ by [F2].