Understanding Game Theory: Basics and Applications

Game Theory

Objective Competition in business, military operations, advertising about a product , marketing etc., It is essential to guess the activities or actions of his opponent or competitor.

Game Theory Game theory is a mathematical theory that deals with the general features of competitive situations like these in a formal, abstract way. It places particular emphasis on the decision-making processes. Game theory is a decision theory in where ones choice of action is determined after talking into account all possible alternatives available to an opponent playing in a same field.

Basic Terms used in game theory Player Competitor(individual or group or organization) Strategy Alternate course of action(choices) Pure strategy Using same strategy each time (deterministic) Mixed strategy Using the course of action depending on some fixed probability. Optimum strategy The choice that puts the player in the most preferred position irrespective of his competitors strategy.

Two person zero sum game Definition: Only 2 persons are involved in the game and the gain made by one player is equal to the loss of the other. As the name implies, these games involve only two players .They are called zero- sum games because one player wins whatever the other one loses, so that the sum of their net winnings is zero. In general, a two-person game is characterized by The strategies of player 1. The strategies of player 2. The pay-off table.

Formulation of Two person zero sum game B1 B2 Bn A1 A2 . a11 a12 a1n a21 a22 ........a2n . . . Am am1 am2 . amn

Formulation of Two person zero sum game A1,A2, ..,Am are the strategies of player A B1,B2, ...,Bn are the strategies of player B aij is the payoff to player A (by B) when the player A plays strategy Ai and B plays Bj (aij is ve means B got |aij| from A)

Example Consider the game of the odds and evens. This game consists of two players A,B, each player simultaneously showing either of one finger or two fingers. If the number of fingers matches, so that the total number for both players is even, then the player taking evens (say A) wins Rs.1 from B (the player taking odds). Else, if the number does not match, A pays Rs.1 to B. Thus the payoff matrix to player A is the following table:

Optimum Solution A game can be solved by using the following three methods, based on the nature of the problem. Saddle point concept/Max-min and Min max principle Games without saddle point Dominance rule Graphical method. A primary objective of game theory is the development of rational criteria for selecting a strategy. Two key assumptions are made: Both players are rational Both players choose their strategies solely to promote their own welfare

Min- Max and Max-Min principle Max Min : A row(winning) payer will select the maximum out of the minimum gains. Min- Max : A column(loosing) player will always try to minimize his maximum losses. Saddle point: If the max-min and min-max values are same then the game has a saddle point and is the intersection point of both the values.

B1 B2 B3 B4 8 6 2 8 Row min 2 A1 A2 A3 8 9 4 (SP) 5 4 7 5 3 5 3 Col 8 9 4 8 Max Max min min max

Solution The solution of the game is based on the principle of securing the best of the worst for each player. If the player A plays strategy 1, then whatever strategy B plays, A will get at least 2. Similarly, if A plays strategy 2, then whatever B plays, will get at least 4. and if A plays strategy 3, then he will get at least 3 whatever B plays. Thus to maximize his minimum returns, he should play strategy 2.

Solution (cont..) Now if B plays strategy 1, then whatever A plays, he will lose a maximum of 8. Similarly for strategies 2,3,4. (These are the maximum of the respective columns). Thus to minimize this maximum loss, B should play strategy 3. and 4 = max (row minima) = min (column maxima) is called the value of the game. 4 is called the saddle-point.

Dominance Rule Definition: A strategy is dominated by a second strategy if the second strategy is always at least as good (and sometimes better) regardless of what the opponent does. Such a dominated strategy can be eliminated from further consideration. The following rules of dominance is used reduce the sixe of the matrix Row dominance Column dominance Modified row dominance- Average of rows Modified column dominance- Average of columns

Example Thus in our example (below), for player A, strategy A3 is dominated by the strategy A2 and so can be eliminated. Eliminating the strategy A3 , we get the B1 B2 B3 B4 A1 A2 A3 7 5 3 5 8 6 2 8 8 9 4 5

Cont.. following reduced payoff matrix: Now , for player B, strategies B1, B2, and B4 are dominated by the strategy B3. Eliminating the strategies B1 , B2, and B4 we get the reduced payoff matrix: B1 B2 B3 B4 A1 A2 8 9 4 5 8 6 2 8

Cont.. following reduced payoff matrix: Now , for player A, strategy A1 is dominated by the strategy A2. Eliminating the strategy A1 we thus see that A should always play A2 and B always B3 and the value of the game is 4 as before. B3 2 A1 4 A2

Example The following game gives A s payoff. Determine p,q that will make the entry (2,2) a saddle point. B1 B2 B3 A1 A2 A3 6 2 3 Col max max(p,6) max(q,5) 10 Since (2,2) must be a saddle point, 5 p 5 q Row min 1 q 6 min(1,q) p 5 10 min(p,5) 2

Example Specify the range for the value of the game in the following case assuming that the payoff is for player A. Row min B1 B2 3 6 1 B3 A1 A2 A3 1 2 5 2 3 4 2 -5 -5 3 Col max 5 6 Thus max( row min) <= min (column max) The game has no saddle point. Thus the value of the game lies between 2 and 3.

Games without saddle point(mixed strategy) No pure strategy or no saddle point exists. The optimal mix for each player may be determined by assigning each strategy a probability of it being chosen. Thus these mixed strategies are probabilistic combinations of available better strategies and these games hence called Probabilistic games. The probabilistic mixed strategy games without saddle points are commonly solved by any of the following methods Analytical Method Graphical Method Simplex Method

Analytical Method A 2x2 game without saddle point can be solved using following formula.

Formula

Example Solve the following game and determine its value

Graphical Method : Solution of 2 x n and m x 2 Games 2 x n and m x 2 Games : When the player A, for example, has only 2 strategies to choose from and the player B has n, the game shall be of the order 2 x n, whereas in case B has only two strategies available to him and A has m strategies, the game shall be a m x 2 game.

Example Solve the following using graphical method.

Algorithm for solving 2 x n matrix games Draw two vertical axes 1 unit apart. The two lines are x1 = 0, x1 = 1 Take the points of the first row in the payoff matrix on the vertical line x1 = 1 and the points of the second row in the payoff matrix on the vertical line x1 = 0. The point a1j on axis x1 = 1 is then joined to the point a2j on the axis x1 = 0 to give a straight line. Draw n straight lines for j=1, 2 n and determine the highest point of the lower envelope obtained. This will be the maximin point. The two or more lines passing through the maximin point determines the required 2 x 2 payoff matrix. This in turn gives the optimum solution by making use of analytical method.

Example Solve using graphical method

Solution

Cont.. V = 66/13 SA = (4/13, 9 /13) SB = (0, 10/13, 3 /13

Algorithm for solving m x 2 matrix games Draw two vertical axes 1 unit apart. The two lines are x1 =0, x1 = 1 Take the points of the first row in the payoff matrix on the vertical line x1 = 1 and the points of the second row in the payoff matrix on the vertical line x1 = 0. The point a1j on axis x1 = 1 is then joined to the point a2j on the axis x1 = 0 to give a straight line. Draw n straight lines for j=1, 2 n and determine the lowest point of the upper envelope obtained. This will be the minimax point. The two or more lines passing through the minimax point determines the required 2 x 2 payoff matrix. This in turn gives the optimum solution by making use of analytical method.

Example Solve by graphical method

Solution

Cont.. V = 3/9 = 1/3 SA = (0, 5 /9, 4/9, 0) SB = (3/9, 6 /9)