At 1:42 AM 7/30/96, Wei Dai wrote:
I agree with Tim that game theory is very interesting and a potentialy useful tool in cryptography. However, game theory currently has a major ... I have not read any of Schelling's work, but the notion of Schelling points seems to be closely connected to that of equilibria in game theory. If this is the case, then I don't see how it can be usefully applied to the complex interactions of an entire society. It is easy to say that current social conventions are an equilibrium in some game, but how much is this worth? What we would like to know is what is the entire set of possible equilibria, why we are in one of them (instead of the others), and how changes in the game (such as introduction of strong crypto) change that set. I find it unlikely that game theory will soon advance to such a state that it will give us the answers to these questions. ... P.S. Now that I've reread Tim's original messages, I realize that maybe Schelling points are not really the equilibria of game theory. If this is the case, Tim, can you please clarify its actual meaning? (Perhaps by quoting a definition from Schelling's book?)
I certainly make no grandiose claims that any _single_ facet of reality is guaranteed to be useful, as I'm sure Wei Dai would agree. I presented the theory of Schelling points because I've found the notion to be interesting, unifying, and helpful in my understanding of many phenomena. (Clearly, there are dozens or even hundreds of such "core concepts.") Schelling was addressing a different aspect of game theory than conventional equilibria (as in payoffs, I presume to be Wei's emphasis). The David Friedman paper I cited the URL for (http://www.best.com/~ddfr/Academic/Property/Property.html) has a fuller explanation of Schelling points than I can justify writing here. He writes: "Such an outcome, chosen because of its uniqueness, is called a Schelling point, after Thomas Schelling who originated the idea. It provides a possible solution to the problem of coordination without communication. As this example shows, it is relevant both to situations where communication is physically impossible and to situations where communication is impossible because there is no way that either party can provide the other with a reason to believe that what he says is true." My conjecture that game theory and cryptography have some natural and fruitful points of intersection is of course just a conjecture. I have long believed--though I cannot formally prove it--that many of the problems with digital cash and related ideas are "made to converge" by consideration of iterated games, e.g., reputations, expectations, expected payoffs, and so forth. I believe we see this in the "real world," where economies actually work in ways that the pure theory (absent game theory) would suggest problems. --Tim May Boycott "Big Brother Inside" software! We got computers, we're tapping phone lines, we know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Licensed Ontologist | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."