Special Operations Research Models
Chapter 12. Elements of game theory
Chapter 13. Inventory Management Models
Chapter 14. Network Planning and Management Models
Chapter 15. Elements of Queuing Theory
Elements of game theory
The concept of gaming models
In different fields of activity, one often has to deal with situations in which decisions must be made in conditions of uncertainty, and the choice of an effective solution without taking into account uncontrolled factors is impossible.
Uncertainty can be generated, in particular, by so-called conflict situations, in which two (or more) parties pursue different goals, and the results of any action of either party depend on the activities of the partner. In such situations that arise, for example, when playing chess, checkers, dominoes, etc., the result of each player's move depends on the opponent's retreat, the goal of the game is to win one of the partners.
In the economy, conflict situations are very diverse. These include, for example, the relationship between the supplier and the consumer, the buyer and the seller, the bank and the client, in the competitive struggle of firms for markets, in the exchange game, in the planning of advertising campaigns, etc.
In all these examples, the conflict situation arises from the difference in the interests of the partners and the desire of each of them to make optimal decisions that fulfill the stated goals to the greatest extent, while each has to be considered not only for its own purposes, but also for the partners' in advance decisions that these partners will take, i.e. there is a need to act in conditions of uncertainty.
Uncertainty arises in the case of non-conflict situations, i.e. when & quot; enemy & quot; has no opposing interests, but the winnings of the acting player largely depends on the enemy's unknown state in advance.
For example, the commercial success of the seller of seasonal goods depends on how much his strategy coincides with the weather conditions. In this case, as the opponent-partner is nature, or rather, its state - weather conditions, which introduce uncertainty into the decision-making process. Such situations are called games with nature, where nature is a generalized concept of an opponent who does not pursue his own goals in this conflict, and conflict can only be called conditional.
In any of these cases - with or without conflict - it is important to understand the nature of the uncertainty in the context of the task.
Uncertainty can be stochastic, ie. containing random variables whose distribution laws or, at least, their numerical characteristics are known and can be taken into account in solving the problem.
As an example, we can cite a class of maintenance and repair tasks for some equipment, when the probability of failures of serviced devices is known (statistically obtained).
More often, uncertainty is of another, non-stochastic type, when there is no data about the parameters that determine the successful solution of the problem.
Such uncertainties may be external, "objective", related to the conditions of the task, or "subjective", associated with the unpredictability of the conscious actions of persons participating in the situation in question.
Finally, we can talk about an intermediate type of uncertainty when a decision is made on the basis of any hypotheses about the laws of distribution of random variables.
In any case, tasks containing uncertainty can not be solved accurately and unambiguously. Uncertainty, i.e. lack of information, always entails an element of risk in making a decision.
However, at the present time a mathematical apparatus has been developed that allows, at least, to evaluate possible solutions from one or another point of view and choose the most reasonable of them.
Game Theory examines decision-making situations by several interacting individuals, hereinafter referred to as players.
The classical theory of games deals with the problems of constructing mathematical models for making optimal decisions under conditions of conflict and uncertainty and methods for their solution. The distribution of game theory, which deals with non-conflict situations, is sometimes called the theory of statistical solutions.
We will become acquainted with the basic concepts of the classical game theory and basic types of models in game theory.
The mathematical model of the conflict situation is called the game, the parties involved in the conflict are the players, and the outcome of the conflict is the win .
For each formalized game, rules are entered, ie. a system of conditions that determines: 1) options for the actions of opponents; 2) the amount of information of each player about the behavior of partners; 3) the gain to which each set of actions leads.
Generally, a win (or loss) can be quantified; for example, you can estimate the loss by zero, the win is one, and the draw is 0.5.
The choice and implementation of one of the actions stipulated by the rules is called the move of the player.
The moves can be personal and random.
A personal move is a conscious choice by the player of one of the possible actions (for example, a move in a chess game). A random move is a randomly selected action (for example, choosing a card from a shuffled deck or weather conditions at a given moment, if one considers the nature as one of the players).
The player's strategy is the set of rules that determine the choice of his action for each personal move, depending on the situation. Usually, in the process of playing with each personal move the player makes a choice depending on the specific situation. However, in principle it is possible that all decisions are made by the player in advance (in response to any current situation). This means that the player has chosen a specific strategy, which can be specified as a list of rules or programs. (This is how you can make a game using a computer.)
In accordance with various characteristics, the following basic classification of games is adopted:
- stochastic and non-stochastic games (depending on the type of uncertainty faced by players). In the first case, the distribution laws or at least the numerical characteristics of the random factors participating in the problem are known or can be at least estimated, in the second case there is no data on unknown parameters affecting the success of the solution of the problem;
- antagonistic (games with strict rivalry) and non-antagonistic games. In the first case, the goals of the players are opposite, in the second - they can coincide or one of the players may simply not have any goals (be neutral);
- strategic and non-strategic games (in the first subject of the system acts independently of the others, pursuing their goals, secondly - the subjects choose a common strategy)
- paired and multiple games (the game is called a pair if two players are involved, and multiple if the number of players is more than two);
- finite and infinite games (the game is called finite if each player has a finite number of strategies, and infinite - otherwise);
- coalition and non-cooperative, or cooperative and non-cooperative games (in the first possible exchange of information on possible strategies players, the subject of decision-making is a group or a coalition, there are obligatory agreements between the players of one coalition, in the second the individual acts as the subject of decision-making, the players make decisions independently);
- positional and non-position games. In positional games, each player has his own payment matrix, winning one does not mean losing another. The player must consistently make several decisions, and the choice of strategy is based on previous decisions.
The simplest of situations that contain non-stochastic uncertainty are conflict situations, when, as noted earlier, two or more parties pursue different objectives, and the results of any action by either party depend on the activities of the partner or partners.
An antagonistic pair game is called a zero-sum game, if the payoff of one of the players a is equal to
loss of another I), ie. to complete the game it is sufficient to specify the value of one of them: b = -a.
In order to solve the game, or to find the game solution, for each player, choose a strategy that satisfies the optimality condition . one of the players must receive a maximum winnings, when the second adheres to its strategy. At the same time, the second player must have a minimal loss, if the former adheres to his strategy. Such strategies are called optimal. Optimal strategies must satisfy the condition of sustainability, ie. any of the players should be disadvantageous to abandon their strategy in this game.
If the game is repeated many times, the players may be interested not in the win and loss in each particular game, but in the average win (loss ) in all games.
The goal of the game theory is to determine the optimal strategy for each player. When choosing the optimal strategy, it is natural to assume that both players behave reasonably in terms of their interests.
Next, in paragraphs (12.2-12.5), the main methods for solving conflict, pair, strategic, non-cooperative, finite, noncooperative games, the simplest from the point of view of finding the optimal solution, where the goal is the only gain as an indicator effectiveness.
In real life, many economic problems have more than one measure of efficiency. In addition, other restrictions are often not met in real situations: the interests of the partners are not necessarily antagonistic, the games can be multiple, coalition, cooperative, etc. The methods for solving such problems are beyond the scope of this manual, except for the basic principles of solving the "games with nature" discussed in paragraph 12.6.
How to ...
We made your life easier with putting together a big number of articles and guidelines on how to plan and write different types of assignments (Essay, Research Paper, Dissertation etc)