Game theory

Definition, Terms Used, Types of Strategies,Odd method, Saddle Point, Dominance method, Graphical Method.

1. GAME THEORY Jagdeep Singh Jagdev

2. Definition of game theory The branch of mathematics concerned with the analysis of strategies for dealing with competitive situations where the outcome of a participant’s choice of action depends critically on the actions of other participants. Game theory has been applied to contexts in war, business, and biology

3. A few examples of competitive and conflicting decision environment Pricing of products, where sale of any product is determined not only by its price but also by the price set by competitors for a similar product The success of any TV channel programme largely depends on what the competitors presence in the same time slot and the programme they are telecasting The success of an advertising/marketing campaign depends on various types of services offered to the customers.

4. Terms Used in Game theory Number of Players • How many players are there? • If a game involves only two players (competitors), then it is called a two-person game. However, if the number of players is more, the game is referred to as n-person game Strategies: The strategy for a player is the list of all possible actions (moves or courses of action) that he will take for every payoff (outcome) that might arise. It is assumed that the rules governing the choices are known in advance to the players.

5. Payoffs are the consequences for each player for every possible profile of strategy choices for all players. Zero-sum (or constant-sum) game : one player's winnings are the others' losses, so the net gain is zero across all players Optimal Strategy: The particular strategy by which a player optimises his gains or losses without knowing the competitor's strategies. Value of game: The expected outcome per play when players follow their optimal strategy.

6. Assumptions of the Game theory Each player has available to him a finite number of possible strategies (courses of action). The list may not be same for each player. Player A attempts to maximize gains and player B minimise losses. The decision of both players are made individually prior to the play with no communication between them.

7. The decisions are made simultaneously and also announced simultaneously so that neither player has an advantage resulting from direct knowledge of the other player’s decision. Both the players know not only possible payoffs to themselves but also of each other.

8. Note By convention, the payoff table for the player whose strategies are represented by rows (say player A) is constructed.

9. Types of Strategies • Pure Strategy It is the decision rule which is always used by the player to select the particular strategy. Thus, each player knows in advance of all strategies out of which he always selects only one particular strategy regardless of the other player’s strategy, and the objective of the player is to maximize profit or minimize losses.

10. Mixed strategy Courses of action that are to be selected on a particular occasion with some fixed probability are called mixed strategies.

11. Pure Strategy Maximin – minimax principle Maximin Criterion: The player who is maximizing his outcome or payoff finds out his minimum gains from each strategy (course of action) and selects the maximum value out of these minimum gains. Minimax Criterion: In this criterion the minimizing player determines the maximum loss from each strategy and then selects with minimum loss out of the maximum loss list

12. Example 1 For the game with payoff matrix: Determine the best strategies for players A and B. Also determine the value of game. Is this game (i) fair? (ii) strictly determinable?

13. Example 1 Player A adopts A1 strategy. Player B adopts B3 strategy. Value of game V = -2 Not fair but strictly determinable.

14. Saddle Point or Equilibrium Point In a payoff matrix the value, which is the smallest in its row and the largest in the column, is called the saddle point.

15. Example 2 A company management and the labour union are negotiating a new three year settlement. Each of these has 4 strategies: (i) Hard and aggressive bargaining (ii) Reasoning and negotiating approach (iii) Legalistic strategy (iv)Conciliatory approach

16. The cost to the company are given for every pair of strategy choice What strategy will the two sides adopt? Also determine the value of the game.

17. The company will adopt strategy III And union will always adopt strategy I. Value of game V = 12

18. Mixed Strategies A method of playing a matrix game in which the player attaches a probability weight to each of the possible options, the probability weights being nonnegative numbers whose sum is unity, and then operates a chance device that chooses among the options with probabilities equal to the corresponding weights.

19. 1. Odds Method (2X2 matrix) If payoff matrix for player A is given by The following formulae are used to find the value of game and optimal strategies:

20. Value V ={a1 ( b1 – b2 ) + b1 ( a1 – a2 )}/{( b1 -b2 )+( a1 – a2 )} Prob. of A1 = ( b1 – b2 )/ {( b1 -b2 )+( a1 – a2 )} Prob. of A2 = ( a1 – a2 ) / {( b1 -b2 )+( a1 – a2 )} Prob. of B1 = ( a2 – b2 ) / {( a2 – b2 )+( a1 – b1 )} Prob. of B2 = ( a1 – b1 ) / {( a2 – b2 )+( a1 – b1 )}

21. Example 2 Two players A and B are involved in a game of matching coins. When there are both heads, player A wins 100 points and wins 0 when there are two tails. When there is one head and one tail, B wins 50 points. Determine the payoff matrix, the best strategy for both players A and B. Find the value of game to A.

22. Value V = {100 (50) + (-50)(150)} / {(-50) + (150)} = -12.5 Prob. of A selecting strategy H = 50/200 = 1/4 Prob. of A selecting strategy T = 150/200 = 3/4 Prob. of B selecting strategy H = 50/200 = 1/4 Prob. of B selecting strategy T = 150/200 = 3/4

23. Dominance Method Rule 1. If all the elements in a row (say ith row) of a payoff matrix are less than or equal to the corresponding elements of the other row (say jth row) then the player A will never choose the ith strategy or in other words the ith strategy is dominated by the jth strategy

24. Rule 2. If all the elements in a column (say rth column) of a payoff matrix are greater than or equal to the corresponding elements of the other column (say sth column) then the player B will never choose the rth strategy or in other words the rth strategy is dominated by the sth strategy. • Rule 3. A pure strategy may be dominated if it is inferior to average of two or more other pure stategies .

25. Example 3 Reduce the following game by dominance method and find the game value:

26. Graphical Method The graphical method is useful for the game where the payoff matrix is of the size m X 2 or 2 X n

27. Consider the following pay-off matrix Player A Player B   B 1 B 2 A 1 -2 4 A 1 8 3 A 1 9

28. Solution. The game does not have a saddle point as shown in the following table Player A   Player B Minimum Probability B 1 B 2 A 1 -2 4 -2 q 1 A 2 8 3 3 q 2 A 3 9 q 3 Maximum 9 4     Probability p 1 p 1  

29. First, we draw two parallel lines 1 unit distance apart and mark a scale on each. The two parallel lines represent strategies of player B . If player A selects strategy A1, player B can win –2 (i.e., loose 2 units) or 4 units depending on B’s selection of strategies. The value -2 is plotted along the vertical axis under strategy B 1  and the value 4 is plotted along the vertical axis under strategy B 2 . A straight line joining the two points is then drawn. Similarly, we can plot strategies A 2  and A 3  also . The problem is graphed in the following figure.

30. The lowest point V in the shaded region indicates the value of game. From the above figure, the value of the game is 3.4 units. Likewise, we can draw a graph for player B. The point of optimal solution (i.e., maximin point) occurs at the intersection of two lines: E1 = -2p 1  + 4p 2  and E2 = 8p 1  + 3p 2

31. Comparing the above two equations, we have -2p 1  + 4p 2  = 8p 1  + 3p 2 Substituting p 2  = 1 - p 1 -2p 1  + 4(1 - p 1 ) = 8p 1  + 3(1 - p 1 ) p 1  = 1/11 p 2  = 10/11 Substituting the values of p 1  and p 2  in equation E1 V = -2 (1/11) + 4 (10/11) = 3.4 units

32. Graphic Method (mX2 or 2Xn)

33. Good management is the art of making problems so interesting and their solutions so constructive that everyone wants to get to work and deal with them. - Paul Hawken