{'fraction_non_alphanumeric': 0.03879514272196814, 'fraction_numerical': 0.010513588813541502, 'mean_word_length': 4.280044407438246, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dynamical Mechanisms in Multi-agent Systems: Minority Games

We consider a version of large population games whose agents compete for resources using strategies with adaptable preferences. Diversity among the agents reduces their maladpative behavior. We find interesting scaling relations with diversity for the variance of decisions. When diversity increases, the scaling dynamics is modified by kinetic sampling and waiting mechanisms.

Many natural and artificial systems involve interacting agents, each making independent decisions to compete for limited resources, but globally exhibit coordinated behavior through their mutual adaptation [1,2]. Examples include the competition of predators in ecology, buyers or sellers in economic markets, and routers in computer networks. While a standard approach is to analyse the steady state behavior of the system described by the Nash equilibria [3], it is interesting to consider the dynamics of how the steady state is approached. Dynamical studies are especially relevant when one considers the effects of changing enviroment, such as those in economics or distributed control.
The recently proposed Minority Games (MG) are prototypes of such multi-agent systems [2]. The dynamical nature of the adaptive processes is revealed when the complexity of the agents is low, where the final states depend on the initial conditions [4,5]. Here, the system exhibits large fluctuations, which are caused by the initially zero preference of strategies for all agents. However, when the game is used to model economic systems, it is not realistic to expect that all agents enter the market with the same preference. Besides, in games which use public information only, this imply that different agents would maintain identical preferences of strategies at all subsequent steps, which is again unlikely. Furthermore, when the game is used to model distributed control in multi-agent systems, identical preferences of strategies of the agents lead to maladaptative behavior, which refers to the bursts of the population's decisions due to their premature rush to certain state, compromising the system efficiency [6,7]. There were attempts of improvement by introducing thermal noise [8], biased starts [9,10], bias strategies [11], and random initial conditions [5]. However, no systematic studies have been made.
In this Letter, we consider the effects of introducing randomness in the initial preferences of strategies among the agents, focusing on the regime of low complexity, where analyses assuming vanishing step sizes are not applicable [4,9]. Concretely, we consider a population of N agents competing in an environment of limited resources, N being odd [2]. Each agent makes a decision + or − at each time step, and the minority group wins. The decisions of each agent are prescribed by strategies, which are Boolean functions mapping the history of the winning bits in the most recent m steps to decisions + or −. Before the game starts, each agent randomly picks s strategies. Out of her s strategies, each agent makes decisions according to the most successful one at each step; the success of a strategy is measured by its virtual point, which increases (decreases) by 1 if it indicates a winning (losing) decision at a time step.
In contrast to early versions of the game, the agents may enter the game with diverse preferences of their strategies. This is done by randomly assigning R virtual points to the s strategies of each agent before the game starts. Hence the initial virtual point of each strategy obeys a multinomial distribution with mean R/s and variance R(s − 1)/s 2 . The ratio ρ ≡ R/N is referred to as the diversity. In particular, for s = 2 and odd R, no two strategies have the same virtual points throughout the game, and the dynamics of the game is deterministic, resulting in highly precise simulation results useful for refined comparison with theories.
To describe the macroscopic dynamics of the system, we define the D-dimensional vector A µ (t), which is the sum of the decisions of all agents responding to history µ of their strategies, normalized by N , where D ≡ 2 m is the number of histories. While only one of the D components corresponds to the historical state µ * (t) of the system, the augmentation to D components is necessary to describe the attractor structure and the transient behavior of the system dynamics. The inset of Fig. 1 illustrates the convergence to the attractor for the visualizable case of m = 1. The dynamics proceeds in the direction which tends to reduce the magnitude of the components of A µ (t) [4]. However, a certain amount of maladaptation always exists in the system, so that the components of A µ (t) overshoot, resulting in periodic attractors with period of 2D. Every state µ appears as historical states two times in a steady-state period, yielding the winning bits − and + each exactly once. One occurence brings A µ from positive to negative, and another bringing it back from negative to positive, thus completing a cycle. For m = 1, the steady state is described by the sequence µ(t) = −, +, +, −, where both states − and + are followed by − and + once each. For general values of m, the states in an attractor are given by a binary de Brujin sequence of order m + 1 [12].
As shown in Fig. 1, the variance σ 2 /N of the population for decision + scales as a function of the complexity α ≡ D/N , agreeing with previous observations [6]. When α is small, games with increasing complexity create time series of decreasing fluctuations. A phase transition takes place around α c ≈ 0.3, after which it increases gradually to the limit of random decisions, with σ 2 /N = 0.25. When α < α c , we have the symmetric phase, in which the occurences of decisions 1 and 0 responding to a given historical state µ are equal, whereas in the asymmetric phase above α c , the occurences are biased for at least some history µ [13]. Figure 1 also shows the data collapse for different N for ρ ∼ 1, indicating that the variance is a function of ρ. It is observed that the variance decreases significantly with diversity in the symmetric phase, and remains unaffected in the asymmetric phase.
The dependence of the variance on the diversity is further shown in Fig. 2 for given memory sizes m. Here we focus on the physical picture of the dynamics [14]. Four regimes can be identified: (a) Multinomial regime. When ρ ∼ N −1 , σ 2 /N ∼ N with proportionality constants dependent on m. To analyse this and other regimes, we let S αβ (ω) be the number of agents holding strategies α and β (with α < β), and the virtual point of strategy α is initially displaced by ω with respect to β. The average of S αβ (ω) over initial condition is proportional to the binomial distribution of virtual points, i.e., The key to analysing the system dynamics is the observation that the virtual points of a strategy displace by exactly the same amount for all agents. Hence for a given strategy pair, the profile of the virtual point distribution remains unchanged, but the peak position shifts with the game dynamics. If the virtual point displacement of strategy α at time t is Ω α (t), then the agents holding strategies α and β make decisions according to strategy α if ω + Ω α (t) − Ω β (t) > 0, and strategy β otherwise. At time t, we can write Ω α (t) = µ k µ (t)ξ µ α , where k µ (t) is the number of wins minus losses of decision + up to time t when the game responded to history µ.
Its average can be found by introducing the average S αβ (ω) , writing the step function as a sum over Kronecka deltas and introducing their integral representation, using the identity e ikθ(ξ µ α −ξ µ β ) = cos 2 kθ+i sin kθ cos θ(ξ µ α −ξ µ β )+sin 2 kθξ µ α ξ µ β , and noting that α ξ µ α = 0. The final result is and is self-averaging. Since A µ (0) is Gaussian with variance N −1 , the values of A µ (t) at the attractors can be computed, and the variance found. For example, for m = 1, , where c n = 2 −n C n n/2 for even integer n.
(b) Scaling regime. When ρ ∼ 1, σ 2 /N ∼ ρ −1 with proportionality constants effectively independent of m for m not too large. In this case, Eq. (1) can be sim- 2 ) and is self-averaging. To interpret this result, we note that changes in A µ (t) are only contributed by fickle agents with marginal preferences of their strategies. That is, those with ω + Ω α (t) − Ω β (t) = ±1 and ξ µ α − ξ µ β = ∓2sgnA µ (t) for µ = µ * (t). For large R, the binomial virtual point distribution among agents of a given strategy pair is effectively a Gaussian with variance R.
Hence the number of agents switching strategies at time t scales as the height of the Gaussian distribution, which is 2/πR. Thus, by spreading the virtual point distribution, diversity reduces the step size and hence maladaptation.
As a result, each state of the attractor is confined in a D-dimensional hypercube of size 2/πR, irrespective of the initial position of the A µ components. Starting from the initial state A µ (0), the state changes in steps of size 2/πR until it reaches the attractor, whose 2D historical states are given by 2/πR⌈ πR/2A µ (0)⌉ and 2/πR{⌈ πR/2A µ (0)⌉ − 1}, where ⌈x⌉ represents the decimal part of x. Averaging over A µ (0), which are Gaussian numbers with mean 0 and variance 1/N , the variance of decisions become σ 2 /N = f (ρ)/2πρ, where f (ρ) approaches (1 − 1/4D)/3 for ρ ≫ 1. Note that f (ρ) is a smooth function of ρ, since σ 2 /N depends on ρ mainly through the step size factor 1/2πρ, whereas f (ρ) merely provides a higher order correction to the functional dependence. This accounts for the scaling regime in Fig. 2. Furthermore, we note that f (ρ) rapidly approaches 1/3 when m increases. Hence for general values of m, σ 2 /N → 1/6πρ, provided that m is not too large.
(c) Kinetic sampling regime. When ρ ∼ N , σ 2 /N deviates above the scaling with ρ −1 , and is given by σ 2 /N = f m (∆)/N , where ∆ ≡ 2N/πρ is the kinetic step size, and f m is a function dependent on the memory size m. Here A µ (t + 1) − A µ (t) scales as N −1 and is no longer self-averaging. Rather, it is equal to 2/N times the number of agents who switch strategies at time t, which is Poisson distributed with a mean of 2/πR. However, since the attractor is formed by steps which reverse the sign of A µ , the average step size in the attractor is larger than that in the transient state. To see this, we consider the probability of P att (∆A) of step sizes ∆A in the attractor. Assuming that all states of the phase space are equally likely to be accessed, we have P att (∆A) = A P att (∆A, A), where P att (∆A, A) is the probability of finding the position A with displacement ∆A in the attractor. Consider the example of m = 1 in the inset of Fig. 1. The sign reversal condition implies that P att (∆A, where P Poi (∆A) is the Poisson distribution of step sizes, yielding P att (∆A) = P Poi (∆A) µ ∆A µ . Thus the attractor averages (∆A ± ) 2 att , which are required for computing the variance of decisions, are given by In other words, the sampling of the step sizes is weighted by the attractor sizes due to the kinetics. The result for m = 1 is σ 2 /N = (14∆ 3 + 105∆ 2 + 132∆ + 24)/96N (2∆ + 1).
(d) Waiting regime. When ρ ≫ N , σ 2 /N deviates above the predictions of kinetic sampling. Here the agents are so diverse that the average step size is approaching 0. At each state in the phase space, the system remains stationary for many time steps, waiting for some agent to reduce the magnitude of her virtual point until strategy switching can take place. This waiting ef-fect modifies the composition of the group of fickle agents who contribute to the state transitions, and consequently increase the step sizes and variance above those predicted by kinetic sampling. Consider the example of m = 1. As shown in the inset of Fig. 1, the attractor consists of both vertical and horizontal hops, and detailed analysis shows that only one type of agents can complete both hops. Since fewer and fewer agents contribute to the switching of states in the limit ρ ≫ N , a single agent of this type will dominate the game dynamics, and one would expect that σ 2 /N approaches 1/4N . However, when waiting is possible, agents not of this correct type can wait for other agents to complete the hops in the attractor, even though one would expect that the probability of finding more than one fickle agents is drastically less than that for one. In fact, analysis shows that the attractor consists of a single fickle agent with a probability of 1/11 only, and σ 2 /N approaches 9/22N rather than 1/4N . As shown in the inset of Fig. 2, lengthy analytic results including waiting effects significantly improve the agreement with simulations over the kinetic sampling prediction.
Many properties of the system dependent on the transient dynamics also depend on its diversity. For example, since diversity reduces the fraction of agents switching strategies at each time step, it also slows down the convergence to the steady state. Hence in the scaling regime, the convergence time scales as ρ 1/2 . Specifically, when ρ ≫ 1, the average convergence time becomes (2+ √ 2) √ ρ for m = 1. Similarly, the distribution of payoffs among the frozen agents (that is, agents who do not switch their strategies at the steady state) also depends on the transient. Since the system dynamics reaches a periodic attractor, they have constant average payoffs at the steady state. Hence any spread in their payoff distribution is a consequence of the transient dynamics. Thus, in the scaling regime, the mean square payoff scales as ρ. Specifically, when ρ ≫ 1, the mean square payoff becomes πρ for m = 1. Simulation results of both the convergence time and the mean square payoff have an excellent agreement with the theory [14].
The results presented here can be generalized to other cases. Consider the exogenous MG, in which the information µ(t) was randomly and independently drawn at each time step t [4]. The picture that the states of the game are hopping between hypercubes in the phase space remains valid. At the steady state, the attractor consists of hoppings among all vertices of a hyperpolygon enclosing the origin in the phase space, analogous to the present endogenous case, in which a fraction of hyperpolygon vertices belong to the attractor. In the scaling regime, the behavior depends on the scaling of the step sizes with diversity, rather than the actual sequence of the steps. Consequently, the behavior is similar to that of the endogenous game.
The present results can be extended to higher values of m [14]. For m = 2, analysis using the de Bruijn sequence explicitly yields excellent results. For higher m, we approximate the attractor of the exogenous game by a hyperpolygon enclosing the origin of the phase space. Using a generating function approach, and taking into account the scaling of step sizes and kinetic sampling, the computed variance of decisions agrees qualitatively with simulations, except for values of α close to α c .
We can also make qualitative predictions about the transition from the symmetric to asymmetric phase when the complexity α increases [13]. From Eq. (1), the average displacement in the phase space is given by where k 2 represents the mean of k ν (t) 2 for all ν ≤ D.
is self-averaging. Suppose the game dynamics leads to an attractor near the origin, with A µ (t) → 0. Noting that A µ (0) 2 ∼ 1/N , we obtain the self-consistent relation k 2 = ρ/2(α c − α), where α c = 1/π ≈ 0.318. This means that when α approaches α c , the average step size appraoches 0 in the asymptotic limit. There is a critical slow down since the convergence time diverges. When α exceeds α c , the average step size vanishes before the system reaches the attractor near the origin, so that the state of the system is trapped at locations with at least some components being nonzero. The interpretation is that when α is large, the distributions of strategies become so sparse that motions in the phase space cannot be achieved by the switching of strategies. Note that the value of α c is close to the value of 0.337 obtained by the continuum approximation [4] or batch update [9]. From the perspective of game theory, it is natural to consider whether the introduction of diversity assists the game to reach a Nash equilibrium. It has been verified that Nash equilibria consist of pure strategies [4]. Hence all frozen agents have no incentives to switch their strategies. In fact, since the dynamics in the attractor is periodic, the payoffs of all strategies become zero when averaged over a period. Thus, the Nash equilibrium is approached in the sense that the fraction of fickle agents decreases with increasing diversity. In the extremely diverse limit, it is probable that only one fickle agent switches strategy at each step in the attractor. In this case, even the fickle agent cannot increase her payoff, since on switching she always remains on the majority side and loses. Then a Nash equilibrium is reached exactly. For m = 1, for example, a Nash equilibrium is reached in this way with probability 7/11.
In summary, we have studied the effects of diversity in the initial preference of strategies on a game with adaptive agents competing for finite resources. Scaling of step sizes accounts for the behavior of the variance of decisions in the scaling regime (ρ ∼ 1). At high diversity, we find that the scaling mechanism is supplemented by kinetic sampling, a mechanism self-imposed by the requirement to stay in the attractor. In extremely diverse systems, we discover further a waiting mechanism, when agents who are unable to complete the attractor dynamics alone wait for other agents to collaborate with them. Together, these mechanisms yield theoretical predictions with excellent agreement with simulations over 9 decades of data. By introducing diversity, the variance of decisions in the symmetric phase decreases, showing that the maladaptive behavior is reduced.
The combination of scaling, kinetic sampling and waiting in accounting for the steady state properties of the system illustrates the importance of dynamical considerations in describing the system behavior. We anticipate that these dynamical effects will play a crucial role in explaining the system behavior in the entire symmetric phase, since when α increases, the state motion in a high dimensional phase space can easily shift the tail of the virtual point distributions to the verge of strategy switching, leading to the sparseness condition where kinetic sampling and waiting effects are relevant. Due to the generic nature of these effects, we expect that they are relevant to minority games with different payoff functions and updating rules, as well as other multi-agent systems.
We thank P. Luo, Y. C. Zhang, L. H. Tang, B. H. Wang for fruitful discussions. This work is supported by the research grants HKUST6153/01P and HKUST6062/02P from the Research Grant Council of Hong Kong.