Principles for solving matrix antagonistic games. Matrix games: examples of problem solving

Principles for solving matrix antagonistic games. Matrix games: examples of problem solving

Methods for solving matrix games in mixed strategies

Methods for solving matrix games in mixed strategies

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

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

Similar documents

Are you here: Holidays

Purpose of the service. Using the online service you can:

determine the price of a matrix game (lower and upper bounds), check for the presence of a saddle point, find a solution to a mixed strategy, find a minimax strategy of players;
write down a mathematical model of a pair of dual linear programming problems, solve a matrix game using the following methods: minimax, simplex method, graphical (geometric) method, Brown's method.

Instructions. Select the matrix dimension, click Next. In the new dialog box, select a method for solving the matrix game. Filling example. The calculation results are presented in a report in Word format.

A game is a mathematical model of a real conflict situation. A conflict situation between two players is called a doubles game. It is convenient to study a zero-sum pair game if it is described in the form of a matrix. This game is called matrix; a matrix composed of numbers a ij is called payment. The table presents options for solving the game specified by the payment matrix A.

Description of the algorithm:

Based on the analysis of the payment matrix, it is necessary to determine whether there are dominated strategies in it and eliminate them.
Find the upper and lower prices of the game and determine whether this game has a saddle point (the lower price of the game must be equal to the upper price of the game).
If a saddle point exists, then the optimal strategies of the players, which are the solution to the game, will be their pure strategies corresponding to the saddle point. The price of the game is equal to the upper and lower prices of the game, which are equal to each other.
If the game does not have a saddle point, then the solution to the game should be sought in mixed strategies. To determine optimal mixed strategies in m × n games, one should use the simplex method, having first reformulated the game problem into a linear programming problem.

Let us present the algorithm for solving a matrix game graphically.

Figure - Scheme of solving a matrix game.

So, if there is no saddle point, the game is solved using mixed strategies and solved using the following methods:

Solving the game through a system of equations.
If a square matrix nxn (n=m) is given, then the probability vector can be found by solving the system of equations. This method is not always used and is applicable only in certain cases (if the matrix is 2x2, then the solution to the game is almost always obtained). If the solution produces negative probabilities, then this system is solved using the simplex method.
Solving the game graphically.
In cases where n=2 or m=2, the matrix game can be solved graphically.
Solving a matrix game using the simplex method.
In this case, the matrix game reduces to

The approach to solving matrix games can be generalized to the case of zero-sum games in which the payoff of players is specified as a continuous function (infinite zero-sum game).

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

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

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

at *

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

In this case v is called the net price of the game, and (x°, y 0) is the saddle point of an infinite zero-sum game.

For matrix games of magnitude v x And v 2 always exist, but in infinite antagonistic games they may not exist, i.e. an endless zero-sum game is not always solvable.

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

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

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

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

xGX y eg

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

Thus, the lower net price of the game v x - 1. Top clean

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

>egheh u ey

game v l =v 2 =l. Therefore the net price of the game v= 1, and the saddle point (x° = 1; y° = 1).

Let us now assume that Chi Y- open intervals, i.e. player 1 chooses xeA"=(0; 1), player 2 chooses ue 7= (0; 1). In this case, choosing X, close enough to 1, player 1 will be confident that he will receive a payoff no less than a number close to "=1; by choosing y close to 1, player 2 will not allow player 1's payoff to significantly exceed the net cost of the game v= 1.

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

If the game does not have a saddle point (c-saddle point), i.e. solutions in pure strategies, then optimal strategies can be sought among mixed strategies, which are used as probability distribution functions of players using pure strategies.

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

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

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

The average payoff of player 1 given that player 2 uses his pure strategy y, can be obtained by integrating payments over all possible values X, those. on a unit interval:

Average payoff of player 1, assuming both players use their mixed strategies F(x) And Q(y), will be equal

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

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

Then the floor price of an infinite zero-sum game solved in mixed strategies can be defined as v x= check

min E(FQ), and the top price of the game is like v 2 = min max E(F, Q).

Q Q f

If such mixed strategies exist F* (x) And Q*(y) respectively for players 1 and 2, for which the lower and upper prices of the game coincide, then F*(x) And Q*(y) It is natural to call the optimal mixed strategies of the corresponding players, a v=v x = v 2- at the cost of the game.

Unlike matrix games, a solution to an infinite zero-sum game does not exist for every function Shh, uh). But the theorem has been proven that every infinite zero-sum game with a continuous payoff function Shh, uh) on the unit square has a solution (players have optimal mixed strategies), although there are no general methods for solving infinite zero-sum games, including continuous games. However, antagonistic infinite games with convex and concave continuous payoff functions (they are called respectively convex And concave games).

Let us consider the solution of games with a convex payoff function. The solution of games with a concave payoff function is symmetric.

Convex function/variable X on the interval ( A; b) is a function for which the inequality holds

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

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

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

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

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

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

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

and the meaning y 0 is defined as the solution to the following equation:

If the function Shchh, y) is not strictly convex in y, then player 2 will not have the only optimal pure strategy.

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

The price of the game is determined by the formula

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

Based on these properties of infinite zero-sum games with convex or concave payoff functions, a general scheme for solving such games on a unit square (хе, уе) is constructed. We present this scheme only for convex games, since for concave games it is symmetrical.

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

2. Determine y 0 from the relation v- min max Shh, uh) as meaning

y, at which minimax is achieved.

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

4. Find parameter A from Eq.

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

Let us use an example to demonstrate the use of this scheme to solve a game of this type. Let the payoff function in an infinite zero-sum game be given on a unit square and be equal to Shchh, y) = =(x - y) 2 =x 2 - 2 xy ch-y 2.

1. This function is continuous in X And y, and therefore this game has a solution. Function Shh, uh) strictly convex along y, because

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

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

Let us successively find the first and second partial derivatives of the payment function with respect to x:

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

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

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

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

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

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

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

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

Conditions are met for them

4. Let us determine the parameter a, i.e. the probability of player 1 using his pure strategy X] = 0. Let’s create the equation a-1 + (1 - a) (-1) = 0, from which a = Y 2. Thus, the optimal strategy of player 1 is to choose his pure strategies 0 and 1 with probability 1 / 2 each. The problem is solved.

The simplest case, developed in detail in game theory, is a finite zero-sum pairs game (an antagonistic game of two persons or two coalitions). Consider a game G in which two players A and B participate, having opposing 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 the “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 winnings if we use the strategy and the opponent uses the strategy

Table 26.1

Let us assume that for each pair of strategies the payoff (or average payoff) a is known to us. Then, in principle, it is possible to construct a rectangular table (matrix) that lists the players' strategies and the corresponding payoffs (see Table 26.1).

If such a table is compiled, then they say that the game G has been reduced to a matrix form (bringing the game to such a form in itself can already be a difficult task, and sometimes almost impossible, due to the immense variety of strategies). Note that if the game is reduced to matrix form, then the multi-move game is actually reduced to a single-move game - the player is required to make only one move: choose a strategy. We will briefly denote the game matrix

Let's look at an example of the game G (4X5) in matrix form. We have four strategies at our disposal (to choose from), while the enemy has five strategies. The game matrix is given in table 26.2

Let's think about what strategy should we (player A) use? In Matrix 26.2 there is a tempting payoff of "10"; we are tempted to choose a strategy in which we will get this “tidbit”.

But wait: the enemy is not a fool either! If we choose a strategy, he will, to spite us, choose the strategy , and we will get some pathetic payoff “1”. No, you cannot choose a strategy! How to be? Obviously, based on the principle of caution (and it is the basic principle of game theory), we must choose the strategy at which our minimum gain is maximum.

Table 26.2

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

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

Table 26.3

Of all the values (right column), the largest (3) is highlighted. The strategy corresponds to it. By choosing this strategy, we can in any case be sure that (for any behavior of the enemy) we will win no less than 3. This value is our guaranteed win; Behaving carefully, we cannot get less than this, maybe we will get more).

This winning is called the lower price of the game (or “maximin” - the maximum of the minimum winnings). We will denote it as a. In our case

Now let’s take the enemy’s point of view and reason for him. He’s not some kind of pawn, but he’s also smart! When choosing a strategy, he would like to give less, but he must count on our worst behavior 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, etc. We will add an additional bottom line to Table 26.3 and write down the maximums of the columns in it. Obviously, a cautious opponent should choose the strategy in 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 enemy’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 sides in our example stick to their minimax strategies, the payoff will be

Now let's imagine for a moment that we have learned that the enemy is following a strategy. Come on, let's punish him for this and choose a strategy, we'll get 5, and that's not so bad. But the enemy is also not a failure; let him know that our strategy is , he will also hurry to choose, reducing our winnings to 2, etc. (the partners “rushed about with strategies”). In short, the minimax strategies in our example are unstable with respect to information about the behavior of the other party; these strategies do not have the property of equilibrium.

Is this always the case? No not always. Consider the example with the matrix given in Table 26.4.

In this example, the lower price of the game is equal to the upper price: . What follows from this? The minimax strategies of players A and B will be stable. As long as both players adhere to them, the payoff is 6. Let's see what happens if we (A) find out that the opponent (B) adheres to strategy B?

Table 26.4

But absolutely nothing will change, because any deviation from the strategy can only worsen our situation. Likewise, the information received by the opponent will not force him to deviate from his strategy. A pair of strategies has 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.” 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 denote it

The strategies (in this case) at which this gain is achieved are called optimal pure strategies, and their totality is called a solution to the game. In this case, they say about the game itself that it is solved in pure strategies. Both parties A and B can be given their optimal strategies, in which their position is the best possible. And if 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, we will answer this question: there are “mixed” strategies, which consist in the fact that the player uses not just one strategy, but several, interspersing them randomly. So, if we allow mixed strategies in addition to pure ones, every finite game has a solution - an equilibrium point. But this is still to be discussed.

The presence of a saddle point in a game is far from being a rule; rather, it is an exception. Most games don't have a saddle point. However, there is a type of game that always has a saddle point and, therefore, is 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, with each personal move, knows the entire background of its development, i.e., the results of all previous moves, both personal and random. Examples of games with complete information include: checkers, chess, tic-tac-toe, etc.

In game theory it is proven that every game with complete information has a saddle point, and therefore is solved in pure strategies. In every game with complete information, there is a pair of optimal strategies that give a stable payoff equal to the cost of the game and. If such a game consists only of personal moves, then when each player uses his optimal strategy, it should end in a very definite way - with a win equal to the cost of the game. This means that if the solution to 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, randomly choosing the position of the center of the coin (mutual overlap of coins is not allowed). The one who puts in the last nickel wins (when there is no room left for others). It is easy to see that the outcome of this game is, in essence, predetermined. There is a certain strategy that ensures that the player who places the coin first wins.

Namely, he must first place a nickel in the center of the table, and then respond to each opponent’s move with a symmetrical move. Obviously, no matter how the enemy behaves, he cannot avoid losing. The situation is exactly the same with chess and games in general with complete information: any of them, written in matrix form, has a saddle point, which means that the solution is in pure strategies, and therefore makes sense only as long as this solution does not found. Let's say a chess game either always ends with White winning, or always with Black winning, or always with a draw, but we don't yet know what exactly (fortunately for chess lovers). Let us also add: we are unlikely to know in the foreseeable future, because the number of strategies is so huge that it is extremely difficult (if not impossible) to bring 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 single pure strategy, then there is nothing to do: we must be guided by the minimax principle. It’s another matter if you can “mix” your strategies, alternate them randomly with some probabilities. The use of mixed strategies is thought of 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, “casts lots,” and takes the strategy that came up (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 (though 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, where (forming a total of one) - the probability of player A using strategies - the probability of player B using strategies

In the special case when all probabilities except 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 finite two-person zero-sum game has at least one solution - a pair of optimal strategies, generally mixed, and a corresponding price

A pair of optimal strategies that form a solution to a 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. This pair of strategies forms a certain equilibrium position in the game: one player wants to turn the gain into a maximum, the other - into a minimum, each pulls in his own direction and, with reasonable behavior of both, equilibrium and a stable gain 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.

Let's 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 total number of fingers decides the winnings: if it is even, A wins and receives from B an amount equal to this number; if it is odd, then, on the contrary, A pays B an amount equal to this number. What should 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 additional right column shows the row minima, and the additional bottom row shows the column maxima.

The lower price of the game corresponds to the strategy. This means that with reasonable, careful behavior, we guarantee that we will not lose more than 3. Small consolation, but still better than, say, a win of 5, found in some cells of the matrix. It’s bad for us, player L... But let us console ourselves: the enemy’s position seems to be even worse: the lower price of the game is at. reasonable behavior he will give us at least 4.

The decision-making problem, considered within the framework of the systems approach, contains three main components: it distinguishes the system, the control subsystem and the environment. Now we move on to the study of decision-making problems in which the system is influenced not by one, but by several control subsystems, each of which has its own goals and possibilities of action. This approach to decision making is called game-theoretic, and mathematical models of the corresponding interactions are called games. Due to the differences 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 conflicting nature. Therefore, every game is a mathematical model of conflict. Let us limit 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- many strategies for player 1, 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) - assessment of utility for player 1 of that state

system into which it goes when the player chooses 1 strategy X And

player 2 strategy at. Number F(x,y) is called win player 1 in situation ( x,y), and the function F- player 1's payoff function. Player's winnings

1 is simultaneously 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

a 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 defined by the system G=(X, Y, F).

Note that formally the zero-sum game is set in virtually the same way as the decision-making task under conditions of uncertainty - if

identify 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 drawing up a mathematical model of a real conflict, we have reason (or intention) to consider the environment as an enemy whose goal is to bring

maximum harm to us, then such a situation can be presented in the form of an antagonistic game. In other words, the zero-sum game can be interpreted as an extreme case of the ZPR under conditions of uncertainty,

characterized by treating the environment 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 justified here is the hypothesis of extreme caution, when, when making a decision, we count on the worst possible course of action for us by the environment.

Definition. If X And Y are finite, then the antagonistic game is called a matrix game. In a 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. Two finger game.

Two people simultaneously show one or two fingers and call the number 1 or 2, which, in the speaker’s opinion, 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 didn’t guess how many fingers their opponent showed, everyone’s winnings are zero; if only one guessed, then the opponent pays the guesser an amount of money proportional to the total number shown

This is a zero-sum matrix game. Each player has four strategies: 1- show 1 finger and call 1, 2- show 1 finger and call 2, 3-

show 2 fingers and call 1, 4 - show 2 fingers and call 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 in other cases.

Example 3.2. Discrete duel type game.

Dueling type problems describe, for example, a fight between two players,

each of whom wants to perform some one-time action (releasing a batch of goods to the market, applying for a purchase at an auction) and chooses a time for this. Have the players move towards each other n steps. After each step taken, the player can choose to shoot or not shoot at the enemy. Each person can only have one shot. It is believed that the probability of hitting the enemy if you advance k n =5 has the form

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 2x2

1.4 Algebraic method

1.5 Graphical method

1.6 Games 2xn or mx2

1.7 Solving games using the matrix method

2. Practical part

2.2 Games 2xn and mx2

2.3 Matrix method

2.4 Brown method

Analysis of results

Introduction

A zero-sum game is a zero-sum game. A zero-sum game is a non-cooperative game involving two players whose payoffs are opposite.

Formally, an antagonistic game can be represented by a troika , 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, assigning each pair of strategies (x,y), where a real number corresponding to the utility of the first player in implementing a given situation.

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

Historically, zero-sum games are the first class of mathematical game theory models with which gambling was described. It is believed that this subject of study is where game theory got its name. Nowadays, antagonistic games are considered part of the broader 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 the distribution of winnings depending on their behavior and outcomes. A player is considered to be one participant or a group of game participants who have some common interests 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 game's development. Making a choice for a player means choosing one of his behavior options. The player then makes these choices using moves. Making a move means at a certain stage of the game making 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 player tries to take into account information about the past development of the game, if such a possibility is permitted by the rules of the game.

A set of rules that clearly indicate to the player what choice he must make at each move, depending on the situation that arises 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 game development. Strategy means the totality of all instructions for any state of information available to the player at any stage of the game's development. From this it is already clear that strategies can be good and bad, successful and unsuccessful, etc.

A zero-sum game will be when the sum of the winnings of all players in each of its games is equal to zero, i.e. in a zero-sum game, the total capital of all players does not change, but is redistributed between 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 between 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

A two-player zero-sum matrix game can be thought of as the following abstract two-player game.

The first player has t strategies i =1, 2,…, t, the second has n strategies j = 1, 2,…, p. Each pair of strategies (i, j) is associated with a number a ij , expressing the first player’s winnings due to the second player if the first player uses his i-th strategy, and the second player uses his j-th strategy.

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

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

A two-player zero-sum matrix game will henceforth be simply called a matrix game. Obviously the matrix game belongs to the antagonistic games. From its definition it follows that to define a matrix game it is enough to specify a matrix A = (a ij) of the order of the first player's payoffs.

If we consider the payoff matrix

then playing each game of a matrix game with matrix A is reduced to the choice by the first player of the i-th row, and the second player of the j-th column, and the first player receiving (at the expense of the second) the winnings located in matrix A at the intersection of the i-th row and 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 create a payoff matrix.

The next stage is to determine the optimal strategies and winnings of the players.

The main thing in the study of games is the concept of optimal strategies of players. This concept intuitively has the following meaning: a player’s strategy is optimal if the use of this strategy provides him with the largest guaranteed win for all possible strategies of the other player. Based on these positions, the first player examines the matrix A of his payoffs using formula (1.1) as follows: for each value of i (i = 1, 2,..., t) 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, 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 price of the game and shows what minimum winnings the first player can guarantee for 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, through his strategies, to minimize the winnings of the first player. 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 pure strategy, then the second player finds his j = j 1 strategy under which the first player will receive the minimum payoff, i.e., finds

Definition. The number b, determined by formula (1.5), is called the net upper price of the game and shows what maximum winnings the first player can guarantee for himself through his strategies. In other words, by applying his pure strategies, the first player can ensure a payoff of no less than b, and the second player, by applying his pure strategies, can prevent the first player from winning more than b.

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 price of the game:

n = b = v (1.6)

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

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

where i, j are any pure strategies of the first and second players, respectively; (i 0 , j 0) are strategies that form 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 minimal in the i 0th row and maximum in the j 0th column in matrix A. Finding the saddle point of matrix A is easy: in matrix A, the minimum element is successively found in each row and check whether 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 on the left side of (1.11) x is arbitrary, then

On the right side of inequality (1.12) y is arbitrary, therefore

Q.E.D.

In particular, 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 obtain that the lower net price is not exceeds the upper net price of play in the matrix game.

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

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 the study of the game ends with finding this point. If in a matrix game there is no saddle point in pure strategies, then one can find the lower and upper net prices of this game, which indicate that the first player should not hope to win more than the upper price of the game, and can be sure of receiving a win no less 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. Improving the solutions of matrix games should be sought in using the secrecy of using pure strategies and the possibility of repeating games in the form of games many times. So, for example, a series of games of chess, checkers, and football are played, and each time the players apply their strategies in such a way that their opponents have no idea about their content, and along this way, on average, they achieve certain winnings by playing the entire series of games. These winnings are on average greater than the lower price of the game and less than the upper price of the game. The higher this average value, the better the strategy the player uses. Therefore, the idea arose to apply pure strategies randomly, with a certain probability. This completely ensures the secrecy of their use. Each player can change the probabilities of using 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. A player's mixed strategy is the full set of probabilities of using 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 m ) satisfying the relations

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

Similarly, for the second player, who has n pure strategies, a mixed strategy y is a 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 excludes the use of another, pure strategies are incompatible events. Moreover, they are the only possible events.

Obviously, a pure strategy is a special case of a mixed strategy. Indeed, if in a mixed strategy any i-th pure 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 other player's choices.

Definition. The average payoff of the first player in a 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, by changing his mixed strategies x, to maximize his average payoff E (A, x, y), and the second player, through his mixed strategies, strives to make E (A, x, y) minimal, i.e. To solve the game it is necessary to find such x, y, at which the upper price of the game is achieved.

1.3 Game of order 22

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

The solution to this game should begin by finding a saddle point in pure strategies. To do this, find the minimum element in the first row and check whether 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.

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

Let us 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 = 1 - x 1 is the probability of him using his second strategy. Similarly for the second player: 1 is the probability of him using the first strategy, 2 = 1 - 1 is the probability of him using the second strategy.

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

Let us now show that if a matrix game does not have a saddle point in pure strategies, then these inequalities must turn into equalities:

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

0<<1, 0<< 1,

0< <1, 01. (1.25)

Let us assume that both inequalities from (1.22) are strict

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

It is similarly proven that both inequalities from (1.23) cannot be strict inequalities.

Let us now assume 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. Consequently, from (1.23) we obtain

If both inequalities (1.24) are strict, then, according to the theorem, x 1 = x 2 = 0, which contradicts (1.25). 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 of 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 a matrix game does not have a saddle point in pure strategies, then for the optimal strategies of the first player, inequalities (1.22) turn into equalities. Similar reasoning regarding 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 does not have a 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 has also been established that if in a matrix game of order 2x2 one of the players has an optimal pure strategy, then the other player also has an optimal pure strategy.

Consequently, 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). Solution of system (1.25)

1.4 Algebraic method

There are two possible cases for solving problems using 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:

Let's find strategies and... When the first player uses his optimal strategy, the second player can, for example, apply two such pure strategies

Moreover, due to the property, if one of the players uses an optimal mixed strategy, and the other uses any pure strategy included in his optimal mixed strategy with a probability not equal to zero, then the mathematical expectation of winning always remains unchanged and equal to the price of the game, i.e.

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

A system of equations similar to (2.5), (2.6) can be constructed 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, you can solve 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 to game 22 can be obtained quite simply 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 x-axis. The left end of it will depict the first strategy of the first player, and the right end will represent the second. All intermediate points correspond to 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 of is the probability of using the second strategy by the first player.

Two axes I-I and II-II are drawn. We will put the winnings on I-I when the first player uses the first strategy, on II-II when he uses the second strategy. Let, for example, the second player apply his first strategy, then the value should be plotted on the I-I axis, and the value should be plotted on the II-II axis

For any mixed strategy of the first player, his payoff will be determined by the value 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. Similarly, you can construct the second strategy of the second player. Then, in general, the graphical display of the game matrix will take the following form:

Figure 1.2 - finding the price of the game

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

The 1N2 line is called the lower winning limit. Here you can clearly see that point N corresponds to the maximum amount of the guaranteed winnings of the first player.

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

or on axis II-II

However, the strategy of the second player can be determined similarly to how it is done for the first player, i.e. build such a graph.

Figure 1.3 - determining the strategy of the second player

Here line 1N2 is the upper limit of 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 matrix coefficients, the graphs may have a different form, for example, this:

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 of the first player has the form:

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

Let's assume that the game has saddle points. Then it is necessary to find such mixed strategies and, accordingly, the first and second players and the game price v, which satisfy the relations:

Since the game does not have a saddle point, inequality (1.54) is replaced by the inequalities

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

matrix game mathematical model

or, putting from (1.55) and carrying out simple transformations, we obtain

where is the average payoff of the first player provided that he uses his mixed strategy, and the second player 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 winnings of the first player by choosing his strategies. Therefore we calculate

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

Posted on http://www.allbest.ru/

Figure 1.6 - function graph

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

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

In this way, the optimal mixed strategy of the first player and a pair of pure strategies of the second player are graphically determined, which at the intersection form a point. 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 accurately determine the values of and (graphically they are determined approximately). Then, putting all the values for 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 boundary of the sets of restrictions is depicted 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 is depicted in Figure 1.7, where the segment MN depicts the upper limits, the optimal values are within the limits The second player has a pure optimal strategy j=j 0 .

Matrix games of order m2 can also be 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 similarly as in the case of games of order 2n. Let the value from 0 to 1 be plotted along the horizontal axis, and the value of the average winning) of the first player along 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 strives to find

The function is represented by a thick line and represents the upper bound of a set of constraints. 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, the two strategies of the first player and the probability for the second player are determined at 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 remaining 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 price 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 adjoint to B;

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

- (1) a matrix obtained by deleting elements that correspond to the rows deleted from upon receipt.

Algorithm:

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

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

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

Checking whether the inequalities are satisfied

for everyone (1.75)

and inequalities

for everyone (1.76)

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

1.8 Method of successive approximation of game price

When studying game situations, it can often happen that there is no need 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 price and optimal mixed strategies. Then you can use approximate methods for solving a matrix game.

Let us describe one of these methods - the method of successively approximating the price of a game. The number calculated when 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: the game is played mentally many times, i.e. sequentially, in each game the player chooses the strategy that gives him the greatest overall (total) winnings.

After such implementation of some games, the average value of the winnings of the first player and the losses of the second player is calculated, and their arithmetic average is taken as an approximate value of the cost of the game. The method makes it possible to find the 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 proven 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 where the game has a unique solution will tend to the optimal mixed strategies of each player. Generally speaking, the tendency of approximate values above these values to approach the true values is slow. However, this process is easy to mechanize and thereby help 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 usefully for both.

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

The guy suggests going to the technology park and then watching a match of local club football players in the central stadium.

In accordance with this, you need to find how long it will take to achieve the goal of one of the players. The winning matrix will look like this:

Table 1. Payoff matrix

Strategies

Since 1 2 , Obviously, this game does not have a saddle point in pure strategies. Therefore, we use the following formulas and get:

Posted on http://www.allbest.ru/

2.2 Game 2xn and mx2

Problem 1(2xn)

Two grain crops are grown for dry and wet climates.

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

Posted on http://www.allbest.ru/

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

Problem 2(mx2)

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

The choice of a vacation spot can be thought of as: a park, a cinema, a restaurant.

Posted on http://www.allbest.ru/

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

To determine the value of v, the following equations must be solved:

2.5 Matrix method

Two restaurants (catering establishments) competing with each other 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 high-quality customer service;

2) the dishes are focused on French cuisine;

The second restaurant provides:

1) inexpensive and high-quality service;

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

3) also constant promotions and discounts;

4) delivers and accepts orders for home delivery.

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

Table 2. Payoff matrix

Solving a game of the form using a matrix method:

There are six submatrices and:

Consider the matrix:

x 1 = ? 0, x 2 = ? 0

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

Let's now consider the matrix:

x 1 = ? 0, x 2 = ? 0

Game price.

This ratio contradicts the requirement and is therefore not suitable.

Let's now consider the matrix:

x 1 = , x 2 = ? 0,

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

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

Let's now consider the matrix:

x 1 = , x 2 = 0, since x 2 = 0, then we discard and.

Let's now consider the matrix:

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

Let's now consider 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 basic relationships are checked:

Posted on 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 union negotiates with its management about organizing hot lunches at the company’s expense. The union representing the workers wants to ensure that lunch is as high quality as possible and therefore more expensive. The company's management has opposing interests. In the end, the parties agreed on the following. The trade union (player 1) chooses one of three companies (A 1, A 2, A 3) that supply hot meals, and the company management (player 2) chooses a set of dishes from three possible options (B 1, B 2, B 3) . After signing the agreement, the union generates the following payment matrix, the elements of which represent the cost of a set of dishes:

Let the game be defined by the following payoff matrix:

Suppose the second player chose his 2nd strategy, then the first will receive:

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

Batch number	Player 2 strategy	1st player win

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

1 if he uses his 1st strategy,

3, if he uses his 2nd strategy,

4 if he uses his 3rd strategy.

Table 4. First player strategy

Batch number	1st player strategy	2nd player loses

From Table 2 it can be seen that with the 2nd strategy of the first player, the second player will have the smallest loss of 1 if he applies his 1st strategy. Since the second player wants to lose less, in response to the 2nd strategy of the first player, he will use his 1st strategy. The results obtained are summarized in Table 5.

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

Batch number

Player 2 strategy

Total winnings of 1st player

1st player strategy

In table 5 in the strategy column of the second player in the second line there is a number 1, which indicates that in the second game it is beneficial for the second player to use his 1st strategy; in the column is the largest average winning 3 of the first player, received by him in the first game; column w contains the smallest average loss of 1 received by the second player in the first game; column v contains the arithmetic mean v = (u + w) - i.e., the approximate value of the game price obtained as a result of losing one game of the game. If the second player applies his 1st strategy, then the first will receive 3, 1, 2, respectively, with his 1st, 2nd, 3rd strategies, and the total winnings 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 row of the table. 3 and in the columns corresponding to the strategies of the first player: 1, 2, 3.

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

With the 1st strategy of the first player, the second 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 row 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. The largest total winnings of the first player over two games, divided by the number of games, is placed in the column, i.e.; Column w contains the smallest total loss of the second player over two games, divided by the number of games, i.e. ; in column v the arithmetic mean of these values is put, 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 games.

Table 6. Total winnings and losses of players after two games played

Player 2 strategy

Total winnings of 1st player

1st player strategy

Total loss of the 2nd player

In the third row of Table 6 in the strategy column of the second player there is a 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 winnings over three games will be:

3 + 5 = 8 with his 1st strategy,

1 +4 = 5 with his 2nd strategy,

2 + 5 = 7 with his 3rd strategy.

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

With the 1st strategy of the first player, the second will lose 3, 1, 2, respectively, to his 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 needs to apply his 1st strategy.

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

Thus we get table. 7 for three games.

Table 7. Total winnings and losses of players after three games played

Batch number

Player 2 strategy

Total winnings of 1st player

1st player strategy

Total loss of the 2nd player

Table 8. Final table after twenty games played

Batch number

Player 2 strategy

Total winnings of 1st player

1st player strategy

Total loss of the 2nd player

From the 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 7, 11,2 times respectively, therefore their relative frequencies are respectively equal; approximate price of the game. This approximation is quite good.

Finally, note that if a game has more than one solution, then the approximations of the game's cost will still indefinitely approach the true cost of the game, and the relative frequencies of the players' strategies will no longer necessarily approach the players' true optimal mixed strategies.

Analysis of results

In this course work, we studied the material of finding solutions to zero-sum games using the graphical, matrix method, and the method of successive approximation of the game price. The optimal strategies of the first and second players, as well as the cost of playing in the games 2x2, 2xn and mx2, as well as in games using the matrix method and Brown's method, were found.

Using the example of a pair, a 2x2 game was simulated, which was solved using algebraic and graphical methods. Solving the game algebraically, the solution shows that using their optimal mixed strategies, the first and second players will spend 4.6 hours together. The graphical solution to the problem was obtained with a small error and amounted to 4.5 hours.

And also two problems 2xn and mx2 were simulated. In problem 2xn, an agricultural crop was considered and the strategy shows that it is better to plant a field 50 to 50, and the price of the game was 3.75 million rubles. And in problem mx2, a couple was considered whose strategy showed that it was cheaper to go to the park and cinema, and the cost would be 4.3 rubles.

A problem was modeled for the matrix method, in which two restaurants were considered, the solution of the problem showed that when using 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 to earn more than 15.6 million rubles. The graphical solution resulted in an error and the price of the game was 14.9 million rubles.

For Brown's method, a task was drawn up in which the trade union and the company's management are considered, their task is to provide food to the workers. If 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 Decisions”, - Branch - “Voskhod” MAI. 1979. 146 p.

2) Krushevsky A.V. Game Theory, - Kyiv: Vishcha School, 1977. - 216 p.

3) Churchmen 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

Posted on Allbest.ru

Strategies