Rafael Pass
ABSTRACT
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 develop a definition of protocol security relying on game-theoretic notions of implementation. We show that a natural special case of this definition 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.
Index Terms
- Game theory with costly computation: formulation and application to protocol security
Recommendations
Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computingWe study k-resilient Nash equilibria, joint strategies where no member of a coalition C of size up to k can do better, even if the whole coalition defects. We show that such k-resilient Nash equilibria exist for secret sharing and multiparty computation, ...
Discovering theorems in game theory: Two-person games with unique pure Nash equilibrium payoffs
In this paper we provide a logical framework for two-person finite games in strategic form, and use it to design a computer program for discovering some classes of games that have unique pure Nash equilibrium payoffs. The classes of games that we ...
Discovering theorems in game theory: two-person games with unique pure nash equilibrium payoffs
IJCAI'09: Proceedings of the 21st International Joint Conference on Artificial IntelligenceIn this paper we provide a logical framework for using computers to discover theorems in two-person finite games in strategic form, and apply it to discover classes of games that have unique pure Nash equilibrium payoffs. We consider all possible ...
Comments