Adaptive learning and \(p\)-best response sets. (English) Zbl 1233.91035

Summary: A product set of strategies is a \(p\)-best response set if for each agent it contains all best responses to any distribution placing at least probability \(p\) on his opponents’ profiles belonging to the product set. A \(p\)-best response set is minimal if it does not properly contain another \(p\)-best response set. We study a perturbed joint fictitious play process with bounded memory and sample and a perturbed independent fictitious play process as in [H. P. Young, Econometrica 61, No. 1, 57–84 (1993; Zbl 0773.90101)]. We show that in \(n\)-person games only strategies contained in the unique minimal \(p\)-best response set can be selected in the long run by both types of processes provided that the rate of perturbations and \(p\) are sufficiently low. For each process, an explicit bound of \(p\) is given and we analyze how this critical value evolves when \(n\) increases. Our results are robust to the degree of incompleteness of sampling relative to memory.


91A22 Evolutionary games
91A26 Rationality and learning in game theory


Zbl 0773.90101
Full Text: DOI


[1] Basu K, Weibull JW (1991) Strategy subsets closed under rational behavior. Econ Lett 36: 141–146 · Zbl 0741.90097
[2] Ellison G (2000) Basins of attraction, long-run stochastic stability, and the speed of step-by-step evolution. Rev Econ Stud 67: 17–45 · Zbl 0956.91027
[3] Harsanyi JC, Selten R (1988) A general theory of equilibrium selection in games. MIT Press Books, Cambridge, MA · Zbl 0693.90098
[4] Hurkens S (1995) Learning by forgetful players. Games Econ Behav 11: 304–329 · Zbl 0841.90126
[5] Kajii A, Morris S (1997) The robustness of equilibria to incomplete information. Econometrica 65: 1283–1309 · Zbl 0887.90186
[6] Klimm M, Sandholm T, Weibull JW (2010) Finding all minimal sCURB sets in finite games. Working Paper, Stockholm School of Economics
[7] Kojima F, Takahashi S (2008) p-Dominance and perfect foresight dynamics. J Econ Behav Organ 67: 689–701
[8] Maruta T (1997) On the relationship between risk-dominance and stochastic stability. Games Econ Behav 19: 221–234 · Zbl 0882.90132
[9] Matsui A, Matsuyama K (1995) An approach to equilibrium selection. J Econ Theory 65: 415–434 · Zbl 0835.90121
[10] Monderer D, Sela A (1997) Fictitious play and no-cycling conditions. Working Paper, The Technion
[11] Morris S, Rob R, Shin HS (1995) p-Dominance and belief potential. Econometrica 63: 145–157 · Zbl 0827.90138
[12] Morris S, Ui T (2005) Generalized potentials and robust sets of equilibria. J Econ Theory 124: 45–78 · Zbl 1100.91004
[13] Oyama D, Takahashi S, Hofbauer J (2008) Monotone methods for equilibrium selection under perfect foresight dynamics. Theor Econ 3: 155–192
[14] Tercieux O (2006a) p-Best response set. J Econ Theory 131: 45–70 · Zbl 1142.91345
[15] Tercieux O (2006b) p-Best response sets and the robustness of equilibria to incomplete information. Games Econ Behav 56: 371–384 · Zbl 1177.91019
[16] Young HP (1993) The evolution of conventions. Econometrica 61: 57–84 · Zbl 0773.90101
[17] Young HP (1998) Individual strategy and social structure. An evolutionary theory of institutions. Princeton University Press, Princeton
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.