On the Evolution of Memory Size in the Minority Game (extended abstract)

1 Introduction

This work presents a study on the effects of different memory sizes in the Minority Game (MG) market model [Zhang, 1998]. We analyse the effects on an agent's performance when this agent is endowed with a different memory size with respect to other agents in the game. Our aim is to identify in which situations a large or small memory might be advantageous in the game. From the obtained results we argue that there exist convergence to and evolutionary stability around certain memory sizes and we consider an evolutionary setup which confirms our hypothesis.

The MG is defined as an odd number of agents (N) which must choose at each turn of the game whether they will be in one of two possible groups. After all agents have made their choices, agents in the minority group are rewarded. In order to make a decision, agents use an inductive learning algorithm in order to try to exploit patterns from previous outcomes. The number of past turns that agents consider to decide defines their memory size (M).

One of the main properties in a MG is its efficiency, which is evaluated by the statistical variance (σ2 ) of the number of agents in a group [Moro, 2004]. Efficiency is known to be a function of a control parameter α = 2M N [Manuca et al., 2000]. For N fixed, M becomes the main control parameter of the game. Figure 1 shows σ2 for a range of memory sizes. Three regions are observed: (i) for small M variance is very high, above the expected for the random case game (which we will call inefficient region); (ii) for high values of M, variance is exactly the one expected for the random case game (random case region); (iii) for intermediate M the system presents small variances (efficient region).

2 Memory Size and Performance

Firstly, we tackle the design aspects of agents by asking what is the best memory size for an agent immersed in a MG where agents have a different memory size. We do so by modifying the typical MG setup, defining two basic elements: (i) the environment, a classical MG with an even number (N) of agents; (ii) a target-agent endowed with a possibly different memory size (m) from that in the environment. We have simulated different target-agents within environments in all 3 efficiency regions, taking N as a large value, so that the target-agent plays no role in the determination of the game's exploit the environment. Interestingly, the same experiment repeated having m = M - 1 shows that smaller memories makes no difference to the target-agent's performance, it becomes the same as the environment's average.

3 Evolution of memory size

Now we apply our results in an evolutionary setup, in a MG where mutant agents - endowed with slightly different memory sizes - may appear and replace badly performing agents. Let the system be initially in an inefficient phase. Our experiments have shown that an agent with a larger memory would be able to exploit the environment in this region while smaller memories provide no benefits. Thus, agents with larger memories would be able to survive and average memory size would increase until the point where further increases lead to no gains. This happens when the system enters the efficient region. M0 denotes the memory size in which the system first becomes efficient. The system cannot move beyond M0, as larger memories would cause harm to the mutant's performance. In addition, the system cannot move towards lower memory sizes: whenever a sufficient number of agents convert to smaller memories, the system would again be in an inefficient region and the push towards larger memories would reappear.

A similar reasoning might be applied to a MG starting at any point M in the efficient region, above or equal to M0.

Figure 4: Gain of a target-agent with m=M+1.

A mutant agent with larger memory would be penalized, but one with smaller memory would perform just as well and we could expect that memory sizes would end up being distributed throughout values below M. However, this would result in a reduction of the average memory size, causing the system to move towards the inefficient region and making larger memories harmful, thus creating a new upper limit in memory size. The process continues until M0 is reached.

We may say that M0 is not only evolutionary stable, as no mutant agent can do better than the agents already in the environment at this point, but it is also an attractor of memory sizes in the efficient and inefficient regions. By starting in any point in these regions, the system is expected to converge to M0. This reasoning was indeed confirmed by simulations. However we did not have a convergence towards M0 = 4 as it would be expected by analysing the traditional MG (see Fig. 1). We have observed an initial "arms race" of memory sizes up to M = 4 and then a fall towards a final equilibrium at M = 1. This may be explained if we consider that two adaptations happen, adaptation of memory size and adaptation of strategies, for when an agent modifies her memory size she also modifies her strategies. Since the strategies space is much larger than the memory sizes space, adaptation of the latter is faster. Thus, at the beginning of the simulation we indeed have M0 = 4 and, as strategies adapt, a different dynamics emerge [Ara´ujo and Lamb, 2004], with a different value of M0.

Acknowledgments: This work was partly supported by CAPES, CNPq and FAPERGS, Brazil.