Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a game with two players P1 and P2. For P1 the set of strategies is $x_1,...,x_m$ and $y_1,...,y_n$ for P2, gains are $f_1(x_i,y_j)$ for P1 and $f_2(x_i,y_j)$ for P2. Define mixed strategies by $\mathbf{p}_1$ and $\mathbf{p}_2$ where $$ \mathbf{p}_1 = (p_{11},...,p_{1m})\quad\text{and}\quad \mathbf{p}_2 = (p_{21},...,p_{2n}) . $$

Then expected gains are given by $$ g_1(\mathbf{p}_1,\mathbf{p}_2) = \sum\limits_{i=1}^m\sum\limits_{j=1}^n f_1(x_i,y_j)p_{1i}\,p_{2j} $$ and $$ g_2(\mathbf{p}_1,\mathbf{p}_2) = \sum\limits_{i=1}^m\sum\limits_{j=1}^n f_2(x_i,y_j)p_{1i}\,p_{2j}. $$

If $\displaystyle{\frac{\partial g_1}{\partial p_{1i}}>0}$ then by increasing $p_{1i}$ we increase $g_1$, so in Nash equilibrium have to hold $$ \frac{\partial g_1}{\partial p_{1i}} = 0\text{ and }\frac{\partial g_2}{\partial p_{2j}} = 0 $$ for all $i = 1,...,m$ and $j = 1,...,n$. These are systems of linear equations. The first system contains $m$ equations on $n$ variables and the second contains $n$ equations on $m$ variables. It can be the case that there is no solution if $m\neq n$, but Nash equilibrium has to exist.

Could you please help me to find a mistake?

share|cite|improve this question
But the functions $g_1$ and $g_2$ are not a priori known. – GWu Apr 13 '11 at 14:40
@GWu: Why not? The gains are known (they define the game), and the probabilities are the variables -- in what sense are the functions not known? – joriki Apr 13 '11 at 14:45
What do you mean? they are given as expectations. – Ilya Apr 13 '11 at 14:45
up vote 4 down vote accepted

You didn't take into account the constraints: $\sum p_{1i}=\sum p_{2j}=1$ and $p_{1i},p_{2j}>0$. If there's no equilibrium in the interior, it has to occur on the boundary.

share|cite|improve this answer
Did you mean that the sum is equal to $1$? – Ilya Apr 13 '11 at 14:46
I did -- in fact I'd already fixed that in the meantime :-) – joriki Apr 13 '11 at 14:47
Is it a problem then to solve an overdefined system by putting some variables to the boundary? – Ilya Apr 13 '11 at 14:48
That's not what you're doing. You're setting up a system of linear equations, keeping in mind that these are necessary conditions for an equilibrium in the interior, but not necessary conditions for an equilibrium in general. If you find that this system of linear equations is overdetermined and has no solutions, you conclude that there is no equilibrium in the interior, and you go looking for one on the boundary. But then you're no longer solving the overdetermined system; you discarded the overdetermined system, and it's not relevant to solving the problem on the boundary. – joriki Apr 13 '11 at 14:52
But at the time e.g. only one $p_{1k}$ can be $1$. Can we use it? – Ilya Apr 13 '11 at 14:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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