An interesting read: The Myth of the Folk Theorem

Warning: Lots of numbers and mathematical terms involved = nosebleed!

It’s an interesting read. I’m not fond of mathematics but there are times when I do find the numbers quite interesting. This is one of those moments. I got this pdf file from the folks at Microsoft research, thanks to Dana Boyd’s blog.

Here’s the abstract:

A well-known result in game theory known as “the Folk Theorem” suggests that finding Nash equilibria in repeated games should be easier than in one-shot games. In contrast, we show that the problem of finding any (approximate) Nash equilibrium for a three-player infinitely repeated game is computationally intractable (even when all payoffs are in {?1, 0,?1}), unless all of PPAD can be solved in randomized polynomial time. This is done by showing that finding Nash equilibria of (k + 1)-player infinitely-repeated games is as hard as finding Nash equilibria of k-player one-shot games, for which PPAD-hardness is known (Daskalakis, Goldberg and Papadimitriou, 2006; Chen, Deng and Teng, 2006; Chen, Teng and Valiant, 2007). This also explains why no computationally-efficient learning dynamics, such as the “no regret” algorithms, can be rational (in general games with three or more players) in the sense that, when one’s opponents use such a strategy, it is not in general a best reply to follow suit.

If you’re from the social sciences and interested in learning more about the game theory then this might help. It’s not an easy reading because of the terminologies and the complex mathematical concepts involved… so be warned. :)

Download:The myth of Folk theorem