3
$\begingroup$

Consider the following game matrix $$ \begin{array}{l|c|c} & \textbf{S} & \textbf{G} \\ \hline \textbf{S} & (-2,-2) & (-6, -1) \\ \hline \textbf{G} & (-1,-6) & (-4, -4) \end{array} $$ which corresponds to the well-known prisonder's dilemma. Now a Nash Equilibrium by using pure strategies would be (G,G) cause by choosing them neither can improve his outcome by unilaterally changing his strategy.

Now I wanted to calculate a Nash Equilibrium for mixed strategies using this payoff-matrix. (I am using an algorithm proposed at the German wikipedia Article on Nash-Equilibrium). So, I am looking for a mixed strategy for player II which makes player I indifferent regarding his strategy choices, and vice versa.

Let $q$ be the probability that player II chooses $S$ and accordingly $(1-q)$ that he chooses $G$, then the expected values for player I are \begin{align*} EV(I | S) & = (-2)q + (-6)(1-q) \qquad \textrm{if he chooses $S$} \\ EV(I | G) & = (-1)q + (-4)(1-q) \qquad \textrm{if he chooses $G$} \end{align*} (I use the notation $EV(I | S)$ to mean, expected value of player $I$ when he chooses $S$ and so on).

Equating them, to find the probablities for player II which make player I indifferent, I have to solve $$ -2q - 6(1-q) = -q - 4(1-q) $$ which has the solution $q = 2$, which is impossible since q should be a probablity, so with the additional restriction $0 \le q \le 1$ it has no solution? But I heard that Nash-Equilibrium for mixed strategies always exists in finite games, so what did I wrong?

$\endgroup$
  • $\begingroup$ pure strategy is a special case of mixed strategy $\endgroup$ – Artem Mar 8 '13 at 13:26
  • $\begingroup$ yes, but then I should get $q = 0$ as a special solution, which I didn't... $\endgroup$ – StefanH Mar 8 '13 at 13:28
  • $\begingroup$ No. I do not read german, but I suppose that this is a standard algorithm, which works only for the set of strategies of non-zero probability. That is, there is an initial wrong assumption that $q>0$ $\endgroup$ – Artem Mar 8 '13 at 13:32
  • $\begingroup$ www.coursera.org has Game Theory course where they explain how it works. $\endgroup$ – Artem Mar 8 '13 at 13:34
4
$\begingroup$

The reason this doesn't work is the same as the one I gave in this answer to this question of yours. Indifference must hold only between options that are assigned non-zero probabilities, and in the present case the strategies in the only Nash equilibrium assign zero probability to $S$, so there's no indifference between $S$ and $G$ at equilibrium.

That Wikipedia article is rather misleading in that, though it doesn't say so explicitly, it gives the impression that that algorithm can always be used to find a Nash equilbrium, whereas, as you've now twice confirmed, a mixed strategy supported on all pure strategies is in fact rather a special case. You can perhaps most easily see this by noting that no mixed strategy could ever cause your opponent to be indifferent between two options of which one is strongly dominated by the other.

$\endgroup$
  • $\begingroup$ yeah, same trap... jetzt hats klick gemacht $\endgroup$ – StefanH Mar 8 '13 at 19:35
2
$\begingroup$

What you've established is that, in this game, no player will ever be indifferent, no matter which (mixed or pure) strategy her opponent chooses.

The NE you already found is the only NE in this game. It's a pure-strategy equilibrium, which is a degenerate case of the mixed-strategy equilibria. The algorithm that you mention only works for non-degenerate mixed-strategy equilibria.

When it is stated, like above, that a mixed-strategy equilibrium always exists, invariably one implies that this might be a degenerate case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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