Relevance of memory in minority games

By considering diffusion on De Bruijn graphs, we study in detail the dynami cs of the histories in the minority game, a model of competition between ad aptative agents. Such graphs describe the structure of the temporal evoluti on 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 probabil ities are biased. Consequently, all quantities of the model do significantl y depend on whether the histories are real or uniformly and randomly sample d. We expose a self-consistent theory of the case of real histories, which turns out to be in very good agreement with numerical simulations.