Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/59644 
Erscheinungsjahr: 
2009
Schriftenreihe/Nr.: 
Discussion Paper No. 1481
Verlag: 
Northwestern University, Kellogg School of Management, Center for Mathematical Studies in Economics and Management Science, Evanston, IL
Zusammenfassung: 
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 o-Nash equilibria.
Schlagwörter: 
bounded rationality
discounting
uniform equilibria
factoring game
Dokumentart: 
Working Paper

Datei(en):
Datei
Größe
160.62 kB





Publikationen in EconStor sind urheberrechtlich geschützt.