A $m\times n$ matrix $M=(a_{ij})_{m\times n}$ with real entries is said to have a pure saddle point at $(i_0,j_0)$ if $\min_j \max_i (a_{ij}) = \max_j \min_i (a_{ij}) = a_{i_0j_0}$. Here the notation means if the maximum among the row-minimum for each row and the minimum among the column-maximum for each column occurs at the same position $(i_0,j_0)$, we call the position a pure saddle point of $M$. If every $2 \times 2$ sub-matrix of $M$ has a pure saddle point, show that $M$ has a pure saddle point.
It seems a solution to the problem is discussed in "Some Topics in Two-Person Games", 1964, Annals of Mathematical Studies. Unfortunately the google book preview does not show the page (pg. 7).
http://books.google.co.in/books?id=xXfGm5JHhgwC&printsec=frontcover#v=onepage&q&f=false
Can someone help me with the proof of the theorem ?
Edit : I verified the case where $M = (a_{ij})_{m\times n}$ is a $\{0,1\}$-matrix (i.e. the entries are $0$ or $1$), has a pure saddle point.
The $2\times 2$ submatrices has a pure saddle point, iff it is not of the form $\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix}$ or $\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}$. The remaining 6 cases can be verified to have pure saddle points.
Therefore, A $\{0,1\}$-matrix with the property that every submatrix has a pure saddle point, has no $2\times 2$-submatrix of the form $\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix}$ or $\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}$. I.e. for every pair of rows $r_i$ and $r_j$, either $r_i$ dominates $r_j$ or $r_j$ dominates $r_i$. Similar assertion can be made for columns of $M$. Therefore we can permute the rows and columns in such a fashion that $r_i$ dominates $r_j$ whenever $i>j$, and $c_i$ dominates $c_j$ whenever $i<j$. Suppose after this rearrangement of rows and columns of the matrix $M$ we call it $M'$. Then either $M'$ has a row of all $1$'s or a column of all $0$'s. In either case the position $(n,1)$, of the matrix $M'$ is a pure saddle point.
Can a similar argument be made for the general $m\times n$, real matrix ?
Let, $a_{i_0j_0}=\max_{i}\min_{j}a_{ij}$. Then $$a_{i_0,j_0}\ge \min_{j}a_{ij}\quad\forall i$$ Now, fix a column index, say $j_1$ and a row index, say $i_1$. Then, $\{i_0,j_0\},\{i_0,j_1\},\{i_1,j_0\},\{i_1,j_1\}$ form a $2\times 2$ sub-matrix $A_{i_1,j_1}$ with $$a_{i_0,j_0}\ge \min_{j\in j_0,j_1}a_{ij}\quad\forall i\in i_0,i_1$$ Since every $2\times 2$ sub-matrix has a pure saddle point, this implies that $a_{i_0,j_0}$ is a pure saddle point of $A_{i_1j_1}$. So, $$a_{i_0,j_0}\le \max_{i\in i_0,i_1}a_{ij} \quad \forall j\in j_0,j_1$$ But this is true $\forall j_1,i_1$. So, $$a_{i_0,j_0}\le \max_{i}a_{ij}\quad \forall j\Rightarrow a_{i_0,j_0}=\min_{j}\max_{i}a_{ij}$$ Hence, $a_{i_0,j_0}$ is a pure saddle point.