1
$\begingroup$

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?

  • 0
    But the functions $g_1$ and $g_2$ are not *a priori* known.2011-04-13
  • 0
    @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?2011-04-13
  • 0
    What do you mean? they are given as expectations.2011-04-13

1 Answers 1

4

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.

  • 0
    Did you mean that the sum is equal to $1$?2011-04-13
  • 0
    I did -- in fact I'd already fixed that in the meantime :-)2011-04-13
  • 0
    Is it a problem then to solve an overdefined system by putting some variables to the boundary?2011-04-13
  • 0
    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.2011-04-13
  • 0
    But at the time e.g. only one $p_{1k}$ can be $1$. Can we use it?2011-04-13
  • 0
    Sure -- whatever comes out of the optimization. The fact that *in general* you need mixed strategies to guarantee the existence of a Nash equilibrium doesn't mean that you can't get pure equilibrium strategies in some cases. For instance, if we both get $0$ if we don't both cooperate, and get $1$ if we both do, then the only Nash equilibrium is that we both cooperate with probability $1$; no need for mixed strategies there.2011-04-13
  • 0
    But note that one probability being $1$ is not the only way that the equilibrium can lie on the boundary. Some probabilities could be $0$ while others are fractional. In that case, the linear equations for the fractional probabilities will hold but the ones for the zero probabilities generally won't.2011-04-13
  • 0
    Sure. Isn't it a solvable procedure?2011-04-13