Suppose you have a simple 2x2 simultaneous game of the sort that is described in all textbooks on game theory. This game may well have mixed strategy Nash equilibria. The algorithm to compute their probability distributions is simple: It is a feature of Nash equilibria that if one player plays the Nash strategy, then the other player becomes indifferent as to their own respective options. So if you assume that player A plays the available strateges A1 and A2 with probabilities p and (1-p), you can calculate player B’s expected payoffs for B’s respective options B1 and B2 as a function of p: For B1 it will be B’s payoff for A1/B1 multiplied by p plus B’s payoff for A2/B1 multiplied by (1-p); for B2 it will be B’s payoff for A1/B2 multiplied by p plus the payoff for A2/B2 multiplied by (1-p). In a Nash equilibrium, B’s payoffs for B1 and B2 must be equal, so you put a = between the two and solve the resulting equation for p. Likewise, to get the probability distribution q and (1-q) for player B, you express A’s expected payoffs for options A1 and A2 as a function of q, equate A1 and A2, and solve for q.
There are cases when this method produces results that are plainly garbage, such as negative probabilities. I suppose there are other cases when the results are not evidently implausible but still wrong. What are the criteria under which the algorithm becomes inapplicable? It can’t be the presence of a pure strategy Nash equilibrium, since it’s perfectly possible for a game to have both pure and mixed strategy equilibria.
Do you have an example of a payoff matrix where a Nash equilibrium is “wrong”? I assume you know that a Nash equilibrium is not necessarily stable. One will exist, though, not involving negative probabilities or anything like that.
It’s not that the equilibrium itself is wrong, it’s that the algorithm for finding it is. An example is the following game:
B1 B2
A1 5 8
A2 6 7
(With these being the payoffs for the row player; let’s assume it’s zero sum, so the payoffs for the column player are the corresponding negatives)
The algorithm above will give a probability of -0.5 for A1 and 0.5 for B1. I suppose this is because there is strict dominance in this game (of B1 over B2), but I wonder if strict dominance (or perhaps only weak dominance?) is a necessary or sufficient condition for the algorithm to become inapplicable.
This seems analogous to finding minimums of f(x) for restricted regions - the algorithm for finding a minimum is setting the derivative to zero and solving for x. But this fails if the question is "find the minimum of x*x over the range from 1 to 2. The solution from the derivative is (of course) x=0, but that’s outside the acceptable range. So you need to recognize that the derivative solution is not applicable, and examine the function at the limits of the range (x=1 and x=2). Once you do that, you find that the answer is x=1. In the example you provide, the implicit limits are that p1 and p2 are between zero and 1. When you come up with an answer of less than zero or more than 1, you need to reject those bogus solutions and look at p=0 and p=1, which tells you that the right answer is to always choose B2. But I’m working from analogy, here (it’s been several years since I did any game theory), so I may be talking out of my hat.
Nash was quoted as deriding people who steal ideas. First described in Le Chatelier’s principle … Le Chatelier’s equilibria…
I think its only when you have a situation that is suitably stable… self-stabilising, as in Le Chatelier’s principle, that you have sensible p’s and q’s. Nash does help guide you through the murky waters of the less table and unstable cases… but only helps… At least you know when its going chaotic.
Engineers do Bode plots, computer programmers do fractals showing chaos… same thing really
negative has poles on the right, very unstable.
It seems that the inequalities are not just incidental in this type of problem; we always have to worry about them. So, even before enumerating everything that can happen even in the 2×2 case, we see that solving linear equations as described in the OP does not “fail”, rather part of the correct algorithm is to check that the solution is non-negative and therefore represents a probability distribution.
Note that a matrix game can be degenerate. Beyond that, you need to check pure strategies, and for the case in the OP the constraint that p,\,q\ge0, and that no player can do better by deviating, i.e., Nash’s best response condition. The OP “algorithm” is only part of a correct algorithm to output all Nash equilibria.