Bounding Rationality by Discounting Time

Details Bounding Rationality by Discounting Time Bounding Rationality by Discounting Time

2009-11-16

arxiv.org/abs/0911.3162v1

Computer Science

Computer Science and Game Theory

To appear in Proceedings of The First Symposium on Innovations in Computer Science

Scientific paper

Consider a game where Alice generates an integer and Bob wins if he can factor that integer. Traditional game theory tells us that Bob will always win this game even though in practice Alice will win given our usual assumptions about the hardness of factoring. We define a new notion of bounded rationality, where the payoffs of players are discounted by the computation time they take to produce their actions. We use this notion to give a direct correspondence between the existence of equilibria where Alice has a winning strategy and the hardness of factoring. Namely, under a natural assumption on the discount rates, there is an equilibriumwhere Alice has a winning strategy iff there is a linear-time samplable distribution with respect to which Factoring is hard on average. We also give general results for discounted games over countable action spaces, including showing that any game with bounded and computable payoffs has an equilibrium in our model, even if each player is allowed a countable number of actions. It follows, for example, that the Largest Integer game has an equilibrium in our model though it has no Nash equilibria or epsilon-Nash equilibria.

Affiliated with

Also associated with

No associations

Rating

Bounding Rationality by Discounting Time 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 Bounding Rationality by Discounting Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounding Rationality by Discounting Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-649391