In the previous video, we studied the multi-stage game models with perfect information. The main question was of how to model the behavior of players in the processes that can be defined by the multi-stage game with perfect information in the processes such as chess game. Today, we will talk about the cooperative multi-stage games. In the first part, we will study the cooperative multi-stage games in characteristic function form. We suppose that in the beginning of the game, players choose strategies that would maximize their joint payoff and then they would choose a rule to allocate this cooperative payoff among the players. This models can be used in order to define the parameters of cooperative agreements. For example cooperative agreements for joint venture. So on the first step, we defined set of strategies of how we would invest into the joint venture. Then on the second step, we choose a rule for allocation the cooperative payoff or cooperative profit. The next part of today's video is devoted to multi-stage cooperative games with non transferable utilities. In here, we suppose that we cannot allocate cooperative payoff among the players but we can make an agreement on strategies. So we can choose a set of strategies that could give to all of the players a good outcomes. So we could negotiate strategies so that everyone of the players would benefit from this cooperation. This could be used for defining the parameters of the strategic agreements. Let's consider the following example model which is called a signing of package of documents. Let's suppose that there is a company who wants to sign a package of documents in three institutions. On the first step the package of documents goes to the first institution. First institution can approve or decline the documents, then the package goes to the second institution. Then again the second institution can approve or decline the documents. Then it goes to the third institution. If the third institution approves the documents, then the documents are approved. If not, then they are declined. In any way, the company should pay a fee to the all three institutions. So the question is of how to construct a mathematical model for this problem and how they define a way to allocate the joint fee or the fee that pays company to all institutions among the institutions. Why it is so important? The first institution has the control over the system because if it decides to decline the documents, then the documents will be declined and they would not go to the second and the third institution. So the first institution has the power over the system. So in order to construct the mathematical model, we need to define a cooperative multi-stage game with perfect information. We will do that in the same way we defined a multi-stage game with perfect information. So we define a set of players N from 1 to n. We define a graph which defines a set of possible positions of all the players and the set of possible alternative or set of strategies. The set of all positions on the graph is divided to the sets X_i, i from 1 to n which are the sets of personal positions of the players or the sets of vertices where player i makes a move and to the set X_n+1, which is the set of terminal positions. The payoff in this type of games should be defined in each vertex or the payment for each player now is defined for each vertex. For example, on the first vertex players 1,2...n receive a payment. Then on the next stage, again all players receive a payment. Strategies of players are defined in the same way as they were defined for the multi-stage games with perfect information. We will say that the strategy is a mapping which for each position from the set of personal positions of player i assigns an exposition on the graph. For a given strategy profile or for a given vector of strategies, the unique path or the unique trajectory on the graph is defined. Along this graph, the sum of payments for player i is equal to his payoff function. So that is how we define the payoff function in this game. Let's go back to our example signing a package of documents. The graph for this game is defined in the way it is presented on the slide. So on the first stage, player one makes a move. He has two alternatives. The first alternative is to approve a package of documents. The second one is to decline it. On this next step, the second player has also two alternatives, and the third step, again, the third player has two alternatives. The payments for each player here are defined only on the set of terminal positions because we suppose that the company pays a fee only at the end of the process, so if the documents are approved or if the documents are declined. So on the first step, the player one or the institution one can approve the documents or decline. Then again approve the documents or decline, approve or decline. The set of players is equal to the set of institutions. So, one, two, and three. The corresponding payoffs are presented on the slide. Then how do we define a cooperative game? On the first step, we need to define a set of strategies that would maximize the joint payoff of players. In this case, it means that we would need to define a set of strategies that would maximize the joint payoff of all institutions. That is not very realistic. So, that is not how they should behave in the real life, but we suppose that they are going to do this. So, we define a set of strategies that maximize the payoff for all players. Then for corresponding set of strategies, there is a unique path or unique trajectory in the graph. This trajectory and corresponding strategies, we will call the cooperative strategies and cooperative trajectory. On the slide, you can see the cooperative trajectory for the game of signing of package of documents, and this trajectory is X_0 dash, X_1 dash, X_2 dash, and X_3 dash. Why? Because the joint payoff of all players along this path is equal to six. For example, the joint payoff on the path X_0 and when the first player chooses the alternative B, is equal to three. It is even less if the other players will choose to decline. Next question is of how to allocate the joint payoff along the cooperative trajectory. So, now the institutions or players made an agreement on strategies, but how to allocate the joint payoff so that this agreement would be beneficial for all of the participants, because sometimes the cooperative agreement that assigns such a behavior is not beneficial for one of the participants. Then we need to reallocate the cooperative payoff among the players so that it would be individually rational and group rational. So, in order to do that, firstly, we need to define the characteristic function. In one of the previous sections, we also worked with characteristic function. But there, it was a static game. So, the characteristic function was predefined. In here, we need to define characteristic function using the multi-stage game. So, we will use the following approach. The characteristic function of coalition S will be defined as a value of the zero-sum game between coalitions S and N-S. So, for a given coalition S, we consider a zero-sum game between all players acting as one from coalition S and all players acting as one from college and N minus S. So, the payoff of players from coalition S in saddle point will be the value of characteristic function. For this case, the value of characteristic function of all players, so the value of characteristic function for coalition N will be equal to the maximum joined payoff in the whole game. Also, the characteristic function which is defined by the following approach, and it is called a Maximin Approach, satisfies the superadditivity property. This property tells us that a grand coalition of all players is beneficial for all of them. On the basis of characteristic function, we will define a set of imputations in the whole game or set of ways for allocating joint payoff in the game. Each imputation is a vector ksi from ksi_1 to ksi_n, which satisfies the group rationality and individual rationality properties. So, the individual rationality property tells us that the imputation or the payoff that player i receives in the cooperation is more or equal to his payoff that he obtains if he's not in the cooperation or not cooperating, or the value of characteristic function of coalition consisting of only player i. The group rationality property tells us that we allocate a maximum joint payoff of all players. Why? Because the V(N) in this particular approach actually is the maximum joint payoff of players. So, the payoff that the players obtain along the cooperative trajectory. Next thing we need to do is, we need to choose a subset from the set of imputation or the set of imputation that we would use for our cooperative agreement. The subset we will call a cooperative solution. In this case, we will use a Shapley Values cooperative solution. On the slide, you can see the explicit formula for Shapley Value. Of course, we would need to define it using the set of axioms, but we already did that in one of the previous sections, and then we derive the explicit formula. Now we will just use it for our particular game model. Let's go back to our model of signing of package from documents. On the slide, you can see values of characteristic function. The value of characteristic function for coalition 1,2,3 or for all players is equal to six. Why? Because the maximum joint payoff of all players is equal to six. Let's consider the way we can calculate the value of characteristic function for coalition consisting of only player one. It is equal to one. Why? On the first step, player one makes a move. He has two alternatives: to approve the package of documents or to decline the package of documents. Let's suppose that he chooses to approve a package of documents. Then, according to the procedure of calculating the characteristic function, players two and three should minimize his payoff or they should choose strategies so that the payoff of player one would be minimum. Then, according to this procedure, player two would choose to approve a package of documents, but the player three would choose to decline. Then, as a result, player one would receive payoff equal to one-third. Of course, on the first step, player one would choose an alternative B, so to decline. Then his payoff would be equal to one no matter what strategies will the players two and three chose. So, the characteristic function of player one is equal to one. In the same way, we can calculate the values of characteristic function for other coalitions. On the basis of values of characteristic function, we can define a set of imputations in the following way. This is set of vectors, Xi one, Xi two, and Xi three, where Xi one is more or equal to one, Xi two is more or equal to one-half, and Xi three is more or equal to one-third. The sum of them is equal to six. Then, in a set of imputations, we can choose a specific cooperative solution or, in this case, we will choose a Shapley Value. The formula for Shapley Value is presented on slide. On this slide, you can see a list of references, where you can find more information of how to define a cooperative multi-stage game, how to define a characteristic function for this game and what cooperative solutions can be used for a multi-stage games.