Gustaf Rydberg (1835-1933) was a Swedish landscape painter.
One of the principal difficulties with the Shapley value is that its computation generally requires the sum of a very large number of terms.
Therefore we consider the multilinear extension of the game. Given a cooperative game \((N,v)\), we can interpret the coalitions \(S\subseteq N\) as the set of all vectors \((x_{1},\cdots ,x_{|N|})\) whose components are either \(0\) or \(1\). Therefore, \(2^{N}=\{0,1\}^{N}\) is the set of all corners of the unit cube in \(|N|\)-dimensional space. The cooperative game \((N,v)\) is then defined on the corners of the cube. It seems reasonable to try to extend it throughout the cube
\[[0,1]^{N}=\{(x_{1},\cdots ,x_{|N|}):0\leq x_{i}\leq 1\mbox{ for all }i\}.\]
There are many ways of extending the function \(v\). We shall extend it in a manner that is linear in each variable. This is the multilinear extension of \((N,v)\) (Owen \cite[p.267]{owe}).
Let \(f(x_{1},\cdots ,x_{n})\) be a function of \(n\) variables. We shall say that \(f\) is {\bf multilinear} if and only if \(f\) can be expressed in the form
\[f(x_{1},\cdots ,x_{n})=\sum_{S\subseteq N}c_{S}\prod_{i\in S}x_{i}\]
where \(N=\{1,2,\cdots ,n\}\) and the \(c_{S}\) are constants. We are interested in multilinear functions defined over th unit cube \([0,1]^{N}\). Given a cooperative game \((N,v)\), the {\bf multilinear extension} of \((N,v) is a function \)latex f$ defined by
\begin{equation}{\label{owe72eq1}}\tag{1}
f(x_{1},\cdots ,x_{|N|})=\sum_{S\subseteq N}\left [\prod_{i\in S}x_{i}\prod_{i\not\in S}(1-x_{i})\right ]v(S)
\end{equation}
for \(0\leq x_{i}\leq 1\), \(i=1,\cdots ,|N|\). (Owen \cite[p.78]{owe72} and Owen \cite[p.267]{owe}).
To justify the name, we shall show that \(f\) is multilinear (i.e., linear in each variable \(x_{i}\)), it is an extension of \(v\), and it is unique with respect to those properties. The multilinearity of \(f\) is obvious. We show that \(f\) is an extension of \(v\). For \(S\subseteq N\), we let \(\alpha^{S}\) be the \(S\)-corner of the cube, i.e.,
\[\alpha_{i}^{S}=\left\{\begin{array}{ll}
1 & \mbox{if \(i\in S\)}\\ 0 & \mbox{if \(i\not\in S\)}.\end{array}\right .\]
Then
\begin{equation}{\label{oweeq1222}}\tag{2}
f(\alpha_{S})=\sum_{T\subseteq N}\left [\prod_{i\in T}\alpha_{i}^{S}\prod_{i\not\in T}(1-\alpha_{i}^{S})\right ]v(T).
\end{equation}
It is easy to see that if \(T\neq S\) then the term in bracket in (\ref{oweeq1222}) vanishes. However, if \(T=S\), then the term in bracket is
equal to \(1\). Then \(f(\alpha_{S})=v(S)\). This shows that \(f\) is an extension of \(v\). The uniqueness is shown in the following result (Owen \cite[p.267]{owe}).
Proposition. (Owen \cite[p.79]{owe72}). Given a cooperative game \((N,v)\), there exists a unique multilinear function \(f\) defined on the unit cube \([0,1]^{N}\) satisfying \(f(\alpha_{S})=v(S)\) for all \(S\subseteq N\).
Heuristically, we can give a probabilistic interpretation to the multilinear extension \(f\) of the game \((N,v)\). Let us suppose that a coalition
is to be formed at random. Let \({\cal S}\) be this random coalition, and let the event \(A_{i}=\{i\in {\cal S}\}\) have probability \(x_{i}\), i.e., \(\mathbb{P}\{i\in {\cal S}\}=x_{i}\). Assuming that the events \(A_{i}\) are independent, then, for any fixed \(S\subseteq N\),
\[\mathbb{P}\{{\cal S}=S\}=\prod_{i\in S}x_{i}\prod_{i\not\in S}(1-x_{i}),\]
and so \(\mathbb{E}[v({\cal S})]=f(x_{1},\cdots ,x_{n})\). Therefore \(f\) can be thought of as the mathematical expectation of \(v({\cal S})\) under the given randomization shceme (Owen \cite[p.269]{owe}).
Let \(\phi_{i}(t)\), \(i=1,\cdots ,n\), be continuous and monotone functions with \(\phi_{i}(0)=0\) and \(\phi_{i}(1)=1\) for all \(i\). Then the equations \(x_{i}=\phi_{i}(t)\) for \(0\leq t\leq 1\) will represent a monotone path from the origin \((0,0,\cdots ,0)\) to the unit corner \((1,1,\cdots ,1)\). Let us write
\[z_{i}=\int_{0}^{1}f_{i}(x_{1},\cdots ,x_{n})dx_{i}=\int_{0}^{1}f_{i}(\phi_{1}(t),\cdots ,\phi_{n}(t))d\phi_{i}(t),\]
where \(f_{i}\) is the \(i\)th partial derivative of the function \(f\). Then
\begin{align*}
\sum_{i=1}^{n}z_{i} & =\int_{0}^{1}\sum_{i=1}^{n}\frac{\partial f}{\partial x_{i}}\frac{dx_{i}}{dt}dt=\int_{0}^{1}\frac{df}{dt}dt\\
& =f(\phi_{1}(1),\cdots ,\phi_{n}(1))-f(\phi_{1}(0),\cdots ,\phi_{n}(0))\\
& =f(\alpha_{N})-f(\alpha_{\emptyset})=v(N)-v(\emptyset )=v(N);
\end{align*}
that is, we obtain
\begin{equation}{\label{owe72eq7}}\tag{3}
\sum_{i=1}^{n}z_{i}=v(N).
\end{equation}
Moreover, differenting (\ref{owe72eq1}), we have
\[f_{i}({\bf x})=\sum_{S’\subseteq N,i\in S’}\left [\prod_{j\in S’,j\neq i}
x_{j}\prod_{j\in S’}(1-x_{j})\right ]v(S’)-\sum_{S\subseteq N,i\not\in S}
\left [\prod_{j\in S}x_{j}\prod_{j\not\in S,j\neq i}(1-x_{j})\right ]v(S).\]
Letting \(S’=S\cup\{i\}\), we can collect the two sums to obtain
\begin{equation}{\label{owe72eq8}}\tag{4}
f_{i}({\bf x})=\sum_{S\subseteq N,i\not\in S}\left [\prod_{j\in S}x_{j}\prod_{j\not\in S,j\neq i}(1-x_{j})\right ]
\left [v(S\cup\{i\})-v(S)\right ].
\end{equation}
In particular, we let \(\phi_{i}(t)=t\) for all \(i\), i.e., the path of integration will be the diagonal. In this case, from (\ref{owe72eq8}), we
obtain
\[f_{i}(t,t,\cdots ,t)=\sum_{S\subseteq N,i\not\in S}t^{|S|}(1-t)^{|N|-|S|-1}\left [v(S\cup\{i\})-v(S)\right ],\]
and so
\begin{align*}
z_{i} & =\sum_{S\subseteq N,i\not\in S}\int_{0}^{1}t^{|S|}(1-t)^{|N|-|S|-1}dt\left [v(S\cup\{i\})-v(S)\right ]\\
& =\sum_{S\subseteq N,i\not\in S}\frac{|S|!(|N|-|S|-1)!}{|N|!}\left [v(S\cup\{i\})-v(S)\right ],
\end{align*}
which gives the following result (Owen \cite[p.66]{owe72}).
Theorem. (Owen \cite[p.66]{owe72}). If the path of integration is the main diagonal, then \({\bf z}=(z_{1},\cdots ,z_{n})\) is the Shapley value.
Proof. Here we give an alternative proof by showing that \({\bf Z}\) satisfies the Shapley’s axioms. In effect, the carrier axiom is satisfied by
(\ref{owe72eq7}). The symmetry of the path of integration (the main diagonal) guarantees the symmetry axiom. Finally, the form (\ref{owe72eq1}) is linear in \(v\), which guarantees the additivity of \(f\), and hence of its derivatives \(f_{i}\) and their integrals \(z_{i}\). Since the Shapley value is the only vector satisfying these axioms, it must coincides with \({\bf z}\). \(\blacksquare\)
