Game Theory with Costly Computation
| dc.creator | Halpern, Joseph Y. | |
| dc.creator | Pass, Rafael | |
| dc.date | 2008-08-29 | |
| dc.date.accessioned | 2026-07-07T09:59:37Z | |
| dc.date.available | 2026-07-07T09:59:37Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/0809.0024 | |
| dc.identifier | http://arxiv.org/abs/0809.0024 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/168084 | |
| dc.subject | Computer Science and Game Theory | |
| dc.subject | Cryptography and Security | |
| dc.title | Game Theory with Costly Computation | |
| dc.type | text |