Aliasing on Purpose
10 min read
For \(d\ge1\), let \([d]=\{1,\ldots,d\}\) be a set of players. A coalition is a subset \(S\subseteq[d]\), and a set function \(g\) assigns a real number \(g(S)\) to each coalition.
We want to average these numbers using a distribution \(P\): choose the size \(k\) uniformly from \(0,\ldots,d\), then choose \(S\) uniformly among the \(\binom dk\) coalitions of that size. Thus a particular coalition has probability \(P(S)=1/\bigl((d+1)\binom d{|S|}\bigr)\), and our target is
\[ \mu=\mathbb E_P[g(S)] =\frac1{d+1}\sum_{k=0}^d \frac1{\binom dk}\sum_{|S|=k}g(S). \]
Evaluating \(g(S)\) may require an expensive experiment or model run. Calculating the sum directly requires all \(2^d\) evaluations. The idea is to choose fewer coalitions whose values determine the average, even though they do not determine the whole function. We will make the required assumption on \(g\) precise, then apply the construction to Shapley values [ZMHZ, JASA ’25].
Write the Function in Signs
Represent a coalition by signs: \(x_j=+1\) when \(j\in S\), and \(x_j=-1\) otherwise. We write \(g(x)\) for the same value \(g(S)\). For any subset \(T\subseteq[d]\), define the sign product \(\chi_T(x)=\prod_{j\in T}x_j\), with \(\chi_\emptyset(x)=1\). Every set function has a unique expansion
\[ g(x)=\sum_{T\subseteq[d]}a_T\chi_T(x). \]
These \(a_T\) are the Boolean Fourier coefficients. The term indexed by \(T\) is an interaction of order \(|T|\); the empty set gives the constant term. The full expansion is exact. A low-degree assumption means that some of these coefficients are zero.
To identify the coefficients, let \(U\) be the uniform distribution on all \(2^d\) sign vectors. Under \(U\), the signs are independent and equally likely to be \(-1\) or \(+1\). For any two subsets \(T,R\subseteq[d]\),
\[ \mathbb E_U[\chi_T(x)\chi_R(x)] =\begin{cases}1,&T=R,\\0,&T\ne R.\end{cases} \]
This is orthogonality: different sign products have zero average product. When \(T\ne R\), at least one independent sign occurs only once, making the expectation zero. Multiplying the expansion by \(\chi_T\) and averaging therefore picks out its coefficient:
\[ a_T=\mathbb E_U[g(x)\chi_T(x)]. \]
There are \(2^d\) orthogonal products for \(2^d\) function values, so they form a basis. We use the coefficients to describe the function; our experiment will recover the needed sum without computing them individually.
The coefficients use the uniform law \(U\), even though our target average uses \(P\). Under \(P\), these products need not be orthogonal. We will compute their target means separately.
The Sum We Need
Assume now that \(a_T=0\) for \(|T|\ge4\). Writing \(a_0,a_j,a_{jk},a_{jk\ell}\) for the constant, single-player, pair, and triple coefficients, this says
\[ g(x)=a_0+\sum_j a_jx_j +\sum_{j<k}a_{jk}x_jx_k +\sum_{j<k<\ell}a_{jk\ell}x_jx_kx_\ell. \]
The restriction concerns polynomial degree; we can still evaluate coalitions of any size.
Under \(P\), complementary coalitions have the same probability. Complementing reverses every sign, so every odd-order term has mean zero.
For a pair, the mean is \(1/3\). To see this, place the \(d\) elements and a marker in a uniformly random order, and take \(S\) to be the elements before the marker. The marker’s position is uniform, and the elements before it form a uniform coalition of that size, giving exactly our distribution. Among two particular elements and the marker, the marker is first or last with probability \(2/3\), giving equal signs. It is in the middle with probability \(1/3\), giving opposite signs. Thus \(\mathbb E_P[x_jx_k]=2/3-1/3=1/3\), and
\[ \boxed{\mu=a_0+\frac13\sum_{j<k}a_{jk}.} \]
Estimating every pair coefficient separately would recover more information than we need.
Five Players, Sixteen Evaluations
For five players there are \(32\) possible coalitions. Evaluate only the \(16\) satisfying
\[ x_1x_2x_3x_4=1. \]
Call this set of sign vectors \(H\). It is a fractional factorial design: we evaluate a chosen fraction of the full set of sign combinations. Generate \(H\) by letting \(x_1,x_2,x_3,x_5\) each take both signs and setting \(x_4=x_1x_2x_3\). On every one of these coalitions,
\[ x_1x_2=x_3x_4,\qquad x_1x_3=x_2x_4,\qquad x_1x_4=x_2x_3. \]
The corresponding pairs are aliased: our observations cannot distinguish their sign patterns. For example, adding one to \(a_{12}\) and subtracting one from \(a_{34}\) changes none of the observed values. It also changes none of their contribution to \(\mu\), because both coefficients have weight \(1/3\).
Using the same sixteen observed values each time, compute the ordinary average and signed averages:
\[ B_0=\frac1{16}\sum_{x\in H}g(x), \qquad B_{jk}=\frac1{16}\sum_{x\in H}g(x)x_jx_k. \]
These are averages over the chosen experiment \(H\), not expectations under the target law \(P\). No random sampling is required: we evaluate every point in \(H\) once.
Under our degree-three assumption, these measurements give
\[\begin{align} B_0&=a_0,\\ B_{12}&=a_{12}+a_{34},& B_{13}&=a_{13}+a_{24},& B_{14}&=a_{14}+a_{23},\\ B_{j5}&=a_{j5}\qquad (j=1,2,3,4). \end{align}\]
Here orthogonality does the recovery work. Within \(H\), two sign products either become identical or remain orthogonal:
\[ \frac1{16}\sum_{x\in H}\chi_T(x)\chi_R(x) =\begin{cases} 1,&\chi_T(x)=\chi_R(x)\text{ for every }x\in H,\\ 0,&\text{otherwise}. \end{cases} \]
To see this, substitute \(x_4=x_1x_2x_3\). Every product becomes a product of the four free signs. Its average is zero unless every sign occurs an even number of times, in which case the product is always one. Among terms of degree at most three, only \(x_1x_2\) and \(x_3x_4\) agree with \(x_1x_2\) on \(H\). Their coefficients therefore survive in \(B_{12}\), and all other terms cancel. The same argument gives the other measurements.
Add one measurement from each group:
\[ \boxed{ \mu=B_0+\frac13 \left(B_{12}+B_{13}+B_{14} +B_{15}+B_{25}+B_{35}+B_{45}\right). } \]
This is exact because the seven measurements partition the ten pair coefficients. The individual effects remain ambiguous, but their required sum is determined.
The choice of fraction matters. A constraint such as \(x_1x_2x_3=1\) would merge \(x_1x_2\) with \(x_3\). That combines a pair with weight \(1/3\) and a single-player term with weight zero, so their sum would not be enough.
Why the Distribution Matters
For a different target distribution \(Q\), define the interaction weights \(m_T=\mathbb E_Q[\chi_T(x)]\). Linearity gives
\[ \mathbb E_Q[g(x)]=\sum_Ta_Tm_T. \]
Changing the distribution changes these weights, while the Fourier coefficients stay the same. For example, under the uniform law \(U\), every nonconstant interaction has mean zero, so the target is just \(a_0\), recovered by \(B_0\) under our degree-three assumption. Under \(P\), each pair has weight \(1/3\), so we also need the sum of pair coefficients.
This determines which effects we may safely merge. Write \(m_{12}=m_{\{1,2\}}\) and \(m_{34}=m_{\{3,4\}}\). The measurement \(B_{12}\) tells us \(a_{12}+a_{34}\). It determines \(m_{12}a_{12}+m_{34}a_{34}\) for arbitrary coefficients exactly when \(m_{12}=m_{34}\).
Orthogonality separates the observable groups; equal target weights let us use their sums. We do not require orthogonality under the target distribution.
The Same Construction in Any Dimension
We need two properties: odd effects must stay separate from even effects, and no pair may look like the constant term. Pairs are allowed to merge with one another.
For \(d\ge2\), set \(r=\lceil\log_2d\rceil\) and let \(z_0,\ldots,z_r\) each take values in \(\{-1,+1\}\). Choose \(d\) distinct subsets \(A_1,\ldots,A_d\) of \(\{1,\ldots,r\}\), including the empty set and each singleton. There is room because \(r+1\le d\le2^r\). Define the player signs by
\[ x_j=z_0\prod_{k\in A_j}z_k, \qquad j=1,\ldots,d, \]
and evaluate \(g\) for every choice of the free signs. The empty-set choice gives \(z_0\); each singleton choice then reveals one more \(z_k\). Thus the player signs determine all the free signs, giving \(2^{r+1}<4d\) distinct evaluations. For \(d=1\), use both coalitions.
The extra sign \(z_0\) is doing useful work. Every odd-order term contains it, while every even-order term loses it through cancellation. Odd and even terms therefore cannot have the same observed sign pattern. Also, two distinct player signs have a nonconstant product, so no pair is aliased with the constant term.
Define \(B_0\) and \(B_{jk}\) as before, now taking the uniform average over all points in this design. This is also the uniform average over all settings of the free signs, so distinct products of those signs are orthogonal. Consequently, under degree three, \(B_0=a_0\) and each \(B_{jk}\) is the sum of all pair coefficients sharing its sign pattern. Choose one representative from each distinct pair pattern, forming a set \(\mathcal R\). Then
\[ \widehat\mu=B_0+\frac13\sum_{\{j,k\}\in\mathcal R}B_{jk} =a_0+\frac13\sum_{j<k}a_{jk} =\mu. \]
That proves exact recovery with fewer than \(4d\) evaluations. This construction uses regular fractional factorial designs [WH, ’21]. The bound counts evaluations of \(g\); grouping pair patterns and computing the signed averages also require arithmetic.
When Higher Interactions Matter
The same estimator can be used for any \(g\), but higher interactions may contaminate its measurements. In the five-player example, add the term \(c\,x_1x_2x_3x_4\), where \(c\) is any real coefficient. It is always \(c\) on our fraction, so the estimate increases by \(c\). Its true mean is only \(c/5\). The resulting error is \(4c/5\).
For the general error, return to the full Fourier expansion, allowing coefficients of every order. Odd-order terms contribute zero to both the target mean and our estimate, because both \(P\) and the design are unchanged by reversing every sign. An even-order coefficient has true weight \(1/(|T|+1)\). In the estimate its weight \(w_T\) is one if it aliases with the constant term, one third if it aliases with a pair, and zero otherwise. The constant and pair coefficients already have the correct weights, giving the exact error formula
\[ \widehat\mu-\mu = \sum_{\substack{|T|\ge4\\|T|\text{ even}}} \left(w_T-\frac1{|T|+1}\right)a_T. \]
Since each weight difference has magnitude at most one,
\[ \boxed{ |\widehat\mu-\mu| \le \sum_{\substack{|T|\ge4\\|T|\text{ even}}}|a_T|. } \]
Accuracy therefore follows when the total magnitude of the higher even-order coefficients is small. Without such a condition, changing \(g\) at an unobserved coalition can change the target mean arbitrarily.
The mean of a higher-order interaction
Draw \(t\) uniformly from \([0,1]\), then include each element independently with probability \(t\). For a particular coalition \(S\), the Beta integral gives
\[ \Pr(S)=\int_0^1t^{|S|}(1-t)^{d-|S|}\,dt =\frac1{d+1}\binom d{|S|}^{-1}, \]
so this is our uniform-by-size, uniform-within-size distribution. Conditional on \(t\), each sign has mean \(2t-1\) and the signs are independent. Thus
\[ \mathbb E_P[\chi_T] =\int_0^1(2t-1)^{|T|}\,dt = \begin{cases} 1/(|T|+1),&|T|\text{ even},\\ 0,&|T|\text{ odd}. \end{cases} \]
Applying the Design to Shapley Values
Let \(N=\{1,\ldots,n\}\) be a set of \(n\ge2\) players, and let the game value \(f(S)\) be a real number for each coalition \(S\subseteq N\). Fix player \(i\). Its marginal contribution to a coalition \(S\subseteq N\setminus\{i\}\) is the change in value when it joins:
\[ g(S)=f(S\cup\{i\})-f(S). \]
The Shapley value averages this contribution over a uniformly random ordering of the players, with \(S\) the players before \(i\). Player \(i\) has a uniform position, so \(|S|\) is uniform from \(0\) through \(n-1\); conditional on its size, \(S\) is uniform too. After labeling the other \(d=n-1\) players by \([d]\), this is exactly our distribution \(P\):
\[ \phi_i(f)=\mathbb E_P[g(S)]. \]
Taking a marginal contribution lowers interaction degree by one. Indeed, let \(b_T\) be the Boolean Fourier coefficients of \(f\), so \(f(x)=\sum_{T\subseteq N}b_T\chi_T(x)\). Write \(x_{-i}\) for all signs except \(x_i\). Terms not involving \(i\) cancel, while changing \(x_i\) from \(-1\) to \(+1\) gives
\[ g(x_{-i})=2\sum_{T\ni i}b_T\chi_{T\setminus\{i\}}(x_{-i}). \]
Thus if \(f\) has no interactions above order four, \(g\) has none above order three and the fractional design gives its Shapley value exactly. Higher odd-order interactions of \(f\) involving \(i\) can create the higher even-order error described above.
For \(n\ge2\), each player needs fewer than \(4(n-1)\) evaluations of \(g\). Each uses two values of \(f\), so computing all players separately costs fewer than \(8n(n-1)\) game evaluations. Zhou, Mee, Hamers & Zheng reuse evaluations across players: their recursive construction requires at most \(4n^2-4\) distinct game evaluations under the same degree-four exactness condition [ZMHZ, JASA ’25].
The computational saving comes from recovering the weighted sums that Shapley values need, while letting individual interactions remain unresolved.