Dynamical spin-glass-like behavior in an evolutionary game

We study a new evolutionary game, where players are tempted to take part by the premium, but compete for being the first who take a specific move. Those, who manage to escape the bulk of players, are the winners. While for large premium the game is very similar to the Minority Game studied earlier, significant new behavior, reminiscent of spin glasses is observed for premium below certain level.


I. INTRODUCTION
The transfer of physical ideas and procedures to traditionally social disciplines and a parallel backflow of inspiration for statistical physics from these disciplines play an increasing role in the last decade.
Among other applications, the field of econophysics [1,2] attracted much attention. An impotrant approach seems to be modelling the collective effect found in economic systems by assemblies of individually acting heterogeneous agents. One of the basic models is the Minority game [3,4], an evolutionary game which mimics the adaptive behavior of agents with bounded rationality, studied by W. B. Arthur in his El Farol bar problem [5].
In the Minority game, each player faces the choice between two possibitities, which can be buying or selling stock, entering or not a business, selecting first or second drive and so on. The winning side is that of the minority of players. Each player posesses a set of S ≥ 2 strategies. Each strategy collects its score, indicating the virtual gain of the player, if she had played that strategy all the time. At each round, the playes choose among their strategies the one with highest score. Such a sort of an on-line learning and agaptation leads to betterthan-random performance of the system as a whole. It was found, that the properties of the game depend on the memory length M and number of players N through the scaling variable α = 2 M /N [4,6,7]. The Minoriry game was thoroughly studied both numerically and analytically [8][9][10][11][12][13][14][15][16][17][18][19] along with the study of the original bar attendance problem [20,21] and various modifications of the Minority game [22][23][24][25][26][27][28][29] An important role is attributed to the observation that the dynamics of the memorized pattern and the strategies' scores are in certain regimes decoupled [30][31][32] and that the thermal noise can ge introduced in the players' decisions [33][34][35].
The Minority game is essentially symmetric. The players can choose between two sides, none of which is a priori preferred. The situation is somewhat different in the bar attendance model [20,21], where the optimal attendance is set from outside. There are also variants of thge game, in which the players can decide to participate or not, depending on their accumulated wealth [27,39]. The number of players who influence the outcome of the game can thus vary in time.
In this work we want to study a more abstract version of these models with variable number of players. We implement a scheme, in which the players struggle to be "ahead" of the other players, i. e. to come in before the others and not to stay if others have already left. This behavior is relevant in situations, where the early comers have advantage, irrespectively of what is the direction of the movement. We can think, for example, of a bunch of apes exploring a virgin land. The first animal coming to a place finds enough food, but much less is left for the followers. In an infinite space we could have stationary movement of the bunch in one dorection. When the space available is limited, frustration comes into play. The bunch should oscillate between the borderlines and no-one can steadily win. Our aim is to formalize and simulate this situation in a similar manner as the Minority game formalizes the inductive behavior.

II. ESCAPE GAME
We introduce a new mechanism, which leads to frustration in the agent's actions. Similarly to the Minority game, we have N agents. The agents can choose between two options: to participate (1) or not (0) in the business. If we denote a j ∈ {0, 1} the action of j'th player, the attendance is A = j a j . We measure the success of the j'th player by her wealth W j . The players who decide to participate can be either rewarded or punished by corresponding change in their wealth, while the wealth of non-participating agents remains unchanged.
There are two sources of the wealth change. First, there is a constant influx of wealth into the system, which we will call premium p. All participating players receive the amount p/A. Second, we reward the players, who by some means induce the others to follow them in the next step. If a player decided to participate in step t − 1 and the attendance rose from t − 1 to t (i. e. A(t) − A(t − 1) > 0), we consider that the player was "ahead" of their companions and gets a point. If, on the other hand the attendance decreased (i. e. A(t) − A(t − 1) < 0), the player is considered as "behind" and looses a point. If the attendance remains unchanged, no points are assigned. Thus, each player tries to "escape" the bulk of the other players. That is why we nicknamed the present dynamical multi-agent system "Escape game".
As in the Minority game, the record is kept about the past M changes of the attendance, There are two possibilities how to deal with the case when the attendance does not change. It is possible to attribute c = 0 to such a situation; then the state variable will have values from the set c ∈ {−1, 0, +1}. Alternatively, we can merge the cases of decrease and no change, so c = −1 also in the case when the attendance is constant. In this case we distinguish only two states, c ∈ {−1, +1}. We found, that both choices give qualitatively similar results, while the former one leads to slightly more demanding simulations. Therefore, throughout this article we we will investigate the latter choice, with two states only.
The agents look at the record µ ∈ {−1, +1} M . They have a set of S strategies (S = 2 in our simulations). The s-th strategy of the j-th player prescribes for the record µ the action a µ j,s ∈ 0, 1. For each strategy, the score is computed, which is the virtual gain of the player, if she played constantly that strategy. The update of the strategies' scores can be written as For the function G, weighting the attendance changes, we use the signum function, G(x) = sign(x). Note that the delivery of the player's gain is delayed: the action taken at time t − 1 can be rewarded anly at time t, so that it influences the scores at time t + 1. Again with close analogy to the Minority game, the actions the players take are prescribed by the strategies with highest score, a j = a j,sM , where s M denotes the most successfull strategy at the moment, U j,sM = max s U j,s .
To see clearly the points of difference from the Minority game, note first that in the Escape game the nonparticipation a j = 0 cannt change the wealth of the player. Second, the strategie's update rule (1) contains derivative of the attendance, not the attendance itself.

III. EVOLUTION OF ATTENDANCE AND GLASSY BEHAVIOR
Let us see qualitatively first, what is the time dependence of the attendance. We have found that for large enough premium the Escape game behaves in very similar manner to the Minority game. The attendance fluctuations decrease from its initial value until they stabilize at a stationary value. The average attendance is shifted from its random value N/2 above, as a response to the incentive, posed by the premium, for the payers to prefer presence over absence. We can see in Fig. 1 an example of such a behavior. The stationary state is reached in a short time (shorter than 10 5 steps for N = 200). The wealth of the most successful player grows constantly at high rate and also the average wealth slightly grows. This means, that due to the premium the game is a positivesum game on average. We can also observe the time dependence of the effective number of strategies per player e Σ . We define it through the average entropy of the usage of the strategies, where ν j,s is the time-averaged frequency of the usage of s-th strategy of j-th player. We performed the time averaging over a relatively short window using the exponential weighting, ν j,s (t) = (1 − λ)u j,s (t) + λν j,s (t − 1), where the usage index u j,s (t) = 1 if the player j used the strategy s at time t, and u j,s (t) = 0 otherwise. We used λ = 0.99, which corresponds to effective time-window width 100 steps.
We can see in Fig. 1 that the effective number of used strategies stabilizes at a value above but close to 1, which also corresponds well to the behavior of the Minority game in the symmetry-broken phase. On the other hand, we can observe significant change of the behavior of the model, if the premium is decreased below certain level. An example can be seen in Fig. 2. First, the transient time before the system settles in a stationary state is significantly larger (we observed, that it is nearly 10 6 steps). Then, we can see that periods with significant attendance fluctuations are alternating with periods with constant attendance, which can frequently last more than 10 4 steps. The fluctuating periods are characterized by decrease of the average wealth (the game is a negative-sum one) and effective number of strategies larger than 1. On the other hand, the periods of constant attendance exhibit nearly constant average wealth and effective number of strategies equal to 1. It means, that within the constant periods the system is able to find a favorable configuration, in which the game is globally effective (avoids the losses due to fluctuations) and everybody is stuck at single strategy. Moreover, there are many of such states: in different constant periods the attendance may differ considerably. This behavior is further pronounced when we diminish the premium even more. We can see such a behavior in Fig. 3. We can observe long periods (sometimes longer than 10 5 steps) of constant attendance, separated by very short fluctuating periods. The effective number of strategies differs from 1 only during these short periods. Again, there are many configurations in which the attendance does not change for long time.
The situation is reminiscent of spin glasses. In the spin glass behavior, there are many states, stable for long time, but mutually very different, in which the system can stay. If the bariers between these states are not infinite (which happens only in the fully connected case in thermodynamic limit), the dynamics of such a system is very similar to our Escape game: long periods of stasis within one state, interrupted by short periods coresponding to the jumps from one state to another. Therefore, we can describe the behavior with changing premium p as a kind of transition from "paramagnet" (high p) to "spin-glass" phase (low p). We have not studied in detail the phase diagram. However, we observed, that with fixed N the transition occurs at smaller p if the memory is longer.

IV. TIME-AVERAGED ATTENDANCE AND ITS FLUCTUATIONS
The response of the player's assembly to the premium was measured by the average attendance. Its dependence on the value of premium is shown in Fig. 4. As expected, it is an increasing function. We can see, that shorter memory leads to more strong response to the premium. The value of p at which the average attendance crosses its random value N/2 is smaller for shorter memory.  . The data are averaged over 50 independent runs. Each run was 10 6 steps long and the average was taken over 5 · 10 5 last steps. Where not shown, the error bars are smaller than symbol size.
The dependence of the attendance fluctuations σ 2 on p is shown in Fig. 5. Again, the dependence on p is more pronounced for shorter memory. The minimum, which is located around p = 3 for N = 200 is probably connected with the transition from the "paramagnet" to "spin-glass" phase: for low p the fluctuations are mainly due to rare but large jumps of the attendance from one quasi-static value to another. Indeed, we observed qualitatively that the transition occurs somewhat below the position of the minimum in σ 2 . . The data are averaged over 50 independent runs. Each run was 10 6 steps long and the average was taken over 5 · 10 5 last steps steps. Where not shown, the error bars are smaller than symbol size.
The memory dependence of attendence fluctuations for several valuer of p is presented in Fig. 6. In the minimum of fluctuations we recognize the same behavior as in the Minority game. Here, however, the position of the minimum depends strongly on the value of the premium. We can see, that the long-memory phase does not depend much on the premium. On the other hand, the crowded phase is strongly influenced by the premium. For smaller p the crowded phase occurs at longer memories.
In Fig. 7 the dependence of average attendance on M is shown. We can clearly observe that, as discussed already with Fig. 4, longer memory supresses the response of the system to the premium. For shorter memories and sufficiently small p (for N = 200 it means M ≤ 4 and p ≤ 0.1), we observe an interesting, yet not clearly understood behavior, characterized by non-monotonic dependence of the average attendance on M . In the minority game the relevant quantities are functions of the scaling variable 2 N /N . We tried the same scaling also in our Escape game. The results for p = 0.1 are in Fig. 8, while the case p = 1 is shown in Fig. 9. As we already noted, larger p makes the game be behave more similarly to usual Minority game. Here it is illustrated by the fact, that the data collapse is much better for p = 1 than for p = 0.1. We can also see again that the in large-memory phase the scaling works very well, while the crowded phase behaves differently.

V. CONCLUSIONS
We introduced an evolutionary game, which we called Escape game. The dynamical rules are similar in priciple to the Minority game, but some substantial differencs occur. We observed that in the large-memory phase the response to the premium is lower. At the same time, the behavior is closer to the Minority game, which is quantitatively seen in the fact, that the relevant quantities depend on the scaling variable 2 M /N as in the Minority game. On the other hand, for fixed memory length the behavior is similar for large premium but different from it for small premium.
The fact that the players are drawn into the play by the premium leads to enhanced attendance for high premium. On the other hand, for small premium the incentive is not strong enough and the system starts to exhibit a new dynamical phase, whose character is very close to a spin-glass.
This result can be qualitatively understood as follows. The presence of fluctuations makes the game a negativesum one, if we neglected the premium. High premium overweights the negative efect of fluctuations and the players choose the strategies, which give them highest possible attendance, irrespectively of fluctuations they cause. That is why for higher premium both the attendance and its fluctuations grow.
For small premium the fluctuations are disastrous and the players tend to avoid them by not participating. The situations, in which there are two groups, one of constantly participating players and second of constantly non-patricipating ones are suitable for both groups. The first one receives steadily the small premium, the second one at least does not loose anything. After some time, however, the scores of the absent players change so that they would prefer being in over staying out. At that moment, the system is reshuffled and another configuration of participating and non-participating players is found. The mean period of such reshufflings must be longer for smaller premium, because in this case the scores change more slowly. We expect, that the transition occurs at such a value of the premium, which would correspond to reshuffling period of order one. So, the "spin-glass" behavior is purely dynamical in origin.
To sum it up, we can draw a fuzzy line in the M versus p plane, which encloses the region of both p and M small. Outside this region the Escape game behaves merely as a sligt modification of the usual Minorit game, while inside we observe qualitatively new features, including the dynamical "spin-glass" behavior.

ACKNOWLEDGMENTS
We woulkd like to express our gratitude to P. De Los Rios and D. Challet for useful discussions and comments.