Crowd-anticrowd model of the Minority Game
M. Hart
P. Jefferies and N.F. Johnson
We provide a theoretical description of the Minority Game in terms of crowd effects. The size of the fluctuations arising in the game is controlled by the interplay between crowds of like-minded agents and their anti-correlated partners (anticrowds). The theoretical results are in good agreement with the numerical simulations over the entire parameter range of interest.
paper.tex
	paper.texTEXT*TEX�DLUp��`��mBIN���
\documentstyle[aps,manuscript]{revtex}

\begin{document}


\title {Crowd-anticrowd model of the Minority Game}
\author{M. Hart, P. Jefferies and N.F. Johnson}
\address {Physics Department, Oxford University,
Oxford, OX1 3PU, U.K.}
\author{P.M. Hui}
\address {Department of Physics, The Chinese
University of Hong Kong, Shatin, \\
New Territories, Hong Kong}

\maketitle


\begin{abstract}
We provide a theoretical description of the  
Minority Game in terms of crowd effects. The size of the
fluctuations arising in the game is controlled by the interplay between crowds of
like-minded agents and their anti-correlated partners (anticrowds). The
theoretical results are in  good agreement with the numerical
simulations
over the entire parameter range of interest.


\end{abstract}
\bigskip


\noindent PACS: 01.75.+m, 02.50.Le, 05.40.+j, 87.23.Ge


\newpage

The study of agent-based models of complex adaptive systems
is attracting much attention\cite{arthur}. Among the many possible
interdisciplinary applications is the growing field of
econophysics\cite{stanley}: each agent knows the past ups and downs in the
index
of a financial market and must decide how to trade based on this global
information. The Minority Game (MG) introduced by
Challet and Zhang\cite{challet,savit}, offers arguably the simplest paradigm
for
such a complex, adaptive system.  The MG comprises an odd number
$N$ of agents, each equipped with $s$ strategies and a memory size
$m$, who repeatedly compete to be in the
minority\cite{challet,savit,spinglass,sherrington,dHR,cavagna,us,crowd}.
The most
striking feature arising from numerical simulations is the
non-monotonic variation in the size of the fluctuations (i.e. standard
deviation) produced by the MG as
$m$ is varied\cite{savit}.
Challet {\em et al}
provided a sophisticated formal connection between the MG and spin
glass systems\cite{spinglass} which offers many fascinating quantitative
insights into the MG's dynamics. Given the 
complexity of this dynamics, it is
understandable that no general theory has yet been proposed which yields
quantitative agreement with the numerical results of Ref. \cite{savit} over
the
full range of
$m$, $s$ and $N$ values.

In this paper, we show that a theoretical
model can be constructed in a surprisingly simple way by incorporating
the `crowd' effects (i.e. strong inter-agent correlations) which arise
within the
interacting, many-agent population. The results yield good agreement
with the numerical results\cite{savit} 
over the entire range of $m$, $s$ and $N$.
The
non-monotonic behaviour of the standard deviation\cite{challet,savit} 
is shown to
arise from a fascinating interplay between a crowd and its anti-correlated
partner
(`anticrowd').

The MG\cite{challet} comprises an
odd number of agents $N$ who choose repeatedly between
option 0 (e.g. buy) and option 1 (e.g. sell).   
The winners are those in the
minority group, e.g. sellers win if there is an excess of buyers. The
outcome at
each timestep represents the winning decision, 0 or 1. 
A common bit-string of the $m$ most recent
outcomes is made available to the agents at each timestep.
The agents
randomly pick $s$ strategies at the beginning of the game, with repetitions
allowed. After each turn, the agent assigns one (virtual) point to each of his
strategies which would have
predicted the correct outcome. At each turn of the game, the agent
uses the most successful strategy, i.e. the one with the 
most virtual points, 
among his $s$ strategies. The strategy-space ${\cal V}_m$ forms a
$2^m$-dimensional  hypercube with
strategies at the $2^{2^m}$ vertices. Fortunately,
the MG's standard deviation is essentially unchanged if a `reduced' strategy
space ${\cal U}_m$ is used instead of ${\cal V}_m$ \cite{challet}: the
${\cal U}_m$ only contains
$2^{m+1}$ strategies or equivalently $2^m$ strategy pairs $\{\cal G\}$.
The two strategies within a given pair $\cal G$ are anticorrelated, i.e. they
differ by the maximum possible Hamming distance $d_H=2^m$ \cite{challet}.
Strategies between any two pairs
$\cal G$ and $\cal G'$ are uncorrelated, i.e. they differ by $d_H=2^{m-1}$.  The
results presented in this paper employ the reduced strategy space. 

If ${n}_R$ agents use the same strategy $R$, then they
will act as a `crowd', i.e. they will make the same decision. If
${n}_{\bar R}$ agents simultaneously use the 
anticorrelated strategy  
$\bar R$, they will make the opposite decision and will hence act as an
`anticrowd' (${\cal G}\equiv (R,\bar R)$). If
${n}_R\approx {n}_{\bar R}$ for all $\cal G$, then the actions of the crowds and
anticrowds cancel and the standard deviation $\sigma$ of the number of agents
choosing a given option (the so-called `attendance' time-series
$A(t)$) will be small. In contrast if
${n}_R
\gg n_{\bar R}$ for all
$\cal G$, then
$\sigma$ will be large. Since there is no correlation between $\cal G$ and
$\cal
G'$, each group $\cal G$ comprising a
crowd-anticrowd pair $(n_R,n_{\bar R})$ will contribute to the attendance
$A(t)$ via a separate random walk in time of step-size
$|n_R-n_{\bar R}|$. The variances of these walks can then be summed to
obtain the standard deviation of $A(t)$. Hence we describe the MG standard
deviation using the following theoretical expression:
\begin{equation}
\sigma = \bigg[\sum_{{\cal G}=1}^{2^{m}} \sigma^2_{\cal
G}\bigg]^{\frac{1}{2}} =
\bigg[\sum_{{\cal G}\equiv (R,{\bar R})}
\frac{1}{4}|n_R-n_{\bar R}|^2\bigg]^{\frac{1}{2}}
\
\end{equation}
where both time-averaging, for a given configuration of
initial strategies, and configuration-averaging have been
carried out. We now demonstrate that this crowd-anticrowd cancellation underlies
the numerical results for
$\sigma$ vs. $m$
\cite{savit}.
We run the numerical simulation of the MG and wait until transients in
$A(t)$
have disappeared. At timestep $t_0$, we read out the number of players
playing each strategy $R$, where $R=1,2,\dots 2^{m+1}$. For each strategy pair
${\cal G}=(R,{\bar R})$, we calculate 
$n_R-n_{\bar R}$ at time $t_0$ and hence obtain $\sigma$.  We then
average this $\sigma$ over 1000 timesteps to simulate the time-averaging.
We have checked that our
results are insensitive to the precise time-averaging procedure.  Finally,
we
average over 16 runs to simulate the configuration-averaging.
Figure 1 compares the resulting time and configuration-averaged $\sigma$ with that
obtained from the numerical MG simulation. The agreement is very good for all
$m$, $s$ and
$N$ (not shown). We conclude that the crowd-anticrowd cancellation can
indeed quantitatively explain the numerical results of Ref. \cite{savit}.

We need expressions for the number of agents using each strategy, i.e.
$\{n_R\}$.
Since the labels $R$ are arbitrary in Eq. (1), the ordering of
strategies
$\{n_R\}$ has no particular significance.
At any particular time
$t_0$, these
$2^{m+1}$ strategies can be ranked according to their virtual points by a
sort-operation $\Theta$ acting on the list $\{n_R\}$. Hence
$\{n_R\}\stackrel{\Theta}\mapsto \{{n}_\rho\}$ where $\rho$ is
the virtual-point rank label with $\rho=1$ being the highest scoring
strategy and
$\{n_\rho\}\equiv n_{\rho=1}, n_{\rho=2},\dots n_{\rho={2^{m+1}}}$. Another
useful
method of ordering is achieved by ranking strategies $\{n_R\}$ at time
$t_0$ according to their
popularity. In particular, strategy $r=1$ is defined as the strategy
which is being used 
by the largest number of agents, strategy $r=2$ is being used
by the second largest number of agents, etc. We denote the 
popularity ranking by
$\{n_r\}$ where
$\{n_r\}\equiv n_{r=1}, n_{r=2},\dots n_{r={2^{m+1}}}$. 
Note that $\{n_r\}$ can be
obtained from $\{n_R\}$ and hence $\{n_\rho\}$ by sort operations, i.e.
$\{n_R\}\stackrel{\Psi}\mapsto \{n_r\}$ and
hence $\{n_\rho\}\stackrel{\Gamma}\mapsto
\{n_r\}$.
Each agent plays
the available strategy having highest virtual points; this allows an analytic
expression to be obtained for the probability that an agent plays a given
strategy for general $s$, which in turn yields 
\begin{equation} n_r=N\bigg(\bigg[1 - \frac{(r-1)}{2^{m+1}}\bigg]^s -
\bigg[1-\frac{r}{2^{m+1}}\bigg]^s\bigg)
\end{equation}
where $\sum_{r=1}^{2^{m+1}} n_r =N$ as required. Since agents are discrete objects, the simulation
tends to produce discrete steps in the curves of $n_r$ as a function of $r$. This
effect
becomes more pronounced as $m$ increases since the total number of
strategies $2^{m+1}$
then exceeds the population size $N$. We therefore convert the theoretical
$n_{r}$
values of Eq. (2) to an integer. For large $m$ such that $2^{m+1}\gg N$, the
resulting theoretical values are typically $n_r\sim 1$ for small $r$ and
$n_r=0$ for $r>N$. Figure 2 compares the
theoretical
values of $n_r$ calculated using Eq. (2) with $s=2$ and $N=101$, to
numerical values
taken from the MG simulation. The
agreement is good. 

For the
virtual-point ordered list $\{n_\rho\}$, the strategy
$\rho'=2^{m+1}+1-\rho$ is {\em always} anticorrelated to the strategy
$\rho$, i.e.
$\rho'\equiv \bar \rho$. Hence knowledge of the sort operation $\Gamma$
completely
determines where  each strategy's anticorrelated partner is located in the
popularity-ordered list $\{n_r\}$. Since we are here only interested
in time-averaged and run-averaged
$\sigma$, we only need to consider the probability distribution of locations of
$\bar r$ in the  popularity-ordered
list $\{n_r\}$. We
therefore replace the sort operation $\Gamma$ by a
probability function $P(r'={\bar r})$ which gives the
probability that any strategy $r'$ is the anti-correlated partner
of strategy $r$ in the list $\{n_r\}$.
Hence Eq. (1) becomes
\begin{equation}
\sigma =
\bigg[ \frac{1}{2} \sum_{r=1}^{2^{m+1}} \sum_{r'=1}^{2^{m+1}}
\frac{1}{4}|n_r-n_{r'}|^2 P(r'={\bar r})\bigg]^{\frac{1}{2}}
\
\
\end{equation}
where the factor
$\frac{1}{2}$ discounts double-counting.
There are two limiting cases. When the virtual-point ordered
list
$\{n_\rho\}$ and the popularity-ordered list $\{n_r\}$ are identical, then
$P(r'={\bar r})$ will be a $\delta$-function at $r'=2^{m+1}+1-r$ and hence
Eq. (3)
has the same form 
as Eq. (1). In the opposite case where the two ordered
lists
are uncorrelated, $P(r'={\bar r})$ should be a flat distribution. In each
case, Eqs.
(2) and (3) can be combined to obtain closed-form analytic solutions for
arbitrary $s$
and $N$. 


Figure 3 shows $P(r'={\bar r})$ for $r=1$ as a function of $r'$, taken from
the
numerical MG  simulation at $m=2,5$ and $10$. For small $m$ ($m=2$) the
anticorrelated strategy to the most popular strategy (i.e. $r=1$) 
is at $r'=2^{m+1}$,
i.e. it is the least popular strategy. Hence $P(r'={\bar r})$ resembles the
$\delta$-function limiting case mentioned above. From Fig. 2 we know that
very few agents will therefore pick this anticorrelated strategy. Hence the
crowd-anticrowd
cancellation will be small and $\sigma$ will be large, as can be seen in
Fig. 1. As
$m$ increases ($m=5$) a remarkable effect occurs: the peak in $P(r'={\bar
r})$ moves
up toward $r=1$. Hence both $r=1$ and its anticorrelated partner $\bar r$
are now very
popular. Whereas for $m=2$ it seemed like there was an effective `repulsion'
between
$r$ and $\bar r$, for $m=5$ this now seems more like an attraction.
Amusingly, the
shape of $P(r'={\bar r})$ for $m=5$ is reminiscent of the screening effect
of a
negative charge cloud around a positive charge placed at $r=1$, or even a
bound
electron-hole pair (i.e. exciton) with the crowd (anticrowd) playing the
role of the
positive (negative) charge. For large $m$ ($m=10$), the ability of the
anticrowd to `screen' the crowd has decreased yielding a rather flat
distribution as
shown. The consequence of this strong crowd-anticrowd correlation which
appears as $m$
increases, is that the crowd and anticrowd become comparable in size. Hence
$\sigma$ is small for $m\sim 5-6$, in agreement with Fig. 1. 
Note that the MG cannot fully `optimize' itself by building equal-sized crowds and
anticrowds.  In modified models of MG\cite{prl}
where this in-built frustration in the strategy space is allowed to relax,
equal-sized
crowds and anti-crowds do naturally emerge.

We now consider analytic expressions for $\sigma$ for
general $s$ using Eqs. (2) and (3). For small $m$, 
the virtual-point ordered list $\{n_\rho\}$ and the popularity-ordered list
$\{n_r\}$
will be very similar, hence $P(r'={\bar r}) \sim \delta_{r',2^{m+1}+1-r}$. The
discreteness of the agents will be unimportant since $n_r\gg1$,
hence $n_r$ can
be treated as continuous. Equations (2) and (3) yield
\begin{eqnarray}
\sigma_{{\rm low}\ m} & = & \frac{N}{2}\bigg[ \sum_{r=1}^{2^{m}} \bigg[
\bigg(1-\frac{r-1}{2^{m+1}}\bigg)^s - \bigg(1-\frac{r}{2^{m+1}}\bigg)^s
\nonumber \\
& & - \bigg(\frac{r}{2^{m+1}}\bigg)^s + \bigg(\frac{r}{2^{m+1}}\bigg)^s
\bigg(1 -
\frac{1}{r}\bigg)^s
\bigg]^2\
\bigg]^{\frac{1}{2}}\ \ .
\end{eqnarray}
For $s=2$ this becomes
\begin{equation}
\sigma_{{\rm low}\ m} = \frac{N}{{\sqrt 3}\  2^{\frac{m}{2}+1}} \bigg[ 1 -
2^{-2(m+1)}\bigg] ^{\frac{1}{2}} \ \ .
\end{equation}
Figure 4 shows these analytic curves for $s=2$ and $s=4$ (solid
lines monotonically decreasing). As
might be expected using the extreme
$\delta$-function form for
$P(r'={\bar r})$, these curves are slightly higher than the numerical
results in Fig.
1 for small $m$. Now consider the opposite extreme of uncorrelated $r'$ and
$\bar r$,
i.e. the flat distribution
$P(r'={\bar r})\sim 2^{-(m+1)}$.
For $s=2$ this gives
\begin{equation}
\sigma_{{\rm low}\ m} = \frac{N}{{\sqrt 3}\  2^{\frac{(m+3)}{2}}} \bigg[ 1 -
2^{-2(m+1)}\bigg] ^{\frac{1}{2}} \ \ .
\end{equation}
Equation (6) typically produces lower estimates for each $s$ value
(dashed lines). Values of $\sigma$ obtained from separate numerical
runs tend to be scattered in the region of these curves. For
larger $m$
($m>6$) we cannot ignore the discreteness of the agents 
(Fig. 2).
In this regime, $n_r\sim 1$ for $r<N$ while $n_r=0$ for $r>N$. Using the integer
form of Eq. (2) for high $m$, and the flat distribution
for $P(r'={\bar r})$, yields
\begin{equation}
\sigma_{{\rm high}\ m} =  \frac{\sqrt N}{2} \bigg[ 1 -
\frac{N}{2^{m+1}}\bigg]^{\frac{1}{2}}\ .
\end{equation}
This expression approaches the coin-toss limit from below as $m\rightarrow
\infty$, as shown in Fig. 4 (solid line monotonically increasing).
Within the approximation used
here, this curve is insensitive to $s$. Note that the numerical MG
results are also
consistent with this finding of weak $s$-dependence for large $m$.
Hence Fig. 4 gives
a clear picture of what happens to $\sigma$ as $s$ 
and $m$ increase: considering
the
monotonically decreasing curve for low $m$, and the monotonically increasing
curve for
high $m$, we see that (a) there should be a minimum in $\sigma$ for $s=2$,
(b) this
minimum should move to higher
$m$ as
$s$ increases and (c) the minimum should become shallower as $s$ increases.
Each of
these statements agrees with numerical simulation results (c.f.
Fig. 1).
In addition, the curve $\sigma_{{\rm high}\ m}\rightarrow 0$ at $N=2^{m+1}$,
i.e. for $m\sim 5-6$. 


We now compare the theoretical crowd-anticrowd calculation (Eq. (3)) with the
numerical simulation. The most interesting case is $s=2$. Figure 5 shows the
spread of numerical values for different runs (open circles) compared to
theory (solid circles). The
agreement is good. The appropriate analytic expressions for the
probability
function
$P(r'={\bar r})$ in Eq. (3) involve multiple sums and are complicated:
we therefore obtained the results for each $m$ in Fig. 5 by generating the
corresponding 
$P(r'={\bar r})$ forms to those in Fig. 3. The theoretical
points tend to lie in between the limiting curves of Fig. 4 {\em except} at the
minimum where the
remarkable form for $P(r'={\bar r})$ (recall Fig. 3) pulls the theoretical
value slightly
below the cruder limiting curves of Fig. 4. Elsewhere we will discuss
simpler closed-form expressions for
$P(r'={\bar r})$, together with 
an analysis of the time-series $A(t)$ and history bit-string
statistics within the crowd-anticrowd model \cite{long}.



In summary we presented an analytic analysis of crowding
effects in MG which offers a novel explanation of the
main finding of Ref.
\cite{savit}. Future work 
will explore possible connections to the spin-glass formalism
of  Challet {\em et al} \cite{spinglass}.


We thank T.S. Lo, J.P. Garrahan, D. Sherrington and D. Challet for
discussions.


\newpage




\begin{thebibliography}{99}
\bibitem{arthur} W.B. Arthur, 
Science {\bf 284}, 107 (1999).
\bibitem{stanley} H.E. Stanley, Computing
in Science \& Engineering Jan/Feb, 76 (1999).
\bibitem{challet} D. Challet and Y.C. Zhang, Physica A {\bf 246}, 407
(1997);
{\em ibid.} {\bf 256}, 514 (1998); {\em ibid.} {\bf 269}, 30 (1999).
\bibitem{savit} R. Savit, R. Manuca and R. Riolo, Phys. Rev. Lett.  {\bf
82}, 2203
(1999).
\bibitem{spinglass} D. Challet and M. Marsili, Phys. Rev. E {\bf 60}, R6271
(1999); D. Challet, M. Marsili, and R. Zecchina,
Phys. Rev. Lett. {\bf 84}, 1824 (2000); D. Challet and M Marsili,
cond-mat/9908480.
\bibitem{sherrington} A. Cavagna, I. Giardina, J.P. Garrahan and D.
Sherrington,
Phys. Rev. Lett. {\bf 83}, 4429 (1999).
\bibitem{dHR} R. D'Hulst and G.J. Rodgers, Physica A {\bf 270}, 514 (1999).
\bibitem{cavagna} A. Cavagna,
Phys. Rev. E {\bf 59}, R3783 (1999).
\bibitem{us} N.F. Johnson, P.M. Hui, D. Zheng and M. Hart,
J. Phys. A: Math. Gen. {\bf 32} L427 (1999).
\bibitem{crowd} N.F. Johnson, M. Hart and P.M. Hui, Physica A {\bf 269}, 1
(1999). This conference paper provides a preliminary report of the
qualitative effects
of crowding.
\bibitem{prl} N.F. Johnson, P.M. Hui, R. Jonson and T.S. Lo,  Phys. Rev.
Lett. {\bf 82}, 3360 (1999).
\bibitem{long} P. Jefferies, M. Hart, N.F. Johnson and P.M. Hui, in
preparation.

\end{thebibliography}

\begin{figure}
\bigskip

\caption{Standard deviation $\sigma$ for the Minority Game as a function of
memory-size $m$
for $s=2,3,4$ strategies per agent and $N=101$ agents. Solid curve:
numerical
simulation. Dashed curve: crowd-anticrowd theory using Eq.
(1). Random (coin-toss) limit $\sigma={\sqrt N}/2=5.0$ is indicated.}
\bigskip
\bigskip



\caption{Histograms of the number of agents using strategy $r$
for $r=1$ (most popular) to $r=2^{m+1}$ (least
popular). Results are shown for $m=2$ (left scale) and $m=7$ (right scale).
Solid lines: numerical simulation. Dashed lines: theory from Eq. (2).}
\bigskip
\bigskip


\caption{Probability function $P(r'={\bar r})$ giving the probability that the
strategy
ranked $r'$ on the popularity-ordered list, is anti-correlated with the
strategy
ranked $r$. Results are shown for $r=1$ (i.e. most popular strategy) as a
function of
$r'$ for
$m=2$ (dotted-dashed), $m=5$ (dotted) and
$m=10$ (solid).
$s=2$ and $N=101$. Note that $\sum_{r'} P(r'={\bar r}) =1$.}
\bigskip
\bigskip


\caption{Theoretical curves for $\sigma$ using Eqs.
(4)-(7). Monotonically decreasing curves for $s=2,4$ at low $m$ ($m<6$): solid
lines correspond to
$\delta$-function
$P(r'={\bar r})$ distribution 
neglecting agent discreteness, dashed lines correspond to flat distribution
neglecting agent discreteness. Monotonically increasing solid line for large $m$
($m>6$) is  independent of $s$: it corresponds
to a flat distribution and accounts for agent discreteness.}
\bigskip
\bigskip


\caption{Theoretical crowd-anticrowd calculation (solid circles) vs. numerical 
simulations (open circles)
for
$s=2$, $N=101$.
16 numerical runs are shown for each $m$.}







\end{figure}

\end{document}

on�.ukn.johnson@physics.ox.ac.ukL	paper.texTEXT*TEX�DTEXT*TEX�D��`LUpance Seminars - 2000"SHEILA HAMMERTON" <forcsha@razor.wbs.warwick.ac.uk>"Neil F. Johnson" <n.johnson@physics.ox.ac.uk>RE: BBC VKpKp�MonacoP_j%�,%� h��@P__!,Tl*PI2O�	$��	LaTeXxHH
����+6Gz�HH
d�'h�*����;� TeX output 2000.03.30:1059��b
���;����
	���u

cmex10�X�Qcmr12�X�Qffcmr12���N�ffcmbx12�K�`y
�3
cmr10��':
�3
cmti10�|{Ycmr8��Aa�cmr6���g�cmmi12��2cmmi8�;�cmmi6�!",�
cmsy10��K�cmsy8�q�%cmsy6���N�cmbx12�$���@cmti12�0�b>
�3
cmmi10�1!",�
�3
cmsy10�kh����G���������7g����xg��Dp���N�ffcmbx12�Cro���wd-an�ticro�wd�ffmo�s3del�of�the�Minorit���y�Game��+����8�X�Qcmr12�M.��Hart,�P��V.�Jeeries�and�N.F.�Johnson���[��M�<��':
�3
cmti10�Physics���Dep��p�artment,�Oxfor�d�University,�Oxfor�d,�O��\X1�3PU,�U.K.��)��ҖH�P��V.M.��Hui����?���Dep��p�artment���of�Physics,�The�Chinese�University�of�Hong�Kong,�Shatin,�����y�New���T��)erritories,�Hong�Kong��;�<���"n�X�Qffcmr12�Abstract��$���5�O�K�`y
�3
cmr10�W��ee�1�pro��!vide�a�theoretical�description�of�the�Minorit�y�Game�in�terms�of�cro�wd����2R�eects.�k�The�*�size�of�the�
uctuations�arising�in�the�game�is�con��!trolled�b�y�the����2R�in��!terpla�y��b�M�et�w�een�cro�wds�of�lik�e-minded�agen�ts�and�their�an�ti-correlated�part-����2R�ners�ٍ(an��!ticro�wds).�wSThe�theoretical�results�are�in�go�M�o�d�agreemen��!t�with�the����2R�n��!umerical��fsim�ulations�o�v�er�the�en�tire�parameter�range�of�in�terest.��#�[��P��VA��rCS:��01.75.+m,�02.50.Le,�05.40.+j,�87.23.Ge������1���-�*����7g����xg�����The��study�of�agen��rt-based�mo�S�dels�of�complex�adaptiv�e�systems�is�attracting�m�uc�h�at-���[�ten��rtion�al[1].��-Among�the�man�y�p�S�ossible�in�terdisciplinary�applications�is�the�gro�wing�eld�of���econoph��rysics�X[2]:��8eac�h�agen�t�kno�ws�the�past�ups�and�do�wns�in�the�index�of�a�nancial�mark�et���and��m��rust�decide�ho�w�to�trade�based�on�this�global�information.�8The�Minorit�y�Game�(MG)���in��rtro�S�duced� 3b�y�Challet�and�Zhang�[3,4],�m�oers�arguably�the�simplest�paradigm�for�suc�h�a���complex,�-�adaptiv��re� |system.��\The�MG� ncomprises�an�o�S�dd�n�um�b�S�er����g�cmmi12�N�a`�of�agen�ts,�-�eac�h�equipp�S�ed���with� ��s��strategies�and�a�memory�size��m�,�I8who�rep�S�eatedly�comp�ete�to�b�e�in�the�minorit��ry�[3�{����10].���The�W�most�striking�feature�arising�from�n��rumerical�sim�ulations�is�the�non-monotonic�v��X�ariation���in���the�size�of�the�
uctuations�(i.e.�r�standard�deviation)�pro�S�duced�b��ry�the�MG���as��m��is�v��X�aried���[4].�ZChallet�q�$���@cmti12�et��ual��pro��rvided�a�sophisticated�formal�connection�b�S�et�w�een�the�MG�p�and�spin�glass���systems�eV[5]�whic��rh�oers�man�y�fascinating�quan�titativ�e�insigh�ts�in�to�the�MG's�dynamics.���Giv��ren��#the�complexit�y�of�this�dynamics,��it�is�understandable�that�no�general�theory�has�y�et���b�S�een��aprop�osed�whic��rh�yields�quan�titativ�e�agreemen�t�with�the�n�umerical�results�of�Ref.�[4]���o��rv�er��the�full�range�of��m�,��s��and��N�+��v��X�alues.������In�&�this�pap�S�er,�u�w��re�sho�w�that�a�theoretical�mo�S�del�can�b�e�constructed�in�a�surprisingly���simple�8Xw��ra�y�b�y�incorp�S�orating�the�`cro�wd'�eects�(i.e.�!�strong�in�ter-agen�t�correlations)�whic�h���arise��within�the�in��rteracting,��eman�y-agen�t��p�S�opulation.��The�results�yield�go�o�d�agreemen��rt�with���the�d�n��rumerical�results�[4]�o�v�er�the�en�tire�range�of��m�,���s��and��N�@�.�IThe�non-monotonic�b�S�eha�viour���of��the�standard�deviation�[3,4]�is�sho��rwn�to�arise�from�a�fascinating�in�terpla�y�b�S�et�w�een�a�cro�wd���and��its�an��rti-correlated�partner�(`an�ticro�wd').������The��MG�[3]�comprises�an�o�S�dd�n��rum�b�er��of�agen��rts��N�U̹who�c�ho�S�ose�rep�eatedly�b�et��rw�een��option���0�	V(e.g.���buy)�and�option�1�(e.g.�sell).�The�winners�are�those�in�the�minorit��ry�group,�6ge.g.�sellers���win��?if�there�is�an�excess�of�buy��rers.�&�The�outcome�at�eac�h�timestep�represen�ts�the�winning���decision,�Xr0�Jor�1.���A��common�bit-string�of�the��m��most�recen��rt�outcomes�is�made�a�v��X�ailable���to�L�the�agen��rts�at�eac�h�timestep.�^�The�agen�ts�randomly�pic�k��s��strategies�at�the�b�S�eginning�of���the�|�game,��Cwith�rep�S�etitions�allo��rw�ed.��"After�|�eac�h�turn,��Cthe�agen�t�assigns�one�(virtual)�p�S�oin�t���to�Nneac��rh�of�his�strategies�whic�h�w�ould�ha�v�e�predicted�the�correct�outcome.�d3A�t�eac�h�turn�of���the���game,���the�agen��rt�uses�the�most�successful�strategy��V,�i.e.���the�one�with�the�most�virtual������2���~�q����7g����xg��p�S�oin��rts,�ĸamong��his��s��strategies.�D:The�strategy-space��!",�
cmsy10�V������2cmmi8�m���߹forms�a�2����2�m��Ĺ-dimensional�h�yp�S�ercub�e���[�with�!�strategies�at�the�2����2�|{Ycmr8�2���-:�;�cmmi6�m����v��rertices.�ݨF��Vortunately�,�/Pthe�!�MG's�standard�deviation�is�essen�tially���unc��rhanged�
Hif�a�`reduced'�strategy�space��U�����m���is�used�instead�of��V�����m���[3]:�x!the��U�����m���only�con��rtains���2����2�m�+1��ή�strategies��nor�equiv��X�alen��rtly�2����2�m���2�strategy�pairs��fG��.g�.�A3The�t�w�o�strategies�within�a�giv�en���pair��1�G�w_�are�an��rticorrelated,�6�i.e.�
�|they�dier�b�y�the�maxim�um�p�S�ossible�Hamming�distance����d�����H��n��=�UR2����2�m���J�[3].�&�Strategies���b�S�et��rw�een�an�y�t�w�o�pairs��G�j��and��G���.���2��K�cmsy8�0��8��are�uncorrelated,��Zi.e.�&�they�dier�b�y����d�����H��n��=�UR2����2�m��1���@�.�8�The��results�presen��rted�in�this�pap�S�er�emplo�y�the�reduced�strategy�space.������If����n�����R��
�~�agen��rts�use�the�same�strategy��R�J�,��Dthen�they�will�act�as�a�`cro�wd',��Di.e.�Lthey�will�mak�e���the��same�decision.���If��n��t����������R���
�&�agen��rts�sim�ultaneously�use�the�an�ticorrelated�strategy����x����������R���
g�,��they�will���mak��re�C#the�opp�S�osite�decision�and�will�hence�act�as�an�`an�ticro�wd'�(�G�����(�R�J;����x������������R���
ҹ)).�BPIf��n�����R��
����n��t����������R������for�*all��G��.�,�(�then�the�actions�of�the�cro��rwds�and�an�ticro�wds�cancel�and�the�standard�deviation�����T:�of��the�n��rum�b�S�er��of�agen��rts�c�ho�S�osing�a�giv�en�option�(the�so-called�`attendance'�time-series����A�(�t�))���will�b�S�e�small.�3�In�con��rtrast�if��n�����R��
H���UR�n��t����������R���
΂�for�all��G��.�,��then���I(�will�b�e�large.�3�Since�there�is�no���correlation�i�b�S�et��rw�een��G�йand��G���.���2�0���g�,��peac�h�group��G�йcomprising�a�cro�wd-an�ticro�wd�pair�(�n�����R����;���n��t����������R����)�will���con��rtribute�o�to�the�attendance��A�(�t�)�via�a�separate�random�w�alk�in�time�of�step-size��j�n�����R�������I�n��t����������R�����j�.���The��ev��X�ariances�of�these�w��ralks�can�then�b�S�e�summed�to�obtain�the�standard�deviation�of��A�(�t�).���Hence��w��re�describ�S�e�the�MG�standard�deviation�using�the�follo�wing�theoretical�expression:��#0|���ya���Ë�=����UR��f^���u

cmex10�����������
#ھ2���-:�m���
����������X���"%��
�n�G�v�=1����E�������n9�2���ڍ�G������]��f^���������Z��|���Aa�cmr6�1��|��x|�fe������2����/ڹ=����UR��f^��������b�����X���
G��
�n�G�v�(�R��;����P���������R���s��)��������ō�/Ά�1��/Ά�Qm�fe����4�����6��j�n�����R��	�;�����n��t����������R�����j�����2��������f^���������Z��:U�1��:U�x|�fe������2���������{�(1)����$͔�where���b�S�oth�time-a��rv�eraging,���for���a�giv��ren�conguration�of�initial�strategies,�and�conguration-���a��rv�eraging�!Jha�v�e�b�S�een�carried�out.���W��Ve�no�w�demonstrate�that�this�cro�wd-an�ticro�wd�cancella-���tion�ʹunderlies�the�n��rumerical�results�for���;��vs.���m��[4].�W��Ve�run�the�n��rumerical�sim�ulation�of���the��)MG��and�w��rait�un�til�transien�ts�in��A�(�t�)�ha�v�e�disapp�S�eared.��A�t�timestep��t���̾0����,��Bw�e�read�out�the���n��rum�b�S�er��of�pla��ry�ers��pla�ying�eac�h�strategy��R�J�,��where��R�n��=�UR1�;����2�;��:�:�:��ʜ�2����2�m�+1���@�.�7�F��Vor�eac��rh�strategy�pair����G���=�UR(�R�J;����x������������R���
ҹ),�UNw��re�/�calculate��n�����R�� ���-V�n��t����������R���
#��at�time��t���̾0�����and�hence�obtain���n9�.���W��Ve�then�a�v�erage�this����1�o�v�er���1000�7 timesteps�to�sim��rulate�the�time-a�v�eraging.��W��Ve�ha�v�e�c�hec�k�ed�that�our�results�are�insensi-���tiv��re���to�the�precise�time-a�v�eraging�pro�S�cedure.���Finally��V,�(3w�e�a�v�erage�o�v�er�16�runs�to�sim�ulate�the���conguration-a��rv�eraging.�{Figure�tx1�compares�the�resulting�time�and�conguration-a��rv�eraged�tx��������3����������7g����xg��with��that�obtained�from�the�n��rumerical�MG��sim�ulation.��.The�agreemen�t�is�v�ery�go�S�o�d��for�all���[��m�,�ׅ�s��&�and��N��
�(not�sho��rwn).�qYW��Ve�conclude�that�the�cro�wd-an�ticro�wd�cancellation�can�indeed���quan��rtitativ�ely��explain�the�n��rumerical�results�of�Ref.�[4].������W��Ve�V�need�expressions�for�the�n��rum�b�S�er�V�of�agen��rts�using�eac�h�strategy��V,���i.e.�	|��f�n�����R����g�.�Since���the�M�lab�S�els��R�g*�are�arbitrary�in�Eq.�	b�(1),���the�ordering�of�strategies��f�n�����R����g��has�no�particular���signicance.��A��rt�ߓan�y�particular�time��t���̾0����,��these�2����2�m�+1���ӹstrategies�can�b�S�e�rank�ed�according�to���their�Evirtual�p�S�oin��rts�b�y�a�sort-op�S�eration��acting�on�the�list��f�n�����R����g�.�ǸHence��f�n�����R���g�����������g	��Z�7!�����:f�n��������S�g����where������is�the�virtual-p�S�oin��rt�rank�lab�el�with����#�=�1���b�eing�the�highest�scoring�strategy�and����f�n��������S�g����n������=1�����;���n������=2���;��:�:�:��ʜn�����=�2������m�+1���� 
�.�ɿAnother�ŝuseful�metho�S�d�of�ordering�is�ac��rhiev�ed�ŝb�y�ranking���strategies����f�n�����R����g��at�time��t���̾0��	��according�to�their�p�S�opularit��ry��V.�H�In�particular,�1Qstrategy��r�e��=�"1�is���dened���as�the�strategy�whic��rh�is�b�S�eing�used�b�y�the�largest�n�um�b�S�er�of�agen�ts,���strategy��r���=�cV2���is�VEb�S�eing�used�b��ry�the�second�largest�n�um�b�S�er�of�agen�ts,�s�etc.�jW��Ve�denote�the�p�S�opularit�y�ranking���b��ry��o�f�n�����r���b�g��where��f�n�����r���g�����n�����r�<r�=1��n��;���n�����r�<r�=2���;��:�:�:��ʜn����r�<r�=�2������m�+1������.�H5Note��othat��f�n�����r���b�g��can�b�S�e�obtained�from��f�n�����R����g����and�"hence��f�n��������S�g��b��ry�sort�op�S�erations,�/�i.e.����f�n�����R����g��������eW�	��g	�����7!����g&f�n�����r���b�g��and�hence��f�n��������g�����������g	�����7!����g&f�n�����r���b�g�.���Eac��rh�agen�t���pla��rys��Bthe�a�v��X�ailable�strategy�ha�ving�highest�virtual�p�S�oin�ts;��this�allo�ws�an�analytic�expression���to���b�S�e�obtained�for�the�probabilit��ry�that�an�agen�t�pla�ys�a�giv�en�strategy�for�general��s�,���whic�h���in��turn�yields��#�	���|���n�����r��紹=�UR�N����@��f^���������X��f^����
�v�1����������ō��۹(�r��6���1)���۟Qm�fe#MD���F2������m�+1���������(^R��f^������-�p��*��s��4�T�������f^������ƹ1��������ō�
n��r���۟Qm�fe�<���2������m�+1����������J��f^������#h��*��s�����'����f^����������|�(2)�����where��փ�����P����*���d��2���-:�m�+1����̍�d��r�<r�=1���&{��n�����r��	y(�=����N�g�as�փrequired.��pSince�agen��rts�are�discrete�ob��jects,�zthe�sim�ulation�tends���[�to�m�pro�S�duce�discrete�steps�in�the�curv��res�of��n�����r����as�a�function�of��r��.���This�eect�b�ecomes�more���pronounced��as��m��increases�since�the�total�n��rum�b�S�er��of�strategies�2����2�m�+1���ɹthen�exceeds�the�p�op-���ulation��size��N�@�.�S�W��Ve�therefore�con��rv�ert��the�theoretical��n�����r�����v��X�alues�of�Eq.�(2)�to�an�in��rteger.�F��Vor���large��a�m��suc��rh�that�2����2�m�+1��@P��_�N�@�,���the�resulting�theoretical�v��X�alues�are�t�ypically��n�����r���r��_�1�for�small����r���and����n�����r��	*�=���0�for��r��>�N�@�.�r�Figure�2�compares�the�theoretical�v��X�alues�of��n�����r��	:��calculated�using���Eq.���(2)� �with��s����=�2� �and��N��=���101,�.�to�n��rumerical�v��X�alues�tak�en�from�the�MG� �sim�ulation.���The���agreemen��rt��is�go�S�o�d.������F��Vor��;the�virtual-p�S�oin��rt�ordered�list��f�n��������S�g�,��Qthe�strategy������2�0��#��=�UR2����2�m�+1��b/�+���1������;�is��always��an�ticor-������4�����!����7g����xg��related�I�to�the�strategy���,�a�i.e.�V������2�0��Ū����	׹����q����
�.�Hence�I�kno��rwledge�of�the�sort�op�S�eration��completely���[�determines��where�eac��rh�strategy's�an�ticorrelated�partner�is�lo�S�cated�in�the�p�opularit��ry-ordered���list�hW�f�n�����r���b�g�.���Since�w��re�are�here�only�in�terested�in�time-a�v�eraged�and�run-a�v�eraged���n9�,���w�e�only���need�}to�consider�the�probabilit��ry�distribution�of�lo�S�cations�of����(����r���
��in�the�p�opularit��ry-ordered�list����f�n�����r���b�g�.��W��Ve�/�therefore�replace�the�sort�op�S�eration��b��ry�a�probabilit�y�function��P��ƹ(�r��S����2�0����=���Q�����S�r���	jl�)�whic�h���giv��res�xthe�probabilit�y�that�an�y�strategy��r��S����2�0��9?�is�the�an�ti-correlated�partner�of�strategy��r�k�in�the���list���f�n�����r���b�g�.�8�Hence�Eq.�(1)�b�S�ecomes��#�	���x����Ë�=����UR��f^����������ō�	ϣ�1��	ϣ�Qm�fe����2������������о2���-:�m�+1���
����w�����X���ҁ�����r�<r�=1���������)y�2���-:�m�+1���
���,�������X���G ��*��r��<r�����q�%cmsy6�0���9�=1��������ō�AD-�1��AD-�Qm�fe����4�����HW\�j�n�����r��=
�����n�����r��<r�����0���D)�j�����2����P��ƹ(�r��S�����0��w�=��������UR�r����k�)�����f^���������Z��zQ�1��zQ�x|�fe������2���������|�(3)�����where�fpthe�factor�����Fu�����1�����콉fe@��'�2�����sJ�discoun��rts�double-coun�ting.�	�9There�are�t�w�o�limiting�cases.�	�9When�the���[�virtual-p�S�oin��rt��ordered�list��f�n��������S�g��and�the�p�opularit��ry-ordered�list��f�n�����r���b�g��are�iden�tical,�Jthen��P��ƹ(�r��S����2�0��w�=�����������r�����)��will�b�S�e�a���s2�-function�at��r�����2�0��w�=�UR2����2�m�+1����+��1����r�㥹and��hence�Eq.��(3)�has�the�same�form�as�Eq.�(1).���In���the�opp�S�osite�case�where�the�t��rw�o���ordered�lists�are�uncorrelated,��t�P��ƹ(�r�����2�0��w�=��������UR�r����k�)�should�b�e�a�
at���distribution.�*�In���eac��rh�case,��`Eqs.�(2)�and�(3)�can�b�S�e�com��rbined�to�obtain�closed-form�analytic���solutions��for�arbitrary��s��and��N�@�.������Figure��F3�sho��rws��P��ƹ(�r��S����2�0���Թ=���
�����
�r���
&&�)�for��r�ڛ�=��
1�as�a�function�of��r��S����2�0��!ǹ,��-tak�en�from�the�n�umerical�MG���sim��rulation���at��m�UR�=�2�;����5���and�10.��F��Vor�small��m��(�m�UR�=�2)���the�an�ticorrelated�strategy�to�the�most���p�S�opular���strategy�(i.e.����r��]�=���1)�is�at��r�����2�0��͖�=���2����2�m�+1���@�,��,i.e.���it�is�the�least�p�opular�strategy��V.���Hence����P��ƹ(�r��S����2�0��w�=��������UR�r����k�)��resem��rbles�the���s2�-function�limiting�case�men�tioned�ab�S�o�v�e.��F��Vrom�Fig.�2�w��re�kno�w�that���v��rery�&few�agen�ts�will�therefore�pic�k�this�an�ticorrelated�strategy��V.��ZHence�the�cro�wd-an�ticro�wd���cancellation��Iwill�b�S�e�small�and���_��will�b�e�large,�2�as�can�b�e�seen�in�Fig.�L�1.�As��I�m��increases���(�m��>�=�5)�A�a�remark��X�able�eect�o�S�ccurs:��the�p�eak�in��P��ƹ(�r�����2�0���=���o�����>�r���	�W�)�mo��rv�es�A�up�to��rw�ard�A��r�<̹=��>1.�=�Hence���b�S�oth����r��۹=��M1�and�its�an��rticorrelated�partner���'p����r���ࣹare�no�w�v�ery�p�S�opular.�[8Whereas�for��m��M�=�2���it���seemed���lik��re�there�w�as�an�eectiv�e�`repulsion'�b�S�et�w�een��r��P�and���*m����r���
B۹,��	for��m��c�=�5���this�no�w�seems���more��lik��re�an�attraction.���Am�usingly��V,�#Uthe�shap�S�e�of��P��ƹ(�r�����2�0���F�=���)*�����r���	A��)�for��m���=�5��is�reminiscen��rt�of�the���screening��Zeect�of�a�negativ��re�c�harge�cloud�around�a�p�S�ositiv�e�c�harge�placed�at��r���=�UR1,��6or�ev�en���a���b�S�ound�electron-hole�pair�(i.e.�8�exciton)�with�the�cro��rwd�(an�ticro�wd)�pla�ying�the�role�of�the���p�S�ositiv��re���(negativ�e)�c�harge.�?kF��Vor�large��m��(�m�{��=�10),�·the�abilit��ry�of�the�an�ticro�wd�to�`screen'������5���ԋ0����7g����xg��the��Ncro��rwd�has�decreased�yielding�a�rather�
at�distribution�as�sho�wn.�k�The�consequence�of���[�this�a�strong�cro��rwd-an�ticro�wd�a�correlation�whic��rh�app�S�ears�as��m��increases,�|�is�that�the�cro�wd�and���an��rticro�wd�_�b�S�ecome�comparable�in�size.��mHence�����is�small�for��m�����5��q���6,�}#in�_�agreemen��rt�with���Fig.��B1.�Note�sthat�the�MG�icannot�fully�`optimize'�itself�b��ry�building�equal-sized�cro�wds�and���an��rticro�wds.�JIn��mo�S�died�mo�dels�of�MG�[11]�where�this�in-built�frustration�in�the�strategy���space��is�allo��rw�ed��to�relax,�equal-sized�cro��rwds�and�an�ti-cro�wds�do�naturally�emerge.������W��Ve���no��rw�consider�analytic�expressions�for���9�for�general��s��using�Eqs.��_(2)�and�(3).�F��Vor���small�C��m�,�ethe�virtual-p�S�oin��rt�ordered�list��f�n��������S�g��and�the�p�opularit��ry-ordered�list��f�n�����r���b�g��will�b�e�v��rery���similar,�hence���P��ƹ(�r��S����2�0�����=����������r���	5�)����������r��<r�����0���9�;�2������m�+1��W�+1��r��3�
�.���The�discreteness�of�the�agen��rts�will�b�S�e�unimp�ortan��rt���since���n�����r�����UR�1,�hence��n�����r��}
�can�b�S�e�treated�as�con��rtin�uous.�8�Equations��(2)�and�(3)�yield��"���cTX�����̾lo�Îw���{����m�������蕹=����������ō�����N������Qm�fe
�����d͹2���������qk��f^���������������2���-:�m���
����������X���ҁ������r�<r�=1��������c��f^����������f^�����J��1����������ō����r��6���1���۟Qm�fe)�����@2������m�+1���������:ʟ�f^������&�>��*��s��-�"�������f^�����
�1��������ō�
n��r���۟Qm�fe�<���2������m�+1����������J��f^������%.���*��s�����#������ao������f^����������ō� ��r�����Qm�fe�<���2������m�+1���������"���f^������)����*��s��0�n�+��������f^����������ō��a�r��:O�Qm�fe�<���2������m�+1���������%.���f^������,�2��*��s�������f^�����8U�1����������ō��۹1���۟Qm�fe����� r�r��������
�
��f^������M~��*��s���������f^������؟�*��2�����$����f^���������Z��+'տ1��+'՟x|�fe������2����8Z��:��������|�(4)�����"F��Vor���s�UR�=�2�this�b�S�ecomes������GB�����̾lo�Îw���{����m��摹=������ō�2{�N�����Qm�fe-���	[��������p���
����z����	�l��3�����ʦ2������L䍑33�m��33�x|�fe�������r��2������d���.�+1���������3�:��f^�����9X�1������2������2(�m�+1)�����$Z4��f^���������Z��*ԅ�1��*ԅ�x|�fe������2����8��:������{�(5)�����Figure���4�sho��rws�these�analytic�curv�es�for��s�UR�=�2���and��s�UR�=�4���(solid�lines�monotonically�decreas-���[�ing).��As�_migh��rt�b�S�e�exp�ected�using�the�extreme���s2�-function�form�for��P��ƹ(�r�����2�0��w�=��������UR�r����k�),�C;these�curv��res�are���sligh��rtly���higher�than�the�n�umerical�results�in�Fig.�BV1�for�small��m�.�No��rw�consider�the�opp�S�osite���extreme�H|of�uncorrelated��r��S����2�0��jC�and����'����r���	畹,�_�i.e.�R]the�
at�distribution��P��ƹ(�r��S����2�0��Ϲ=���{������r���	�!�)�����2����2��(�m�+1)�� 0�.�F��Vor�H|�s��=�2���this��giv��res��"���.j�����̾lo�Îw���{����m��摹=������ō�KT�N�����Qm�fe2/3�:���������p���
����z����	�l��3�����ʦ2����x���33�(�m�+3)��33�Lʉfe�+�������2�����������7���f^�����=2	�1������2������2(�m�+1)�����$Z4��f^���������Z��*ԅ�1��*ԅ�x|�fe������2����8��:������|�(6)�����Equation�q�(6)�t��rypically�pro�S�duces�lo�w�er�estimates�for�eac�h��s��v��X�alue�(dashed�lines).��V��Values�of���[���Hùobtained�ڊfrom�separate�n��rumerical�runs�tend�to�b�S�e�scattered�in�the�region�of�these�curv�es.���F��Vor��larger��m��(�m�Z�>��6)��w��re�cannot�ignore�the�discreteness�of�the�agen�ts�(Fig.���2).�In��this���regime,���n�����r�����UR�1��tfor��r���<�N��X�while��n�����r��紹=�0�for��r���>�N�@�.�yUsing�the�in��rteger�form�of�Eq.�(2)�for�high����m�,��and�the�
at�distribution�for��P��ƹ(�r��S����2�0��w�=��������UR�r����k�),�yields������6���J�?�����7g�����A������������̾high�������m��S�=������ō���������p��������؉z�
���
(��N�������Qm�fe�����dι2��������eP��f^������n�1����������ō�
��N���۟Qm�fe�<���2������m�+1����������J��f^���������Z��$L��1��$L��x|�fe������2����-��:������|�(7)����#�[�This�mexpression�approac��rhes�the�coin-toss�limit�from�b�S�elo�w�as��m�_{�!�1�,�jas�msho�wn�in�Fig.���[�4�p�(solid�line�monotonically�increasing).�˲Within�the�appro��rximation�used�here,���this�curv�e�is���insensitiv��re���to��s�.�?�Note�that�the�n�umerical�MG��dresults�are�also�consisten�t�with�this�nding���of�7w��reak��s�-dep�S�endence�for�large��m�.���Hence�Fig.�4�giv��res�a�clear�picture�of�what�happ�S�ens�to������
�as�>��s��and��m��increase:��8considering�the�monotonically�decreasing�curv��re�for�lo�w��m�,�S�and�the���monotonically��'increasing�curv��re�for�high��m�,�ħw�e�see�that�(a)�there�should�b�S�e�a�minim�um�in������for�3,�s����=�2,�EM(b)�this�minim��rum�should�mo�v�e�to�higher��m��as��s��increases�and�(c)�the�minim�um���should��b�S�ecome�shallo��rw�er��as��s��increases.���Eac��rh�of�these�statemen�ts�agrees�with�n�umerical���sim��rulation��Uresults�(c.f.�#�Fig.�1).�In��Uaddition,��@the�curv�e������̾high�������m�� i��!�k�0�at��N��ι=�2����2�m�+1���@�,��@i.e.�#�for����m�UR���5������6.������W��Ve�Ńno��rw�compare�the�theoretical�cro�wd-an�ticro�wd�calculation�(Eq.�,~(3))�with�the�n�umer-���ical��Bsim��rulation.�=�The�most�in�teresting�case�is��s�X
�=�2.�=�Figure��B5�sho�ws�the�spread�of�n�umerical���v��X�alues��for�dieren��rt�runs�(op�S�en�circles)�compared�to�theory�(solid�circles).�8+The�agreemen�t�is���go�S�o�d.��The�N�appropriate�analytic�expressions�for�the�probabilit��ry�function��P��ƹ(�r��S����2�0��w�=��������UR�r����k�)�in�Eq.�(3)���in��rv�olv�e��+m�ultiple�sums�and�are�complicated:�7�w�e�therefore�obtained�the�results�for�eac�h��m��in���Fig.��5�Qb��ry�generating�the�corresp�S�onding��P��ƹ(�r�����2�0���_�=���C���}��r���	��)�forms�to�those�in�Fig.��3.�The�Qtheoretical���p�S�oin��rts��<tend�to�lie�in�b�et��rw�een��<the�limiting�curv��res�of�Fig.���4��exc��ffept��at�the�minim�um�where���the�F�remark��X�able�form�for��P��ƹ(�r��S����2�0��!�=���y����Z�r���	�s�)�(recall�Fig.�M�3)�pulls�the�theoretical�v�alue�sligh��rtly�b�S�elo�w���the�0�cruder�limiting�curv��res�of�Fig.��4.�Elsewhere�0�w�e�will�discuss�simpler�closed-form�expres-���sions�*for��P��ƹ(�r��S����2�0����=���G�����'�r���	`@�),�9�together�with�an�analysis�of�the�time-series��A�(�t�)�and�history�bit-string���statistics��within�the�cro��rwd-an�ticro�wd��mo�S�del�[12].������In�@summary�w��re�presen�ted�an�analytic�analysis�of�cro�wding�eects�in�MG�6whic�h�oers�a���no��rv�el��}explanation�of�the�main�nding�of�Ref.�[4].�P`F��Vuture�w��rork�will�explore�p�S�ossible�connec-���tions��to�the�spin-glass�formalism�of�Challet��et�35al��[5].������W��Ve��thank�T.S.�Lo,�J.P�.�Garrahan,�D.�Sherrington�and�D.�Challet�for�discussions.������7���6�O�����7g����xg�����REFERENCES��$�[�������[1]���GW.B.��Arth��rur,�Science����N�cmbx12�284�,�107�(1999).���[������[2]���GH.E.��Stanley��V,�Computing�in�Science�&�Engineering�Jan/F�eb,�76�(1999).��������[3]���GD.��Challet�and�Y.C.�Zhang,�?-Ph��rysica�A����246�,�407�(1997);��H�ibid.��256�,�514�(1998);��H�ibid.���[��G�269�,��30�(1999).��������[4]���GR.��Sa��rvit,�R.�Man�uca�and�R.�Riolo,�Ph�ys.�Rev.�Lett.��82�,�2203�(1999).��������[5]���GD.�2Challet�and�M.�Marsili,���Ph��rys.�Rev.�E�1��60�,�R6271�(1999);���D.�Challet,�M.�Marsili,����Gand��,R.�Zecc��rhina,���Ph�ys.��,Rev.�Lett.��84�,�1824�(2000);�6�D.�Challet�and�M���Marsili,�cond-����Gmat/9908480.��������[6]���GA.��0Ca��rv��X�agna,��I.�Giardina,�J.P��V.�Garrahan�and�D.�Sherrington,�Ph��rys.�Rev.�Lett.��83�,�4429����G(1999).��������[7]���GR.��D'Hulst�and�G.J.�Ro�S�dgers,�Ph��rysica�A��270�,�514�(1999).��������[8]���GA.��Ca��rv��X�agna,�Ph�ys.�Rev.�E��59�,�R3783�(1999).��������[9]���GN.F.��RJohnson,�,�P��V.M.�Hui,�D.�Zheng�and�M.�Hart,�J.�Ph��rys.�A:�Math.�Gen.��32��L427�(1999).�����[10]���GN.F.��*Johnson,��M.�Hart�and�P��V.M.�Hui,�Ph��rysica�A��&�269�,�1�(1999).�This�conference�pap�S�er����Gpro��rvides��a�preliminary�rep�S�ort�of�the�qualitativ�e�eects�of�cro�wding.�����[11]���GN.F.��Johnson,�P��V.M.�Hui,�R.�Jonson�and�T.S.�Lo,�Ph��rys.�Rev.�Lett.��82�,�3360�(1999).�����[12]���GP��V.��Jeeries,�M.�Hart,�N.F.�Johnson�and�P�.M.�Hui,�in�preparation.������8���	^�	[Ԡ���7g����xg���r��FIGURES��h�����lϼFIG.�V�1.��"Standard�hdeviation��0�b>
�3
cmmi10��̖�for�the�Minorit��!y�Game�as�a�function�of�memory-size��m��for���[��s��=�2�;��1�3�;��4�:"strategies�p�M�er�agen��!t�and��N�2�=��101�agen�ts.��Solid�curv�e:�Vn�umerical�sim�ulation.��Dashed���curv��!e:��+cro�wd-an�ticro�wd��theory�using�Eq.�	1Q(1).�Random��(coin-toss)�limit����x�=����q�����1!",�
�3
cmsy10�p���������p 	��	?J��N�������=�2�q�=�5�:�0��is���indicated.���Q5���J��l�FIG.��2.�$�Histograms�
]of�the�n��!um�b�M�er�
]of�agen��!ts�using�strategy��r�X;�for��r��ȼ=�[�1�(most�p�opular)�to���[��r����=�=�2�����m�+1���=�(least���p�M�opular).�9�Results�are�sho��!wn�for��m��=�2�(left�scale)�and��m��=�7�(righ��!t�scale).�9�Solid���lines:���n��!umerical��fsim�ulation.�Dashed��flines:�theory�from�Eq.�(2).���l%獟�l�FIG.��<3.�NProbabilit��!y�Wfunction��P��V�(�r��Mޟ���0��M�=�������1��r���	p^�)�giving�the�probabilit�y�that�the�strategy�rank�ed��r��Mޟ���0��s��on���[�the�q�p�M�opularit��!y-ordered�list,��Wis�an�ti-correlated�with�the�strategy�rank�ed��r�M޼.�?RResults�are�sho�wn�for����r��U�=�uw1��}(i.e.��"most�p�M�opular�strategy)�as�a�function�of��r������0����for��m�uw�=�2��}(dotted-dashed),����m��=�5�(dotted)���and��f�m�
��=�10�(solid).����s��=�2�and��N�<F�=�101.���Note�that����C0�P���4���8�r��<r�����0���K��P��V�(�r��Mޟ���0��&��=���������r���I5�)�=�1.�����
������l�FIG.�H�4.�y�Theoretical�~Mcurv��!es�for�����using�Eqs.�{*(4)-(7).�Monotonically�~Mdecreasing�curv�es�for��s�
��=�2�;��1�4���[�at�m�lo��!w��m��(�m�
�<��6):���solid�m�lines�corresp�M�ond�to���j�-function��P��V�(�r������0��&��=��������
��r���I5�)�distribution�neglecting�agen��!t�dis-���creteness,�;�dashed� �lines�corresp�M�ond�to�
at�distribution�neglecting�agen��!t�discreteness.��TMonotonically���increasing��solid�line�for�large��m��(�m�bT>��6)��is�indep�M�enden��!t�of��s�:�Git�corresp�onds�to�a�
at�distribution���and��faccoun��!ts�for�agen�t�discreteness.���;Vҍ�����l�FIG.�H�5.�y�Theoretical��cro��!wd-an�ticro�wd�calculation�(solid�circles)�vs.��\n�umerical�sim�ulations�(op�M�en���[�circles)��ffor��s�
��=�2,��f�N�<F�=�101.���16�n��!umerical�runs�are�sho�wn�for�eac�h��m�.��������9���on��V@>�rTEX"*FMT.PREC:DVI2
F����T����Z�R���d�P�� ��T���� �Pp�� ��U��� �S�� 6�Q�� #��S�� 2��P��� BZ�V�� R2�S��� ^��UD	�� d��R�
cond-mat0003486.extracted_bib
\begin{thebibliography}{99}
\bibitem{arthur} W.B. Arthur, 
Science {\bf 284}, 107 (1999).
\bibitem{stanley} H.E. Stanley, Computing
in Science \& Engineering Jan/Feb, 76 (1999).
\bibitem{challet} D. Challet and Y.C. Zhang, Physica A {\bf 246}, 407
(1997);
{\em ibid.} {\bf 256}, 514 (1998); {\em ibid.} {\bf 269}, 30 (1999).
\bibitem{savit} R. Savit, R. Manuca and R. Riolo, Phys. Rev. Lett.  {\bf
82}, 2203
(1999).
\bibitem{spinglass} D. Challet and M. Marsili, Phys. Rev. E {\bf 60}, R6271
(1999); D. Challet, M. Marsili, and R. Zecchina,
Phys. Rev. Lett. {\bf 84}, 1824 (2000); D. Challet and M Marsili,
cond-mat/9908480.
\bibitem{sherrington} A. Cavagna, I. Giardina, J.P. Garrahan and D.
Sherrington,
Phys. Rev. Lett. {\bf 83}, 4429 (1999).
\bibitem{dHR} R. D'Hulst and G.J. Rodgers, Physica A {\bf 270}, 514 (1999).
\bibitem{cavagna} A. Cavagna,
Phys. Rev. E {\bf 59}, R3783 (1999).
\bibitem{us} N.F. Johnson, P.M. Hui, D. Zheng and M. Hart,
J. Phys. A: Math. Gen. {\bf 32} L427 (1999).
\bibitem{crowd} N.F. Johnson, M. Hart and P.M. Hui, Physica A {\bf 269}, 1
(1999). This conference paper provides a preliminary report of the
qualitative effects
of crowding.
\bibitem{prl} N.F. Johnson, P.M. Hui, R. Jonson and T.S. Lo,  Phys. Rev.
Lett. {\bf 82}, 3360 (1999).
\bibitem{long} P. Jefferies, M. Hart, N.F. Johnson and P.M. Hui, in
preparation.

\end{thebibliography}