Abstract
Aumann’s Rationality Theorem claims that in perfect information games, common knowledge of rationality yields backward induction (BI). Stalnaker argued that in the belief revision setting, BI does not follow from Aumann’s assumptions. However, as shown by Artemov, if common knowledge of rationality is understood in the robust sense, i.e., if players do not forfeit their knowledge of rationality even hypothetically, then BI follows. A more realistic model would bound the number of hypothetical non-rational moves by player i that can be tolerated without revising the belief in i’s rationality on future moves. We show that in the presence of common knowledge of rationality, if n hypothetical non-rational moves by any player are tolerated, then each game of length less than 2n + 3 yields BI, and that this bound on the length of model is tight for each n. In particular, if one error per player is tolerated, i.e., n = 1, then games of length up to 4 are BI games, whereas there is a game of length 5 with a non-BI solution.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Asheim, G.B.: On the epistemic foundation for backward induction. Mathematical Social Sciences 44, 121–144 (2002)
Artemov, S.: Robust knowledge and rationality. Technical Report TR-2010010, CUNY Ph.D. Program in Computer Science (2010)
Aumann, R.: Backward induction and common knowledge of rationality. Games and Economic Behavior 8, 6–19 (1995)
Baltag, A., Smets, S., Zvesper, J.A.: Keep “hoping” for rationality: A solution to the backward induction paradox. Synthese 169, 301–333 (2009); Knowledge, Rationality and Action, 705–737
Feinberg, Y.: Subjective reasoning: Dynamic games. Games and Economic Behavior 52, 54–93 (2005)
Ghosh, S., Meijering, B., Verbrugge, R.: Empirical reasoning in games: Logic meets cognition. In: Ågotnes, T., Alechina, N., Logan, B. (eds.) Proceedings Third Logics for Resource Bounded Agents Workshop (LRBA 2010), pp. 15–34 (2010)
Halpern, J.: Substantive rationality and backward induction. Games and Economic Behavior 37, 425–435 (2001)
Perea, A.: Epistemic game theory: Reasoning and choice. Cambridge University Press (2012)
Samet, D.: Hypothetical knowledge and games with perfect information. Games and Economic Behavior 17, 230–251 (1996)
Stalnaker, R.: Belief revision in games: forward and backward induction. Mathematical Social Sciences 36, 31–56 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Taşdemir, Ç. (2013). On Tolerance Analysis of Games with Belief Revision. In: Artemov, S., Nerode, A. (eds) Logical Foundations of Computer Science. LFCS 2013. Lecture Notes in Computer Science, vol 7734. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35722-0_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-35722-0_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35721-3
Online ISBN: 978-3-642-35722-0
eBook Packages: Computer ScienceComputer Science (R0)