Computability of Nash Equilibrium

This is the most frustrating part in academic career: You come up with a cool idea, google around a bit for references, and discover that the Simpsons did it twenty years ago. It happened to Ronen and I recently when we were talking about computability of Nash equilibrium. Only thing left is to blog about it, so here we are.

A good starting point is the omitted paragraph from John Nash’ Thesis (scanned pdf), in which Nash motivates his new idea. The paragraph is not included in the published version of the thesis, it is not clear whether because of editorial intervention or Nash’ own initiative.

We proceed by investigating the question: What would be a rational prediction of the behavior to be expected of rational playing the game in question? By using the principles that a rational prediction should be unique, that the players should be able to deduce and make use of it, and that such knowledge on the part of each player of what to expect the others to do should not lead him to act out of conformity with the prediction, one is led to the concept of a solution defined before.

The `concept of a solution defined before’ is what every reader of this blog knows as Nash Equilibrium in mixed strategies. This paragraph is intriguing for several reasons, not the least of them is the fact, acknowledged by Nash, that Nash equilibrium of a game is not necessarily unique. This opens the door to the equilibrium refinements enterprise, which aims to identify the unique `rational prediction’: the equilibrium which the players jointly deduce from the description the game. The refinements literature seems to have gone out of fashion sometimes in the eighties (`embarrassed itself out’ as one prominent game theorist told me) without producing a satisfactory solution, though it is still very popular `in applications’.

Anyway, the subject matter of this post is another aspect of Nash’s argument, that the players should be able to deduce the prediction and make use of it. It is remarkable that Nash (and also von-Neumann and Morgenstern before him but I’ll leave that to another post) founded game theory not on observable behavior, as economics orthodoxy would have had it, but on unobservable reasoning process. How can we formally model reasoning process ? At the very least, the players should somehow contain the mixed strategies in their mind, which means that the strategies can be explicitly described, i.e that the real numbers that represent the probabilities of each actions are computable: Their, say, binary expansion should be the output of a Turing Machine. If this is the case then the player can also `make use’ of these mixed strategies: they have an effective way (that is, a computer program) that randomizes a strategy according to these strategies.

I hasten to say that while I refer to the agent’s mind, we must not be so narrow mindedly earth-bound as to assume our players are human beings. Our players might arrives from another planet, where evolution made a better job than what we see around us, or from another universe where the law of physics are different, or they may be the gods themselves. Species come and go, but concepts like rationality and reasoning — the subject matter of game theory — are eternal.

Well, Can the players contain the mixed strategies in their mind ? Are the predictions of game theory such that cognitive agents can reason about them and make use of them? Fortunately they are

Theorem 1 Every normal form game with computable payoffs admits a mixed Nash Equilibrium with computable mixed strategies.

My favorite way to see this is to using Tarski’s Theorem that real algebraic fields are elementary isomorphic (I also wrote about it here). Thus, Nash’s Theorem, being a first order statement, is also true in the field of computable real numbers.

The story does not ends here, though. Take another look at Nash’s omitted paragraph: Our players are not only supposed to be able to somehow hold the prediction in their minds and make use of it. They should also deduce it: Starting from the payoff matrix, one step after another, a long sequence of arguments, each following the previous one, should culminate in the `rational prediction’ of the game. You see where this leads: The prediction should be computable from the payoff matrix. Alas,

Theorem 2 There exists no computable function that get as input payoff matrix with computable payoffs and outputs a mixed Nash Equilibrium of the game.

Bottom line: Rational players can reason about and make use of Nash’s rational prediction, but they cannot deduce it. The prediction should somehow magically pop up in their minds. Here is a link to Kislaya Prasad’s paper where these theorems were already published.