Question

True or False (proof or counterexample): If a strategy profile survives IESDS then it must also be a Nash equilibrium.

Answer 1

The proposition basically goes like, if a strategy solution is Nash equilibrium then it can not be eliminated by IESDS. This is the reverse scenario present in the question, which is not necessarily true in general, except for some special exceptional cases.

So the statement is FALSE.

Proof of the verdict : (Source : http://homepages.math.uic.edu/~marker/stat473-S16/IESDS.pdf )

statement : If (a ∗ , b∗ ) is a Nash equilibrium, then (a ∗ , b∗ ) is not eliminated by IESDS.

Proof: We prove this by contradiction. Suppose (a ∗ , b∗ ) is eliminated during IESDS. Then one of the strategies is removed at some stage of the construction. Let’s suppose that a ∗ is removed before b ∗ (the other case is similar). Consider the stage when a ∗ is eliminated. At this stage of the construction, we have a game where a ∗ and b ∗ are possible strategies and, because it is about to be eliminated, there is a strategy a 0 ∈ A1 such that a 0 strictly dominates a ∗ . But then v1(a 0 , b∗ ) > v1(a ∗ , b∗ ) and a ∗ is not a best response for Player 1 to b ∗ . This contradicts our assumption that (a ∗ , b∗ ) is a Nash equilibrium. The converse fails. For example, in Battle of the Sexes, (F, O) and (O, F) are not eliminated by IESDS (or even IEDS) but are not Nash equilibria. Similarly, in Mathching Coins no strategies are elimated by IESDS (or IEDS) but no strategy profile is a Nash equilibrium. The converse is true in the special case when there is IEDS solution–i.e. some IESDS procedure ends in a unique solution.