In the following we will consider two-person zero-sum games. Let $A = (a_{ij})$ be the payoff-matrix of such a game. In this book the fundamental theorem of such games is states as:
Theorem: Given any $m \times n$ matrix $$ A = (a_{ij}) $$ there exists vectors $X = (x_1, \ldots, x_m), Y = (y_1, \ldots, y_n)$ with $y_i \ge 0, x_i \ge 0$ and $x_1 + \ldots x_m = y_1 + \ldots y_n = 1$ and a real number $v$ such that:
- $x_1 a_{1j} + \ldots + x_m a_{mj} \ge v$ for $j = 1,\ldots n$
- $a_{i1} y_1 + \ldots + a_{in} y_n \le v$ for $i = 1, \ldots m$.
The number $v$ is called the value of the game. The vectors $X$ and $Y$ are the optimal strategies for player 1 and player 2 respectively.
Lets consider player 1. A common method to find an optimal strategy for him is to find a probability distribution $X = (x_1, \ldots x_n)$ such that player 2 is indifferent regarding his pure strategies, meaning we are going to solve the equations $$ \sum_{i=1}^m x_i a_{i1} = \sum_{i=1}^m x_i a_{i2} = \ldots = \sum_{i=1}^m x_i a_{in} $$ and $x_1 + \ldots + x_n = 1$, $x_i \ge 0$. This is done for example in this question here on stackexchange.
Lets denote by $E(X,j) = \sum_{i=1}^m x_i a_{ij}$ the expectation for player 1 if player 2 plays his pure strategy $j$ (i.e. chooses the $j$-th column of the payoff-matrix).
Then as I see it the fundamental theorem stated above says that for the value $v$ of the game we have $E(X, j) \ge v$ for each pure strategy $j$ of player 2. But the above method of solving a game uses, I guess, a much stronger claim, namely that $$v = E(X, 1) = E(X,2) = \ldots = E(X,n)$$ if $X$ is optimal? (This is the condition we solve for). So here are my question.
- Am I right in my objection, and if not
- Can you give me an example of a game such that $E(X, j) > v$ for some optimal strategy $X$ of player 1 and some pure strategy $j$ of player 2 (i.e. not equality with the value for the pure strategy)?
Thank you!
First: the players must be indifferent only between strategies that they assign positive probability. What is really hard about finding equilibria is to find which strategies receive positive prob.
Second: the method of equating payoffs (of strategies that have positive payoff) does not use $E[X,j]=v$ since (accordingly to the question) these are the payoffs of 1 given a pure strategy of 2. If you are going to look at the payoffs of 1 then you must consider the pure strategies of 1 given the mixed strategy of 2 -- maybe you want to call it $E[j,Y]$? Because this is a zero-sum game it really doesn't matter, see point forth. But it matters for general games.
Third: In a zero-sum (or constant) bi-matrix game: you will attain the value with equality.
Forth: Let $(X,Y)$ be a mixed strategy Nash eq. of zero-sum game then $u_2(X,s_j)=c$ for all $s_j$ such that $y_j>0$ and constant $c$. Since it is zero sum game $u_1(X,s_j)=-c$. So yes: the payoff of player 1 when 1 mixes accordingly to $X$ is constant for any strategy that 2 plays with positive prob.
Unrelated but of interest: In zero-sum games, equilibria are interchangeable: if $(X,Y)$ and $(W,Z)$ are equilibria then $(X,Z)$ and $(W,Y)$ are also equilibria.