Bounding Rationality by Discounting Time

Lance Fortnow and Rahul Santhanam

No 1481, Discussion Papers from Northwestern University, Center for Mathematical Studies in Economics and Management Science

Abstract: 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 E-Nash equilibria.

Keywords: Bounded rationality; Discounting; Uniform equilibria; Factoring game (search for similar items in EconPapers)
JEL-codes: C72 D58 (search for similar items in EconPapers)
Date: 2009-11-16
New Economics Papers: this item is included in nep-evo, nep-gth, nep-hpe and nep-upt
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://people.cs.uchicago.edu/~fortnow/papers/factor.pdf main text (application/pdf)
Our link check indicates that this URL is bad, the error code is: 403 Forbidden

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nwu:cmsems:1481

Ordering information: This working paper can be ordered from

Access Statistics for this paper

More papers in Discussion Papers from Northwestern University, Center for Mathematical Studies in Economics and Management Science Center for Mathematical Studies in Economics and Management Science, Northwestern University, 580 Jacobs Center, 2001 Sheridan Road, Evanston, IL 60208-2014. Contact information at EDIRC.
Bibliographic data for series maintained by Fran Walker ( this e-mail address is bad, please contact ).