Antagonistic games with continuous strategies. Solving matrix antagonistic games Solving antagonistic games online

A two-person zero-sum game is called, in which each of them has a finite set of strategies. The rules of the matrix game are determined by the payoff matrix, whose elements are the payoffs of the first player, which are also the losses of the second player.

Matrix game is an antagonistic game. The first player receives the maximum guaranteed (not dependent on the behavior of the second player) payoff equal to the price of the game, similarly, the second player achieves the minimum guaranteed loss.

Under strategy is understood as a set of rules (principles) that determine the choice of a variant of actions for each personal move of a player, depending on the current situation.

Now about everything in order and in detail.

Payoff matrix, pure strategies, game price

AT matrix game its rules are determined payoff matrix .

Consider a game in which there are two participants: the first player and the second player. Let the first player have m pure strategies, and at the disposal of the second player - n pure strategies. Since a game is being considered, it is natural that there are wins and losses in this game.

AT payment matrix the elements are numbers expressing the gains and losses of the players. Wins and losses can be expressed in points, money or other units.

Let's create a payoff matrix:

If the first player chooses i-th pure strategy, and the second player j-th pure strategy, then the payoff of the first player is aij units, and the loss of the second player is also aij units.

Because aij + (- a ij ) = 0, then the described game is a zero-sum matrix game.

The simplest example of a matrix game is tossing a coin. The rules of the game are as follows. The first and second players toss a coin and the result is heads or tails. If heads and heads or tails or tails are rolled at the same time, then the first player will win one unit, and in other cases he will lose one unit (the second player will win one unit). The same two strategies are at the disposal of the second player. The corresponding payoff matrix would be:

The task of game theory is to determine the choice of the strategy of the first player, which would guarantee him the maximum average gain, as well as the choice of the strategy of the second player, which would guarantee him the maximum average loss.

How is a strategy chosen in a matrix game?

Let's look at the payoff matrix again:

First, we determine the payoff of the first player if he uses i th pure strategy. If the first player uses i-th pure strategy, then it is logical to assume that the second player will use such a pure strategy, due to which the payoff of the first player would be minimal. In turn, the first player will use such a pure strategy that would provide him with the maximum payoff. Based on these conditions, the payoff of the first player, which we denote as v1 , is called maximin win or lower game price .

At for these values, the first player should proceed as follows. From each line, write out the value of the minimum element and choose the maximum from them. Thus, the payoff of the first player will be the maximum of the minimum. Hence the name - maximin win. The line number of this element will be the number of the pure strategy chosen by the first player.

Now let's determine the loss of the second player if he uses j-th strategy. In this case, the first player uses his own pure strategy, in which the loss of the second player would be maximum. The second player must choose such a pure strategy in which his loss would be minimal. The loss of the second player, which we denote as v2 , is called minimax loss or top game price .

At solving problems on the price of the game and determining the strategy to determine these values ​​for the second player, proceed as follows. From each column, write out the value of the maximum element and choose the minimum from them. Thus, the loss of the second player will be the minimum of the maximum. Hence the name - minimax gain. The column number of this element will be the number of the pure strategy chosen by the second player. If the second player uses "minimax", then regardless of the choice of strategy by the first player, he will lose at most v2 units.

Example 1

.

The largest of the smallest elements of the rows is 2, this is the lower price of the game, the first row corresponds to it, therefore, the maximin strategy of the first player is the first. The smallest of the largest elements of the columns is 5, this is the upper price of the game, the second column corresponds to it, therefore, the minimax strategy of the second player is the second.

Now that we have learned how to find the lower and upper price of the game, the maximin and minimax strategies, it's time to learn how to designate these concepts formally.

So, the guaranteed payoff of the first player is:

The first player must choose a pure strategy that would provide him with the maximum of the minimum payoffs. This gain (maximin) is denoted as follows:

.

The first player uses his pure strategy so that the loss of the second player is maximum. This loss is defined as follows:

The second player must choose his pure strategy so that his loss is minimal. This loss (minimax) is denoted as follows:

.

Another example from the same series.

Example 2 Given a matrix game with a payoff matrix

.

Determine the maximin strategy of the first player, the minimax strategy of the second player, the lower and upper price of the game.

Decision. To the right of the payoff matrix, we write out the smallest elements in its rows and mark the maximum of them, and from the bottom of the matrix - the largest elements in the columns and select the minimum of them:

The largest of the smallest elements of the rows is 3, this is the lower price of the game, the second row corresponds to it, therefore, the maximin strategy of the first player is the second. The smallest of the largest elements of the columns is 5, this is the upper price of the game, the first column corresponds to it, therefore, the minimax strategy of the second player is the first.

Saddle point in matrix games

If the upper and lower price of the game are the same, then the matrix game is considered to have a saddle point. The converse is also true: if a matrix game has a saddle point, then the upper and lower prices of the matrix game are the same. The corresponding element is both the smallest in the row and the largest in the column and is equal to the price of the game.

Thus, if , then is the optimal pure strategy of the first player, and is the optimal pure strategy of the second player. That is, equal lower and upper prices of the game are achieved on the same pair of strategies.

In this case the matrix game has a solution in pure strategies .

Example 3 Given a matrix game with a payoff matrix

.

Decision. To the right of the payoff matrix, we write out the smallest elements in its rows and mark the maximum of them, and from the bottom of the matrix - the largest elements in the columns and select the minimum of them:

The lower price of the game is the same as the upper price of the game. Thus, the price of the game is 5. That is . The price of the game is equal to the value of the saddle point. The maximin strategy of the first player is the second pure strategy, and the minimax strategy of the second player is the third pure strategy. This matrix game has a solution in pure strategies.

Solve the matrix game problem yourself, and then see the solution

Example 4 Given a matrix game with a payoff matrix

.

Find the lower and upper price of the game. Does this matrix game have a saddle point?

Matrix games with optimal mixed strategy

In most cases, the matrix game does not have a saddle point, so the corresponding matrix game has no pure strategy solutions.

But it has a solution in optimal mixed strategies. To find them, it must be assumed that the game is repeated enough times that, based on experience, one can guess which strategy is preferable. Therefore, the decision is associated with the concept of probability and average (expectation). In the final solution, there is both an analog of the saddle point (that is, the equality of the lower and upper prices of the game), and an analog of the strategies corresponding to them.

So, in order for the first player to get the maximum average gain and for the second player to have the minimum average loss, pure strategies should be used with a certain probability.

If the first player uses pure strategies with probabilities , then the vector is called the mixed strategy of the first player. In other words, it is a "mixture" of pure strategies. The sum of these probabilities is equal to one:

.

If the second player uses pure strategies with probabilities , then the vector is called the mixed strategy of the second player. The sum of these probabilities is equal to one:

.

If the first player uses a mixed strategy p, and the second player - a mixed strategy q, then it makes sense expected value the first player wins (the second player loses). To find it, you need to multiply the first player's mixed strategy vector (which will be a one-row matrix), the payoff matrix, and the second player's mixed strategy vector (which will be a one-column matrix):

.

Example 5 Given a matrix game with a payoff matrix

.

Determine the mathematical expectation of the first player's gain (the second player's loss), if the mixed strategy of the first player is , and the mixed strategy of the second player is .

Decision. According to the formula for the mathematical expectation of the first player's gain (loss of the second player), it is equal to the product of the first player's mixed strategy vector, the payoff matrix, and the second player's mixed strategy vector:

The first player is called such a mixed strategy that would provide him with the maximum average payoff if the game is repeated a sufficient number of times.

Optimal mixed strategy The second player is called such a mixed strategy that would provide him with the minimum average loss if the game is repeated a sufficient number of times.

By analogy with the notation of maximin and minimax in the cases of pure strategies, optimal mixed strategies are denoted as follows (and are linked to the mathematical expectation, that is, the average, of the first player's gain and the second player's loss):

,

.

In this case, for the function E there is a saddle point , which means equality.

In order to find the optimal mixed strategies and saddle point, i.e. solve the matrix game in mixed strategies , you need to reduce the matrix game to a linear programming problem, that is, to an optimization problem, and solve the corresponding linear programming problem.

Reduction of a matrix game to a linear programming problem

In order to solve a matrix game in mixed strategies, you need to compose a straight line linear programming problem and its dual task. In the dual problem, the augmented matrix, which stores the coefficients of variables in the constraint system, constant terms, and coefficients of variables in the goal function, is transposed. In this case, the minimum of the goal function of the original problem is associated with the maximum in the dual problem.

Goal function in direct linear programming problem:

.

The system of constraints in the direct problem of linear programming:

Goal function in the dual problem:

.

The system of constraints in the dual problem:

Denote the optimal plan of the direct linear programming problem

,

and the optimal plan of the dual problem is denoted by

Linear forms for the corresponding optimal designs will be denoted by and ,

and you need to find them as the sum of the corresponding coordinates of the optimal plans.

In accordance with the definitions of the previous section and the coordinates of optimal plans, the following mixed strategies of the first and second players are valid:

.

Mathematicians have proven that game price is expressed in terms of linear forms of optimal plans as follows:

,

that is, it is the reciprocal of the sums of the coordinates of the optimal plans.

We, practitioners, can only use this formula to solve matrix games in mixed strategies. Like formulas for finding optimal mixed strategies respectively the first and second players:

in which the second factors are vectors. Optimal mixed strategies are also vectors, as we already defined in the previous paragraph. Therefore, multiplying the number (the price of the game) by the vector (with the coordinates of the optimal plans), we also get a vector.

Example 6 Given a matrix game with a payoff matrix

.

Find the price of a game V and optimal mixed strategies and .

Decision. We compose the linear programming problem corresponding to this matrix game:

We get the solution of the direct problem:

.

We find the linear form of optimal plans as the sum of the found coordinates.

Send your good work in the knowledge base is simple. Use the form below

Students, graduate students, young scientists who use the knowledge base in their studies and work will be very grateful to you.

Introduction

1. Theoretical part

1.3 Game order 2v2

1.4 Algebraic method

1.5 Graphical method

1.6 Games 2xn or mx2

1.7 Solving games by the matrix method

2. Practical part

2.2 2xn and mx2 games

2.3 Matrix method

2.4 Brown method

Analysis of results

Introduction

The antagonistic game is a zero-sum game. An antagonistic game is a non-cooperative game in which two players participate, whose payoffs are opposite.

Formally, an antagonistic game can be represented by a triple , where X and Y are the sets of strategies of the first and second players, respectively, F is the payoff function of the first player, which associates each pair of strategies (x, y), where is a real number corresponding to the utility of the first player in realizing this situation.

Since the interests of the players are opposite, the function F simultaneously represents the loss of the second player.

Historically, antagonistic games are the first class of mathematical models of game theory, which were used to describe gambling. It is believed that thanks to this subject of research, game theory got its name. Currently, antagonistic games are considered as part of a wider class of non-cooperative games.

1. Theoretical part

1.1 Basic definitions and provisions of the game

The game is characterized by a system of rules that determine the number of participants in the game, their possible actions and distribution of winnings depending on their behavior and outcomes. A player is considered to be one participant or a group of participants in the game who have some common interests for them that do not coincide with the interests of other groups. Therefore, not every participant is considered a player.

The rules or conditions of the game determine the possible behaviors, choices and moves for players at any stage of the development of the game. To make a choice for the player means to stop at one of his possibilities of behavior. The player then makes that choice with moves. To make a move means at a certain stage of the game to make all or part of the choice at once, depending on the possibilities provided for by the rules of the game. Each player at a certain stage of the game makes a move according to the choice made. The other player, knowing or not knowing about the first player's choice, also makes a move. Each of the players tries to take into account information about the past development of the game, if such a possibility is allowed by the rules of the game.

A set of rules that unambiguously tell the player what choice he should make at each move, depending on the situation that has developed as a result of the game, is called the player's strategy. Strategy in game theory means a certain complete plan of action for the player, showing how he should act in all possible cases of the development of the game. Strategy means the totality of all indications for any state of information available to the player at any stage of the development of the game. This already shows that strategies can be good and bad, successful and unsuccessful, etc.

There will be a zero-sum game when the sum of the payoffs of all players in each of its games is zero, i.e., in a zero-sum game, the total capital of all players does not change, but is redistributed among the players depending on the resulting outcomes. Thus, many economic and military situations can be viewed as zero-sum games.

In particular, a zero-sum game of two players is called antagonistic, since the goals of the players in it are directly opposite: the gain of one player occurs only at the expense of the loss of the other.

1.1.1 Definition, examples and solutions of matrix games in pure strategies

The two-player zero-sum matrix game can be viewed as the following abstract two-player game.

The first player has m strategies i =1, 2,…, m, the second has n strategies j = 1, 2,…, n. Each pair of strategies (i, j) is assigned a number a ij , which expresses the payoff of the first player due to the second player if the first player uses his i-th strategy, and the second - its j-th strategy.

Each of the players makes one move: the first player chooses his i-th strategy (i = 1, 2, ..., m), the second --your j-th strategy (j = 1, 2,…, n), after which the first player receives payoff a ij at the expense of the second player (if a ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

Each strategy of the player i = 1, 2,…, t; j = 1, 2,…, n is often called a pure strategy.

A zero-sum matrix game of two players will be referred to simply as a matrix game. Obviously, the matrix game belongs to antagonistic games. It follows from its definition that to define a matrix game, it suffices to specify a matrix A = (a ij) of the order of m of the payoffs of the first player.

Considering the payoff matrix

then the execution of each game of the matrix game with matrix A is reduced to the choice by the first player i-th line, and by the second player in the j-th column and the first player (at the expense of the second) receives the payoff located in the matrix A at the intersection of the i-th row and the j-th column.

To formalize a real conflict situation in the form of a matrix game, it is necessary to identify and renumber the pure strategies of each player and compile a payoff matrix.

The next step is to determine the optimal strategies and payoffs of the players.

The main thing in the study of games is the concept of optimal strategies for players. This concept intuitively has the following meaning: a player's strategy is optimal if the application of this strategy provides him with the greatest guaranteed payoff for all possible strategies of the other player. Based on these positions, the first player examines the matrix A of his payoffs according to the formula (1.1) as follows: for each value i (i = 1, 2, ..., m), the minimum payoff value is determined depending on the strategies used by the second player

(i = 1, 2,..., m) (1.2)

i.e., the minimum payoff for the first player is determined, provided that he applies his i -th pure strategy, then from these minimum payoffs such a strategy i=i 0 is found for which this minimum payoff will be maximum, i.e. is found

Definition. The number b determined by formula (1.3) is called the lower net cost of the game and shows what minimum payoff the first player can guarantee himself by applying his pure strategies for all possible actions of the second player.

The second player, with his optimal behavior, should strive, if possible, to minimize the payoff of the first player at the expense of his strategies. Therefore, for the second player, we find

i.e., the maximum payoff of the first player is determined, provided that the second player applies his j-th clean strategy, then the second player finds his own j = j 1 strategy for which the first player receives the minimum payoff, i.e., finds

Definition. The number β determined by formula (1.5) is called the net upper cost of the game and shows what maximum gain the first player can guarantee himself due to his strategies. In other words, by applying his pure strategies, the first player can secure a payoff of at least b, and the second player, by applying his pure strategies, can prevent the first player from winning more than c.

Definition. If in a game with matrix A the lower and upper net prices of the game coincide, i.e., b = c, then this game is said to have a saddle point in pure strategies and a net game price:

n = b = c (1.6)

A saddle point is a pair of pure strategies () of the first and second players, respectively, under which equality is achieved

The concept of a saddle point has the following meaning: if one of the players adheres to the strategy corresponding to the saddle point, then the other player cannot do better than to adhere to the strategy corresponding to the saddle point. Bearing in mind that the best behavior of the player should not lead to a decrease in his payoff, and the worst behavior may lead to a decrease in his payoff, these conditions can be written mathematically in the form of the following relations:

where i, j are any pure strategies of the first and second players, respectively; (i 0 , j 0) -- strategies forming a saddle point. Below we will show that the definition of a saddle point is equivalent to conditions (1.8).

Thus, based on (1.8), the saddle element is the minimum in the i 0 -th row and the maximum in the j 0 -th column in the matrix A. Finding the saddle point of the matrix A is easy: in the matrix A, successively in each row, find the minimum element and check if this element is the maximum in its column. If it is such, then it is a saddle element, and the pair of strategies corresponding to it forms a saddle point. A pair of pure strategies (i 0 , j 0) of the first and second players, forming a saddle point and a saddle element, is called a solution to the game.

Pure strategies i 0 and j 0 forming a saddle point are called optimal pure strategies of the first and second players, respectively.

Theorem 1. Let f (x, y) be a real function of two variables x A and y B and exist

then b = c.

Proof. From the definition of minimum and maximum, it follows that

Since x is arbitrary on the left side of (1.11), then

On the right-hand side of inequality (1.12), y is arbitrary, so

Q.E.D.

In particular, the matrix () is a special case of the function f (x, y), i.e. if we put x = i, y = j, = f (x, y), then from Theorem 1 we get that the lower net price is not exceeds the upper net value of the game in the matrix game.

Definition. Let f (x, y) be a real function of two variables x A and y B. A point (x 0, y 0) is called a saddle point for the function f (x, y) if the following inequalities hold:

f (x, y 0) f (x 0, y 0) f (x 0, y) (1.14)

for any x A and y B.

1.2 Optimal mixed strategies and their properties

The study of a matrix game begins with finding its saddle point in pure strategies. If a matrix game has a saddle point in pure strategies, then finding this point ends the study of the game. If in the matrix game there is no saddle point in pure strategies, then we can find the lower and upper pure prices of this game, which indicate that the first player should not hope for a payoff greater than the upper price of the game, and can be sure of receiving a payoff no less than the lower price of the game. Such recommendations regarding the behavior of players in a matrix game without a saddle point in pure strategies cannot satisfy researchers and practitioners. An improvement in the solution of matrix games should be sought in the use of the secrecy of the application of pure strategies and the possibility of repeated repetition of games in the form of parties. So, for example, a series of games of chess, checkers, football are played, and each time the players apply their strategies in such a way that their opponents are not aware of their content, and along the way achieve certain payoffs on average by playing the entire series of games. These payoffs are, on average, greater than the lower price of the game and less than the upper price of the game. The larger this average value, the better strategy applied by the player. Therefore, the idea arose to apply pure strategies randomly, with a certain probability. This fully ensures the secrecy of their use. Each player can change the probabilities of applying his pure strategies in such a way as to maximize his average payoff and obtain optimal strategies along the way. This idea led to the concept of mixed strategy.

Definition. The mixed strategy of a player is the complete set of probabilities of applying his pure strategies.

Thus, if the first player has m pure strategies 1, 2, … i, … m, then his mixed strategy x is a set of numbers x = (x 1 , x 2 , ..., x i ,…, x t ) satisfying the relations

x i 0 (i = 1, 2, ... , m), = 1. (1.15)

Similarly, for the second player, who has n pure strategies, the mixed strategy y is the set of numbers y = (y 1 ,…, y j , … y n) satisfying the relations

y j 0 (j = 1, 2, ... , n), = 1. (1.16)

Since each time a player uses one pure strategy precludes the use of another, pure strategies are incompatible events. In addition, they are the only possible events.

Clearly, a pure strategy is a special case of a mixed strategy. Indeed, if in a mixed strategy any i-th net strategy is applied with probability one, then all other pure strategies are not applied. And this i-th pure strategy is a special case of a mixed strategy. To maintain secrecy, each player applies his own strategies regardless of the choice of the other player.

Definition. The average payoff of the first player in the matrix game with matrix A is expressed as the mathematical expectation of his payoffs

E (A, x, y) = (1.20)

Obviously, the average payoff of the first player is a function of two sets of variables x and y. The first player aims to maximize his average payoff E (A, x, y) by changing his mixed strategies x, and the second player seeks to make E (A, x, y) minimal through his mixed strategies, i.e. e. to solve the game, it is necessary to find such x, y for which the upper price of the game is reached.

1.3 Order 22 game

A matrix game of order 22 is given by the following payoff matrix for the first player:

The solution of this game should begin with finding a saddle point in pure strategies. To this end, find the minimum element in the first row and check if it is the maximum in its column. If such an element is not found, then the second line is checked in the same way. If such an element is found in the second line, then it is a saddle element.

By finding a saddle element, if there is one, the process of finding its solution ends, since in this case the price of the game is found - a saddle element and a saddle point, i.e. a pair of pure strategies for the first and second players, constituting optimal pure strategies. If there is no saddle point in pure strategies, then it is necessary to find a saddle point in mixed strategies, which necessarily exists according to the main theorem of matrix games.

Denote by x=(x 1 ,x 2), y=(y 1 ,y 2) the mixed strategies of the first and second players, respectively. Recall that x 1 means the probability of the first player using his first strategy, and x 2 \u003d 1 - x 1 is the probability of using his second strategy. Similarly for the second player: 1 - the probability of using the first strategy, y 2 = 1 - 1 - the probability of using the second strategy.

According to the corollary of the theorem, for the optimality of mixed strategies x and y it is necessary and sufficient that for non-negative x 1 , x 2 , y 1 , y 2 the following relations hold:

We now show that if the matrix game has no saddle point in pure strategies, then these inequalities must turn into equalities:

Indeed. Let the game have no saddle point in pure strategies, then the optimal values ​​of mixed strategies satisfy the inequalities

0<<1, 0<< 1,

0< <1, 01. (1.25)

Suppose that both inequalities from (1.22) are strict

then, according to the theorem, y 1 = y 2 = 0, which contradicts conditions (1.25).

It can be proved similarly that both inequalities in (1.23) cannot be strict inequalities.

Suppose now that one of the inequalities (1.22) can be strict, for example, the first

This means that according to the theorem y 1 = 0, y 2 =1. Therefore, from (1.23) we obtain

If both inequalities (1.24) are strict, then by the theorem x1 = x2 = 0, which contradicts (1.25). But if a 12 a 22 , then one of the inequalities (1.27) is strict, and the other is an equality. Moreover, the equality will hold for the larger element from a 12 and a 22 , i.e. one inequality from (1.27) must be strict. For example a 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Thus, it is shown that if the matrix game has no saddle point in pure strategies, then inequalities (1.22) turn into equalities for the optimal strategies of the first player. Similar arguments about inequalities (1.23) will lead to the fact that in this case the inequalities (1.23) must be equalities.

So, if a matrix game of order 22 has no saddle point, then the optimal mixed strategies of the players and the price of the game can be determined by solving the system of equations (1.24). It is also established that if in a 2x2 matrix game one of the players has an optimal pure strategy, then the other player also has an optimal pure strategy.

Therefore, if a matrix game does not have a saddle point in pure strategies, then it must have a solution in mixed strategies, which are determined from equations (1.24). System solution (1.25)

1.4 Algebraic method

There are two cases for solving problems by the algebraic method:

1. the matrix has a saddle point;

2. the matrix does not have a saddle point.

In the first case, the solution is a pair of strategies that form the saddle point of the game. Let's consider the second case. Solutions here should be sought in mixed strategies:

Find strategies and When the first player uses his optimal strategy, the second player can, for example, apply two such pure strategies

At the same time, by virtue of the property, if one of the players uses the optimal mixed strategy, and the other - any pure, included in his optimal mixed strategy with a non-zero probability, then the mathematical expectation of the payoff always remains unchanged and equal to the price of the game, i.e.

The payoff must in each of these cases be equal to the value of the game V. In this case, the following relations are valid:

A system of equations similar to (2.5), (2.6) can also be composed for the optimal strategy of the second player:

Taking into account the normalization condition:

Let's solve the equation (1.37) - (1.41) together with respect to the unknowns, and not all at once, but three at a time: separately (1.36), (1.38), (1.40) and (1.37), (1.39), (1.41). As a result of the solution, we get:

1.5 Graphical method

An approximate solution of the game 22 can be quite easily obtained using the graphical method. Its essence is as follows:

Figure 1.1 - finding a section of unit length

Select a section of unit length on the abscissa axis. The left end of it will depict the first strategy of the first player, and the right end of the second. All intermediate points correspond to the mixed strategies of the first player, and the length of the segment to the right of the point is equal to the probability of using the first strategy, and the length of the segment to the left is the probability of using the second strategy by the first player.

Two axes I-I and II-II are carried out. On I-I we will postpone the payoff when the first player uses the first strategy, on II-II when he uses the second strategy. Let, for example, the second player applied his first strategy, then the value should be plotted on the I-I axis, and the value on the II-II axis

For any mixed strategy of the first player, his payoff will be determined by the size of the segment. Line I-I corresponds to the application of the first strategy by the second player, we will call it the first strategy of the second player. The second strategy of the second player can be constructed similarly. Then, in general, the graphical display of the game matrix will take the following form:

Figure 1.2 - finding the price of the game

However, it should be noted that this construction was carried out for the first player. Here the length of the segment is equal to the value of the game V.

The 1N2 line is called the lower payoff line. It is clearly seen here that the point N corresponds to the maximum value of the guaranteed payoff of the first player.

Generally speaking, the strategy of the second player can also be determined from this figure, for example in such ways. On the I-I axis:

or on axis II-II

However, the strategy of the second player can also be defined in the same way as it is done for the first player, i.e. build such a chart.

Figure 1.3 - definition of the strategy of the second player

Here the line 1N2 is the upper limit of the loss. Point N corresponds to the minimum possible loss of the second player, and it determines the strategy.

Depending on the specific values ​​of the coefficients, the graph matrices may also have a different form, for example, as follows:

Figure 1.4 - determines the optimal strategy of the first player

In such a situation, the optimal strategy of the first player is pure:

1.6 Games 2n or m2

In games of order 2n, the first player has 2 pure strategies, and the second player has n pure strategies, i.e. The payoff matrix for the first player is:

If such a game has a saddle point, then it is easy to find it and obtain a solution.

Suppose the game has saddle points. Then it is necessary to find such mixed strategies and, respectively, the first and second players and the price of the game v, which satisfy the relations:

Since the game has no saddle point, inequality (1.54) is replaced by the inequalities

To solve systems (1.56), (1.55), (1.53) it is expedient to use the graphical method. For the purpose, we introduce the notation for the left side of the inequality (1.53)

matrix game mathematical model

or, setting from (1.55) and performing simple transformations, we obtain

where is the average payoff of the first player, provided that he uses his mixed strategy, and the second - his j-th pure strategy.

According to the expression, each value j=1, 2, …, n corresponds to a straight line in a rectangular coordinate system.

The goal of the second player is to minimize the payoff of the first player by choosing his strategies. Therefore, we calculate

where is the lower bound of the constraint set. In Figure 1.6, the graph of the function is shown with a thick line.

Hosted at http://www.allbest.ru/

Figure 1.6 - function graph

The goal of the first player is to maximize his payoff through choice, i.e. calculate

In figure 1.6, the dot means the maximum value that is obtained at. The price of the game, because:

Thus, the optimal mixed strategy of the first player and a pair of pure strategies of the second player are graphically determined, which form a point at the intersection. Figure 1.6 shows the 2nd and 3rd strategies of the second player. For such strategies, inequalities (1.53) turn into equalities. In Figure 1.6, these are strategies j=2, j=3.

Now we can solve the system of equations

and precisely determine the values ​​of and (graphically they are determined approximately). Then putting all the values ​​at those j for which they do not form a point, solving the system of equations (1.56) For the example shown in Figure 1.6, this is the following system:

and the rest This system can be solved by sloping If, for some j=j 0, the strategies of the second player form a point M 0 and then the maximum value of the lower bound of the constraint sets is represented by a segment parallel to the axis In this case, the first player has infinitely many optimal values ​​and the price of the game This case shown in Figure 1.7, where and the segment MN represent the upper limit, the optimal values ​​are within the limits. The second player has a pure optimal strategy j=j 0 .

Matrix games of order m2 are also solved using the graphical method. The payoff matrix of the first player in this case has the form

The mixed strategies of the first and second players, respectively, are defined in the same way as in the case of games of order 2n. Let the value from 0 to 1 be plotted along the horizontal axis, the value of the average payoff) of the first player on the vertical axis under the conditions that the first player applies his pure i-th strategy (i=1, 2, ..., m), the second - his mixed strategy (y 1 , 1- y 1) =y. For example, when m=4 graphically) can be represented as shown in Figure 1.7.

Figure 1.7 - function graph)

The first player tries to maximize his average payoff, so he tries to find

The function is shown as a thick line and represents the upper bound of the constraint set. The second player tries to minimize by choosing his strategy, i.e. value corresponds

In the figure, the value is indicated by a dot. In other words, such two strategies of the first player and the probability for the second player are defined for which equality is achieved

From the figure we see that the price of the game is the ordinate of the point, the probability is the abscissa of the point. For the rest of the pure strategies of the first player in the optimal mixed strategy must ().

Thus, solving system (1.69), we obtain the optimal strategy of the second player and the value of the game. We find the optimal mixed strategy for the first player by solving the following system of equations:

1.7 Matrix method for solving games

Designations:

Any square submatrix of the order matrix

Matrix (1);

Matrix transposed to;

Matrix attached to B;

- (1) a matrix obtained from X by deleting the elements that correspond to the rows deleted from when received;

- (1) a matrix obtained from the deletion of elements that correspond to the rows deleted from when received.

Algorithm:

1. Choose a square submatrix of the order matrix () and calculate

2. If some or, then discard the found matrix and try another matrix.

3. If (), (), we calculate and build X and from and, adding zeros in the appropriate places.

Checking if the inequalities are satisfied

for each (1.75)

and inequalities

for each (1.76)

If one of the ratios is not satisfied, then we try another. If all relations are valid, then X, and the desired solutions.

1.8 The method of successive approximation of the price of the game

In the study of game situations, it can often happen that it is not necessary to obtain an exact solution to the game or, for some reason, it is impossible or very difficult to find the exact value of the game cost and optimal mixed strategies. Then you can use approximate methods for solving the matrix game.

Let us describe one of these methods - the method of successive approximation of the game price. The number of payoffs calculated using the method increases approximately in proportion to the number of rows and columns of the payoff matrix.

The essence of the method is as follows: mentally the game is played many times, i.e. sequentially, in each game game, the player chooses the strategy that gives him the greatest overall (total) payoff.

After such an implementation of some games, it calculates the average value of the first player's win and the second player's loss, and their arithmetic mean is taken as an approximate value of the game price. The method makes it possible to find an approximate value of the optimal mixed strategies of both players: it is necessary to calculate the frequency of application of each pure strategy and take it as an approximate value in the optimal mixed strategy of the corresponding player.

It can be proved that with an unlimited increase in the number of program games, the average gain of the first player and the average loss of the second player will indefinitely approach the price of the game, and the approximate values ​​of mixed strategies in the case when the solution of the game is unique will tend to the optimal mixed strategies of each player. Generally speaking, the approximation of values ​​above the specified values ​​to the true values ​​is slow. However, this process can be easily mechanized and thus help to obtain a solution to the game with the required degree of accuracy even with payoff matrices of a relatively large order.

2. Practical part

The couple decides where to go for a walk and spend time for the benefit of two.

The girl decides to go for a walk in the park to get some fresh air, in the evening to go to see a movie at the nearest cinema.

The guy offers to go to the technopark, after watching the match of the football players of the local club in the central stadium.

In accordance with this, you need to find how long the goal of one of the players will be achieved. The payoff matrix will look like this:

Table 1. Payoff Matrix

Since 1 2 , there is obviously no saddle point in this game in pure strategies. Therefore, we use the following formulas, and we get:

Hosted at http://www.allbest.ru/

2.2 Playing 2xn and mx2

Problem 1(2xn)

Two crops are grown for dry and humid climates.

And the state of nature can be considered as: dry, wet, moderate.

Hosted at http://www.allbest.ru/

The maximum value of M() is reached at the point M formed by the intersection of the lines corresponding to j=1, j"=2. Therefore, we assume: ,

Problem 2(mx2)

The guy and the girl are considering options for where to go for the weekend.

The choice of a place of rest can be represented as: a park, a cinema, a restaurant.

Hosted at http://www.allbest.ru/

The maximum value of M() is reached at the point E formed by the intersection of the lines corresponding to j=1, j"=2. Therefore, we assume: ,

To determine the value, v, you need to solve the following equations:

2.5 Matrix method

Two competing restaurants (catering establishments) provide the following sets of services. The first restaurant is located in the center and the other on the outskirts of the city.

The central restaurant includes the following services:

1) more expensive and better customer service;

2) dishes are focused on French cuisine;

The second restaurant provides:

1) not expensive and high-quality service;

2) the menu combines various famous cuisines of the world;

3) also regular promotions and discounts;

4) carries out delivery and accepts orders for home delivery.

In accordance with the task, the profit for one day between the two restaurants will be distributed as follows:

Table 2. Payoff Matrix

Solving a game of the form in a matrix way:

There are six submatrices and:

Consider the matrix:

x 1 =? 0,x2=? 0

Since x 2 =< 0, то мы отбрасываем.

Consider now the matrix:

x 1 =? 0,x2=? 0

Game price.

This ratio contradicts the requirement, so it is not suitable.

Consider now the matrix:

x 1 = , x 2 = ? 0,

y 1 =< 0, y 2 = ? 0.

Since y 1 =< 0, то мы отбрасываем и.

Consider now the matrix:

x 1 \u003d, x 2 \u003d 0, since x 2 \u003d 0, then we discard and.

Consider now the matrix:

x 1 = , x 2 = ? 0. Since x 1 \u003d 0, then we discard and.

Consider now the matrix:

x 1 = , x 2 =, y 1 = , y 2 =, then we continue further:

x 1 = , x 2 =, y 1 = , y 2 = or

Game price.

Now the main relations are checked:

Hosted at http://www.allbest.ru/

Answer: x 1 =, x 2 =, y 1 =, y 2 =, y 3 =0, y 4 =0,.

Brown method

At the request of the workers of a certain company, the trade union negotiates with its management about the organization of hot meals at the expense of the company. The trade union representing the interests of the workers ensures that the meal is of the highest quality possible and therefore more expensive. The management of the company has conflicting interests. In the end, the parties agreed on the following. The trade union (player 1) chooses one of three firms (A 1 , A 2 , A 3) supplying hot meals, and the company management (player 2) selects a set of dishes from three possible options (B 1 , B 2 , B 3) . After signing the agreement, the trade union forms the following payment matrix, the elements of which represent the cost of a set of dishes:

Let the game be given by the following payoff matrix:

Suppose the second player has chosen his 2nd strategy, then the first one will get:

2 if he uses his 1st strategy,

3 if he uses his 3rd strategy.

The obtained values ​​are summarized in Table 1.

Table 3. Strategy of the second player

Table 3 shows that with the 2nd strategy of the second player, the first player will receive the largest payoff 3 using his 2nd or 3rd strategy. Since the first player wants to get the maximum payoff, he responds to the 2nd strategy of the second player with his 2nd strategy. With the 2nd strategy of the first player, the second one will lose:

1 if he applies his 1st strategy,

3 if he uses his 2nd strategy,

4 if he uses his 3rd strategy.

Table 4. Strategy of the first player

Table 2 shows that with the 2nd strategy of the first player, the second player will have the least loss 1 if he applies his 1st strategy. Since the second player wants to lose less, then in response to the 2nd strategy of the first player, he will apply his 1st strategy. The results obtained are summarized in Table 5.

Table 5. Strategies of the first and second players, respectively

In table. 5 in the column of the strategy of the second player in the second line is the number 1, which indicates that in the second game it is beneficial for the second player to use his 1st strategy; in the column and is the largest average payoff 3 of the first player, received by him in the first game; the column w contains the smallest average loss 1 received by the second player in the first game; the v column contains the arithmetic mean v = (u + w) -- that is, the approximate value of the price of the game, obtained as a result of playing one game of the game. If the second player uses his 1st strategy, then the first player will get 3, 1, 2, respectively, with his 1st, 2nd, 3rd strategies, and the total payoff of the first player for both games will be:

2 + 3=5 with his 1st strategy,

3 + 1=4 with his 2nd strategy,

3 + 2=5 with his 3rd strategy.

These total winnings are recorded in the second line of the table. 3 and in the columns corresponding to the strategies of the first player: 1, 2, 3.

Of all the total payoffs, the largest is 5. It is obtained with the 1st and 3rd strategies of the first player, then he can choose any of them; say, in such cases when there are two (or several) identical total payoffs, the strategy with the smallest number is chosen (in our case, we need to take the 1st strategy).

With the 1st strategy of the first player, the second player will lose 3, 2, 3, respectively, to his 1st, 2nd, 3rd strategies, and the total loss of the second player for both games will be:

1 + 3=4 with his 1st strategy,

3 + 2=5 with his 2nd strategy,

4 + 3=7 with his 3rd strategy.

These total losses are recorded in the second line of the table. 5 and in the columns corresponding to the 1st, 2nd, 3rd strategies of the second player.

Of all the total losses of the second player, the smallest is 4. It is obtained with his 1st strategy, therefore, in the third game, the second player must apply his 1st strategy. In the column and put the largest total payoff of the first player in two games, divided by the number of games, i.e.; the w column contains the smallest total loss of the second player in two games, divided by the number of games, i.e. ; the arithmetic mean of these values ​​is put in column v, i.e. = This number is taken as an approximate value of the price of the game with two “played” games.

Thus, the following table 4 is obtained, for two sets of the game.

Table 6. Total gains and losses of players in two games played

In the third row of Table 6, in the strategy column of the second player, there is the number 1, which indicates that in the third game the second player must apply his 1st strategy. In this case, the first player wins 3, 1, 2, using his 1st, 2nd, 3rd strategies, respectively, and his total payoff for three games will be:

3 + 5 = 8 at his 1st strategy,

1 +4 = 5 with his 2nd strategy,

2 + 5 = 7 for his 3rd strategy.

These total payoffs of the first player are recorded in the third row of table 6 and columns corresponding to his strategies 1, 2, 3. Since the largest total payoff 8 of the first player is obtained with the 1st strategy, he chooses the 1st accordingly.

With the 1st strategy of the first player, the second player will lose 3, 1, 2, respectively, to the 1st, 2nd, 3rd strategies, and the total loss of the second player for both games will be:

3 + 4=7 with his 1st strategy,

2 + 5=7 with his 2nd strategy,

3 + 7=10 with his 3rd strategy.

These total losses are recorded in the third line of the table. 6 and in the columns corresponding to the 1st, 2nd, 3rd strategies of the second player. Of all his total losses, 7 is the smallest and is obtained with his 1st and 2nd strategies, then the second player must apply his 1st strategy.

In table. 6 in the third row in the column and the largest total winnings of the first player in three games, divided by the number of the game, i.e. ; column w contains the smallest total loss of the second player in three games, divided by the number of games, i.e. ; in column v put their arithmetic mean

Thus we get the table. 7 for three parties.

Table 7. Total gains and losses of players in three games played

Table 8. Final table with twenty games played

From Table. 7 and 8, it can be seen that in 20 lost games, strategies 1, 2, 3 for the first player occur 12, 3, 5 times, respectively, therefore, their relative frequencies are respectively equal; strategies 1, 2, 3 for the second player occur respectively 7, 11.2 times, hence their relative frequencies are respectively equal; approximate value of the price of the game. This approximation is good enough.

In conclusion, we note that if the game has more than one solution, then the approximate values ​​of the cost of the game will still approach the true cost of the game indefinitely, and the relative frequencies of the appearance of the strategies of the players will no longer necessarily approach the true optimal mixed strategies of the players.

Analysis of results

In this course work, the material for finding a solution to antagonistic games is studied by a graphical, matrix method, the method of successive approximation of the price of the game. The optimal strategies of the first and second players, as well as the cost of the game in 2x2, 2xn and mx2 games, as well as in games using the matrix method and Brown's method, are found.

On the example of a pair, a 2x2 game was modeled, which was solved by an algebraic and graphical method. Solving the game by the algebraic method, the solution shows that by applying their optimal mixed strategies, the first and second players will spend 4.6 hours together. The graphic solution of the problem turned out with a small error and amounted to 4.5 hours.

And also two tasks 2xn and mx2 were modeled. In the 2xn problem, agricultural culture was considered and the strategy shows that it is better to plant the field 50 by 50, and the price of the game was 3.75 million rubles. And in the mx2 problem, a pair was considered, the strategy of which showed that it is cheaper to go to the park and the cinema, and the price and cost will be 4.3 rubles.

A task was modeled for the matrix method, in which two restaurants were considered, the solution of the problem showed that when applying its optimal mixed strategy, the profit of the first restaurant will be 15.6 million rubles, and when using its optimal mixed strategy by the second restaurant, it will not allow the first one to earn more than 15.6 million rubles. The solution by the graphical method gave an error and the price of the game was 14.9 million rubles.

For the Brown method, a task was drawn up in which the union and company management are considered, their task is to provide food for the workers. When both players use their optimal strategies, food per person will be 2.45 thousand rubles.

List of sources used

1) Vilisov V.Ya. Lecture notes "Game Theory and Statistical Solutions", - Branch - "Voskhod" MAI. 1979. 146 p.

2) Krushevsky A.V. Game theory, - Kyiv: Vishcha school, 1977. - 216 p.

3) Cherchmen U., Akof R., Arnof L., Introduction to Operations Research. - M.: Science. 1967. - 488 p.

4) http://www.math-pr.com/exampl_gt2.htm

5) http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0 %B3%D0%BE%D0%BD%D0%B8%D1%81 %D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0

Hosted on Allbest.ru

Similar Documents

Decision making as a special kind of human activity. Rational representation of the game matrix. Examples of matrix games in pure and mixed strategies. Operations research: the relationship of linear programming problems with a game-theoretic model.

term paper, added 05/05/2010


Games repeated many times, their distinctive properties and stages. Mixed strategies, conditions and opportunities for their use in practice. An analytical method for solving a 2 x 2 game. Basic theorems for rectangular games. Algebraic solutions.

presentation, added 10/23/2013


Basic definitions of the theory of bimatrix games. An example of a bimatrix game "Student-Teacher". Mixed strategies in bimatrix games. Search for "equilibrium situation". 2x2 bimatrix games and formulas for the case when each player has two strategies.

abstract, added 02/13/2011


The study of general information about matrix and antagonistic games. Concept of positional game, tree, information set. Consideration of the maximin principle and the principle of equilibrium. Pareto optimality. Positional non-antagonistic game, its properties.

term paper, added 10/17/2014


Game theory is a branch of mathematics, the subject of which is the study of mathematical models for making optimal decisions in a conflict. Iterative Brown-Robinson method. Monotone iterative algorithm for solving matrix games.

thesis, added 08/08/2007


Compilation of the payoff matrix, search for the lower and upper net prices of the game, the maximin and minimax strategies of the players. Simplification of the payment matrix. Solving a matrix game using reduction to a linear programming problem and the add-in "Search for a solution".

test, added 11/10/2014


Game theory is a mathematical theory of conflict situations. Development of a mathematical model of a two-person zero-sum game, its implementation in the form of program codes. Problem solving method. Input and output data. Program, user manual.

term paper, added 08/17/2013


Basic information about the simplex method, evaluation of its role and importance in linear programming. Geometric interpretation and algebraic meaning. Finding the maximum and minimum of a linear function, special cases. Solution of the problem by the matrix simplex method.

thesis, added 06/01/2015


Techniques for constructing mathematical models of computing systems that reflect the structure and processes of their functioning. The number of file accesses during the average task. Determination of the possibility of placing files in external memory drives.

laboratory work, added 06/21/2013


Designing a mathematical model. Description of the game of tic-tac-toe. Logic game model based on Boolean algebra. Digital electronic devices and development of their mathematical model. Game console, game controller, game board string.

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

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):

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:

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:

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 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 AND 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 AND case when the player AT applies a strategy appropriate to minimum element of this line, the player's payoff AND will be equal to the number.

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

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 a game G in which two players A and B participate, having opposite interests: the gain of one is equal to the loss of the other. Since the payoff of player A is equal to the payoff of player B with the opposite sign, we can only be interested in the payoff of player a. Naturally, A wants to maximize and B wants to minimize a.

For simplicity, let's mentally identify ourselves with one of the players (let it be A) and call him "we", and player B - "opponent" (of course, no real advantages for A follow from this). Let us have possible strategies and the opponent - possible strategies (such a game is called a game). Let us denote our payoff if we use the strategy and the opponent uses the strategy

Table 26.1

Suppose that for each pair of strategies, the payoff (or average payoff) a is known to us. 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 the game G is said to be reduced to a matrix form (by itself, bringing the game to such a form can already be a difficult task, and sometimes practically 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

Consider an example of a game G (4X5) 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 (player A) use? Matrix 26.2 has the enticing payoff "10"; we are drawn to choose a strategy in which we will get this “tidbit”.

But wait, the enemy isn't stupid either! If we choose the strategy, he, to spite us, will choose the strategy , and we will get some miserable payoff "1". No, you can't choose a strategy! How to be? Obviously, proceeding from the principle of caution (and it is the main principle of game theory), we must choose the strategy for which our minimum gain is maximum.

Table 26.2

This is the so-called “mini-max principle”: act in such a way that, with the worst behavior of your opponent, you get the maximum gain.

Let's rewrite the table 26.2 and in the right additional column we will write down the minimum value of a gain in each line (a minimum of a line); let's denote it for row a (see table 26.3).

Table 26.3

Of all the values ​​(right column), the largest (3) is selected. It matches the strategy. Having chosen this strategy, we can in any case be sure that (for any behavior of the enemy) we will gain no less than 3. This value is our guaranteed gain; behaving carefully, we can not get less than this, we can get more).

This payoff is called the lower price of the game (or "maximin" - the maximum of the minimum payoffs). We will denote it as a. In our case

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, we will answer him and he will give 10; if he chooses, we will answer him and he will give it back, etc. We add an additional lower row to table 26.3 and write the maximums of the columns in it. Obviously, a cautious adversary must choose the strategy for which this value is minimal (the corresponding value 5 is highlighted in table 26.3) . This value P 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 "mi-nimax" - the minimum of the maximum winnings). In our example, and is achieved with the opponent's strategy

So, based on the principle of caution (the reinsurance rule “always count on the worst!”), We must choose strategy A and the enemy - strategy. 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

Now imagine for a moment that we have learned that the enemy is following strategy . Come on, we punish him for this and choose a strategy, we get 5, and this is not so bad. But after all, the enemy is also not a miss; let him know that our strategy is , he will also hurry up to choose , reducing our payoff to 2, etc. (partners “rushed around the strategies”). In short, the minimax strategies in our example are unstable with respect to information about the behavior of the other side; 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: . What follows from this? The minimax strategies of players A and B will be stable. As long as both players stick to them, the payoff is 6. Let's see what happens if we (A) find out that the opponent (B) sticks to strategy B?

Table 26.4

And exactly nothing will change, Because any deviation from the strategy can only worsen our situation. Equally, the information received by the opponent will not make him retreat from his strategy. 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 total value is called the price of the game. We will label it

Strategies (in this case, ) at which this gain is achieved are called optimal pure strategies, and their combination is a solution to the game. In this case, the game itself is said to be solved in pure strategies. Both parties A and B can be given their optimal strategies in which their position is the best possible. And that player A wins 6, and player B loses, well, these are the conditions of the game: they are beneficial for A and disadvantageous for B.

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 admit, in addition to pure ones, also mixed strategies, any finite game has a solution - an equilibrium point. But more about this is yet to come.

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 complete information is a game in which each player knows the entire prehistory of its development at each personal move, i.e., the results of all previous moves, both personal and random. 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 therefore 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 price of the game and. 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 put a nickel in the center of the table for the first time, 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 does not found. Let's say chess game either it always ends in a win for White, or it always ends in a win for Black, or it always ends in a draw, but 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.

And 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 a single pure strategy, then there is nothing to do: we must be guided by the minimax principle. Another thing is if you can “mix” your strategies, alternate them 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 players A and B, respectively

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 fundamental theorem of game theory: any two-player finite zero-sum game has at least one solution - a pair of optimal strategies, generally mixed, and a corresponding price

A pair of optimal strategies forming a game solution 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. This pair of strategies forms a kind of equilibrium in the game: one player wants to turn the payoff to the maximum, the other - to the minimum, each pulls in his own direction, and, with reasonable behavior of both, an equilibrium and a stable payoff v are established. If then the game is beneficial for us, if - for the enemy; when 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 A and B simultaneously and without saying a word show one, two or three fingers. The winning is decided by the total number of fingers: if it is even, A wins and receives from B an amount equal to this number; if odd, then, on the contrary, A pays B an amount equal to this 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 3x3 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 is consistent with the strategy. This means that with a reasonable, cautious behavior, we guarantee that we will not lose more than 3. Small consolation, but still better than, say, winning - 5, found in some cells of the matrix. It's bad for us, player L... But let's console ourselves: the opponent's position seems to be even worse: the lower price of the game at. reasonable behavior, he will give us a minimum of 4.