Re: game theory

[tcmay@got.net (Timothy C. May)]

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."