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…)