antagonistic game. Solving matrix antagonistic games Principles for solving matrix antagonistic games
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 rather limited. Taking into account the above, it can be argued that problem situations of this magnitude most often have to be analyzed using 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
Moscow Power Engineering Institute
(Technical University)
Lab report
in game theory
"A search program for optimal strategies for a paired antagonistic game given in matrix form"
Completed by students
group A5-01
Ashrapov Daler
Ashrapova Olga
Basic concepts of game theory
Game theory designed to resolve conflict situations , i.e. situations in which the interests of two or more parties pursuing different goals collide.
If the goals of the parties are directly opposite, then they talk about antagonistic conflict .
game called a simplified formalized model of a conflict situation.
Playing a game once from start to finish is called party . The result of the party is payment (or win ).
The party is made up of moves , i.e. choosing players from a set of possible alternatives.
Moves can be personal and random.personal move , Unlike random , implies a conscious choice by the player of some option.
Games in which there is at least one personal move are called strategic .
Games in which all moves are random are called gambling .
When making a personal move, they also talk about strategies player, i.e. about the rule or set of rules that determine the choice of the player. At the same time, the strategy should be comprehensive, i.e. the choice must be determined for any possible situation during the course of the game.
Game theory challenge– finding the optimal strategies of the players, i.e. strategies that provide them with the maximum gain or minimum loss.
Classification of game-theoretic models
game n persons are usually referred to as, where 
is the set of strategies of the i-th player, 
- game payment.
In accordance with this designation, the following classification of game-theoretic models can be proposed:
Discrete (sets of strategies 
discrete)
Final
Endless
Continuous (sets of strategies 
continuous)
Endless
n persons ( 
)
Coalition (cooperative)
Non-cooperative (non-cooperative)
2 persons (paired)
Antagonistic (zero-sum games)
(the interests of the parties are opposite, i.e. the loss of one player is equal to the gain of the other)
Non-antagonistic
With complete information (if the player making a personal move knows the entire history of the game, i.e. all the moves of the opponent)
With incomplete information
With zero amount (total payment is zero)
With a non-zero sum
One-way (lotteries)
multi-way
Matrix representation of a paired antagonistic game
In this tutorial, we will consider antagonistic games of two persons
given in matrix form. This means that we know the set of strategies of the first player (player A){
A i },
i = 1,…,
m and the set of strategies of the second player (player B){
B j },
j = 1,...,
n, and the matrix A
= ||
a ij ||
the payoffs of the first player. Since we are talking about an antagonistic game, it is assumed that the gain of the first player is equal to the loss of the second. We consider that the matrix element a ij is the payoff of the first player when he chooses a strategy A i and the answer of the second player with the strategy B j. We will refer to such a game as 
, where m
- number of player strategies BUT,n
- number of player strategies AT. In general, it can be represented by the following table:
|
B 1 |
|
B j |
|
B n |
|
|
A 1 |
|
| |||
|
|
|
|
|
|
|
|
A i |
|
| |||
|
|
|
|
|
|
|
|
A m |
|
|
Example 1
As a simple example, consider a game in which the game consists of two moves.
1st move: Player BUT chooses one of the numbers (1 or 2) without telling the opponent about his choice.
2nd move: Player AT selects one of the numbers (3 or 4).
Outcome: Player selection BUT and AT add up. If the sum is even, then AT pays its value to the player BUT, if odd - vice versa, BUT pays the player AT.
This game can be represented as 
in the following way:
|
|
|
|
|
| ||
|
|
(choice 3)
(choice 4)
(choice 1)
(choice 2)It is easy to see that this game is antagonistic, in addition, it is a game with incomplete information, since player AT, making a personal move, it is not known what choice the player made BUT.
As noted above, the task of game theory is to find the optimal strategies of the players, i.e. strategies that provide them with the maximum gain or minimum loss. This process is called game decision .
When solving a game in matrix form, one should check the game for the presence saddle point . For this, two values are introduced:
is the lower bound for the price of the game, and
is the upper estimate of the price of the game.
The first player will most likely choose the strategy in which he will get the maximum gain among all possible answers of the second player, and the second one, on the contrary, will choose the one that minimizes his own loss, i.e. possible win of the first.
It can be proved that α ≤ V ≤ β , where V–game price , i.e., the probable payoff of the first player.
If the relation α
=
β
=
V, then they say that the game has a saddle point
, and solved in pure strategies
. In other words, there are a couple of strategies 
, giving the player BUTV.
Example 2
Let's return to the game we considered in Example 1 and check it for the presence of a saddle point.
|
|
|
|
|
|
| |||
|
| |||
|
|
(choice 3)
(choice 4)
(choice 1)
(choice 2)
For this game 
=
-5,
=
4,
, therefore, it has no saddle point.
Again, note that this game is an incomplete information game. In this case, you can only advise the player BUT choose a strategy 
, because in this case, he can get the largest payoff, however, provided that the player chooses AT strategies 
.
Example 3
Let's make some changes to the rules of the game from example 1. Let's give the player AT player selection information BUT. Then AT There are two additional strategies:
- a strategy that is beneficial to BUT. If choice A - 1, then AT chooses 3 if choice A - 2, then AT chooses 4;
- a strategy that is not beneficial for BUT. If choice A - 1, then AT chooses 4 if choice A - 2, then AT chooses 3.
|
|
|
|
|
|
|
|
| |||||
|
| |||||
|
|
(choice 3)
(choice 4)
(choice 1)
(choice 2)
This game is full of information.
In this case 
=
-5,
=
-5,
, hence the game has a saddle point 
. This saddle point corresponds to two pairs of optimal strategies: 
and 
. Game price V= -5.
It is obvious that for BUT this game is useless.
Examples 2 and 3 are a good illustration of the following theorem, proven in game theory:
Theorem 1
Every paired antagonistic game with perfect information is solved in pure strategies.
That. Theorem 1 says that any two-person game with perfect information has a saddle point and there is a pair of pure strategies 
, giving the player BUT sustainable gain equal to the price of the game V.
In the case of the absence of a saddle point, the so-called mixed strategies
:, where p i andq j are the probabilities of choosing strategies A i
and
B j the first and second players, respectively. The solution of the game in this case is a pair of mixed strategies 
maximizing the mathematical expectation of the price of the game.
A generalization of Theorem 1 to the case of a game with incomplete information is the following theorem:
Theorem 2
Any paired antagonistic game has at least one optimal solution, i.e., a pair of mixed strategies in the general case 
, giving the player BUT sustainable gain equal to the price of the game V, moreover α ≤
V ≤
β
.
In a special case, for a game with a saddle point, the solution in mixed strategies looks like a pair of vectors in which one element is equal to one, and the rest are equal to zero.
The simplest case, elaborated in detail in game theory, is a zero-sum finite pair game (an antagonistic game of two persons or two coalitions). Consider this game G, in which two players BUT and AT, having opposing interests: the gain of one is equal to the loss of the other. Since the player's payoff BUT is equal to the player's payoff In with opposite sign, we can only be interested in the payoff a player BUT. Naturally, BUT wants to maximize and AT - minimize a. For simplicity, let's mentally identify ourselves with one of the players (let it be BUT) and we will call him "we", and the player AT -"opponent" (of course, no real advantages for BUT does not follow from this). Let us have t possible strategies BUT 1 , A 2 , ..., BUT m, and the enemy n possible strategies AT 1 , AT 2 , ..; AT n(such a game is called a game t × n). Denote a ij our payoff if we use the strategy A i , and the enemy is a strategy B j .
Table 26.1
|
A i B j |
B 1 |
B 2 |
B n |
|
|
A 1 A 2 A m |
a 11 a 21 a m1 |
a 21 a m |
a 1 n a 2 n a mn |
Suppose that for each pair of strategies A<, AT, win (or average win) a, j we know. Then, in principle, it is possible to compile a rectangular table (matrix), which lists the strategies of the players and the corresponding payoffs (see table 26.1).
If such a table is compiled, then we say that the game G reduced to a matrix form (by itself, bringing the game to such a form can already be a difficult task, and sometimes almost impossible, due to the vast number of strategies). Note that if the game is reduced to a matrix form, then the multi-move game is actually reduced to a one-move game - the player is required to make only one move: choose a strategy. We will briefly denote the game matrix ( a ij).
Consider an example game G(4×5) in matrix form. At our disposal (to choose from) four strategies, the enemy has five strategies. The game matrix is given in table 26.2
Let's think about what strategy we (the player BUT) take advantage? Matrix 26.2 has the enticing payoff "10"; we are drawn to choose a strategy BUT 3 , at which we will get this "tidbit". But wait, the enemy isn't stupid either! If we choose a strategy BUT 3 , he, to spite us, will choose a strategy AT 3 , and we get some miserable payoff "1". No, choose a strategy BUT 3 it is forbidden! How to be? Obviously, based on the principle of caution (and it is the main principle of game theory), we must choose
Table 26.2
|
B j A i |
B 1 |
B 2 |
B 3 |
B 4 |
B 5 |
|
A 1 A 2 A 3 A 4 |
the strategy that our minimum gain is maximum. This is the so-called "minimax principle": act in such a way that, with the worst behavior of the enemy for you, you get the maximum gain.
We rewrite table 26.2 and in the right additional column we write down the minimum value of the payoff in each line, (line minimum); let's designate it for i-th row α i(see table 26.3).
Table 26.3
|
B j A i |
B 1 |
B 2 |
B 3 |
B 4 |
B 5 | |
|
A 1 A 2 A 3 A 4 | ||||||
|
β j |
Of all values α i(right column) the largest (3) is highlighted. It matches the strategy A four . Having chosen this strategy, we, in any case, can be sure that (for any behavior of the enemy) we will gain no less than 3. This value is our guaranteed gain; being careful, we can not get less than this (I may get more). This payoff is called the lower price of the game (or "maximin" - the maximum of the minimum payoffs). We will denote it a. In our case α = 3.
Now let us take the point of view of the enemy and argue for him. He's not some kind of pawn, but also reasonable! Choosing a strategy, he would like to give less, but he must count on our behavior, which is the worst for him. If he chooses a strategy AT 1 , we will answer him BUT 3 , and he will give 10; if he chooses B 2 - we will answer him BUT 2 , and he will give 8, etc. We add an additional lower row to table 26.3 and write in it the maximums of the columns β j. Obviously, a cautious adversary should choose the strategy that minimizes this value (the corresponding value of 5 is highlighted in Table 26.3). This value of β is the value of the gain, more than which a reasonable opponent will certainly not give us. It is called the upper price of the game (or "minimax" - the minimum of the maximum winnings). In our example, β = 5 and is achieved with the opponent's strategy B 3 .
So, based on the principle of caution (the reinsurance rule “always count on the worst!”), We must choose a strategy BUT 4 , and the enemy - strategy AT 3 . Such strategies are called "minimax" (following from the minimax principle). As long as both parties in our example stick to their minimax strategies, the payoff will be a 43 = 3.
Now imagine for a moment that we have learned that the enemy is pursuing a strategy AT 3 . Come on, let's punish him for this and choose a strategy BUT 1 - we'll get 5, which isn't that bad. But after all, the enemy is also not a miss; let him know that our strategy BUT 1 ; he is also quick to choose AT 4 , reducing our payoff to 2, etc. (partners “rushed about strategies”). In a word, minimax strategies in our example unstable in relation to to information about the behavior of the other party; these strategies do not have the equilibrium property.
Is it always like this? No not always. Consider an example with the matrix given in Table 26.4.
In this example, the lower price of the game is equal to the upper one: α = β = 6. What follows from this? Minimax Player Strategies BUT and AT will be sustainable. As long as both players stick to them, the payoff is 6. Let's see what happens if we (BUT) know that the enemy (AT)
Table 26.4
|
Bj A i |
B 1 |
B 2 |
B 3 |
B 4 | |
|
A 1 A 2 A 3 | |||||
|
β j |
sticks to the strategy B 2 ? And exactly nothing will change. Because any deviation from the strategy BUT 2 can only make our situation worse. Likewise, information received by the enemy will not cause him to retreat from his strategy. AT 2 . Pair of strategies BUT 2 , B 2 possesses the property of equilibrium (a balanced pair of strategies), and the payoff (in our case, 6) achieved with this pair of strategies is called the “saddle point of the matrix” 1). A sign of the presence of a saddle point and a balanced pair of strategies is the equality of the lower and upper prices of the game; the common value of α and β is called the price of the game. We will label it v:
α = β = v
Strategies A i , B j(in this case BUT 2 , AT 2 ), for which this payoff is achieved are called optimal pure strategies, and their totality is called a solution to the game. In this case, the game itself is said to be solved in pure strategies. Both sides BUT and AT one can indicate their optimal strategies under which their position is the best possible. What is a player BUT in this case, 6 wins, and the player AT - loses 6, - well, These are the conditions of the game: they are beneficial for BUT and disadvantageous for AT
1) The term "saddle point" is taken from geometry - this is the name of the point on the surface, where the minimum along one coordinate and the maximum along the other are simultaneously reached.
The reader may have a question: why are optimal strategies called “pure”? Looking ahead a little, let's answer this question: there are "mixed" strategies, which consist in the fact that the player uses not one strategy, but several, alternating them randomly. So, if we allow, in addition to pure ones, also mixed strategies, any end game has a solution - an equilibrium point. But we are still talking about the atom.
The presence of a saddle point in the game is far from being the rule; rather, it is the exception. Most games do not have a saddle point. However, there is a variety of games that always have a saddle point and, therefore, are solved in pure strategies. These are the so-called "games with complete information". A game with a shelf of information is a game in which each player knows the entire history of its development, that is, the results of all previous moves, both personal and random, at each personal move. Examples of games with complete information are checkers, chess, tic-tac-toe, etc.
In game theory, it is proved that every game with complete information has a saddle point, and hence can be solved in pure strategies. In every game with perfect information, there is a pair of optimal strategies that gives a stable payoff equal to the chain of the game v. If such a game consists only of personal moves, then when each player applies his own optimal strategy, it must end in a quite definite way - with a payoff equal to the price of the game. So, if the solution of the game is known, the game itself loses its meaning!
Let's take an elementary example of a game with complete information: two players alternately place nickels on a round table, choosing arbitrarily the position of the center of the coin (mutual overlapping of coins is not allowed). The winner is the one who puts the last penny (when there is no room for others). It is easy to see that the outcome of this game is essentially a foregone conclusion. There is a certain strategy that ensures that the player who puts the coin first wins. Namely, he must first place a nickel on the center of the table, and then respond to each move of the opponent with a symmetrical move. Obviously, no matter how the opponent behaves, he cannot avoid losing. The situation is exactly the same with chess and games with complete information in general: any of them, written in matrix form, has a saddle point, and hence the solution is in pure strategies, and, therefore, makes sense only as long as this solution not found. Let's say a chess game is either always ends with White winning, or always - black wins, or always - a draw, only by what exactly - we don't know yet (fortunately for chess lovers). Let's add one more thing: we will hardly know in the foreseeable future, because the number of strategies is so huge that it is extremely difficult (if not impossible) to reduce the game to a matrix form and find a saddle point in it.
Now let's ask ourselves what to do if the game does not have a saddle point: α ≠ β ? Well, if each player is forced to choose one - the only pure strategy, then there is nothing to do: one must be guided by the minimax principle. Another thing is if it is possible to “mix” a set of strategies, alternate randomly with some probabilities. The use of mixed strategies is conceived in this way: the game is repeated many times; before each game of the game, when the player is given a personal move, he "entrusts" his choice to chance, "throws lots", and takes the strategy that fell out (we already know how to organize the lot from the previous chapter).
Mixed strategies in game theory are a model of changeable, flexible tactics, when none of the players knows how the opponent will behave in a given game. This tactic (albeit usually without any mathematical justification) is often used in card games. Let us note at the same time that the best way to hide your behavior from the enemy is to give it a random character and, therefore, not to know in advance what you will do.
So, let's talk about mixed strategies. We will denote the mixed strategies of the players BUT and AT respectively S A = ( p 1 , R 2 , ..., p m), S B = (q 1 , q 2 , …, q n), where p 1 , p 2 , …, p m(forming a total of one) - the probabilities of the player using BUT strategies BUT 1 , A 2 ,… , A m ; q 1 , q 2 , …, q n- probabilities of use by the player AT strategies AT 1 , AT 2 , ..., AT n . In a particular case, when all probabilities, except for one, are equal to zero, and this one is equal to one, the mixed strategy turns into a pure one.
There is a basic theorem of game theory: any two-person zero-sum finite game has at least one solution - pair of optimal strategies, generally mixed 
and corresponding price v.
Pair of optimal strategies 
forming the solution of the game has the following property: if one of the players adheres to his optimal strategy, then it cannot be profitable for the other to deviate from his own. This pair of strategies forms a kind of equilibrium in the game: one player wants to turn the gain to a maximum, the other to a minimum, each pulls in his own direction, and, with reasonable behavior of both, an equilibrium and a stable gain are established. v. If a v > 0, then the game is profitable for us if v<
0
-
for the enemy; at v= 0 the game is “fair”, equally beneficial for both participants.
Consider an example of a game without a saddle point and give (without proof) its solution. The game is as follows: two players BUT and AT at the same time and without saying a word show one, two or three fingers. Winning is decided by the total number of fingers: if it is even, wins BUT and receives from AT an amount equal to this number; if odd, then vice versa BUT pays AT an amount equal to that number. What should the players do?
Let's create a game matrix. In one game, each player has three strategies: show one, two or three fingers. The 3×3 matrix is given in Table 26.5; the extra right column shows the row minima, and the extra bottom row shows the column maxima.
The lower price of the game α = - 3 and corresponds to the strategy A 1 . This means that with reasonable, cautious behavior, we guarantee that we will not lose more than 3. Small consolation, but still better than, say, a win of 5, which occurs in some cells of the matrix. Bad for us, the player BUT... But let's console ourselves:
the opponent's position seems to be even worse: the lower cost of the game is β = 4, i.e., with reasonable behavior, he will give us at least 4. In general, the position is not very good - neither for one nor for the other side. But let's see if it can be improved? It turns out you can. If each side uses not one pure strategy, but a mixed one, in which
Table 26.5
|
Bj A i |
B 1 |
B 2 |
B 3 | |
|
A 1 A 2 A 3 | ||||
|
β j |
the first and third enter with probability 1/4, and the second - with probability 1/2, i.e.
then the average payoff will be steadily equal to zero (which means that the game is “fair” and equally beneficial to both sides). Strategies 
form a solution to the game, and its price v= 0. How did we find this solution? This is a different question. In the next section, we show how finite games are generally solved.
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 Bj. If the game consists only of personal moves, then the choice of strategies Ai and Bj 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 Bj).
If the game contains, in addition to personal random moves, then the payoff for a pair of strategies Ai, Bj 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 ( Bj):
| 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 chess game the number of possible strategies is so large that the construction of the 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 four . 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 AT 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 AT.
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 AT. 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 AT):
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 BUT will choose a strategy A i, then all its possible payoffs will be elements i-th row of the matrix FROM. Worst for a player BUT case when the player AT applies a strategy appropriate to minimum element of this line, the player's payoff BUT will be equal to the number.
Therefore, in order to get the maximum payoff, the player BUT you need to choose one of the strategies for which the number maximum.
The decision-making problem, considered within the framework of the system approach, contains three main components: the system, the control subsystem and the environment are identified in it. Now we turn to the study of decision-making problems, in which the system is affected by not one, but several control subsystems, each of which has its own goals and possibilities of action. This approach to decision making is called game-theoretic, and the mathematical models of the corresponding interactions are called games. Due to the difference in the goals of the control subsystems, as well as certain restrictions on the possibility of exchanging information between them, these interactions are of a conflict nature. Therefore, any game is a mathematical model of conflict. We restrict ourselves to the case when there are two control subsystems. If the goals of the systems are opposite, the conflict is called antagonistic, and the mathematical model of such a conflict is called antagonistic game..
In game-theoretic terminology, the 1st control subsystem is called player 1, 2nd control subsystem - player 2, sets
their alternative actions are called sets of strategies these players. Let X- set of player 1 strategies, Y- many strategies
player 2. The state of the system is uniquely determined by the choice of control actions by subsystems 1 and 2, that is, the choice of strategies
x∈X and y∈Y. Let F(x,y) - utility estimate for player 1 of that state
the system to which it passes when player 1 chooses a strategy X and
player 2 strategy at. Number F(x,y) is called winning player 1 in the situation ( x,y), and the function F- player 1 payoff function. Player win
1 is also the loss of player 2, that is, the value that the first player seeks to increase, and the second - to reduce. That's what it is
manifestation of the antagonistic nature of the conflict: the interests of the players are completely opposite (what one wins, the other loses).
An antagonistic game is naturally set by the system G=(X, Y, F).
Note that formally the antagonistic game is actually set in the same way as the problem of making a decision under conditions of uncertainty - if
identify the control subsystem 2 with the environment. The substantive difference between the control subsystem and the environment is that
the behavior of the first is purposeful. If, when compiling a mathematical model of a real conflict, we have a reason (or intention) to consider the environment as an adversary, the purpose of which is to bring
us the maximum harm, then such a situation can be represented as an antagonistic game. In other words, the antagonistic game can be interpreted as an extreme case of the ZPR under conditions of uncertainty,
characterized by the fact that the environment is seen as an adversary with a goal. At the same time, we must limit the types of hypotheses about the behavior of the environment.
The most substantiated here is the hypothesis of extreme caution, when, when making a decision, we rely on the worst possible scenario for us to act in the environment.
Definition. If a X and Y are finite, then the antagonistic game is called matrix. In the matrix game, we can assume that X={1,…,n},
Y={1,…,m) and put aij=F(i,j). Thus, the matrix game is completely determined by the matrix A=(aij), i=1,…,n, j=1,…,m.
Example 3.1. Game with two fingers.
Two people at the same time show one or two fingers and call the number 1 or 2, which, according to the speaker, means the number
fingers shown to others. After the fingers are shown and the numbers are named, the winnings are distributed according to the following rules:
if both guessed or both did not guess how many fingers their opponent showed, the payoff of each is equal to zero; if only one has guessed correctly, then the opponent pays the guesser the amount of money proportional to the total number of shown
This is an antagonistic matrix game. Each player has four strategies: 1- show 1 finger and say 1, 2- show 1 finger and say 2, 3-
show 2 fingers and say 1, 4 - show 2 fingers and say 2. Then the payoff matrix A=(aij), i= 1,…, 4, j= 1,…, 4 is defined as follows:
a12= 2, a21 = – 2, a13=a42=–3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 otherwise.
Example 3.2. Discrete duel-type game.
Duel-type tasks describe, for example, the struggle of two players,
each of which wants to perform some one-time action (the release of a consignment of goods on the market, an application for purchase at an auction) and chooses a time for this. Let the players move towards each other on n steps. After each step taken, the player may or may not shoot at the opponent. Each person can have only one shot. It is believed that the probability of hitting the enemy if you advance by k n =5 has the form
