Mixing saddle points of a zero-sum game

Question

I am fairly new to proof writing so I would appreciate if you could help me out!

Suppose that $(X^*, Y^*)$ and $(X^0, Y^0)$are saddle points of a zero-sum game with payoff matrix $A$. Show that $(X^*, Y^0) and (X^0, Y^*)$ are also saddle points.

This is what I know: If $(X^*, Y^*)$ is a saddle point for a zero sum game with payoff matrix A (which is an $n \times m$ matrix), then

$ E(X,Y^*) \leq E(X^*,Y^*) \leq E(X^*,Y) \ \forall X \in S_n, Y \in S_m $

Where $E(X,Y)$ denotes the expected payoff to Player 1. Similarly, for $(X^0,Y^0)$ we have

$E(X,Y^0) \leq E(X^0,Y^0) \leq E(X^0,Y) \ \forall X \in S_n, Y \in S_m $

Now, to check whether $(X^0, Y^*)$ is a saddle point, I know that $E(X,Y^0)\leq E(X^*,Y^0)$ since $X^*$ is an optimal strategy for Player 1, but this feels like an illegal step to make. How should I go about it? Should I use that $E(X,Y)=\sum_j\sum_i x_i a_{i,j}y_j^T$?

I am stuck since the result looks so obvious but I can't think of a way to justify it.

Answer 1

I think the step you suspect is illegal is illegal indeed.

Note that the strategy $X^*$ is optimal, when we are sure that the other player plays $Y^*$, but we don't know yet, if it is optimal, when the other player plays any other strategy.

I'd rather approach the problem in the following way. Since $E(X, Y^*) \leq E(X^*, Y^*) \leq E(X^*, Y) \quad (*)$, and $E(X, Y^0) \leq E(X^0, Y^0) \leq E(X^0, Y) \quad (**)$ we also have the following inequalities:

$E(X^0, Y^0) \stackrel{(**)}{\leq} E(X^0, Y^*) \stackrel{(*)}{\leq} E(X^*, Y^*)$

$E(X^*, Y^*) \stackrel{?}{\leq} E(X^*, Y^0) \stackrel{?}{\leq} E(X^0, Y^0)$

Where I left the second line for you to fill in which inequalitites imply the inequalities. Can you finish the proof from here?

Answer 2

Then using the chain of inequalities from above i.e.,

$E(X^0,Y^0) \le E(X^0,Y*) \le E(X*,Y*)$ &

$E(X*,Y*)\le E(X*,Y^0)\le E(X^0,Y^0)$

along with (*) and (**)

We have,

$E(X,Y*)\le E(X^0,Y*)\le E(X^0,Y)$

$E(X,Y^0)\le E(X*,Y^0)\le E(X*,Y)$

Thus, $E(X*,Y^0)$ & $E(X^0,Y*)$ are indeed saddle points