# Statistical mechanics of systems with heterogeneous agents: Minority Games

\[

## Abstract

We study analytically a simple game theoretical model of heterogeneous interacting agents. We show that the stationary state of the system is described by the ground state of a disordered spin model which is exactly solvable within the simple replica symmetric ansatz. Such a stationary state differs from the Nash equilibrium where each agent maximizes her own utility. The latter turns out to be characterized by a replica symmetry broken structure. Numerical results fully agree with our analytic findings.

\]

Statistical mechanics of disordered systems provides analytical and numerical tools for the description of complex systems, which have found applications in many interdisciplinary areas. When the precise realization of the interactions in an heterogeneous system is expected not to be crucial for the overall macroscopic behavior, then the system itself can be modeled as having random interactions drawn from an appropriate distribution. Such an approach appears to be very promising also for the study of systems with many heterogeneous agents, such as markets, which have recently attracted much interest in the statistical physics community . Indeed it provides a workable alternative to the so called representative agent approach of micro-economic theory, where assuming that agents are identical, one is lead to a theory with one single (representative) agent.

In this Letter we present analytical results for a simple model of heterogeneous interacting agents, the so called minority game (MG), which is a toy model of $`N`$ agents interacting through a global quantity representing a market mechanism. Agents aim at anticipating market movements by following a simple adaptive dynamics inspired at Arthur’s inductive reasoning. This is based on simple speculative strategies that take advantage of the available public information concerning the recent market history, which can take the form of one of $`P`$ patterns. Numerical studies  have shown that the model displays a remarkably rich behavior. The relevant control parameter turns out to be the ratio $`\alpha =P/N`$ between the “complexity” of information $`P`$ and the number $`N`$ of agents, and the model undergoes a phase transition with symmetry breaking independently of the origin of information.

We shall limit the discussion on the interpretation of the model – which is discussed at some length in refs.  – to a minimum and rather focus on its mathematical structure and to the analysis of its statistical properties for $`N1`$. Our main aim is indeed to show that the model can be analyzed within the framework of statistical mechanics of disordered system.

We find that dynamical steady states can be mapped onto the ground state properties of a model very similar to that proposed in ref. in the context of optimal dynamics for attractor neural networks. There one shows that the minimization of the interference noise is equivalent to maximizing the dynamical stability of each device composing the system. Conversely, we show that the individual utility maximization in interacting agents systems is equivalent to the minimization of a global function. We also find that different learning models lead to different patterns of replica symmetry breaking.

The model is defined as follows: Agents live in a world which can be in one of $`P`$ states. These are labelled by an integer $`\mu =1,\mathrm{},P`$ which encodes all the information available to agents. For the moment being, we follow ref.  and assume that this information concerns some external system so that $`\mu `$ is drawn from a uniform distribution $`\varrho ^\mu =1/P`$ in $`\{1,\mathrm{},P\}`$. Each agent $`i=1,\mathrm{},N`$ can choose between one of two strategies, labeled by a spin variable $`s_i\{\pm 1\}`$, which prescribes an action $`a_{s_i,i}^\mu `$ for each state $`\mu `$. Strategies may be “look up tables”, behavioral rules  or information processing devices. The actions $`a_{s,i}^\mu `$ are drawn from a bimodal distribution $`P(a_{s,i}^\mu =\pm 1)=1/2`$ for all $`i,s`$ and $`\mu `$ and they will play the role of quenched disorder. Hence there are only two possible actions – such as “do something” ($`a_{s,i}^\mu =1`$) or “do the opposite” ($`a_{s,i}^\mu =1`$). It is convenient to make the dependence on $`s`$ explicit in $`a_{s,i}^\mu `$, introducing $`\omega _i^\mu `$ and $`\xi _i^\mu `$ so that $`a_{s,i}^\mu =\omega _i^\mu +s\xi _i^\mu `$. If agent $`i`$ chooses strategy $`s_i`$ and her opponents choose strategies $`s_i\{s_j,ji\}`$, in state $`\mu `$, she receives a payoff

$$u_i^\mu (s_i,s_i)=a_{s_i,i}^\mu G(A^\mu ),$$
(1)   
where, defining $`\mathrm{\Omega }^\mu =_j\omega _j^\mu `$,

$$A^\mu =\underset{j}{}a_{s_j,j}^\mu =\mathrm{\Omega }^\mu +\underset{j}{}\xi _j^\mu s_j.$$
(2)   
The function $`G(x)`$, which describes the market mechanism, is such that $`xG(x)>0`$ for all $`x`$ so that the total payoff to agents is always negative: the majority of agents receives a negative payoff whereas only the minority of them gain. Note that the agent–agent interaction, which comes from the aggregate quantity $`G(A^\mu )`$, is of mean-field character.

The game defined by the payoffs in Eq. (1) can be analyzed along the lines of game theory by looking for its Nash equilibria in the strategies space $`\{s_j,j=1,\mathrm{},N\}`$. Before doing this, we prefer to discuss the dynamics of inductive agents following refs. : There, the game is repeated many times and agents try to estimate empirically which of the two strategies they have is the best one, using past observations. More precisely, each agent $`i`$ assigns a score $`U_{s,i}(t)`$ to her $`s^{\mathrm{th}}`$ strategy at time $`t`$, and we assume, as in ref. , that she chooses that strategy with probability

$$\pi _{s,i}(t)\mathrm{Prob}\{s_i(t)=s\}=Ce^{\mathrm{\Gamma }U_{s,i}(t)}$$
(3)   
with $`C^1=_s^{}e^{\mathrm{\Gamma }U_{s^{},i}(t)}`$ and $`\mathrm{\Gamma }>0`$. The scores are initially set to $`U_{s,i}(0)=0`$, and they are updated as

$$U_{s,i}(t+1)=U_{s,i}(t)a_{s,i}^{\mu (t)}G(A^{\mu (t)})/P.$$
(4)   
The idea is that if a strategy $`s`$ has predicted the right sign i.e. if $`a_{s,i}^\mu =\mathrm{sign}G(A^\mu )`$, its score, and hence its probability of being used, increases. Note that $`a_{s,i}^\mu G(A^\mu )`$ in Eq. (4) is not the payoff $`u_i^\mu (s,s_i)`$ which agent $`i`$ would have received if she had actually played strategy $`ss_i(t)`$. Indeed $`G(A^\mu )`$ depends on the strategy $`s_i(t)`$ that agent $`i`$ has actually played through $`A^\mu `$. Agents in the MG neglect this effect and behave as if they were facing an external process $`G(A^\mu )`$ rather than playing against other $`N1`$ agents. This may seem reasonable for $`N1`$ since the relative dependence of aggregate quantities on each agent’s choice is expected to be small. We shall see below (see Eq. 11) that this is not true: if agents consider the impact of their actions on $`A^\mu `$, the collective behavior changes considerably.

We focus on the linear case $`G(x)=x`$, which allows for a simple treatment. Other choices, such as the original one $`G(x)=\text{sign}x`$, lead to similar conclusions, as it will be discussed elsewhere. With this choice, the total losses of agents is $`_iu_i^\mu =(A^\mu )^2`$. The time average $`\sigma ^2`$ of $`(A^\mu )^2`$ is shown in Fig. 1, as a function of $`\alpha P/N`$. The system shows a complex behavior characterized, among other things, by a phase transition at $`\alpha _c0.34`$ where $`\sigma ^2`$ shows a cusp and a small $`\alpha `$ phase where $`\sigma ^2`$ increases with $`\mathrm{\Gamma }`$.

In order to uncover this behavior, let us focus on the long time behavior of the dynamics. The key observation is that, in the long run, the score of a strategy depends on its performance in all $`P`$ states. Hence, the behavior of agents will change systematically only on time-scales of order $`P`$. This suggests to introduce the rescaled time $`\tau =t/P`$. As $`P\mathrm{}`$, any finite interval $`d\tau =\mathrm{\Delta }t/P`$ is made of infinitely many time steps and we can use the law of large numbers to approximate time averages with statistical averages over the variables $`\mu (t)`$ and $`s_i(t)`$ from their respective distributions $`\varrho ^\mu `$ and $`\pi _{s,i}`$. We henceforth use the notation $`\overline{o}=_\mu \varrho ^\mu o^\mu `$ for averages over $`\mu `$ and $``$ for averages on $`s_i(t)`$ and we define $`m_i(\tau )s_i(t)`$. With this notations, $`\sigma ^2`$ reads:

$$\sigma ^2=\overline{A^2}=\overline{\mathrm{\Omega }^2}+\underset{i}{}\left[\overline{\xi _i^2}+2\overline{\mathrm{\Omega }\xi _i}m_i\right]+\underset{ij}{}\overline{\xi _i\xi _j}m_im_j$$
(5)   
where we have used statistical independence of $`s_i`$, i.e. $`s_is_j=m_im_j+(1m_i^2)\delta _{i,j}`$. The evolution of scores $`U_{s,i}`$ in continuum time $`\tau `$, is obtained iterating Eq. (4) for $`\mathrm{\Delta }t=Pd\tau `$ time steps. Using Eq. (3) in the form $`m_i=\mathrm{tanh}[\mathrm{\Gamma }(U_{+1,i}U_{1,i})]`$, we find

$$\frac{dm_i}{d\tau }=2\mathrm{\Gamma }(1m_i^2)\left[\overline{\mathrm{\Omega }\xi _i}+\underset{j}{}\overline{\xi _i\xi _j}m_j\right].$$
(6)   
This can be easily written as a gradient descent dynamics $`\frac{dm_i}{d\tau }=\mathrm{\Gamma }(1m_i^2)\frac{H}{m_i}`$ which minimizes the Hamiltonian

$$H=\overline{A^2}=\sigma ^2\underset{i}{}\overline{\xi _i^2}(1m_i^2).$$
(7)   
As a function of $`m_i`$, $`H`$ is a positive definite quadratic form, which has a unique minimum. This implies that the stationary state of the MG is described by the ground state properties of $`H`$. It is easy to see that $`H`$ is closely related to the order parameter $`\theta =\sqrt{\overline{\text{sign}A^2}}`$ introduced in , which is a measure of the system predictability. Indeed $`H\theta ^2`$ when $`\theta `$ is small, suggesting that inductive agents actually minimizes predictability rather than their collective losses $`\sigma ^2`$.

It is possible to study the ground state properties of $`H`$ in Eq. (7) using the replica method . First we introduce an inverse temperature $`\beta `$ and compute the average over the disorder variables $`\mathrm{\Xi }=\{a_{s,i}^\mu \}`$ of the partition function of $`n`$ replicas of the system, $`Z^n_\mathrm{\Xi }`$. Next we perform an analytic continuation for non-integer values of $`n`$, thus obtaining $`\mathrm{ln}Z_\mathrm{\Xi }=lim_{n0}\frac{Z^n_\mathrm{\Xi }1}{n}`$. The ‘free energy’ $`F_{ID}=\mathrm{ln}Z_\mathrm{\Xi }/\beta `$ depends on the the overlap matrix $`Q_{a,b}=m_i^am_i^b`$ ($`a,b=1,\mathrm{}n`$, $`ab`$) and on the order parameter $`Q_a=\frac{1}{N}_i(m_i^a)^2`$, together with their Lagrange multipliers $`r_{a,b}`$ and $`R_a`$ respectively. $`F_{ID}`$ can be calculated using a saddle point method that, within the replica symmetric (RS) ansatz $`Q_{a,b}=q`$, $`r_{a,b}=r`$ (for all $`a<b`$), and $`Q_a=Q`$, $`R_a=R`$ (for all $`a`$), leads to

$`F_{ID}`$ $`=`$ $`{\displaystyle \frac{\alpha }{2}}{\displaystyle \frac{1+q}{\alpha +\beta (Qq)}}+{\displaystyle \frac{\alpha }{2\beta }}\mathrm{log}\left[1+{\displaystyle \frac{\beta (Qq)}{\alpha }}\right]`$   
$`+`$ $`{\displaystyle \frac{\beta }{2}}(RQrq){\displaystyle \frac{1}{\beta }}{\displaystyle 𝑑\mathrm{\Phi }(\zeta )\mathrm{log}_1^1𝑑se^{\beta V(s|\zeta )}}`$   
where $`V(x|\zeta )=\beta (rR)\frac{x^2}{2}\sqrt{r}\zeta x`$ and $`\mathrm{\Phi }`$ is the normal distribution. The ground state properties of $`H`$ are obtained solving the saddle point equations in the limit $`\beta \mathrm{}`$. Fig. 1 compares the analytic and numerical findings for $`\sigma ^2`$. For $`\alpha >\alpha _c=0.33740\mathrm{}`$, the solution leads to $`Q=q<1`$ and a ground state energy $`H_0>0`$. $`H_00`$ as $`\alpha \alpha _c^+`$ and $`H_0=0`$ for $`\alpha \alpha _c`$.

This confirms the conclusion $`A^\mu =0`$ $`\mu `$ (or $`\theta =0`$) for $`\alpha \alpha _c`$ and it implies the relation

$$\sigma ^2=\underset{i}{}\overline{\xi _i^2}(1m_i^2)\frac{N}{2}(1Q),\alpha \alpha _c.$$
(8)   
The RS solution is stable against replica symmetry breaking (RSB) for any $`\alpha `$, as expected from positive definiteness of $`H`$. Following ref., we compute the probability distribution of the strategies, which for $`\alpha >\alpha _c`$ is bimodal and it assumes the particularly simple form

$$𝒫(m)=\varphi (z)[\delta (m1)+\delta (m+1)]+\frac{z}{\sqrt{2\pi }}e^{(zm)^2/2}$$
(9)   
with $`z=\sqrt{\alpha /(1+Q)}`$ ($`Q`$ taking its saddle point value) and where $`\varphi (z)=(1\mathrm{Erf}(z/\sqrt{2}))/2`$ is the fraction of frozen agents (those who always play one and the same strategy). Below $`\alpha _c`$, $`𝒫(m)`$ is continuous, i.e. $`\varphi =0`$ in agreement with numerical findings.

At the transition the spin susceptibility $`\chi =lim_\beta \mathrm{}\beta (Qq)`$ diverges as $`\alpha \alpha _c^+`$ and it remains infinite for all $`\alpha \alpha _c`$. This is because the ground state is degenerate in many directions (zero modes) and an infinitesimal perturbation can cause a finite shift in the equilibrium values of $`m_i`$. This implies that in the long run, the dynamics (6) leads to an equilibrium state which depends on the initial conditions $`U_{s,i}(t=0)`$. The under-constrained nature of the system is also responsible for the occurrence of anti-persistent effects for $`\alpha <\alpha _c`$. The periodic motion in the subspace $`H=0`$ is probably induced by inertial terms $`d^2U_{s,i}/d\tau ^2`$ which we have neglected, and which require a more careful study of dynamical solutions of Eqs. (3,4). It is however clear that the amplitude of the excursion of $`U_{+1,i}(t)U_{1,i}(t)`$ decreases with $`\mathrm{\Gamma }`$, by the smoothing effect of Eq. (3). When this amplitude becomes of the same order of $`1/\mathrm{\Gamma }`$ anti-persistence is destroyed, which explains the sudden drop of $`\sigma ^2`$ with $`\mathrm{\Gamma }`$ found in ref. .

A natural question arises: is this state individually optimal, i.e. is it a Nash equilibrium of the game where agents maximize the expected utility $`\overline{u_i}=\overline{a_{s,i}A}`$? One way to find the Nash equilibria is to consider stationary solutions of the multi-population replicator dynamics. This takes the form of an equation for the so called mixed strategies, i.e. for the probabilities $`\pi _{s,i}`$ with which agent $`i`$ plays strategy $`s`$. In terms of $`m_i=\pi _{+,i}\pi _{,i}`$, with a little algebra, these equations  read

$$\frac{dm_i}{d\tau }=(1m_i^2)\frac{\overline{u_i}}{m_i}.$$
(10)   
Observing that $`\frac{\overline{u_i}}{m_i}=\frac{\sigma ^2}{m_i}`$, we can rewrite Eq. (10) as a gradient descent dynamics which minimizes a global function which is exactly the total loss $`\sigma ^2`$ of agents. Nash equilibria then correspond to the local minima of $`\sigma ^2`$ in the domain $`[1,1]^N`$. The quadratic form $`\sigma ^2`$ is not positive definite, which means that there shall be many local minima and the Nash equilibrium is not unique. It is easy to see  that Nash equilibria are in pure strategies, i.e. $`m_i^2=1`$ $`i`$, which implies $`\sigma ^2=H`$, by Eq. (7). A detailed characterization of the Nash equilibria shall be given elsewhere. The best Nash equilibrium can be studied applying the replica method to $`\sigma ^2`$ for $`\beta \mathrm{}`$. The multiplicity of Nash equilibria (meta-stable states) manifests itself in the occurrence of replica symmetry breaking for any $`\alpha >0`$ with a non-vanishing $`\sigma ^2/N`$ . The simple RS solution, though incorrect, provides a close lower bound $`F_{NE}^{(RS)}=F_{ID}+\frac{1}{2}(1Q)`$ to $`\sigma ^2/N`$ for $`\beta \mathrm{}`$ (see Fig. 1). For $`\alpha >1/\pi `$, we have $`Q=q=1`$ and $`F_{NE}^{(RS)}(\beta =\mathrm{})=[11/\sqrt{\pi \alpha }]^2`$ positive, whereas $`1=Q<q`$ and $`F_{NE}^{(RS)}=0`$ for $`\alpha <1/\pi `$.

Fig. 1 shows that in a Nash equilibrium agents perform way better than in the MG. This is the consequence of the fact that agents do not take into account their impact on the market (i.e. on $`A^\mu `$) when they update the scores of their strategies by Eq. (4). It is indeed known that reinforcement-learning dynamics based on Eq. (3) is closely related to the replicator dynamics and hence it converges to rational expectation outcomes, i.e. to Nash equilibria. More precisely, ref.  suggests that this occurs if Eq. (4) is replaced with

$$U_{i,s}(t+1)=U_{i,s}(t)+u_i^{\mu (t)}(s,s_i(t))/P$$
(11)   
Now $`U_{s,i}(t)`$ is proportional to the cumulated payoff that agent $`i`$ would have received had she always played strategy $`s`$ (with other agents playing what they actually played) until time $`t`$. As Fig. 1 again shows this leads to results which coincide with those of the Nash equilibrium. It is remarkable that the (relative) difference between Eqs. (4) and (11) is small, i.e. of order $`1/A^\mu 1/\sqrt{N}`$. Yet, it is not negligible because, when averaged over all states $`\mu `$ it produces a finite effect, specially for $`\alpha <\alpha _c`$ and it affects considerably the nature of the stationary state. This term has the same origin of the cavity reaction term in spin glasses. In order to follow Eq. (11) agents need to know the payoff they would have received for any strategy $`s`$ they could have played. That may not be realistic in complex situations where agents know only the payoffs they receive and are unable to disentangle their contribution from $`G(A^\mu )`$. However agents can account approximately for their impact on the market by adding a cavity term $`+\eta \delta _{s,s_i(t)}`$ to Eq. (4) which “rewards” the strategy $`s_i(t)`$ used with respect to those $`ss_i(t)`$ not used. The most striking effect of this new term, as discussed elsewhere  in detail, is that for $`\alpha <\alpha _c`$ an infinitesimal $`\eta >0`$ is sufficient to cause RSB and to reduce $`\sigma ^2/N`$ by a finite amount.

So far, the information $`\mu (t)`$ was randomly and independently drawn at each time $`t`$ form the distribution $`\varrho ^\mu =1/P`$. In the original version of the MG $`\mu `$ is instead endogenously determined by the collective dynamics of agents: $`\mu (t)`$ indeed labels the sequence of the last $`M=\mathrm{log}_2P`$ “minority” signs – i.e. $`\mu (t+1)=[2\mu (t)+1]_{\mathrm{mod}P}`$ if $`A^{\mu (t)}>0`$ and $`\mu (t+1)=[2\mu (t)]_{\mathrm{mod}P}`$ otherwise. The idea is that the information refers to the recent past history of the market, and agents try to guess trends and patterns in the time evolution of the process $`G(A^{\mu (t)})`$. We may say that $`\mu (t)`$ is endogenous information, since it refers to the market itself, as opposed to the exogenous information case discussed above.

Numerical simulations  show that the collective behavior of the MG – based on Eq. (4) – under endogenous information is the same as that under exogenous information. Within our approach, the relevant feature of the dynamics of $`\mu (t)`$ is its stationary state distribution $`\varrho ^\mu `$. The key point is that a finite fraction $`1\varphi `$ of agents behave stochastically ($`m_i^2<1`$) because $`Q<1`$. As a consequence, $`A^\mu `$ has stochastic fluctuations of order $`\sqrt{N(1Q)}`$ which are of the same order of its average $`A^\mu \sqrt{H}`$. With endogenous information, these fluctuations of $`A^\mu `$ induce a dynamics of $`\mu (t)`$ which is ergodic in the sense that typically each $`\mu `$ is visited with a frequency $`\varrho ^\mu 1/P`$ in the stationary state. The situation changes completely when agents follow Eq. (11). Indeed the system converges to a Nash equilibrium where agents play in a deterministic way, i.e. $`m_i^2=1`$ (or $`Q=\varphi =1`$). The noise due to the stochastic choice of $`s_i`$ by Eq. (3) is totally suppressed. The system becomes deterministic and the dynamics of $`\mu (t)`$ locks into some periodic orbit. The ergodicity assumption then breaks down: Only a small number $`\stackrel{~}{P}P`$ of patterns $`\mu `$ are visited in the stationary state of the system, whereas the others never occur ($`\varrho ^\mu =0`$). This leads to an effective reduction of the parameter $`\alpha \stackrel{~}{\alpha }=\stackrel{~}{P}/N`$, which further diminishes $`\sigma ^2`$. Numerical simulations show that $`\stackrel{~}{P}\sqrt{P}`$ which imply that $`\stackrel{~}{\alpha }0`$ in the limit $`P=\alpha N\mathrm{}`$, i.e $`\sigma ^2/N0`$.

In summary we have shown how methods of statistical physics of disordered systems can successfully be applied to study models of interacting heterogeneous agents. Our results extend easily to more general models  and, more importantly, the key ideas can be applied to more realistic models of financial markets, where heterogeneities arise e.g. from asymmetric information.

We acknowledge J. Berg, A. De Martino, S. Franz, F. Ricci-Tersenghi, S. Solla, M. Virasoro and Y.-C. Zhang for discussions and useful suggestions. This work was partially supported by Swiss National Science Foundation Grant Nr 20-46918.98.