Unit - 4
Game theory
Overview:
A game can be defined as below-
A game is a contest involving two or more than two persons (competitors) each of whom wants to win. A theory of games gives a series of mathematical models that can be useful in explaining decision-making concepts, where two or more persons or competitors are involved under conditions of conflict and competition.
A player may be an individual, individuals, or an organization.
Game theory was introduced by John Von Neumann and Oscar Morgenstern in 1944.
Business decisions in a competitive situation do not depend on the decisions of the organization alone but on the interaction between the decisions of the organization and those of the competitors. Each firm tries to select and execute its strategies and aims to maximize its gains at the cost of its opponents. Game theory deals with problems where actions and interactions of competing firms give rise to conditions of business conflict. In other words, Game Theory is a body of knowledge which is concerned with the study of decision-making in situations where two or more rational opponents are involved under conditions of competition and conflicting interest.
Definition: Game theory is a body of knowledge that deals with making decisions when two or more intelligent and rational opponents are involved under conditions of conflict or competition. The competitors in the game are called players.
Note-
The mathematical approach of Von Neumann utilizes the Minimax principle, which involves the fundamental idea of minimization of the maximum losses. Many of the competitive problems can be handled by the game theory but not all the competitive problems can be analyzed with the game theory.
The models in the theory of games is classified into following factors-
Number of players:
If a game involves only two players, then it is called a two-person game. However, if the number of players are more, the game is referred to as n-person game.
Sum of gains and losses:
If, in a game, the sum of the gains to one player is exactly equal to the sum of losses to another player, so that, the sum of the gains and losses equals zero, then the game is said to be a zero-sum game. Otherwise it is said to be non-zero sum game
Strategy:
The strategy for a player is the list of all possible actions that are likely to be adopted by him for ever outcome.
The outcome resulting from a particular strategy is also known to the players in advance and is expressed in terms of numerical values.
The particular strategy that optimizes a player’s gains or losses, without knowing the competitor’s strategies, is called optimal strategy.
A player follows two types of strategies:
Pure Strategy:
A particular strategy that a player chooses to play repeatedly regardless of other player’s strategy, is referred as pure strategy. The objective of the players is to maximize their gains or minimize their losses.
Mixed Strategy:
A set of strategies that a player chooses on a particular move of the game with some fixed probability are called mixed strategies.
Note- Mixed strategy is courses of action that are to be selected on a particular occasion with some fixed probability
Important definitions:
Play- A play occurs when each player selects one of his available strategies. Two basic assumptions in a play are:
(a) The choices of courses of action by players are made simultaneously.
(b) No player knows the choice of his opponents until he has decided on his own.
Outcome- Every combination of strategies of players determines an outcome called pay-off, where pay-off is nothing but a gain to a player. A loss is considered as a negative gain.
Value of the Game
The value of the game is the “expected gain to a player” if he and his opponent use their best strategies.
Two-person zero-sum games:
A game is called two-person zero-sum game when there are only two players.
In other words, “In a game of two persons if the algebraic sum of the gains of both the players after the game is zero, then it is called 2-person-zero-sum game.”
Assumptions
1. There are 2 players having conflicting interests.
2. Each player has a finite number of strategies.
3. Each strategy selected by a player results into a certain pay-off and algebraic sum of these pay-offs to both players is zero.
Two-person-zero-sum game with saddle point are called pure strategy games and two-person zero- sum game without saddle point are called mixed strategy games.
What is payoff matrix?
The payoffs in terms of gains or losses, when players select their particular strategies, can be represented in the form of a matrix, called the payoff matrix.
If player P has m strategies represented by the letters: P1, P2, . . ., Pm and player Q has n strategies represented by the letters: Q1, Q2, . . ., Qn. The numbers m and n need not be equal. The total number of possible outcomes is therefore m × n. It is assumed that each player not only knows his own list of possible strategies but also of his competitor. For convenience, it is assumed that player P is always a gainer whereas player Q a loser. Let aij be the payoff that player P gains from player Q if player P chooses strategy i and player Q chooses strategy j. Then the payoff matrix is shown in the-
Player P’s strategy | Player P’s strategy    |
  . . .
 |       . . . . . . . . .    |
Since player P is assumed to be the gainer, therefore he wishes to gain as large a payoff aij as possible, player Q on the other hand would do his best to reach as small a value of aij as possible. Of course, the gain to player Q and loss to P must be – aij.
Saddle Point
A saddle point in a pay-off matrix corresponds to that element of the matrix which represents the ‘Maxmin’ value of a player and Minimax value of his opponent. For this we find Maximum element of each column and then find the Minimum value of column Maxima known as Minimax. Similarly, we identify minimum element of each row and then find the Maximum of those entries known as Maximin. If Minimax = Maximum of those entries known as Maximin. If Minimax = Maximin, then saddle point exists and the value of the game is equal to Minimax to Maximin. If Minimax Maximin, then no saddle point exists. If Minimax = Maximin, then the pure strategies are called optimum strategies. Usually Maximin value of the game Minimax. If Maximin = Minimax = 0, the game is fair. If Maximin = Minimax, the game is strictly determinable. The value of the game is the average pay-off that would suit the game was played over and over again.
Important notes about game:
1. Each player has available to him a finite number of possible strategies. The list may not be the same for each player.
2. List of strategies of each player and the amount of gain or loss on an individual’s choice of strategy is known to each player in advance.
3. One player attempts to maximize gains and the other attempts to minimize losses.
4. Both players make their decisions individually, prior to the play, without direct communication between them.
5. Both players select and announce their strategies simultaneously so that neither player has an advantage resulting from direct knowledge of the other player’s decision.
6. The payoff is fixed and determined in advance.
Games with mixed strategies or game without saddle point:
In certain cases, no saddle point exists, which means maximin value is unequal to minimax value.
In all such cases, players must choose the mixture of strategies to find the value of game and an optimal strategy.
The value of game obtained by the use of mixed strategies represents the least payoff, which player
A can expect to win and the least which player B can expect to lose. The expected payoff to a player in
a game with payoff matrix [aij] of order m × n is defined as:
Where P = ( p1, p2, . . ., pm) and Q = (q1, q2, . . ., qn) are the probabilities (or relative frequency with which a strategy is chosen from the list of strategies) associated with m strategies of player A and n strategies of player, B respectively, where p1 + p2 + . . . + pm = 1 and q1 + q2 + . . . + qn = 1.
A mixed strategy game can be solved by using following methods:
1. Algebraic method
2. Analytical or calculus method
3. Matrix method
4. Graphical method, and
5. Linear programming method
Key takeaways:
- Game theory is a body of knowledge that deals with making decisions when two or more intelligent and rational opponents are involved under conditions of conflict or competition. The competitors in the game are called players.
- Mixed strategy is courses of action that are to be selected on a particular occasion with some fixed probability
- A saddle point in a pay-off matrix corresponds to that element of the matrix which represents the ‘Maxmin’ value of a player and Minimax value of his opponent.
- The value of the game is the “expected gain to a player” if he and his opponent use their best strategies.
- In a game of two persons if the algebraic sum of the gains of both the players after the game is zero, then it is called 2-person-zero-sum game.
When we have payoff matrix is of the size 2 × n or m × 2, then the graphical method is useful.
Optimal strategies for both the players assign non-zero probabilities to the same number of pure strategies. Therefore, if one player has only two strategies, the other will also use the same number of strategies. Hence, this method is useful in finding out which of the two strategies can be used.
Consider the following 2 × n payoff matrix of a game, without saddle point.
Player P | Player Q    |
  . . .  Probability |       . . . . . . . . .    q1 q2 ….  |
Player A has two strategies P1 and P2 with probability of their selection p1 and p2, respectively, such that p1 + p2 = 1 and p1, p2 ≥ 0. Now for each of the pure strategies available to player Q, the expected pay off for player P would be as follows:
Q’s pure strategies | P’s expected payoff |
  . . . 
|   . . . 
|
According to the maximin criterion for mixed strategy games, player P should select the value of probability p1 and p2 so as to maximize his minimum expected payoffs. This may be done by plotting the straight lines representing player P’s expected payoff values.
The highest point on the lower boundary of these lines will give the maximum expected payoff among the minimum expected payoffs and the optimum value of probability p1 and p2.
Now, the two strategies of player Q corresponding to those lines which pass through the maximin point can be determined. This helps in reducing the size of the game to (2 × 2), which can be easily solved by any of the methods discussed earlier.
The (m × 2) games are also treated in the same way except that the upper boundary of the straight lines corresponding to Q’s expected payoff will give the maximum expected payoff to player Q and the lowest point on this boundary will then give the minimum expected payoff (minimax value) and the optimum value of probability q1 and q2.
Case study:
Example: Two MNC’s A and B make plasma and LCD television sets. Company A can make either 150 plasma sets in a week or an equal number of LCD sets, and make a profit of Rs 400 per plasma set, or 150 plasma and 150 LCD sets, or 300 LCD sets per week. It also has the same profit margin on the two sets as A. Each week there is a market of 150 plasma sets and 300 LCD sets and the manufacturers would share market in the proportion in which they manufacture a particular type of set. Write the pay-off matrix of A per week. Obtain graphically A’s and B’s optimum strategies and value of the game.
Sol:
For company A, the strategies are:
A1: make 150 plasma sets, A2: make 150 LCD sets. For company B, the strategies are:
B1: make 300 plasma sets, B2: make 150 plasma and 150 LCD sets.
B3: make 300 LCD sets.
For the combination A1B1, the profit to company A would be: {150/(150 + 300)} × 150 × 400 = Rs 20,000 wherein 150/(150 + 300) represents share of market for A, 150 is the total market for plasma television sets and 400 is the profit per set. In a similar manner, other profit figures may be obtained as shown in the following pay-off matrix:
This pay-off table has no saddle point. Thus to determine optimum mixed strategy, the data are plotted on Graph given below-
Lines joining the pay-offs on axis A1 with the pay-offs on axis A2 represents each of B’s strategies. Since company A wishes to maximize his minimum expected pay-off, we consider the highest point of intersection, P on the lower envelope of A’s expected payoff equation. This point P represents the maximum expected value of the game. The lines B1 and B3 passing through P, define the strategies which company B needs to adopt. The solution to the original 2 × 3 game, therefore, reduces to that of the simpler game with 2 × 2 pay-off matrix as follows:
The optimal mixed strategies of player A are: A1 = 3/11, A2 = 8/11. Similarly, the optimal mixed strategies for B are: B1 = 6/11, B2 = 0, B3 = 5/11. The value of the game is V = 38,182.
Example: Solve the following game graphically:
Player A | Player B
  |
     | 1 2 4 5 9 -7 -3 -4 2 1 |
Sol:
The given pay-off matrix has no saddle point. So, let the player B play the mixed strategies with probability q1 and q2 such that, q1 + q2 = 1. Then, B’s expected pay-offs against A’s pure strategies are given by
Graph for B
The expected pay-off equations are plotted as shown in Fig. 12.5. The point P represents the minimax expected value of the game for player B. The minimal point occurs at the intersection of two pay-off lines
E2 = 4q1 + 5q2
And E3 = 9q1 – 7q2.
The solution to the 5 × 2 game reduces to that of the game with pay-off matrix of size (2 × 2). The optimum pay-off to player B can be obtained by setting E2 and E3 equal and solving for q1,
4q1 + 5q2 = 4q1 – 7q2
Or 4q1 + 5(1 – q1)
= 9q1 – 7(1 – q1)
Or q1 = 12/17 and
q2 = 1 – q1 = 5/17.
Substituting the value of q1 and q2 in equation E2 (or E3), we have the expected loss to B as V = 73/13.
If the probability of player A’s selecting strategy A2 and A3 are p2 and p3, respectively, then the expected gain to A can be calculated by equating two pay-off lines: 4p2 + 9p3 = 5p2 – 7p3 to obtain p2 = 16/17, p3 = 1 – p2
= 1/17 whereas p1 = 0 and p4 = 0. The expected gain to A is V = 73/17.
We can solve the two-person zero-sum by using linear programming.
Linear programming helps to solve the mixed-strategy games of larger dimension payoff matrix.
Consider a payoff matrix of size m × n. Let aij be the element in the ith row and jth column of game payoff matrix, and letting pi be the probabilities of m strategies (i = 1, 2, . . ., m) for player A. Then, the expected gains for player A, for each of player B’s strategies will be:
The aim of player A is to select a set of strategies with probability pi (i = 1, 2, . . ., m) on any play of game such that he can maximize his minimum expected gains.
Now to obtain values of probability pi, the value of the game to player A for all strategies by player
B must be at least equal to V. Thus to maximize the minimum expected gains, it is necessary that:
….
….
….
Where
Dividing both sides of the m inequalities and equation by V the division is valid as long as V > 0.
In case V < 0, the direction of inequality constraints must be reversed. But if V = 0, the division would be meaningless. In this case a constant can be added to all entries of the matrix, ensuring that the value of the game (V ) for the revised matrix becomes more than zero. After optimal solution is obtained, the true value of the game is obtained by substracting the same constant value. Let pi/V = xi, (≥0), we then have
….
….
….
Since the objective of player A is to maximize the value of the game, V, which is equivalent to minimizing 1/V, the resulting linear programming problem can be stated as:
Subject to the constraints
….
….
….
And
Where
Similarly, Player B has a similar problem with the inequalities of the constraints reversed, i.e. minimize the expected loss. Since minimizing V is equivalent to maximizing 1/V, therefore, the resulting linear programming problem can be stated as:
Subject to the constraints
….
….
….
And
Where
Note- LP problem for player B is the dual of LP problem for player A and vice versa. Therefore, the solution of the dual problem can be obtained from the primal simplex table. Since for both the players Zp = Zq, the expected gain to player A in the game will be exactly equal to expected loss to player B.
Example: For the following payoff matrix, transform the zero-sum game into an equivalent linear programming problem and solve it by using the simplex method.
Sol:
The first step is to find out the saddle point (if any) in the payoff matrix as shown below:
The given game payoff matrix does not have a saddle point. Since the maximin value is –1, therefore, it is possible that the value of game (V) may be negative or zero because –1 < V < 1. Thus, a constant that is at least equal to the negative of maximin value, i.e. more than –1 is added to all the elements of the payoff matrix. Thus, adding a constant number 4 to all the elements of the payoff matrix, the payoff matrix becomes:
Let pi ( i = 1, 2, 3) and qj ( j = 1, 2, 3) be the probabilities of selecting strategies Ai (i = 1, 2, 3) and
Bj ( j = 1, 2, 3) by players A and B, respectively.
The expected gain for player A will be as follows:
5p1 + 7p2 + 10p3 ≥ V (if B uses strategy B1)
3p1 + 9p2 + 6p3 ≥ V (if B uses strategy B2)
7p1 + p2 + 2p3 ≥ V (if B uses strategy B3)
p1 + p2 + p3 = 1
And p1, p2, p3 ≥ 0
Dividing each inequality and equality by V, we get,
In order to simplify, we define new variables:
x1 = p1/V, x2 = p2 /V and x3 = p3 /V
The problem for player A, therefore becomes,
Minimize Zp ( = 1/V ) = x1 + x2 + x3
Subject to the constraints
(i) 5x1 + 7x2 + 10x3 ≥ 1
(ii) 3x1 + 9x2 + 6x3 ≥ 1
(iii) 7x1 + x2 + 2x3 ≥ 1 and x1, x2, x3 ≥ 0 game V.
Hence, the problem of player B can be expressed as follows:
Maximize Zq (= 1/V) = y1 + y2 + y3
Subject to the constraints
(i) 5y1 + 3y2 + 7y3 ≤ 1, (ii) 7y1 + 9y2 + y3 ≤ 1, (iii) 10y1 + 6y2 + 2y3 ≤ 1
And y1, y2, y3 ≥ 0
Where y1 = q1/V; y2 = q2/V and y3 = q3/V.
It may be noted here the that problem of player A is the dual of the problem of player B. Therefore,
The solution of the dual problem can be obtained from the optimal simplex table of primal.
To solve the problem of player B, introduce slack variables to convert the three inequalities to equalities. The problem now becomes:
Maximize Zq = y1 + y2 + y3 + 0s1 + 0s2 + 0s3
Subject to the constraints
(i) 5y1 + 3y2 + 7y3 + s1 = 1
(ii) (ii) 7y1 + 9y2 + y3 + s2 = 1
(iii) (iii) 10y1 + 6y2 + 2y3 + s3 = 1
And y1, y2, y3, s1, s2, s3 ≥ 0
Proceeding with the usual simplex method, the optimal solution is shown in Table
The optimal solution (mixed strategies) for B is: y1 = 0; y2 = 1/10 and y3 = 1/10 and the expected value of the game is: Z = 1/V – constraint (= 4) = 5 – 4 = 1.
These solution values are now converted back into the original variables: If 1/V = 1/5 then V = 5
y1 = q1/V, then q1 = y1 × V = 0
y2 = q2/V, then q2 = y2 × V = 1/10 × 5 = 1/2
y3 = q3/V, then q3 = y3 × V = 1/10 × 5 = 1/2
The optimal strategies for player A are obtained from the cj – zj row of the Table.
x1 = 2/15, x2 = 1/15 and x3 = 0
Then p1 = x1 × V = (2/15) × 5 = 2/3; p2 = x2 × V = (1/15) × 5 = 1/3; p3 = x3 × V = 0
Hence, the probabilities of using strategies by both the players are:
Player A = (2/3, 1/3, 0); Player B = (0, 1/2, 1/2) and, Value of the game V = 1.
Key takeaways:
- Every way has its own significance and advantages, thus making game theory a model for winning business in a competitive environment.
- Game theory describes the situations involving conflict in which the payoff is affected by the actions and counteractions of intelligent opponents.
- Minimax Criterion: Minimax criterion is selecting the strategies that minimize the loss for each player. In other words, the player always anticipates worst possible outcome and chooses the strategy to get maximum for profit and minimum for loss.
- Mixed Strategy: Selects at least 2 courses of action, while a probability of selecting an individual strategy will be less than 1, but the sum of the strategies will be 1.
- Pure Strategy: The strategy to select a course of action with the probability of one.
- Saddle Point: A situation where both the players are facing pure strategies.
- Strategy: All possible actions that can be taken for every pay–off.
- Value of the game: The Value of the game is the expected gain of player A if both players use their best strategies. The best strategy is arrived at using minimax criterion.
References:
- Operations research- theory and application, JK Sharma, trinity press
- Operations research, P. Rama Murthy, new age international publishers
- Operations research by kanti swarup
