Aliasing on Purpose
8 min read
Over the past few years, much of my research has focused on estimating Shapley values. I would have thought that working on one problem would limit what areas I get to explore. Instead, as I look for hammers to hit my nail, I have explored many (often tangentially) related areas. Today, we’ll see how ideas from experimental design can be used to more accurately estimate Shapley values.
Zheng Zhou, Robert Mee, Herbert Hamers, and Wei Zheng had a brilliant insight: something that is a disadvantage when designing experiments can be a strength when estimating Shapley values [ZMHZ, JASA ’25]. In particular, an experiment can leave individual effects tangled together and still tell us exactly the sum we need.
Shapley Values as an Expectation
Let \(d\) be the number of players and define \(f(S)\) be the value produced by a coalition \(S \subseteq [d]\). The Shapley value of player \(i\) is
\[ \phi_i(f)=\mathbb E[\Delta_i f(S)], \qquad \Delta_i f(S)=f(S\cup\{i\})-f(S). \]
Here \(S\) is the set of players who appear before \(i\) in a uniformly random ordering. The marginal contribution \(\Delta_i f\) is a discrete derivative: how much does the function change when we add player \(i\)? So the Shapley value is the expectation of a derivative.
For now, let’s abstract away the derivative. Let \(g:2^{[n]} \to \mathbb{R}\) be any real-valued function defined on \(n\) players, e.g., \(n=d-1\). Here \(P\) is the Shapley distribution on these \(n\) players:
\[ P(S)=\frac1{(n+1)\binom n{|S|}}. \]
Our target is \(\mu=\mathbb E_P[g]\). A fractional factorial design (FFD) will let us recover something close to this expectation from a carefully chosen set of \(O(n)\) coalitions under a low-order assumption on \(g\). For one Shapley value with \(g=\Delta_i f\), this means \(O(d)\) evaluations of the game \(f\). In contrast, evaluating the expectation directly would require evaluating \(g\) on all \(2^n\) coalitions.
Fourier Representation
To describe interactions among players, encode a coalition by signs: \(x_j=+1\) if \(j\in S\) and \(x_j=-1\) otherwise. We now represent each coalition \(S\) by its sign vector \(x\), and write \(g(x)\) for \(g(S)\). The subset \(T\) indexes an interaction among coordinates. Define
\[ \chi_T(x)=\prod_{j\in T}x_j, \qquad \chi_\emptyset(x)=1. \]
Every function on these sign vectors has a unique Boolean Fourier expansion:
\[ g(x)=\sum_{T\subseteq[n]}G(T)\chi_T(x). \]
The coefficient \(G(T)\) describes an interaction among the players in \(T\). The constant coefficient is \(G(\emptyset)\), and an interaction has order \(|T|\).
Claim: For every \(T\subseteq[n]\), the Fourier coefficient is
\[ G(T) =\frac1{2^n}\sum_{x\in\{-1,+1\}^n}g(x)\chi_T(x). \]
Proof
Let \(U\) be uniform on all \(2^n\) sign vectors. The signs are independent with mean zero, so
\[ \mathbb E_U[\chi_T\chi_R] =\begin{cases}1,&T=R,\\0,&T\ne R.\end{cases} \]
When \(T=R\), every term \(x_j \in T\) appears twice and the product is one. When \(T\ne R\), some term $x_j T $ appears exactly once, making the expectation zero. Multiplying the Fourier expansion by \(\chi_T\) and averaging therefore gives
\[\begin{align*} \frac1{2^n}\sum_x g(x)\chi_T(x) =\sum_{R\subseteq[n]}G(R)\mathbb E_U[\chi_R\chi_T] =G(T). \end{align*}\]
These coefficients use the uniform distribution on sign vectors. Next, we’ll use them to compute an expectation under the Shapley distribution.
Fourier Representation of the Shapley Value
Claim: For every \(T\subseteq[n]\), the Shapley distribution satisfies
\[ { \mathbb E_P[\chi_T] =\begin{cases} \dfrac1{|T|+1},&|T|\text{ even},\\[4pt] 0,&|T|\text{ odd}. \end{cases} } \]
Proof
Give the \(n\) players and a marker independent uniform arrival times in \([0,1]\), and take the coalition arriving before the marker. Their ordering is uniform, so this produces \(P\). Conditional on the marker arriving at time \(t\), each player independently belongs to the coalition with probability \(t\). Each sign then has mean \(1\cdot t+(-1)\cdot(1-t)=2t-1\), giving
\[ \mathbb E_P[\chi_T] =\int_0^1(2t-1)^{|T|}\,dt =\frac12\int_{-1}^1u^{|T|}\,du. \]
Odd powers integrate to zero. For even powers, the final expression is \(1/(|T|+1)\).
By linearity,
\[ { \mathbb E_P[g] =\sum_{\substack{T\subseteq[n]\\|T|\text{ even}}} \frac{G(T)}{|T|+1}. } \]
Notice that the weight of a coefficient depends only on its order.
Computing each coefficient from its Fourier formula still requires evaluating \(g\) everywhere. But we do not need the coefficients individually, only their weighted sum. We will build an estimate that gives the constant and pair coefficients their correct weights and keeps track of how higher-order terms enter.
Aliasing
Let \(H\subseteq\{-1,+1\}^n\) be a collection of coalitions, written as sign vectors. We will evaluate \(g(x)\) for every \(x\in H\). If two interactions \(\chi_T\) and \(\chi_R\) agree everywhere on \(H\), we say they are aliased on \(H\), i.e., their coefficients cannot be distinguished from these observations.
For a concrete example, take \(n=5\) and choose
\[ H=\{x\in\{-1,+1\}^5:x_1x_2x_3x_4=1\}. \]
There are \(16\) such coalitions, half of the full \(32\). To generate them, let \(x_1,x_2,x_3,x_5\) take all possible signs and set \(x_4=x_1x_2x_3\). On \(H\), we have
\[ x_1x_2=x_3x_4,\qquad x_1x_3=x_2x_4,\qquad x_1x_4=x_2x_3. \]
Aliasing on H
x₁x₂
x₃x₄
We choose \(H\) to be nonempty and closed under coordinatewise multiplication: if \(x,y\in H\), then \(x\odot y\in H\), where \((x\odot y)_j=x_jy_j\). Constraints of the form \(\chi_T(x)=1\) are preserved by this operation. This structure makes any two interactions either aliased or orthogonal on \(H\). The following claim holds in every dimension for any design with the closure property above.
Claim: Let \(H\subseteq\{-1,+1\}^n\) be nonempty and closed under coordinatewise multiplication. For any \(T,R\subseteq[n]\),
\[ \frac1{|H|}\sum_{x\in H}\chi_T(x)\chi_R(x) =\begin{cases} 1,&\chi_T\text{ and }\chi_R\text{ are aliased on }H,\\ 0,&\text{they differ at some point of }H. \end{cases} \]
Proof
The product \(\chi_T\chi_R=\chi_{T\triangle R}\) is the interaction indexed by the symmetric difference of \(T\) and \(R\), since coordinates appearing twice cancel. If the interactions are aliased, then \(\chi_{T\triangle R}(x)=1\) for every \(x\in H\), so its average is one.
Otherwise, choose \(y\in H\) where the interactions differ, so \(\chi_{T\triangle R}(y)=-1\). Closure ensures that \(x\mapsto x\odot y\) stays in \(H\). It is a bijection because applying it twice returns \(x\). Since each interaction is a product of coordinates,
\[ \chi_{T\triangle R}(x\odot y)=\chi_{T\triangle R}(x)\chi_{T\triangle R}(y)=-\chi_{T\triangle R}(x). \]
Reindexing the average by this bijection gives
\[ \frac1{|H|}\sum_{x\in H}\chi_{T\triangle R}(x) =\frac1{|H|}\sum_{x\in H}\chi_{T\triangle R}(x\odot y) =-\frac1{|H|}\sum_{x\in H}\chi_{T\triangle R}(x). \]
The average equals its own negative, so it is zero.
For the rest of the derivation, let \(n\) be arbitrary and choose \(H\) with two further properties: no pair interaction aliases with the constant, and no odd-order interaction aliases with an even-order interaction.
Define the measurements
\[ \widehat G_H(R)=\frac1{|H|}\sum_{x\in H}g(x)\chi_R(x). \]
The hat distinguishes these measurements from the true Fourier coefficients. The same \(|H|\) evaluations of \(g\) give every measurement, with only the signs multiplying them changing. Substitute the full Fourier expansion and apply the aliasing claim:
\[\begin{align*} \widehat G_H(R) &=\sum_{T\subseteq[n]}G(T) \left(\frac1{|H|}\sum_{x\in H}\chi_{T\triangle R}(x)\right)\\ &=\sum_{\substack{T\subseteq[n]\\\chi_T=\chi_R\text{ on }H}}G(T). \end{align*}\]
Each measurement is the sum of all coefficients aliased with its interaction, whatever their order. The ordinary average \(\widehat G_H(\emptyset)\) includes the constant coefficient and any higher-order coefficients aliased with it. A pair measurement includes every pair coefficient in its alias group, along with any higher-order coefficients in that group. Odd-order coefficients enter neither measurement, by our design conditions.
This loss of information is a problem when an experiment aims to estimate individual effects, i.e., the familiar aliasing of experimental design. But every pair coefficient has the same target weight, \(1/3\), so their sum is enough for us. Pairs in the same alias group give the same measurement, which already includes all their coefficients. Choose one pair from each group and define
\[ \widehat\mu =\widehat G_H(\emptyset) +\frac13\sum_{\text{one pair }R\text{ per alias group}}\widehat G_H(R). \]
Any representative of a group gives the same result. Every pair coefficient appears exactly once in this sum. To track the higher-order terms too, write the weight of an interaction in the estimator as
\[ w_H(T)=\begin{cases} 1,&\chi_T=1\text{ on }H,\\ \frac13,&\chi_T=\chi_R\text{ on }H\text{ for some pair }R,\\ 0,&\text{otherwise}. \end{cases} \]
The first two cases are disjoint because no pair aliases with the constant. All odd-order interactions have weight zero. The measurement identity now gives the estimate for any \(g\):
\[ \widehat\mu =G(\emptyset)+\frac13\sum_{j<k}G(\{j,k\}) +\sum_{\substack{T\subseteq[n]\\|T|\ge4,\ |T|\text{ even}}}w_H(T)G(T). \]
For any \(n\ge1\), the construction below satisfies all our design conditions and uses exactly
\[ |H|=2^{\lceil\log_2n\rceil+1}, \qquad 2n\le |H|<4n. \]
Thus \(H\) contains at least \(2n\) and fewer than \(4n\) coalitions. Each coalition requires one evaluation of \(g\), and all the signed averages reuse those same values.
A design for any number of players
For \(n\ge2\), set \(r=\lceil\log_2n\rceil\). Choose \(n\) distinct subsets \(A_1,\ldots,A_n\) of \(\{1,\ldots,r\}\), including the empty set and every singleton. There is room because \(r+1\le n\le2^r\). Use free signs \(z_0,z_1,\ldots,z_r\) and define
\[ x_j=z_0\prod_{k\in A_j}z_k, \qquad j=1,\ldots,n. \]
Let \(H\) contain the resulting \(x\) for every setting of the free signs. Multiplying two free-sign settings coordinatewise multiplies their resulting \(x\) vectors coordinatewise, so \(H\) is closed under this operation and the general claim applies. The coordinate corresponding to the empty set reveals \(z_0\), and each singleton coordinate then reveals one of the other \(z_k\). Thus the settings give distinct points, and \(|H|=2^{r+1}<4n\).
Every odd-order interaction contains \(z_0\), while every even-order interaction cancels it. The two kinds cannot alias. Also,
\[ x_jx_k=\prod_{\ell\in A_j\mathbin{\triangle}A_k}z_\ell \]
is nonconstant for \(j\ne k\), because the subsets are distinct. So no pair aliases with the constant.
Two pairs alias exactly when their symmetric differences \(A_j\triangle A_k\) agree. Group the pairs by these symmetric differences and choose one representative per group. For \(n=1\), use both sign choices. The estimator is their ordinary average because there are no pairs.
Low-Order Structure
The estimator gives the constant and pair coefficients exactly the weights they have in \(\mu=\mathbb E_P[g]\). Odd-order coefficients contribute to neither quantity. Only higher even-order coefficients can cause error:
\[ \widehat\mu-\mu =\sum_{\substack{T\subseteq[n]\\|T|\ge4,\ |T|\text{ even}}} \left(w_H(T)-\frac1{|T|+1}\right)G(T). \]
Claim: The estimate is exact if \(G(T)=0\) for all even \(|T|\ge4\), in particular when \(g\) has degree at most three. For any \(g\),
\[ |\widehat\mu-\mu| \le\sum_{\substack{T\subseteq[n]\\|T|\ge4,\ |T|\text{ even}}}|G(T)|. \]
Thus the total magnitude of the higher even-order coefficients controls the error. There is no restriction on odd-order coefficients, even those of high order.
An Algorithm for Shapley Values
Now consider a game with \(d\) players. To estimate the Shapley value of one player \(i\), set \(n=d-1\) and label the other players by \([n]\). Apply the construction in dimension \(n\) to the contribution of adding \(i\):
- Choose the coalitions. For \(d\ge2\), build \(H\) using the construction above: fewer than \(4n=4(d-1)\) coalitions of the other players.
- Measure the contribution. For each sign vector \(x\in H\), let \(S\) be its coalition. Evaluate \(f(S)\) and \(f(S\cup\{i\})\), then store the value with \(i\) minus the value without \(i\). These stored differences are the values of \(g=\Delta_i f\).
- Average the differences. Take their ordinary average and the signed average for one pair \(\{j,k\}\) from each alias group.
- Combine. Return the ordinary average plus one third of the sum of the signed averages, counting each alias group once.
For one Shapley value, this uses \(|H|\) differences, each requiring two game values:
\[ 2|H|=2^{\lceil\log_2n\rceil+2}<8n=8(d-1). \]
That is \(O(d)\) evaluations of \(f\) for one player. Repeating for all \(d\) players costs \(O(d(d-1))=O(d^2)\) game evaluations in total.
The estimator is exact whenever \(f\) has Fourier degree at most four. To see why, notice that taking the discrete derivative \(\Delta_i f\) eliminates interactions not involving \(i\) and reduces the order of every remaining interaction by one. Thus \(g=\Delta_i f\) has degree at most three, for which the estimator is exact. For higher-degree games, the error is bounded as above.