2
$\begingroup$

To fix notation, let there be two players $\in N = \{1, 2\}$, finite action sets $A_j$ with $A = A_1 \times A_2$, and utility $u_j: A \rightarrow \mathbb{R}_+$. Define a set of strategies $S_j$ which are probability distributions (lotteries) over player action sets $A_j$, and $S = S_1 \times S_2$. Define expected utility $v_j(s_j, s_{-j}) = \sum_{a \in A}u_j(a)p(a)$, where $p(a) = s_1(a_1)s_2(a_2)$. A profile $s^* \in S$ is a Nash equilibrium if $\forall j \in N, \forall s_j \in S_j, \: \;v_j(s_j^*, s_{-j}^*) \geq v_j(s_j, s_{-j}^*)$.

Now consider a two person zero sum game ($u_1(a) = -u_2(a), N=\{1, 2\}$). I'm confused about proving the following remark:

$\textbf{(1)}$ "If $(s_1^*, s_2^*), (s_1', s_2')$ are nash equilibria, then so are $(s_1^*, s_2'), (s_1', s_2^*)$"

In the proof I have, all that is shown is: $\textbf{(2)}$ "Pick $\forall j $ any two $s_j^*, s_j' \in \arg\max_{s_j} \min_{s_{-j}} v_j(s_j, s_{-j})$, then they are Nash." Even though we may use $\max\min = \min\max$ here, I don't see how we can show this is the case (And I particularly don't see how the statement above is enough).

The statement above relies on a lemma which shows that when $\max\min = \min\max$ holds, if we choose $s_1^* \in \arg\max_{s_1} \min_{s_2} v_1(s_1, s_2)$, $s_2^* \in \arg\min_{s_2} \max_{s_1}v_1(s_1, s_2)$, then $(s_1^*, s_2^*)$ is Nash.

I don't see how the second part is exactly symmetric to $\arg\max\min$. Specifically, from $\textbf{(2)}$ we have that $s_2^* \in \arg\max_{s_2}\min_{s_1}v_2(s_2,s_1)$, but in the lemma we require $s_2^* \in \arg\min_{s_2} \max_{s_1}v_1(s_1, s_2)$. To me these seem like opposites because $v_1 = -v_2$.

More context can be found in A Course in Game Theory by Osborne and Rubinstein, Chapter 2 on Nash Equilibria. Thanks.

$\endgroup$

1 Answer 1

0
$\begingroup$

This is a misunderstanding with respect to $\arg\max$.

Although $\min_x(-f(x)) = -\max_x f(x)$, we have that $\arg\min_x(-f(x)) = \arg\max_xf(x).$

Thus, the terms above are in fact symmetric:

$$s_2^* = \arg\max_{s_2}\min_{s_1}v_2(s_1, s_2) = \arg\max_{s_2}\min_{s_1}(-v_1(s_1, s_2)) = \arg\max_{s_2}(-\max_{s_1}v_1(s_1, s_2)) = \arg\min_{s_2}\max_{s_1}v_1(s_1, s_2).$$

The solution then follows from the lemma.

Specifically, see Chapter 2, Lemma 22.1 in "A Course in Game Theory" by Osborne and Rubinstein.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.