Course 14 : Game Theory

Author: OptimizationCity Group

Introduction

The game is a description of economic, social and political activities of people. Each of these activities or games has a structure and rules according to which the players play the game to achieve their goals. These rules and structure tell us what actions each player can take and why. To analyze a game, it is necessary to know the rules of each game in order to be able to analyze how people choose from different actions and what the consequences are for them.

Definition of game theory

In the real world, every person is faced with the reactions of others in their decisions. The outcome of the situations in which a person is placed, on the one hand, depends on his decisions, and on the other hand, it depends on the decisions of others. Therefore, people in their real life are always faced with situations that can be on the same side or conflict with others. These features have been an important factor for experts to pay attention to game theory. They seek to show how games, wars, economic behavior and other activities are similar in making strategic decisions. In fact, it can be said that this is the basis for the formation of game theory.

In this regard, the first comprehensive and systematic study to apply game theory in economics was done by Von Neumann and Oskar Morgenstern in 1944, whose opinions were published in a book titled “Game Theory and Economic Behavior”. After several developments, game theory was applied to help explain which decisions about cooperation or non-cooperation with competitors are best. John Nash, John Harsanyi and Reinhard Selten were the three theorists who won the Nobel Prize in Economics in 1994 for their original studies in the field of game theory.

Anyway, the general idea of ​​the game means fun and entertainment, which is fundamentally different from what is proposed in the theory of games. In game theory, a game is a set of rules, arrangements, and relationships known to all players. In other words, a game is a set of rules known to all players, which determines what choices each of them can make and what consequences each choice leads to. Most games have a following features:

First, games have rules that evaluate the consequences of each decision to that decision.

Second, every game has a number of rational decision makers or players who are seriously trying and competing to get the best result.

Game elements and categories of games

Games can be divided into different aspects. This division can be done based on the number of players, the number of strategies, agreement and disagreement, perfect information and imperfect information. First, let’s talk about the elements of a game.

player

In a game, each decision maker is called a player. Therefore, the player is a person who makes decisions in the game and these decisions are based on his rational behavior, so that he can reach the best possible result by considering the behavior of his competitors. Games are divided into two-player, three-player or n-player games according to the number of players. Of course, we note that in a two-player game, each player may include a group, such as a two-player game between two countries regarding the determination of customs tariff rates.

Strategy

Strategy is an action or a set of actions that a player can choose according to the information he has. In a game, each player has a number of strategies that he can choose according to his conditions and goals. A player’s strategies may be limited, such as a coin game where there are only two strategies or a chess game where there is a fixed number of moves. But consider a problem where there are two firms. In determining the level of production, there are infinite strategies, in this case, the number of strategies is unlimited.

Outcome

In general, what the player gets in a game is called an outcome. Outcome can express profit, favorability, etc. The total outcome of the game are obtained from the total outcome of all players after the end of the game. Based on this, the total outcome, or winning, is another criterion in the division of games, which divides them into three types.

In the first type, the sum of the players’ winnings is zero, like a two-player game of coin toss, where one player’s win is equal to the other player’s loss. Here, the algebraic sum of two players’ wins is zero, which is called a two-person game with zero sum or a two-person game with zero sum.

The second type is games in which the sum of the winnings of both players is equal to a fixed number in any situation, such as two producers who control the market for a product and the consumers of this product spend a fixed amount to buy this product in any situation. do In this case, the total winnings of the two players will be spent on buying this product. In this case, the total winnings of two players is equal to the fixed amount that applicants pay for that item. Such a game is called a game with a fixed total win or, in short, a fixed sum game. The first type of game is not different from the second type and they are interchangeable.

The third type is the games whose total win is variable, because the total win changes according to the players’ strategy choices.

Cooperative and non-cooperative games

One of the important criteria in the division of games is whether there is a negotiation between the players before playing the game or not. If there is a negotiation between the players and an agreement is reached, it is called a cooperative game. But if there is no such negotiation or if it does not lead to an agreement, it is called a non-cooperative game. In fact, in a cooperative game, players have the possibility to communicate with each other and negotiate with each other to reach a workable agreement.

Strategic and random games

Chess is an example of a strategic game where players make moves and react to each other. In such games, the choice of strategies and the outcome of the game depends on the player’s intelligence, talent and resourcefulness. On the other hand, there are games where the selection of strategies and their results are mostly random. For example, consider two people in a coin toss game, each of whom has a coin in his hand and throws it. For example, it has already been determined that if both heads come out, the first one pays 100 unit to the second one. This is a random game, and the player has no choice in his choices, and intelligence does not play a role in it. Therefore, the main difference between random and strategic game is the amount of intelligence and skill used by the players.

Complete and incomplete information games

There is another division of games which is based on the amount of information the players have about the state of the game. If each player knows the number of players, the strategies of each of them, as well as the amount of winning and losing at the end of the game, it is called a game with complete information. But in a game, players may not have complete knowledge of winning and losing, which is called a game with incomplete information.

Static and dynamic games

A static game is a game in which the movements of the players are simultaneous. In these games, the situation is described for the players in such a way that they all make a decision at the same time. In the dynamic game, the movements of the players are sequential, that is, one player moves by observing the movement of the first player. If in a dynamic game, the second player cannot observe the movement of the first player, this game is not much different from a static game. In this case, the only difference is that we have given one of the players the point of making the first move, according to which he can be the starter of the game. Rock-paper-scissors is one of the static games, and chess is one of the dynamic games.

Equilibrium

Equilibrium means a static state from which there is no desire to change. In game theory, they show the equilibrium of the situation that the players are not interested in changing. Therefore, finding the balance of the game means finding a solution for the game in which each player has formed his behavior based on the arguments, predictions, preferences and behavior of competitors, and no player has the desire to change it. In game theory, equilibrium does not mean the best state or the best solution, but rather a solution to the game that the players are not interested in changing.

In the figure below, the types of non-cooperative games are categorized, which will be discussed in detail below.

Static games with complete information

A static game is a game in which the players move simultaneously and there is no lead or delay. It is as if the players choose their strategies based on their guesses and information without meeting each other or observing each other’s behavior. On the other hand, it is assumed that there is complete information in these games. Complete information means that every player knows the number of players, their strategies, and the winnings at the end of the game. Here, the meaning of win is the benefit from the game, such as profit or utility. In the following, the most important type of static game will be explained with complete information.

Two-person game

In this game, two persons play a role in the game and they are non-cooperative. In the following, we will specifically discuss a specific type of this type of game called the two-person zero-sum game.

In Two Person-Zero Sum Game, two players are present, one of them is player 1 or row player and the other player is player 2 or column player. player 1 is only allowed to choose one of his m policies. Similarly, player 2 or column player is allowed to choose one of n policies. The reason why this game is called zero sum is that the amount of one player’s win is exactly equal to the second player’s loss, and the algebraic sum of the net win of both players is equal to zero.

If player 1 or row player chooses his i-th policy and player 2 or column player chooses his j-th policy, player 1 receives (wins) amount aij and player 2 pays (loses) amount aij. It is possible for a player to receive from another player’s payment, and that is why we call the Zero-Sum Game.

The pay-off matrix in these types of games is usually written from the point of view of player 1 or row player. If aij>0 means player 1 receives aij units from player 2 and if aij<0 means player 1 pays to player 2. The payoff matrix is ​​as follows.

Let’s give an example to clarify the problem. Two players in a game show one or two fingers at the same time. If they have the same number of fingers showing, the first player pays the amount of one dollar to the second player. Otherwise, the second player must pay one dollar to the first player. In this way, each player can adopt one of the following two policies.

  • Show a finger.
  • Show two fingers.

The table below shows the payoff of the first player in dollars if each of the policies is chosen.

Note: In game theory, there is a predetermined policy that specifies how each player should react to any action. Before starting the game, each player determines the policies that he/she and the other party can obtain the payoff table from his/her point of view. Game theory is based on two assumptions.

  • Both players are wise and logical, and both players use their best against the opponent to achieve the best result.
  • Every actor knows when choosing his policy, what policy his opponent chooses by understanding the chosen policy.

Example:

Two politicians are facing each other in an election campaign. A campaign plan should be prepared for the last two days before the elections. Both politicians want to spend the remaining two days in two cities (a) and (b). They can spend one day in each city or two days in one city. Every politician is unaware of the opponent’s plan until it is announced. It mean we have the static game.

These two politicians have asked their program managers to find the effects of their and their competitor’s decision to spend one or two days in these two cities, depending on the forecast of increase or decrease in the number of votes.

In order to formulate this problem in the majority of a two-person zero-sum game. At first, the two sides of the game (which are the two politicians here) should determine the policies of each and also the payoff table.

Each politician has three policies ahead.

  • Policy 1: spend one day in each city
  • Policy 2: Spend both days in the city (a)
  • Policy 3: Spend both days in the city (b)

Three payoff tables for this problem are defined as follows.

The first type:

Suppose the payoff table of two politicians is in the following table.

In the above table, the second player has no policy that is significantly worse than the other policy. This situation is explained in the figure below.

Note: For player 2, the lower the better.

But for the first actor, policy 1 dominates policy 3, and regardless of the decision of actor 2, policy 1 is always better than policy 3. The figure below shows this concept.

Note: In this case, the higher the value, the better.

In this case, policy 3 is the dominant strategy, and the dominant strategy is eliminated at each stage. In this case, the payoff table is as follows.

Considering that both players are rational, therefore, player 2 knows that player 1 only chooses two policies 1 and 2 and does not choose policy 3 anymore. In this table, the player 2 has a losing policy, which is policy 3. The figure below shows the reason why policy 3 is dominated.

Note: For player 2, the lower, the better.

By removing the policy 3, we get the following table.

For the first player, policy 1 is dominant over policy 2, and policy 2 is the defeated policy for player 1. In this case, the payoff table is as follows.

For player 2, policy 2 is a losing policy to policy 1, and both players choose policy 1.

In this way, the first player always takes one unit from the player 2 and in this case the value of the game is equal to one. If the value of the game is equal to zero, it is called a fair game.

The second type:

In this case, suppose the payoff table is as follows.

In the above table, there is no defeated policy and it is no longer possible to find the policy by the previous type. By choosing policy 1, the player 1 can win from 6 units to lose 3 units. Because player 2 is rational, he chooses policy 1 so that player 1 loses. Also, by choosing policy 3, player 1 can win 5 units, but player 2 does not give this opportunity to player 1 and imposes 4 loss units on him. Also, by choosing policy 2, player 1 will not experience a loss and it seems like a good policy.

With a similar analysis for player 2, it can be concluded that by choosing policies 1, 2, and 3, the loss is equal to 5, 0, and 6, respectively, and it seems that policy 2 is a wise choice because It has less loss. Therefore, policy 2 is the right policy for both players.

Specifically, each player should play in such a way as to minimize his maximum loss. Minimax Criterion is the basic criterion of game theory in policy selection. This rule means that the first player should choose the policy with the largest minimum payoff, and the second player the policy with the smallest maximum payoff.

Definition: If we have zero total in a two-person game:

Then this game has a Saddle Point. In this case, the best policy of player 1 is to choose maxi (minj aij) and the best policy of player 2 is to choose the policy whose payoff is equal to minj (maxi aij). This policy is called Pure Strategy and the value of v is called the Value of the Game. If the value of the game is zero, this game is called a fair game.

In this game, the presence of the saddle point plays an important role and makes it impossible for any player to use the opponent’s policy to their advantage. That is, whenever the player 2 knows that player 1 chooses policy 2, he will only increase his loss by changing a policy other than 2, and therefore none of them will have an incentive to consider changing the policy. In other words, the saddle point is actually the Equilibrium Point for the game. The equilibrium point is the point where none of the players will benefit from unilaterally changing their policy.

The third type:

In this case, suppose the payoff table is as follows.

What if both players follow the Minimax rule as before?

If, similar to type 2, the players follow the Minimax rule, player 1 knows that the minimum value of the game is equal to -2, which is the maximum of the Min column. Player 1 will not lose more than 2 units by choosing policy 1. Likewise, since the minimum of the Max row is 2, and player 2 can be sure not to lose more than 2 units by choosing policy 3.

Because the value of the game is greater than zero, this game does not have a Saddle Point. Now let’s see what happens when player 1 chooses policy 1 and player 2 chooses policy 3. By choosing policy 1, player 1 wins 2 units and in this case player 2 loses 2 units. In order to avoid this loss, player 2 chooses policy 2 and instead of losing 2 units, he will win 2 units. The player 1 is also rational and chooses policy 2 to increase his win from -2 to 4. Realizing this, player 2 chooses policy 3, which trades 4 units of loss for 3 units of gain. The loss of 3 units of player 1 causes this player to add the loss of 3 units to the win of 2 units, and therefore this movement is created anew. Actually, the solution is policy 1 for player 1 and policy 3 for player 2 is an Unstable solution.

Finding a solutionabout games that do not have a saddle point is necessary because of its practicality. In the following, we will examine the method of finding the optimal solution for such games.

Mixed strategy games

If there is no saddle point in a game, game theory advises each player to choose their policies based on a probability distribution function. To express this, suppose we have

xi: the probability that player 1 chooses policy i (i=1,…,m)

yj: the probability that player 2 chooses policy j (j=1,…,n)

where m and n are the number of policies related to players 1 and 2. Vector (x1,x2,…,xm) is the game plan of player 1 and xi represents the probability of choosing strategy i. it must be non-negative and summation of xi for all i equal to one. Similarly, for player 2, yj represents the probability of choosing strategy j. In game theory literature, (x1,x2,…,xm) and (y1,y2,…,ym) are called policies. Each player chooses one of his pure policies and this choice is obtained using the probability distribution function through the mixed policy.

To clarify the issue, suppose that in the third type of the election problem, the players have mixed policies (x1,x2,x3)=(0.5,0.5,0) and (y1,y2,y3)=(0,0.5,0.5) respectively. This answer means that player 1 will choose policies 1 and 2 with a probability of 0.5 and player 2 will choose policies 2 and 3 with a probability of 0.5. For this purpose, each player throws a coin and based on that, chooses one of two acceptable policies.

Maximin value or the lower bound of the value of the game: A policy that maximizes the mathematical expectation value of the return or win of the first player, which is defined as no matter what policy the second player chooses. The mathematical representation of this definition is as follows:

Minimax value or the upper bound of the value of the game: the policy that, regardless of what policy the first player chooses, minimizes the mathematical expected value of the return or loss of the second player. The mathematical representation of this definition is as follows.

If the following relationship holds

The game does not have a stable point and mixed policy should be used. Now, if the players use a mixed policy, v or the value of the game becomes as follows.

  

In this example:

The basic theorem of two-player zero-sum games

If two players of a two-player zero-sum game use mixed policies, the value of the game is always equal to the following relation.

Therefore, if both players use a mixed policy, then the mathematical expectation of their return will be equal to v, and none of the players can achieve a better situation by unilaterally changing their policy.

Now the question is how to determine the optimal policy of each player. There are several methods for this. Two common methods are described below.

Graphical solution method

Consider a mixed policy game that has only two policies. Consider player 1. The probability of policies chosen by player 1 is (x1,x2) so that x1=1-x2. In this case, it is enough to calculate the value of x1. Consider the payoff table below.

The return of player 1 in case of policy selection by player 2 is as follows.

Player 1 seeks to maximize his minimum expected return (Maximin), which is graphically represented as follows.

The optimal expected value is located at the intersection of the two lines  -3+5x1 and 4-6x1, which is obtained from the algebraic solution of 4-6x1-3+5x1, which gives x1=11/7. The optimal policy of player 1 is (x1 ,x2)=(11/7,11/4). The value of the game is obtained in the following.

Therefore, the optimal point for player 1 is obtained from the intersection of policies 2 and 3 for player 2. Therefore, in the optimal policy of player 2, only policies 2 and 3 are effective, and the probability of choosing policy 1 in the mixed policy is zero.

Now consider player 2.

 The return of player 2 in case of policy selection by player 1 is as follows.

player 2 seeks to minimize his maximum expected return (Minimax), which is graphically represented as follows.

The optimal expected value is located at the intersection of two lines -3+7y2 and 2-4y2, which is obtained from the algebraic solution of 2-4y2=-3+7y2, where y2=5/11. The optimal policy of player 2 will be (y1,y2,y3)=(0,5/11,6/11) and the value of the game is obtained in the following.

Note: Any mixed policy for player 1 guarantees that the expected value of the return at the most is equal to the the value of the game.

Note: Any mixed policy for player 2 guarantees that the expected value of return at the least is equal to the value of the game.

Solving with linear programming

Any mixed policy game can be solved by a linear programming model. We use an example to present this method.

Example: For the rock-paper-scissors problem, consider the following payoff table.

The expected payoff for player 1 based on the choice of player 2 is as follows.

Player 2 seeks to choose a policy that minimizes player 1’s expected payoff as follows:

On the other hand, player 1 tries to maximize his payoff, so we have:

The above relationship can be rewritten as a linear programming as follows:

The optimal solution of the above model is as follows.

The value of the game is represented by v* and is equal to zero in the above model.

The expected payoff for player 2 based on the choice of player 1 is as follows.

Player 1 seeks to choose a policy that maximizes player 2’s expected payoff.

On the other hand, player 2 tries to minimize the amount of expected payoff, as follows:

The above relationship can be expressed as a linear programming.

The optimal solution of the above model is as follows:

We call W* the value of the above game, which is equal to zero.

Note: The linear model of player 1 is the dual of the linear model of player 2, and we have V*=W*.

Note: In a zero-sum two-player game, if we add the constant value C to each element of the payoff matrix, then the optimal strategy will not change, but the value of the game will be equal to C.

Example: Consider the following payoff matrix. Obtain the value of game and optimal policies using linear programming.

Because the above payoff table does not have a saddle point, it has a mixed optimal policy. We use linear programming to calculate the optimal policy. The linear programming model for player 1 is as follows.

The linear programming model for player 2 is as follows.

From solving the above linear programming models, the optimal policy and the value of game are as follows.

Example: Determine the optimal policy of each player in the payoff table below using successive elimination of the losing policies.

Solution:

For player 1, policy 3 is eliminated by policy 2.

For player 2, policy 3 is eliminated by policy 1.

For player 1, policy 1 is eliminated by policy 2.

For actor 2, policy 2 is removed by policy 1.

Therefore, the optimal policy is equal to choosing policy 2 for player 1 and policy 1 for player 2, which results in a payoff of 1 for player 1.

Example: Determine the optimal policy of each player in the payoff table below using successive elimination of the losing policies.

Solution:

For player 2, policies 1 and 4 are eliminated by policy 3.

For player 1, policies 1 and 2 are eliminated by policy 3.

For player 2, policy 2 is eliminated by policy 3.

Therefore, policy 3 is the optimal policy for both players, and the final payoff for player 2 is equal to 2 and for player 1 is equal to -2.

Example: Find the optimal policy for each player using the Minimax criterion? Does this game have a point? Is this game stable?

Solution:

The optimal policy becomes policy 3 for player 1 and policy 2 for player 2, and the final payoff is 3 for player 1. The game is stable and has a saddle point, which is due to the fact that the Minimax is equal to the Maximin.

Example: Find the best policy for each player using the Minimax criterion? Does this game have a point? Is this game stable?

Solution:

The optimal policy is policy 3 for player 1 and policy 2 for player 2. The payoff for player 2 is 1. The game is stable and has a saddle point.

Example: The product market is controled by two companies. These two companies are preparing their next year’s marketing plan and are trying to take a share of the other party’s market (the total sales of the product is almost constant, so the increase in the sales of each company is only possible by reducing the sales of the other company). Every company has three ways to achieve this goal:

  • Improvement of product packaging
  • Increase advertising
  • Reducing the price of the product

The cost of implementing all three solutions is almost equal to each other. The marketing budget of each company is only enough to implement one of the three solutions. The effects of choosing each of the solutions by each company in terms of percentage increase in sales of company 1 (player 1) are shown in the table below.

Each company adopts its own policy before knowing the other company’s policy.

A) Determine the optimal policy of each company without removing the loser policies and using the Minimax rule.

b) Identify and remove the loser policies as much as possible. Write the list of loser policies in the order of their elimination. Finally, show the payoff table in which there is no longer any loser policy.

Solution:

a) The optimal policies for the players of this game are calculated as follows.

The best policy is policy 1 for player 1 and policy 3 for player 2, and the final payoff for player 1 is equal to 1.

b)

For player 2, policy 1 is eliminated by policy 3.

For player 1, policy 3 is eliminated by policies 1 and 2.

For player 2, policy 2 is eliminated by policy 3.

For player 1, policy 2 is eliminated by policy 1.

The optimal solution is policy 1 for player 1 and policy 3 for player 2, and the final payoff for player 1 is equal to 1.

Example: Consider the payoff table for a game problem as follows.

a) Transform the problem of finding optimal policies by the Minimax rule into the equivalent linear programming.

b) Obtain the optimal solution of the linear model using the simplex method.

Solution:

a)

b) The optimal solution of the model of part (a) is as follows.

In this case, the value of the game is equal to 2.368.

Example: Consider the payoff table for the following game.

a) Determine the value of the game and the mixed policy of each player in the form of the Minimax rule using the graphical method.

b) If we consider the payoff table of player 2 as a base, find the optimal solution of the game problem using the graphical method.

Solution:

a)

Therefore,

The graphical representation of the above mathematical problem is as follows.

The optimal solution for the mixed policy (y1,y2) is as follows.

b) From the perspective of player 2, the payoff matrix is as follows.

Therefore:

The graphic representation of the problem of the above game is as follows.

Example: For the payoff table below, find the value of the  game and optimal mixed policy by the Minimax rule and using the graphical method.

Solution:

Therefore,

The graphic representation of the problem of the above game is as follows.

To calculate the optimal mixed policy of player 2, we proceed as follows.

Dynamic games with complete information

In the previous section, we examined static games, whose main feature is that players’ decisions are made simultaneously. But in dynamic games, players’ decisions are made sequentially. In other words, one player moves first, then the other player makes his move after observing the first player’s move. This feature has made the analysis method of these games different from static games. The main difference between dynamic and static games is that in static games, each player guesses the behavior of his opponent and reacts to it, but in dynamic games, at least one of the players observes the behavior of the opponent and then reacts to it. At the beginning of the lesson, we first examine the expansion form or game tree, which plays an important role in the analysis of dynamic games. Then we discuss the dynamic game equilibrium and finally some of its economic applications. Here too, it is assumed that we have complete information and each player knows exactly his competitors and their strategies and also knows the wins and losses at the end of the game. In other words, players are not faced with uncertainty about the number of players and their nature, their strategies, and the consequences of each strategy.

Extensive form or game tree

The nature of the games in which the decisions of the players are made sequentially has made the use of the expansion form as a suitable way to display these games. For this purpose, players are numbered from 1 to n. In the expansion form of a game, the following are shown:

1- Set of players

2- Order of players’ movements

3- Possible actions that a player can perform in each move.

4- Information of each player in each move

5- Outcome of players at the end of the game

One of the simple ways to display the dynamic game is the extensive form, which is usually shown as a game tree. For example, consider the following game where two firms decide to enter (E) or not to enter (S) the market.

Now suppose that the players move sequentially. For this purpose, assume that first firm 1 and then firlm 2 make a decision. Here we have a sequence of moves that can be represented by a game tree.

We call each of the circles as a decision node and the orange circles as an end or terminal node of the game. Each game has a start node that starts with a move by one of the players. In each end node, the outcome of the players are specified. Inside each parenthesis, the first digit is the outcome of player 1 and the second number is outcome of player 2. In the example above, the game starts with firm 1, which can choose either E or S. Then firm 2 has two decision nodes according to the movement of firm 1 and in each node it can choose E or S.

Figure 1

In this example, it is assumed that firm 2 first observes firm 1’s move and then makes its own move. Therefore, firm 2, which plays the second stage of this game, has two decision nodes and knows exactly which node it is in.

Example: Suppose player A chooses the number x from the set {1,2} in his first move. In the second move, player B, knowing x, chooses the number y from the set {1,2}. In the third move, player A, knowing y and remembering x, can choose z from the set {1,2}. Therefore, three moves have been made, the result of which is the selection of numbers x, y, and z. Suppose at the end of the game, the outcome of player A is equal to E(x,y,z)=x-2y+z and the outcome of player B is equal to -E(x,y,z). The outcome of player A win for all possible decisions is calculated as follows.

This game can be represented by a tree. This is a two-player game that has three stages. In the first and third stages, player A decides, and in the second stage, player B decides. At the end of the tree, the value of the first component is the outcome of player A and the value of the second component is the outcome of player B.

Figure 2

Example: Consider two computer companies. Company A and Company B. Company A is trying to design an advertising program to sell a software that it has newly designed. After much research, the company has come to the conclusion that it should pursue one of two advertising programs, L or W. These two programs do not affect the total sales and income of the company, but the difference is in the amount of sales at different times. In the L method, most of the product is sold in the first year and sales are reduced for the second year because the market is saturated in the first year. The cost of advertising method L is higher than that of W method. In the W advertising method, the first year sales are the lesser, but in the second year, the sales are the higher and then market becomes saturated. The profit from the two advertising methods is written in the following table:

According to the table above, if company A is the only company producing software in the market, it should choose W advertising method.

The managers of company A realize that another company called company B will market the similar software with a different brand in the second year, and as a result, the market will be equally divided between them in the second year. The simulation cost for company B was 300 and it shows the profits of companies A and B if company B enters. The following table is the outcome of company B if it enters the market.

The following table is the outcome of company A if company B enters the market.

So, it can be seen that with the entry of company B, the profit of company A is affected and therefore there is a game between these two companies. Besides, at the time of the entry of company B, company A is active in the market. In this game, player A can decide to choose method L or method W to advertise, and company B can decide to enter the market in the second year (E) or not (O).

Since company A makes a decision in the first year, it makes a decision before company B. Then it’s time for Company B’s decision in the second year. The expansion form of the game can be shown as follows:

Figure 3

If firm A chooses method L, firm B must decide whether to enter (E) or not to enter (O). Similarly, if company A chooses method W, company B must decide whether to enter (E) or not (O) the market in the second year. For each decision sequence of the players, their outcome is finally shown. The first component belongs to player A and the second component belongs to player B. In this game, a1 is the decision node of player A, and the branches L and W also represent player A’s actions. b1 and b2 decision nodes of player B and branches E and O also show player B’s actions.

Expansion form of game with perfect information and imperfect information

The expansion form or game tree was described in the previous section. In this form of the game, the players move sequentially. This means that first one player moves and then it is the turn of the second player, who has exactly observed the movements of the previous player and knows it, this game is called a dynamic game with perfect information. This situation makes the player know exactly in which decision node he is. In such a case, we say that the desired player’s information set contains only one decision node, which we call Singleton Information Set. But if the player does not know the history of the game or the moves of the previous players, when it is his turn to move, he does not know at which decision node he is. In such a case, he has an information set that has more than one decision node, which we call the Multiple-Node Information Set. We call the game that has a multi-node information set as a Dynamic Game With Imperfect Information. But if there is no information set with more than one decision node in a game, we call it a Dynamic Game With Perfect Information.

Example: Suppose that in the first move, player A chooses the number x from the set {1,2}. In the second move, player B, knowing the value of x, chooses the number y from the set {1,2}. In the third move, player A, without knowing the value of y and forgetting the value of x, chooses the number z from the set {1,2}.

To show this game, it should be done in such a way that player A has forgotten the past moves. The important point is that player A’s information is only related to the time when he wants to choose his action, because he does not have any information about his past performance or the other player’s action. Therefore, in the first move, player A’s information set contains only one node, but in the third move, his information set contains four nodes. Because it does not have any other information, it cannot make any distinction between these four nodes. But player B has two decision nodes in the second move, and because he knows the value of x, he can distinguish between these two nodes, and therefore each decision node forms a set of information. Thus, this game has Imperfect Information. The presentation of this game is as follows, where the set of decisions of player A is placed in the dashed box in the third move.

Figure 4

Example: Suppose in the first move, player A chooses the number x from the set {1,2}. In the second move, player B chooses the number y from the set {1,2} without knowing the value of x. In the third move, player A, knowing x and y, chooses x from the set {1,2}. In this example, player B’s information set consists of two decision nodes, but for player A, each decision node constitutes one information set. Thus, this game has Imperfect Information.

Figure 5

Example: Suppose in the previous example, each player does not know the other player’s move and his previous moves at the time of his move. In this case, player A has 4 choices (1,1), (2,1), (1,2), and (2,2) and player B has two choices 1 and 2. Here player A’s moves simply consist of a pair of numbers that are independent of the other player’s moves because he knows nothing about player B’s moves.

Figure 6

Example: Suppose two persons have participated in a coin game. In the first stage, person A flips his coin first. Then person B flips his coin without seeing the result of person A’s coin. Now both players see the result of this stage. At this stage, if the result of both coins is head (H) or tail (T), player B loses 5, and otherwise, player B wins the same. In the second stage, the loser has the right to decide whether to continue or end the game. Therefore, the loser can now choose one of the strategies of ending the game (Q) or continuing the game. If the loser decides to continue the game, he throws his coin. Then the winner must also flips the coin before seeing the result of the loser’s coin. In this stage, if both coins are head or tail, the loser of the first stage must pay 10 (double the amount of the first stage) to the winner of the first stage. But if the results of both coins are not the same , the outcome of both players will be zero. In fact, the loser of the first stage is given an opportunity to take a risk to enter the game into the second stage, which either doubles his loss or reduces the loss to zero.

Figure 7

First, player A makes the first move, and his information set consists of one node. But when player B makes his move, he has two decision nodes in his information set because he is not aware of player A’s decision. In the second stage, the loser has a node. But in the second stage, the player who won the first stage has two sets of information, each containing two nodes.

Nash equilibrium in dynamic game with perfect information: Backward induction method

If we have the dynamic game with perfect information, it can be solved by a simple method called backward induction method. For this purpose, consider the following static game.

If we solve this game statically (that is, when the players move simultaneously), the equilibrium of the game is (R1, C2), where R’s win is 1 and C’s win is 5. But if we consider the game dynamically, we must first assume that one of the players makes his move and then the other moves by observing the first move. Here, assume that R moves first and then C. The expanded form of this game is shown in the diagram of Figure 8:

Figure 8

Now the question is, which strategy should player R choose? If he chooses R1, he might win 10. On the other hand, if he chooses R2, he can win 9. Does this win mean he has to play R1?

The answer is No. R is a Rational player who answers the following two questions:

a) He asks himself what will player C do if I choose R1?

b) He asks himself what will player C do if I choose R2?

Player R answers question (a) by saying that C chooses C2 because he prefers 5 to 4. But the answer to question (b) is that C chooses C1 because he prefers 9 to 3. Therefore, R concludes that his best choice is R2 because 9 is greater than 1. If player R chooses R2, player C chooses C1. Therefore, the equilibrium of the game will be (R2,C1). The result of the game is different from the case where the moves are performed simultaneously, because in the simultaneous game or the static game, the result of this game is (R1,C2).

In short, to use the Backward Induction Method, we start from the last stages and go back to the beginning of the game. For this purpose, imagine that player C is at node E, then his best choice is C2. In this way, the path goes from E to H, and R and C will win 1 and 5, respectively. If player C is in node F, he chooses C1, in which case the board of R and C is 9 and 9, respectively.

Now we will examine the behavior of player R who is at node A and guesses player C’s behavior. Player R knows that if he chooses R1, the path of the game is A®E®H, which will lead to win 1. If he chooses R2, the path of the game is A®F®I, which leads to a win of 9. From the comparison of nodes H and I, it is clear that from the point of view of player R, I has priority over H, and therefore R2 is better. Therefore, the equilibrium of this game is (R2,C1) and the Equilibrium Path of the Game is also A®F®I.

  

Figure 9

In this game, player R’s information set has only one decision node, i.e. A. Meanwhile, player C has two sets of information and each of which contains a node (node E or node F). Since each set of information contains only one node, therefore, it is mentioned by the Game with Perfect Information.

Nash equilibrium in dynamic game with perfect information

For dynamic games, Nash equilibrium can be obtained based on the concept of Sub-game Perfect Nash Equilibrium. This method is more general than the Backward Induction Method. In order to use this method, it is first necessary to introduce concepts such as Subgame and Strategy in dynamic games and then discuss the sub-game perfect Nash equilibrium.

Sub-game in dynamic game

The term Sub-game is related to the game tree or the extensive form of the game. A sub-game is a part of an extensive form of a game or a its subset. In the extensive form of a game, a subset of the game that has the following properties is a sub-game:

a) The sub-game starts from a decision node, which is necessarily the only node in the information set. In other words, the sub-game cannot start from the multi-node information set, but it must start from the single-node information set. This mode is shown in the figure below.

Figure 10

b) The sub-game includes all the nodes that branch off from the starting node of the sub-game. This case is shown in the figure below.

Figure 11

c) The sub-game does not interrupt any information set. In other words, on the way to the end of the game, if it comes across a multi-node information set, all nodes are in the game. This case is shown in the figure below.

Figure 12

According to the above definition, every game has at least one sub-game which is the same as the main game. Consider Figure 13.

Figure 13

There are three sub-games in this form. Because in addition to the top node, the game can be started from two other nodes, each of which has the conditions of the sub game.

Figure 14

But in Figure 15 there is no subgame because we have no starting node that has the single-node information set condition, i.e. condition (a). Of course, the main game itself is a subgame.

Figure 15

In Figure 16, there is no subgame because, despite the fact that there are two decision nodes for player B, each of which can be a starting point for the subgame, but along the way, it interrupts player A’s information set, which It is condition (c).

Figure 16

Strategy in dynamic game

In a static game, each strategy simply represents a player’s action. But in the dynamic game, the concept of strategy is somewhat more complicated, because in addition to the player’s action, it also shows his reaction. In addition, they should plan how he will react in all the situations that occur in this game. Therefore, in the expansive form of the game, we define the strategy as follows.

A Strategy is a comprehensive plan that describes the set of actions of the player who make decisions at all possible nodes. Such a strategy depends on the background of the game.

Example: Firm 1 owns a product market and firm 2 decides to enter the market. Supposed that if firm 2 decides to enter the market, firm 1 can choose between two entry strategies: one high price (H) and one low price (L). The profits earned by firm 1 will be positive at high price but negative at low price. Of course, if firm 2 does not enter, its profit is zero.

Figure 17

Firm 2 has a decision node and two actions that represent its strategies, namely entry (E) and non-entry (S). Firm 1 also has two options: high price (H) and low price (L). But because it has two decision nodes, firm 1 has four strategies. Each strategy represents an action for each possible situation. The possible positions for firm 1 are to be in the right node or in the left node. Firm 1 must define an action for every possible situation, which is actually its reaction to firm 2. In this case, each strategy of firm 1 is a pair of possible actions where the first element describes the action that is in response to the entry of firm 2 and the second element describes the action that is in response to the non-entry of firm 2. Therefore, the set of possible strategies for firm 1 are:

For example, the strategy (H,H) describes the plan of firm 1, the first element (H) is in response to the entry of firm 2 and the second element (H) is in response to the non-entry of firm 2. That is, in any case, firm 1 increases the price, whether firm 2 enters or not. Also, the strategy (H, L) represents the case of firm 2 in response to firm 1, which is H in response to E and L in response to S, briefly.

Sub-game perfect Nash equilibrium

The definition of Nash equilibrium for a dynamic game is similar to that of a static game. A Nash equilibrium is a set of strategies such that no player is willing to change his strategy. For this purpose, first we show the extensive form game as a table form. For example, the table form for figure (19) is as follows.

Positive signs above each element indicate the best reaction of the players. As before, wherever there are two positive signs, it indicates Nash Equilibrium, which are:

The Nash equilibrium points are placed in the set N.

There are three equilibrium points in this game, but equilibrium 2 and 3 are not valid. This can be carefully checked in Figure 18. In this figure, there are two subgames that start from the decision nodes of firm 1.

Figure 18

At the left node, firm 2 has entered the market and it is clear that firm 1’s best response is to choose H because a > – c. At the right node, firm 2 does not enter the market, and it is obvious that firm 1’s best response is to choose H because a > – c. Therefore, in each of these subgames, H dominates L, because it is not profitable for firm 1 to choose the low price or L.

Consider equilibrium 2. In this case, if firm 2 chooses the entry strategy or E, the optimal strategy of firm 1 is to choose the higher price or H, which is reasonable because a > – c. But if firm 2 chooses the non-entry strategy or S, the optimal strategy of firm 1 based on equilibrium 2 is equal to choosing a lower price or L, which is clearly illogical, because this answer means that firm 1 chooses – c while a > – c.

Consider Equilibrium 3. In this case, if firm 2 chooses the non-entry strategy or S, the optimal strategy of firm 1 is to choose higher price or H, which is reasonable because a > – c. But if firm 2 chooses the entry strategy or E, firm 1’s optimal strategy based on equilibrium 2 is equal to choosing a lower price or L, which is clearly illogical, because this answer means that firm 1 chooses – c while a > – c.

The above two analyzes show that equilibrium 2 and 3 represent situations that are Not Valid.

But equilibrium 1 is Valid. If firm 2 chooses entry strategy or E, firm 1’s optimal strategy is to choose higher price or H, which is reasonable because a > – c. If firm 2 chooses the non-entry strategy or S, firm 1’s optimal strategy based on equilibrium 1 is equal to choosing higher price or H, which is clearly rational, because firm 1 chooses a between a and -c. This analysis shows that equilibrium 1 is Valid.

In this way, the concept of Nash equilibrium can also be used for extensive form of the game. For this purpose, all strategies must be Valid. This means that the actions of the players must be optimal in all the subgames, both in the equilibrium path and out the equilibrium path. Based on this, the definition of Sub-game Perfect Nash Equilibrium is:

A set of strategies in the extensive form of the game represents a Subgame Perfect Nash Equilibrium if and only if the actions that follow these strategies are Nash Equilibrium in all the subgames.

Example: We return to the example of two computer firms A and B. The tabular form of this game is as follows.

Nash equilibrium strategies are (L,OE) and (W,EE). Now the question is which one of the strategies is valid. The game tree along with sub-games is as follows. In this form, solid bows are the best strategies in the sub-games.

Figure 19

There are three sub-games in this game. Subgame 1 starts from node b2. Subgame 2 starts from group b1. Subgame 3, which is the whole game, starts at a1.

In subgame 1, a subgame equilibrium is that firm B chooses O (-250<0). In subgame 2, a subgame equilibrium is that firm B chooses E (100>0). In subgame 3, firm A chooses L. Because L is chosen, firm B chooses O and Firm A’s profit becomes 430. If firm A chooses W, firm B chooses E and firm A’s profit becomes 400. Because 430 > 400, therefore firm A chooses L. In this case, among the two strategies (L, OE) and (W, EE), only the strategy (L, OE) is Valid.

Example: Suppose two computer companies A and B play a dynamic game. Company A has produced a computer game that is sure to catch on market quickly. Company B has the ability to simulate the computer game with the help of its engineers, which can compete with the product of Company A. Company B can use the engineers of Company A and develop the program with a very low cost. Company A can include provisions in the employment contracts with its engineers that they do not have the right to consult for other companies and pay them more to eliminate the interest of working for other companies. This work of company A will change the outcome of company B, and this preventive action of company A will be costly. Therefore, company A can take preventive action (P) or not perform any preventive action (D) at the beginning of the game. In both cases, Company B can decide whether to simulate Company A’s product and enter the market (E) or not to simulate and not enter the market (S). In response to the entry of company B into the market, company A must decide the high advertising program to take to attract customers to the market. It will cost him 80000. This advertising program will attract 70% of the market if he takes preventive action, but if he does not take preventive action, only 62% of the market will be attracted to him. Another advertising program that Company A can undertake is low advertising program (H) and it costs him nothing and can attract 50% of the market.

The potential net income of the entire market after substracting production costs is 500000 for both company A and B. If company A wants to take preventive action, it should spend 100000 more. if company B wants to simulate the computer program with the help of engineers of company A, it will cost him 100000. Otherwise, company B need to pay 200000 to develop the program. The following tables show the profits of companies A and B.

The extensive form of this problem is in the following figure.

Figure 20

The consequences of this game are shown in the table below.

The Nash equilibrium of the above game is as follows:

In order to check which of the above strategies is valid, we have to extract the sub-games. This game has five sub-games as follows:

Figure 21

The solid arcs are obtained from the Nash equilibrium of the sub-games, which must be checked to see if they are valid. Only Nash equilibrium (PHF,ES) is valid and other strategy of set N are not valid.

In this game, there are 5 sub-games with the main game itself. In sub-game 1 company A chooses F, in sub-game 2 chooses H, in sub-game 3 chooses F and in sub-game 4 chooses H and in sub-game 5 which is the whole game, chooses P.

Example: Suppose that in the first step, player 1 chooses the value x1 and in the second step, player 2 chooses the value x2 after seeing x1. The payoff functions of these two players are:

If we solve the static game, we will have:

So,

If the game is dynamic, first player 1 will choose the value of x1 and this choice will be based on the reaction of player 2 to the behavior of player 1.

By taking the derivative with respect to x1, we will have:

Now the player 2 reacts to x1*=3:

Therefore, in the Dynamic Game, when player 1 makes the first move, he has an advantage that increases his outcome. Below is a static game where the movements are simultaneous. The outcome of player 1 is equal to 4, but in the dynamic game when he makes the first move, the win reaches 4.5. In other words, it is not possible the outcome of player 1 (the player who makes the first move)in a dynamic game to be worse than in a static game.

Example: We consider two mineral water producing companies. These two companies are the only suppliers of mineral water in the market. The production amount of company 1 is equal to q1 and company 2 is equal to q2, and the price in this market is determined by the demand function that is p=10-Q, which is q1+q2=Q. Company 1 has the good management and can enter into negotiations and contracts with the suppliers of mineral water production institutions before Company 2 and enters the products into the market earlier. So the order of movement in this problem is as follows. First, company 1 determines the amount of production, then company 2 determines its optimal production by observing the decision of company 1. The production cost of each bottle is equal to 3 and there is no fixed cost. The extensive form of the game is as follows:

Figure 22

In the game of the expanded form above, the dashed point in the form of an angle shows the continuity of the production value of two companies, where q1 and q2 is an arbitrary value from that interval.

The demand function will be as follows:

According to the above, the outcome function will be as follows:

The above function shows that ui(q1,q2)=0 when 7-(q1+q2)=0. In other words, q1+q2=7. So the total production will never be more than 7.

The reaction function of player 2 will be as follows and shows how player 2 reacts upon seeing q1. R2(q1) means that the reaction of player 2 is based on the reaction value of player 1 or q1.

Since player 1 can predict the reaction of player 2 by the above function, therefore, player 1 chooses q1 in such a way that according to the reaction of player 2, his outcome is maximized:

And the best reaction of player 2 to q1=3.5 is equal to:

The outcome of companies 1 and 2 is as follows.

The above answer shows that the player who moved Earlier (player 1) is more profitable than the player who moved Later (player 2). This is called the advantage of the Game Starter. In this example, the strong management and the quicker decision-making, to enter into a contract with the suppliers before player 2, have caused this advantage for player 1.

Now suppose that in this game, the companies do not know each other’s reactions. so, they will play a static game with perfect information. In this case, the Nash equilibrium solution is equal to:

The best reactions of the companies will be as follows:

R1(q2) is the reaction of company 1 according to the reaction of company 2, i.e. q2; and R2(q1) is the reaction of company 2 according to the reaction of company 1, i.e. q1. The Nash equilibrium is calculated as follows:

The comparison of static and dynamic game with perfect information is summarized in the table below and its explanations are given below:

1- The production of each company is different in the equilibrium of the static and dynamic game.

2- The total production of two companies in dynamic game equilibrium is equal to 1.75+3.5=5.25. Static game equilibrium is equal to 2.33+2.33=4.66. That is, the amount of production in the dynamic game is higher than the production in the static game (5.25>4.66).

3- The price, i.e. p, is equal to p=10-Q. For the dynamic game, the price is 10-5.25=4.75 and for the static game, the price is 10-4.66=5.33. So the price in dynamic game equilibrium is lesser than the price in static game equilibrium.

4- While the price in the dynamic game is lower than the static game, the higher production in the dynamic game did not lead to an increase in total profit. In general, simultaneous decision-making, i.e. static game, has increased the total profit for both companies. If the dynamic game starts with company 1, the profit of company 1 will be higher than in the static game.

Dynamic game with imperfect information

In dynamic games with perfect information, each player knows the previous player’s move and knows at which node the decision has been made. The information set of the players is a single member. If the assumption is not true that the player does not know the move of the other player, then the player will not know in which decision node he is, so his information sets will be non-single member. In this section, we will discuss the method of solving this type of game with the following example.

Example: Suppose a soft drink Company named P is the only supplier of soft drinks in a city. Company C is looking to enter (E) in this market. If Company C enters the market, they must decide whether to cooperate implicitly (A) or to compete (T). In case of no entry (O), his outcome is zero and player P’s outcome is equal to 5. The extensive form of this game is as follows:

Figure 23

The strategies of company P and company C is as follows:

The outcome of the players (companies) for each strategy is shown in the table below.

The Nash equilibrium based on the above table is as follows:

Next, it should be checked which of the strategies is valid. For this, sub-games are recognized. This game has two sub-games which are shown in the figure below. The game itself is also a sub-game 2.

It should be seen which of above strategies corresponds to the Nash equilibrium of the sub-games of the problem. The Nash equilibrium in sub-game 1, g1, is as follows (there is no need to examine subgame 2 because it is the main game itself):

By comparing N(G) and N(g1), the valid equilibrium solution can be introduced as follows:

Static games with incomplete information

In the previous sections, we discussed the games with complete information. In these games, the player knows the payoff function of other players. Here we examine Static Game With Incomplete Information. In such a game, at least one of the players is uncertain about the payoff function of the other player. There are many cases in which the player cannot fully predict the payoff of his opponent. For example, in auctions, each buyer knows the value of his own product, but he does not know the value of the product of other players.

Obviously, in an auction, players present their bids in sealed envelopes and then these envelopes are opened at a certain time. Therefore, we have a game in which the movements of the players are performed simultaneously, but the players do not know the payoff of their competitors. Therefore, this is a static game with incomplete information. The static game with incomplete information are also called Bayesian Game.

We have two firms that produce the same product. The market demand function is P(Q)=a-Q and Q=q1+q2, where q1 and q2 represent the amount of production of firms 1 and 2, respectively. Suppose the cost function of firm 1 is as follows:

On the other hand, the cost function of firm 2 is not completely known. The amount of this cost is equal to the low cost with probability p and equal to the high cost with probability 1-p.

Cost function with probability p

Cost function with probability 1-p

Obviously, cH>cL.

Firm 2 decides how much to produce based on its final cost. On the other hand, firm 1 also knows that firm 2 determines its production level based on low(cL) or high cost(cH). If the cost of firm 2 is equal to cH, firm 2 chooses q*2(cH) to maximize his profit according to the firm 1’s production level. In this case, the profit of firm 2 is calculated as follows:

If the cost of firm 2 is equal to cL, firm 2 chooses q*2(cL) to maximize his profit according to the firm 1’s production level. In this case, the profit of firm 2 is calculated as follows:

Firm 1 also knows that the cost of firm 2 is high with a probability of p and predicts that the value of q2 is equal to q*2(cH). Otherwise, the value of q2 will be equal to q*2(cL). In this way, firm 1 chooses q*1 that it maximizes profit of firm 1 according to firm 2’s reaction. In this case, the expected profit of firm 1 is obtained as follows:

In the above expression, (a-q1-q2(cH))q1 is the sale of firm 1 assuming a high cost for firm 2. cq1 is the production cost of firm 1, and the difference between these two numbers, i.e. (a-q1-q2(cH))q1-cq1, is the net profit of firm 1 assuming the high cost of firm 2.

To maximize the profit of firm 2, we act as follows.

The necessary condition for maximizing the profit of firm 1 is:

Equations (1), (2), and (3) represent the best reaction of the firms that we will have by solving them simultaneously:

Now suppose these two firms have complete information about each other (static game with complete information). In this case, the amount of production of firms 1 and 2 is calculated as follows. The utility of firms 1 and 2 is equal to u1 and u2, respectively. Also, the cost of selling by firms 1 and 2 is equal to c1 and c2, respectively.

In the following, we discuss the result of static game with complete and incomplete information.

The production of firm 2 not only relates to its own cost, but also to firm 1’s behavior. This observation is clear in the results of the static game with complete and incomplete information. In the state of incomplete information, if the cost of firm 2 is high, the production of firm 2 (q2*(cH)) will be greater than the state of complete information where the production value is

that is

Because firm 1 is uncertain about the high cost of firm 2 and there is the possibility the production cost is low. Similarly, in the case of incomplete information, if the production cost of firm 2 is low, the production of firm 2 (q2*(cL)) will be lower than in the case of complete information where the production of firm 1 is 

i.e.

The reason for this result is that firm 1 is not sure about the cost of production being low and there is a possibility that the cost of production is high.

A Bayesian Game or a Static Game with Incomplete Information that has n players, includes the set of possible actions of the players (A1,A2,…,An), the specific actions of the players (a1,a2,…,an), the set of types of players (T1,T2,…,Tn), probabilities are related to each of the types (p1,p2,…,pn) and their profit functions are (u1,u2,…,un). The type of player i, which is ti, is known to him, determines the profit function of player i, i.e. ui(a1,…,an;ti). The probability of player i means Pi(t-i|ti) represents the probability of player i subject to the type of other players -i. Thus, this game is shown as G={A1,…,An;T1,…,Tn;p1, …,pn;u1,…,un}.

Nash-Bayes equilibrium: In a Bayesian game or a static game with incomplete information, strategy (s*1,…, s*n) is a Nash-Bayes equilibrium if for each player i and for each type of player i, the strategy s*i(ti) is obtained from the following problem.

The above expression states that player i, considering knowing his own type, chooses action ai from the set Ai so that, according to the probability about the type of other players, he maximizes the expected payoff. The concept of Nash-Bayes equilibrium is explored in more detail in the following example.

Example: Here we examine the situation of two firms C and R. Firm C is currently operating in the market. Firm C is a newly established company that decides to enter this market. Therefore, firm R is deciding whether to enter (sR1) and not to enter (sR2) the market, so the set of strategy is SR={sR1,sR2}. Firm C, which is active in the market, wants to decide on expansion of activity (sC1) and non-expansion of activity (sC2), where the set of strategy is SC={sC1,sC2}. The summary of this game is as follows:

We denote the actions of firm R by aR1 and aR2 and the actions of firm C by aC1 and aC2.

The equilibrium is (aR1, aC2), that is, firm R enters the market and firm C does not expand the activity and the answer of the game is (1,1). There is no difference between the strategy and action in this case. In fact, every strategy represents an action and there is a one-to-one relationship between action and strategy.

Now suppose that the firm R has only one type, which we call the normal type and denote it by tR. The probability distribution of the player R’s type from the view point of firm C is as follows:

This distribution means that firm C knows exactly the type of firm R because firm R has only one type. But there are two types of firm C, which depends on whether the cost of expansion is low or high. If the cost of expansion is high, firm C is the type of firm that faces a high cost, and if the cost of expansion is low, firm C is the type of firm that faces a low cost. Thus, the set of type for firm C is TC={tCL,tCH}, where tCL and tCH indicate low cost and high cost, respectively. The probability distribution of tC in terms of firm R is:

This distribution means that firm R guesses that firm C faces the low cost with a probability of 2/3 and the high cost with a probability of 1/3. The payoff of this game are shown in the table below.

Here, firm C knows the cost of expansion (of its own type) and its own payoff. Therefore, firm C’s payoff depends on the cost of expansion on the one hand (the same type as tCL and tCH) and on the other hand, it depends on the entry (Enter) or non-entry (Not enter) of firm R. The table above shows that firm R’s payoff depends only onthe strategies, i.e. Enter or Not enter.

In this game, firms R and C make decisions simultaneously, which represents a static game. On the other hand, we call it a Bayesian game, which means that firm R must calculate its own guesses about the probabilities of firm C’s cost. In this way, the characteristics of the static game with incomplete information are as follows:

a) This game includes two players R and C.

b) Each action represents what the player will do when its type is determined. For example, firm C should expand the activity (action) if the expansion cost is low (type); and it should not expand the activity (action) if the expansion cost is high (type).

c) Firm C has two types, i.e. high cost and low cost, and Firm R has a normal type. So the two combinations of the type of firms (firm R and firm C) are (tR,tCL) and (tR,tCH).

d) Probabilities are assigned to each combination of firms. For example, suppose that the combination (tR,tCL) has a probability of 2/3 and the combination (tR,tCH) has a probability of 1/3.

e) Determine the payoff from the combination of actions (for firm C: expansion or non-expansion and for firm R: entry or non-entry) and the combination of types of firms (for firm C: high or low cost of expansion and for firm R: normal). For example, the profit of firm R when it enters the market but firm C does not expand its activity, while the type of firm R and C are normal and low-cost, respectively, is equal to one.

f) Each firm’s strategy expresses the player’s movement, which is in the terms of the player’s type. Firm R’s strategies include entry or non-entry as a function of firm R’s type (here we have one type).

The strategy of firm C is expansion of activity and non-expansion of activity, which is a function of the type of firm. Therefore, firm C’s strategies are:

Above, indices 1 and 2 indicate expansion and non-expansion, respectively, and indices L and H indicate the type of firm, i.e., low cost and high cost, respectively. Thus, firm C has four strategies. So, we have a two-player static game with perfect information, where firm R has two pure strategies and firm C has four pure strategies. The outcome of this game is shown in the table below:

Using the above table, the Nash-Bayes equilibrium will be (sR2,{sC1(tCL),sC2(tCH)})).

In the following, we will look at an example of the calculations in the above table. If firm R chooses strategy sR1 (the action is aR1) and firm C also chooses strategy {sC1(tCL),sC1(tCH)} (the action is {aC1(tCL),aC1(tCH)}), firm R’s profit is equal to -1 and firm C’s profit is equal to (2,-1), whose calculations are given below.

where P(tCL|sC1) and P(tCH|sC1) are the probability that if the firm C is to expand then the cost of expansion will be low and high.

If firm R’s strategy is sR1 (the action is aR1) and firm C’s strategy is {sC1(tCL),sC2(tCH)} (the action is {aC1(tCL),aC2(tCH)}), the profit of firm C is equal to (2,1) and the profit of firm R is calculated as follows.

Where P(tCL|sC1) and P(tCH|sC2) respectively, the probability is that if the firm C is to expand, the cost of expansion is low, and the probability is that if the firm C is not to expand, the cost of expansion is high. -1 represents the outcome of firm R in strategy sR2 (the action is aR2) in the case that firm C chooses to expand and the cost of expansion is low.

Dynamic game with incomplete information

The dynamic game with complete information has two types. (1) In the dynamic game with perfect information, the players’ moves are completely sequential and we do not observe any simultaneous moves. A player makes a move after seeing the moves of his opponents. (2) But in the dynamic game with imperfect information, the players are faced with simultaneous movements. This means that the player may know the payoff of the game, but at the time of making his move, he does not know exactly the past moves of other players.

In a dynamic game with incomplete information, when a player wants to make a move, he has less information than the type of player who moved before him. Note that in a dynamic game with imperfect information, players are simply not aware of the actions taken by other players. But players are aware of other types of players and know what their possible strategies are and what their outcomes are. Hence, information about other players is imperfect but complete. But in a dynamic game with incomplete information, players may not know information about other players, for example, the type of players, their strategy and their outcome.

In order to examine equilibrium in dynamic games with imperfect information, consider the following example.

Example: Consider person R and C where R is female and C is male. Suppose that C proposes marriage to R. R can accept or reject this offer, but the problem is that R is not sure about whether C is addicted or not. It is obvious that C knows his own type, that is, whether he is addicted or not, but it is unknown to R. C first determines his own type and then proposes marriage to R. In the next step, R reacts to C’s proposal. Now imagine that there is information available to the public that shows that 10% of men are addicted. If X=0 means no addiction and X=1 means addiction, then P(X=0)=0.9 and P(X=1)=0.1. Thus, R’s prior guess is that C is addicted with probability 0.1. it calls the prior probability distribution.

But to solve the problem of these two people, it is said that there is a test that can determine the addiction of men who are really addicted with a probability of 95%. But among those who are not addicts, 10% of the time it gives a positive answer. This means that there is a 5% error in identifying the addiction of addicts, and there is a 10% error in identifying no addiction in healthy people.

T+ indicates a positive test result. X and X   also show addiction and non-addiction, respectively. Based on the above possibilities, the following possibilities can be obtained:

T indicates that the test result is negative. R can extract useful information from these figures. We know that the joint probability of two events T+ and X is:

If a person is selected from the population (such as person C), the probability that he is addicted and also test is positive is only 9.5%. Other probabilities are as follows:

But R is interested in changing the order of events. He wants to know what is the probability that C is addicted given the test result. That is, let’s say that C is tested and the result is negative, what is the probability that he is not really an addict?

P(T) can be obtained as follows:

Now imagine that the test result is positive. According to the error in this experiment, we want to calculate the probability that C is addicted:

Even if the test is positive, there is still a 48% chance that C is not an addict.

To solve this game, we first schedule it as follows:

  1. C has two types, either addicted (X) or not addicted (X ).
  2. C knows its own type, but R does not know C’s type. But R knows that there is a test that identifies type C with high accuracy.
  3. C proposes marriage to R. Due to the concern that R has about her future and due to the fact that he does not know the type of C, R asks C to do an addiction test before answering to him. Given the R’s condition (i.e. doing the addition test), C must decide whether to perform the test or not. Now, after C’s decision, R must decide on C’s proposal. In the following table, the outcome are shown as ( , ) where the first component is player C’s outcome and the second component is player R’s outcome.

If R rejects C’s offer, R’s outcome is zero and R has not taken any risk. If C is an addict and refuses to take the test, but R accepts C’s offer, then C’s and R’s outcomes are 3 and -1, respectively, because R has exposed herself to a great risk. Also, if C is an addict and accepts the experiment and R also accepts the offer, then C’s and R’s outcome are 2 and 1, respectively, because R has avoided risky behavior to some extent. All possible results are shown in the following table:

The pure strategies of this game is drawn in the table below.

C’s strategies indicate what action to choose for each his own type. For example, column C1 shows that TX means accepting the test even though C knows C is an addict, and T means accepting the test even though C knows C is not an addict.

Each R strategy also has two moves. The first one corresponds to C’s move when C does the test and the second one corresponds to C’s move when C does not do the test. For example, in strategy R1, Tx means acceptance of the proposal by R in response to do test by C, and T means acceptance of the proposal by R in response to not to do the test by C. Now we will examine how to calculate the above table.

Consider strategy R1 for R and strategy C1 for C. These strategies mean that R accepts C’s offer either way (do or not to do the test). Now, if player C is an addict (X), C does the test, and if C is not an addict (X̄), C does the test. In other words, C does the test in any case. Now we will calculate the outcome of R. R’s outcome depends on whether C is addicted or not, which player R does not know about. From the previous calculations, we have that the probability of a person being addicted is 0.1 and that of a person is not addicted is 0.9. We use these values to calculate R’s outcome. If C is addicted (which probability is equal to 0.1), C does the test according to strategy C1, and according to strategy R1, R accepts the offer of C, in which case her outcome (R’s outcome) is equal to 1. . Now, if C is not addicted (which probability is equal to 0.9), C does the test according to strategy C1, and according to strategy R1, R accepts C’s offer, in which case her outcome is equal to 2 will be In this case, the expected outcome of R will be equal to 1.9.

The above calculation is an example. For other values in the table, calculations are given below.

According to the above calculations, the Nash equilibrium can be obtained as follows.

According to the table above, C’s strategy is equal to C3 and R’s strategy is equal to R2. That is, R and C adopt their strategies as follows:

C’s strategy: Not doing the test if he is addicted and doing the test if he is not addicted.

R’s strategy: If player C accepts the test, accept the marriage proposal, and if player C does not accept the test, reject the marriage proposal.

Leave a Reply

Your email address will not be published. Required fields are marked *