Solution of matrix antagonistic games. Antagonistic game Antagonistic game examples

Tests for final control

1. Antagonistic game can be set:

a) a set of strategies for both players and a saddle point.

b) the set of strategies of both players and the payoff function of the first player.

2. The price of the game always exists for matrix games in mixed strategies.

a) yes.

3. If all columns in the payoff matrix are the same and look like (4 5 0 1), then what strategy is optimal for the 1st player?

a) first.

b) second.

c) any of the four.

4. Let in the matrix game one of the mixed strategies of the 1st player has the form (0.3, 0.7), and one of the mixed strategies of the 2nd player has the form (0.4, 0, 0.6). What is the dimension of this matrix?

a) 2*3.

c) another dimension.

5. The principle of dominance allows you to remove from the matrix in one step:

a) entire lines.

b) separate numbers.

6. In the graphical method for solving games 2 * m, directly from the graph find:

a) the optimal strategies of both players.

b) the price of the game and the optimal strategies of the 2nd player.

c) the price of the game and the optimal strategies of the 1st player.

7. The graph of the lower envelope for the graphical method of solving games 2 * m is in the general case:

a) broken.

b) straight.

c) a parabola.

8. In the 2*2 matrix game, the two components of the player's mixed strategy are:

a) determine each other's values.

b) are independent.

9. In the matrix game, the element aij is:

a) the payoff of the 1st player when he uses the i-th strategy, and the 2nd - the j-th strategy.

b) the optimal strategy of the 1st player when the opponent uses the i-th or j-th strategy.

c) the loss of the 1st player when he uses the j-th strategy, and the 2nd - the i-th strategy.

10. Matrix element aij corresponds to the saddle point. The following situations are possible:

a) this element is strictly less than all in the string.

b) this element is second in order in the string.

11. In the Brown-Robinson method, each player, when choosing a strategy at the next step, is guided by:

a) opponent's strategies on previous steps.

b) their strategies in the previous steps.

c) something else.

12. According to the criterion of mathematical expectation, each player proceeds from the fact that:

a) the worst situation for him will happen.

c) all or some situations are possible with some given probabilities.

13. Let the matrix game be given by a matrix in which all elements are negative. The value of the game is positive:

b) no.

c) there is no clear answer.

14. The price of the game is:

a) number.

b) vector.

c) matrix.

15. What is the maximum number of saddle points in a 5 * 5 game (matrix can contain any numbers):

16. Let in a matrix game of dimension 2*3 one of the mixed strategies of the 1st player has the form (0.3, 0.7), and one of the mixed strategies of the 2nd player has the form (0.3, x, 0.5). What is the number x?

c) another number.

17. For what dimension of the game matrix does the Wald criterion turn into the Laplace criterion?

c) only in other cases.

18. The upper price of the game is always less than the lower price of the game.

b) no.

b) the question is incorrect.

19. What strategies are there in the matrix game:

a) clean.

b) mixed.

c) both.

20. Can the values ​​of the payoff function of both players for some values ​​of the variables be equal to 1 in some antagonistic game?

a) always.

b) sometimes.

c) never.

21. Let in the matrix game one of the mixed strategies of the 1st player has the form (0.3, 0.7), and one of the mixed strategies of the 2nd player has the form (0.4, 0.1,0.1,0.4). What is the dimension of this matrix?

c) different dimensions.

22. The principle of dominance allows you to remove from the matrix in one step:

a) whole columns

b) separate numbers.

c) smaller submatrices.

23. In a 3*3 matrix game, the two components of the player's mixed strategy are:

a) determine the third.

b) not defined.

24. In the matrix game, the element aij is:

a) the loss of the 2nd player when he uses the j-th strategy, and the 2nd player - the i-th strategy.

b) the optimal strategy of the 2nd player when the opponent uses the i-th or j-th strategy,

c) the payoff of the 1st player when he uses the j-th strategy, and the 2nd - the i-th strategy,

25. The matrix element aij corresponds to the saddle point. The following situations are possible:

a) this element is the largest in the column.

b) this element is strictly greater than all in order in the string.

c) the string contains elements both greater and less than this element.

26. According to the Wald criterion, each player proceeds from the fact that:

a) the worst situation for him will happen.

b) all situations are equally possible.

c) all situations are possible with some given probabilities.

27. The lower price is less than the upper price of the game:

b) not always.

c) never.

28. The sum of the components of a mixed strategy for a matrix game is always:

a) is equal to 1.

b) is non-negative.

c) is positive.

d) not always.

29. Let in a matrix game of dimension 2*3 one of the mixed strategies of the 1st player has the form (0.3, 0.7), and one of the mixed strategies of the 2nd player has the form (0.2, x, x). What is the number x?

Game theory is a theory of mathematical models of decision making under conditions of conflict or uncertainty. It is assumed that the actions of the parties in the game are characterized by certain strategies - sets of action rules. If the gain of one side inevitably leads to the loss of the other side, then they speak of antagonistic games. If the set of strategies is limited, then the game is called a matrix game and the solution can be obtained very simply. The solutions obtained with the help of game theory are useful in drawing up plans in the face of possible opposition from competitors or uncertainty in the external environment.

If the bimatrix game is antagonistic, then the payoff matrix of player 2 is completely determined by the payoff matrix of player 1 (the corresponding elements of these two matrices differ only in signs). Therefore, a bimatrix antagonistic game is completely described by a single matrix (the payoff matrix of player 1) and, accordingly, is called a matrix game.

This game is antagonistic. In it j \u003d x2 - O, P, and R (O, O] \u003d H (P, P) \u003d -I and R (O, P) \u003d R (P, O) \u003d 1, or in matrix form o p

Let some class of games Г be "mirror-closed", i.e. together with each of its games contains a mirror isomorphic game (since all games that are mirror isomorphic to a given one are isomorphic to each other, we, in accordance with what has just been said, can speak of one mirror isomorphic game). Such a class is, for example, the class of all antagonistic games or the class of all matrix games.

Recalling the definition of acceptable situations in the antagonistic game, we obtain that the situation (X, Y) in the mixed extension of the matrix game is acceptable for player 1 if and only if for any x G x the inequality

The process of converting games into symmetrical ones is called symmetrization. We describe here one method of symmetrization. Another, fundamentally different version of symmetrization will be given in Section 26.7. Both of these variants of symmetrization are actually applicable to arbitrary antagonistic games, but will be formulated and proved only for matrix games.

Thus, the initial terms and designations of the theory of general antagonistic games coincide with the corresponding terms and designations of the theory of matrix games.

For finite antagonistic (matrix) games, the existence of these extrema was proved by us in Chapter 10. 1, and the whole point was to establish their equality, or at least to find ways to overcome their inequality.

The consideration of matrix games already shows that there are antagonistic games without equilibrium situations (and even without e-equilibrium situations for sufficiently small e > 0) in the initially given strategies of the players.

But each finite (matrix) game can be extended to an infinite game , for example, by providing each player with any number of dominated strategies (see 22 Ch. 1). Obviously, such an expansion of the player's set of strategies will not really mean an expansion of his possibilities, and his actual behavior in the expanded game should not differ from his behavior in the original game. Thus, we immediately obtained a sufficient number of examples of infinite antagonistic games that do not have saddle points. There are also examples of this kind.

Thus, in order to implement the maximin principle in an infinite antagonistic game, it is necessary, as in the case of a finite (matrix) game, some expansion of the strategic capabilities of the players. For 96

As in the case of matrix games (see Chap. 1, 17), for general antagonistic games an important role is played by the concept of a mixed strategy spectrum, which here, however, has to be given a more general definition.

Finally, note that the set of all mixed strategies of player 1 in an arbitrary antagonistic game is, as in the matrix

Even a consideration of antagonistic games shows that a large number of such games, including finite ones, matrix games have equilibrium situations not in the original, pure strategies, but only in generalized, mixed strategies. Therefore, for general, non-antagonistic, non-cooperative games, it is natural to look for equilibrium situations precisely in mixed strategies.

So, for example (see Fig. 3.1), we have already noted that the "Contractor" almost never has to deal with behavioral uncertainty. But if we take the conceptual level of the "Administrator" type, then everything is just the opposite. As a rule, the main type of uncertainty that such "our decision maker" has to face is "Conflict". Now we can clarify that this is usually a non-strict rivalry. Somewhat less often, the "Administrator" makes decisions in conditions of "natural uncertainty", and even more rarely does he encounter a strict, antagonistic conflict. In addition, the clash of interests when making decisions by the "Administrator" occurs, so to speak, "once", i.e. in our classification, he often plays only one (sometimes a very small number) of games of the game. Scales for evaluating consequences are more often qualitative than quantitative. The strategic independence of the "Administrator" is quite limited. Taking into account the above, it can be argued that problem situations of this magnitude most often have to be analyzed with the help of non-cooperative non-antagonistic bi-matrix games, moreover, in pure strategies.

Principles for solving matrix antagonistic games

As a result, it is reasonable to expect that in the game described above, opponents will adhere to their chosen strategies. Matrix antagonistic game for which max min fiv = min max Aiy>

However, not all matrix antagonistic games are quite definite, and in the general case

Thus, in the general case, to solve a matrix antagonistic game of dimension /uxl, it is necessary to solve a pair of dual linear programming problems , resulting in a set of optimal strategies , / and the cost of the game v.

How is the matrix antagonistic game of two persons defined?

What are the methods for simplifying and solving matrix antagonistic games

In the case of a game of two persons, it is natural to consider their interests as directly opposite - the game is antagonistic. Thus, the payoff of one player is equal to the loss of the other (the sum of the payoffs of both players is zero, hence the name, the zero-sum game). We will consider games in which each player has a finite number of alternatives. The payoff function for such a zero-sum two-person game can be given in matrix form (in the form of a payoff matrix).

As already noted, the final antagonistic game is called matrix.

MATRIX GAMES - a class of antagonistic games in which two players participate, and each player has a finite number of strategies. If one player has m strategies and the other player has n strategies, then we can construct a game matrix of dimension txn. M.i. may or may not have a saddle point. In the latter case

Introduction

Real conflict situations lead to different types of games. Games differ in a number of ways: by the number of players participating in them, by the number of possible players, by the number of possible strategies, by the nature of the relationship between the players, by the nature of the payoffs, by the type of payoff functions, by the number of moves, by the nature of the informational support of the players, etc. .d. Consider the types of games depending on their division:

By the number of strategies, games are divided into final(each player has a finite number of possible strategies) and endless(where at least one of the players has an infinite number of possible strategies).

By the nature of the winnings, games with zero sum(the total capital of the players does not change, but is redistributed between the players depending on the resulting outcomes) and games with non-zero sum.

By the type of functions, the winnings of the game are divided into matrix ( is a finite two-player zero-sum game in which the player's payoff is given A in the form of a matrix (the row of the matrix corresponds to the number of the player’s applied strategy IN, column - the number of the applied strategy of the player IN; at the intersection of the row and column of the matrix is ​​the player's payoff A corresponding to the applied strategies.

For matrix games, it is proved that any of them has a solution, and it can be easily found by reducing the game to a linear programming problem), bimatrix game (this is a finite game of two players with a non-zero sum, in which the payoffs of each player are given by matrices separately for the corresponding player (in each matrix, a row corresponds to the player's strategy A, column - player's strategies IN, at the intersection of the row and column in the first matrix is ​​the payoff of the player A, in the second matrix is ​​the payoff of the player IN.

For bimatrix games, the theory of optimal behavior of players has also been developed, but solving such games is more difficult than conventional matrix games. continuous games ( continuous a game is considered in which the payoff function of each player is continuous depending on the strategies. It is proved that games of this class have solutions, but practically acceptable methods for finding them have not been developed), etc.

Other approaches to partitioning games are also possible. Now let's return directly to the topic of research, namely to Game Theory. First, let's define this concept.

Game theory - a branch of mathematics that studies formal models for making optimal decisions in a conflict. At the same time, a conflict is understood as a phenomenon in which various parties participate, endowed with different interests and opportunities to choose the actions available to them in accordance with these interests. In a conflict, the enemy’s desire to hide his forthcoming actions creates uncertainty. On the contrary, uncertainty in decision making (for example, based on insufficient data) can be interpreted as a conflict between the decision maker and nature. Therefore, game theory is also considered as the theory of making optimal decisions under uncertainty. It allows you to systematize some important aspects of decision-making in engineering, agriculture, medicine and sociology and other sciences. The parties involved in the conflict are called coalitions of action; the actions available to them are their strategies; possible outcomes of the conflict - situations.

The goal of the theory is to:

1) optimal behavior in the game.

2) study of the properties of optimal behavior

3) determination of the conditions under which its use is meaningful (questions of existence, uniqueness, and for dynamic games also questions of nominal validity).

4) construction of numerical methods for finding the optimal behavior.

Game theory, created for the mathematical solution of problems of economic and social origin, cannot be generally reduced to classical mathematical theories created for solving physical and technical problems. However, in various specific issues of game theory, very diverse classical mathematical methods are widely used.

In addition, game theory is related to a number of mathematical disciplines in an internal way. In game theory, concepts of probability theory are systematically and essentially used. Most of the problems of mathematical statistics can be formulated in the language of game theory, and since game theory is related to decision theory, it is considered as an essential part of the mathematical apparatus of operations research.

The mathematical concept of a game is extraordinarily broad. It includes the so-called parlor games (including chess, checkers, civil defense, card games, dominoes), but can also be used to describe models of an economic system with numerous buyers and sellers competing with each other. Without going into details, a game can be broadly defined as a situation in which one or more individuals (“players”) jointly control some set of variables and each player, when making a decision, must take into account the actions of the whole group. The "payoff" for each player is determined not only by his own actions, but also by the actions of other members of the group. Some of the "moves" (individual actions) during the game may be random. A well-known poker game can serve as a clear illustration: the initial deal of cards is a random move. The sequence of bets and counterbets preceding the final comparison of tricks is formed by the rest of the moves in the game.

Mathematical GAME THEORY began with the analysis of sports, card and other games. They say that the discoverer of game theory, an outstanding American mathematician of the XX century. John von Neumann came up with the ideas of his theory while watching a game of poker. This is where the name “game theory” comes from.

Let's start this research with retrospective analysis of the development of game theory. Consider the history and development of the issue of game theory. Usually, a "family tree" is represented as a tree in the sense of graph theory, in which the branching comes from some single "root". Genealogy of game theory - book by J. von Neumann and O. Morgenstern. Therefore, the historical course of the development of game theory as a mathematical discipline is naturally divided into three stages:

First stage- before the publication of the monograph by J. von Neumann and O. Morgenstern. It can be called "pre-monographic". At this stage, the game still appears as a concrete competition, described by its rules in meaningful terms. Only at the end of it does J. von Neumann develop an idea of ​​play as a general model of abstract conflict. The result of this stage was the accumulation of a number of specific mathematical results and even individual principles of future game theory.

Second phase is the monograph of J. von Neumann itself and

O. Morgenstern "The Theory of Games and Economic Behavior" (1944), which combined most of the previously obtained (however, by modern mathematical standards, rather few) results. She first presented the mathematical approach to games (both in the concrete and abstract sense of the word) in the form of a systematic theory.

Finally, on third stage game theory in its approach to the objects under study differs little from other branches of mathematics and develops to a large extent according to the laws common with them. At the same time, of course, the specifics of its practical applications, both actual and possible, have a significant influence on the formation of areas of game theory.

However, even the mathematical theory of games is not able to completely predetermine the outcome of some conflicts. It seems possible to single out three main reasons for the uncertainty of the outcome of a game (conflict).

Firstly, these are games in which there is a real opportunity to explore all or, at least, most of the variants of game behavior, of which one is the most true, leading to a win. Uncertainty is caused by a significant number of options, so it is not always possible to explore absolutely all options (for example, the Japanese game of GO, Russian and international checkers, British reversi).

Secondly, unpredictable by the players, the random influence of factors on the game. These factors have a decisive influence on the outcome of the game and can only be to a small extent, or not at all, controlled and determined by the players. The final outcome of the game is only to a very small extent determined by the actions of the players themselves. Games, the outcome of which is uncertain due to random reasons, are called gambling. The outcome of the game is always probabilistic or conjectural (roulette, dice, toss).

Thirdly, the uncertainty is caused by the lack of information about which strategy the playing opponent adheres to. Players' ignorance of the opponent's behavior is fundamental and is determined by the very rules of the game. Such games are called strategic.

Game theory is one of the important sections of "Operations Research" and represents the theoretical foundations of mathematical models for making optimal decisions in conflict situations of market relations that are in the nature of a competitive struggle in which one opposing side wins from the other at the expense of the other. Along with such a situation, within the framework of the science of Operations Research, which provides a mathematical description of the formulations of various decision-making problems, situations of risk and uncertainty are considered. In a situation of uncertainty, the probabilities of the conditions are unknown and there is no way to obtain additional statistical information about them. The environment surrounding the solution of the problem, which manifests itself in certain conditions, is called "nature", and the corresponding mathematical models are called "games with nature" or "statistical game theory". The main goal of game theory is to develop recommendations for the satisfactory behavior of players in a conflict, that is, to identify the “optimal strategy” for each of them.

Consider a finite zero-sum pair game. Denote by a player's payoff A, and through b- player win B. Because a = –b, then when analyzing such a game there is no need to consider both of these numbers - it is enough to consider the payoff of one of the players. Let it be, for example, A. In what follows, for convenience of presentation, the side A we will conditionally name " We"and the side B – "enemy".

Let us have m possible strategies A 1 , A 2 , …, A m, and the enemy n possible strategies B 1 , B 2 , …, B n(such a game is called a game m×n). Assume that each side has chosen a certain strategy: we have chosen Ai, adversary B j. If the game consists only of personal moves, then the choice of strategies Ai And B j uniquely determines the outcome of the game - our payoff (positive or negative). Let's denote this gain as aij(winning when we choose the strategy Ai, and the enemy - strategies B j).

If the game contains, in addition to personal random moves, then the payoff for a pair of strategies Ai, B j is a random variable that depends on the outcomes of all random moves. In this case, the natural estimate of the expected payoff is mathematical expectation of a random win. For convenience, we will denote by aij both the payoff itself (in a game without random moves) and its mathematical expectation (in a game with random moves).

Suppose we know the values aij for each pair of strategies. These values ​​can be written as a matrix whose rows correspond to our strategies ( Ai), and the columns show the opponent's strategies ( B j):

B j A i	B 1	B 2	…	B n
A 1	a 11	a 12	…	a 1n
A 2	a 21	a 22	…	a 2n
…	…	…	…	…
A m	a m 1	a m 2	…	amn

Such a matrix is ​​called payoff matrix of the game or simply game matrix.

Note that the construction of a payoff matrix for games with a large number of strategies can be a difficult task. For example, for a chess game, the number of possible strategies is so large that the construction of a payoff matrix is ​​practically impossible. However, in principle any finite game can be reduced to a matrix form.

Consider example 1 4×5 antagonistic game. We have four strategies at our disposal, the enemy has five strategies. The game matrix is ​​as follows:

B j A i	B 1	B 2	B 3	B 4	B 5
A 1
A 2
A 3
A 4

What strategy should we (i.e., the player A) to use? Whatever strategy we choose, a reasonable adversary will respond to it with the strategy for which our payoff will be minimal. For example, if we choose the strategy A 3 (tempted by a win of 10), the opponent will choose a strategy in response B 1 , and our payoff will be only 1. Obviously, based on the principle of caution (and it is the main principle of game theory), we must choose the strategy in which our minimum gain is maximum.

Denote by a i minimum payoff value for the strategy Ai:

and add a column containing these values ​​to the game matrix:

B j A i	B 1	B 2	B 3	B 4	B 5	minimum in rows a i
A 1
A 2
A 3
A 4							maximin

When choosing a strategy, we must choose the one for which the value a i maximum. Let's denote this maximum value by α :

Value α called lower game price or maximin(maximum minimum win). Player strategy A corresponding to the maximin α , is called maximin strategy.

In this example, the maximin α is equal to 3 (the corresponding cell in the table is highlighted in gray), and the maximin strategy is A 4 . Having chosen this strategy, we can be sure that for any behavior of the enemy we will win no less than 3 (and maybe more with the “unreasonable” behavior of the enemy). This value is our guaranteed minimum, which we can ensure for ourselves, adhering to the most cautious ("reinsurance") strategy.

Now we will carry out similar reasoning for the enemy B B A B 2 - we will answer him A .

Denote by βj A B) for the strategy Ai:

βj β :

7. WHAT IS THE UPPER VALUE GAME Now we will carry out similar reasoning for the opponent B. He is interested in minimizing our gain, that is, giving us less, but he must count on our behavior, which is the worst for him. For example, if he chooses the strategy B 1 , then we will answer him with a strategy A 3 , and he will give us 10. If he chooses B 2 - we will answer him A 2 , and he will give 8, and so on. Obviously, a cautious opponent must choose the strategy in which our maximum gain will be minimum.

Denote by βj the maximum values ​​in the columns of the payoff matrix (the maximum payoff of the player A, or, which is the same, the player's maximum loss B) for the strategy Ai:

and add a row containing these values ​​to the game matrix:

Choosing a strategy, the enemy will prefer the one for which the value βj minimum. Let's denote it by β :

Value β called top game price or minimax(minimum maximum win). The opponent's (player's) strategy corresponding to the minimax B), is called minimax strategy.

Minimax is the value of the gain, more than which a reasonable opponent will certainly not give us (in other words, a reasonable opponent will lose no more than β ). In this example, minimax β is equal to 5 (the corresponding cell in the table is highlighted in gray) and it is achieved with the opponent's strategy B 3 .

So, based on the principle of caution ("always expect the worst!"), we must choose a strategy A 4 , and the enemy - a strategy B 3 . The principle of caution is fundamental in game theory and is called minimax principle.

Consider example 2. Let the players A And IN one of three numbers is written simultaneously and independently of each other: either "1", or "2", or "3". If the sum of the written numbers is even, then the player B pays the player A this amount. If the amount is odd, then the player pays this amount A player IN.

Let's write down the payoff matrix of the game and find the lower and upper prices of the game (the strategy number corresponds to the written number):

Player A must adhere to the maximin strategy A 1 to win at least -3 (that is, to lose at most 3). Minimax Player Strategy B any of the strategies B 1 and B 2 , which guarantees that he will give no more than 4.

We will get the same result if we write the payoff matrix from the player's point of view IN. In fact, this matrix is ​​obtained by transposing the matrix constructed from the player's point of view A, and changing the signs of the elements to the opposite (since the payoff of the player A is the loss of the player IN):

Based on this matrix, it follows that the player B must follow any of the strategies B 1 and B 2 (and then he will lose no more than 4), and the player A– strategies A 1 (and then he will lose no more than 3). As you can see, the result is exactly the same as the one obtained above, so the analysis does not matter from the point of view of which player we conduct it.

8 WHAT IS A VALUABLE GAME.

9. WHAT DOES THE MINIMAX PRINCIPLE CONSIST OF. 2. Lower and upper price of the game. Minimax principle

Consider a matrix game of the type with payoff matrix

If the player A will choose a strategy A i, then all its possible payoffs will be elements i-th row of the matrix WITH. Worst for a player A case when the player IN applies a strategy appropriate to minimum element of this line, the player's payoff A will be equal to the number.

Therefore, in order to get the maximum payoff, the player A you need to choose one of the strategies for which the number maximum.

The approach to solving matrix games can be generalized to the case of antagonistic games, in which the payoff of the players is given as a continuous function (an infinite antagonistic game).

Such a game is represented as a two-player game in which player 1 chooses a number X from many x, player 2 chooses a number y from the set 7, and after that players 1 and 2 receive payoffs respectively U(x, y) and -U(x, y). Choosing a certain number by a player means applying his pure strategy corresponding to this number.

By analogy with matrix games, the net lower price of a game can be called v(= max min U(x, y), a net top game price -v 2 =

minmax U(x, y). Then, by analogy, we can assume that if for some

at *

or an endless antagonistic play of magnitude V And v2 exist and are equal to each other (“i \u003d v 2 \u003d v), then such a game has a solution in pure strategies, i.e., Player 1's optimal strategy is to choose the number x° e x, and player 2 - numbers at 0 e 7, at which Wx ( at 0) -v.

In this case v is called the pure value of the game, and (x°, y 0) is the saddle point of the infinite antagonistic game.

For matrix games, the quantities v x And v2 always exist, but in infinite antagonistic games they may not exist, i.e. the endless antagonistic game is not always solvable.

When formalizing a real situation in the form of an endless antagonistic game, a single strategic interval is usually chosen - a single interval from which players can make a choice (X - the number (strategy) chosen by player 1; -

number (strategy) chosen by player 2). Technically, this simplifies the solution, since by a simple transformation any interval can be converted into a unit one and vice versa. Such a game is called antagonistic game on a unit square.

For example, let's say that player 1 chooses the number X from many X=, player 2 chooses a number y from the set Y=. After that, player 2 pays player 1 the amount Wx, y) -2x 2 -y 2. Since player 2 seeks to minimize player 1's payoff, he determines min ( 2x 2 - y 2) = 2x 2- 1, i.e. in this case = 1. Player 1 seeks to mak-tag

Simulate your payment, therefore determines the maxi min Wh, y)1 =

xGX y er

- max (2x 2 - 1) = 2- 1 = 1, which is achieved when X = 1.

So the bottom net price of the game is vx- 1. Top clean

game pricev 2 =min - min (2 - y 2) = 2 - 1 = 1, i.e. in this

>eghehe yey

game v l \u003d v 2 \u003d l. So the net price of the game v= 1, while the saddle point is (x° = 1; y°=1).

Suppose now that Hee Y- open intervals, i.e. player 1 chooses xeA"=(0; 1), player 2 chooses ye 7= (0; 1). In this case, choosing X, close enough to 1, player 1 will be sure that he will receive a payoff no less than a number close to "=1; by choosing y close to 1, player 2 will not allow player 1's payoff to be much greater than the net value of the game v= 1.

The degree of closeness to the price of the game can be characterized by the number ?>0. Therefore, in the described game, we can talk about the optimality of pure strategies x°= 1, 0 = 1, respectively, players 1 and 2 up to an arbitrary number?>0. Dot (X", y E), where x e e X, y (. eY, in the endless antagonistic game is called z-equilibrium point (s.-saddle point), if for any strategies xTiger 1, ye Tigger 2 the following inequality holds: Wh, u.) - ? W x r , y (.) U(x t ., y) + ?. In this case, strategies x k. and at. called with,-optimal strategies. These strategies are optimal up to? in the sense that if a deviation from the optimal strategy cannot bring any benefit to the player, then his deviation from the c-optimal strategy can increase his payoff by no more than e.

If the game has no saddle point (c-saddle point), i.e. solutions in pure strategies, then optimal strategies can be sought among mixed strategies, which are used as functions of the probability distribution of the use of pure strategies by players.

Let F(x) is the probability distribution function of the use of pure strategies by player 1. If the number E, is the pure strategy of player 1, then F(x) = P(q where P(q -X)- the probability that a randomly chosen pure strategy E will not exceed X. The probability distribution function of applying pure strategies r| player 2: Q(y) = P(g.

Functions F(x) And Q(y) called mixed strategies players 1 and 2 respectively. If fx) And Q(y) are differentiable, then their derivatives exist, denoted respectively by f(x) And q(y)(functions of distribution density).

In general, the differential of the distribution function dF(x) expresses the probability that the strategy With, is in between x E, Similarly for player 2: dQ(y) means the probability that his strategy p is in the interval at g| y + dy. Then player 1's payoff is Wx, y) dF(x), and player 2's payoff is Wx, y) dQ(y).

Player 1's average payoff given Player 2's pure strategy y, can be obtained by integrating payments over all possible values X, those. on a single interval:

Player 1's average payoff given that both players use their mixed strategies F(x) And Q(y), will be equal to

By analogy with matrix games, the optimal mixed strategies of players and the price of the game are determined: if a pair of mixed strategies F*(x) And Q*(y) respectively, for players 1 and 2 are optimal, then for any mixed strategies F(x) And Q(y) the following ratios are valid:

If player 1 deviates from his strategy F*(x), then his average payoff cannot increase, but can decrease due to the rational actions of player 2. If player 2 retreats from his mixed strategy Q*(y), then the average payoff of player 1 can increase, but not decrease, due to more reasonable actions of player 1. The average payoff E(F*, Q*), received by player 1 when the players use optimal mixed strategies corresponds to the price of the game.

Then the lower cost of an infinite antagonistic game solved in mixed strategies can be defined as v x= check

min E(FQ), and the top price of the game as v 2 = minmax E(F, Q).

Q Q f

If there are such mixed strategies F*(x) And Q*(y) for players 1 and 2, respectively, for which the lower and upper prices of the game are the same, then F*(x) And Q*(y) it is natural to call the optimal mixed strategies of the corresponding players, a v=vx=v2- the price of the game.

In contrast to matrix games, the solution of an infinite antagonistic game does not exist for every function Shh, y). But the theorem is proved that any infinite antagonistic game with a continuous payoff function Wh, y) has a solution on the unit square (players have optimal mixed strategies), although there are no general methods for solving infinite antagonistic games, including continuous games. However, antagonistic infinite games with convex and concave continuous payoff functions are solved quite simply (they are called respectively convex And concave games).

Consider solving games with a convex payoff function. The solution of games with a concave payoff function is symmetrical.

convex function/variable X on the interval ( A; b) is called such a function for which the inequality

Where xx And x 2 - any two points from the interval (a; b);

X.1, A.2 > 0, and +X.2= 1.

If for / h * 0 D 2 * 0, the strict inequality always holds

then the function / is called strictly convex on (a; b).

A geometrically convex function depicts an arc, the graph of which is located below the chord subtending it. Analytically, the convexity of a twice differentiable function corresponds to the nonnegativity (and in the case of strict convexity, to the positivity) of its second derivative.

For concave functions, the properties are opposite; for them, the inequality /(/4X1 + A.2X2) > Kf(xi) +)-if(x 2) (> with strict concavity), and the second derivative / "(x)

It is proved that a continuous and strictly convex function on a closed interval takes on a minimum value only at one point of the interval. If Wh, y) is a continuous payoff function of player 1 on the unit square and strictly convex in at for any x, then there is a unique optimal pure strategy y=y° e for player 2, the price of the game is determined by the formula

and the value at 0 is defined as the solution of the following equation:

If the function Wh, y) is not strictly convex in y, then Player 2 will not have a unique optimal pure strategy.

The symmetric property also holds for strictly concave functions. If the function Wh, y) is continuous in both arguments and strictly concave in x for any y, then player 1 has a unique optimal strategy.

The price of the game is determined by the formula

and the pure optimal strategy x 0 of player 1 is determined from the equation

Based on these properties of infinite antagonistic games with convex or concave payoff functions, a general scheme for solving such games on a unit square (х e , y e ) is constructed. We present this scheme only for convex games, since it is symmetric for concave games.

1. Check function Wh, y) convexity in y (the second partial derivative must be greater than or equal to 0).

2. Determine y 0 from the relation v- minmax Wh, y) as value

y, where the minimax is reached.

3. Find a solution to the equation v = U(x, y 0) and make pairs of its solutions X And x 2, for which

4. Find parameter A from the equation

Parameter A determines the optimal strategy of player 1 and has the meaning of the probability of his choice of his pure strategy x x. The value 1 - a has the meaning of the probability that player 1 chooses his pure strategy x 2 .

Let us show by an example the use of this scheme for solving a game of this type. Let the payoff function in an infinite antagonistic game be given on the unit square and be equal to Wx, y) = =(x - y) 2 \u003d x 2 - 2 hu h-y 2 .

1. This function is continuous in X And y, and so this game has a solution. Function Wh, y) strictly convex y, because

Therefore, player 2 has the only pure optimal strategy y 0 .

2. We have v= min max (x - y) 2. To determine max (x 2 - 2xy X-y 2)

sequentially find the first and second partial derivatives of the payoff function with respect to x:

So the function U has a minimum for any y for x=y. This means that when xy - increases, and its maximum should be achieved at one of the extreme points x=0 or x= 1. Let's determine the values ​​of the function U at these points:

Then check (x - y) 2 \u003d max (y 2; 1 - 2y + y 2). Comparing "internal"

maxima in curly brackets, it is easy to see that at 2 > 1 - - 2y+y 2 , If y >*/ 2 and y 2 1 - 2 y+y 2 , If y "/ 2. This is more clearly represented by a graph (Fig. 2.5).

Rice. 2.5. Internal maximums of the payoff function U(x, y) = (x- at) 2

Therefore, the expression (x - y) 2 reaches its maximum at x=0 if y > 7 2 , and at x= 1 if at U 2:

Hence, v= min ( min y 2 ; min (1 - y) 2 ). Each of the

morning lows is reached at y=*/ 2 and takes the value Y 4 . Thus, the price of the game is r = Y 4 , and the optimal strategy for player 2 is:

3. Determine the optimal strategy of player 1 from the equation U(x, y 0)= v, those. for this game (x - Y 2) 2 \u003d Y 4. The solution to this equation is X| \u003d 0, x 2 \u003d 1.

They satisfy the conditions

4. Define the parameter a, i.e. the probability of player 1 using his pure strategy X] = 0. Let's make the equation a-1 + (1 - a) (-1)=0, whence a = Y 2 . Thus, the optimal strategy of player 1 is to choose his pure strategies 0 and 1 with probability 1 / 2 each. Problem solved.