GRAPHICAL METHOD FOR GAMES 2 x n / m x 2 MATRIX

Consider the following 2 x n games

           B1       B2 .............Bn
A1 [    a11       a12.............a1n
A2      a21       a22.............a2n]


Let the mixed strategy for Player A is given by
          [  A1        A2
SA =     P1        P2]         such that p1+ p2=1   and p1,p2 >=0


Now the Pure Strategy for A available to B would be as follows

B's PURE MOVE                   A's EXPECTED PAY OFF
    B1                                         E1(P)=a11P1+a21P2
    B2                                         E2(P)=a12P1+a22P2
     .
     .
     .
     .
    Bn                                         En(P)=a1nP1+a2nP2

GAME THEORY : (WITHOUT SADDLE POINT)

Q1.Solve the following Pay off Matrix

                   B1         B2
     A1   [   5              1
     A2       3              4]

Soln:

STEP I:
Find the row minima and colmn maxima, and find out the maximin amd minimax values.

[5      1       1
 3      4]      3        maximin=3

 5       4
minimax=4

maximin != minimax
Therefore there is no saddle point.

              a22-a12
p1=   --------------------
        (a11+a22)-(a12+a21)

p1=(4-1) / (5+4)-(1+3)

p1=3/5      p2=1-p1=1-3/5=2/5  
p2 = 2/5


        a22-a21
q1=   --------------------
        (a11+a22)-(a12+a21)

q1=1/5    q2=4/5

                            a22a11-a12a21
Value of game= ---------------------------   =17/5
                             (a11+a22)-(a12+a21)

Optimum Strategies are given by
       
           [ A1        A2
SA=     3/5        2/5]

             [B1       B2
SB =       1/5      4/5]

GAMES (2 x 2) WITHOUT SADDLE POINT

Consider a 2 x 2 , 2 person zero sum game without any saddle point having the pay off matrix for player as

          B1       B2
A1  [ a11        a12
A2    a21        a22]

The optimum strategy for A is given as
              [  A1       A2
 SA  =       p1        p2]

The optimm strategy for B is given as
            [ B1        B2
SB =      q1         q2]

             a22-a12
p1= ---------------------
       (a11+a22)-(a12+a21)

p1+p2=1
p2=1-p1


             a22-a21
q1 =  ----------------------
          (a11+a22)-(a12+a21)

q1+q2=1
q2=1-q1

                              a11a22 - a12a21
Value of game  = -----------------------------------
                              (a11+a22)-(a12+a21)

Game Theory Example

Q1.Solve the game whose Pay off Matrix is given by

                           B1          B2          B3           Player B
Player A  A1   [  1              3            1
               A2       0             -4          -3
               A3       1              5           -1]


Soln:
STEP I:
Find out the Row minima and column maxima.

              [1       3       1        1
               0       -4      -3      -4        maximin=1
               1        5       -1]     -1

               1         5        1
  minimax=1

STEP II:
maximin=minimax=1
There exists a saddle point value of game = 1
The optimal strategy is (A1,B1)    -->  this  value is the intersection of maxima and minima.
The game is strictly determined since maximin=minima   is not equal to  0

Q2. Solve:

[ 0      2
 -1      4]

Soln:
STEP I:
     [ 0      2   0
      -1      4]  -1     maximin=0
       0       4
minimax=0

STEP II:
maximin=minimax=0
there exists a saddle point value of game=0
The optimum strategy is (A1,B1)
The game is fair since maximin=minimax=0

MAXMIN MINIMAX Principle

MAXIMIN=MINIMAX PRINCIPLE

MAXIMIN- Maximum of  Minimum among the row
MINIMAX- Minimum of Maximum among the column

If maximin=minimax value then the corresponding stratifies are called Optimal Strategies and the game is said to have a Saddle Point.
The value of the game is given by the saddle point.

SADDLE POINT:
Saddle point is the position in which the maximum of row coincides with the minimum of column maxima.

Game Theory

COMPETITION:
Its a watch word of modern life.A competitive situation is called a game.
The term game represents the conflict between two or more parties.
STRATEGY:
It is defined as a complete set of plans of action.Its a decision rule for making a choice fom the list of course of action.
Two types of Strategy:
1. Pure Strategy
2. Mixed Strategy

A strategy is called pure if one knows in advance of the play that its certain to be adapted irrespective of the strategy the other player might choose.

The optimal strategy mixed for each player may be determined by assigning to each strategy its probability of being chosen.
ie., the probabilistic combination of available choices of strategy.

PAY OFF:
Pay off is the outcome of playing the game.If a Player 'A' has 'm' course of action and Player 'B' has 'n' course of action then the Pay off matrix may be constructed as

                      Player B
                      1          2          ........................ n
                1[ a11     a12         ................... ....a1n
Player A  2   a21    a22       ...........................a2n           -----> Out come of A
                .
                .
                .
                m    am1     am2   .........................amn]
----> Out come of B

TYPES OF GAME:
1. 2 Person Game
2. n Persons Game

ZERO SUM GAME:
Its one in which the sum of payment to all the competitors is zero for every possible outcome of game.

Sum of points won= sum of points lost

TWO PERSON ZERO SUM GAME:
Gain of one player=Loss of other player

A game with 2 players where the gain of one player equals to the loss of other.

TSP Example

Q2.A salesman has to visit 5 cities the distance between the 5 cities are as follows:

                             To City
                          A         B         C         D           E

From City   A[infi         7            6          8            4
                   B 7         infi            8          5            6
                   C 6           8           infi         9            7
                   D 8           5            9        infi            8
                   E  4           6            7          8           infi]

If the sales man starts from city A and has to come back to his starting point which route should he select so that the total distance covered is minimum.

Soln:'

If we solve this problem, the final distance matrix will be.

           A             B               C              D           E
A      infi              3                0              4             0
B       3              infi                1              0             1
C       0               1                infi             2             0
D       4               0                  2            infi            3
E        0               1                  0             3           infi

The travel is given as A-->E-->B-->D-->C-->A

Distance=4+5+6+9+6
             =30 Km