Deck 15: Game Theory

Question 1

Consider the two-person,zero-sum game having the following payoff table. Determine the optimal strategy and payoff for each player by successively eliminating dominated strategies.Show your reasoning and the order in which you eliminated strategies.

Answer 1

Since but with ,strategy 1 of player 2 is dominated by strategy 3,so this strategy 1 is eliminated.Next,[-2 -1] < [3 1] and [-2 -1] < [4 0] ,so strategy 2 for player 1 is dominated by both strategy 1 and strategy 3,so this strategy 2 is eliminated.Next, ,so strategy 2 for player 2 is dominated by strategy 3,so this strategy 2 is eliminated.Finally,1 > 0,so strategy 3 for player 1 is dominated by strategy 1,so this strategy 3 is eliminated.Therefore,player 1 will choose strategy 1 and player 2 will choose strategy 3,resulting in a payoff of 1 to player 1 and a payoff of -1 to player 2.

Question 2

Consider the two-person,zero-sum game having the following payoff table. (a)Assuming this is a stable game,use the minimax (or maximin)criterion to determine the best strategy for each player.Does this game have a saddle point? If so,identify it.Is this a stable game? (b)Formulate the problem of finding the optimal pure or mixed strategy for player 1 according to the maximin criterion as a linear programming problem.(c)If the simplex method were to be applied to the linear programming problem formulated in part (b),would this also identify the optimal pure or mixed strategy for player 2? If so,describe how.

Answer 2

(a)Applying the minimax criterion to player 2 and the maximin criterion to player 1 yields the following results. Maximum 5 3 5 Minimax value Thus,strategies 1 and 2 both yield the maximin value of -2 for player 1.Strategy 2 yields the minimax value of 3 for player 2.However,the entries in the payoff table that yield the maximin and minimax values are not the same,so we do not have a saddle point.Therefore,this is not a stable game,so the players instead need to find their optimal mixed strategies for this unstable game.(b)Let x_i = probability that player 1 will use strategy i (i = 1,2,3)x₄ = value of the game for player 1.Using the formulation developed in Sec.15.5,the linear programming formulation for player 1 now is Maximize x₄,subject to 5x₁ - 2x₂ + 4x₃ - x₄ ≥ 0 -2x₁ + 3x₂ - 3x₃ - x₄ ≥ 0 3x₁ - x₂ + 5x₃ - x₄ ≥ 0 x₁ + x₂ + x₃ = 1 and x₁ ≥ 0,x₂ ≥ 0,x₃ ≥ 0.(c)The corresponding linear programming formulation for player 2 is the dual of the linear programming model (the primal)formulated for player 1 in part (b).Applying the simplex method to find the optimal solution for the primal problem also automatically identifies the optimal solution for the dual problem as well in Row 0 of the simplex tableau (as described in Sec.6.1).Therefore,yes,applying the simplex method to the linear programming problem formulated in part (b)also will identify the optimal mixed strategy for player 2.