extfieldsofstudy:
Computer Science
Physics

text:
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.


extfieldsofstudy: Physics Economics Mathematics

text:
Identifying Business Sectors from Stock Price Fluctuations

Firms having similar business activities are correlated. We analyze two different cross-correlation matrices C constructed from (i) 30-min price fluctuations of 1000 US stocks for the 2-year period 1994-95 and (ii) 1-day price fluctuations of 422 US stocks for the 35-year period 1962-96. We find that the eigenvectors of C corresponding to the largest eigenvalues allow us to partition the set of all stocks into distinct subsets. These subsets are similar to conventionally-identified business sectors, and are stable for extended periods of time. Using a set of coupled stochastic differential equations, we argue how correlations between stocks might arise. Finally, we demonstrate that the sectors we identify are useful for the practical goal of finding an investment which earns a given return without exposure to unnecessary risk.

The internal structure of a complex system manifests itself in correlations among its constituents. In physical systems, one relates correlations to basic interactions, but for the stock market problem [1], the underlying 'interactions' are not known. Suppose that the change of stock prices can be visualized by the motion of point particles. Correlated particle motion can be pictured as "strings" connecting pairs of particles. Given only the records of the particle positions at equal time intervals, how can we identify the strings without 'seeing' them? One approach is to first calculate the cross-correlation matrix C whose elements C ij are the correlation-coefficients between the velocities of two particles i and j. The eigenvectors of C convey information about the collective modes of the system.
What is the analog of the cross-correlation matrix C for the stock market problem? We define the crosscorrelation matrix C with elements C ij ≡ [ G i G j − G i G j ]/σ i σ j , where σ i is the standard deviation of price fluctuations G i (t) ≡ ln S i (t + ∆t) − ln S i (t) (returns), S i (t) denotes the price of stock i = 1, . . . , N , and . . . denotes a time average over the period studied. To investigate correlations on different time scales, we analyze (i) 30-min returns of N = 1000 largest stocks for the two-year period 1994-95 and (ii) daily returns of N = 422 stocks for the 35-year period 1962-96 [2]. We first diagonalize C and rank-order its eigenvalues λ k such that λ k+1 > λ k ; the corresponding eigenvectors are denoted u k . Next, we analyze the components of those deviating eigenvectors whose eigenvalues are larger than the upper bound for uncorrelated time series [3,4]. A direct examination of these eigenvectors, however, does not yield a straightforward interpretation of their economic relevance. To interpret their meaning, we note that the largest eigenvalue is an order of magnitude larger than the others, which constrains the remaining N − 1 eigenvalues since Tr C = N . Thus, in order to analyze the contents of the deviating eigenvectors, we first remove the effect of the largest eigenvalue [5].
To analyze the information contained in the eigenvectors u k , we partition the 1000 stocks into groups labeled ℓ = 1 . . . , 75 (comprising N ℓ stocks each) according to the first two digits of their Standard Industrial Classification (SIC) code, which classifies major industry groups. We define a projection matrix P, with elements P ℓi = 1/N ℓ if stock i belongs to group ℓ and P ℓi = 0 otherwise. For each deviating eigenvector u k , we compute the contribution X k ℓ ≡ N i=1 P k ℓi [u k i ] 2 of each industry group ℓ. The above procedure of computing X k ℓ is analogous to the analysis of wave functions in disordered systems, where one calculates the probability of finding a particle in a given region. Figure 1 shows X k ℓ for ten largest eigenvectors after excluding the influence of the largest eigenvalue. The contribution X 999 ℓ shows several industries. We examine the significant contributors and find mainly stocks with large market capitalization [ Fig. 2]. We analyze X k ℓ for the remainder of the deviating eigenvectors and find a significant 'peak' at distinct values of the SIC codesuggesting that these eigenvectors correspond to distinct industry groups [6].
One deviating eigenvector u 995 displays large values of X k ℓ for firms belonging to the heavy construction industry and telecommunications industry. In addition, an examination of these firms shows significant business activity in Latin America. Another case corresponds to eigenvectors u 996 and u 997 , both of which contain a mixture of stocks of gold-mining firms and banking firms. We find that these two sectors separate when we compute the symmetric and antisymmetric combinations 1/ √ 2( u 996 ± u 997 ). The remainder of the deviating eigenvectors display technology, metal mining, banking, petroleum refining, auto manufacturing, drug manufacturing, and paper manufacturing firms [ Fig. 1].
We next focus on the interpretation of the largest eigenvalue λ 1000 . Using the eigenvector u 1000 , we construct a time series We then compare G 1000 (t) with the returns G SP (t) of the S&P 500 index, a benchmark for gauging the performance of entire US stock market. Regressing G 1000 (t) against G SP (t) shows a scatter around a linear fit with slope 0.85 ± 0.09 [ Fig. 3]. Thus, we interpret the eigenvector u 1000 as the influence of the entire market, that is common for all stocks [3,4].
Next, we examine whether the eigenvectors u k corresponding to business sectors remain stable in time. Partitioning the year 1994 into two 6-month periods, A and B, we calculate the corresponding eigenvectors u A and u B of the cross-correlation matrices and quantify the time stability by calculating the magnitude of the scalar products O ij ≡ | u i A u j B | for the 20 largest eigenvalues. Perfect time stability would mean O ij = δ ij . For i = 1000, we find O ii = 0.93 -indicating almost perfect stability. We find that O ii decreases as i decreases from 1000 [ Fig. 4]. Extending this analysis to daily returns using database (ii) shows that the eigenvectors corresponding to the largest 3 eigenvalues are stable for as many as 10 years.
How can we explain correlations that are stable in time? In physical systems, one starts from the interactions between the constituents, and then relates interactions to correlated "modes" of the system. In economic systems, we ask if "interactions" give rise to the correlated behavior. Interactions can arise when two companies are doing business together, or compete for the same market. To study if the correlations can be explained through interactions [7], we model stock price dynamics by a differential equation [8,9], which describes the 'instantaneous" returns g i (t) = d dt ln S i (t) as a random walk with interactions J ij Here, ξ i (t) are Gaussian random variables with correlation function ξ i (t)ξ j (t ′ ) = δ ij τ i δ(t − t ′ ), and τ i are relaxation times of the g i (t)g i (t+ T ) correlation function. The return G i at a finite time interval ∆t is given by the integral of g i over ∆t.
Calculating time-dependent correlation functions for the g i , we find that correlations caused by interactions are accompanied by a phenomenon analogous to "critical slowing down". The market time series G 1000 (t) -as well as time series constructed similarly for other deviating eigenvectors -have considerably larger correlation times than a time series constructed out of a random eigenvector, consistent with the hypothesis that correlations between firms are caused by interactions.
The eigenvectors that we interpret as defining business sectors also have relevance to the practical goal of finding an investment which earns a given return without exposure to unnecessary risk ("optimal portfolio"). Risk can be reduced by diversification of investment into indepen-dently fluctuating groups of stocks, such as the mutually uncorrelated business sectors that we find. Since the sectors (eigenvectors) are stable in time, we expect the ratio of risk to return of the portfolios constructed from them to be stable.
Consider a portfolio P (t) ≡ N i=1 w i S i (t), where w i is the fraction of wealth invested in stock i. The portfolio return is given by R = N i=1 w i G i . The risk in holding the portfolio P (t) can be quantified by the variance . In order to find an optimal portfolio, we minimize D 2 under the constraints that the portfolio return is some fixed value R and N i=1 w i = 1. We thereby obtain a family of optimal portfolios, which we represent by plotting R as a function of risk D 2 [Fig. 5].
To find the effect of randomness of the C ij on optimal portfolio selection, we partition the time period 1994-95 into two 1-year periods. Using the cross-correlation matrix C 94 for 1994, and G i for 1995 [11], we construct a family of optimal portfolios and plot R as a function of the predicted risk D 2 p for 1995 [ Fig. 5(a)]. For this family of portfolios, we also compute the risk D 2 r realized during 1995 using C 95 [ Fig. 5(a)]. We find that the predicted risk is significantly smaller than the realized risk: [D 2 r − D 2 p ]/D 2 p ≈ 170%. Since the meaningful information in C is contained in the deviating eigenvectors that define business sectors, we construct a 'filtered' correlation matrix C ′ , by retaining only the deviating eigenvectors [12]. We repeat the above calculations for finding the optimal portfolio using C ′ instead of C. Figure 5(b) shows that the realized risk is now much closer to the predicted risk: [D 2 r − D 2 p ]/D 2 p ≈ 25%. Thus, the optimal portfolios constructed using C ′ are significantly more stable in time.
In summary, given only the change in price of a stock, and no additional information about the stock, we can partition the set of all 10 3 stocks studied into subsets whose identities correspond well to conventionallyidentified sectors of economic activity. The sector correlations are stable in time and can be used for the construction of optimal portfolios with a stable ratio of risk to return.
We thank J.-P. Bouchaud, P. Cizeau, E. Derman, X. Gabaix, J. Hill, M. Janjusevic, R. N. Mantegna, M. Potters, L. Viceira, J. Zou, and especially L. A. N. Amaral for stimulating discussions, and DFG grant RO1-1/2447 for financial support. Our results on the applications to portfolio selection were presented at the APS March 2000 meeting by one of us (BR) and independently by P. Cizeau.
[1] A recent review of research done by physicists is J. D.
[2] The 30-min data analyzed are from the Trades and Quotes database published by the New York Stock Exchange. The daily data is from the Center for Research in Securities Prices (CRSP) database. In both cases, only those companies that survive the entire period are considered in our analysis.
[4] V. Plerou, et al., Phys. Rev. Lett. 83, 1471(1999. [5] The presence of a very large eigenvalue, by preservation of the trace Tr (C)= N , tends to cause the other large eigenvalues and eigenvectors to be influenced by randomness. Therefore, in order to remove the effect of the "market mode" on other large eigenvalues, we implement the linear regression Gi(t) = αi + βiG 1000 (t) + ǫi(t), where We then recompute the correlation matrix C using the residuals ǫi(t). Alternatively, removing the intra-daily patterns in absolute values of Gi(t) using the procedure of Y. Liu et al., Phys. Rev. E 60, 1390(1999 also yields similar results. [6] An interesting classification of stocks into sectors using the concept of ultrametric distances was obtained by R. N. Mantegna, Eur. Phys. J. B 11, 193 (1999). [12] To filter C from the effects of the random part, we first construct a diagonal matrix Λ ′ , with elements Λ ′ ii = {0, . . . , 0, λ988, . . . , λ1000}. We then transform Λ ′ to the basis of C, thus obtaining the 'filtered' cross-correlation matrix C ′ . In addition, we set the diagonal elements C ′ ii = 1, to preserve Tr(C) = Tr(C ′ ) = N .
[13] The curves specify ∆t = 30 min risk and return values.