Existence of Saddle Point of a Matrix (Shapley's Theorem) 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 ?
 A: Let, $v = \operatorname{Val}[M]$.
Let, $j_1$ be the index of the column with minimum number of entries ($r$, assume $r > 0$) greater than $v$.
Let, $i_1$ be a row position where, $a_{i_1j_1} > \omega$, then, $\exists \, j_2$ such that $a_{i_1j_2} \le v$.
Since, the column indexed by $j_2$ has atleast $r$ positions with entry value $> v$, too many to be paired off against the $r-1$ remaining entries $>v$ of the other column  $j_1$.
Hence, $\exists \, i_2$ column position such that $a_{i_2j_2} > v > a_{i_2j_1}$.
Since, the $2 \times 2$ submatrix:
$$\begin{align} & (j_1) & (j_2) \\ (i_1) & > v & \le v \\ (i_2) & \le v &  > v \end{align}$$
clearly has no saddle-point, the assumption $r > 0$ must be incorrect.
Hence, there is a column with no entries $> v$.
Similarly, we can prove there is a row with no entry less than $v$.
Hence, the matrix $M$ has a pure saddle point.
A: 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. 
