3
$\begingroup$

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

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

"$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.