Time Dependent Bounded Recall Strategies Are Enough to Play the Discounted Repeated Prisoners Dilemma
We show that for any discount factor, there is a natural number M such that all subgame perfect equilibrium outcomes of the discounted repeated prisoners dilemma can be obtained by subgame perfect equilibrium strategies with the following property: current play depends only on the number of the time-index and on the history of the last M periods. Therefore, players who are restricted to using pure strategies, have to remember, at the most, M periods in order to play any equilibrium outcome of the discounted repeated prisoners dilemma. This result leads us to introduce the notion of time dependent complexity, and to conclude that in the repeated prisoners dilemma, restricting attention to finite time dependent complex strategies is enough.
|Date of creation:||2004|
|Contact details of provider:|| Postal: Campus de Campolide, 1099-032 Lisboa|
Phone: (351) 21 3801638
Fax: (351) 21 3870933
Web page: http://www.fe.unl.pt
More information through EDIRC
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Neyman, Abraham, 1985. "Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma," Economics Letters, Elsevier, vol. 19(3), pages 227-229.
- Cole, Harold L. & Kocherlakota, Narayana R., 2005.
"Finite memory and imperfect monitoring,"
Games and Economic Behavior,
Elsevier, vol. 53(1), pages 59-72, October.
- Harold L. Cole & Narayana R. Kocherlakota, 2000. "Finite memory and imperfect monitoring," Working Papers 604, Federal Reserve Bank of Minneapolis.
- Harold L. Cole & Narayana R. Kocherlakota, 2001. "Finite memory and imperfect monitoring," Staff Report 287, Federal Reserve Bank of Minneapolis.
- Kalai, Ehud & Stanford, William, 1988. "Finite Rationality and Interpersonal Complexity in Repeated Games," Econometrica, Econometric Society, vol. 56(2), pages 397-410, March.
- Ehud Kalai & William Stanford, 1986. "Finite Rationality and Interpersonal Complexity in Repeated Games," Discussion Papers 679, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Rubinstein, Ariel, 1986. "Finite automata play the repeated prisoner's dilemma," Journal of Economic Theory, Elsevier, vol. 39(1), pages 83-96, June.
- Ariel Rubinstein, 1997. "Finite automata play the repeated prisioners dilemma," Levine's Working Paper Archive 1639, David K. Levine.
- Barlo, Mehmet & Carmona, Guilherme & Sabourian, Hamid, 2009. "Repeated games with one-memory," Journal of Economic Theory, Elsevier, vol. 144(1), pages 312-336, January. Full references (including those not matched with items on IDEAS)