Game theory strategies. Game Theory and Statistical Decisions

If the game does not have a saddle point, then difficulties arise in determining the price of the game and the optimal strategies of the players. Consider, for example, the game:

In this game and. Therefore, the first player can guarantee himself a win equal to 4, and the second can limit his loss to 5. The area between and is, as it were, a draw and each player can try to improve his result at the expense of this area. What should be the optimal strategies of the players in this case?

If each player uses the strategy marked with an asterisk (and ), then the winnings of the first player and the loss of the second will be equal to 5. This is disadvantageous for the second player, since the first wins more than it can guarantee itself. However, if the second player somehow reveals the first player's intention to use the strategy, then he can apply the strategy and reduce the first player's payoff to 4. However, if the first player reveals the second player's intention to use the strategy, then, using the strategy, he will increase his payoff to 6 Thus, a situation arises where each player must keep secret the strategy he is going to use. However, how to do this? After all, if the game is played many times and the second player always uses the strategy, then the first player will soon figure out the second player’s plan and, having applied the strategy, will have an additional win. Obviously, the second player must change the strategy in each new game, but he must do this in such a way that the first player does not guess which strategy he will use in each case.

For a random selection mechanism, players' wins and losses will be random variables. The result of the game in this case can be estimated by the average loss of the second player. Let's go back to the example. So, if the second player uses a strategy and randomly with probabilities of 0.5; 0.5, then with the strategy of the first player the average value of his loss will be:

and with the first player strategy

Therefore, the second player can limit his average loss to 4.5 regardless of the strategy used by the first player.

Thus, in some cases it turns out to be advisable not to outline a strategy in advance, but to choose one or another at random, using some kind of random selection mechanism. A strategy based on random selection is called mixed strategy, in contrast to intended strategies, which are called pure strategies.

Let us give a more strict definition of pure and mixed strategies.

Let there be a game without a saddle point:

Let us denote the frequency of using the first player's pure strategy by , (the probability of using the i-th strategy). Similarly, let us denote the frequency of using the pure strategy of the second player by , (the probability of using the j-th strategy). For the game with a saddle point, there is a solution in pure strategies. For a game without a saddle point, there is a solution in mixed strategies, that is, when the choice of strategy is based on probabilities. Then

Lots of pure 1st player strategies;

Lots of mixed 1st player strategies;

Lots of pure 2nd player strategies;

Lots of mixed 2nd player strategies.

Let's consider an example: let there be a game

The second player chooses the probability . Let us estimate the average loss of the second player when he uses strategies and, respectively.

In general, V * ≠ V * - there is no saddle point. There is also no optimal solution in pure strategies. However, if we expand the concept of pure strategy by introducing the concept of mixed strategy, then it is possible to implement an algorithm for finding the optimal solution to a not well-defined game problem. In such a situation, it is proposed to use a statistical (probabilistic) approach to finding the optimal solution to the zero-sum game. For each player, along with a given set of strategies possible for him, an unknown vector of probabilities (relative frequencies) with which one or another strategy should be applied is introduced.

Let us denote the vector of probabilities (relative frequencies) of choosing given strategies of player A as follows:
P = (p 1, p 2,…, p m),
where p i ≥ 0, p 1 + p 2 +…+ p m = 1. The value p i is called the probability (relative frequency) of using strategy A i.

Similarly, for player B, an unknown vector of probabilities (relative frequencies) is introduced and has the form:
Q = (q 1, q 2,…, q n),
where q j ≥ 0, q 1 + q 2 +…+ q n = 1. The value q j is called the probability (relative frequency) of using strategy B j. The set (combination) of pure strategies A 1, A 2, …A m and B 1, B 2, …B n in combination with vectors of probabilities of choosing each of them are called mixed strategies.

The main theorem in the theory of finite zero-sum games is von Neumann's theorem: every finite matrix game has at least one optimal solution, possibly among mixed strategies.
From this theorem it follows that a non-well-defined game has at least one optimal solution in mixed strategies. In such games, the solution will be a pair of optimal mixed strategies P * and Q *, such that if one of the players adheres to his optimal strategy, then it is not profitable for the other player to deviate from his optimal strategy.
The average payoff of player A is determined by the mathematical expectation:

If the probability (relative frequency) of using a strategy is different from zero, then such a strategy is called active.

Strategies P*, Q* are called optimal mixed strategies if M A (P, Q *) ≤ M A (P *, Q *) ≤ M A (P *, Q) (1)
In this case M A (P * , Q *) is called at the cost games and is denoted by V (V * ≤ V ≤ V *). The first of inequalities (1) means that player A's deviation from his optimal mixed strategy provided that player B sticks to his optimal mixed strategy, leads to a decrease in average winnings player A. The second of the inequalities means that player B's deviation from his optimal mixed strategy provided that player A sticks to his optimal mixed strategy, leads to an increase in the average loss of player B.

In general, such problems can be successfully solved by this calculator.

Example.

1. Check whether the payment matrix has a saddle point. If yes, then we write out the solution to the game in pure strategies.

We assume that player I chooses his strategy in such a way as to maximize his payoff, and player II chooses his strategy in such a way as to minimize player I’s payoff.

We find the guaranteed payoff determined by the lower price of the game a = max(a i) = 2, which indicates the maximum pure strategy A 1 .
The upper price of the game is b = min(b j) = 7. Which indicates the absence of a saddle point, since a ≠ b, then the price of the game is within the range 2 ≤ y ≤ 7. We find a solution to the game in mixed strategies. This is explained by the fact that players cannot announce their pure strategies to the enemy: they must hide their actions. The game can be solved by allowing players to choose their strategies randomly (mixing pure strategies).

2. Check the payment matrix for dominant rows and dominant columns.
There are no dominant rows or dominant columns in the payment matrix.

3. Find a solution to the game in mixed strategies.
Let's write down a system of equations.
For player I
4p 1 +7p 2 +2p 3 = y
7p 1 +3p 2 +p 3 = y
2p 1 +2p 2 +8p 3 = y
p 1 +p 2 +p 3 = 1

For Player II
4q 1 +7q 2 +2q 3 = y
7q 1 +3q 2 +2q 3 = y
2q 1 +q 2 +8q 3 = y
q 1 + q 2 + q 3 = 1

Solving these systems using the Gauss method, we find:

y = 4 1 / 34
p 1 = 29 / 68 (probability of using the 1st strategy).
p 2 = 4 / 17 (probability of using the 2nd strategy).
p 3 = 23 / 68 (probability of using the 3rd strategy).

Optimal mixed strategy of player I: P = (29 / 68; 4 / 17; 23 / 68)
q 1 = 6 / 17 (probability of using the 1st strategy).
q 2 = 9 / 34 (probability of using the 2nd strategy).
q 3 = 13 / 34 (probability of using the 3rd strategy).

Player II's optimal mixed strategy: Q = (6 / 17; 9 / 34; 13 / 34)
Game price: y = 4 1 / 34

5. THEORY OF GAMES AND STATISTICAL DECISIONS

5.1. Zero-sum matrix game

Economic and mathematical modeling is carried out under the following conditions:

Certainty;

Uncertainties.

Modeling in conditions of certainty assumes the availability of all the initial regulatory data necessary for this (matrix modeling, network planning and management).

Modeling at risk carried out under stochastic uncertainty, when the values ​​of some initial data are random and the laws of probability distribution of these random variables are known (regression analysis, queuing theory).

Modeling in conditions of uncertainty corresponds to the complete absence of some data necessary for this (game theory).

Mathematical models for making optimal decisions in conflict situations are built under conditions of uncertainty.

Game theory operates with the following basic concepts:

Strategy;

Win function.

On the move we will call the choice and implementation by the player of one of the actions provided for by the rules of the game.

Strategy - this is a technology for choosing an action option at each move, depending on the current situation.

Win function serves to determine the amount of payment from the losing player to the winning one.

In a matrix game, the payoff function is represented as payment matrix :

where is the amount of payment to player I, who chose the move, from player II, who chose the move.

In such a paired game, the values ​​of the payoff functions of both players in each situation are equal in value and opposite in sign, i.e. and this game is called zero sum .

The process of "playing the matrix game" is represented as follows:

The payment matrix is ​​set;

Player I, regardless of player II, chooses one of the rows of this matrix, for example, -th;

Player II, regardless of player I, chooses one of the columns of this matrix, for example, - th;

The matrix element determines how much player I will receive from player II. Of course, if , then we are talking about the actual loss of player I.

We will call an antagonistic paired game with a payoff matrix a game.

Example

Let's consider the game.

The payment matrix is ​​set:

.

Let player I, independently of player II, choose the 3rd row of this matrix, and player II, independently of player I, choose the 2nd column of this matrix:

Then player I will receive 9 units from player II.

5.2. Optimal pure strategy in a matrix game

Optimal strategy is called a strategy of player I in which he will not reduce his winnings for any choice of strategy by player II, and such a strategy of player II in which he will not increase his loss for any choice of strategy by player I.

By choosing the th row of the payoff matrix as a move, player I ensures that he will win no less than the value in the worst case, when player II tries to minimize this value. Therefore, player I will choose the th row that will provide him with the maximum winnings:

.

Player II argues similarly and can certainly ensure a minimal loss:

.

The inequality is always true:

The quantity is called the lowest price of the game .

The quantity is called top price of the game .

Optimal strategies are called clean , if the equalities hold for them:

,

.

The quantity is called at the pure price of the game , If .

Optimal pure strategies form saddle point payment matrix.

For a saddle point the following conditions are met:

that is, the element is the smallest in the row and the largest in the column.

Thus, if the payoff matrix has saddle point , then you can find optimal pure strategies players.

The pure strategy of player I can be represented by an ordered set of numbers (vector), in which all numbers are equal to zero, except for the number in the -th place, which is equal to one.

Player II's pure strategy can be represented by an ordered set of numbers (a vector) in which all numbers are equal to zero, except for the number in the -th place, which is equal to one.

Example

.

By choosing any row of the payoff matrix as a move, player I ensures that in the worst case the winnings are no less than the value in the column marked:

Therefore, player I will choose the 2nd row of the payment matrix, which provides him with the maximum winnings regardless of the move of player II, who will try to minimize this value:

Player II reasons similarly and chooses the 1st column as his move:

Thus, there is a saddle point of the payment matrix:

corresponding to the optimal pure strategy for player I and for player II, in which player I will not reduce his winnings for any change in strategy by player II and player II will not increase his loss for any change in strategy by player I.

5.3. Optimal mixed strategy in a matrix game

If the payoff matrix does not have a saddle point, then it is irrational for any player to use one pure strategy. It is more profitable to use "probability mixtures" pure strategies. Then mixed strategies are identified as optimal.

Mixed strategy a player is characterized by the probability distribution of a random event consisting in the choice of a move by this player.

The mixed strategy of player I is such an ordered set of numbers (vector) that satisfies two conditions:

1) for , i.e. the probability of choosing each row of the payment matrix is ​​non-negative;

2), i.e., the choice of each of the rows of the payment matrix together represents a complete group of events.

Player II's mixed strategy will be an ordered set of numbers (vector) satisfying the conditions:

Payment amount to player I, who chose a mixed strategy

from player II, who chose a mixed strategy

,

represents the average value

.

Optimal called mixed strategies

And ,

if for any arbitrary mixed strategies and the following condition is satisfied:

i.e., with an optimal mixed strategy, player I’s gain is the greatest, and player II’s loss is the least.

If there is no saddle point in the payment matrix, then

,

i.e. there is a positive difference ( unallocated difference )

- ³ 0,

and players need to look for additional opportunities to confidently receive a larger share of this difference in their favor.

Example

Consider the game defined by the payoff matrix:

.

Let's determine whether there is a saddle point:

, .

It turns out that there is no saddle point in the payment matrix and the undistributed difference is equal to:

.

5.4. Finding optimal mixed strategies

for games 2x2

Determination of optimal mixed strategies for a payment matrix of dimensions is carried out by finding the optimal points of a function of two variables.

Let the probability of player I choosing the first row of the payment matrix

equal to . Then the probability of choosing the second row is equal to .

Let the probability of player II choosing the first column be equal to . Then the probability of choosing the second column is equal to .

The amount of payment to player I by player II is equal to:

The extreme value of player I's gain and player II's loss corresponds to the following conditions:

;

.

Thus, the optimal mixed strategies of players I and II are respectively equal to:

5.5. Geometric solution of games 2×n

As the dimension of the payment matrix increases from to, it is no longer possible to reduce the determination of optimal mixed strategies to finding the optimum of a function of two variables. However, given that one of the players has only two strategies, a geometric solution can be used.

The main stages of finding a solution to the game are as follows.

Let us introduce a coordinate system on the plane. Let's plot the segment on the axis. We draw perpendiculars from the left and right ends of this segment.

The left and right ends of the unit segment correspond to two strategies and available to player I. We will plot the winnings of this player on the drawn perpendiculars. For example, for the payment matrix

such payoffs of player I when choosing a strategy will be and , and when choosing a strategy they will be and .

Let us connect by straight line segments the winning points of player I, corresponding to the strategies of player II. Then the formed broken line, limiting the graph from below, determines the lower limit of the payoff of player I.

Finding the optimal mixed strategy of player I

,

which corresponds to the point on the lower bound of player I's payoff with the maximum ordinate.

Let us pay attention to the fact that in the example under consideration, using only two strategies and , corresponding to straight lines intersecting at the found point on the lower boundary of the payoff of player I, player II can prevent player I from getting a larger payoff.

Thus, the game is reduced to a game and the optimal mixed strategy of player II in the example under consideration will be

,

where the probability is the same as in the game:

5.6. Game solvingm× n

If a matrix game does not have a solution in pure strategies (i.e., there is no saddle point) and, due to the large dimension of the payoff matrix, cannot be solved graphically, then to obtain a solution, use linear programming method .

Let a payment matrix of dimension be given:

.

Need to find probabilities , with which player I must choose his moves so that this mixed strategy guarantees him a win of no less than the value regardless of the choice of moves by player II.

For each move chosen by player II, the payoff of player I is determined by the dependencies:

Let us divide both sides of the inequalities by and introduce new notations:

Equality

Will take the form:

Since player I seeks to maximize the payoff, the inverse must be minimized. Then the linear programming problem for player I will take the form:

under restrictions

The problem for player II is constructed similarly as dual:

under restrictions

Solving problems using the simplex method, we get:

,

5.7. Features of solving matrix games

Before solving the problem of finding optimal strategies, two conditions should be checked:

Is it possible to simplify the payment matrix;

Does the payment matrix have a saddle point?

Let's consider the possibility of simplifying the payment matrix:

Due to the fact that player I strives to get the largest win, the th row can be deleted from the payment matrix, since he will never use this move if the following relation is satisfied with any other row:

Similarly, striving for the smallest loss, player II will never choose the -th column in the payoff matrix as a move, and this column can be crossed out if the following relation is satisfied with any other -th column:

The simplest solution to the game is the presence of a saddle point in the simplified payment matrix, which meets the following condition (by definition):

Example

The payment matrix is ​​given:

.

Simplification of the payment matrix:

Presence of a saddle point:

5.8. Playing with nature

Unlike game theory problems in problems of statistical decision theory an uncertain situation does not have an antagonistic conflict connotation and depends on objective reality, which is usually called "nature" .

In matrix games with nature, player II is a set of uncertain factors that influence the effectiveness of decisions made.

Matrix games with nature differ from ordinary matrix games only in that when choosing an optimal strategy for player I, it is no longer possible to rely on the fact that player II will strive to minimize his loss. Therefore, along with the payment matrix, we introduce risk matrix :

where is the amount of risk of player I when using a move in conditions, equal to the difference between the payoff that player I would receive if he knew that the condition would be established, i.e. , and the winnings that he will receive, not knowing when choosing a move that the condition will be established.

Thus, the payment matrix is ​​uniquely transformed into a risk matrix, but the inverse transformation is ambiguous.

Example

Winning matrix:

.

Risk matrix:

Possible two problem statements about choosing a solution in a matrix game with nature :

Maximizing winnings;

Minimizing risk.

The decision-making problem can be posed for one of two conditions:

- at risk , when the probability distribution function of nature's strategies is known, for example, the random variable of the occurrence of each of the expected specific economic situations;

- in conditions of uncertainty , when such a probability distribution function is unknown.

5.9. Solving problems in statistical decision theory

at risk

When making decisions under risk conditions, player I knows the probabilities the onset of states of nature.

Then it is advisable for player I to choose the strategy for which the average winning value taken by line is maximum :

.

When solving this problem with a risk matrix, we obtain the same solution, corresponding minimum average risk :

.

5.10. Solving problems in statistical decision theory

in conditions of uncertainty

When making decisions under conditions of uncertainty, you can use the following criteria :

Maximum Wald criterion;

Savage's minimum risk criterion;

Hurwitz's criterion of pessimism - optimism;

Laplace's principle of insufficient reason.

Let's consider maximin Wald test .

The game with nature is played as with a reasonable aggressive opponent, i.e., a reinsurance approach is taken from the position of extreme pessimism for the payment matrix:

.

Let's consider Savage's minimum risk criterion .

An approach similar to the previous one from the position of extreme pessimism for the risk matrix:

.

Let's consider Hurwitz criterion of pessimism - optimism .

The opportunity is offered not to be guided by either extreme pessimism or extreme optimism:

where is the degree of pessimism;

at - extreme optimism,

at - extreme pessimism.

Let's consider Laplace's principle of insufficient reason .

It is assumed that all states of nature are equally probable:

,

.

Conclusions on the fifth section

In a matrix game, two players participate and the payoff function, which serves to determine the amount of payment from the losing player to the winning player, is represented in the form of a payment matrix. It was agreed that player I chooses one of the rows of the payment matrix as a move, and player II chooses one of its columns. Then at the intersection of the selected rows and columns of this matrix there is a numerical value of the payment to player I from player II (if this value is positive, then player I really won, and if it is negative, then player II essentially won).

If there is a saddle point in the payoff matrix, then the players have optimal pure strategies, i.e., to win, each of them must repeat his one optimal move. If there is no saddle point, then to win, each of them must use the optimal mixed strategy, that is, use a mixture of moves, each of which must be made with optimal probability.

Finding optimal mixed strategies for 2x2 games is done by calculating optimal probabilities using known formulas. Using the geometric solution of 2×n games, determining optimal mixed strategies in them is reduced to finding optimal mixed strategies for 2×2 games. To solve m×n games, the linear programming method is used to find optimal mixed strategies in them.

Some payment matrices can be simplified, as a result of which their dimension is reduced by removing rows and columns corresponding to unpromising moves.

If player II is a set of uncertain factors that depend on objective reality and do not have an antagonistic conflict overtones, then such a game is called a game with nature, and problems from the theory of statistical decisions are used to solve it. Then, along with the payment matrix, a risk matrix is ​​introduced and two formulations of the problem of choosing a solution in a matrix game with nature are possible: maximizing gain and minimizing risk.

Solving problems of the theory of statistical decisions under risk conditions shows that it is advisable for player I to choose the strategy for which the average value (mathematical expectation) of winnings, taken from a row of the payment matrix, is maximum, or (which is the same thing) the average value (mathematical expectation) of risk , taken by row of the risk matrix, is minimal. When making decisions under conditions of uncertainty, the following criteria are used: Wald's maximin criterion, Savage's minimum risk criterion, Hurwitz's pessimism-optimism criterion, Laplace's principle of insufficient reason.

Self-test questions

How are the basic concepts of game theory defined: move, strategy and payoff function?

What is the payoff function represented in a matrix game?

Why is a matrix game called zero-sum?

What is the process of playing a matrix game like?

What game is called the m×n game?

What matrix game strategy is called optimal?

What is the optimal strategy for a matrix game called pure?

What does the saddle point of the payment matrix mean?

What is the optimal strategy for a matrix game called mixed?

What does a player's mixed strategy look like?

What is the amount of payment to player I from player II who chose mixed strategies?

What mixed strategies are called optimal?

What does undistributed difference mean?

What method is used to find optimal mixed strategies for 2x2 games?

How are optimal mixed strategies found for 2×n games?

What method is used to find optimal mixed strategies for m×n games?

What are the features of solving matrix games?

What does simplification of the payment matrix mean and under what conditions can it be implemented?

Which matrix game is easier to solve when the payoff matrix has or does not have a saddle point?

What game theory problems are related to statistical decision theory problems?

How does the payment matrix translate into a risk matrix?

What two formulations of the problem of choosing solutions are possible in a matrix game with nature?

For what two conditions can decision-making problems be posed in a matrix game with nature?

What strategy is appropriate for player I to choose when solving a statistical decision theory problem under risk conditions?

What decision-making criteria can be used when solving statistical decision theory problems under conditions of uncertainty?

Examples of problem solving

1. The payment matrix indicates the amount of profit of the enterprise when it sells different types of products (columns) depending on established demand (rows). It is necessary to determine the optimal strategy of the enterprise for the production of different types of products and the corresponding maximum (on average) income from their sales.

Let us denote the given matrix by and introduce the variables . We will also use the matrix (vector). Then and , i.e. .

The inverse matrix is ​​calculated:

The values ​​are found:

.

Probabilities are calculated:

The average sales income is determined:

.

2. The Pharmacist company is a manufacturer of medicines and biomedical products in the region. It is known that the peak demand for some drugs occurs in the summer (cardiovascular drugs, analgesics), for others - in the autumn and spring (anti-infective, antitussive).

Costs per 1 standard unit units products for September-October were: for the first group (cardiovascular drugs and analgesics) – 20 rubles; for the second group (anti-infectious, antitussive drugs) – 15 rubles.

According to observations over the past few years, the company's marketing service has established that it can sell 3050 conventional units during the two months under consideration in warm weather conditions. units products of the first group and 1100 conventional units. units products of the second group; in cold weather conditions - 1525 arb. units products of the first group and 3690 conventional units. units second group.

In connection with possible changes in the weather, the task is set to determine the company's product production strategy that ensures maximum sales income at a selling price of 40 rubles. for 1 standard unit units products of the first group and 30 rub. - second group.

SOLUTION. The company has two strategies:

The weather will be warm this year;

The weather will be cold.

If the company adopts the strategy and in reality there is warm weather (nature strategy), then the manufactured products (3050 standard units of drugs of the first group and 1100 standard units of the second group) will be fully sold and the income will be

3050×(40-20)+1100×(30-15)=77500 rub.

In cool weather conditions (nature's strategy), the drugs of the second group will be sold in full, and the first group only in the amount of 1525 conventional units. units and some of the drugs will remain unsold. The income will be

1525×(40-20)+1100×(30-15)-20×()=16500 rub.

Likewise, if the form adopts the strategy and the weather is actually cold, then the income will be

1525×(40-20)+3690×(30-15)=85850 rub.

In warm weather, income will be

1525×(40-20)+1100×(30-15)-() ×15=8150 rub.

Considering the company and the weather as two players, we obtain the payment matrix

,

The price of the game is in the range

From the payment matrix it is clear that under all conditions the company’s income will be no less than 16,500 rubles, but if weather conditions coincide with the chosen strategy, then the company’s income can be 77,500 rubles.

Let's find a solution to the game.

Let us denote the probability of a firm using a strategy by , and a strategy by , and . Solving the game graphically, we get , while the price of the game is p.

The optimal plan for the production of drugs will be

Thus, it is advisable for the company to produce 2379 conventional units during September and October. units drugs of the first group and 2239.6 conventional units. units drugs of the second group, then in any weather she will receive an income of at least 46,986 rubles.

In conditions of uncertainty, if it is not possible for a company to use a mixed strategy (agreements with other organizations), we use the following criteria to determine the optimal strategy of the company:

Walde criterion:

Hurwitz criterion: for definiteness we accept , then for the company’s strategy

for strategy

It is advisable for a company to use a strategy.

Savage criterion. The maximum element in the first column is 77500, in the second column - 85850.

The elements of the risk matrix are found from the expression

,

where , ,

The risk matrix looks like

,

It is advisable to use the or strategy.

Therefore, it is advisable for the company to use the or strategy.

Let us note that each of the considered criteria cannot be considered completely satisfactory for the final choice of decisions, however, their joint analysis allows us to more clearly imagine the consequences of making certain management decisions.

Given a known probability distribution of various states of nature, the decision criterion is the maximum mathematical expectation of winning.

Let it be known for the problem under consideration that the probabilities of warm and cold weather are equal and amount to 0.5, then the optimal strategy of the company is determined as follows:

It is advisable for the company to use the or strategy.

Tasks for independent work

1. An enterprise can produce three types of products (A, B and C), while receiving a profit depending on demand. Demand, in turn, can take one of four states (I, II, III and IV). In the following matrix, the elements characterize the profit that the enterprise will receive when releasing the -th product and the -th state of demand:

A mixed strategy SA of player A is the use of pure strategies A1, A2, ..., Am with probabilities p1, p2, ..., pi, ..., pm and the sum of the probabilities is equal to 1: Mixed strategies of player A are written in the form of a matrix or in the form of a string SA = (p1, p2, ..., pi, ..., pm) Similarly, mixed strategies of player B are denoted: , or, SB = (q1, q2, ..., qi, ..., qn ), where the sum of the probabilities of the appearance of strategies is equal to 1: Pure strategies can be considered a special case of mixed ones and can be specified by a line in which 1 corresponds to a pure strategy. Based on the minimax principle, the optimal solution (or solution) of the game is determined: this is a pair of optimal strategies S*A , S*B in the general case mixed, having 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. The payoff corresponding to the optimal solution is called the game price v. The price of the game satisfies the inequality: ? ? v? ? (3.5) where? And? - lower and upper prices of the game. The following fundamental theorem of game theory is true - Neumann's theorem. Every finite game has at least one optimal solution, possibly among mixed strategies. Let S*A = (p*1, p*2, ..., p*i, ..., p*m) and S*B = (q*1, q*2, ..., q* i, ..., q*n) is a pair of optimal strategies. If a pure strategy is included in an optimal mixed strategy with a nonzero probability, then it is called active. The theorem about active strategies is true: if one of the players adheres to his optimal mixed strategy, then the payoff remains unchanged and equal to the cost of the game v, if the second player does not go beyond the limits of his active strategies. This theorem is of great practical importance - it provides specific models for finding optimal strategies in the absence of a saddle point. Consider a game of size 2x2, which is the simplest case of a finite game. If such a game has a saddle point, then the optimal solution is a pair of pure strategies corresponding to this point. A game in which there is no saddle point, in accordance with the main theorem of game theory, the optimal solution exists and is determined by a pair of mixed strategies S*A = (p*1, p*2) and S*B = (q*1, q*2) . In order to find them, we use the theorem on active strategies. If player A adheres to his optimal strategy S "A, then his average payoff will be equal to the cost of the game v, no matter what active strategy player B uses. For a 2x2 game, any pure strategy of the opponent is active if there is no saddle point. The gain of player A (loss of player B) is a random variable, the mathematical expectation (average value) of which is the price of the game. Therefore, the average payoff of player A (optimal strategy) will be equal to v for both the 1st and 2nd strategy of the opponent. Let the game be given by the payoff matrix. The average payoff of player A, if he uses the optimal mixed strategy, and player B uses the pure strategy B1 (this corresponds to the 1st column of the payoff matrix P), is equal to the price of the game v: a11 p*1+ a21 p*2 = v. Player A gets the same average payoff if player 2 uses strategy B2, i.e. a12 p*1+ a22 p*2= v. Considering that p*1+ p*2= 1, we obtain a system of equations for determining the optimal strategy S"A and the game price v: (3.6) Solving this system, we obtain the optimal strategy (3.7) and the game price (3.8) Applying the theorem active strategies when finding SВ* - the optimal strategy of player B, we find that for any pure strategy of player A (A1 or A2), the average loss of player B is equal to the price of the game v, i.e. (3.9) Then the optimal strategy is determined by the formulas: (3.10 )

Mathematical methods and models in economics

Matrix games

Introduction

In economic practice, situations often arise in which different parties pursue different goals. For example, the relationship between seller and buyer, supplier and consumer, bank and depositor, etc. Such conflict situations arise not only in the economy, but in other types of activities. For example, when playing chess, checkers, dominoes, lotto, etc.

A game is a mathematical model of a conflict situation involving at least two persons using several different methods to achieve their goals. The game is called steam room, if it involves two players. The game is called antagonistic, if one player's gain is equal to the other's loss. Therefore, to set up a game, it is enough to set the winning values ​​of one player in different situations.

Any method of action by a player depending on the current situation is called strategy. Each player has a specific set of strategies. If the number of strategies is finite, then the game is called ultimate, otherwise - endless . The strategies are called clean, if each player chooses only one strategy in a specific and not random manner.

Game solution is to choose a strategy that satisfies optimality condition. This condition is that one player receives maximum win, if the second one sticks to his strategy. Conversely, the second player receives minimum loss, if the first player sticks to his strategy. Such strategies are called optimal . Thus, The goal of the game is to determine the optimal strategy for each player.

Pure strategy game

Consider a game with two players A And IN. Let's assume that the player A It has m strategies A 1, A 2, …, A m, and the player IN It has n strategies B 1, B 2, …, B n. We will assume that the player's choice A strategies A i, and the player IN strategies Bj uniquely determines the outcome of the game, i.e. winnings a ij player A and winnings b ij player IN. Here i=1,2,…,m, j=1,2,…,n.

The simplest game with two players is the zero-sum game. , those. a game in which the interests of the players are directly opposed. In this case, the players' payoffs are related by the equality

b ij =-a ij

This equality means that the gain of one player is equal to the loss of the other. In this case, it is enough to consider only the winnings of one of the players, for example, the player A.

Each pair of strategies A i And Bj corresponds to winnings a ij player A. It is convenient to write down all these winnings in the form of the so-called payment matrix

The rows of this matrix correspond to the player's strategies A, and the columns – the player’s strategies IN. In general, such a game is called (m×n)-game.

Example 1. Two players A And IN toss a coin. If the sides of the coin match, then he wins A, i.e. player IN pays the player A a certain amount equal to 1, and if they do not match, then player B wins, i.e. on the contrary, the player A pays the player IN the same amount , equal to 1. Create a payment matrix.

Solution. According to the conditions of the problem