title: Relevance of memory in minority games
abstract: By considering diffusion on De Bruijn graphs, we study in detail the dynamics of the histories in the minority game, a model of competition between adaptative agents. Such graphs describe the structure of the temporal evolution of M bit strings, each node standing for a given string, i.e., a history in the minority game. We show that the frequency of visit of each history is not given by 1/2(M) in the limit of large M when the transition probabilities are biased. Consequently, all quantities of the model do significantly depend on whether the histories are real or uniformly and randomly sampled. We expose a self-consistent theory of the case of real histories, which turns out to be in very good agreement with numerical simulations.
authors.affiliation: Institut de Physique Theorique, Universite de Fribourg, CH-1700 Fribourg, Switzerland.
authors.initials: D
authors.lastname: Challet
authors.initials: M
authors.lastname: Marsili