Cesar Boetius van Everdingen (1616-1678) was a Dutch painter.
The topics are
- Owen (1974) Approach
- Sankaran (1991) Approach
- Arin and Feltkamp (1997) Approach
- Andersen and Lind (1999) Approach
\begin{equation}{\label{a}}\tag{A}\mbox{}\end{equation}
Owen (1974) Approach.
(Owen (1974) \cite{owe74} Approach). Let \(N=\{1,\cdots ,n\}\) denote the set of players. Let \(S_{1},\cdots , S_{2^{n}}\) denote all the coalitions of players in \(N\). An imputation is a vector of payoffs \((x_{1},\cdots ,x_{n})\), where \(x_{j}\) denotes the payoff of player \(j\), \(j\in N\). Let \(X\subset\mathbb{R}_{+}^{n}\) be a polytope denoting the set of all possible imputations. Let \(v(S)\) denote the worth of coalition \(S\) and let \(x(S)\) denote the total payoff of the players in \(S\), i.e., \(x(S)=\sum_{j\in S}x_{j}\). Let \(e(S,x)\) denote the excess of coalition \(S\) under imputation \(s\), i.e., \(e(S,{\bf x})=v(S)-x(S)\). Let \(\Pi\) denote the set of all permutations of order \(2^{n}\). Let \(t\) be a sufficiently large number. Kohlberg’s \cite{koh71,koh72} method of finding the nucleolus is by solving the following linear programming problem:
\[\begin{array}{ll}
\min & z\\
\mbox{sugject to} & {\displaystyle z\geq\sum_{i=1}^{2^{n}}t^{\pi (i)}\cdot
e(S_{i},{\bf x})\mbox{ for all }\pi\in\Pi}\\
& {\bf x}\in X.
\end{array}\]
Kohlberg \cite{koh71} shows that if \(X=\{{\bf x}\in\mathbb{R}_{+}^{n}:\sum_{i=1}^{n}x_{i}\}\), \(t\) must be at least about \(n^{2^{n}}\) in order that the nucleolus be the unique solution to the above problem. This means that under double precision arithmetic, there will be round-off errors even when \(n=4\) (Sankaran \cite{san}).
Kohlberg \cite{koh72} shows that the nucleolus of the game \((N,v)\) over the polyhedral set \(X\) can be expressed as the solution of a linear program. In effect, it is shown that the nucleolus minimizes the maximum of the \((2^{n})!\) functions
\[\sum_{k=1}^{2^{n}}\alpha^{k}\cdot E(S_{k},{\bf x}),\]
where \(n=|N|\), \(S_{1},\cdots ,S_{2^{n}}\) is a permutation of the \(2^{n}\) subsets of \(N\), \(e(S_{k},{\bf x})\) is the excess of the coalition \(S_{k}\)
\[e(S_{k},{\bf x})=v(S_{k})-\sum_{i\in S_{k}}x_{i}\]
and \(0<\alpha <\beta\), where \(\beta\) is a small positive number, which depends on \(|N|\) and the polyhedral set \(K\), but not on the particular \(v\) chosen. (If, in particular, \(X\) is the set of imputations for the game \(v\), then it suffices that \(\alpha\) be chosen smaller than the smallest balancing coefficient for a full complement of balanced collections in \(N\).) (Owen \cite{owe74}).
Assuming \(v\) to be in \((0,1)\)-normalization, we might let \(K\) be the set of all imputations, i.e., all nonnegative vectors \((x_{1},\cdots ,x_{n})\) whose components have sum \(1\). Thus the nucleolus \({\bf x}^{*}\) is the solution of the program
\[\begin{array}{ll}
\min & \lambda\\
\mbox{subject to} & {\displaystyle \lambda\geq\sum_{k=1}^{2^{n}}
\alpha^{k}\cdot E(S_{k},{\bf x})
\mbox{ for all \((2^{n})!\) permutations }S_{1},\cdots ,S_{2^{n}}}\\
& x_{1}+\cdots +x_{n}=1\\
& x_{i}\geq 0\mbox{ for all }i\in N.
\end{array}\]
From the definition of the excess \(e(S,{\bf x})\), we see that the constraints \(\lambda\geq\sum\alpha^{k}\cdot E(S_{k},{\bf x})\) is linear in \({\bf x}\). Thus the above program is a linear program, and presumably can be solved by the simplex algorithm or some other such methods. There is, unfortunately, one problem with this, namely the large number of constraints. In fact, there is one constraint \(\lambda\geq\sum\alpha^{k}\cdot E(S_{k},{\bf x})\) for each permutation of the subsets of \(N\). Since there are \(2^{n}\) subsets, this gives \((2^{n})!\) permutations and a like number of constraints. In all, the program has then \(n\) variables and \((2^{n})!+1\) constraints (apart from the nonnegativity conditions \(x_{i}\geq 0\)). For \(n=4\), this means a total of \(16!+1=2.1\times 10^{13}\) constraints. Even admitting that many of the permutations can be eliminated out of hand, this is clearly beyond the scope of even the largest computers available.
It is, however, possible to reduce the size of the program to more manageable proportions. Let \(\{T_{1},T_{2},\cdots ,T_{2^{n}}\}\) be some fixed ordering of the subsets of \(N\). There we are looking for
\[\min_{\bf x}\max_{\pi}\sum_{k=1}^{2^{n}}\alpha^{k}\cdot e(T_{\pi (k)},{\bf x}),\]
where \({\bf x}\) is taken over the set of all imputations and \(\pi\) over the set of all permutations on \(2^{n}\) elements. We may represent \(\pi\) by the permutation matrix \(P=(p_{kl})\), where
\[p_{kl}=\left\{\begin{array}{ll}
1, & \mbox{if \(\pi (k)=l\)}\\ 0, & \mbox{otherwsie}
\end{array}\right .\]
Therefore, we have
\[e(T_{\pi (k)},{\bf x})=\sum_{l=1}^{2^{n}}e(T_{l},{\bf x})\cdot P_{kl}\]
and we are looking for \({\bf x}\) to minimize the expression
\begin{equation}{\label{own74eq7}}\tag{1}
\max_{P}\sum_{k=1}^{2^{n}}\sum_{l=1}^{2^{n}}\alpha^{k}\cdot e(T_{l},{\bf x})\cdot P_{kl}
\end{equation}
where the maximum is taken over all permutation matrices \(P\). We note that this expression is linear in \(P\), and so the maximum will be the same if we allow \(P\) to range over the set of all doubly stochastic matrices, i.e., the expression (\ref{own74eq7}) is the same as
\[\begin{array}{ll}
\max & {\displaystyle \sum_{k=1}^{2^{n}}\sum_{l=1}^{2^{n}}
\alpha^{k}\cdot E(T_{l},{\bf x})\cdot P_{kl}}\\
\mbox{subject to} & {\displaystyle \sum_{k=1}^{2^{n}}p_{kl}=1\mbox{ for each }l}\\
& {\displaystyle \sum_{l=1}^{2^{n}}p_{kl}=1\mbox{ for each }k}\\
& p_{kl}\geq 0\mbox{ for each }k,l.
\end{array}\]
The above original program has now been replaced by the min-max problem
\[\begin{array}{ll}
{\displaystyle \min_{\bf x}\max_{P}} & {\displaystyle \sum_{k=1}^{2^{n}}\sum_{l=1}^{2^{n}}
\alpha^{k}\cdot E(T_{l},{\bf x})\cdot P_{kl}}\\
\mbox{subject to} & {\displaystyle \sum_{k=1}^{2^{n}}p_{kl}=1\mbox{ for each }l}\\
& {\displaystyle \sum_{l=1}^{2^{n}}p_{kl}=1\mbox{ for each }k}\\
& p_{kl}\geq 0\mbox{ for each }k,l\\
& x_{1}+\cdots +x_{n}=1\\
& x_{i}\geq 0\mbox{ for each }i.
\end{array}\]
This is much smaller than the original program, as it has only \(2^{n+1}+1\) constraints (apart from the nonegativity constraints). However, it is not a pure minimization problem, but a min-max problem. Applying duality to the maximization part, we will have the equivalent program
\[\begin{array}{ll}
\min & {\displaystyle \sum_{k=1}^{2^{n}}u_{k}+\sum_{l=1}^{2^{n}}w_{l}}\\
\mbox{subject to} & u_{k}+w_{l}\geq\alpha^{k}\cdot E(T_{l},{\bf x})
\mbox{ for each }k,l\\
& x_{1}+\cdots +x_{n}=1\\
& x_{i}\geq 0\mbox{ for each }i.
\end{array}\]
This is a pure minimization program equivalent to the original program. It has only \(2^{n+1}+n\) variables and \(4^{n}+1\) constraints. In particular, for \(n=4\), it will have \(36\) variables and \(257\) constraints.
\begin{equation}{\label{b}}\tag{B}\mbox{}\end{equation}
Sankaran (1991) Approach
(Sankaran (1991) \cite{san} Approach). We will present a new procedure for finding the nucleolus of a cooperative game with side payments as defined by Schmeidler \cite{sch69}. Kohlberg \cite{koh72} and Owen \cite{owe74} illustrate how the nucleolus can be found by solving a single minimization LP when the imputation sapce is polytope. Owen \cite {owe74} shows how the nucleolus may be found by solving solving an LP with \(2^{n+1}+n\) variables and \(4^{n}\) constraints, not including the constraints that define the polytope of imputations. Kohlberg’s approach is attractive because it requires the solution of only one LP. However the coefficients in the LP have a very wide range even for problems with \(n=3\) or \(4\). This is likely to cause severe errors due to finite precision and round-off when the LP is solved by computer. Hence the method may be accurate only for very small problems. Maschler et al. \cite{mas79} give another method of finding the nucleolus by giving a constructive definition of the lexicographic center of a cooperative game and by showing the equivalence of the lexicographic center and the nucleolus. Their approach requires solving a sequence of minimization problems. When the imputation space is polytope, these problems are LP’s. The coefficients in the constraints are \(-1,0,1\), but the number of LP’s to be solved is \(O(4^{n})\). Here we show how the lexicographic center may be found by solving a sequence of \(O(2^{n})\) LP’s in which the constraint coefficients are \(-1,0,1\). Maschler \cite{mas79} use the following procedure to find the lexicographic center.
- Step 1. Let \(X^{0}=X\) be the set of all imputations and \(I^{0}=\{1,\cdots ,2^{n}\}\). Set \(r\leftarrow 1\).
- Step 2. Recursively define the following
\begin{align*}
\epsilon^{r} & =\min_{{\bf x}\in X^{r-1}}\max_{i\in I^{r-1}}e(S_{i},{\bf x})\\
X^{r} & =\left\{{\bf x}\in X^{r-1}:e(S_{i},{\bf x})\leq\epsilon^{r}\mbox{ for all }i\in I^{r-1}\right\}\\
I^{r} & =\left\{i\in I^{r-1}:e(S_{i},{\bf x})=\epsilon^{r}\mbox{ for all }{\bf x}\in X^{r}\right\}\\
I^{r} & =I^{r-1}\setminus I_{t}(???).
\end{align*} - Step 3. If \(I^{r}=\emptyset\), then set \(R=r\) and stop; else \(set r\leftarrow r+1\) and go to Step 2.
The above definition can be used constructively for finding the lexicographic center. Since \(X\) is a polytope, so is \(X^{r}\) for all \(r=0,\cdots ,R\). Then the lexicographic center may be found by solving a sequence of LP’s. In the \(r\)th iteration in the above procedure, the following LP may be solved in order to find \(\epsilon^{r}\):
\[\begin{array}{ll}
\min & \epsilon\\
\mbox{subject to} & {\bf x}\in X^{r-1}\\
& \epsilon\geq e(S_{i},{\bf x})\mbox{ for all }i\in I^{r-1}.
\end{array}\]
To ascertain \(I_{r}\), one may consider coalition \(S_{i}\) by turn for each \(i\in I^{r-1}\) and solve the following problem for that coalition
\[\begin{array}{ll}
\min & e(S_{i},{\bf x})\\ \mbox{subject to} & {\bf x}\in X^{r}.
\end{array}\]
Now we describe the computational procedure. Let \(\bar{\bf x}\) denote the nucleolus. Let \(V(P)\) denote the optimal objective value of problem (P). Now consider the following procedure.
- Step 1. Set \(r\leftarrow 1\) and \(\tilde{I}^{0}\leftarrow I\).
- Step 2. Solve the following min-max problem:.
\[\begin{array}{lll}
(MM) & \min & u\\ & \mbox{subject to} & u\geq e(S_{i},{\bf x})\mbox{ for all }
i\in\tilde{I}^{0}\\ && {\bf x}\in X
\end{array}\]
Let \({\bf x}^{0}\) be an optimal solution and set \(c_{1}\leftarrow V(MM)\). - Step 3. Set \(\tilde{X}^{1}\leftarrow X\cap\{{\bf x}:e(S_{i},{\bf x})\leq c_{1}\mbox{ for all }i\in\tilde{I}^{0}\}\).
- Step 4. If \(|I^{r-1}|=1\), then set \(m(r)\leftarrow 1\) and \({\bf x}^{r}\leftarrow {\bf x}^{r-1}\), and go to step 9; else go to step 5.
- Step 5. Set \(t\leftarrow 1\).
- Step 6. Sovle the following problem:
\[\begin{array}{lll}
(LM(r,t)) & \min & z\\
& \mbox{subject to} & {\displaystyle \mbox{for all \(\bar{I}\subseteq\tilde{I}^{r-1}\)
such that }|\bar{I}|=t+1,z\geq\sum_{i\in\bar{I}}e(S_{i},{\bf x})}\\
&& {\bf x}\in\tilde{X}^{r}
\end{array}\] - Step 7. If \(V(LM(r,t))<(t+1)\cdot c_{r}\), then go to step 8; else if \(t+1=|\tilde{I}^{r-1}|\), then go to step 8; else set \(t\leftarrow t+1\). Go to step 6.
- Step 8. Let \({\bf x}^{r}\) be optimal solution of problem \((LM(r,t))\). If \(V(LM(r,t))<(t+1)\cdot c_{r}\), then set \(c_{r+1}\leftarrow V(LM(r,t))-t\cdot c_{r}\) and \(m(r)\leftarrow t\); else set \(m(r)\leftarrow |\tilde{I}^{r-1}|\).
- Step 9. Set \(C_{r}\leftarrow \{i\in\tilde{I}^{r-1}:e(S_{i},{\bf x}^{r})=c_{r}\}\).
- Step 10. If \(m(r)=|\tilde{I}^{r-1}|\), then set \(\widehat{\bf x}\leftarrow {\bf x}^{r}\) and \(\widehat{R}\leftarrow r\) and stop; else go to step 11.
- Step 11. Set \(\tilde{I}^{r}\leftarrow\tilde{I}^{r-1}\setminus C_{r}\), \(\bar{X}^{r+1}\leftarrow \bar{X}^{r}\cap\{{\bf x}:e(S{i},{\bf x})\leq c_{r+1}\mbox{ for all }i\in\tilde{I}^{r}\}\) and \(r\leftarrow r+1\). Go to step 4.
Theorem. (Sankaran \cite{san}) The payoff vector \(\widehat{\bf x}\) obtained by the above computational procedure is the nucleolus \(\bar{\bf x}\). \(\sharp\)
Let \(|I_{r}|\) be denoted by \(n(r)\). In the \(r\)th pass of the above procedure, when \(1\leq r<\widehat{R}\), the number of LPs solved is \(n(r)\). The number of LPs solved in the \(\widehat{R}\)th pass is \(n(\widehat{R})-1\). Hence the total number of LPs solved (including the problem (MM)) is \(\sum_{r=1}^{\widehat{R}}n(r)=2^{n}\). Besides the constraints defining \(X\), the number of constraints in problem
(LM(r,t)) equals
\[\frac{|\tilde{I}^{r-1}|!}{(t+1)!\cdot(|\tilde{I}^{r-1}|-t-1)!}+2^{n}.\]
The number of columns in each of these LPs is \(n+1\). Now we show how the number of constraints in these LPs can be reduced. Let \(\Omega_{t}^{r}\) be the set of all combinations of size \(t+1\) of coalitions in \(\tilde{I}^{r-1}\). A combination is denoted by \(\{\mu (i)\}_{i\in\tilde{I}^{r-1}}\), where \(\mu (i)\) is \(1\) if coalition \(i\) is in the combination, \(0\) else. Problem \((LM(r,t))\) can be rewritten as follows
\begin{eqnarray*}
& {\displaystyle \min_{{\bf x}\in\tilde{X}^{r}}\max_{\mu\in\Omega_{t}^{r}}} &
\sum_{i\in\tilde{I}^{r-1}}\mu (i)\cdot E(S_{i},{\bf x})\\
& \mbox{subject to} & \sum_{i\in\tilde{I}^{r-1}}\mu (i)=t+1\\
&& \mu(i)\in\{0,1\}\mbox{ for all }i\in\tilde{I}^{r-1}.
\end{eqnarray*}
It is easy to see that without loss, the constraint \(\mu(i)\in\{0,1\}\mbox{ for all }i\in\tilde{I}^{r-1}\) may be replaced by \(0\leq\mu(i)\leq 1\mbox{ for all }i\in\tilde{I}^{r-1}\).
This is a saddle-point problem with \(|\tilde{I}^{r-1}||n\) variables and \(2^{n}+1\) constraints (not including the constraints that define the polytope \(X\) and the upper bounding constraints on \(\mu (i)\)). Applying duality to the maximization part (in a manner similar to Owen \cite{owe74})), we have the following problem
\[\begin{array}{ll}
\min & {\displaystyle (t+1)\alpha +\sum_{i\in\tilde{I}^{r-1}}\beta (i)}\\
\mbox{subject to} & \alpha +\beta (i)\geq e(S_{i},{\bf x})\mbox{ for all }i\in\tilde{I}^{r-1}\\
& e(S_{i},{\bf x})\leq c_{k}\mbox{ for all }k=1,\cdots ,r-1\mbox{ and for all }i\in C_{k}\\
& e(S_{i},{\bf x})\leq c_{r}\mbox{ for all }i\in\tilde{I}^{r-1}\\
& \beta (i)\geq 0\mbox{ for all }i\in\tilde{I}^{r-1}\\
& {\bf x}\in X.
\end{array}\]
Besides the constraints that define \(X\), there are \(|\tilde{I}^{r-1}|+2^{n}\) constraints in the above problem. The number of variables is \(|\tilde{I}^{r-1}|+1+n\). Hence the number of constraints is \(O(2^{n})\) and the number of variables is \(O(2^{n})\) as contrasted with \(O(4^{n})\) and \(O(2^{n})\) respectively in Owen’s problem.
Now we illustrate the procedure for \(n=5\). The set of imputation is \(X=\{{\bf x}\in\mathbb{R}_{+}^{5}:\sum_{j=1}^{n}x_{j}=1\}\). This game has an empty core. \(\epsilon^{1}=0.335\), \(V(LM(1,1))=0.71=2*0,355\). Hence \(LM(1,1)\) is solved. \(V(LM(1,2))=1.0355<3*0.355\). \(\{4,5\}\) and \(\{1,2,3\}\) attain an excess of \(0.355\) in \(V(LM(1,2))\). So \(I_{1}=\{15,16\}\) and \(\epsilon^{2}=1.035-0.71=0.325\). Now \(LM(2,1)\) is solved. \(V(LM(2,1))=0.65=2*0.325\). Hence \(LM(2,2)\) is solved. \(V(LM(2,2))=0.975=3*0.325\). Therefore \(LM(2,3)\) is solved. Since \(V(LM(2,3))=1.300=4*0.325\), \(LM(2,4)\) is solved. \(V(LM(2,4))=1.6025<5*0.325\). \(\{1,2\},\{1,4\},\{2,4\}\) and \(\{3,5\}\) attain an excess of \(0.325\) in \(LM(2,4)\) and so \(I_{2}=\{6,8,11,14\}\). \(\epsilon^{3}=1.6025-4*0.325=0.3025\). Proceeding in this manner, the nucleolus \(\bar{\bf x}\) is found to be \((0.0975,0.275,0.1,0.1375,0.3875)\).
\begin{equation}{\label{c}}\tag{C}\mbox{}\end{equation}
Arin and Feltkamp (1997) Approach
Arin and Feltkamp (1997) \cite{ari97} Approach
Computing the Nucleolus of Veto-Rich Games.
Begin by assigning zero to those players \(j\) such that there is a coalition \(S\) containing \(i\) but not \(j\), that satisfies \(v(S)\geq v(N)\). Call the set of these players \(A_{0}\). Then iteratively, at each step \(t\), look for the coalitions \(S\) containing \(i\), that still have players in their complement whose payoffs have not yet been assigned. Among these admissible coalitions, select those coalitins that minimize the amount
\[\frac{v(N)-v(S)-x(A_{t-1}\setminus S)}{|A_{t-1}^{c}|+1}.\]
The idea is that for any such minimizing coalition \(S\), the amount \(v(N)-v(S)-x(A_{t-1}\setminus S)\) remains to be divided, and dividing it equally between the not yet allocated players outside \(S\) and the coalition \(S\) itself, will equate the complaints of the veto player \(i\) against the players outside \(S\) that have just been allocated and the complaints of those players against player \(i\). Let \(A_{t}\) equal the set of players whose payoffs have been determined in step \(t\) or earlier. When all other players have been assigned payoffs in this way, the veto player \(i\) obtains the rest. We now give a more formal description: the input is a veto-rich game \((N,v)\) with a veto player \(i\) and the output is an allocation, the nucleolus of the game.
Stage 0. Start with the stage \(t=0\). Define the set of players whose payoff is allocated in stage \(0\):
\[A_{0}=\left\{j\in N\setminus\{i\}:\mbox{there exists a \(S\subset N\) such that \(i\in S\) and \(v(S)\geq v(N)\)}\right\}.\]
Put \(q_{0}=0\) and allocate \(x_{j}=q_{0}=0\) for all \(j\in A_{0}\).
Stage 1. While there is a player that is not the veto player \(i\) and whose payoff has not been allocated, do steps 1(i) to 1(iv).
- (i) Put \(t\leftarrow t+1\).
- (ii) Given the set \(A_{t-1}\) of players whose payoffs have been allocated before stage \(t\), call a coalition \(S\) {\bf admissible at stage} \(t\) is \(S\) contains the veto player \(i\) and there remain players in \(N\setminus S\) to be allocated. For all admissible coalitions \(S\), recall
\[q_{t}(S)=\frac{v(N)-v(S)-x(A_{t-1}\setminus S)}{|A_{t-1}^{c}\setminus S| +1}\] - (iii) Define the payoff obtained by players whose payoff is allocated at stage \(t\)
\[q_{t}:\min\{q_{t}(S):S\mbox{ admissible at stage \(t\)}\},\]
the set of players who are not going to be allocated during this stage
\[S_{t}=\cap\arg\min\{q_{t}(S):S\mbox{ admissible at stage \(t\)}\}\]
and the set of players allocated at or before stage \(t\)
\[A_{t}=A_{t-1}\cup S_{t}^{c}=A_{t-1}\cup (A_{t-1}^{c}\setminus S_{t}).\] - (iv) Allocate \(x_{j}=q_{t}\) for all \(j\in A_{t}\setminus A_{t-1}=A_{t-1}^{c}\setminus S_{t}\).
Stage 2. Allocate \(x_{i}=v(N)-x(N\setminus\{i\})\) to veto player \(i\).
Stage 3. Define \(x=x(N,v)\) as the vector with coordinates \((x_{j})_{j\in N}\).
In each stage (except maybe in stage \(0\)), at least one player is allocated, so at the latest after stage \(|N|\), each player has been allocated a payoff.
Proposition. (Arin and Feltkamp \cite{ari97}). If the algorithm allocated a payoff to player \(k\) before player \(j\), then \(x_{k}\leq x_{j}\) unless \(j=i\) and \(v(i)<0\). \(\sharp\)
Theorem. (Arin and Feltkamp \cite{ari97}). The allocation \({\bf x}\) defined in the algorithm is the nucleolus \({\cal N}_{0}(v)\) is defined in \((\ref{ga55})\). \(\sharp\)
Proposition. (Arin and Feltkamp \cite{ari97}). For a veto-rich game \((N,v)\) with veto player \(i\), the following are equivalent
- (a) \(Core(v)\neq\emptyset\).
- (b) \(v\) satisfies \(v(S)\leq v(N)\) for all \(S\subset N\) with \(i\in S\). \(\sharp\)
\begin{equation}{\label{d}}\tag{D}\mbox{}\end{equation}
Andersen and Lind (1999) Approach.
Andersen and Lind (1999) \cite{and99} Approach
The NTU-Shapley Value.
Let \(N=\{1,\cdots ,n\}\) be a finite set of players. A coalition is a non-empty subset of \(N\). Let \(M=2^{N}\setminus\{\emptyset\}\) denote the set of all coalitions. For every \({\bf x}\in\mathbb{R}^{N}\), the restriction of \({\bf x}\) to \(\mathbb{R}^{S}\) for \(S\subset N\) is denoted by \({\bf x}^{S}\). Moreover, for all \({\bf x},{\bf y}\in\mathbb{R}^{N}\), define \({\bf x}*{\bf y}\in\mathbb{R}^{N}\) by \(({\bf x}*{\bf y})_{i}=x_{i}y_{i}\) for all \(i\in N\). Finally, for an arbitrary \(p\times q\) matrix \(D\) let \(d_{i}\) denote the \(i\)th column and for each \(K\subset\{1,\cdots ,q\}\), let \(D_{K}=(d_{i})_{i\in K}\).
A cooperative game with non-transferable utility (NTU game) is a pair \((N,V)\), where \(N\) is the of players and \(V\) is a mapping which for each coalition \(S\), defines a characteristic set \(v^{S}\) satisfying
- (a) \(v^{S}\) is nonempty and closed subset of \(\mathbb{R}^{S}\).
- (b) \(v^{S}\) is comprehensive, i.e., if \({\bf x},{\bf y}\in\mathbb{R}^{S}\), \({\bf x}\in v^{S}\) and \({\bf x}\geq {\bf y}\), then \({\bf y}\in v^{S}\).
- (c) The set \(\{{\bf y}\in v^{S}:{\bf y}\geq {\bf x}\}\) is compact for all \({\bf x}\in\mathbb{R}^{S}\).
The characteristic set \(v^{S}\) is interpreted as the set of outcomes the players in \(S\) can guarantee themselves without cooperating with the players in \(N\setminus S\). In particular,an NTU game \((N,V)\) is called a game with transferable utility (TU game) when the characteristic set for each coalition \(S\) takes the form
\[v^{S}=\left\{{\bf x}\in\mathbb{R}^{S}:\sum_{i\in S}x_{i}\leq v(S)\right\}\]
where \(v:2^{N}\rightarrow\mathbb{R}\) satisfies \(v(\emptyset )=0\). A TU game is fully described by the set of players \(N\) and the characteristic function \(v\), and is denoted by the tuple \((N,v)\).
Let \({\cal G}\) denote the class of NTU games and let \({\cal G}^{TU}\) denote the class of TU games. Moreover, let \({\cal G}’\subset {\cal G}\). A solution concept \(\sigma\) on \({\cal G}’\) is a correspondence that associates with each game \((N,V)\in {\cal G}’\) a nonempty subset \(\sigma (N,V)\) of \(V_{N}\). A {\bf solution} on \({\cal G}’\) is a function which associates with each game in \({\cal G}’\) a unique point in \(V_{N}\). A solution concept \(\sigma\) on \({\cal G}’\) is said to be efficient if for every game \((N,V)\in {\cal G}’\) and every \({\bf x}\in\sigma (N,V)\), there does not exist any \({\bf y}\in V_{N}\) such that \({\bf y}\geq {\bf x}\) and \({\bf y}\neq {\bf x}\).
Probably the best known solution on \({\cal G}^{TU}\) is the Shapley value \(\mbox{\boldmath \)latex \phi$}$ which was introduced and given an axiomatic characterization in Shapley (1953). Let \((N,v)\in {\cal G}^{TU}\). The Shapley value of \((N,v)\) is defined as
\[\phi_{i}(v)=\sum_{S\subset N,i\in S}\frac{(n-|S|)!\cdot(|S|-1)!}{n!}\cdot\left (v(S)-v(S\setminus\{i\})\right )\]
for all \(i\in N\). The NTU-Shapley value was introduced by Shapley (1969) as a generalization of the Shapley value to a larger class of games.
Let \(\Lambda =\{\mbox{\boldmath \)latex \lambda$}\in\mathbb{R}^{N}:\mbox{\boldmath \(\lambda\)}>{\bf 0},\sum_{i=1}^{n}\lambda_{i}=1\}$ and let \((N,V)\in {\cal G}\). Then for each \(\mbox{\boldmath \)latex \lambda$}\in\Lambda$
and each coalition \(S\), let
\begin{equation}{\label{and99eq1}}\tag{2}
v_{\mbox{\boldmath \(\lambda\)}}(S)=\max\{\mbox{\boldmath \(\lambda\)}^{S}{\bf x}:{\bf x}\in v^{S}\}.
\end{equation}
Secondly, let \(N(V)=\{\mbox{\boldmath \)latex \lambda$}\in\Lambda :v_{\mbox{\boldmath \(\lambda\)}}(S)<+\infty\mbox{ for all }S\in M\}$. Now \({\bf x}\in V_{N}\) is called an NTU-Shapley value of the game \((N,V)\in {\cal G}\) if and only if there exists a vector \(\mbox{\boldmath \)latex \lambda$}\in N(V)$ satisfying
\begin{equation}{\label{and99eq2}}\tag{3}
\mbox{\boldmath \(\lambda\)}*{\bf x}=\mbox{\boldmath \(\phi\)} (v_{\mbox{\boldmath \(\lambda\)}}).
\end{equation}
The comparison weight \(\mbox{\boldmath \)latex \lambda$}$ is introduced in order to make the utilities of the distinct players comparable and (\ref{and99eq2}) has to be satisfied such that the value is equitable in some sense. It can be shown (ref. Aumann \cite{aum85} and Kern \cite{ker}) that an NTU-Shapley value exists if \(N(V)\) is nonempty, \(v_{\mbox{\boldmath \)latex \lambda$}}$ is continuous on \(N(V)\) for all coalitions and the characteristic sets satisfy a weak type of monotonicity.
Let \({\cal G}^{S}\) denote the subset of NTU games for which an NTU-Shapley value exists. Moreover, for every game \((N,V)\in {\cal G}^{S}\), let \(\mbox{\boldmath \)latex \psi$}(N,V)$ denote the set of NTU-Shapley value of the game. We will refer to \(\mbox{\boldmath \)latex \psi$}$ as the NTU-Shapley value. Notice that \(\mbox{\boldmath \)latex \psi$}$ is an efficient solution concept on \({\cal G}^{S}\).
In contrast to Shapley’s original definition, we have not allowed vanishing weights. The reason for doing so is threefold. First, the use of positive weights guarantees that the NTU-Shapley value is efficient. Secondly, the interpretation of a vanishing weight is muddled, and thirdly, zero weights were originally only introduced in order to prove existence. Moreover, our definition is identical with the definitions given in Aumann \cite{aum85} and Kern \cite{ker}.
Consider the multiple objective linear program
\[\begin{array}{ll}
\max & {\bf c}^{i}{\bf x}\mbox{ for }i=1,\cdots ,n\\
\mbox{subject to} & A{\bf x}\leq {\bf b}\\
& {\bf x}\geq {\bf 0}
\end{array}\]
where \(A\) is an \(r\times l\) matrix of full rank, \({\bf b}\in\mathbb{R}^{r}\), \({\bf c}^{i}\in\mathbb{R}^{l}\) for \(i=1,\cdots ,n\) and \({\bf x}\in\mathbb{R}^{l}\). We assume that \(\max\{{\bf c}^{i}{\bf x}:A{\bf x}\leq {\bf b},{\bf x}\geq {\bf 0}\}<+\infty\) for \(i=1,\cdots ,n\). We want to asociate an NTU game with each MOLP and here we follow Christensen et al. \cite{chr96}.
Each player is associated with an objective function, so let \(N=\{1,\cdots ,n\}\) denote the set of players. Mext, let \(S\in M\) and let the
characteristic set \(v^{S}\) be defined by $latex v^{S}=Z_{S}-\mathbb{R}_{+}^{S}=\{{\bf x}\in\mathbb{R}^{S}:\mbox{there exists }
{\bf z}\in Z_{S}\mbox{ such that }{\bf x}\leq {\bf z}\}$ where \(Z_{S}=\{{\bf z}\in\mathbb{R}^{S}:{\bf z}=C^{S}{\bf x},A{\bf x}\leq {\bf b},{\bf x}\geq {\bf 0}\}\) and \(\mathbb{R}_{+}^{S}\) denotes the nonnegative orthant of the Euclidean space \(\mathbb{R}^{S}\). \(C^{S}\) is the \(|S|\times l\) matrix where the rows contain the coefficients of the objective functions associated with the players in \(S\). The players are listed in increasing index order. It is easy to verify that, for all coalitions, the sets \(v^{S}\) are in fact characteristic sets. For any arbitrary coalition \(S\), i.e., for a subset of the objective functions, the characteristic set \(v^{S}\) coincides with the lower comprehensive hull of the feasible region of the criterion space projected on \(\mathbb{R}^{S}\).
Let \({\cal G}^{MOLP}\) denote the set of games defined by multiobjective linear programs. It follows directly from Kern \cite{ker} that there exists at least one NTU-Shapley value of every game in \({\cal G}^{MOLP}\).
Computation of the NTU-Shapley Value.
Let \((N,v)\in {\cal G}^{TU}\) ith \(n=|N|\). Assume that the characteristic function value for each coalition can be obtained in unit time. Then Faigle and Kern \cite{fau92} have shown that the computation of the Shapley value for a given player requires at least \(2^{n-1}\) operations. A modification of their proofs implies that any algorithm which is able to compute the Shapley value of every TU game will have a time-complexity of at least \(O(n2^{n})\). For the computation of NTU-Shapley values of games in \({\cal G}^{MOLP}\), the structure of the characteristic sets can be utilized.
The bicriterion case.
We describe an algorithm to determine all NTU-Shapley values of games in \({\cal G}^{MOLP}\) with two players (objective functions). The algorithm is based on the simplex method. Let \({\bf z}^{*}=(z_{1}^{*},z_{2}^{*})\) denote the ideal point. That is, \(z_{i}^{*}=\max\{{\bf c}^{i}{\bf x}:A{\bf x}\leq {\bf b},{\bf x}\geq {\bf 0}\}\) for \(i=1,2\). Also let \({\bf z}\in Z_{\{1,2\}}\) (the feasible set). Now it follows from (\ref{and99eq1}) and (\ref{and99eq2}) that \({\bf z}\) is an NTU-Shapley value if and only if there exists a weight
$\mbox{\boldmath \(\lambda\)}\in\Lambda$ such that
\begin{equation}{\label{and99eq4}}\tag{4}
{\bf z}\in\arg\max\{\mbox{\boldmath \(\lambda\)}{\bf y}:{\bf y}\in V_{N}\}
\end{equation}
and
\begin{equation}{\label{and99eq5}}\tag{5}
\lambda_{i}z_{i}=\frac{1}{2}\lambda_{i}z_{i}^{*}+\frac{1}{2}(\lambda_{1}z_{1}+
\lambda_{2}z_{2}-\lambda_{j}z_{j}^{*})\mbox{ for }i,j=1,2\mbox{ and }
i\neq j.
\end{equation}
Notice that (\ref{and99eq5}) can be rewritten as follows: \(\lambda_{1}(z_{1}^{*}-z_{1})=\lambda_{2}(z_{2}^{*}-z_{2})\). It follows that directly from (\ref{and99eq4}) that an NTU-Shapley value \({\bf z}\) belongs to a facet of \(Z_{\{1,2\}}\) (it might be an extreme point). Also, it can be seen that the comparison weights \(\mbox{\boldmath \)latex \lambda$}$ can be only one of two types, namely normals to a facet of \(Z_{\{1,2\}}\) (from (\ref{and99eq4})) or a vector from an extreme point of \(Z_{\{1,2\}}\) to the ideal point $latex {\bf z}^{*}=(z_{1}^{*},
z_{2}^{*})$ (from (\ref{and99eq5}) and the fact that \(\lambda_{1}+\lambda_{2}=1\)). One of the ideas behind the algorithm is to check all relevant comparison weights.
The algorithm below gives the details of the procedure to determine all NTU-Shapley values in the case of two criteria. The algorithm uses standard simplex notation. For convenience let us review the notation: \(S\) and \(R\) denotes the indices for the basic variables and non-basic variables, respectively, corresponding to the present extreme points. \(B=A_{S}\) is the basis matrix corresponding to the present extreme point. \(B\) is the columns in \(A\) corresponding to the indices in \(S\). \(N=A_{R}\) is the present non-basic matrix. \(W=C_{S}B^{-1}N-C_{R}\) is the reduced cost matrix. This is the present value of \(C=C_{\{1,2\}}\).
Algorithm. Compute all NTU-Shapley values in the bicriterion case. Let \((N,V)\in {\cal G}^{MOLP}\) with \(|N|=2\).
Initialization Step.
- 1. Compute the ideal point \({\bf z}^{*}=(z_{1}^{*},z_{2}^{*})\), i.e., for \(i=1,2\) solve
\begin{equation}{\label{and99eq6}}\tag{6}
\begin{array}{llll}
z_{i}^{*} & = & \max & {\bf c}^{i}{\bf x}\\
&& \mbox{subject to} & A{\bf x}\leq {\bf b}, {\bf x}\geq {\bf 0}.
\end{array}
\end{equation} - 2. Let \(i=2\). Choose an optimal basis \(B\) for program (\ref{and99eq6}). Compute the reduced cost matrix
\[W=\left [\begin{array}{c}
w_{j}^{1}\\ w_{j}^{2}
\end{array}\right ]_{j\in R}=C_{S}B^{-1}N-C_{R}.\]
If there exists a \(j\in R\) such that \(w_{j}^{1}<0\) and \(w_{j}^{2}=0\), let variable \(x_{j}\) enter the basis and update \(R,S,B,N,W\).
Let \({\bf x}^{1}\) denote the optimal solution. If \(z_{1}^{*}={\bf c}^{1}{\bf x}^{1}\), then stop. \({\bf z}^{*}\) is the unique non-dominated point in \(Z_{\{1,2\}}\) and hence the unique NTU-Shapley value. Finally set \(m=1\).
Main Step.
- 1. Set \(m\leftarrow m+1\) and
\[\frac{w_{p}^{1}}{w_{p}^{2}}=\min_{j\in R}\left\{\frac{w_{j}^{1}}{w_{j}^{2}}:w_{j}^{2}>0\right\}.\]
Let \(x_{p}\) enter the basis and let \(x_{q}\) leave the basis where the index \(q\) is determined by the following minimum ratio test
\[\frac{(B^{-1}{\bf b})_{q}}{(B^{-1}N)_{qp}}=\min_{1\leq j\leq r}\left\{\frac{(B^{-1}{\bf b})_{j}}{(B^{-1}N)_{jp}}:(B^{-1}N)_{jp}>0\right\}.\]
Update \(B\) by replacing \({\bf a}_{q}\) with \({\bf a}_{p}\). Update \(R,S,N\) and let \({\bf x}^{m}=({\bf x}_{S}^{m},{\bf x}_{R}^{m})=(B^{-1}{\bf b},{\bf 0})\). - 2. Set
\[\lambda_{1}=\frac{w_{p}^{2}}{w_{p}^{2}-w_{p}^{1}}\mbox{ and }\lambda_{2}=\frac{w_{p}^{1}}{w_{p}^{1}-w_{p}^{2}}\]
and let
\[z_{i}=\frac{1}{2}z_{i}^{*}+\frac{\mbox{\boldmath \(\lambda\)}C{\bf x}^{m}-\lambda_{j}z_{j}^{*}}{2\lambda_{i}}\mbox{ for }i,j=1,2\mbox{ and }i\neq j.\]
If \((z_{1},z_{2})\) belongs to the line segment (facet) between \(C{\bf x}^{m-1}\) and \(C{\bf x}^{m}\), i.e., if the equation system
\begin{equation}{\label{and99eq7}}\tag{7}
\mu C{\bf x}^{m-1}+(1-\mu )C{\bf x}^{m}=z\mbox{ for }\mu\in (0,1)
\end{equation}
has a solution, then \((z_{1},z_{2})\) is an NTU-Shapley value with \((\lambda_{1},\lambda_{2})\) as comparison weight. - 3. Let \({\bf z}=C{\bf x}^{m}\) and set
\[\lambda_{i}=\frac{z_{j}^{*}-z_{j}}{z_{1}^{*}-z_{1}+z_{2}^{*}-z_{2}}\mbox{ for }i,j=1,2,\mbox{ and }i\neq j.\]
If \(\lambda_{1}=1\), then stop. Otherwise, update \(W\). Then, if \((\lambda_{1},\lambda_{2})W\geq 0\), \({\bf z}\) is an NTU-Shapley value with comparison weight \((\lambda_{1},\lambda_{2})\). - 4. Repeat the main step.
In the initialization step first the ideal point \({\bf z}^{*}\) is found and then the lexicographic maximal vector \((z_{1},z_{2}^{*})\) in the feasible region of the criterion space. Next, for each iteration of the main step two tests are performed. Consider the \(m\)th iteration. In part 2 of the main step it is checked whether or not there exists an NTU-Shapley value on the facet between the two neighbor extreme points \(({\bf c}^{1}{\bf x}^{m-1},{\bf c}^{2}{\bf x}^{m-1})\) and \(({\bf c}^{1}{\bf x}^{m},{\bf c}^{2}{\bf x}^{m})\) (in this case the comparison weight is normal to the facet) and in part 3 whether or not \(({\bf c}^{1}{\bf x}^{m},{\bf c}^{2}{\bf x}^{m})\) is an NTU-Shapley value (in this case the comparison weight is a vector from \(({\bf c}^{1}{\bf x}^{m},{\bf c}^{2}{\bf x}^{m})\) to the ideal point \((z_{1}^{*},z_{2}^{*})\). Finally, the optimal basis \(B\) is updated in the 1st part (a simplex pivot is performed).
Theorem. (Andersen and Lind \cite{and99}). The algorithm computes th set of NTU-Shapley values in a finite number of iteration. \(\sharp\)
Example. We consider the following MOLP
\begin{equation}{\label{and99eq9}}\tag{8}
\begin{array}{ll}
\max & x_{i}\mbox{ for }i=1,2\\
\mbox{subject to} & x_{1}+3x_{2}\leq 18\\
& x_{1}+2x_{2}\leq 13\\
& x_{1}+x_{2}\le 10\\
& x_{1},x_{2}\geq 0.
\end{array}
\end{equation}
Initialization step.
- 1. The ideal point \((z_{1}^{*},z_{2}^{*})=(10,6)\).
- 2. Let \(s_{j}\) denote the slack variable of row \(j\) for \(j=1,2,3\). From now on we state the variables in the order: \(x_{1},x_{2},s_{1},s_{2},s_{3}\). The optimal basic variables for program (\ref{and99eq9}) with \(i=2\) are \(x_{2},s_{2},s_{3}\). The reduced cost matrix is
\[W=\left [\begin{array}{cc}
-1 & 0\\ 1/3 & 1/3
\end{array}\right ]\]
and the optimal solution \({\bf x}^{1}=(x_{1},x_{2},s_{1},s_{2},s_{3})=(0,6,0,1,4)\). Hence \({\bf c}^{1}{\bf x}^{1}=0\neq z_{1}^{*}\). Finally, let \(m=1\).
Main step 1.
- 1. \(m=2\), \(x_{1}\) enters the basis and it follows from the minimum ratio test that \(s_{2}\) leaves it. \({\bf x}^{2}=(3,5,0,0,2)\). Thus \({\bf c}^{1}{\bf x}^{2}=3\neq 0={\bf c}^{1}{\bf x}^{1}\).
- 2. \(\lambda_{1}=\frac{1/3}{(1/3)+1}=1/4\) and \(\lambda_{2}=\frac{-1}{-1-(1/3)}=3/4\). Moreover, \((z_{1},z_{2})=(5,13/3)\). The system \(\mu C{\bf x}^{1}+(a-\mu )C{\bf x}^{2}={\bf z}\) reads
\[\mu\left [\begin{array}{c}
0\\ 6\end{array}\right ]+(1-\mu )\left [\begin{array}{c}
3\\ 5\end{array}\right ]=\left [\begin{array}{c}
5 \\ 13/3\end{array}\right ]\]
This system has the solution \(\mu =-2/3\) whihc means that \({\bf z}\) does not belong to the line segment between \(C{\bf x}^{1}\) and \(C{\bf x}^{2}\). Thus \((z_{1},z_{2})\) is not feasible. - 3. \({\bf z}=(3,5)\), \((\lambda_{1},\lambda_{2})=(1/8,7/8)\). The new reduced cost matrix becomes
\[W=\left [\begin{array}{cc}
-2 & 3\\ 1 & -1\end{array}\right ].\]
However \((\lambda_{1},\lambda_{2})W=(5/8,-1/2)\neq\geq {\bf 0}\). - 4. Repeat the main step.
Main step 2.
- 1. \(m=3\). Now \(s_{1}\) enters the basis and \(s_{3}\) leaves it. \({\bf x}^{3}=(7,3,2,0,0)\). Hence \({\bf c}^{1}{\bf x}^{3}\neq {\bf c}^{1}{\bf x}^{2}\).
- 2. \((\lambda_{1},\lambda_{2})=(1/3,2/3)\) and \({\bf z}=(11/2,15/4)\). Since \(\mu =3/8\) solves (\ref{and99eq7}) we conclude that \((11/2,15/4)\) is an NTU-Shapley value with comparison weight \((1/3.2/3)\).
- 3. \({\bf z}=(7,3)\), \((\lambda_{1},\lambda_{2})=(1/2,1/2)\) and
\[W=\left [\begin{array}{cc}
-1 & 2\\ 1 & -1\end{array}\right ].\]
$(\lambda_{1},\lambda_{2})W=(0,1/2)\geq {\bf 0}$. We conclude that \((7,3)\) is an NTU-Shapley value with comparison weight \((1/2,1/2)\). - 4. Repeat the main step.
Main step 3.
- 1. \(m=4\). \(s_{2}\) enters and \(x_{2}\) leaves the basis. \({\bf x}^{4}=(10,0,8,3,0)\). Hence, \({\bf c}^{1}{\bf x}^{3}\neq {\bf c}^{1}{\bf x}^{4}\).
- 2. \((\lambda_{1},\lambda_{2})=(1/2,1/2)\), \({\bf z}=(7,3)\). Since \(\mu =1\) solves (\ref{and99eq7}) the test does not reveal that \((7,3)\) is an NTU-Shapley value with comparison weight \((1/2,1/2)\).
- 3. \({\bf z}=(10,0)\). \(\lambda_{1}=\frac{6-0}{10-10+6-0}=1\). Thus the algorithm stops.
Two NTU-Shapley values were found: \((11,15/4)\) with \((1/3,2/3)\) as comparison weight and \((7,3)\) with comparison weight \((1/2,1/2)\). Notice that \((11/2,15/4)\) is not an extreme point but belongs to the relative interior of a non-dominated facet of \(Z_{\{1,2\}}\). \(\sharp\)
A recursiv procedure for computing the TU-Shapley value.
We present a new method for the computation of the Shapley value. The following result gives rise to an optimal recursive procedure.
\begin{equation}{\label{and99t2}}\tag{9}\mbox{}\end{equation}
Theorem \ref{and99t2}. (Andersen and Lind \cite{and99}) Let \((N,v)\in {\cal G}^{TU}\). Then
\[\mbox{\boldmath \(\phi\)}(v)=\frac{v(N)}{n}{\bf e}_{N}+\sum_{S\in M\setminus N}\left (\begin{array}{c} n\\|S|\end{array}\right )^{-1}\cdot\left (\frac{v(S)}{|S|}{\bf e}_{S}-\frac{v(S)}{|N\setminus S|}{\bf e}_{N\setminus S}\right )\]
where for each coalition \(S\in M\), the incidence vector is denoted by \({\bf e}_{S}\), i.e., \(({\bf e}_{S})_{i}=1\) if \(i\in S\) and \(({\bf e}_{S})_{i}=0\) if \(i\not\in S\). \(\sharp\)
Now, let \((N,v)\in {\cal G}^{TU}\), \(m=2^{n}-1\), \(k\in\{1,\cdots ,|M|\}\) and \(S_{1},\cdots ,S_{|M|}\) be an order of \(M\) for which \(S_{k}=N\). Consider the following recursive procedure
\[\mbox{\boldmath \(\phi\)}^{0}={\bf 0}\in\mathbb{R}^{N}\]
\[\mbox{\boldmath \(\phi\)}^{i}=\mbox{\boldmath \(\phi\)}^{i-1}+v(S_{i})\cdot\left (\begin{array}{c} n\\ |S_{i}|\end{array}\right )^{-1}\cdot\left (\frac{1}{|S_{i}|}{\bf e}_{S_{i}}-\frac{1}{n-|S_{i}|}{\bf e}_{N\setminus S_{i}}\right )\mbox{ for }i=1,\cdots ,k-1.\]
\begin{equation}{\label{and99eq10}}\tag{10}
\mbox{\boldmath \(\phi\)}^{k}=\mbox{\boldmath \(\phi\)}^{k-1}+\frac{v(N)}{n}{\bf e}_{N}
\end{equation}
\[\mbox{\boldmath \(\phi\)}^{i}=\mbox{\boldmath \(\phi\)}^{i-1}+v(S_{i})\cdot
\left (\begin{array}{c} n\\ |S_{i}|\end{array}\right )^{-1}\cdot\left (
\frac{1}{|S_{i}|}{\bf e}_{S_{i}}-\frac{1}{n-|S_{i}|}{\bf e}_{N\setminus S_{i}}\right )\mbox{ for }i=k+1,\cdots ,|M|.\]
It follows from Theorem \ref{and99t2} that the Shapley value of \((N,v)\) is equal to \(\mbox{\boldmath \)latex \phi$}^{|M|}$. Moreover, from a pure game theoretic perspective, it is interesting to noe that (\ref{and99eq10}) can be seen as a bargaining procedure which leads the players to the Shapley value. Now, assume that the characteristic function value for each coalition can be obtained in unit time. Then, by application of (\ref{and99eq10}) the Shapley value is found in \(O(n2^{n})\) using \(O(n)\) space. Notice that the coalitions can be considered in any given order.
