When the game does not have a saddle point. What game is called a saddle point game? matrix games and the concept of a saddle point

Consider a finite non-cooperative game with two participants. Player A has m strategies, player B has n strategies. The choice by player A of the strategy with number I, and by player B of the strategy with number j, determines the outcome of the game. Neither player knows the opponent's choice. Player A receives the amount a ij as winnings, and player B receives the amount b ij. This game is called a two-person game in normal shape .

A game of two persons with payoff matrices a ij and b ij is called antagonistic (or zero-sum game), if a ij + b ij = 0 for any strategy I of player A and any strategy j of player B. An antagonistic game is described by one matrix (payoff or payoff).

The theory of antagonistic games has been developed in the most detail. Her mathematical apparatus associated with such a branch of mathematics as linear programming.

In set-theoretic form, the zero-sum matrix game is written as

Н = ( A, B, H(m,n)), (1)

where A = (a 1 ,a 2 ,…a m ) is the set of strategies of player A;

B = (b 1 ,b 2 ,…b n ) - set of strategies for player B;

H(m,n) – payment matrix or winning matrix, dimension m x n.

Any element of the matrix H - (a ij) - numerically shows the amount of gain of player A if he adopts strategy i, and, accordingly, the amount of loss of player B if he adopts strategy j.

Solving game (1) means calculating a pair of strategies (a i ,b j) that the best way would satisfy the interests of both players.

The simplest case of a matrix zero-sum game is. a well-defined game (a yoke with a saddle point).

Quite a certain game or a game with a saddle point is a game in which the lower and top prices game, that is, the equality holds:

a = max min and ij= min max a ij = b.

i j j i

In this case, the value V = a = b called at the cost of the game , element and ij corresponding to equality is called a saddle point.

The simplicity of solving a saddle point game lies in the fact that the optimal strategies (in this case they are called pure strategies ) of both players are obtained immediately. For example 1 α = β = 6, i.e. the price of the game V = 6 USD, and the element of the matrix H located at the intersection of row 2 (strategy A 2) and column 2 (strategy B 2) is the saddle point of the game.

A saddle point is always the minimum element of the corresponding row and the maximum element of the corresponding column. This point is the equilibrium point of the game, which uniquely determines the pure optimal strategies.

Such a solution has the property of stability in the sense that if one of the players applies its optimal strategy, then any deviation of the other player from the optimal strategy may not be beneficial for him.

There can be several saddle points to a matrix. Meanwhile, the price of the game is always unique.

Player strategies, implying the rationality of opponents’ actions in achieving their goals, were received in game theory name of the principle guaranteed result, or the maximin principle.

The solution to the game in example 1 is the choice of strategy A 2 by player A and B 2 by player B, with the cost of the game V = 6.

Classification of games. Definition of a saddle point.

Games can be classified according to the number of players, the number of strategies, the nature of interaction between players, the nature of winning, the number of moves, the state of information, etc.

Depending on the number of players, games are divided into two and n players. The first of them are the most studied. Games of three and more players are less studied due to the fundamental difficulties that arise and technical capabilities obtaining a decision. How more players- the more problems.

Based on the number of strategies, games are divided into finite and infinite. If all players in a game have a finite number of possible strategies, then it is called ultimate. If at least one of the players has an infinite number of possible strategies, the game is called endless.

Based on the nature of interaction, games are divided into:

1) non-coalition: players do not have the right to enter into agreements or form coalitions;

2) coalition(cooperative) - can join coalitions.

IN cooperative games coalitions are determined in advance.

According to the nature of winnings, games are divided into: games with zero sum(the total capital of all players does not change, but is redistributed between players; the sum of winnings of all players is zero) and games with non-zero sum.

Based on the type of winning functions, games are divided into: matrix, bimatrix, continuous, convex, separable, duel type, etc.

Definition. If in a game with matrix A = (the lower net price is equal to the upper net price), then this game is said to have saddle point in pure strategies and net price games u = =.

Saddle point is a pair of pure strategies (i o, j o) respectively, players 1 and 2, at which equality is achieved = . If one of the players adheres to the strategy corresponding to the saddle point, then the other player cannot do better than to adhere to the strategy corresponding to the saddle point. Mathematically, this can be written another way: , Where i, j– any pure strategies of players 1 and 2, respectively; (i o, j o)– strategies that form a saddle point.

Thus, the saddle element is minimal in the i o -th row and maximum in the j o -th column in matrix A. Finding the saddle point of matrix A occurs as follows: in matrix A sequentially in each line find the minimum element and check whether this element is the maximum in its column. If yes, then it is a saddle element, and the pair of strategies corresponding to it forms a saddle point. A couple of pure strategies (i o, j o) players 1 and 2, forming a saddle point and a saddle element, is called game solution . Wherein i o And j o are called optimal clean strategies respectively players 1 and 2.

Properties of saddle points:

1. Equivalence. If there are several saddle points in the game, then the values of the payoff function in them are the same.

2. Interchangeability of optimal strategies. Players can replace their optimal strategies with others optimal strategies, in this case the equilibrium will not be disturbed, and the gain (loss) will remain unchanged.

13.Definition of a mixed strategy. Solution of the 2*2 game in mixed strategies.

A mixed strategy is when, instead of applying any one specific strategy, the participants in the game can randomly alternate (mix) their strategies in accordance with a specially designed scheme that provides the desired frequency, or probability, of the implementation of each of the strategies.

For each player you can set the following components:

Pia– probability of using the i-th strategy by A.

If you choose such a set Pia, which provides biggest win regardless of the actions of the second party, then this set of probabilities (p 1 a, p 2 a, ..., p ma) = S A and will be called a mixed strategy.

S * A = (p * 1 a, p * 2 a, …, p * ma) – optimal mixed strategy.

( S A ) – set mixed strategies from side A, from which the optimal one must be selected.

Game 2*2 in mixed strategies.

If at least one party has only 2 actions, we apply the graph-analytical solution method. Let's define the game in the form next matrix:

a 11	a 12
a 21	a 22

For this game, the following can be considered: the player plays against some pure strategy of the other side each time. At the same time, he can choose a probability ratio that will give him a guaranteed win equal to the price of the game.

A 11 p * 1 a + a 21 p * 2 a = γ - when playing against the first pure strategy of side B.

a 12 p * 1 a + a 22 p * 2 a = γ – against the second pure strategy of side B.

p * 1 a + p * 2 a = 1

Likewise for B:

A 11 p * 1 b + a 12 p * 2 b = γ - when playing against the first pure strategy of side B.

a 21 p * 1 b + a 22 p * 2 b = γ – against the second pure strategy of side B.

p * 1 b + p * 2 b = 1

Solution of the system of equations:

In order for the solutions obtained to make sense, the following relationships must be required:

If either one or the other is true, then the probabilities range from 0 to 1.

For side A: For side B:

In problems of theory statistical solutions payment matrices (for a discrete case) or a payment function (in a continuous case) are considered. Values in payment. matrix, or in payment. functions depend on 2 factors: 1. state of nature, 2. decision maker options.

Unlike game theory, here only one of the parties is considered as the party with rational behavior. Dr. side is considered as a natural factor with an element of uncertainty. In this case, it is conventionally considered that we are playing with nature, therefore, regarding the second side, various assumptions are made about how options for its state will be chosen.

The payment matrix can be formed as a result of solving an optimization problem when, for example, several equivalent solutions can be obtained. To make a selection the best option it is necessary to introduce a criterion function reflecting the decision maker’s preference system.

Geometric interpretation.

e 11	e 12
e 21	e 22
…	…
e n 1	e n2

F i – state of nature.

E i – solution options.

If you set aside the points (e i 1, e i 2), they will fill a certain space limited by the rectangle. RT – operating point. Inside this rectangle, 4 quadrants or 4 cones were formed. Let us consider the properties of points from these cones.

I: all points in at least one coordinate are better than the considered RT. Therefore, cone I is a cone of preference.

III: all points in at least one coordinate are obviously worse than RT.

II and IV: all points along one coordinate can be better, but worse along another. Therefore, these cones are cones of uncertainty.

To determine points that are more or less preferable than RT, it is necessary to consider different lines, representing lines of equations or lines of equivalent solutions.

The bisector line (line 1) corresponds to the neutral criterion function. Line 2 – pessimistic criterion function. Line 3 – optimistic criterion function.

Any of lines 1, 2, 3 connects points that are equivalent in preference. Points to the right and above any of these lines are preferable to points to the left and below.

The limiting case for the pessimistic function is the lines bounding the first quadrant. For the optimistic – the third quadrant.

Each player should not generally strive for a situation in which the value payoff functions maximum or minimum, and above all to the situation that may arise during the game. For a situation to be feasible, it must simultaneously achieve acceptable results for both Player I and Player II. Situations with this property are called equilibrium situations. They are the ones that can develop as a result of the players’ wise choice of their strategies. When identifying equilibrium situations it is necessary first of all to analyze sequentially each strategy of player I from the point of view of the most unfavorable outcome for him when player II chooses one of his strategies. To do this, the minimum winning value is found in the - row of the matrix. Let's denote it , where the sign (minimum by) denotes the operation of finding the minimum value payoff functions at all possible .

The numbers that are written next to the matrix in the form of an additional column characterize the minimum winnings of player I, taking into account the reasonable actions of player II. Therefore, player I must choose his strategy in such a way as to maximize his minimum payoff, that is, he must choose the strategy for which the number is maximum. Let us denote the maximum value by , that is

The quantity is called the bottom value of the game or maximin, and the corresponding strategy of player I is maximin strategy .

maximin strategy player I ensures himself (regardless of the opponent’s behavior) a guaranteed win of at least .

Next, we will analyze each strategy of player II from the point of view of the most unfavorable outcome for him when player I chooses one of his strategies. As a result of this, we will find the maximum loss values, which we denote

where the sign (maximum by) indicates the maximum value payoff functions at all possible .

The numbers , which are written under the matrix in the form of an additional line, characterize the maximum losses of player II, taking into account the reasonable actions of player I. Therefore, player II must choose his strategy in such a way as to minimize his maximum loss. To do this, he must choose the strategy in which the number will be minimal. Let us denote the minimum value by , that is

The quantity is called upper value of the game or minimax , and the corresponding strategy of player II is minimax strategy .

Obviously, when choosing the most careful minimax strategy Player II does not, under any circumstances, allow Player I to win more than .

Therefore, if both players behave reasonably, then player I's payoff must be no less than maximin and no more than minimax, that is:

A necessary and sufficient condition for the fulfillment of equality 7.2. is the existence of a saddle point. matrices. The term "saddle point" is borrowed from geometry. However, the presence of a saddle point in geometry is considered locally, and in game theory – globally. That is, the existence of a pair of integers is declared, for which it turns out to be both the minimum of its row and the maximum of its column. Therefore, player I, using the maximin strategy, guarantees himself a win, and player II, using the minimax strategy, does not allow him to win more than .

Therefore, for player I it is best to choose the strategy, and for player II it is best to choose . According to this, the strategies are called optimal, and the guaranteed payoff of player I is the value of the game, which is denoted by .

The set of optimal strategies is called game solution .

The principle of optimality underlying the players' choice of strategies is called minimax principle. According to this principle (or minimax criterion for reasonable behavior) each method of action is evaluated according to the worst outcome for it, and the optimal method is the one that leads to the best of the worst results.

Let's consider the game matrix.

So, the matrix has a saddle point , since the number 7 is the minimum of the second row and the maximum of the first column. Therefore, the optimal strategy of player I is maximin, and that of player II is minimax. The meaning of the game.

Having chosen his optimal strategy, player I can be sure that he will get at least 7, and player II, having chosen his optimal strategy, will not allow player I to get more than 7. These strategies constitute the solution to the saddle point game.

The solution to a saddle point game has the following property: if the players stick to their optimal strategies, then the payoff is equal to the value of the game. If one of the players adheres to his optimal strategy, and the other deviates from it, then he only loses in the game and in no case can increase his winnings. Moreover, the presence of information from any player that the other has chosen his optimal strategy does not serve as a basis for choosing any strategy other than the optimal (minimax or maximin) strategy. A pair of optimal strategies in a saddle point game creates an equilibrium situation, and any deviation from the optimal strategy results in disadvantageous consequences for the player using the suboptimal strategy. Thus, for the game under consideration, the presence of information from the player that player I has chosen the optimal strategy does not affect his choice of his optimal strategy. Otherwise, player II will give player I the opportunity to win 9 instead of 7.

Matrix games and the concept of a saddle point. Let's take a closer look at antagonistic games and their main properties. In a convenient way The task of a two-player zero-sum game is payment matrix. This, by the way, is where another name comes from - matrix games. Each element of the payment matrix and ij contains a numeric value player's winnings I (player II loses) if the first one applies the strategy i, and the second - strategy j. Terms winnings And loss should be understood in in a broad sense, because they can accept negative values and from an everyday point of view mean the opposite. The non-trivial nature of the problem lies primarily in the fact that each player makes his own choice without knowing about the choice of the other, which significantly complicates the process of optimizing the chosen strategy.

Classic example An antagonistic game is a game with two participants guessing numbers independently of each other. It is assumed that if their sum turns out to be even, then the winnings equal to 1 go to the first player, and if odd, then to the second. Assuming that for both players guessing an odd number is the first strategy, and an even number is the second, we can write the payoff matrix of this game:

The rows of matrix (6.1) correspond to the strategies of player I, the columns - to the strategies of player II, and its elements - to the results of the first player. It also follows from the definition of the game that the elements of this matrix, taken with the opposite sign, correspond to the winnings of the second player.

A more complex and meaningful payment matrix can be obtained if the proposed game is slightly modified. Let's assume that both participants have the right to guess the numbers from 1 to 4, which constitute their respective strategies. If the result of adding the intended numbers is even, then the second player pays the resulting amount to the first, and if it is odd, then the first player pays the second. Let's write down the payment matrix for such a game:

Some conventionality and artificiality in the formulation of the problem should not be in this case confuse us, since a model describing, for example, competition between two firms for a newly opened market for products, etc., can be reduced to a similar form.

As already noted, the most important question in game theory is the optimality of the solution (choice of strategy) for each player. From this point of view, let us analyze a certain matrix game for which the payment matrix is given A=║a ij║m x n. When player I chooses strategy i his guaranteed income regardless of the actions of player II will be min a i,j. Because he can choose i independently, then it is advisable to make this choice in such a way that, for any enemy strategy, it maximizes the amount of guaranteed income, i.e., ensures the receipt of max (min a i,j). This principle of choosing a strategy is called “ maximin principle" On the other hand, similar reasoning can be carried out regarding the actions of the second player. His biggest loser when choosing a strategy j will be max a i,j, and, therefore, he should choose a strategy in such a way as to minimize the amount of loss for any actions of the opponent, i.e., ensure min (max a i,j). that's the point minimax principle.

The validity of the following relation can be proven:

However, of obvious interest is the situation in which the value of the payoff (payment) received by player I when he chooses the maximin strategy is equal to the payment (loss) of player II with the minimax strategy

In this case the game is said to have saddle point. The coincidence of the values of the guaranteed payoffs of the players under the maximin and minimax strategies means the possibility of achieving some optimal (stable, equilibrium) state in the game, from which it is unprofitable for any of the participants to deviate. The concept of “optimality” here means that no reasonable (cautious) player seeks to change his strategy, since his opponent, in principle, will be able to choose a strategy that will give the worst result for the first one. Strategies i* And j* forming a saddle point are called optimal, and the value v = a i*j* called at the cost of the game. Troika ( i*, j*, v) counts solving a matrix game with a saddle point.

It is easy to see that not every game has a saddle point. In particular, both game (6.1) and game (6.2) do not have a saddle point. An example of a game that has a saddle point is the game with payment matrix (6.5).

In this matrix, the minimum (guaranteed) winnings of the first player in rows are 1, 5 and (-3). Consequently, his maximin choice will correspond to strategy 2, which guarantees a win of 5. For the second player, the maximum losses in the columns of the matrix will be 8, 10, 5, 17, so it makes sense to choose strategy 3, under which he will lose only 5. Thus, the second the strategy of the first player and the third strategy of the second form a saddle point with the value 5, i.e., for the game with matrix (6.5) it has a solution (2; 3; 5).

Depending on the number of players, games are divided into two and n players. The first of them are the most studied. Games of three or more players have been less studied due to the fundamental difficulties encountered and the technical possibilities of obtaining a solution. The more players there are, the more problems there are.

Based on the nature of interaction, games are divided into:

1) non-coalition: players do not have the right to enter into agreements or form coalitions;

2) coalition(cooperative) - can join coalitions.

In cooperative games, coalitions are predetermined.

Based on the type of winning functions, games are divided into: matrix, bimatrix, continuous, convex, separable, duel type, etc.

Definition. If in a game with a matrix A = (the lower net price is equal to the upper net price), then this game is said to have saddle point in pure strategies and net price games u = = .

Saddle point is a pair of pure strategies (i o, j o) respectively, players 1 and 2, at which equality is achieved = . If one of the players adheres to the strategy corresponding to the saddle point, then the other player cannot do better than to adhere to the strategy corresponding to the saddle point. Mathematically, this can be written differently: , where i, j– any pure strategies of players 1 and 2, respectively; (i o, j o)– strategies that form a saddle point.

Properties of saddle points:

1. Equivalence. If there are several saddle points in the game, then the values of the payoff function in them are the same.

2. Interchangeability of optimal strategies. Players can replace their optimal strategies with other optimal strategies, while the equilibrium will not be disrupted, and the gain (loss) will remain unchanged.

13.Definition of a mixed strategy. Solution of the 2*2 game in mixed strategies.

For each player you can set the following components:

Pia– probability of using the i-th strategy by A.

If you choose such a set Pia, which provides the greatest gain regardless of the actions of the second party, then this set of probabilities (p 1 a, p 2 a, ..., p ma) = S A and will be called a mixed strategy.

S * A = (p * 1 a, p * 2 a, …, p * ma) – optimal mixed strategy.

( S A ) – a set of mixed strategies on the part of A, from which the optimal one must be selected.

Game 2*2 in mixed strategies.

If at least one party has only 2 actions, we apply the graph-analytical solution method. Let's define the game in the form of the following matrix.