Game theory- operation research- Dr. Mohamed Sameh.pdf

Game theory by dr. Mohamed Saemh

1. OPERATIONS
RESEARCH
Dr. Mohamed Sameh

2. GAME THEORY

3. 3
Game theory
◦Contains a finite number of players.
◦Each player has a number of actions called ‘strategies’.
◦All the strategies and their effects are known to the players.
◦No player knows his opponent’s strategy until he decides his own.
◦The outcomes of strategies are put in a ‘pay-off matrix’.
◦The players playing the game are assumed “Rationale”, i.e. always trying to
choose ‘optimal strategy’.
◦The expected payoff is known as ‘Value of the game’.
◦The game is said to be ‘fair’ if the value of the game is zero.Otherwise, it’s
‘unfair’.

4. 4
Strategy
◦Pure Strategy:
◦Each player knows exactly what the other player is going to do.
◦A deterministicsituation.
◦The objective is to maximize the actualgain.
◦Mixed Strategy:
◦Each player is guessing which activity is to be selected by the other.
◦A probabilisticsituation.
◦The objective is to maximize the expectedgain.

5. 5
TWO-PERSON
ZERO-SUM GAME
◦Most common form
◦Two competitors, each will be rewarded
◦Fixed reward total
◦What one wins, the other loses

6. 6
Payoff matrix
◦Player A has ‘m’ strategies and player B has ‘n’ strategies.
◦Rows (i) are the strategies available to player A.
◦Columns (j) are the activities strategies to player B.
◦Cell value V
ijis the payment to player A if A chooses strategy iand B chooses
strategy j.
◦In a zero-sum, two-person game, player B’s payoff is the negative of player A’s.
◦Payoff matrices for player A and player B is ultimately zero.

7. 7
Minimax criterion (Pure strategy)
1.Identify the players.
2.Identify the possible strategies for each of them.
3.Identify the payoff for all strategy combinations.
4.Build the Pay-off matrix for one of the players.
5.Apply minimax criterion.
6.Each player should play in such a way as to minimize his maximum losses.
7.Player 1should select the strategy whose minimum payoff is largest (max-mini ), whereas player 2
should choose the one whose maximum payoff to player 1 is the smallest (mini-max).
8.Determine the saddle point if it exists, where mini-max = max-mini (stable solution).
9.The Saddle point has always the minimum payoff in its row and the maximum in its column.
10.If there is no saddle point, the solution is unstable.

8. 8
Example
◦CokeandPepsiarecompetingagainsteachothertohavethehighestbeveragesales
duringsummer.TheyarebothplanningbigadvertisingcampaignsduringJulyand
Augustintwoofthenorthcoastvillages,MarassiandAmwaj.Theyhaveachoiceof
eitherspendingamonthineachvillageorspendingthetwomonthsinoneofthem.
Sincethenecessaryarrangementsmustbemadeinadvance,neithercompanywilllearn
theother’scampaignscheduleuntilafterithasfinalizeditsown.Therefore,each
companyhasaskeditsadvertisingmanagertoassesswhattheimpactwouldbe(in
termsofsaleswonorlost)fromthevariouscombinationsofstrategiestousethis
informationtochoosethebeststrategy.ThePayoffforeachcombination(intermsof
millionbottlessales)forCokearetabulated.
Pepsi
Coke
Strat. 1Strat. 2Strat. 3
Spend one month in each village (strat. 1) 1 -1 1
Spend two months in Marassi(strat. 2) -2 0 3
Spend two months in Amwaj(strat. 3) 3 1 2

9. Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3 Minimum
Strat. 1 1 -1 1 -1
Strat. 2 -2 0 3 -2
Strat. 3 3 1 2 1
Maximum 3 1 3
Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3
Strat. 1 1 -1 1
Strat. 2 -2 0 3
Strat. 3 3 1 2
Solution
Mini-max value Max-mini value
Saddle point
Optimal strategy:
-For Coke : Strat.3
-For Pepsi: Strat.2
-Value (V) = +1 for Coke
-V = -1 for Pepsi

10. 10
Dominated strategies (pure & mixed)
1.Identify the players.
2.Identify the possible strategies for each of them.
3.Identify the payoff for all strategy combinations.
4.Build the Pay-off matrix for one of the players.
5.Apply dominated strategies to find the solution (pure) or thin out the matrix(mixed).
6.A strategy is dominated by another if the second strategy has always an equal or a
better pay-off regardless of what the opponent does.
7.Usually used for big tables.

11. 11
Example
◦CokeandPepsiarecompetingagainsteachothertohavethehighestbeveragesales
duringsummer.TheyarebothplanningbigadvertisingcampaignsduringJulyand
Augustintwoofthenorthcoastvillages,MarassiandAmwaj.Theyhaveachoiceof
eitherspendingamonthineachvillageorspendingthetwomonthsinoneofthem.
Sincethenecessaryarrangementsmustbemadeinadvance,neithercompanywilllearn
theother’scampaignscheduleuntilafterithasfinalizeditsown.Therefore,each
companyhasaskeditsadvertisingmanagertoassesswhattheimpactwouldbe(in
termsofsaleswonorlost)fromthevariouscombinationsofstrategiestousethis
informationtochoosethebeststrategy.ThePayoffforeachcombination(intermsof
millionbottlessales)forCokearetabulated.
Pepsi
Coke
Strat. 1Strat. 2Strat. 3
Spend one month in each village (strat. 1) 2 3 5
Spend two months in Marassi(strat. 2) 2 1 4
Spend two months in Amwaj(strat. 3) 0 -1 -3

12. Solution
Dominating
strategy
Dominated
strategy
Dominating
strategy
Dominated
strategy
Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3
Strat. 1 2 3 5
Strat. 2 2 1 4
Strat. 3 0 -1 -3
Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3
Strat. 1 2 3 5
Strat. 2 2 1 4

13. Solution
Pepsi
Coke
Strat. 1 Strat. 2
Strat. 1 2 3
Strat. 2 2 1
Dominating
strategy
Dominated
strategy
Pepsi
Coke
Strat. 1 Strat. 2
Strat. 1 2 3
Dominating
strategy
Dominated
strategy
Pepsi
Coke
Strat. 1
Strat. 1 2
Optimal strategy:
-For Coke : Strat.1
-For Pepsi: Strat.1
-V = +2 for Coke
-V = -2 for Pepsi

14. 14
Mixed strategies
1.Identify the players.
2.Identify the possible strategies for each of them.
3.Identify the payoff for all strategy combinations.
4.Build the Pay-off matrix for one of the players.
5.Apply minimax criterion.
6.No saddle point is found.
7.Apply dominance to thin out the table.
8.Use one of the following:
▪ODDS METHOD (2x2 game)
▪Sub Games Method. –For (mx2) or (2xn) Matrices
▪Equal Gains Method.
▪Linear Programming Method-Graphic solution (For (mx2) or (2xn) Matrices).

15. 15
ODDS Method (Mixed Strategies)
1.Find out the difference in the value of in cell (1, 1) and the value in the cell (1,2) of the first row and place
it in front of secondrow.
2.Find out the difference in the value of cell (2, 1) and (2, 2) of the second row and place it in front of first
row.
3.Find out the differences in the value of cell (1, 1) and (2, 1) of the first column and place it below the
secondcolumn.
4.Find the difference between the value of the cell (1, 2) and the value in cell (2, 2) of the second column and
place it below the firstcolumn.
5.The above odds or differences are taken as positive.
Player 2
Strat.1 (Y1)Strat.2 (Y2)
Player 1
Strat.1 (X1) a1 a2 |b1-b2|
Strat.2 (X2) b1 b2 |a1-a2|
|a2-b2| |a1-b1|

16. 16
ODDS Method
1.Calculate the following:

17. 17
Example
◦CokeandPepsiarecompetingagainsteachothertohavethehighestbeveragesales
duringsummer.TheyarebothplanningbigadvertisingcampaignsduringJulyand
Augustintwoofthenorthcoastvillages,MarassiandAmwaj.Theyhaveachoiceof
eitherspendingamonthineachvillageorspendingthetwomonthsinoneofthem.
Sincethenecessaryarrangementsmustbemadeinadvance,neithercompanywilllearn
theother’scampaignscheduleuntilafterithasfinalizeditsown.Therefore,each
companyhasaskeditsadvertisingmanagertoassesswhattheimpactwouldbe(in
termsofsaleswonorlost)fromthevariouscombinationsofstrategiestousethis
informationtochoosethebeststrategy.ThePayoffforeachcombination(intermsof
millionbottlessales)forCokearetabulated.
Pepsi
Coke
Strat. 1Strat. 2Strat. 3
Spend one month in each village (strat. 1) 1 5 5
Spend two months in Marassi(strat. 2) 4 2 4
Spend two months in Amwaj(strat. 3) 0 -1 -3

18. Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3 Minimum
Strat. 1 1 5 5 1
Strat. 2 4 2 4 2
Strat. 3 0 -1 -3 -3
Maximum 4 5 5
Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3
Strat. 1 1 5 5
Strat. 2 4 2 4
Strat. 3 0 -1 -3
Solution
Mini-max value
Max-mini value
No Saddle point

19. Solution
Dominating
strategy
Dominated
strategy
Dominating
strategy
Dominated
strategy
Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3
Strat. 1 1 5 5
Strat. 2 4 2 4
Strat. 3 0 -1 -3
Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3
Strat. 1 1 5 5
Strat. 2 4 2 4

20. Solution
Pepsi
Coke
Strat. 1 Strat. 2
Strat. 1 1 5
Strat. 2 4 2
Expected Value of the game =
1∗2+(4∗4)
(2+4)
=3
For coke; probability for strat. 1 = 1/3 , strat. 2 = 2/3
For Pepsi; probability for strat. 1 = 1/2 , strat. 2 = 1/2
Pepsi
Strat.1 (Y1)Strat.2 (Y2)
Coke
Strat.1 (X1) 1 5 |b1-b2|= 2
Strat.2 (X2) 4 2 |a1-a2|= 4
|a2-b2|=3 |a1-b1|=3

21. 21
Graphical Solution (Mixed strategies)
1.Find which player has only two strategies.
2.Assign X as the probability of using strat. 1 and (1-X) as the probability of using strat. 2.
3.Plot the expected payoff as a function of X for each of the opponent’s pure strategies.
Expected payoff = σ
�=1
�
σ
�=1
�
??????
���
��
�
Hint:put X = 0 , and X = 1 as your graph limits.
4.This graph can then be used to identify the point that maximizes the minimum expected payoff.
5.The probability x can be found from the lowest intersection of the drawn lines.
6.The expected value can be then calculated from the equation of any of the lines.
7.The probabilities of the other player strategies can be calculated from the expected payoff equation.

22. 22
Example
◦CokeandPepsiarecompetingagainsteachothertohavethehighestbeveragesales
duringsummer.TheyarebothplanningbigadvertisingcampaignsduringJulyand
Augustintwoofthenorthcoastvillages,MarassiandAmwaj.Theyhaveachoiceof
eitherspendingamonthineachvillageorspendingthetwomonthsinoneofthem.
Sincethenecessaryarrangementsmustbemadeinadvance,neithercompanywilllearn
theother’scampaignscheduleuntilafterithasfinalizeditsown.Therefore,each
companyhasaskeditsadvertisingmanagertoassesswhattheimpactwouldbe(in
termsofsaleswonorlost)fromthevariouscombinationsofstrategiestousethis
informationtochoosethebeststrategy.ThePayoffforeachcombination(intermsof
millionbottlessales)forCokearetabulated.
Pepsi
Coke
Strat. 1Strat. 2Strat. 3
Spend one month in each village (strat. 1) 1 5 5
Spend two months in Marassi(strat. 2) 4 2 4
Spend two months in Amwaj(strat. 3) 0 -1 -3

23. Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3 Minimum
Strat. 1 1 5 5 1
Strat. 2 4 2 4 2
Strat. 3 0 -1 -3 -3
Maximum 4 5 5
Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3
Strat. 1 1 5 5
Strat. 2 4 2 4
Strat. 3 0 -1 -3
Solution
Mini-max value
Max-mini value
No Saddle point

24. Solution
Dominating
strategy
Dominated
strategy
Dominating
strategy
Dominated
strategy
Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3
Strat. 1 1 5 5
Strat. 2 4 2 4
Strat. 3 0 -1 -3
Pepsi
Coke
Strat. 1 Strat. 2 Strat. 3
Strat. 1 1 5 5
Strat. 2 4 2 4

25. Solution
Pepsi
Coke
Strat. 1 Strat. 2
Strat. 1 1 5
Strat. 2 4 2
First plot line equation = 1 * X + 4 * (1-X) = 4 –3X
Second plot line equation = 5 * X + 2 *(1-X) = 2+ 3X
Pepsi
Strat.1 (Y1)Strat.2 (Y2)
Coke
Strat.1 (X) 1 5
Strat.2 (1-X) 4 2
|a2-b2|=3 |a1-b1|=3

26. Solution
From graph; point of intersection occurs at (1/3, 3)
The probability of using strat.1 for Coke = 1/3
The probability of using strat.1 for Coke = 2/3
Expected Payoff = σ
�=1
�
σ
�=1
�
??????
���
��
�=3.
For Pepsi; expected payoff =(4-3X)* Y
1+ (2+3X)* Y
2 = 3
Put: x =0➔4Y
1+2Y
2= 3 & x= 1 ➔Y
1+5 Y
2= 3
Solving for both equations;
The probability of using strat.1 for Pepsi = 1/2
The probability of using strat.1 for Pepsi = 1/2

27. THANK YOU!