Abstract
This paper considers the condition of perfect recall for the class of arbitrarily large discrete extensive form games. The known definitions of perfect recall are shown to be equivalent even beyond finite games. Further, a qualitatively new characterization in terms of choices is obtained. In particular, an extensive form game satisfies perfect recall if and only if the set of choices, viewed as sets of ultimate outcomes, fulfill the “Trivial Intersection” property, that is, any two choices with nonempty intersection are ordered by set inclusion.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Definition 1 is equivalent to the concept of discrete game tree in Definition 5 of Alós-Ferrer and Ritzberger (2013) plus the property that \(\left\{ w\right\} \in N\) for all \(w\in W\), which is called completeness in that work and can be assumed without loss of generality (Alós-Ferrer and Ritzberger 2013, Proposition 4).
Even though the same symbol serves for the map and its codomain, no confusion can arise, because the argument will always be specified.
If perfect recall were defined as a property of player i’s choice set alone, as it is possible, the first quantifier could be dropped.
Not all violations of no-absent-mindedness contradict the basic idea of choice, i.e. condition (DEF1). Example 15 of Alós-Ferrer and Ritzberger (2005) gives a two-player game violating no-absent-mindedness which fulfills (DEF1) and fails (DEF2) instead.
References
Alós-Ferrer C, Ritzberger K (2005) Trees and decisions. Econ Theory 25(4):763–798
Alós-Ferrer C, Ritzberger K (2008) Trees and extensive forms. J Econ Theory 43(1):216–250
Alós-Ferrer C, Ritzberger K (2013) Large extensive form games. Econ Theory 52(1):75–102
Alós-Ferrer C, Ritzberger K (2016a) Equilibrium existence for large perfect information games. J Math Econ 62:5–18
Alós-Ferrer C, Ritzberger K (2016b) Characterizing existence of equilibrium for large extensive form games: a necessity result. Econ Theory. doi:10.1007/s00199-015-0937-0
Alós-Ferrer C, Ritzberger K (2016c) Does backwards induction imply subgame perfection? Games Econ Behav. doi:10.1016/j.geb.2016.02.005
Aumann RJ (1964) Mixed and behavior strategies in infinite extensive games. In: Advances in game theory, Princeton University Press. Ann Math Study 52:627–650
Aumann RJ (1961) Borel structures for function spaces. Ill J Math 5:614–630
Kuhn H (1953) Extensive games and the problem of information. In: Kuhn H, Tucker A (eds) Contributions to the Theory of Games, vol II. Princeton University Press, Princeton
Osborne MJ, Rubinstein A (1994) A course in game theory. The MIT Press, Cambridge
Perea A (2001) Rationality in extensive form games. Theory and decision library, series C, vol 29. Kluwer Academic Publishers, Boston
Piccione M, Rubinstein A (1997) On the interpretation of decision problems with imperfect recall. Games Econ Behav 20:3–24
Ritzberger K (1999) Recall in extensive form games. Int J Game Theory 28:69–87
Ritzberger K (2001) Foundations of non-cooperative game theory. Oxford University Press, Oxford
Schwarz G (1974) Ways of randomizing and the problem of their equivalence. Isr J Math 17:1–10
Selten R (1975) Reexamination of the perfectness concept for equilibrium points in extensive games. Int J Game Theory 4:25–55
von Neumann J, Morgenstern O (1944) Theory of games and economic behavior. Princeton University Press, Princeton
von Stengel B (2002) Computing equilibria for two-person games. In: Aumann RJ, Hart S (eds) Handbook of game theory, vol 3. Elsevier, Amsterdam, pp 781–799
Wichardt PC (2008) Existence of Nash equilibria in finite extensive form games with imperfect recall: a counterexample. Games Econ Behav 63(1):366–369
Acknowledgments
We thank Bernhard von Stengel, an associate editor, and an anonymous referee for helpful comments which helped improve the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
We gratefully acknowledge financial support from the German Research Foundation (DFG) and the Austrian Science Fund (FWF) under Projects Al-1169/1 and I 1242-G16, respectively.
Rights and permissions
About this article
Cite this article
Alós-Ferrer, C., Ritzberger, K. Characterizations of perfect recall. Int J Game Theory 46, 311–326 (2017). https://doi.org/10.1007/s00182-016-0534-x
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-016-0534-x