{'fraction_non_alphanumeric': 0.05361000196373634, 'fraction_numerical': 0.014858938273221182, 'mean_word_length': 4.106283422459893, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Theory of enhanced performance emerging in a sparsely-connected competitive population

We provide an analytic theory to explain Anghel et al.'s recent numerical finding whereby a maximum in the global performance emerges for a sparsely-connected competitive population [Phys. Rev. Lett. 92, 058701 (2004)]. We show that the effect originates in the highly-correlated dynamics of strategy choice, and can be significantly enhanced using a simple modification to the model.

There are two particularly active areas of research into Complex Systems among physicists: multi-agent populations [1,2,3] and complex networks [4]. Arthur's barattendance problem [1] and its binary Ising-like simplifications (e.g. the Minority Game (MG) [2,3]) constitute everyday examples of multi-agent competition for limited resources. However researchers have only just started considering combining networks with such multiagent systems [5,6]. Anghel et al. [5] reported some fascinating numerical results in which the fluctuation in the number of agents taking a particular action can exhibit a minimum at small connectivity (see Fig. 1 inset). It is truly remarkable that there exists an optimal number of network connections such that the overall system performance is maximized, and that this optimal connectivity is actually quite small. Anghel et al.'s results have so far lacked any theoretical explanation, yet they represent an important challenge for physics -not just because of the potential application areas but also because they expose our limited understanding of complex dynamical networks. Here we provide the first analytic theory which explains their remarkable finding. The essential underlying physics comprises (i) the highly correlated, non-random temporal evolution of strategy scores, (ii) the tendency to link to future winners (losers) at low (high) connectivity p, and (iii) the emergence of different species of agent characterized by the relative Hamming distance D of their strategies. The importance of the underlying dynamics means that approaches based on assumptions of random histories, e.g. spin-glass theories, are invalid. Our theory also shows that network connections play a crucial role, even when only a tiny fraction exist. This enables us to propose a minor modification to Anghel et al.'s model which provides significantly enhanced global performance. Interestingly, there is recent empirical evidence to suggest that our proposed 'second-best' rule does actually arise in everyday life [7]. Our theory in the zero-connectivity limit (i.e. p = 0) also provides a new microscopic theory for the MG. Note that the theory we present does not benefit from the simplifications and hence beauty of conventional many-body theory in physics. This is because -in contrast to conventional physical systems -the dynamics and configuration space are now so closely intertwined. However it is precisely this feature which makes the problem so interesting for a theoretical physicist [8].
Anghel et al.'s model [5] features N agents who repeatedly choose between two actions '1' or '0' [2]. The winners are those in the minority group. The global information is the bit-string containing the m most recent winning outcomes (i.e. history). Each agent holds s = 2 strategies. Each strategy is one of the 2 2 m possible mappings from the 2 m histories to action '1' or '0'. All strategies collect one virtual point (VP) if they predicted the winning outcome correctly, while each agent collects one (real) point if he wins. The mean success rate w is the average number of real points per agent per turn. The agents are connected by an undirected random network with p being the probability that a link between two randomly chosen agents exists. Each agent compares the cumulated performance of his best-performing strategy (i.e. his predictor) with that of his neighbors, and then follows the prediction of whoever holds the best-performing predictor, including himself. The p = 0 limit of the model reduces to the MG. The identity of the best-performing strategy changes over time, and for p > 0 the predictor's performance is generally different from the agent's performance. Figure 1 (inset) illustrates the minimum in fluctuation arising at finite p [5], together with w as a function of p for m = 1. Since these quantities are simply related, we focus here on w .
The features of interest occur at small m and small p, hence we focus on the explicit example of m = 1 (see Fig. 1) and make the reasonable assumption that the predictors' performance can be approximated by the p = 0 results. Generalization to m = 2, 3 . . . and s > 2 is straightforward but lengthy. For p = 0 and small m, no single strategy outperforms the others (i.e. no runaway VPs) and the system restores itself in a finite (mdependent) number of timesteps. The Eulerian trail acts as a quasi-attractor of the system's dynamics [9], yielding anti-persistent behavior whenever the system revisits a given history node on the de Bruijn graph of possible history bit-strings. Let {t ν even } ({t ν odd }) be a set consisting of the turns in a history series at which a particular history ν occurred an even (odd) number of times from the beginning of the run until the moment of the current history µ. For t ∈ {t µ even }, the agents decide randomly since the strategy scores are not biased. For t ∈ {t µ odd }, the success rate is determined by: (i) The number of histories κ that had occurred an odd number of times at the moment of decision. Since there are 2 m histories, we have 0 ≤ κ ≤ 2 m . (ii) The Hamming distance d between an agent's best-performing strategy and the best performing strategy among all strategies (BPS) at that particular turn. (iii) The Hamming distance D between the strategies that an agent holds. For s = 2, the probability that the strategies are separated by a Hamming distance D is given by the binomial coefficient C 2 m D , where D = 0, 1, . . . , 2 m . For m = 1, there are on average N/4 agents belonging to the D = 0 'species' (i.e. two perfectly correlated strategies), N/2 in the D = 1 'species' (i.e. two uncorrelated strategies), and N/4 in the D = 2 'species' (i.e. two anticorrelated strategies). For m = 1, κ = 0, 1 or 2 since there are two possible history bitstrings. Consider a particular time t corresponding to κ = 0: t ∈ {t ν even } for both histories assuming the system follows the Eulerian trail. Hence the agents become dynamically segregated by their performance, according to their D value. As we now explain, N/4 (D = 0) agents should have a score of t/2, N/2 (D = 1) agents should have a score of 3t/8, and N/4 (D = 2) agents should have a score of 5t/16, in the long time limit. Prior to a current history of, say, 0, each history bit (1 and 0) has occurred an even number of times. The strategies are all tied. The outcome is thus random (i.e. coin-toss). Agents with a given D might have won with probability w (even) κ=0 < ∼ 1/2 or lost with probability (1 − w (even) κ=0 ) and hence there are two subgroups (i.e. won or lost) of agents for a given D, with different sizes. Regardless of the outcome, the system now corresponds to κ = 1 and the agents' scores can be classified into six groups. We denote the groups by the label {D, Y } κ , where κ gives the number of history bit-strings occurring an odd number of times (0 ≤ κ ≤ 2 m ) and Y is the net number of times that the group has won (i.e., number of winning turns minus number of losing turns) starting from the most recent occurrence of κ = 0. If the outcome is 0, then t ∈ {t µ odd }. For the D = 0 species, their strategies do not allow them to change their action and hence the agents who won in the last occurrence (carrying the label {0, 1} 1 ) will definitely lose and those who lost (carrying the label {0, 0} 1 ) will definitely win, a situation denoted by the winning probabilities S {0,1}1 = 0 and S {0,0}1 = 1. For the D = 1 species (i.e. two uncorrelated strategies), those agents who won in the last occurrence of the history (carrying the label {1, 1} 1 ) must hold a strategy that points to the most recent winning option, and hence they will make the same choice -they will definitely lose due to the crowd effect. For those who lost, their winning probability depends on whether their two strategies give the same or different predictions for the history concerned. For those agents with strategies giving the same (different) prediction(s) (for history 0 in our example), they will lose (win). Thus the group of agents labelled by {1, 0} 1 will have an average winning probability of S {1,0}1 = 1/2. For the D = 2 species, these agents' anticorrelated strategies give different predictions and hence they will definitely lose, i.e., S {2,1}1 = S {2,0}1 = 0.
If the outcome is 1 instead of 0, the situation corresponds to κ = 1 since the history 0 has occurred an odd number of times and t ∈ {t µ even } since the current history 1 occurred an even number of times. The strategies' VPs do not indicate a preference and hence do not lead to a crowd effect. In this case, each of the six groups of agents has a probability of w (even) κ=1 of winning. As a result, the population will subsequently be grouped into nine groups according to the agents' performance in the last two turns, i.e. win-win, win-lose or lose-win, and lose-lose groups for each value of D. Regardless of the outcome, the system is updated to κ = 2 and t ∈ {t µ odd }. The instantaneous BPS is the strategy that predicted correctly the most recent t ∈ {t µ even } outcomes for both µ = 0, 1. The BPS will predict incorrectly in the following turns, due to the VPs' anti-persistence. The strategies with the second highest VPs, i.e. one correct prediction out of two turns, will predict correctly with probability 1/2. The momentarily worse-performing strategy is the one that predicted incorrectly for both histories at t ∈ {t µ even }. However, it will predict correctly in the coming t ∈ {t µ odd } timesteps. Therefore, agents holding the BPS will use it and are bound to lose. Hence the {D, 2} 2 groups have winning probabilities S {D,2}2 = 0 for D = 0, 1, 2, since they hold the BPS. For the other D = 0 agents, those who won (lost) in the last occurrence of the current history will lose (win). Therefore, the winning probabilities are S {0,1}2 = 1/2 and S {0,0}2 = 1. For the other D = 1 agents, their winning probabilities are S {1,1}2 = 1/4 and S {1,0}2 = 1/2. For D = 2, the {2, 0} 2 agents must hold two anticorrelated strategies of second highest VPs and thus S {2,0}2 = 1/2. For the {2, 1} 2 group, an agent may either hold (i) the BPS and the worse-performing strategy, or (ii) two strategies with the second highest virtual points. For combination (i), this agent's winning probability is 0 while for combination (ii), his winning probability is 1/2. Averaging over these two possibilities gives S {2,1}2 = 1/2. A common feature of the winning probabilities is that {D, κ} κ is always zero, i.e. agents with momentarily high-performance predictors are bound to lose in the following timesteps.
This dynamics is valid for p ≥ 0. An agent of Hamming distance D has an average winning probability at t ∈ {t µ odd } for a given κ:  . For small m, the probabilities of occurrence of all histories are equal. Hence the probability of having a particular value of κ is P (κ) = C 2 m κ /2 2 m . For a given value of κ, the probability of having t ∈ {t µ odd } and t ∈ {t µ even } in a randomly picked turn is κ/2 m and (1 − κ/2 m ), respectively. Combining with Eq.(1), the winning probability of the agents with a given Hamming distance D is [6] where w (even) κ is the winning probability for timesteps with t ∈ {t even } and can be found by random walk arguments for p = 0 and p = 0 [10]. For p = 0, Eq. (2) gives the segregation in success rates determined by the agents' 'species' type D. The overall mean success-rate is hence For the range of p where the important features arise, the agents' predictor performance is identical to the (real) scores or success rates at p = 0 discussed above. For p = 0, the agents in each group {D, y} κ can be separated into two subgroups: where N {D,y}κ is the number of agents in the group {D, y} κ who follow their own predictor, and ∆N {D,y}κ,{D ′ ,j}κ is the number of agents who follow the predictor of a neighbor belonging to group {D ′ , j} κ , due to the presence of links. Since agents only follow neighbors with better performing predictors, only links to neighbors in the group with labels D ′ < D or j > y (if D = D ′ ) are effective. For given p, the probability of an agent in {D, y} κ having at least one link to agents in The number of agents having predictor performance better than the group {D, y} κ is given by The number of agents N {D,y}κ in Eq.(4) is then given by since q A {D ′ ,j}κ is the probability of the agents in group {D, y} κ not having any links to other groups with better predictor performance, and so still have winning probability S {D,y}κ for t ∈ {t µ odd }. Agents will follow the prediction of agents in {D ′ , j} κ only if (i) they have connections to them and (ii) they do not have any connection to a better performing group. Therefore, ∆N {D,y}κ,{D ′ ,j}κ in Eq.(4) is given by (7) and these agents will have the same winning probability S {D ′ ,j}κ as those in group {D ′ , j} κ for t ∈ {t µ odd }. Hence the mean success rate S {D,y}κ for agents labelled by {D, y} κ for t ∈ {t µ odd } is given by For general p, Eq.(1) is modified to Equation (2) can hence be used to evaluate the mean success rate of agents for a given D, while Eq.(3) gives w as a function of the connectivity p. Equations (2) and (3) coupled with Eqs.(4)-(9) are our main formal results. Figure 1 shows w as a function of p. The theory can also be used to evaluate the fluctuation σ (see inset). The theoretical results are in excellent agreement with the numerical simulations. Our theory is further validated in Fig. 2, where we compare theoretical and numerical results for the success rates w D for each species-type D.
Each D species has a distinct p dependence, showing why a peak appears in the model of Anghel et al.. For small connectivity p, D = 1 and D = 2 agents can benefit by hooking up to the better performing D = 0 agents. However as p increases, these agents may hook to agents belonging to groups with momentarily better predictor performance. These links hurt the agent's success rate since momentarily better strategies are bound to lose in subsequent turns. Hence the success rates of D = 1 and D = 2 agents will increase at small p and decrease at higher p, while that for D = 0 agents decreases monotonically with p.
Finally, having understood the underlying physics, we can propose a performance-enhancing modification to Anghel et al.'s model. Instead of following the bestperforming agent, suppose an agent follows the secondbest performing agent among his neighbors. Figure 3 shows that w is substantially larger over a wide range of p. In addition, the value of p at the peak corresponds to a much larger number of network links. Interestingly, there is recent empirical evidence to suggest that such 'second-best' rules do indeed make humans happier on average in everyday life [7].