2
$\begingroup$

The minimax theorem of von Neumann says that for any payoff matrix $A$, we have \begin{equation} \max_x \min_y x^T A y = \min_y \max_x x^T A y. \end{equation} In the above, $x$ and $y$ are probability distributions. In the special case when $A$ satisfies: $$\max_i \min_j A_{ij} = \min_j \max_i A_{i,j} (=A_{\bar{i},\bar{j}}),$$ the maximizing distribution $x$ and the minimizing $y$ in von Neumann's equality above is simply $x = e_{\bar{i}}$ and $y = e_{\bar{j}}$. (The Nash equilibrium is attained by pure strategies for both players.)

In a yet more (?) specific case when $A$ has a dominant column or a dominant row, i.e. there exists a $\bar{j}$ so that $$A_{i,\bar{j}} \leq A_{i,j}, \;\;\; \forall i, \; \forall j,$$ or there exists a $\bar{i}$ so that $$A_{\bar{i},{j}} \geq A_{i,j}, \;\;\; \forall i, \; \forall j,$$ it is quite easy to show that $A$ satisfies the second equality above.

Question: Does the second equality above imply the existence of a dominant row or column?

$\endgroup$

1 Answer 1

2
$\begingroup$

This is a $3 \times 3$ counterexample. $$ \begin{bmatrix} 2 & -1 & -2 \\ 1 & 0 & 1 \\ -2 & -1 & 0 \end{bmatrix} $$ It has maxmin = minmax = 0, but it does not have a dominant column and does not have a dominant row.

Smaller $2 \times 3$ counterexample: $$ \begin{bmatrix} 1 & 2 & 3 \\ 3 & 2 & 2 \end{bmatrix} $$

For $2 \times 2$ matrices the implication holds. If $A$ has maxmin=minmax, without loss of generality assume it appears at $a_{11}=0$, and $$ A = \begin{bmatrix} 0 & b \\ c & d \end{bmatrix} $$ with $b\ge 0$ and $c \le 0$. Now if $d \ge 0$, the first column is dominant , and if $d < 0$, the first row is dominant.

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