Probabilistic Values

Hermann David Salomon Corrodi (1844-1905) was an Italian painter.

For any collection $G\subseteq \mbox{TU}(N)$ of games and any player $i\in N$, a value for $i$ on $G$ is a function $\phi_{i}:G\rightarrow\mathbb{R}$. The value $\phi_{i}(v)$ of a particular game $(N,v)$ represents an assessment by player $i$ of his/her prospects from playing the game. This definition stands somewhat in contrast to the more traditional definition of a group value $\boldsymbol{\phi}=(\phi_{1},\cdots ,\phi_{|N|})$, which associates an $|N|$-vector with each game. Fix a player $i\in N$, and let $\{p_{i}^{S}:S\subseteq N\setminus\{i\}\}$ be a probability distribution over the collection of coalitions not containing $i$. A value $\phi_{i}$ for $i$ on $G$ is said to be a probabilistic value if and only if, for every $v\in G$, we have
\[\phi_{i}(v)=\sum_{\{S:S\subseteq N\setminus\{i\}\}}p_{i}^{S}\cdot\left [v(S\cup\{i\})-v(S)\right ].\]
For each $S\subseteq N\setminus\{i\}$, if $p_{i}^{S}$ is interpreted as the (subjective) probability that player $i$ joins coalition $S$,
then $\phi_{i}(v)$ is simply the expected payoff of player $i$ from the game. Both the Shapley and Banzhaf values are instances of probabilistic values.

The Banzhaf value for an individual player $i$ arises from the subjective belief that the player is equally likely to join any coalition, i.e., $p_{i}^{S}=1/2^{n-1}$ for all $S\subseteq N\setminus\{i\}$.
The Shapley value arises from the belief that the coalition he/she joins is equally likely to be of any size $s$ with $0\leq s\leq |N|$, and that all coalitions of size $s$ are equally likely, i.e.,
\[p_{i}^{S}=\frac{1}{|N|}\cdot\left (\begin{array}{c}|N|-1\\ |S|\end{array}\right )^{-1}=\frac{|S|!(|N|-|S|-1)!}{|N|!}\]
for all $S\subseteq N\setminus\{i\}$. (Weber \cite[p.102-103]{web88}).

We consider another concept of probabilistic value. Let $\{p_{i}^{S}:i\in S\subseteq N\}$ be a collection of probability distributions. For each $i\in N$, we have
\[\sum_{\{S:S\subseteq N,i\in S\}}p_{i}^{S}=1.\]
The probabilistic value $\widehat{\boldsymbol{\phi}}=(\widehat{\phi}_{1},\cdots ,\widehat{\phi}_{|N|})$ is defined by
\begin{equation}{\label{ga30}}\tag{1}
\widehat{\phi}_{i}(v)=\sum_{\{S:S\subseteq N,i\in S\}}p_{i}^{S}\cdot\left [v(S)-v(S\setminus\{i\})\right ]
\end{equation}
for all $i\in N$ (Amer et al. \cite[p.182]{ame03}).

Let $G$ be a subclass of $\mbox{TU}(N)$ and let $\phi_{i}$ be the value of player $i$ defined on $G$. We consider the following axioms.

(W1: Linearity). $\phi_{i}$ is a linear function on $G$, i.e., $\phi_{i}(v_{1}+v_{2})=\phi_{i}(v_{1})+\phi_{i}(v_{2})$ and $\phi_{i}(cv)=c\phi_{i}(v)$ for all $(N,v_{1}),(N,v_{2})\in G$ and $c>0$;
(W2: Dummy). If $i\in N$ is a dummy player in $(N,v)\in G$ defined in (\ref{ga36}), then $\phi_{i}(v)=v(i)$;
(W3: Monotonicity). If $(N,v)\in G$ is monotonic, then $\phi_{i}(v)\geq 0$. The monotonicity says that $v(S\cup\{i\})-v(S)\geq 0$; that is, player $i$ konws at least that his/her presence will never “hurt” a coalition.
(W4: Transfer Axiom). For all games $(N,v_{1}),(N,v_{2})\in G$ such that $(N,v_{1}\vee v_{2}),(N,v_{1}\wedge v_{2})\in G$,
we have $\phi_{i}(v_{1})+\phi_{i}(v_{2})=\phi_{i}(v_{1}\vee v_{2})+\phi_{i}(v_{1}\wedge v_{2})$.
(W5: Symmetry). For every $(N,v)\in G$, every permutation $\pi$ of $N$ and every $i\in N$, we have $\phi_{i}(v)=\phi_{\pi (i)}(\pi v)$.
(W6: Efficiency). For every $(N,v)\in G$, we have $\sum_{i\in N}\phi_{i}(v)=v(N)$.

Theorem. (Weber \cite[p.106]{web88}). Let $\phi_{i}$ be a value of player $i$ on defined $\mbox{TU}(N)$ or the set of all monotonic games. Assume that $\phi_{i}$ satisfies the axioms (W1), (W2) and (W3). Then $\phi_{i}$ is a probabilistic value. Conversely, every probabilistic value on $\mbox{TU}(N)$ or the set of all monotonic games satisfies the axioms {(W1), (W2) and (W3). $\sharp$

Theorem. (Weber \cite[p.106]{web88}). Let $\phi_{i}$ be a value for $i$ defined on the set of all super-additive games. If $\phi_{i}$ satisfies the axioms (W1), (W2) and (W3), then there is a collection of constants $\{p^{S}:S\subseteq N\setminus\{i\}\}$ satisfying
\[\sum_{S\subseteq N\setminus\{i\}}p^{S}=1\mbox{ and }p^{S}\geq 0\]
for all $\emptyset\neq S\subseteq N\setminus\{i\}$ such that, for every super-additive game $(N,v)$,
\[\phi_{i}(v)=\sum_{S\subseteq N\setminus\{i\}}p^{S}\cdot\left [v(S\cup\{i\})-v(S)\right ].\]
Furthermore, every such value defined on the set of all super-additive games satisfies axioms (W1), (W2) and (W3). $\sharp$

Therefore, for values defined on $\mbox{TU}(N)$ or the set of all monotonic games, we have a natural axiomatic characterization of the probabilistic values. However, for values defined on the set of all superadditive games, we are unable to rule out the possibility that $p^{\emptyset}<0$. This phenomenon is investigated next (Weber \cite[p.106]{web88}).

Given a cooperative game $(N,v)$, a player $i$ faced with the prospect of playing this game may seek to determine the amount of gain that
is guaranteed in the sense that he/she contributes at least this amount to any coalition that he/she joins. When $v$ is super-additive, this “floor” to the expectation of player $i$ is precisely $v(i)$, since $v(S\cup\{i\})-v(S)\geq v(i)$ for all $S\subseteq N\setminus\{i\}$ (when $S=\emptyset$, the marginal contribution is exactly $v(i)$). Taking this amount as ensured, player $i$ will strive to achieve as great a reward as he/she can in the new game $(N,v^{(i)})$ defined by
\[v^{(i)}(S)=\left\{\begin{array}{ll}
v(S), & \mbox{if $i\not\in S$}\\ v(S)-v(i), & \mbox{otherwise}.
\end{array}\right .\]
However, any gain from this new game is uncertain and depends upon factors such as the bargaining ability of the player. Hence, the two amounts under consideration, $v(i)$ and his/her gain from playing game $(N,v^{(i)})$, are measured, respectively, in “certain” and “uncertain” units (Weber \cite[p.107]{web88}).

Assume that the attitude of player $i$ toward risk is such that $1$ unit of uncertain gain is worth $\gamma$ units of certain gain, where $\gamma <1$ corresponds to risk aversion, and $\gamma =1$ to risk neutrality. Further assume that player $i$ evaluates his/her prospects from any game $(N,v)$ with $v(i)=0$ in terms of a probabilistic value $\phi_{i}(v)$. Then the valuation of any super-additive game $(N,v)$ expressed in units of certain gain will be
\begin{equation}{\label{ga27}}\tag{2}
\xi_{i}(v)=\gamma\phi_{i}(v^{(i)})+v(i).
\end{equation}
Let ${\cal P}$ be the set of probabilistic value defined on the set of all super-additive games. For any $\gamma\geq 0$, we denote by $V_{i}(\gamma )$ the set of all values $\xi_{i}$ on the set of all super-additive games such that (\ref{ga27}) is satisfied for some $\phi_{i}\in {\cal P}$, where $\gamma$ represents the attitude of player $i$ toward uncertain gain (Weber \cite[p.107-108]{web88}).

Theorem. (Weber \cite[p.108]{web88}). Given any player $i\in N$, a value $\xi_{i}$ defined on the set of all super-additive games satisfies axioms (W1), (W2) and (W3) if and only if $\xi_{i}\in\bigcup_{\gamma\geq 0}V_{i}(\gamma )$. If $0\leq\gamma^{\prime}<\gamma$, then $V_{i}(\gamma^{\prime})\subset V_{i}(\gamma )$ and $V_{i}(\gamma^{\prime})\neq V(\gamma )$. Furthermore, we have $V_{i}(1)={\cal P}$. $\sharp$

The above theorem can be viewed in several ways. One might ask whether the addition of some other natural axiom will lead to the conclusion that $p^{\emptyset}\geq 0$. For example, it is unreasonable for any player $i\in N$ to hope to attain more than
\[b_{i}(v)=\max_{S\subseteq N\setminus\{i\}}\left [v(S\cup\{i\})-v(S)\right ].\]
If we require that $\phi_{i}(v)\leq b_{i}(v)$ for all superadditive games $(N,v)$, then
\[\phi_{i}(\widehat{u}_{\{i\}})=\sum_{\emptyset\neq S\subseteq N\setminus\{i\}}p^{S}=1-p^{\emptyset}\leq b_{i}(\widehat{u}_{\{i\}})=1,\]
which implies $p^{\emptyset}\geq 0$, where $\widehat{u}_{\{i\}}$ is defined in (\ref{ga28}). (Weber \cite[p.108-109]{web88}).

Theorem. (Weber \cite[p.111]{web88}). Let $\phi_{i}$ be a value of player $i$ defined on the set of all simple games or the set of all monotonic games. Assume that $\phi_{i}$ satisfies the axioms (W2), (W3) and (W4). Then, $\phi_{i}$ is a probabilistic value. Furthermore, every probabilistic value on the set of all simple games or the set of all monotonic games satisfies the axioms (W2), (W3) and (W4). $\sharp$

Theorem. (Weber \cite[p.111]{web88}). Let $\phi_{i}$ be a value of player $i$ defined on the set of all simple and super-additive games.
Assume that $\phi_{i}$ satisfies the axioms (W2), (W3) and (W4). Then, there is a collection of constants $\{p^{S}:S\subseteq N\setminus\{i\}\}$ satisfying
\[\sum_{S\subseteq N\setminus\{i\}}p^{S}=1\mbox{ and }p^{S}\geq 0\]
for all $\emptyset\neq S\subseteq N\setminus\{i\}$ such that, for every simple and super-additive game $(N,v)$,
\[\phi_{i}(v)=\sum_{S\subseteq N\setminus\{i\}}p^{S}\cdot\left [v(S\cup\{i\})-v(S)\right ].\]
Furthermore, every such value defined on set of all simple and super-additive games satisfies axioms (W2), (W3) and (W4). $\sharp$

Let $\pi$ be any permutaion of $N$ and let $G$ be a subclass of $\mbox{TU}(N)$. We say that $G$ is {\bf symmetric} if and only if $v\in G$ implies $\pi v\in G$.

Proposition. (Weber \cite[p.112]{web88}). Let $G$ be a symmetric subclass of $\mbox{TU}(N)$ containing the set of all unanimity games and the set of all strict unanimity games. For each $i\in N$ and $(N,v)\in G$, suppose that
\[\phi_{i}(v)=\sum_{S\subseteq N\setminus\{i\}}p_{i}^{S}\cdot\left [v(S\cup\{i\})-v(S)\right ].\]
If axiom (W5) is satisfied, then there are constants $\{p^{S}\}_{s=0}^{n-1}$ such that $p_{i}^{S}=p_{|S|}$ for all $i\in N$ and $S\subseteq N\setminus\{i\}$. $\sharp$

Let $\{\mathbb{P}(\pi ):\pi\in\Pi (N)\}$ be a probability distribution over the set $\Pi (N)$ of $|N|!=n!$ permutations of $N$. From (\ref{ga40}), a random order value $\boldsymbol{\xi}=(\xi_{1},\cdots ,\xi_{n})$ on $G$ is defined by
\[\xi_{i}(v)=\mathbb{E}_{\mathbb{P}}[m_{i}(v,\cdot)]\]
for each $v\in \mbox{TU}(N)$, where $\mathbb{E}_{\mathbb{P}}$ is the expectation with respect to $\mathbb{P}$, i.e.,
\begin{equation}{\label{ga41}}\tag{3}
\xi_{i}(v)=\sum_{\pi\in\Pi (N)}\mathbb{P}(\pi )\cdot\left [v(P(\pi ,i)\cup\{i\})-v(P(\pi ,i))\right ]
\end{equation}
for all $i\in N$ and $(N,v)\in G$. To interpret this definition, we assume that the players have as their goal the eventual formation of the
grand coalition $N$. Further assume that they see coalition formation as a sequential process. Given any permutation $\pi$ of the players, each player $i$ joins with his predecessors in $\pi$, making the marginal contribution $v(\pi^{(i)}\cup\{i\})-v(\pi^{(i)})$ in the game $(N,v)$. Then, if the players share a common perception $\{r_{\pi}:\pi\in\Pi\}$ of the likelihood of the various permutations, the expected marginal contribution of a player is precisely his component of the random order value
(Weber \cite[p.113-114]{web88} and Monderer et al. \cite[p.29]{mon}).

\begin{equation}{\label{web88t13}}\tag{4}\mbox{}\end{equation}

Theorem \ref{web88t13}. (Weber \cite[p.114]{web88}). We have the following propertiese.

(i) Let $\boldsymbol{\xi}=(\xi_{1},\cdots ,\xi_{n})$ be a random order value on a subclass $G$ of $\mbox{TU}(N)$. Then each component of $\boldsymbol{\xi}$ is a probabilistic value on $G$, and $\boldsymbol{\xi}$ satisfies axiom {(W6).

(ii) Let $\boldsymbol{\phi}=(\phi_{1},\cdots ,\phi_{n})$ be a collection of probabilistic values on a subclass $G$ of $\mbox{TU}(N)$. Assume that $G$ contains the set of all unanimity games and the set of all strict unanimity games, and that $\boldsymbol{\phi}$ satisfies axiom (W6). Then $\boldsymbol{\phi}$ is a random order value. $\sharp$

From Theorem \ref{web88t13}, we see that a collection of individual probabilistic values is efficient for all games in its domain precisely when the players’ probabilistic views of the world are consistent, i.e., only when $\{p_{i}^{S}:S\subseteq N\setminus\{i\}\}$ arises from a single distribution $\{\mathbb{P}(\pi ):\pi\in\Pi (N)\}$. The family of random order values associates a set of imputation with each game. This set clearly contains the Shapley value of the game, we next show that it also contains the core of the game (Weber \cite[p.116]{web88}).

For any cooperative game $(N,v)$ and any permutation $\pi$ of $N$, the marginal vector ${\bf m}(v,\pi )$ is the imputations. The Weber set of $(N,v)$ is defined by
\[{\cal W}(v)=\overline{\mbox{co}}\left (\{{\bf m}(v,\pi ):\pi\in\Pi\}\right ),\]
where ${\cal W}(v)$ is the set of all imputations associated with $(N,v)$ by some random order value (Weber \cite[p.116]{web88}).

Theorem. (Weber \cite[p.117]{web88}). Given any cooperative game $(N,v)$, we have ${\cal C}(v)\subseteq {\cal W}(v)$. Furthermore, the cooperative game $(N,v)$ is convex if and only if ${\cal C}(v)={\cal W}(v)$. $\sharp$

The characterization of the Shapley value is as the only (group) value that satisfies the linearity, dummy, symmetry and efficiency axioms.

Theorem. (Weber \cite[p.117]{web88}). Let $\boldsymbol{\phi}=(\phi_{1},\cdots ,\phi_{n})$ be a solution function defined on $\mbox{TU}(N)$, the set of all monotonic games or the set of all superadditive games. Assume that each $\phi_{i}$ satisfies axioms (W1) and (W2), and that $\boldsymbol{\phi}$ satisfies axioms (W5) and (W6). Then, we have
\[\phi_{i}(v)=\sum_{S\subseteq N\setminus\{i\}}\frac{|S|!(|N|-|S|-1)!}{|N|!}\cdot\left [v(S\cup\{i\})-v(S)\right ]. \sharp\]

If we replace the linearity axiom (W1) with the transfer axiom (W4), we obtain an analogous result characterizing the Shapley value on the set of all simple games, the set of all monotonic games and the set of all simple and super-additive games. Let us remark that Derks \cite{der05} present an alternative proof for the characterization of the random order values (Weber \cite[p.118]{web88}).

Probabilistic Values for Multi-Choice Games.

Now, we want to consider the Weber set ${\cal W}(v)$ of a multi-choice game $(N,v)$. We first define the marginal vectors of a multi-choice game $(N,v)$. Suppose the coalition ${\bf m}=(m_{1},\cdots ,m_{n})$ will be formed step by step starting from the coalition ${\bf 0}=(0,0,\cdots ,0)$, where, in each step, the level of one of the players is increased by $1$. This says that there are $\sum_{i\in N}m_{i}$ steps in this procedure. We define
\[M^{+}=\{(i,j):i\in N,j\in M_{i}\setminus\{0\}\}.\]
An admissible order for $(N,v)$ is a bijection
\[\sigma :M^{+}\rightarrow\left\{1,\cdots ,\sum_{i\in N}m_{i}\right\}\]
satisfying $\sigma (i,j)<\sigma (i,j+1)$ for all $i\in N$ and $j\in\{1,\cdots ,m_{i}-1\}$.
The number of admissible orders for $(N,v)$ is given by
\[\frac{(\sum_{i\in N}m_{i})!}{\prod_{i\in N}m_{i}!}.\]
Given $k\in\{1,\cdots ,\sum_{i\in N}m_{i}\}$, the coalition that is present after $k$ steps according to $\sigma$, denoted by ${\bf s}^{\sigma ,k}$, is given by
\[s_{i}^{\sigma ,k}=\max\{j\in M_{i}:\sigma (i,j)\leq k\}\]
for all $i\in N$, and the {\bf marginal vector} ${\bf w}^{\sigma}$ is defined by
\[w_{ij}^{\sigma}=v({\bf s}^{\sigma ,\sigma (i,j)})-v({\bf s}^{\sigma ,\sigma (i,j)-1})\]
for all $i\in N$ and $j\in M_{i}\setminus\{0\}$. In general, the marginal vectors of a multi-choice game are not necessarily imputations. However, for zero-monotonic mutli-choice games, the marginal vectors are imputations, which will be shown below. (van den Nouweland et al. \cite[p.298-299]{van95}).

A multi-choice game $(N,v)$ is called zero-monotonic when its zero-normalization proposed in Definition \ref{gad20} is monotone, i.e.,
$v_{0}({\bf s})\leq v_{0}({\bf t})$ for all ${\bf s},{\bf t}\in\prod_{i\in N}M_{i}$ with ${\bf s}\leq {\bf t}$.
(van den Nouweland et al. \cite[p.299]{van95})

Proposition. (van den Nouweland et al. \cite[p.299]{van95}). Let $(N,v)$ be a zero-monotonic multi-choice game. Then, for every admissible order $\sigma$, the marginal vector corresponding to $\sigma$ is an imputation of $(N,v)$. $\sharp$

The Weber set ${\cal W}(v)$ of a multi-choice game $(N,v)$ is the convex hull of the marginal vectors of $(N,v)$, i.e.,
\[{\cal W}(v)=\mbox{co}\left\{{\bf w}^{\sigma}:\mbox{$\sigma$ is an admissible order for $v$}\right\}.\]
Let ${\bf x},{\bf y}$ be two payoff vectors. We say that ${\bf x}$ is weakly smaller than ${\bf y}$ if and only if $\sum_{i\in N}X_{is_{i}}\leq\sum_{i\in N}Y_{is_{i}}$, where $X_{ij}$ and $Y_{ij}$ are presented in (\ref{van95eqa}), for all coalition ${\bf s}\in\prod_{i\in N}M_{i}$. Note that this does not imply that $x_{ij}\leq y_{ij}$ for all $i\in N$ and $j\in M_{i}$. The core ${\cal MC}(v)$ of multi-choice game $(N,v)$ is proposed in (\ref{van95d12}). The set ${\cal MC}_{\min}(v)$ of minimal core elements is defined as follows
\[{\cal MC}_{\min}(v)=\left\{{\bf x}\in {\cal MC}(v):\mbox{there is no ${\bf y}\in {\cal MC}(v)$
such that ${\bf y}\neq {\bf x}$ and ${\bf y}$ is weakly smaller than ${\bf x}$}\right\}.\]
A multi-choice game $(N,v)$ is called {\bf convex} if and only if
\[v({\bf s}\vee {\bf t})+v({\bf s}\wedge {\bf t})\geq v({\bf s})+v({\bf t})\]
for all ${\bf s},{\bf t}\in\prod_{i\in N}M_{i}$, where $({\bf s}\wedge {\bf t})_{i}=\min\{s_{i},t_{i}\}$ and $({\bf s}\vee {\bf t})_{i}=\max\{s_{i},t_{i}\}$ for all $i\in N$. (van den Nouweland et al. \cite[p.299-304]{van95})

Theorem. (van den Nouweland et al. \cite[p.300]{van95}). For each multi-choice game $(N,v)$ and each core element ${\bf x}\in {\cal MC}(v)$, there is a vector ${\bf y}$ in the Weber set ${\cal W}(v)$ that is weakly smaller than ${\bf x}$. $\sharp$

Theorem. (van den Nouweland et al. \cite[p.303]{van95}). Let $(N,v)$ be a convex multi-choice game. Then the Weber set ${\cal W}(v)$ is a subset of the core ${\cal MC}(v)$. $\sharp$

\begin{equation}{\label{van95t9}}\tag{5}\mbox{}\end{equation}

Theorem \ref{van95t9}. (van den Nouweland et al. \cite[p.304]{van95}). Let $(N,v)$ be a convex multi-choice game. Then the Weber set ${\cal W}(v)$ is the convex hull of the set ${\cal MC}_{\min}(v)$ of minimal core element. $\sharp$

\begin{equation}{\label{van95t10}}\tag{6}\mbox{}\end{equation}

Theorem \ref{van95t10}. (van den Nouweland et al. \cite[p.305]{van95}). Let $(N,v)$ be a multi-choice game for which the Weber set ${\cal W}(v)$ coincides with the convex hull of the set ${\cal MC}_{\min}(v)$ of minimal core elements. Then the game $(N,v)$ is convex. $\sharp$

From Theorems \ref{van95t9} and \ref{van95t10}, we immediately obtain the following result.

Corollary (van den Nouweland et al. \cite[p.305]{van95}). A multi-choice game is convex if and only if its Weber set coincides with the convex hull of the set of its minimal core elements. $\sharp$

Instead of concentrating on the convex hull of marginal vectors of a multi-choice game, we can also consider the average of the marginal vectors. For the cooperative games, this will give us the Shapley value. Let $(N,v)$ be a multi-choice game. The extended Shapley value $\boldsymbol{\phi}(v)$ is the average of all marginal vectors, i.e., ,
\[\boldsymbol{\phi}(v)=\frac{\prod_{i\in N}m_{i}!}{(\sum_{i\in N}m_{i})!}\cdot\sum_{\sigma}{\bf w}^{\sigma},\]
where the sum is taken over all admissible permutations for $(N,v)$. An interesting question now is if this value does have anything to do with the values that Hsiao and Raghavan \cite{hsi93} defined, starting with axioms that are analogues of axioms that characterize the Shapley value for cooperative games. We found an example of a multi-choice game for which the extended Shapley value does not equal any of the values of Hsiao and Raghavan \cite{hsi93} (van den Nouweland et al. \cite[p.305-306]{van95}).

Semivalues.

A probabilistic value corresponding to a weight system in which coalitions of the same size have equal probability is called a semivalue. This family of solutions is obviously parameterized by the weight systems $\{p^{S}\}_{s=1}^{n}$ satisfying
\[\sum_{s=1}^{n}\left (\begin{array}{c} n-1\\ s-1\end{array}\right )\cdot p^{S}=1\mbox{ and }p^{S}\geq 0.\]
For any cooperaive game $(N,v)$, we define
\[a_{s,i}=\sum_{\{S\subseteq N:|S|=s,i\in S\}}v(S)\]
for all $i\in N$ and $1\leq s\leq n$, where $a_{s,i}$ denotes the total worth which is accumulated over all coalitions with size $s$ and containing player $i$. For the semivalue $\widehat{\boldsymbol{\phi}}$ with coefficients $p_{1},\cdots ,p_{n}$, which is defined in (\ref{ga30}) can be expressed as
\begin{align*}
\widehat{\phi}_{i}(v) & =\sum_{i\in S}p^{S}\cdot\left [v(S)-v(S\setminus\{i\})\right ]\\
& =p_{1}\cdot v(i)+\sum_{s=2}^{n}p^{S}\left [\sum_{\{S\subseteq N:
|S|=s,i\in S\}}v(S)-\sum_{\{S\subseteq N:|S|=s,i\in S\}}v(S\setminus\{i\})\right ]\\
& =p_{1}\cdot a_{1,i}(v)+\sum_{s=2}^{n}p^{S}\left [a_{s,i}(v)-\sum_{\{S\subseteq N:|S|=s-1,i\not\in S\}}v(S)\right ]\\
& =p_{1}\cdot a_{1,i}(v)+\sum_{s=2}^{n}p^{S}\left [a_{s,i}(v)-\sum_{|S|=s-1}v(S)+\sum_{\{S:|S|=s-1,i\in S\}}v(S)\right ]\\
& =p_{1}\cdot a_{1,i}(v)+\sum_{s=2}^{n}p^{S}\left [a_{s,i}(v)+a_{s-1,i}(v)-\frac{1}{s-1}\sum_{j=1}^{n}a_{s-1,j}(v)\right ].
\end{align*}
This shows the following result (Amer et al. \cite[p.183]{ame03}).

Proposition. (Amer et al. \cite[p.183]{ame03}). For the computation of the semivalues of a cooperative game $(N,v)$ only the worths $a_{s,i}(v)$ are needed for $i\in N$ and $1\leq s\leq n$. $\sharp$

We say that two cooperative games $(N,v_{1})$ and $(N,v_{2})$ are inseparable by semivalues,
and write $v_{1}\sim v_{2}$, if and only if $\widehat{\boldsymbol{\phi}}(v_{1})=\widehat{\boldsymbol{\phi}}(v_{2})$ for every semivalue $\widehat{\boldsymbol{\phi}}$ on $\mbox{TU}(N)$. Therefore, the game space $\mbox{TU}(N)$ is divided into equivalence
classes, i.e., the maximal sets of games for which all semivalues attain the same outcome. Semivalues are linear functions on $\mbox{TU}(N)$ such that $v_{1}\sim v_{2}$ if and only if the difference $v_{1}-v_{2}$ attains the zero payoff vector in all semivalues. Consequently, inseparability is directly related to the class of games $(N,v)\in \mbox{TU}(N)$ satisfying $\widehat{\boldsymbol{\phi}}={\bf 0}$ for every semivalue $\widehat{\boldsymbol{\phi}}$ on $\mbox{TU}(N)$. We denote this set by $SK(N)$ and call it the shared kernel, since it equals the intersection of the kernels of all semivalues. Because of the linearity of the semivalues, $SK(N)$ is s linear subspace of $\mbox{TU}(N)$. Given a cooperative game $(N,v)\in \mbox{TU}(N)$, the set of all the semivalues of this game is a convex subset of
$\mathbb{R}^{N}$. Obviously, this allocation set coincides with the corresponding set of any game in the equivalence class of $(N,v)$. An example shows that the converse is not true in general (Amer et al. \cite[p.184]{ame03}).

Proposition. (Amer et al. \cite[p.183]{ame03}). The cooperative game $(N,v)\in \mbox{TU}(N)$ belongs to the shared kernel $SK(N)$ if and only if $a_{s,i}(v)=0$ for all $i\in N$ and $1\leq s\leq n$. $\sharp$

Corollary. (Amer et al. \cite[p.185]{ame03}). Two cooperative games $(N,v_{1})$ and $(N,v_{2})$ are inseparable by semivalue if and only if $a_{s,i}(v_{1})=a_{s,i}(v_{2})$ for all $i\in N$ and $1\leq s\leq n$. $\sharp$

Theorem. (Amer et al. \cite[p.185]{ame03}). The dimension of the shared kernel $SK(N)$ is $2^{n}-n^{2}+n-2$. $\sharp$

For $n=2,3$, the dimension of $SK(N)$ are zero, i.e., all cooperative games are separable by semivalues, whereas, for $n\geq 4$, $SK(N)$ is a linear subspace of $\mbox{TU}(N)$. Let us call the number of coalitions with nonzero worth in a game $(N,v)$ the {\bf caliber} of $(N,v)$. Then we can show that the caliber of a game in the shared kernel $SK(N)$ is either $0$ (the all zero game) or at least $4$.
In the sequel, we consider $n\geq 4$. For a given coalition $S$ in $N$ and players $i,j\in S$ and $k,i\in N\setminus S$, we define the shuffle game $(N,v_{S,i,j,k,l})$ as
\[v_{S,i,j,k,l}=\delta_{S}+\delta_{S\cup\{k,l\}\setminus\{i,j\}}-
\delta_{S\cup\{k\}\setminus\{i\}}-\delta_{S\cup\{l\}\setminus\{j\}},\]
where $\delta_{S}$ is defined by $\delta_{S}(T)=1$ if $T=S$ and $\delta_{S}(T)=0$ otherwise. If $(N,v)\in \mbox{TU}(N)$ is a shuffle game, it is evident that $a_{s,i}(v)=0$ for $i\in N$ and $1\leq s\leq n$ (Amer et al. \cite[p.186]{ame03}).

Without loss of generality, we order the set of players as $N=\{1,2,\cdots ,n\}$. Therefore, we can speak of a last and a first player in a coalitions $S$, which are denoted by $l(S)$ and $f(S)$, respectively. Further, we say that a player is absent in a coalition if he/she is positioned between the first and last player of that coalition but is not a member. For coalitions $S$ with $l(S)\geq |S|+2$, we call the last player, not in $S$, but positioned right before $l(S)$, $f'(S)$, and the second last player $l'(S)$. For these coalitions $S$, i.e., $|S|\geq 2$ and $l(S)\geq |S|+2$, we consider the shuffle game
\[v_{S,f(S),l(S),f'(S),l'(S)}=\delta_{S}+\delta_{S\cup\{f'(S),l'(S)\}\setminus
\{f(S),l(S)\}}-\delta_{S\cup\{f'(S)\}\setminus\{f(S)\}}-\delta_{S\cup\{l'(S)\}\setminus\{l(S)\}}.\]
The choice of this shuffle game is such that we can write a unity game $\delta_{S}$, where coalition $S$ has $2$ or more absent players, as a weighted sum consisting of the shuffle game $v_{S}$ and three unity games corresponding to coalitions with less absent players than in $S$. For a coalition $S$ with only one absent player, and $l(S)\geq |S|+2$, we see that $\delta_{S}$ is a weighted sum consisting of the shuffle game $v^{S}$, the unity game corresponding to the consecutive coalition with cardinality $|S|$ and first player $f(S)+1$ and two unity games corresponding to coalitions with only one absent player but where last player is $l(S)-1$. Since a game is a weighted sum of unity games, we conclude that from the previous arguments that it can be written as a weighted sum of shuffle games and unity games, both corresponding to consecutive coalitions or coalitions $S$ having only one absent player and $l(S)=|S|+1$. In other words, any game $v$ can be written as the sum of a game from the span of the shuffle games and a rest-game $v^{*}$ with the property that $v^{*}(S)\neq 0$ implies that $S$ has no absent players, or only one absent player and last player $|S|+1$ (Amer et al. \cite[p.187]{ame03}).

Theorem. (Amer et al. \cite[p.186]{ame03}). The shared kernel $SK(N)$ is spanned by shuffle games. $\sharp$

Theorem. (Amer et al. \cite[p.188]{ame03}). The shuffle games $v_{S}$ for coalitions $S$ with size $s$ between $2$ and $n-2$, having at least two absent players, or with one absent player and last player equal to $s+2$ or larger, form a basis of the shared kernel. $\sharp$