  We develop a general game-theoretic framework for reasoning about strategic
agents performing possibly costly computation. In this framework, many
traditional game-theoretic results (such as the existence of a Nash
equilibrium) no longer hold. Nevertheless, we can use the framework to provide
psychologically appealing explanations to observed behavior in well-studied
games (such as finitely repeated prisoner's dilemma and rock-paper-scissors).
Furthermore, we provide natural conditions on games sufficient to guarantee
that equilibria exist. As an application of this framework, we consider a
notion of game-theoretic implementation of mediators in computational games. We
show that a special case of this notion is equivalent to a variant of the
traditional cryptographic definition of protocol security; this result shows
that, when taking computation into account, 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
related.
