Game Theory with Costly Computation
Speaker: Rafael Pass , Cornell University
Date: May 6 2008
Time: 4:15PM to 5:30PM
Location: 32-G449 (Kiva)
Host: Silvio Micali, MIT
Contact: Alexandr Andoni, 617 253 6182, andoni@mit.edu
Relevant URL: http://theory.csail.mit.edu/theory-seminars/calendar.html[Please note the UNUSUAL LOCATION, 32-G449.]
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.
See other events that are part of Theory Colloquium Spring 2008
See other events happening in May 2008
