Game Theory is used for decision making under conflicting situation where there are one or more opponents(players). A player may be an individual, a group of individuals or an organisation. The models for which chess, poker, etc are the games which have the characteristics of a competition and are played according to definite rules(strategy). It should be a definite rule. Game Theory provides solution to such games assuming that each of the players wants to maximise the profits and minimise the losses. The Game Theory originated by J.V. Neumann in 1928 and later developed by G.B. Dantzig.

BASIC TERMINOLOGIES

PLAYER:

Each participant in the game is called player. A player may be individuals, a group or an organisation.

Two Person & m-person Games:

If the number of players is two then it is known as two person game. On the other hand, if the number of players is m, then it is known as m-person game.

Zero Sum & Non-Zero Sum Game:

In a zero sum game,, the sum of points won equals the sum of the points lost i.e. one player wins at the expense of the other’s loss. To the contrary, if the sum of games or loses is not equal to zero it is either positive or negative then it is known as non-zero sum game. An example of non-zero game is the case of two competing firms each with a choice regarding its advertising campaign. In such a situation both the firms may gain or lose through their gain or loss may be equal.

Optimal Strategy :

The course of action which maximises the profit of a player or minimises his loss is called an optimal strategy.

Saddle Point:

A saddle point is an element of a pay-off matrix which is both the smallest element in its row and the largest element in its column. That is, if in a game maximin for ‘A’ and minimax for ‘B’ be equal then the game is said to have a saddle point. Thus,

max(row min)=min(column max)=Value of the Game

Furthermore, saddle point is also regarded as an equilibrium point in the theory of games.

If,

max(\textit{row min}) \neq min(column max) 

then, there exists no saddle point and the value of the game lies between theese two values. In situations where a saddle point does not exist, the maximin(minimax) principle for solving a Game Problem breaks down. In that case, the problem can be solved by using mixed strategy.

Pay-off Function:

Let, ((a_{ij})) be any pay-off matrix of order m*n. Then for pay-off function or mathematical expectation of a game is denoted by E(p,q] , denoted as

E(p,q) = \sum_{i=1}^{m} \sum_{j=1}^n a_{ij} p_i q_j 

,where p and q are the mixed strategies for A and B respectively. In particular, if B takes his pure j-th move only then expected gain of A is given by:

E_j(p) = \sum_{i=1}^m a_{ij} p_i \quad \forall j=1(1)n

Similarly, for particular i-th pure move of A only, the expected loss of B is given by:

E_i(q) = \sum_{j=1}^n a_{ij} q_j

Value of the Game:

It refers to the expected outcome per play when players follow their optimal strategy. It is generally denoted by v . For a 2*2 game without saddle point, consider the pay-off matrix for player A,

\left[ \begin{matrix}
a_{11} & a_{12} \\
a_{21} & a_{22}
 \end{matrix} \right]

and p_1,p_2 and q_1,q_2 as the probabilities of choosing strategy A1,A2 and B1,B2 by Player A and Player B respectively.

Clearly,

p_1+p_2 = 1 = q_1 + q_2 \quad and \quad p_1,p_2,q_1,q_2 \geq 0

The expected gain for A when B chooses B1 or B2 are respectively

a_{11}p_1 + a_{12}p_2 \quad and \quad a_{12}p_1+a_{22} p_2

Similarly the expected loss to B when A chooses A1 or A2 are respectively,

a_{11}1_1 + a_{21}q_2 \quad and \quad a_{12}q_1+a_{22} q_2  \quad \dots (*)

Assuming that each rectangular game has a solution and assuming v to be the expected value of the game, we should have

a_{11}p_1 + a_{21}p_2 \geq v , \quad a_{12}p_1 + a_{22}p_2 \geq v  \quad \dots (**)

as A expects to get at least v.

Similarly, B expects to lose at most v and hence,

a_{11}q_1 + a_{21}q_2 \leq v  , \quad a_{12}q_1 + a_{22}q_2 \leq v 

Assuming the above in equations as strict equations and assuming the existence of their solutions, we can say that the solutions (p_1,p_2) and (q_1,q_2) are the optimal solutions for the game. Now if we consider the in- equations (*) as strict equations, we have,

a_{11}p_1 + a_{21}p_2  = a_{12}p_1 + a_{22}p_2  
\implies \frac{p_1}{p_2} = \frac{a_{22}-a_{21}}{a_{11}-a_{12}} \quad \dots (a)

Similarly, from (**) we get,

\frac{q_1}{q_2} = \frac{a_{22}-a_{12}}{a_{11}-a_{21}}\quad \dots (b)

Now using the relation that p_1+p_2 = 1 = q_1 + q_2 , we have

p_1 =   \frac{a_{22}-a_{21}}{(a_{11}+a_{22})-(a_{12}+a_{21})} \quad, q_2 =   \frac{a_{11}-a_{12}}{(a_{11}+a_{22})-(a_{12}+a_{21})}

q_1 =   \frac{a_{22}-a_{12}}{(a_{11}+a_{22})-(a_{12}+a_{21})} \quad, q_2 =   \frac{a_{11}-a_{21}}{(a_{11}+a_{22})-(a_{12}+a_{21})}

Hence the value of the game is,

v = \frac{a_{11}a_{22}-a_{12}a_{21}}{(a_{11}+a_{22})-(a_{12}+a_{21})}

The pay-off matrix does not possess a saddle point. Hence, the largest and the second largest elements of the pay-off matrix must constitute one of its diagonals. Hence, the possible ordering of the elements of the pay-off matrix will be:

a_{11}\geq a_{22}\geq a_{12} \geq a_{21} \\
a_{11}\geq a_{22}\geq a_{21} \geq a_{12} \\
a_{22}\geq a_{11}\geq a_{12} \geq a_{21} \\
a_{22}\geq a_{11}\geq a_{21} \geq a_{12} \\
a_{21} \geq a_{12} \geq a_{22}\geq a_{11} \\
a_{12} \geq a_{21} \geq a_{22}\geq a_{11} \\
a_{21} \geq a_{12} \geq a_{11}\geq a_{22} \\
a_{12} \geq a_{21} \geq a_{11}\geq a_{22} 

The values of p_1,p_2,q_1,q_2 as obtained above are all positive for all such orderings of a_{11},a_{12},a_{21},a_{22} . Hence, this is the optimal solution.

Transformation of a Game Problem to an LPP:

Consider a game problem with the pay-off matrix . The maximizing player A has m mixed strategies which chooses with probabilities respectively, such that- The expected gain to A when the minimizing player B chooses his j-th course of action out of his n-courses is . If the , then A expects to get atleast . A will choose his strategies with such probabilities as to maximize his least guaranteed gain . Now, as is the minimum of all expected gains and the value of the game is clearly the maximum value of , if it exists. Thus, are to be determined as to satisfy (1) and minimize . To put this problem in a standard LPP, we divide (1) and (2) by , which is positive. If is not positive, which will be indicated by the presence of some negative elements in the pay-off matrix, then we add to all the elements of the pay-off matrix a sufficiently large positive quantity ‘c’ such that becomes positive. This operation does not change the optimum solution but only increases the value of the game by ‘c’. Now writing, , we can rewrite (1) and (2) as: Now the maximization of is equivalent to the minimization of it’s reciprocal, hence we can state the roblem for A as: This is an LPP written from the point of view of A. Similarly, considering the problem from the point of view of B who will expect to minimize all the expected loss for him, we can arrive at the following LPP- Having found we can find from the relation and . Finally the value of the original game is obtained by substracting c, if needed.

Theorem(Fundamental theorem or Minimax Theorem)

If mixed strategies be allowed, then there always exists a value of the game, that is,

\underline{v}  = \bar{v}

The Minimax and Maximin Principle

The game theory is viewed in such a manner that each player is interested in determining his optimal strategy. Because of the conflicting nature of the problem involving opposite interests the optimality is based on a pessimistic principle.

The principle is known as “maximin and minimax” principle and is stated as:

If a player lists the worst possible outcome of all the potential strategies, then he will choose that strategy to be the most suitable for him which corresponds to the bet of these worst conditions.

If the maximin value equals the minimax value then the game is said to have a saddle point(equilibrium) point and the corresponding strategies are called optimal strategies. The amount of pay-off at an equilibrium point is known as the value of the game.

In general,

maximin\quad (\underline{v}) \leq minimax \quad (\bar{v}) 

The game is said to be fair if,

\underline{v} = 0 = \bar{v}

The game is said to be stable(determinable) if,

\underline{v} = \bar{v}

Graphical Method

Graphical method is applicable to only the games in which one of the players has two strategies only. The advantage of the method is that it is relatively fast.

Dominance Property

The principle of dominance states that if one strategy of a player dominates over the other strategy in all conditions then the latter strategy can be ignored. A strategy dominates over the other only if it is preferable over other in all conditions. The concept of dominance is especially useful for the evaluation of two-person zero sum games where a saddle point does not exist.

General Rule of Dominance

• If all the elements of a column(say i -th column) are equal to or greater than the corresponding elements of another column (say j -th column) , then the i-th column is eliminated and it is said that j-th column dominates the i-th column.
• If all the elements of a row (say r-th row) are equal to or less than the corresponding elements of another row (say k-th row) then the r-th row is eliminated and it is said that the k-th row dominates the r-th row.

Modified Dominance Property

A pure move or strategy of maximising (or minimising) player may be dominated if it be inferior(superior) to a convex combination of two or more strategies of that player. This property is called modified dominance property.

• If i – th row be dominated by convex combination of other rows, then the I-th row is deleted from the pay-off matrix.
• If j-th column dominates a convex combination of other column then the j-th column is dominated from the pay-off matrix.

Summary of the methods of Solution

1. At first search for saddle points.
2. If there be no saddle point, then use the concept of dominance by which the game may be reduced in size.
3. If the reduced size of the game be 2*2 with no saddle point then solve it by the method of mixed strategies
4. If, on the other hand, the reduced size of the game be n*2 or 2*n, then use graphical method, reduce it to a 2*2 game and then apply the method of mixed strategies.
5. On failure of the above methods, apply graphical method.
6. On failure of other methods one may reduce the game to an LPP and solve it by simplex method.