You are currently browsing the tag archive for the ‘computability’ tag.

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.

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 ${S\subseteq\mathbb{N}}$ is simple if ${S}$ is recursively enumerable and its complement ${S^c}$ 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 ${S}$ and such that no computer program can produce infinitely many elements that are not in ${S}$. By the way, Post introduces the concept of simple set while working on his eponymous problem which Richard mentions. In fact, if ${S}$ is simple set then ${S}$ is not many-one equivalent to a universal recursively enumerable set.

Now let ${S}$ 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 ${n}$. Then Bob announces ${m}$ and then Alice announces ${t}$. After the game is played, a winner is determined as follows: Bob wins if ${m>n}$ and ${m}$ is not the ${t}$-th element in the enumeration of ${S}$. 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 ${n}$ that Alice might chose in the first round there exists some ${m>n}$ such that ${m\notin S}$, since the complement of ${S}$ 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 ${f:\mathbb{N}\rightarrow\mathbb{N}}$ that Bob can chose, there exists some ${m}$ such that either ${f(m)\leq m}$ or ${f(m)\in S}$ since otherwise ${f(0),f(f(0)),f(f(f(0))),\dots}$ would have been a recursive enumeration of infinitely many elements of ${S^c}$. In particular, there exists some ${t}$ such that if Alice plays ${m}$ in the first stage and ${t}$ in the third stage she wins against ${f}$. So, Bob has no winning strategy.

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 $f:\mathbb{N}\rightarrow\mathbb{N}$ 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