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 . Then Bob announces
and then Alice announces
. After these declaration are made, the game coordinator determines the winner: If
Alice wins. If
Bob wins. The set
, 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
.
Rabin gives an example for a game with the following propertie:
is a decidable set: this means that there is an effective way to decide, for every triple
whether or not
. 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.
- Bob has a winning strategy
: whatever actions
and
Alice chooses in the first and third stages, Bob will win the game if in the second stage he chooses
: so that
for any
- Bob has no computable winning strategy: For every function
that can be computed by a computer program there exist some actions
for Alice such that
.
Feel the blow ? Bob finds himself in a strange predicament. On the one hand, after observing Alice’s action from the first round, Bob knows that there is some action
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
, 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…)
15 comments
February 15, 2010 at 3:56 pm
Algorithmic Game Theory in 1957 « Algorithmic Game Theory
[…] Game Theory in 1957 Eran Shmaya posts about a beautiful demonstration from 1957 by Micahel Rabin of the twists that computation puts on […]
February 15, 2010 at 7:49 pm
dsz
Very interesting! What’s the reference to Rabin’s paper?
February 15, 2010 at 8:14 pm
Eran
`Effective computability of winning strategies’, Annals of Mathematics Studies 39.
February 15, 2010 at 11:37 pm
Eilon
I never read Rabin’s paper, and I do not know much about algorithmic game theory, but isn’t this the whole business of the encryption market? And therefore, instead of considering a three-stage game, one can consider a two-stage game: Alice sends a known message enrcypted by a known encryption method, and Bob has to come up with the key? By full enumeration Bob can find the key, and therefore win, but, provided the key is long enough, if the encryption method is sufficiently complex, there is no computationally efficient way to do it.
This leads us back to the literature on repeated games with boundedly rational players, about which I wrote several weeks ago: when the players have bounded rationality, the value may depend on their computational power. Plainly this applies to one-shot games: when each player is restricted to a subset of his strategies, the value in mixed strategies exists, but may differ from the value of the game when the players are not restricted. Moreover, in games with perfect information, the value in pure strategies need not exist, because, as you mention, the winning strategy need not be allowed for a player.
February 16, 2010 at 10:30 am
Eran
Rabin’s point is not that Bob doesn’t have an efficient algorithm to win, but that he has no algorithm at all.
There is some parallel between computational complexity and computability, though I don’t know if it can be formalized. At any rate, I think the game you suggested should in fairness also be cast as a three stage game: First Alice announces the encrypted message, then Bob guesses the key, then Alice announces the correct key. Without the third stage, you cannot verify that Alice did not `cheat’ by announcing a message that has no key at all
February 16, 2010 at 5:31 pm
Eilon
I probably do not understand the terminology: because the game is finite, Bob has an algorithm to win: enumerate over all possible strategies, and check each one to see whether it is the winning strategy. Slow, yes. Requires tons of memory, yes. But an algorithm nonetheless. I guess that what is true is that Bob does not have an algorithm that runs in a reasonable time, where “reasonable” is formalized by the CS guys.
February 16, 2010 at 5:52 pm
Eilon
Just one small thing, concerning the necessity of the third stage in the game, before I switch to the land of dreams. Suppose that Alice uses a 1-1 encryption method. That is, for each input “i” and each key “k” the method output an encrypted message “o”, such that for each input “i”, the function that maps keys to outputs is 1-1. Suppose also that the spaces of inputs, keys and outputs have the same size. Finally, suppose that given the input and output, it is difficult to find the key (I have the good old DES method in mind, though I am sure that better encryption methods exist now). Consider a game where in stage 1 Alice has to announce an input and its corresponding encrypted output, and in the second stage Bob has to announce the key used by Alice. Bob wins if he announces the correct key. If the encryption method is complex, Bob does not have a computable winning strategy (whatever this means), but he does have a non-computable winning strategy.
February 16, 2010 at 10:06 pm
Eran
`enumerate over all possible strategies, and check each one to see whether it is the winning strategy’ ?
there are uncountably many of them, and for each one there is an infinite set of possible responses for Alice
February 17, 2010 at 3:15 am
Eilon
I think that eventually even I see your point: the set of strategies is infinite, and therefore there is no finite-time algorithm that produces the winning strategy. It is not surprising that something like this can be done; after all, the set of strategies is infinite. But then I do not get the point that you try to make. That is, we have a theoretical result that says that winning strategies exist. If the game is complex, we may know who has a winning strategy, but we may not be able to compute a winning strategy efficiently (like in Hex). If the game is infinite, we may not be able to compute the winning strategy.
We live in a finite world. It contains so many particles, and unfortunately our game is bounded by so many years (or billions of years, if you consider longer games). Do infinite games exist at all, except of in our minds? And if they exist only in our minds, then the issue that you raise is irrelevant. We use infinite games to approximate finite games, to capture some specific properties of finite games that are easier to analyze in infinite games.
I tend to think that restricting players to bounded computational capacity is more relevant to applications than restricting them to computable strategies. Though mathematically both restrictions are equally exciting.
February 24, 2010 at 6:52 pm
Hai
That was a great demonstration! However, I still have a doubt…
It is on the computability of the design of the game. Did Robin show how to construct W (or in other words, the decision procedure for W) such that it has the three properties? If he only proved the existence of such a set but not how to construct it, the consequence of the demonstration is limited: economists may claim that nobody will see such a game.
February 24, 2010 at 9:10 pm
Eran
He constructed it, so essentially he gave the program that the job coordinator should use to decide who wins for every play path.
April 20, 2010 at 5:13 pm
Vladimir Nesov
What if we recognize that Alice’s strategy (of choosing a strategy based on Bob’s strategy) is also computable? Who gets to look at whose fixed strategy first?
April 21, 2010 at 9:54 pm
Eran
Not sure if I understand you correctly. The nice thing about this game is that if Alice gets to look at Bob’s strategy she can win the game (that is come up with a strategy that will give her victory) and if Bob gets to look at Alice’s strategy he can win the game.
April 22, 2010 at 2:46 am
Vladimir Nesov
What if they see each other’s source code at the start? It’s not quite the same thing as seeing each other’s strategy, as strategy has to be computed from the source code, and seeing just source code doesn’t in itself lead to any paradoxes. But they can’t both win.
July 4, 2011 at 1:31 pm
The Tel Aviv Workshop « The Leisure of the Theory Class
[…] mention another presentation, by Michael Rabin, whose 1957 paper about computability in game theory I will take with me to a desert island . Rabin presented a simple (“even financiers understood it”) scheme for conducting seal […]