2
$\begingroup$

In the attached Zero Sum Game, i have solved for two Mixed Nash Equilibrium, $(l,m)$ and $(m,r.)$

  • In $(l,m)$ the payoff is $8/5$ to $P_1$, and $-8/5$ to $P_2$. Here $P_1$ mixes between Top and Bottom with probability $4/5$ and $1/5$ respectively. $P_2$ mixes between left and middle with probability $3/5$ and $2/5$ respectively.

  • In $(m,r)$ the payoff is $5/2$ to $P_1$ and $-5/2$ to $P_2$. Here player 1 mixes between Top and Bottom with probability $1/2$ each. And Player two mixes between middle and right with probability $1/4$ and $3/4$ respectively.

I am confused about how this equilibrium relate to each players max-min and min-max strategy and Von Neumann's Minimax theorem. And the theorems of Zero-sum games more generally.

  • For Example: I was under the impression there zero sum games have a unique mixed Nash Equilibrium which would involve player 1 "maximising over the lower envelope." I.e.The 8/5 payoff representing some kind of Security Strategy in terms of Mixed Strategies. I thought this was meant to be the same as player two's Min-Max Strategy, but i feel like that would refer to the other equilibrium on the upper envelope.

enter image description here

$\endgroup$

1 Answer 1

1
$\begingroup$

A two-playerr zero-sum game in normal form is expressed as: $g_1\left(s_{1,i}, s_{2,j}\right) + g_2\left(s_{1,i}, s_{2,j}\right) =0 \forall s_{1,I } \in S_1,\forall s_{2,j} \in S_2 $ where $ S_1=\left\{s_{1,1},..., s_{1,m}\right\} $ and $ S_2=\left\{s_{2,1},..., s_{2,n}\right\} $ are the strategies. The payment functions $ g_1 $ and $ g_2 $ can be represented by means of a matrix consisting of $m$ rows and $n$ columns. The players 1 and player 2 know the contents of the payment matrix: the game consists for each k-th player in choosing a strategy $ s_{k,i} \in S_k $ without knowing the choice of the other. With regards to to the payout matrix for player 1 we set $ A_1\left(s_{1,i}, s_{2,j}\right) = A \left(s_{1,i}, s_{2,j}\right) $ and $ A_2\left(s_{1,i}, s_{2,j}\right) = - A\left(s_{1,i}, s_{2,j}\right) $ The choice of a strategy by player 1 corresponds to the choice of a row, while for player 2 it corresponds to the choice of a column. Player 2 will pay player 1 the sum indicated at the intersection of the row chosen by player 1 with the column chosen by player 2.

The attention of the two players is directed to the same object: the matrix $A$. Player 1 tries to maximize $A$, but his control is limited only to choosing one row. Ditto for player 2 who tries to minimize $A$: his control is limited only to the choice of a column.

What will be the criterion for choosing the two players?

John von Neumann answered this question using the following criterion: player 1 first detects the smallest number in each row and decides to choose the row that contains the largest of the monetary values considered: in this way he is certain that his winnings will not be less than the value $ max_i \left(min_j a_{i,j} \right) $ whatever player 2 chooses. Player 2, for his part, considers the largest number in each column and decides to choose the column that contains the smallest of the numbers considered: thus, he is certain that his loss will not be greater than the value $ min_j \left(max_i a_{i,j} \right) $ whatever player 1 chooses. What has just been described represents the definition of rational behavior given by John von Neumann and is commonly referred to as the minimax decision rule.

The pair of strategies $ s_1^e $, $s_2^e$ constitute an equilibrium point, saddle point if the two conditions hold:

  1. $g\left(s_1^e, s_2^e \right) \ge \ g\left(s_{1,i}, s_2^e \right) \forall s_{1,i} \in S_1$

  2. $g\left(s_1^e, s_2^e \right) \le \ g\left(s_1^e, s_{2,j} \right) \forall s_{2,j} \in S_2$

1-st Condition refers to the maximizing player, 2-nd condition to the minimizing player.

The definition of equilibrium according to Von Neumann given in zero-sum games is the "translation" of the concept of equilibrium in the Nash sense given for non-cooperative games. Below we illustrate how to move from the concept of Von Neumann equilibrium to the concept of Nash equilibrium: just remember that for a zero-sum game we have: $g_1$ = $ g$ and $ g_2$ = $ -g$. It then becomes legitimate to write: $g_1 \left(s_1^e, s_2^e \right) \ge \ g_1 \left(s_{1,i}, s_2^e \right) \forall s_{1,i} \in S_1$

The first equilibrium condition in the Von Neumann sense is therefore the first equilibrium condition in the Nash sense referring to player 1.

For player 2 we have: $-g_2 \left(s_1^e, s_2^e \right) \le \ -g_2 \left(s_1^e, s_{2,j} \right) \forall s_{2,j} \in S_2$

that is

$g_2\left(s_1^e, s_2^e \right) \ge \ g_2\left(s_1^e, s_{2,j} \right) \forall s_{2,j} \in S_2$.

Minimax Theorem Let $ {\displaystyle g:\mathit{K_{1}}\times \mathit{K_{2}} \to \mathbb{R}} $ be a continuous function where $ \mathit{K_{1}} \subset \mathbb{R}^m $ and $ \mathit{K_{2}} \subset \mathbb{R}^n $ are compact convex set. If $g$

$ g(\cdot, s_2):\mathit{K_{1}} \to \mathbb{R}$ is concave for fixed $s_2$ and

$ g(s_1,\cdot):\mathit{K_{2}}\to \mathbb{R} $ is convex for fixed $s_1$

then $\min_{s_1\in \mathit{K_{1}}}\max_{s_2\in \mathit{K_{2}}} g(s_1,s_2)=\max_{s_1\in \mathit{K_{2}}}\min_{s_1\in \mathit{K_{1}}}g(s_1,s_2) $

It is easy to think of the payment function $g:S_1 \times S_2 \rightarrow \mathbb{R} $ as an alternating bilinear form whose alternation property $g(s_1,s_2) = - g( s_2,s_1) $ mathematizes the total opposition of the two players, i.e. the fact that the sum of the payments is zero. The two sets $S_1$ and $S_2$ appear to be compact since they are finite and therefore have no accumulation points. The payment functions $g_i$ are defined on sets without accumulation points, sets therefore consisting only of isolated points, i.e. points in which the two functions $g_i$ are continuous. The reader should regard to $s_1$ as mixed strategies: a non-negative m-tuple of numbers $(\tilde s_1,\ldots, \tilde s_m) $ such that $ \tilde s_1+...+\tilde s_m = 1 $. The same for $s_2$. The domain of variation of mixed strategies is more extensive than that of pure strategies: for the latter, in fact, the domain is a simple finite set of $m$ ordered m-nuples, while mixed strategies are defined on a subset of the vector space of size $m$ consisting of all the convex linear combinations of the $m$ pure strategies. The same for $s_2$. The convex hull $K_i$ is compact because it is built on the compact set of pure strategies. If $ g_1(\cdot,\tilde s_2)$ is convex with respect to $\tilde s_1$ for a fixed $\tilde s_2$ and since $g_1=-g_2$, then $g_2(\tilde s_1,\cdot)$ is concave with respect to $\tilde s_2$ for a fixed $\tilde s_1$.

As a result the conditions of the minimax theorem are satisfied.

To conclude in the field of mathematical programming, remember that a two-player zero-sum game can always be turned into a pair of mutually dual linear programs. The optimal value of the two problems corresponds to the value of the game $v$. We identify the generic mixed strategy with $ \mathbf x$ where a k pure strategy is a vector of the type $(0, \cdots, , 0, 1, 0, \cdots, 0)$ with $x_k=1$.

Linear programming formulation For the maximizing player we have the following primal problem:

$\max_{x\in \mathit{K_{1}}} v $

Subject to

$ \left\{ \begin{array}{l} \begin{matrix} \sum_{j=1}^n a_{i,j} \cdot x_{j} \end{matrix} \ge v \quad \forall i=1,...,m \\ \begin{matrix} \sum_{j=1}^n x_{j} \end{matrix} = 1 \\ x_{j} \ge 0 \quad \forall j=1,...,n \\ \end{array} \right.$

Example Reader can easily fix the first matrix of the example (l,m) to $A$ and solve the Linear Programme. For example, the (l,m) matrix $$\begin{matrix} \begin{array}{c|c|c} &a^1 &a^2 \\ \hline a_1 & 2 & 1 \\ \hline a_2 & 0 & 4 \end{array} \end{matrix} $$ has the optimal strategy $=(s_{1,1}^e, s_{1,2}^e)=(0.8 , 0.2)$ with regards to maximizing player. The value of the game is $1.6$. The point $(0.8 , 0.2)$ is the intersection of $ x_{1,1}+ x_{1,2}=1$ with $1.6= 1x_{1,1}+ 4x_{1,2}$ and with $1.6= 2x_{1,1}+ 0x_{1,2}$.

$\endgroup$
6
  • $\begingroup$ Thank you for this answer, i upvoted as i appreciate the effort. it did clarify to me that for example if i write a Matrix A with positive payoffs, P1 has a max min problem and P2 has a Min Max problem, but if i write a seperate Matrix -A for player 2, then they also have a max-min problem (i.e. picking the most negative number in each column, and then choosing the largest (smallest in absolute value) of these. However your answer hasn't addressed the heart of my concerns regarding the mixed equilibrium etc. $\endgroup$
    – CormJack
    Apr 15 at 20:13
  • $\begingroup$ To add more clarity to my questions, with regards to the specific example i have provided: 1) How do the Mixed Nash Equilibriums relate to Player 1's Min-Max and Max-Min Strategy` 2) How do the Mixed Nash Equilibriums relate to Player 2's Min-Max and Max-Min Strategy 3) How does this game illustrate the relationship found in zero sum games, between players Min-Max and Max-Min Strategy. 4) How does this game illustrate Von Neumann's Minimax theorem. $\endgroup$
    – CormJack
    Apr 15 at 20:14
  • $\begingroup$ I hope the additional part clarifies $\endgroup$ Apr 16 at 7:15
  • $\begingroup$ Hey, thanks again i mean it's helpful! But It would help me parse the information you have provided if it was related to the example i posted. For instance, I think that the lower envelope that corresponds to the payoff 8/11, represents for player, one a Max-Min solution, because the envelope represents the set of minimum playoffs to P1, and the equilibriums is the maximum point. And vice Versa given P2 has costs, it represents Min-max payoff to P2 because it represents her lowest cost envelope, but the largest cost point on it. And then these are reversed for payoff point 5/2. So... $\endgroup$
    – CormJack
    Apr 16 at 10:54
  • $\begingroup$ So what we say is that for both points to be equilibriums in this Zero Sum Game, each point has to be a Max-min for one player and a min-Max for the other. And that is the point that Von Neumann was making (?). It's not that we necessarily require a unique equilibrium, just that the equilibriums in a zero sum game, master is a bit this property.... I think what I have said is true, but this is the kind of insight I was looking for with reference to the specific example with two equilibriums that I provided? $\endgroup$
    – CormJack
    Apr 16 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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