Shapley Values at Legendre Nodes
8 min read
I spend much of my research time on Shapley values, which can feel like a keyhole: while trying to open the lock, I get to see a much larger mathematical world through that small opening. Here, the view includes Legendre polynomials and their orthogonality.
Suppose several improvements multiply a system’s output. The extra output credited to one depends on which others are already in place. Shapley values average over arrival orders, but computing that average appears to require exponentially many groups. For products, a connection to numerical integration gives every player’s value in quadratic time, a saving used to explain decision trees and product-kernel predictors.
The Product Game
Let the players be \([d]=\{1,\ldots,d\}\), with fixed real multipliers \(u_1,\ldots,u_d\). A product game assigns each coalition \(S\subseteq[d]\) the output:
\[ f(S)=\prod_{j\in S}u_j, \qquad f(\emptyset)=1. \]
Player \(i\)’s marginal contribution is the change when it joins:
\[ f(S\cup\{i\})-f(S) =(u_i-1)\prod_{j\in S}u_j, \qquad i\notin S. \]
Its Shapley value averages that contribution over a uniformly random ordering:
\[ \phi_i(f)= \sum_{S\subseteq[d]\setminus\{i\}} \frac{|S|!\,(d-1-|S|)!}{d!} \bigl(f(S\cup\{i\})-f(S)\bigr). \]
The weight counts the \(|S|!\) orders before \(i\) and the \((d-1-|S|)!\) orders after it, out of \(d!\) total orders. For two players that double and triple an initial output of one, player 1 adds one if first and three if second:
\[ \phi_1(f)=\frac{(2-1)+(6-3)}2=2. \]
Player 2 receives three, so their credits sum to five, the increase from one to six. Even one player’s sum contains \(2^{d-1}\) terms. QuadraSHAP converts this sum into a polynomial integral that can be evaluated exactly without expanding it [MRSMC, ’26].
A Random Arrival Time
Give every player an independent arrival time, uniform on \([0,1]\), and sort the times. Ties have probability zero, and symmetry makes every ordering equally likely.
Now condition on player \(i\) arriving at time \(t\). Every other player independently arrives earlier with probability \(t\). Write \(S_t\) for this random predecessor set, which excludes \(i\). For a particular coalition \(S\), its conditional probability is:
\[ \Pr(S_t=S)=t^{|S|}(1-t)^{d-1-|S|}. \]
Without that conditioning, the inclusion events are dependent: a late arrival of \(i\) makes many predecessors likely at once. In the plot, move \(t\) from zero to one: the binomial distribution shifts from no predecessors to all of them. Averaging over a uniform arrival time makes every size equally likely, because player \(i\) is equally likely to occupy any of the \(d\) positions.
Coalition Sizes Before One Player
A Product of Expectations
At time \(t\), each player \(j\ne i\) supplies a factor of \(u_j\) if it has arrived and a factor of one otherwise. The expected factor is:
\[ (1-t)\cdot1+t\cdot u_j=1+t(u_j-1). \]
Conditional independence lets us compute the expected product without visiting the coalitions. Define:
\[ g_i(t) =\mathbb E\!\left[\prod_{j\in S_t}u_j\right] =\prod_{j\ne i}\bigl(1+t(u_j-1)\bigr). \]
Multiplying by \(u_i-1\) gives the expected marginal at time \(t\). Integrating over player \(i\)’s uniform arrival time gives its Shapley value:
Claim: For every product game with real multipliers:
\[ \phi_i(f)=(u_i-1)\int_0^1g_i(t)\,dt, \qquad \deg g_i\le d-1. \]
The degree bound follows from the \(d-1\) linear factors.
Proof by expanding the independent choices
Integrating the conditional coalition probability over player \(i\)’s uniform arrival time recovers its random-order probability:
\[ \int_0^1t^{|S|}(1-t)^{d-1-|S|}\,dt =\frac{|S|!\,(d-1-|S|)!}{d!}. \]
This is the Beta-integral identity. Substitute it into the Shapley sum, factor out \(u_i-1\), and exchange the finite sum with the integral:
\[\begin{align*} \phi_i(f) &=(u_i-1)\sum_{S\subseteq[d]\setminus\{i\}} \left(\int_0^1t^{|S|}(1-t)^{d-1-|S|}\,dt\right) \prod_{j\in S}u_j\\ &=(u_i-1)\int_0^1 \sum_{S\subseteq[d]\setminus\{i\}} t^{|S|}(1-t)^{d-1-|S|}\prod_{j\in S}u_j\,dt\\ &=(u_i-1)\int_0^1\prod_{j\ne i}\bigl((1-t)+tu_j\bigr)\,dt. \end{align*}\]
To see the last equality, expand the product by choosing either \(1-t\) or \(tu_j\) from each factor. The players for which we choose \(tu_j\) form \(S\); every coalition appears exactly once with the displayed probability.
Add a third player to the earlier example, with multipliers \((2,3,2)\). For player 1, the polynomial and its integral are:
\[\begin{align*} g_1(t)&=(1+2t)(1+t)\\ &=1+3t+2t^2,\\ \phi_1(f)&=1+\frac32+\frac23\\ &=\frac{19}{6}. \end{align*}\]
Evaluating only at the midpoint gives three, short of \(19/6\). In the figure, increase the node count from one to two to recover the missing area exactly. Changing the multipliers changes the curve, but two nodes still suffice. Setting one player’s multiplier to one makes that player’s entire marginal curve zero.
Marginal Credit as an Area
Node Locations and Weights
Each node contributes its height times its weight, and the weights add to one.
Exact Integration at Legendre Nodes
A quadrature rule replaces an integral by a weighted sum of function values. With \(q\) nodes \(\tau_1,\ldots,\tau_q\) in \([0,1]\) and weights \(\omega_1,\ldots,\omega_q\), write its action on a polynomial \(p\) as:
\[ Q_q[p]=\sum_{r=1}^q\omega_r p(\tau_r). \]
At any \(q\) distinct nodes, interpolation determines a polynomial of degree at most \(q-1\) from its values. Integrating that interpolating polynomial gives weights that are exact through degree \(q-1\). Gauss–Legendre quadrature doubles the number of polynomial degrees covered by choosing the nodes as well as the weights.
Let \(L_q\) be the degree-\(q\) shifted Legendre polynomial, normalized to equal one at \(t=1\). Its defining orthogonality says:
\[ \int_0^1a(t)L_q(t)\,dt=0 \qquad\text{for every polynomial }a\text{ with }\deg a<q. \]
Thus multiplication by any lower-degree polynomial leaves its signed area zero. Shifted Legendre polynomials are the usual ones on \([-1,1]\) evaluated at \(2t-1\). For example, the degree-two polynomial is:
\[ L_2(t)=6t^2-6t+1. \]
The degree-\(q\) polynomial has \(q\) distinct roots, all inside \((0,1)\).
Claim: Choose the \(q\) roots of \(L_q\) as nodes, with interpolation weights that integrate polynomials through degree \(q-1\). Then:
\[ Q_q[p]=\int_0^1p(t)\,dt \qquad\text{whenever }\deg p\le2q-1. \]
Our integrand has degree at most \(d-1\), so the sufficient node count is:
\[ 2q-1\ge d-1 \quad\Longleftrightarrow\quad q\ge\left\lceil\frac d2\right\rceil. \]
With that choice, the exact Shapley calculation is:
\[ \phi_i(f)= (u_i-1)\sum_{r=1}^{\lceil d/2\rceil} \omega_r\prod_{j\ne i}\bigl(1+\tau_r(u_j-1)\bigr). \]
The values at these nodes need not determine the original polynomial. They determine its integral because every undetected polynomial in the guaranteed degree range has integral zero.
Proof by polynomial division
Divide \(p\) by \(L_q\), obtaining quotient \(a\) and remainder \(r\):
\[ p(t)=a(t)L_q(t)+r(t), \qquad \deg a\le q-1, \qquad \deg r\le q-1. \]
Orthogonality removes the first term from the integral:
\[ \int_0^1a(t)L_q(t)\,dt=0. \]
Every node is a root of \(L_q\), so the same term vanishes at every evaluation point:
\[ p(\tau_s)=r(\tau_s) \qquad(s=1,\ldots,q). \]
The remainder is within the degree range already covered by interpolation, hence:
\[\begin{align*} Q_q[p]&=Q_q[r]\\ &=\int_0^1r(t)\,dt\\ &=\int_0^1p(t)\,dt. \end{align*}\]
The first equality uses the zero values of \(L_q\) at the nodes, the second uses the degree of \(r\), and the third uses orthogonality.
In the figure, the nodes miss the entire plotted curve, yet its positive and negative areas cancel. Switching to the square of \(L_q\) shows exactly where that argument stops working.
What the Nodes Cannot See
The square has degree \(2q\), is zero at every node, and is positive between its roots. Its true integral is therefore positive while the quadrature answer is zero. More generally, for any \(q\) real nodes, the polynomial \(\prod_{s=1}^q(t-\tau_s)^2\) gives the same obstruction. No weighted rule using only those \(q\) values can be exact for every polynomial of degree \(2q\).
Here exactness means equality in exact arithmetic. Computed roots, weights, and products still incur floating-point error. With fewer nodes, a particular game may integrate exactly, but the degree bound no longer guarantees it.
All Players in Quadratic Time
At a fixed node \(t\), write the \(d\) factors as:
\[ b_j=1+t(u_j-1),\qquad j=1,\ldots,d. \]
Computing a separate product for every player would cost \(O(d^2)\) operations at this one node. Instead, form all prefix products in one left-to-right pass, and all suffix products in one right-to-left pass. Player \(i\)’s product is then:
\[ \prod_{j\ne i}b_j =\left(\prod_{j<i}b_j\right) \left(\prod_{j>i}b_j\right). \]
Both passes cost \(O(d)\), and each player needs just one multiplication of stored products. Accumulating the weighted contributions across \(q\) nodes therefore costs \(O(dq)\) arithmetic operations and \(O(d)\) working memory, processing nodes one at a time. The nodes and weights depend only on \(q\) and can be computed once and reused across games. With the exact node count, the evaluation cost is \(O(d^2)\) for all players.
Using prefix and suffix products also avoids dividing by a factor that might be zero. (For large products, overflow, underflow, and cancellation still require care; QuadraSHAP develops log-magnitude evaluation with sign tracking and separate handling of zero factors.)
The arrival-time integral works for any game, as in the classical multilinear-extension representation [Owen, ’72]. For an arbitrary game, evaluating the expected marginal contribution at even one node can still require a sum over \(2^{d-1}\) coalitions. Product structure makes that expectation cheap; replacing it by a random coalition sample would introduce sampling error even with enough quadrature nodes.
Trees and Product Kernels
The Shapley value is linear in the game, so we can compute each product term’s attribution and add the results. In a tree explanation, grouping repeated splits on the same feature gives each leaf a product of factors for the features along its path. Under path-dependent handling of absent features, those factors encode branch probabilities when a feature is absent and observed path decisions when it is present.
TreeGrad-Shap uses the multilinear-extension gradient and quadrature to compute tree attributions [LYL, ICLR ’26]. Quadrature-TreeSHAP extends the participation-probability formulation to higher-order Shapley interaction indices [WMY, ’26].
QuadraSHAP also handles product-kernel predictors, which add terms that multiply similarities across input coordinates. When the missing-feature model preserves that factorization, the same Legendre nodes give feature attributions for those predictors.