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

## 2 comments

February 16, 2010 at 5:44 pm

EilonI think that game theory came from an attempt to understand or explain human (and non-human) behavior. But real life is quite complex, much more than our poor mathematical tools and limited minds allow us to analyze. So we make simplifications. We assume that decision makers satisfy von-Nuemann and Morgenstern’s axioms of utility, so that we can easily use mixed strategies. We assume that the game is common knowledge, so that we do not have to deal with infinite hierarchies of beliefs. And, among other things, we assume that the players are rational, so that we do not have to take into account bounded computational capacity. Your critique about the validity of the last assumption is in place, but it is not different than criticism about quite a few other implicit assumptions that we assume when we analyze games.

But then, to study the effects of bounded computational capacity, there are people who study games played by automata or bounded recall strategies, and happily this strand of literature does not die.

February 16, 2010 at 10:25 pm

EranI believe there are several layers of miscommunication here so let me try to do a better job explaining myself (to my defense, this is the first time I write about computability)

First, I didn’t say anything about computational resources. When I say that a function is computable, I don’t mean anything about the time or memory resources that are required to compute the function. I just mean that there exists an algorithm that outputs f(n) where the input is n. you can think about a computer program in your favorite language, just don’t worry about its running time.

Second, I don’t care whether my players are realistic models of human beings. So even if human beings have, say, bounded memory, it doesn’t bother me for the purpose of this post.

Last, I wasn’t trying to criticize anything in my last statement. What I was trying to do is defend the restriction of strategies to computable functions. I claim that this is not an arbitrary restriction but in fact a natural requirement if you subscribe to von-Neumann and Morgenstern’s view of a strategy as a contingent plan that the player creates in his mind. Such a plan should consist of a set of instruction that tells him what to do under any circumstance. In other words, it must be an algorithm