Bounding Rationality by Discounting Time

Lance Fortnow, Rahul Santhanam

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 equilibrium where 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 ∈-Nash equilibria.
Original languageEnglish
Title of host publicationInnovations in Computer Science - ICS 2010
Place of PublicationTsinghua University, Beijing, China
PublisherTsinghua University Press
Pages143-155
Number of pages13
ISBN (Print)978-7-302-21752-7
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'Bounding Rationality by Discounting Time'. Together they form a unique fingerprint.

Cite this