27.3. 27.3 Methods of cooperative games

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 .

Characteristic-Function( )

  1  , where  a very big positive number   2  
                  FOR
                
                
               
                  TO
                
                  3       4    
                  DO
                
               
                  FOR
                
                
               
                  TO
                
                  5       
                  DO
                
               
                  FOR
                
                
               
                  TO
                
                  6             7          
                  DO
                
               
                  FOR
                
                
               
                  TO
                
                  8             
                  DO
                
               , where  a very big positive number   9                  10                
                  IF
                
                 11                   
                  THEN
                
                 12       
                  IF
                
                 13          
                  THEN
                
                 14  
                  RETURN
                
                
            

Example 27.9 Let's return to the problem discussed in the previous example, and assume that , , Ús for . Since the cost functions are identical, the objective functions are identical as well:

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

for and

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.

Example 27.10 In the previous case a vector is imputation if

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:

Shapley-Value

  1  
                  FOR
                
                  2    
                  DO
                
               
               
                  Characteristic-Function(
                  
                  )
                  3  
                  FOR
                
                
               
                  TO
                
                  4    
                  DO
                use (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 .

Exercises

27.3-1 Let , , . Determine the characteristic function.

27.3-2 Formulate the (27.35), (27.36) condition system for the game of the previous exercise.

27.3-3 Determine the Shapley values for the game of Exercise 27.3-1.