Cornell University
Game Theory with Costly Computation
Tuesday, May 6, 4:15pm
Unusual LOCATION: 32-G449 (Kiva)
[refreshments at 3:45pm in 32-G5]
We develop a general game-theoretic framework for reasoning about
strategic agents performing possibly costly computation. Using this
framework, we provide a game-theoretic definition of protocol
security
that takes both computation and incentives into account.
We show that a special case of the definition is equivalent to a
variant of
precise zero-knowledge (Micali and Pass, STOC'06). This result shows
that the two approaches used for dealing with "deviating" players
in two
different communities---Nash equilibrium in game theory, and
zero-knowledge
"simulation" in cryptography---are intimately connected; indeed,
they are
essentially equivalent in the context of secure computation.
Prior knowledge of game theory or cryptography is not assumed.
Joint work with Joseph Halpern.
Host: Silvio Micali