# Game Theory: Zero-sum game, saddle point proof.

Let $A = (a_{ij} )$ be an $m × n$ matrix zero-sum game. Let $u = min_i(max_j a_{ij} )$ and $v = max_j (min_i a_{ij} )$. Prove that a saddle point exists if and only if u = v.

Moreover, if u = v, show that a saddle point occurs wherever the extremes u and v are attained.

The following "proof" seems redundant and too simple to be convincing, would love feedback regarding how I went about this, what I should change, what you would do, etc.

Attempted Proof:

"$\Rightarrow$" Suppose that a saddle point exists.

So, the $n x m$ payoff matrix has a point $a_{ij}$ that is the minimum of the $ith$ row and a maximum of the $jth$ column. (Definition of Saddle point).

Player 1 can win at least $a_{ij}$ by choosing row $i$.

Player 2 can keep loss to minimum $a_{ij}$ by choosing column $j$.

The saddle point exists, so the point $a_{ij}$ is a minimum of its row and a maximum of its column, concluding that $u = min_i (max a_{ij}) = max_j(min_i a_{ij}) = v$.

"$\Leftarrow$" Suppose that $u=v$.

So, $u = min_i (max a_{ij}) = max_j(min_i a_{ij}) = v$.

So, Player 1 can win at least $a_{ij}$ by choosing row $i$ and Player 2 can keep loss to minimum $a_{ij}$ by choosing column $j$.

So, saddle point where there is an intersection of the $ith$ row and the $jth$ column exists.

NOTE: A saddle point is a point in a matrix that is the minimum of the largest column values and the maximum of the smallest row values

• You might add the definition of a saddle point and make the question self-contained. – mlc May 23 '17 at 19:58

"$\Rightarrow$" Assume that a saddle point exists.

Let the saddle point of Matrix A be $v$.

Then, $v$ is the minimum value of its row.

So, $v \leq a_j$ for all elements in row $j$.

For every element in row $j$, the maximum of that element's column is either that element, or a larger element in that column.

So, the maximum of all other columns is greater than or equal to $v$ and $v$ is the maximum of its column, thus, $v$ is the smallest maximum of all columns.

Since $v$ is a saddle point, $v$ is the maximum of its column.

So, $v \geq a_i$ for all elements in column $i$.

For every element in column $i$, the minimum of that elements row is either that element, or a smaller element. Either way, $v$ is greater than or equal to minimum element of the other rows. And $v$ is the minimum of its row, so $v$ is the largest minimum of all rows.

Concluding that $min_i(max_j a_{ij}) = v = max_j (min_i a_{ij})$, which shows that if $u = min_i(max_j a_{ij} )$ and $v = max_j (min_i a_{ij} )$, and there is a saddle point, $u = v$.

"$\Leftarrow$" Suppose that $u=v$.

So, $min_i(max_j a_{ij} )= u = v = max_j (min_i a_{ij} )$.

So, $v = u \geq a_i$ for all elements in column $i$ and $v \leq a_j$ for all elements in row $j$.

So, $v$ is the minimum of its row, and $v$ is the maximum of its column, so player 1 can play her strategy without regret and player 2 can play her strategy without regret, and thus $v$ is a saddle point.