I know that Iterated Elimination of Strictly Dominated Strategies (IESDS) never eliminates a strategy which is part of a Nash equilibrium. Is the reverse also true? And is there a proof somewhere? I only found this as a statement in a series of slides, but without proof. It seems like this should be true, but I can't prove it myself properly.
Q: If a strategy survives IESDS, is it part of a Nash equilibrium? (mixed strategies also allowed)
Thanks in advance,
Maxim
No. Observe the following payoff matrix: $\begin{bmatrix} 1,1 & 1,5 & 5,2 \\ 1,2 & 1,1 & 1,1 \\ 5,1 & 1,5 & 1,2 \\ \end{bmatrix}$.
The row player's strategy space is $(U,M,B)$ and the column palyer's is $(L,M,R)$.
Ther is no pure Nash equilibrium if where the row player plays $M$, because column's best response is $U$, but to $U$ row's best response ins $B$.
There are also no mixed equilibria in which row plays $B$:
if column mixes over his entire strategy space - $x = (a, b, 1-a-b)$
$u_1(U,x) = 5-4(a+b)$, $u_1(M,x) = 1$, $u_1(B,x) = 1+4a$. I.e. $u_1(U,x) > u_1(M,x) \wedge u_1(B,x) > u_1(M,x) \Rightarrow$ if column plays x row plays $M$ with probability zero.
If column mixes over $(L, M)$ - $x = (a, 1-a, 0)$ $u_1(U,x) = 1$, $u_1(M,x) = 1$, $u_1(B,x) = 1+4a$. I.e. $u_1(B,x) > u_1(U,x) \wedge u_1(B,x) > u_1(M,x) \Rightarrow$ if column plays x row plays $M$ and $U$ with probability zero.
If column mixes over $(L, R)$ - $x = (a, 0, 1-a)$ $u_1(U,x) = 5-4a$, $u_1(M,x) = 1$, $u_1(B,x) = 1+4a$. I.e. $u_1(U,x) > u_1(M,x) \wedge u_1(B,x) > u_1(M,x) \Rightarrow$ if column plays x row plays $M$ with probability zero.
If column mixes over $(M, R)$ - $x = (0, a, 1-a)$ $u_1(U,x) = 5-4a$, $u_1(M,x) = 1$, $u_1(B,x) = 1$. I.e. $u_1(U,x) > u_1(M,x) \wedge u_1(B,x) > u_1(M,x) \Rightarrow$ if column plays x row plays $M$ and $B$ with probability zero.