Game Theory with Costly Computation

Details Game Theory with Costly Computation Game Theory with Costly Computation

2008-08-29

arxiv.org/abs/0809.0024v1

Computer Science

Computer Science and Game Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Game Theory with Costly Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Game Theory with Costly Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Game Theory with Costly Computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-613357