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

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

Join 113 other followers

Follow

Get every new post delivered to your Inbox.

Join 113 other followers

%d bloggers like this: