Similarly to the previous chapter let denote again the decision set of the th decision maker and let be the concrete decision alternatives. Furthermore, let denote the objective function of the th decision maker. Let be some subset of the decision makers, which is usually called coalition in the game theory. For arbitrary , let's introduce the
function, which is also called the characteristic function defined on all of the subsets of the set , if we add the and
special cases to definition (27.34).
Consider again that all of the sets are finite for . Be a coalition. The value of is given by the following algorithm, where denotes the number of elements of , denotes the elements and the elements which are not in .
1 , where a very big positive number 2
DO, where a very big positive number 9 10
In the following we determine the characteristic function. At first be , then
Since the function strictly decreases in the variables, the minimal value of it is given at , so
what is easy to see by plain differentiation. Similarly for
Similarly to the previous case the minimal value is given at , so
where we introduced the new variable. In the case of
where this time we introduced the variable.
Definition (27.34) can be interpreted in a way that the characteristic function value gives the guaranteed aggregate objective function value of the coalition regardless of the behavior of the others. The central issue of the theory and practice of the cooperative games is how should the certain decision makers share in the maximal aggregate profit attainable together. An division is usually called imputation, if
The inequality system (27.35)–(27.36) is usually satisfied by infinite number of imputations, so we have to specify additional conditions in order to select one special element of the imputation set. We can run into a similar situation while discussing the multi-objective programming, when we looks for a special Pareto optimal solution using the concrete methods.
The most popular solving approach is the Shapley value, which can be defined as follows:
where denotes the number of elements of the coalition.
Let's assume again that the decision makers are fully cooperating, that is they formulate the coalition , and the certain decision makers join to the coalition in random order. The difference indicates the contribution to the coalition by the th decision maker, while expression (27.37) indicates the average contribution of the same decision maker. It can be shown that is an imputation.
The Shapley value can be computed by following algorithm:
DOuse (27.37) for calculating
Example 27.11 In the previous example we calculated the value of the characteristic function. Because of the symmetry, must be true for the case of Shapley value. Since , . We get the same value by formula (27.37) too. Let's consider the value. If , , so the appropriate terms of the sum are zero-valued. The non-zero terms are given for coalitions and , so
An alternative solution approach requires the stability of the solution. It is said that the vector majorizes the vector in coalition , if
that is the coalition has an in interest to switch from payoff vector to payoff vector , or is instabil for coalition . The Neumann–Morgenstern solution is a set of imputations for which
(i) There is no , that majorizes in some coalition (inner stability)
(ii) If , there is , that majorizes -t in at least one coalition (outer stability).
The main difficulty of this conception is that there is no general existence theorem for the existence of a non-empty set, and there is no general method for constructing the set .
27.3-3 Determine the Shapley values for the game of Exercise 27.3-1.