Matrix games: examples of problem solving. Antagonistic games with continuous strategies b) not always

Introduction

Real conflict situations lead to different types of games. Games differ in a number of ways: by the number of players participating in them, by the number of possible players, by the number of possible strategies, by the nature of the relationships between players, by the nature of winnings, by the type of winning functions, by the number of moves, by the nature of information provision of players, etc. .d. Let's consider the types of games depending on their division:

· According to the number of strategies, games are divided into final(each player has a finite number of possible strategies) and endless(where at least one of the players has an infinite number of possible strategies).

· According to the nature of winnings, games with zero sum(the total capital of the players does not change, but is redistributed between the players depending on the resulting outcomes) and games with non-zero sum.

· According to the type of functions, the winnings of the game are divided into matrix ( is a finite two-player zero-sum game in which the player's payoff is given A in the form of a matrix (a row of the matrix corresponds to the number of the player’s strategy used IN, column – the number of the player’s strategy used IN; at the intersection of the row and column of the matrix is ​​the player's payoff A, corresponding to the applied strategies.

For matrix games, it is proven that any of them has a solution, and it can be easily found by reducing the game to a linear programming problem), bimatrix game (this is a finite game of two players with a non-zero sum, in which the payoffs of each player are given by matrices separately for the corresponding player (in each matrix a row corresponds to the player’s strategy A, column – player strategies IN, at the intersection of the row and column in the first matrix is ​​the player’s payoff A, in the second matrix – the player’s winnings IN.

A theory of optimal player behavior has also been developed for bimatrix games, but solving such games is more difficult than ordinary matrix games. continuous games ( Continuous It is considered a game in which the payoff function of each player is continuous depending on the strategies. It has been proven that games of this class have solutions, but no practically acceptable methods for finding them have been developed), etc.

Other approaches to splitting games are also possible. Now let's return directly to the topic of research, namely Game Theory. First, let's define this concept.

Game theory - a branch of mathematics that studies formal models of making optimal decisions in conditions of conflict. In this case, conflict is understood as a phenomenon in which various parties are involved, endowed with different interests and opportunities to choose the actions available to them in accordance with these interests. In conditions of conflict, the enemy’s desire to hide his upcoming actions gives rise to uncertainty. On the contrary, uncertainty when making decisions (for example, based on insufficient data) can be interpreted as a conflict between the decision-making subject and nature. Therefore, game theory is also considered as a theory of making optimal decisions under conditions of uncertainty. It allows you to systematize some important aspects of decision making in technology, agriculture, medicine and sociology and other sciences. The parties involved in a conflict are called action coalitions; the actions available to them - by their strategies; possible outcomes of the conflict - situations.

The objective of the theory is that:

1) optimal behavior in the game.

2) study of the properties of optimal behavior

3) determining the conditions under which its use is meaningful (questions of existence, uniqueness, and for dynamic games, questions of nominal consistency).

4) construction of numerical methods for finding optimal behavior.

Game theory, created for the mathematical solution of problems of economic and social origin, cannot be generally reduced to classical mathematical theories created for solving physical and technical problems. However, a wide variety of classical mathematical methods are widely used in various specific questions of game theory.

In addition, game theory is internally connected with a number of mathematical disciplines. In game theory, the concepts of probability theory are used systematically and essentially. In the language of game theory, most problems of mathematical statistics can be formulated, and since game theory is related to the theory of decision making, it is considered as an essential component of the mathematical apparatus of operations research.

The mathematical concept of a game is unusually broad. It includes so-called parlor games (including chess, checkers, GO, card games, dominoes), but can also be used to describe models of an economic system with numerous buyers and sellers competing with each other. Without going into details, a game can be broadly defined as a situation in which one or more individuals (“players”) jointly control a number of variables and each player must take into account the actions of the entire group when making a decision. The “payment” that falls to each player is determined not only by his own actions, but also by the actions of other members of the group. Some of the “moves” (individual actions) during the game may be random. A clear illustration is the famous game of poker: the initial deal of cards is a random move. The sequence of bets and counter-bets preceding the final comparison of tricks is formed by the remaining moves in the game.

Mathematical GAME THEORY began with the analysis of sports, card and other games. They say that the discoverer of game theory, an outstanding American mathematician of the 20th century. John von Neumann came up with the ideas for his theory while watching a poker game. This is where the name “game theory” comes from.

Let's start exploring this topic with retrospective analysis of the development of game theory. Let us consider the history and development of the issue of game theory. Typically, a “family tree” is represented as a tree in the sense of graph theory, in which the branching occurs from some single “root”. The pedigree of game theory is a book by J. von Neumann and O. Morgenstern. Therefore, the historical course of development of game theory as a mathematical discipline is naturally divided into three stages:

First stage- before the publication of the monograph by J. von Neumann and O. Morgenstern. It can be called “pre-monographic”. At this stage, the game still acts as a specific competition, described by its rules in meaningful terms. Only at the end of it does J. von Neumann develop an idea of ​​the game as a general model of abstract conflict. The result of this stage was the accumulation of a number of specific mathematical results and even individual principles of future game theory.

Second phase is the monograph itself by J. von Neumann and

O. Morgenstern “Game Theory and Economic Behavior” (1944), which combined most of the previously obtained (however, by modern mathematical standards, quite few) results. She was the first to present a mathematical approach to games (both in the concrete and abstract sense of the word) in the form of a systematic theory.

Finally, on third stage game theory in its approach to the objects under study differs little from other branches of mathematics and develops to a large extent according to the laws common to them. At the same time, of course, the specifics of its practical applications, both actual and possible, have a significant influence on the formation of directions in game theory.

However, even mathematical game theory is not able to completely predict the outcome of some conflicts. It seems possible to identify three main reasons for the uncertainty of the outcome of the game (conflict).

Firstly, these are games in which there is a real opportunity to study all or at least most variants of gaming behavior, of which one is the most true, leading to winning. Uncertainty is caused by a significant number of options, so it is not always possible to explore absolutely all options (for example, the Japanese game of GO, Russian and international checkers, British reversi).

Secondly, the random influence of factors on the game is unpredictable by players. These factors have a decisive influence on the outcome of the game and can only to a small extent be controlled and determined by the players. The final outcome of the game is determined only to a small, extremely insignificant extent by the actions of the players themselves. Games whose outcome is uncertain due to random reasons are called gambling. The outcome of the game is always probabilistic or conjectural (roulette, dice, toss).

Thirdly, uncertainty is caused by the lack of information about what strategy the playing opponent is following. The players’ ignorance of the opponent’s behavior is fundamental and is determined by the very rules of the game. Such games are called strategic games.

Game theory is one of the important sections of “Operations Research” and represents the theoretical foundations of mathematical models for making optimal decisions in conflict situations of market relations, which are of a competitive nature, in which one opposing party wins over the other at the expense of the other’s loss. Along with this situation, within the framework of the science of Operations Research, which provides a mathematical description of the formulation of various decision-making problems, situations of risk and uncertainty are considered. In a situation of uncertainty, the probabilities of the conditions are unknown and there is no way to obtain additional statistical information about them. The environment surrounding the solution of a problem, which manifests itself in certain conditions, is called “nature,” and the corresponding mathematical models are called “games with nature” or “statistical game theory.” The main goal of game theory is to develop recommendations for the satisfactory behavior of players in a conflict, that is, to identify an “optimal strategy” for each of them.

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

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

Introduction

1. Theoretical part

1.3 Game order 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, that is, 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 payoff 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 sequentially 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, the 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 presented 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 is or, then we 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 of calculations 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 the specified 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 the match of the local club’s 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

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 on the organization of 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:

Let's assume that the second player chose his 2nd strategy, then the first one 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

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

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

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

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, divided by the number of games, is placed, 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

Table 8. Final table after twenty games played

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 approximate the true game's true cost indefinitely, and the relative frequencies of the players' strategies will no longer necessarily approximate the players' true optimal mixed strategies.

Analysis of results

In this course work, we studied the material of finding solutions to antagonistic 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 the Brown method, a task was drawn up in which the trade union and company 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

Similar documents

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

course work, added 05/05/2010


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

presentation, added 10/23/2013


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

abstract, added 02/13/2011


Learn general information about matrix and zero-sum games. The concept of positional play, tree, information set. Consideration of the maximin principle and the principle of equilibrium. Pareto optimality. Positional non-antagonistic game, its properties.

course work, added 10/17/2014


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

thesis, added 08/08/2007


Drawing up a payment matrix, searching for the lower and upper net prices of the game, the maximin and minimax strategies of the players. Simplification of the payment matrix. Solving a matrix game using a reduction to a linear programming problem and the “Search for a solution” add-on.

test, added 11/10/2014


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

course work, added 08/17/2013


Basic information about the simplex method, assessment of its role and significance in linear programming. Geometric interpretation and algebraic meaning. Finding the maximum and minimum of a linear function, special cases. Solving the problem using the matrix simplex method.

thesis, added 06/01/2015


Techniques for constructing mathematical models of computer systems that reflect the structure and processes of their functioning. The number of file accesses in the process of solving an average problem. Determining the possibility of placing files in external memory drives.

laboratory work, added 06/21/2013


Design of a mathematical model. Description of the game of tic-tac-toe. Model of a logic game based on Boolean algebra. Digital electronic devices and development of their mathematical model. Game console, game controller, game field line.

Consider a finite zero-sum pairs game. Let us denote by a player's winnings A, and through b– player’s winnings B. Because a = –b, then when analyzing such a game there is no need to consider both of these numbers - it is enough to consider the winnings of one of the players. Let it be, for example, A. In what follows, for convenience of presentation, A we will conventionally call " We"and the side B – "enemy".

Let us have m possible strategies A 1 , A 2 , …, Am, and the enemy n possible strategies B 1 , B 2 , …, Bn(such a game is called a game m×n). Let us assume that each side has chosen a certain strategy: we have chosen A i, opponent B j. If the game consists only of personal moves, then the choice of strategies A i And B j uniquely determines the outcome of the game - our winnings (positive or negative). Let us denote this gain by a ij(the gain when we choose a strategy A i, and the enemy – strategies B j).

If the game contains, in addition to personal, random moves, then the winnings with a pair of strategies A i, B j is a random value depending on the outcomes of all random moves. In this case, a natural estimate of the expected payoff is mathematical expectation of a random win. For convenience, we will denote by a ij both the winning itself (in a game without random moves) and its mathematical expectation (in a game with random moves).

Let's assume that we know the values a ij for each pair of strategies. These values ​​can be written as a matrix, the rows of which correspond to our strategies ( A i), and the columns – enemy strategies ( B j):

Such a matrix is ​​called payment matrix of the game or simply matrix of the game.

Note that constructing a payoff matrix for games with a large number of strategies can be a difficult task. For example, for a chess game, the number of possible strategies is so large that constructing a payoff matrix is ​​practically impossible. However, in principle, any finite game can be reduced to matrix form.

Let's consider example 1 antagonistic game 4x5. We have four strategies at our disposal, the enemy has five strategies. The game matrix is ​​as follows:

What strategy should we (i.e. the player A) take advantage? Whatever strategy we choose, an intelligent opponent will respond with a strategy for which our payoff will be minimal. For example, if we choose the strategy A 3 (tempted by winning 10), the opponent will respond by choosing a strategy B 1, and our payoff will be only 1. Obviously, based on the principle of caution (and it is the basic principle of game theory), we must choose the strategy in which our minimum winnings are maximum.

Let us denote by αi minimum winning value for the strategy A i:

and add a column containing these values ​​to the game matrix:

When choosing a strategy, we should prefer the one for which the value αi maximum. Let us denote this maximum value by α :

Magnitude α called lower price of the game or maximin(maximum minimum win). Player strategy A, corresponding to maximin α , called maximin strategy.

In this example, maximin α is equal to 3 (the corresponding cell in the table is highlighted in gray), and the maximin strategy is A 4 . By choosing this strategy, we can be sure that for any behavior of the enemy we will win no less than 3 (and maybe more if the enemy’s behavior is “unreasonable”). This value is our guaranteed minimum, which we can ensure for ourselves by adhering to the most cautious ("reinsurance") strategy.

Now let's carry out similar reasoning for the enemy B B A B 2 – we will answer him A .

Let us denote by β j A B) for strategy A i:

β j β :

7. WHAT IS CALLED THE TOP VALUE GAME Now let’s carry out similar reasoning for the opponent B. He is interested in minimizing our winnings, that is, giving us less, but he must count on our worst behavior for him. For example, if he chooses the strategy B 1, then we will answer him with a strategy A 3 and he will give us 10. If he chooses B 2 – we will answer him A 2, and he will give 8, etc. Obviously, a cautious opponent should choose the strategy in which our maximum winnings will be minimal.

Let us denote by β j maximum values ​​in the columns of the payoff matrix (maximum winnings of the player A, or, which is the same thing, the player’s maximum loss B) for strategy A i:

and add a row containing these values ​​to the game matrix:

When choosing a strategy, the enemy will prefer the one for which the value β j minimal. Let's denote it by β :

Magnitude β called top price of the game or minimax(minimum maximum winnings). The strategy of the enemy (player) corresponding to the minimax B), called minimax strategy.

Minimax is the value of the win, more than which a reasonable opponent will certainly not give us (in other words, a reasonable opponent will lose no more than β ). In this example, minimax β is equal to 5 (the corresponding cell in the table is highlighted in gray) and it is achieved using the enemy’s strategy B 3 .

So, based on the principle of caution (“always assume the worst!”), we must choose a strategy A 4, and the enemy - strategy B 3. The principle of caution is fundamental in game theory and is called minimax principle.

Let's consider example 2. Let the players A And IN simultaneously and independently of each other, write down one of three numbers: either “1”, or “2”, or “3”. If the sum of the written numbers is even, then the player B pays the player A this amount. If the amount is odd, then the player pays this amount A to the player IN.

Let's write down the payment matrix of the game and find the lower and upper prices of the game (the strategy number corresponds to the written number):

Player A must adhere to the maximin strategy A 1 to win no less than –3 (that is, to lose no more than 3). Minimax player strategy B– any of the strategies B 1 and B 2, guaranteeing that he will give no more than 4.

We get the same result if we write the payoff matrix from the player's point of view IN. In fact, this matrix is ​​obtained by transposing the matrix constructed from the player's point of view A, and changing the signs of the elements to the opposite (since the player’s winnings A– this is the player’s loss IN):

Based on this matrix it follows that the player B must follow any of the strategies B 1 and B 2 (and then he will lose no more than 4), and the player A– strategies A 1 (and then he will lose no more than 3). As you can see, the result coincides exactly with that obtained above, so when analyzing, it does not matter from the point of view of which player we conduct it.

8 WHAT IS CALLED THE VALUE GAME.

9. WHAT IS THE MINIMAX PRINCIPLE. 2. Lower and upper price of the game. Minimax principle

Consider a matrix game of the type with a payoff matrix

If the player A will choose a strategy A i, then all its possible payoffs will be elements i th row of the matrix WITH. Worst for the player A case when the player IN applies a strategy that is appropriate minimum element of this line, the player's win A will be equal to the number .

Therefore, to get the biggest win, the player A you need to choose the strategy for which the number maximum.

Tests for final control

1. Antagonistic game can be set:

a) a set of strategies for both players and a saddle point.

b) a set of strategies for both players and the payoff function of the first player.

2. The price of the game always exists for matrix games in mixed strategies.

a) yes.

3.If all the columns in the payoff matrix are the same and have the form (4 5 0 1), then what strategy is optimal for the 1st player?

a) first.

b) second.

c) any of the four.

4. Let in a matrix game one of the mixed strategies of the 1st player have the form (0.3, 0.7), and one of the mixed strategies of the 2nd player have the form (0.4, 0, 0.6). What is the dimension of this matrix?

a) 2*3.

c) another dimension.

5. The principle of dominance allows you to remove from the matrix in one step:

a) entire lines.

b) individual numbers.

6. In the graphical method for solving 2*m games, one finds directly from the graph:

a) optimal strategies of both players.

b) the price of the game and the optimal strategies of the 2nd player.

c) the price of the game and the optimal strategies of the 1st player.

7. The graph of the lower envelope for the graphical method of solving 2*m games is in the general case:

a) broken.

b) straight.

c) parabola.

8. In a 2*2 matrix game there are two components of the player’s mixed strategy:

a) determine each other’s values.

b) independent.

9. In a matrix game, the element aij is:

a) the winnings of the 1st player when he uses the i-th strategy, and the 2nd - the j-th strategy.

b) the optimal strategy of the 1st player when the opponent uses the i-th or j-th strategy.

c) the loss of the 1st player when he uses the j-th strategy, and the 2nd - the i-th strategy.

10.The matrix element aij corresponds to the saddle point. The following situations are possible:

a) this element is strictly the smallest in the line.

b) this element is the second in order in the line.

11. In the Brown-Robinson method, each player, when choosing a strategy at the next step, is guided by:

a) the enemy’s strategies at previous steps.

b) your strategies in the previous steps.

c) something else.

12. According to the criterion of mathematical expectation, each player proceeds from the fact that:

a) the worst situation for him will happen.

c) all or some situations are possible with some given probabilities.

13. Let a matrix game be given by a matrix in which all elements are negative. The price of the game is positive:

b) no.

c) there is no clear answer.

14. The price of the game is:

a) number.

b) vector.

c) matrix.

15.What is the maximum number of saddle points that can be in a game of dimension 5*5 (the matrix can contain any numbers):

16. Let in a matrix game of dimension 2*3 one of the mixed strategies of the 1st player have the form (0.3, 0.7), and one of the mixed strategies of the 2nd player have the form (0.3, x, 0.5). What is the number x?

c) another number.

17. For what dimension of the game matrix does the Wald criterion turn into the Laplace criterion?

c) only in other cases.

18. The upper price of the game is always less than the lower price of the game.

b) no.

b) the question is incorrect.

19. What strategies are there in a matrix game:

a) clean.

b) mixed.

c) both.

20. In some antagonistic game, can the values ​​of the payoff function of both players for some values ​​of the variables equal 1?

a) always.

b) sometimes.

c) never.

21. In a matrix game, let one of the mixed strategies of the 1st player be of the form (0.3, 0.7), and one of the mixed strategies of the 2nd player be of the form (0.4, 0.1,0.1,0.4). What is the dimension of this matrix?

c) another dimension.

22. The principle of dominance allows you to remove from the matrix in one step:

a) entire columns,

b) individual numbers.

c) submatrices of smaller sizes.

23. In a 3*3 matrix game there are two components of the player’s mixed strategy:

a) determine the third.

b) do not define.

24. In a matrix game, the element aij is:

a) loss of the 2nd player when he uses the j-th strategy, and the 2nd - the i-th strategy.

b) the optimal strategy of the 2nd player when the opponent uses the i-th or j-th strategy,

c) the winnings of the 1st player when he uses the j-th strategy, and the 2nd - the i-th strategy,

25. The matrix element aij corresponds to the saddle point. The following situations are possible:

a) this element is the largest in the column.

b) this element is strictly the largest in order in the line.

c) the string contains elements both greater and less than this element.

26. According to the Wald criterion, each player assumes that:

a) the worst situation for him will happen.

b) all situations are equally possible.

c) all situations are possible with certain given probabilities.

27. The lower price is less than the upper price of the game:

b) not always.

c) never.

28. The sum of the components of a mixed strategy for a matrix game is always:

a) equals 1.

b) non-negative.

c) positive.

d) not always.

29. Let in a matrix game of dimension 2*3 one of the mixed strategies of the 1st player have the form (0.3, 0.7), and one of the mixed strategies of the 2nd player have the form (0.2, x, x). What is the number x?

Moscow Energy Institute

(Technical University)

Lab report

in game theory

“A program for finding optimal strategies for a paired zero-sum game given in matrix form”

Completed by students

group A5-01

Ashrapov Daler

Ashrapova Olga

Basic concepts of game theory

Game theory is designed to resolve conflict situations , i.e. situations in which the interests of two or more parties, pursuing different goals, collide.

If the goals of the parties are directly opposite, then they speak of antagonistic conflict .

Game called a simplified formalized model of a conflict situation.

A single play of a game from start to finish is called party . The result of the game is payment (or winnings ).

The party consists of moves , i.e. choices of players from a certain set of possible alternatives.

The moves may be personal And random.Personal move , Unlike random , involves the player’s conscious choice of some option.

Games in which there is at least one personal move are called strategic .

Games in which all moves are random are called gambling .

When making a personal move they also talk about strategies player, i.e. about a rule or set of rules that determine a player's choice. At the same time, the strategy must be comprehensive, i.e. the choice must be determined for any possible situation during the game.

Game theory problem– finding optimal strategies for players, i.e. strategies that provide them with maximum gain or minimum loss.

Classification of game-theoretic models

Game n persons are usually denoted as, where
- set of strategies for the i-th player,
- payment for the game.

In accordance with this designation, the following classification of game-theoretic models can be proposed:

Discrete (multiple strategies discrete)

Final

Endless

Continuous (multiple strategies continuous)

Endless

n persons (
)

Coalition (cooperative)

Non-coalition (non-cooperative)

2 persons (pairs)

Antagonistic (zero-sum games)

(the interests of the parties are opposite, i.e. the loss of one player is equal to the gain of the other)

Non-antagonistic

With complete information (if the player making a personal move knows the entire background of the game, i.e. all the opponent’s moves)

With incomplete information

With zero amount (total payment equals zero)

Non-zero sum

One-move (lotteries)

Multi-pass

Matrix representation of a paired zero-sum game

In this tutorial we will look at two-person antagonistic games , given in matrix form. This means that we know many strategies of the first player (player A){ A i }, i = 1,…, m and a variety of strategies for the second player (player B){ B j }, j = 1,..., n, and also given the matrix A = || a ij || winnings of the first player. Since we are talking about an antagonistic game, it is assumed that the gain of the first player is equal to the loss of the second. We assume that the matrix element a ij– the winnings of the first player when he chooses a strategy A i and the second player’s response to him with a strategy B j. We will denote such a game as
, Where m - number of player strategies A,n - number of player strategies IN. In general, it can be represented by the following table:

Example 1

As a simple example, consider a game in which a game consists of two moves.

1st move: Player A chooses one of the numbers (1 or 2) without informing his opponent about his choice.

2nd move: Player IN chooses one of the numbers (3 or 4).

Bottom line: Players' Choices A And IN fold up. If the sum is even, then IN pays its value to the player A, if odd - vice versa, A pays the amount to the player IN.

This game can be presented in the form
in the following way:

It is easy to see that this game is antagonistic; in addition, it is a game with incomplete information, because to the player IN, making a personal move, it is not known what choice the player made A.

As noted above, the task of game theory is to find the optimal strategies of players, i.e. strategies that provide them with maximum gain or minimum loss. This process is called game solution .

When solving a game in matrix form, you should check the game for the presence saddle point . To do this, two values ​​are entered:

– lower estimate of the price of the game and

– upper estimate of the price of the game.

The first player will most likely choose the strategy in which he receives the maximum win among all possible answers of the second player, and the second player, on the contrary, will choose the one that minimizes his own loss, i.e. possible winning of the first.

It can be proven that α ≤ V ≤ β , Where V–game price , i.e., the probable win of the first player.

If the relation holds α = β = V, then they say that the game has a saddle point
, And can be solved in pure strategies . In other words, there are a couple of strategies
, giving the player AV.

Example 2

Let's return to the game we considered in Example 1 and check it for the presence of a saddle point.

For this game
= -5,
= 4,
, therefore, it does not have a saddle point.

Let us note once again that this game is a game with incomplete information. In this case, we can only advise the player A choose a strategy , because in this case, he can get the largest win, however, subject to the player’s choice IN strategies .

Example 3

Let's make some changes to the rules of the game from example 1. We will provide the player IN player selection information A. Then have IN two additional strategies will appear:

- a strategy beneficial to A. If the choice A - 1, That IN chooses 3 if choice A - 2, That IN chooses 4;

- a strategy that is not beneficial for A. If the choice A - 1, That IN chooses 4 if choice A - 2, That IN chooses 3.

This game is with complete information.

In this case
= -5,
= -5,
, therefore, the game has a saddle point
. This saddle point corresponds to two pairs of optimal strategies:
And
. Game price V= -5. It is obvious that for A such a game is unprofitable.

Examples 2 and 3 are a good illustration of the following theorem, proven in game theory:

Theorem 1

Every paired antagonistic game with complete information can be solved in pure strategies.

That. Theorem 1 says that any two-player game with complete information has a saddle point and there is a pair of pure strategies
, giving the player A sustainable winnings equal to the price of the game V.

In the absence of a saddle point, the so-called mixed strategies :, Where p i Andq j– probabilities of choosing strategies A i And B j the first and second players respectively. The solution to the game in this case is a pair of mixed strategies
, maximizing the mathematical expectation of the game price.

The following theorem generalizes Theorem 1 to the case of a game with incomplete information:

Theorem 2

Any paired antagonistic game has at least one optimal solution, i.e., a pair of mixed strategies in the general case
, giving the player A sustainable winnings equal to the price of the game V, and α ≤ V ≤ β .

In the special case, for a game with a saddle point, the solution in mixed strategies looks like a pair of vectors in which one element is equal to one and the rest are equal to zero.