Aliasing on Purpose
9 min read
Consider a set function \(g:2^{[d]}\to\mathbb{R}\) defined on \(d\) elements \([d]=\{1,\ldots,d\}\). We are interested in the expectation \(\mathbb{E}[g(S)]\), where \(S\) is drawn uniformly by size. Computing the expectation directly would require all \(2^d\) values of \(g\).
Instead, an experiment using only \(O(d)\) values of \(g\) can recover the low-order contribution to this expectation [ZMHZ, JASA ’25]. The approximation can be poor when higher-order interactions dominate and, amazingly, is exact when those interactions are zero.
From Coalitions to Interactions
Encode a coalition by one sign per element:
\[ x_j(S) = \begin{cases} +1, & j \in S, \\ -1, & j \notin S. \end{cases} \]
We write \(g(x)\) for the value of \(g\) at the coalition represented by a sign vector \(x\). For each \(T \subseteq [d]\), write \(\chi_T(S)=\prod_{j\in T}x_j(S)\) for the product of the signs indexed by \(T\), with \(\chi_\emptyset(S)=1\).
The corresponding Fourier coefficient is the signed average of \(g\) over the whole cube:
\[ \widehat g(T) = \frac{1}{2^d} \sum_{S\subseteq[d]}g(S)\chi_T(S). \]
The coefficient \(\widehat g(\emptyset)\) is the uniform average of \(g\). A coefficient with \(|T|=1\) is a main effect, and one with \(|T|\geq2\) is an interaction among the elements of \(T\). The degree of an effect is the number of elements involved.
Lemma (Fourier reconstruction): These coefficients reconstruct every value of \(g\) exactly:
\[ g(S) = \sum_{T\subseteq[d]}\widehat g(T)\chi_T(S). \]
Proof
Fix the coalition \(S\) whose value we want to reconstruct. Substitute the definition of every coefficient and interchange the two finite sums:
\[\begin{align} \sum_{T\subseteq[d]}\widehat g(T)\chi_T(S) &= \sum_{T\subseteq[d]} \left( \frac{1}{2^d}\sum_{A\subseteq[d]}g(A)\chi_T(A) \right) \chi_T(S) \\ &= \frac{1}{2^d} \sum_{A\subseteq[d]}g(A) \sum_{T\subseteq[d]}\chi_T(A)\chi_T(S). \end{align}\]
The inner sum has one term for each choice of which coordinates to multiply. Expanding a product of \(d\) two-term factors gives exactly that sum:
\[ \sum_{T\subseteq[d]}\chi_T(A)\chi_T(S) = \prod_{j=1}^d\bigl(1+x_j(A)x_j(S)\bigr). \]
If \(A=S\), every factor is \(2\), so the product is \(2^d\). If \(A\neq S\), some coordinate has opposite signs, so its factor is \(1-1=0\) and the whole product vanishes. Only the term \(A=S\) survives in the outer sum:
\[\begin{align} \sum_{T\subseteq[d]}\widehat g(T)\chi_T(S) &= \frac{1}{2^d}g(S)2^d \\ &=g(S). \end{align}\]
This calculation reconstructs the value at the chosen coalition \(S\), so it holds throughout the cube.
The construction below captures all effects through degree three; exact recovery follows in the special case:
\[ \widehat g(T)=0 \qquad\text{whenever }|T|>3. \]
For general \(g\), we use the same design to estimate the mean, with error determined by the higher-order coefficients. Without any restriction on those coefficients, exact recovery from a strict fraction is impossible: changing \(g\) at an unobserved coalition changes its mean without changing the observations. The aim is to capture the low-order contribution efficiently and understand what the remaining interactions do to the estimate.
What the Mean Sees
Averaging the expansion term by term requires the mean of each parity.
Lemma (Shapley parity moments): Under the Shapley distribution, the mean of a parity depends only on the number of signs being multiplied:
\[ \mathbb{E}[\chi_T(S)] = \begin{cases} \dfrac{1}{|T|+1}, & |T|\text{ even}, \\[5pt] 0, & |T|\text{ odd}. \end{cases} \]
Proof
There is a useful second way to draw the same random coalition. First draw \(p\) uniformly from \([0,1]\); conditional on \(p\), include each element independently with probability \(p\). For any fixed coalition \(A\), this procedure gives:
\[\begin{align} \Pr(S=A) &=\int_0^1p^{|A|}(1-p)^{d-|A|}\,dp \\ &=\frac{|A|!\,(d-|A|)!}{(d+1)!} \\ &=\frac{1}{d+1}\binom{d}{|A|}^{-1}. \end{align}\]
The second line is the beta integral, and the third uses the factorial formula for the binomial coefficient. For a fixed size, summing over its \(\binom{d}{|A|}\) coalitions gives probability \(1/(d+1)\), and all coalitions of that size are equally likely. This is exactly the Shapley distribution.
Conditional on \(p\), the signs are independent and each has mean \(2p-1\). Independence lets us multiply those means:
\[\begin{align} \mathbb{E}[\chi_T(S)\mid p] &= \mathbb{E}\left[\prod_{j\in T}x_j(S)\mathrel{\Big|}p\right] \\ &= \prod_{j\in T}\mathbb{E}[x_j(S)\mid p] \\ &=(2p-1)^{|T|}. \end{align}\]
The second line uses conditional independence, and the third uses the same mean for each of the \(|T|\) signs. Average over \(p\) and substitute \(u=2p-1\):
\[\begin{align} \mathbb{E}[\chi_T(S)] &=\int_0^1(2p-1)^{|T|}\,dp \\ &=\frac12\int_{-1}^1u^{|T|}\,du \\ &= \begin{cases} \dfrac12\left[\dfrac{u^{|T|+1}}{|T|+1}\right]_{-1}^{1} =\dfrac{1}{|T|+1}, & |T|\text{ even}, \\[8pt] 0, & |T|\text{ odd}. \end{cases} \end{align}\]
For even \(|T|\), the antiderivative takes opposite values at \(1\) and \(-1\) and their difference is \(2/(|T|+1)\). For odd \(|T|\), the integrand is odd, so its integral over the symmetric interval \([-1,1]\) is zero.
We can now average the Fourier expansion:
\[\begin{align} \mathbb{E}[g(S)] &= \mathbb{E}\left[ \sum_{T\subseteq[d]}\widehat g(T)\chi_T(S) \right] \\ &= \sum_{T\subseteq[d]}\widehat g(T)\mathbb{E}[\chi_T(S)] \\ &= \sum_{\substack{T\subseteq[d]:\\|T|\text{ even}}} \frac{\widehat g(T)}{|T|+1} \\ &= \widehat g(\emptyset) +\frac13\sum_{|T|=2}\widehat g(T) +\frac15\sum_{|T|=4}\widehat g(T) +\cdots. \end{align}\]
The first line inserts the Fourier expansion, the second uses linearity of expectation, and the third substitutes the parity moments just proved. The last line groups the surviving coefficients by their even order.
Odd-order interactions disappear. Even-order interactions survive, and all interactions of the same order carry the same weight.
Corollary (Degree-three mean): Under the degree-three assumption, only the intercept and the sum of the pairwise interactions remain:
\[ \mathbb{E}[g(S)] = \widehat g(\emptyset) +\frac13\sum_{|T|=2}\widehat g(T). \]
To capture the pairwise contribution, we need only the sum of its coefficients. A design can merge pairs with each other while keeping them separate from the intercept. Higher-order coefficients may enter those same measurements; their contribution will account for the approximation error.
What a Fraction Measures
Restricting the measurements to part of the cube mixes coefficients that full enumeration could distinguish. Let \(H\leq\{-1,+1\}^d\) be a subgroup under coordinatewise multiplication, and evaluate \(g\) only at the coalitions in \(H\). For every \(U\subseteq[d]\), take the signed average:
\[ Y_U := \frac{1}{|H|} \sum_{x\in H}g(x)\chi_U(x). \]
The plain average of the observed values is \(Y_\emptyset\). The other \(Y_U\) multiply those same values by the sign pattern of \(\chi_U\) before averaging.
Two sets are aliased when their parities agree at every observed coalition.
Lemma (Aliasing identity): Each signed average is the sum of the coefficients aliased with its parity:
\[ Y_U = \sum_{\substack{T\subseteq[d]:\\ \chi_T(x)=\chi_U(x)\text{ for every }x\in H}} \widehat g(T). \]
Proof
Substituting the Fourier expansion shows exactly which coefficients each measurement combines:
\[\begin{align} Y_U &= \frac{1}{|H|} \sum_{x\in H} \left( \sum_{T\subseteq[d]}\widehat g(T)\chi_T(x) \right) \chi_U(x) \\ &= \sum_{T\subseteq[d]}\widehat g(T) \cdot \frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(x). \end{align}\]
The first line inserts the expansion. The second swaps the sums and uses \(\chi_T\chi_U=\chi_{T\mathbin{\triangle}U}\). It remains to evaluate the inner average.
First suppose \(\chi_T\) and \(\chi_U\) agree throughout \(H\). Then their product is one at every observed point:
\[\begin{align} \chi_{T\mathbin{\triangle}U}(x) &=\chi_T(x)\chi_U(x) \\ &=\chi_T(x)^2 \\ &=1 \qquad\text{for every }x\in H. \end{align}\]
The average is therefore one:
\[ \frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(x) = \frac{1}{|H|} \sum_{x\in H}1 =1. \]
Now suppose the parities do not agree throughout \(H\). There is then some \(y\in H\) for which their signs differ, and hence:
\[ \chi_{T\mathbin{\triangle}U}(y) = \chi_T(y)\chi_U(y) =-1. \]
Because \(H\) is a subgroup, the map \(x\mapsto yx\) is a permutation of \(H\). Reindexing the average by that permutation and using multiplicativity gives:
\[\begin{align} \frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(x) &= \frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(yx) \\ &= \frac{1}{|H|} \sum_{x\in H} \chi_{T\mathbin{\triangle}U}(y) \chi_{T\mathbin{\triangle}U}(x) \\ &= -\frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(x). \end{align}\]
The same real number equals its negative, so it must be zero. Thus the inner average obeys the cancellation rule:
\[ \frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(x) = \begin{cases} 1, & \chi_T(x)=\chi_U(x)\text{ for every }x\in H,\\ 0, & \text{otherwise}. \end{cases} \]
Substituting this rule into the expression for \(Y_U\) removes every nonaliased coefficient and proves the lemma.
A fractional measurement therefore returns an alias-class sum, not an individual coefficient.
Choosing the Fraction
We construct \(H\) so that selected pair parities agree on every observed coalition. Whenever \(\chi_U|_H=\chi_W|_H\), their signed averages are literally the same number, \(Y_U=Y_W\), and the aliasing lemma says that this common measurement contains the coefficients indexed by both \(U\) and \(W\). The aim is to put pairs into such groups without putting any pair in the intercept’s group.
First consider the three-factor half fraction \(x_1x_2x_3=1\). Its four runs are \((+1,+1,+1)\), \((+1,-1,-1)\), \((-1,+1,-1)\), and \((-1,-1,+1)\). Multiplication by \(x_3\) gives \(x_1x_2=x_3\), so \(Y_{\{1,2\}}=Y_{\{3\}}\). This is the wrong alias: it merges a pair, whose Shapley weight is \(1/3\), with a main effect, whose weight is zero.
For five elements, let \(z_0,z_1,z_2,z_3\in\{-1,+1\}\) vary freely and use the columns:
\[\begin{align} x_1&=z_0, & x_2&=z_0z_1, & x_3&=z_0z_2,\\ x_4&=z_0z_1z_2, & x_5&=z_0z_3.&& \end{align}\]
Their only nontrivial defining relation is \(x_1x_2x_3x_4=1\). It gives three equal pairs of measurements:
\[\begin{align} Y_{\{1,2\}}&=Y_{\{3,4\}}, & Y_{\{1,3\}}&=Y_{\{2,4\}}, & Y_{\{1,4\}}&=Y_{\{2,3\}}. \end{align}\]
The four measurements involving element \(5\) remain distinct. Thus the ten pairs form seven groups, and under the degree-three assumption, adding one \(Y_U\) from each group counts every pairwise coefficient once.
The same construction works for any \(d\geq2\). Set:
\[ r=\lceil\log_2d\rceil. \]
The construction below uses \(2^{r+1}\) evaluations and keeps odd- and even-order interactions in separate alias classes. It also keeps every pairwise term out of the intercept’s alias class.
The construction for arbitrary dimension
Choose distinct sets \(A_1,\ldots,A_d\subseteq[r]\) satisfying:
\[ A_1=\emptyset, \qquad \bigl\{\emptyset,\{1\},\ldots,\{r\}\bigr\} \subseteq \{A_1,\ldots,A_d\} \subseteq 2^{[r]}, \qquad A_j\neq A_\ell\ \text{for }j\neq\ell. \]
Such a choice exists because \(r+1\leq d\leq2^r\). For every \(z=(z_0,\ldots,z_r)\in\{-1,+1\}^{r+1}\), define:
\[ x_j(z) = z_0\prod_{k\in A_j}z_k, \qquad j\in[d], \]
and take the fraction:
\[ H = \bigl\{(x_1(z),\ldots,x_d(z)): z\in\{-1,+1\}^{r+1}\bigr\}. \]
For \(d=5\), the choice \((A_1,\ldots,A_5)=(\emptyset,\{1\},\{2\},\{1,2\},\{3\})\) gives exactly the five columns above. For \(d=1\), use the full two-point cube.
Lemma (Regular fraction): The set \(H\) is a subgroup of \(\{-1,+1\}^d\) with \(|H|=2^{r+1}\). Every restricted parity is a product of \(z_0,\ldots,z_r\), all \(2^{r+1}\) such products occur, and every defining relation contains an even number of factor columns.
Proof
For \(z,w\in\{-1,+1\}^{r+1}\), write \(zw=(z_0w_0,\ldots,z_rw_r)\). Coordinatewise multiplication gives another run because:
\[ x_j(z)x_j(w) = (z_0w_0)\prod_{k\in A_j}(z_kw_k) = x_j(zw). \]
The all-\(+1\) choice gives the identity and \(x(z)^2\) is the identity, so \(H\) is a subgroup.
The map \(z\mapsto x(z)\) is injective. Indeed, \(A_1=\emptyset\) gives \(z_0=x_1(z)\). For each \(k\in[r]\), one chosen set equals \(\{k\}\); if it is \(A_j\), then:
\[ z_k=x_1(z)x_j(z). \]
The run therefore determines every free sign, and hence \(|H|=2^{r+1}\).
For any \(U\subseteq[d]\), its parity on a run is:
\[ \chi_U(x(z)) = z_0^{|U|} \prod_{k=1}^r z_k^{\,|\{j\in U:k\in A_j\}|}. \]
Thus every restricted parity is a product of the free signs after even powers cancel. Conversely, \(\chi_{\{1\}}(x(z))=z_0\), and whenever \(A_j=\{k\}\) we have \(\chi_{\{1,j\}}(x(z))=z_k\). Products of these parities produce all \(2^{r+1}\) products of the free signs.
Finally, a defining relation has \(\chi_U(x(z))=1\) for every \(z\). The exponent of \(z_0\) in the preceding display is \(|U|\), so independence of the free signs forces \(|U|\) to be even. Every defining relation therefore has even length.
This is a regular fractional factorial design in the terminology of Wu and Hamada [WH, ’21]. Even-order coefficients therefore alias only with even-order coefficients, and odd-order coefficients only with odd-order coefficients.
The observed values form a function on the \((r+1)\)-dimensional sign cube. A Walsh–Hadamard transform returns its signed average against every product of the free signs, which is one \(Y_U\) for each alias class. With \(2^{r+1}\) inputs and \(r+1\) stages, this takes \(O(d\log d)\) arithmetic operations.
Recovering the Mean
Choose one pair from each alias class that contains a pair, and let \(\mathcal{R}\) be the set of chosen representatives. Our estimate of \(\mathbb{E}[g(S)]\) is:
\[ \widehat\mu =Y_\emptyset +\frac13\sum_{U\in\mathcal{R}}Y_U. \]
This adds the intercept measurement to one third of the sum of the pair measurements. The same formula applies to general \(g\); the degree-three case establishes which contributions it captures exactly.
Claim (Exact mean recovery): If \(g\) has Fourier degree at most three, then the estimate is exact:
\[ \widehat\mu=\mathbb{E}[g(S)]. \]
Proof
Every defining relation has even length, so even-order coefficients never alias with odd-order coefficients. Under degree three, an even-order coefficient is either the intercept or a pairwise interaction.
The intercept is not aliased with any pair. If \(\chi_{\{j,k\}}(x)=1\) on every run, then \(x_j=x_k\) on every run because each sign is its own inverse. That would make the two factor columns identical, contradicting the construction’s use of distinct products of the free signs. The aliasing lemma therefore gives \(Y_\emptyset=\widehat g(\emptyset)\).
Now start from a pair \(U\). Its alias class contains only even-order coefficients, and the intercept has just been excluded. Under degree three, \(Y_U\) is therefore the sum of exactly the pairwise coefficients in that class. In the five-element example, the relation \(x_1x_2=x_3x_4\) gives \(Y_{\{1,2\}}=\widehat g(\{1,2\})+\widehat g(\{3,4\})\).
The pair alias classes partition all pairwise coefficients. Choosing one representative from each class counts every pairwise coefficient once, so \(\sum_{U\in\mathcal{R}}Y_U=\sum_{|T|=2}\widehat g(T)\). Substituting this identity and \(Y_\emptyset=\widehat g(\emptyset)\) into the earlier mean formula proves the claim.
The design uses one value of \(g\) for each of its \(2^{r+1}\) coalitions, and \(|H|=2^{1+\lceil\log_2d\rceil}<2^{1+(\log_2d+1)}=4d\). The strict inequality uses \(\lceil a\rceil<a+1\) with \(a=\log_2d\). Thus the estimator uses fewer than \(4d\) evaluations, compared with \(2^d\) for full enumeration, and is exact under the degree-three condition.
Beyond Exact Low Degree
The estimator already gives the correct contribution of the intercept and every pairwise term. Odd-order terms contribute zero to both the expectation and the estimate because the design keeps odd and even orders in separate alias classes. Only even-order terms of order four and above can contribute error.
A higher-order coefficient enters the estimate with weight one if it aliases with the intercept, one third if it aliases with a pair, and zero otherwise. Its weight in the true expectation is \(1/(|T|+1)\), where \(T\) indexes that interaction. The error is the sum of each such coefficient multiplied by the difference between these weights. Every weight difference has magnitude at most one, so the triangle inequality bounds the error by the total magnitude of the higher-order coefficients:
\[ \left|\widehat\mu-\mathbb{E}[g(S)]\right| \leq \sum_{\substack{T\subseteq[d]\\|T|\geq4,\ |T|\text{ even}}} \left|\widehat g(T)\right|. \]
Small individual coefficients alone do not guarantee accuracy: many of them can add in the same direction. Contributions of opposite signs can cancel, giving a smaller error than this bound.
Shapley Values
Let \(f:2^{[d]}\to\mathbb{R}\) be a cooperative game and fix player \(i\). On the remaining \(d-1\) players, define the marginal-contribution function:
\[ g(S) = f(S\cup\{i\})-f(S), \qquad S\subseteq[d]\setminus\{i\}. \]
Its Shapley-distribution mean is the Shapley value:
\[ \phi_i(f) = \mathbb{E}[g(S)]. \]
Here the Shapley distribution is on the remaining \(d-1\) players: choose \(|S|\) uniformly from \(\{0,\ldots,d-1\}\), then choose \(S\) uniformly among coalitions of that size.
Lemma (A first difference lowers degree): If \(f\) has Fourier degree at most four, then \(g\) has Fourier degree at most three.
Proof
Split the Fourier expansion into terms that contain \(i\) and terms that do not. The sign of coordinate \(i\) is \(+1\) at \(S\cup\{i\}\) and \(-1\) at \(S\), so the two expansions are:
\[\begin{align} f(S\cup\{i\}) &= \sum_{T\not\ni i}\widehat f(T)\chi_T(S) +\sum_{T\ni i}\widehat f(T)\chi_{T\setminus\{i\}}(S), \\ f(S) &= \sum_{T\not\ni i}\widehat f(T)\chi_T(S) -\sum_{T\ni i}\widehat f(T)\chi_{T\setminus\{i\}}(S). \end{align}\]
Subtracting the second expansion from the first cancels every term not involving \(i\) and doubles every term involving \(i\):
\[\begin{align} g(S) &= \sum_{T\ni i}\widehat f(T)\chi_{T\setminus\{i\}}(S) +\sum_{T\ni i}\widehat f(T)\chi_{T\setminus\{i\}}(S) \\ &= 2\sum_{T\ni i}\widehat f(T)\chi_{T\setminus\{i\}}(S). \end{align}\]
An order-\(|T|\) interaction containing \(i\) has become an order-\(|T|-1\) interaction on the remaining players. Thus degree at most four for \(f\) implies degree at most three for \(g\).
Lemma (Squaring can double degree): If \(f\) has Fourier degree at most \(k\), then the pointwise square \(f^2(S)=f(S)^2\) has Fourier degree at most \(\min\{d,2k\}\).
Proof
Expand both copies of \(f\) and use \(\chi_T\chi_U=\chi_{T\mathbin{\triangle}U}\):
\[\begin{align} f(S)^2 &= \left(\sum_{|T|\leq k}\widehat f(T)\chi_T(S)\right) \left(\sum_{|U|\leq k}\widehat f(U)\chi_U(S)\right) \\ &= \sum_{|T|\leq k}\sum_{|U|\leq k} \widehat f(T)\widehat f(U)\chi_{T\mathbin{\triangle}U}(S). \end{align}\]
Every parity in the last sum has order:
\[ |T\mathbin{\triangle}U| \leq |T|+|U| \leq 2k. \]
No parity can have order above \(d\), so the degree is at most \(\min\{d,2k\}\). The degree can be smaller because repeated variables cancel and different products can cancel in the coefficient sum.
For \(d\geq2\), applying the fractional design on the remaining \(d-1\) players uses fewer than \(4(d-1)\) evaluations of \(g\) for one exact Shapley value. Each evaluation of \(g\) uses the two coalition values \(f(S\cup\{i\})\) and \(f(S)\). The sampled sets \(S\) are distinct, and a coalition without \(i\) cannot equal one with \(i\). Thus one Shapley value costs fewer than \(8(d-1)\) evaluations of \(f\), and computing all \(d\) values separately, without reusing evaluations between players, costs fewer than \(8d(d-1)<8d^2\) evaluations of \(f\).
Zhou, Mee, Hamers & Zheng reuse evaluations of \(f\) across players more cleverly. When every interaction involving five or more players is zero, their recursive construction recovers all Shapley values, and their Theorem 4 bounds the number of distinct evaluations of \(f\) by \(4d^2-4\) [ZMHZ, JASA ’25]. Compared with our direct implementation’s leading bound of \(8d^2\), their reuse cuts the leading evaluation count by a factor of two.
For Shapley estimation, the higher-order error comes from interactions involving player \(i\) and at least four other players in the original game \(f\).
After estimating every Shapley value, efficiency gives an exact diagnostic. The true Shapley values satisfy efficiency, \(\sum_{i=1}^d\phi_i(f)=f([d])-f(\emptyset)\), so estimates \(\widehat\phi_i\) obey:
\[ \left| f([d])-f(\emptyset)-\sum_{i=1}^d\widehat\phi_i \right| = \left| \sum_{i=1}^d\bigl(\phi_i(f)-\widehat\phi_i\bigr) \right| \leq \sum_{i=1}^d\left|\phi_i(f)-\widehat\phi_i\right|. \]
The left side is the magnitude of the total signed error in the estimates and a lower bound on their total absolute error. A large efficiency gap certifies that the estimates are collectively inaccurate; in fact, at least one player’s absolute error is at least the gap divided by \(d\). A small gap is reassuring but does not prove individual accuracy, because individual errors can cancel across players.