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.

A post on Rabin

I wrote some time ago about Michael Rabin’s example of how a backward induction argument is killed when you require players’ plans to be computable. Since Rabin’s paper is not available online, I intended to post the proof at some point, but never actually got to do it. Richard Lipton’s post about Emil Post is a good inspiration to pay that debt since the concept of simple set, which was introduced by Post, has a role in Rabin’s example.

A set is simple if is recursively enumerable and its complement is infinite and contains no infinite recursively enumerable subset.

For Rabin’s purpose, what matters is that Post proved the existence of such a set. So Post provides us with a code of a computer program that enumerates over all the elements of and such that no computer program can produce infinitely many elements that are not in . By the way, Post introduces the concept of simple set while working on his eponymous problem which Richard mentions. In fact, if is simple set then is not many-one equivalent to a universal recursively enumerable set.

Now let be a simple set and consider the following three-round game with perfect information. At each round a player announces a natural number (an action): First Alice announces . Then Bob announces and then Alice announces . After the game is played, a winner is determined as follows: Bob wins if and is not the -th element in the enumeration of . Otherwise, Alice wins. Therefore, determining the winner is a task that can be effectively done using the code provided by Post.

Does any of the players have a strategy that guarantee winning regardless of how the opponent play ? The answer to this question depends on which mathematical creature you use to model the intuitive notion of `strategy’.

If by a strategy you mean just a function from histories to current action then Bob has a winning strategy: for every that Alice might chose in the first round there exists some such that , since the complement of is infinite.

But if you think of a strategy as a complete set of instructions, that is a plan or an algorithm that will tell you how to produce your next action given the past, then you want to model a strategy as a computable function. Now, for every computable function that Bob can chose, there exists some such that either or since otherwise would have been a recursive enumeration of infinitely many elements of . In particular, there exists some such that if Alice plays in the first stage and in the third stage she wins against . So, Bob has no winning strategy.

Describing distributions

What does it mean to describe a probability distribution over, say, ? I am interested in this question because of the expert testing literature (pdf), in which an expert is supposed to provide a client with the distribution of some stochastic process, but the question is also relevant for Bayesiansts, at least those of us who think that the Bayesian paradigm captures (or should capture) the reasoning process of rational agents, in which case it makes little sense to reason about something you cannot describe.

So, what does it mean to describe your belief/theory about a stochastic process with values in ?  Here are some examples of descriptions:

are I.I.D with .

and

where are I.I.D .

Everyone agrees that I have just described processes, and that the first and last are different descriptions of the same process. Also everyone probably agrees that there are only countably many processes I can describe, since every description is a sentence in English/Math and there are only countably many such sentences.

Are players Turing Machines ?

Yes, some would answer, since the cognitive and physical processes that take place in my mind/body/whatever  while I make decisions or choose actions can be simulated by a computer program.

Even if we accept this assertion as true, I find the argument unsatisfactory. For me, the subject matter of game theory and decision theory is the idea of rationality, not the lousy shadow of rationality that evolved in my neighbourhood. When I come across all sort of dumb things people do, my response is `So what ?’  Why should we redo our theory of rationality to accommodate the petty goings-on of a bunch of talking monkeys on a mostly harmless planet in the middle of nowhere ?

So, the fact that human beings happen to be walking computers doesn’t mean players are also  computers.

And yet, even if like me you don’t think of your players as models for human beings, I still believe you may want to consider computability of their strategies. My reason is that game theory traditionally studies not only rational behavior but also the more vague notion of rational reasoning:

Imagine each player instead of making each decision as the necessity for it arises, makes up his mind in advance for all possible contingencies; i.e. that the player begins to play with a complete plan which specifies what choices he will make in every possible situation …. We call such a plan a strategy. (von-Neumann and Morgenstern, Section 11.1)

Back to Rabin’s game that I talked about yesterday. Even if we accept the existence of the function that appears in the second item as a  mathematical entity, such a function presents a `plan’ that cannot, even in principle, be executed, described, or reasoned about.

So I think a case can be made that by restricting our attention to computable functions we don’t arbitrarily restrict the player’s strategy set. On the contrary, the standard game theoretic formulation, by allowing non-computable functions, expands it to mathematical creatures that actually don’t capture our ideal concept of strategy

Computability in game theory

Since in the near future I will have to start advocating a computability argument, and since this position is somewhat in contrast to what was my view a couple of years ago when I first came across algorithmic game theory, I thought I should try to clarify my thoughts about the issue in a couple of posts.

The most beautiful example I know for the surprising outcomes we get when taking computability into account in game theory is Michael Rabin’s paper from 1957. Rabin considers a finite win-loss game with perfect information between two players, Alice and Bob. The game is played in three rounds, at each round a player announces a natural number (an action): First Alice announces . Then Bob announces and then Alice announces . After these declaration are made, the game coordinator determines the winner: If Alice wins. If Bob wins. The set , Alice’s winning set, is part of the description of the games. This is a finite game, which can be solved by a background induction. By the so called Zermelo’s Theorem, the game is determined: One of the player has a winning strategy. The identity of the winner depends of course on .

Rabin gives an example for a game with the following propertie:

1. is a decidable set: this means that there is an effective way to decide, for every triple whether or not . So the job of the game coordinator in this game can be performed by a computer program. Games with effectively computable payoff are called actual games: These are the games that can actually be played.
2. Bob has a winning strategy : whatever actions and Alice chooses in the first and third stages, Bob will win the game if in the second stage he chooses : so that for any
3. Bob has no computable winning strategy: For every function that can be computed by a computer program there exist some actions for Alice such that .

Feel the blow ? Bob finds himself in a strange predicament. On the one hand, after observing Alice’s action from the first round, Bob knows that there is some action he can choose that beats any possible response of Alice. However, if Bob tries to `plan ahead’ which action to take after every possible choice of , he cannot produce such a plan. Bob can beat all Alice’s strategies and Alice can beat all Bob’s (computable) strategies. von-Neumann and Morgenstern’s least controversial idea, solving a zero-sum game with perfect information by backward induction, trembles. The argument that in finite zero-sum games with perfect information a player doesn’t care if the opponent finds out his strategy falls apart.

(To be continued…)