Game Theory Operation Research

GAME THEORY
Terminology
Example : Game with Saddle point
Dominance Rules: (Theory-Example)
Arithmetic method – Example
Algebraic method - Example
Matrix method - Example
Graphical method - Example

1. Operations research Chapter: GAME THEORY Terminology Example : Game with Saddle point Dominance Rules: (Theory-Example) Arithmetic method – Example Algebraic method - Example Matrix method - Example Graphical method - Example

2. What is Game Theory ? At its most basic level,  game theory  is the study of how people or companies (referred as players) determine strategies in different situations despite of competing strategies acted out by other players. What is two person zero sum game? The simplest type of competitive situation. These games involve only  two  players. This game is called  zero - sum  game because one player wins whatever the other player loses.

3. What is Saddle Point? If Maximin = Minimax What is strategy? :  A move or moves chosen by a player.

4. What is optimal strategy? An  optimal strategy  is one that provides the best payoff for a player in a  game .  The strategy that most benefits a player. Optimal Strategy  = A strategy that maximizes a player's expected payoff. What is Value (expected value) of game?:   The amount representing the result when the best possible strategy is played by each player.

5. What is Payoff? It is an outcome of game. An amount showing as an element in the payoff matrix, which indicates the amount gained or lost by the row player . What is payoff matrix? In  game theory , a  payoff matrix  is a table in which strategies of one player are listed in rows and strategies of the other player are listed in columns and the cells show   payoffs  to each player  A matrix whose elements represent all the amounts won or lost by the row player.

6. Pure strategy:  A player always chooses the same strategy-same row or column. Mixed strategy :  A player chooses the strategy with some fix probabilities. A player changes the choice of row or column with different plays or turns.

7. Method 1 : Saddle Point Steps (Rule) Step-1: 1. Select the minimum element from each row and write them in Row Minimum – last column . 2. Select the maximum element from Row Minimum column and enclose it in [ ]. It is called Row MaxiMin . Step-2: 1. Select the maximum element from each column and write them in Column Maximum- last row . 2. Select the minimum element from Column Maximum row and enclose it in ( ). It is called Column MiniMax . Step-3: 1. Find out the elements that is same in rectangle [ ] and circle ( ). 2. If Column MiniMax = Row MaxiMin then the game has saddle point and it is the value of the game.

8. Player A \ Player B B1 B2 B3 B4 A1 20 15 12 35 A2 25 14 8 10 A3 40 2 10 5 A4 -5 4 11 Example-1 Find Solution of game theory problem. Following payoff matrix is given in data.

9. Player  B B 1 B 2 B 3 B 4 Player  A A 1  20   15   12   35  A 2  25   14   8   10  A 3  40   2   10   5  A 4  -5   4   11   0  Solution: Apply the maximin ( minimax ) principle to analyze the game. Saddle point testing

10. Player  B B 1 B 2 B 3 B 4 Row Minimum Player  A A 1  20   15    [(12)]    35  [12] A 2  25   14   8   10  8 A 3  40   2   10   5  2 A 4  -5   4   11   0  -5 Column Maximum 40 15 (12) 35 Maximin Minimax

11. select minimum from the maximum of columns Column MiniMax = (12) Select maximum from the minimum of rows Row MaxiMin = [12]

12. ANSWER Here, Column MiniMax = Row MaxiMin = 12 This is game with saddle point value of the game V= 12 The optimal strategies for both players are The player A will always adopt strategy A1 The player B will always adopt strategy B3

13. Example-2 Player A \ Player B B1 B2 B3 A1 -2 14 -2 A2 -5 -6 -4 A3 -6 20 -8 Find Solution of game theory problem using saddle point

14. Player  B B 1 B 2 B 3 Player  A A 1  -2   14   -2  A 2  -5   -6   -4  A 3  -6   20   -8  Solution: Saddle point testing

15. Player  B B 1 B 2 B 3 Row Minimum Player  A A 1   [( -2 )]   14   -2  [-2 ] A 2  -5   -6   -4  -6 A 3  -6   20   -8  -8 Column Maximum (-2) 20 -2 We apply the maximin ( minimax ) principle to analyze the game. Minimax Maximin

16. ANSWER: Here, Column MiniMax = Row MaxiMin = -2 ∴  This game has a saddle point and value of the game is -2 The optimal strategies for both players are The player A will always adopt strategy 1 The player B will always adopt strategy 1 Select minimum from the maximum of columns Column MiniMax = (-2) Select maximum from the minimum of rows Row MaxiMin = [-2]

17. Operation research GAME THEORY Dominance Rule : (Theory-Example)

18. Dominance Rules: ( method Steps ) Step-1: If all the elements of Column- i are greater than or equal to the corresponding elements of any other Column-j, then the Column- i is dominated by the Column-j and it is removed from the matrix. eg . If all values of Column-2  ≥  Column-4, then remove Column-2 Step-2: If all the elements of a Row- i are less than or equal to the corresponding elements of any other Row-j, then the Row- i is dominated by the Row-j and it is removed from the matrix. eg . If all values of Row-3   ≤  Row-4, then remove Row-3 Step-3: If strategy k is dominated by average of any two strategy i and j than delete column or row strategy k Why Dominance Rules used? To reduce size of payoff matrix in game theory

19. Player A \ Player B B1 B2 B3 B4 A1 3 5 4 2 A2 5 6 2 4 A3 2 1 4 A4 3 3 5 2 Example-3 Reduce matrix size of game theory problem using dominance method and Find Solution.

20. Player A \ Player B B1 B2 B3 B4 A1 3 5 4 2 A2 5 6 2 4 A3 2 1 4 A4 3 3 5 2 Solution: Dominance rule to reduce the size of the payoff matrix Row-3  ≤ Row-4, so remove Row-3

21. Player  B B 1 B 2 B 3 B 4 Player  A A 1  3   5   4   2  A 2  5   6   2   4  A 4  3   3   5   2  Column-2  ≥  Column-4, so remove Column-2

22. Player  B B 1 B 3 B 4 Player  A A 1  3   4   2  A 2  5   2   4  A 4  3   5   2 Column-B1 ≥ Column-B4, so remove Column-B1

23. Player  B B 3 B 4 Player  A A 1  4   2  A 2  2   4  A 4  5   2  Row-1 ≤ Row-3, so remove Row-1

24. Player  B B 3 B 4 Player  A A 2  2   4  A 4  5   2  Now, Find out solution  Optimum strategy and value of game

25. Player A \ Player B B1 B2 B3 A1 1 7 2 A2 6 2 7 A3 5 1 6 Example 4: Reduce matrix size of game theory problem using dominance method and Find Solution.

26. Player  B B 1 B 2 B 3 Player  A A 1  1   7   2  A 2  6   2   7  A 3  5   1   6  Solution: Apply Dominance rule to reduce the size of the payoff matrix All Values of row-3  ≤  row-2, so remove row-3

27. Player  B B 1 B 2 B 3 Player  A A 1  1   7   2  A 2  6   2   7  All Values of column-3 ≥ column-1, so remove column-3

28. Player  B B 1 B 2 Player  A A 1  1   7  A 2  6   2 

29. Operations research GAME THEORY Arithmetic method – Example Algebraic method - Example

30. Mixed strategy :  A player chooses more than one strategy with some fix probabilities. Game without Saddle Point If Maximin ≠ Minimax It is also known as mixed strategy problem

31. Solution Methods of Game without Saddle Point problem For 2*2 matrix size problems four methods are used to find solution: Arithmetic method Algebraic method Matrix method Alternate-calculus method

32. Arithmetic method Steps (Rule) Step-1: Find the difference between the two values of Row-1 and put this value against the Row-2, ignore the sign. Step-2: Find the difference between the two values of Row-2 and put this value against the Row-1, ignore the sign. Step-3: Find the difference between the two values of Column-1 and put this value against the Column-2, ignore the sign. Step-4: Find the difference between the two values of Column-2 and put this value against the Column-1, ignore the sign. Step-5: Find probabilities of each by dividing their sum Step-6: Find value of the game by algebraic method.

33. Player A \ Player B B1 B2 B3 A1 10 5 -2 A2 13 12 15 A3 16 14 10 Example-1 Find Solution of game theory problem using arithmetic method

34. Solution: Saddle point testing Player A \ Player B B1 B2 B3 A1 10 5 -2 A2 13 12 15 A3 16 14 10

35. We apply the maximin ( minimax ) principle to analyze the game. Player A \ Player B B1 B2 B3 Row Minimum A1 10 5 -2  -2 A2 13 [ 12 ] 15 [ 12 ] Maximin A3 16 ( 14 ) 10 10 Column Maximum 16 ( 14 ) Minimax 15

36. Select minimum from the maximum of columns Column MiniMax = (14) Select maximum from the minimum of rows Row MaxiMin = [12] Here, Column MiniMax  ≠ Row MaxiMin ∴ This game has no saddle point.

37. Player A \ Player B B1 B2 B3 A1 10 5 -2 A2 13 12 15 A3 16 14 10 Apply Dominance rule to reduce the size of the payoff matrix row-1 ≤ row-3, so remove row-1

38. Player A \ Player B B1 B2 B3 A2 13 12 15 A3 16 14 10 row-1 ≤ row-3, so remove row-1 column-1 ≥ column-2, so remove column-1

39. Player A \ Player B B2 B3 A2 12 15 A3 14 10 column-1 ≥ column-2, so remove column-1

40. Using arithmetic method to get optimal mixed strategies for both the firms.

41. Probabilities P(A2)=4/7=0.57 P(A3)=3/7=0.43 Hence, Firm  A  should adopt strategy  A 2 and  A 3 with 57% of time and 43% of time respectively.

42. Probabilities P(B2)=5/7=0.71 P(B3)=2/7=0.29 Firm  B  should adopt Strategy  B 2 and  B 3 with 71% of time and 29% of time respectively.

43. Value of Game: Expected gain of Firm A

44. Expected loss of Firm B

45. Example-2 Find Solution of game theory problem using arithmetic method (Practice Problem: similar as problem 1) Player A \ Player B B1 B2 B3 A1 1 7 2 A2 6 2 7 A3 5 1 6

46. Player  B B 1 B 2 B 3 Row Minimum Player  A A 1  1   7   2  1 A 2  (6)    [2]    7  [2] A 3  5   1   6  1 Column Maximum (6) 7 7 We can apply the maximin ( minimax ) principle to analyze the game.

47. Select minimum from the maximum of columns Column MiniMax = (6) Select maximum from the minimum of rows Row MaxiMin = [2] Here, Column MiniMax  ≠ Row MaxiMin ∴ This game has no saddle point.

48. Apply Dominance rule to reduce the size of the payoff matrix row-3 ≤ row-2, so remove row-3 Player  B B 1 B 2 B 3 Player  A A 1  1   7   2  A 2   6   2  7 

49. column-3 ≥ column-1, so remove column-3 Player  B B 1 B 2 Player  A A 1  1   7  A 2   6 2  

50. Hence, firm  A  should adopt strategy  A 1 and  A 2 with 40% of time and 60% of time respectively.

51. Similarly, firm  B  should adopt strategy  B 1 and  B 2 with 50% of time and 50% of time respectively.

52. Value of Game:

53. 2. Algebraic method

54. Operations research GAME THEORY Lecture 4 Matrix method - Example Graphical method - Example

55. Matrix Method

56. Example

57. where  p 1 and  p 2 represent the probabilities of player A's, using his strategies  A 1 and  A 2 respectively.

58. where  q 1 and  q 2 represent the probabilities of player B's, using his strategies  B 1 and  B 2 respectively.

59. Hence, Value of the game  V  = (Player A's optimal strategies) × (Payoff matrix  Pij ) × (Player B's optimal strategies)

60. Graphical method Steps (Rule) Step-1: This method can only be used in games with no saddle point, and having a pay-off matrix of type n × 2 or 2 × n. Step-2: The example is used to explain the procedure.

61. Example

62. A1 A2 A1 A2

63. Self Practice Problem

64. Summery GAME THEORY Terminology Example : Game with Saddle point Dominance Rules: (Theory-Example) Arithmetic method – Example Algebraic method - Example Matrix method - Example Graphical method - Example