In the previous video, we constructed a mathematical model for a Colonel Blotto game. But we did not answer on the main question. How to define the optimal strategies for Colonel Blotto, and what approach can be used in order to do that? Before we start, let's suppose that the Colonel Blotto uses a cautious behavior. Suppose that he can compute all possible outcomes in this game model. So, he can really construct a matrix game. Then, what he can do is for each of his strategy, he can choose the worst case scenario or the worst possible outcome. Then he could do that for each of his strategy, and then choose the strategy that maximizes his payoff for a given worst-case scenario. This kind of strategy, we will call a maximin strategy of the first player. We will denote it as x_i0 and x_i0 satisfies the following equation presented on the slide. Here what we do is for each row in the matrix game, we find a minimum. It means that for each strategy of the first player, we define the worst case scenario or the minimum payoff that he can obtain on this strategy. In this way, we do for each of his strategies, and then the maximin strategy, is the strategy of the first player which maximizes this worst case payoff. The payoff that the first player obtained according to this procedure, we will call the lower value of the game. In the same way we can do for the second player, and we will call it a minimax strategy of the second player. We will denote it as y_j0. For each column of the matrix game, we define a maximum value. The payoff of the second player is minus payoff of the first player. His aim is to minimize the payoff of the first player. So, the worst case scenario for him, is the maximum value for each column. Then, the minimax strategy is the strategy that corresponds to the column with minimum maximum value to the minimization over the worst case scenario for the second player. The payoff that is computed according to this procedure, we will call the upper value of the game. Let's go back to the Colonel Blotto game. So, how Colonel Blotto should behave? What strategy should he choose? Let's suppose, that the enemy chooses the strategy y_1, and Colonel Blotto knows that, then of course he would use a strategy x_1, which is the best reply, which is the maximization of his payoff given that the second player chooses a strategy y_1. But in our game model Colonel Blotto does not know in advance what strategy the enemy will choose. Let's use a maximin strategy for Colonel Blotto. In this case, there are two maximin strategies. The first one is x_0, and the second one is x_4. How did we calculate it there? What we can do is for each row we can define the minimum payoff. In case of x_0, the minimum payoff is equal to zero. In case of x_1, the minimum payoff is equal to minus one. In case of x_2, the minimum payoff is equal to minus two. In case of x_3, the minimum payoff is equal to minus one. In case of x_4, the minimum payoff is equal to zero. Now, we understand that if we would use the maximin strategy, then we would choose x_0 and x_4 because it maximizes the minimum possible payoff for the first player. The corresponding lower value is equal to zero. It is important to notice that, the maximin strategy of the first player, guarantee him the payoff not less than the lower value of the game. In this case, we say that if Colonel Blotto chooses his strategy x_0 or x_4, then he would receive payoff not less than zero. So, he would not lose a war. In the same way we can do for the second layer, in this case we need to define the minimax strategies. According to this matrix, these strategies are y_1 and y_2. The upper value of the game in this case is equal to three. But the problem for this game model and we will talk about that later is that the lower value of the game, does not correspond to the upper value of the game. So, the strategy profile which is composed of a maximin strategy of the first player, and minimax strategy of the second player is not stable. Let's consider another example of a matrix game where each player has three strategies. For this particular game model, the maximin strategy of the first player is a strategy x_1, and minimax strategy of the second player is y_0. For this case, the lower value of the game is equal to the upper value of the game, and is equal to two. It is important to notice here that, for both players, this strategy profile is a good solution. Because in some sense, the strategy profile is stable. In order to formalize this, we need to define the notion of a saddle point. In the two-person zero-sum game, Gamma(X,Y,K) the point (x*,y*) is called a saddle point, if the following conditions are satisfied. This conditions mean that for each player individual deviation from this strategy profile is not beneficial. So, for the player one, his payoff in strategy profile (x*,y*), is more or equal to his payoff when the second player uses a strategy y*, and the first player chooses some arbitrary strategy from his set of strategies. This condition holds for any arbitrary strategy x. For the second player, the condition means that his losses in strategy profile (x*,y*), are less or equal to his losses when the first player uses strategy x*, and the second player uses an arbitrary strategy y. But the question is of when the saddle point of this solution of the game exists? On the slide, you can see the necessary and sufficient conditions for the existence of a saddle point. We say that the saddle point in the game Gamma exists if and only if the lower value of the game is equal to the upper value of the game. So, now we understand that in the example that we considered previously, the saddle point exists. But in Colonel Blotto game in the way we defined it before, it does not exist. On this slide you can see a list of references from where you could get more information about the notion of saddle point, and you could consider a more interesting examples of this topic.