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 ${n}$. Then Bob announces ${m}$ and then Alice announces ${t}$. After these declaration are made, the game coordinator determines the winner: If ${(n,m,t)\in W}$ Alice wins. If ${(n,m,t)\notin W}$ Bob wins. The set $W$, 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 ${W}$.

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

1. ${W}$ is a decidable set: this means that there is an effective way to decide, for every triple ${(n,m,t)}$ whether or not ${(n,m,t)\in W}$. 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 ${f:\mathbb{N}\rightarrow\mathbb{N}}$: whatever actions ${n}$ and ${t}$ Alice chooses in the first and third stages, Bob will win the game if in the second stage he chooses ${f(n)}$: so that $(n,f(n),t)\notin W$ for any $n,t\in \mathbb{N}$
3. Bob has no computable winning strategy: For every function ${f:\mathbb{N}\rightarrow\mathbb{N}}$ that can be computed by a computer program there exist some actions ${n,t}$ for Alice such that ${(n,f(n),t)\in W}$.

Feel the blow ? Bob finds himself in a strange predicament. On the one hand, after observing Alice’s action ${n}$ from the first round, Bob knows that there is some action ${m}$ 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 ${n}$, 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…)