1
$\begingroup$

Can someone explain to me the minmax value which we calculate, for example, in repeated games? And the intuition behind it.

I think I keep calculating it the wrong way. For Player 1 I look at every column what is his best payoff and then minimize those values over the columns (Player I is the row player).

For example, $$ \begin{array}{|c|c|} \hline (3,1) & (0,0) \\ \hline (1,2) & (4,3) \\ \hline \end{array} $$

By my (wrong) conlusions I would get 3 for player one, but if I calculate it explicitly with mixed strategies I get 2. Is there a way to see it rightaway? What should I be looking for when just observing the matrix?

In the example below:

$$\begin{array}{|c|c|c|} \hline (0, 0) & (2, 4) & (4,2) \\ \hline (4,2) & (0,0) & (2,4) \\ \hline (2,4) & (4,2) & (0,0)\\ \hline \end{array}$$

the minmax values should be $0$. How can I see the minmax value without calculating explicitly the equation below?

$$\bar{v}_i = \underset{\sigma_{-i} \in \times_{j \neq i} \Sigma_{j}}{\min}\underset{\sigma_{-i} \in \times_{j \neq i} \Sigma_{j}}{\max}u_i(\sigma_i, \sigma_{-i})$$

$\endgroup$
2
  • $\begingroup$ Your definition concerns the minimax with respect to mixed strategies, as standard. But your discussion seems to be assuming pure strategies. Would you clarify, please? $\endgroup$
    – mlc
    Aug 12, 2017 at 12:39
  • $\begingroup$ It should be mixed but in class we always look at the pure first and then discuss whether there's an equilibrium in mixed strategies. What I think I got wrong (for pure) is that I fix the columns first and then search for the best outcome, but I should look at the rows and see what's the worst that can happen (for row player). I'm not sure how to see when it's enough to look at just pure strategies. In the 3x3 matrix in the example, row player's strategy is (1/3,1/3,1/3) to get the most $\endgroup$
    – Waddles
    Aug 13, 2017 at 7:21

1 Answer 1

3
$\begingroup$

Is it $0$ or is it $2$ from the second example you provided?

Let us label the rows and the columns to simplify the discussion. The first row will be $U$; the second row will be $M$; the third row will be $D$; the first column will be $L$; the second column will be $C$ and the third column will be $R$. We are assuming player 1 is the row player and player $2$ is the column player.

Suppose player $2$ is playing $L$ with probability $\beta_1$ and playing $C$ with probability $\beta_2$. Payoffs from playing $U$, $M$ and $D$ respectively are:

\begin{align*} & u_1(U,\beta_1,\beta_2)=\beta_1 0+\beta_2 2+(1-\beta_1-\beta_2) 4=2[2-\beta_12-\beta_2],\\ & u_1(M,\beta_1, \beta_2)=\beta_14+\beta_20+(1-\beta_1-\beta_2)2=2[1+\beta_1-\beta_2],\\ & u_1(R,\beta_1, \beta_2)=\beta_1 2+\beta_2 4+(1-\beta_1-\beta_2)0=2[\beta_1 +\beta_2 2]. \end{align*}

It is without loss of generality to the take the inner maximum of the max-min payoff of player $1$ over his set of pure strategies (right?). Therefore, using the values of player $1$ expected utility, we get the following relation:

\begin{align*} \underset{a_1\in A_1}{max} u(a_1,\beta_1, \beta_2)= \begin{cases} 2[2-\beta_12-\beta_2] & \text{if $\beta_1+\beta_2 \le 2/3$ and $\beta_2\ge 1/3$},\\ 2[\beta_1+\beta_2 2] & \text{if $\beta_1+\beta_2 \ge 2/3$ and $\beta_2\ge 1/3$},\\ 2[1+\beta_1-\beta_2] & \text{if $\beta_1 +\beta_2\ge 2/3$ and $\beta_2\le 1/3$},\\ 2[2-\beta_12-\beta_2] & \text{if $\beta_1 +\beta_2\le 2/3$, $\beta_2\le 1/3$, $\beta_1\le 1/3$},\\ 2[1+\beta_1-\beta_2] & \text{if $\beta_1 +\beta_2\le 2/3$, $\beta_2\le 1/3$, $\beta_1\ge 1/3$}, \end{cases} \end{align*}

Suppose $\beta_1+\beta_2 \le 2/3$ and $\beta_2\ge 1/3$. 2 minimizes $\max u_1(a_1,\beta_1, \beta_2)$ in this case by setting $\beta_1=\beta_2=1/3$. This leads to a payoff of $2$. Suppose $\beta_1+\beta \ge 2/3$ and $\beta_2\ge 1/3$. 2 minimizes $\max u_1(a_1,\beta_1, \beta_2)$ in this case by setting $\beta_1=\beta_2=1/3$. This leads to a payoff of $2$. Suppose $\beta_1+\beta \ge 2/3$ and $\beta_2\le 1/3$. 2 minimizes $\max u_1(a_1,\beta_1, \beta_2)$ in this case by setting $\beta_1=\beta_2=1/3$. This leads to a payoff of $2$. Suppose $\beta_1+\beta_2 \le 2/3$, $\beta_2\ge 1/3$ and $\beta_1\le 1/3$. 2 minimizes $\max u_1(a_1,\beta_1, \beta_2)$ in this case by setting $\beta_1=\beta_2=1/3$. This leads to a payoff of $2$. Finally, suppose $\beta_1+\beta_2 \le 2/3$, $\beta_2\ge 1/3$ and $\beta_1\ge 1/3$. 2 minimizes $\max u_1(a_1,\beta_1, \beta_2)$ in this case by setting $\beta_1=\beta_2=1/3$. This leads to a payoff of $2$.Therefore, player $2$ min-max payoff is $2$. In any case, the minimum payoff is $2$ so $\bar{v}_1=2$.

Payoffs of player $2$ from playing $L$, $C$ and $R$ respectively are:

\begin{align*} & u_2(L,\alpha_1,\alpha_2)=\alpha_1 0+\alpha_2 2+(1-\alpha_1-\alpha_2) 4=2[2-\alpha_12-\alpha_2],\\ & u_2(C,\alpha_1, \alpha_2)=\alpha_14+\alpha_20+(1-\alpha_1-\alpha_2)2=2[1+\alpha_1-\alpha_2],\\ & u_2(R,\alpha_1, \alpha_2)=\alpha_1 2+\alpha_2 4+(1-\alpha_1-\alpha_2)0=2[\alpha_1 +\alpha_2 2]. \end{align*}

As before, player $1$ min-max strategy is choosing $\alpha_1=\alpha_2=1/3$ and forcing player $2$ to a payoff of $2$. We conclude the min-max value of the game for both players is $2$.

Answering to your question, I do not think there is a way of knowing whether the game will have a min-max value in pure or mixed strategies, but here are some tips:

  • The min-max payoff in pure strategies is always weakly lower than the min-max in pure strategies;
  • Any Nash equilibrium (in pure or mixed strategies) must generate a payoff for each player weakly higher than the min-max payoff of this player.
$\endgroup$
1
  • $\begingroup$ for the minmax payoff for player 1 (the rows), it should be 4 I think? My thinking was that because the inner max gives the result that all 3 rows gives the maximum value $4$, and so the minimum of $\left\{4,4,4\right\}$ is just $4$. $\endgroup$
    – ghjk
    Mar 3, 2020 at 7:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .