Heterogeneous preferences, decisionmaking capacity, and phase transitions in a complex adaptive system
See allHide authors and affiliations

Edited by H. Eugene Stanley, Boston University, Boston, MA, and approved February 24, 2009 (received for review November 21, 2008)
This article has a Correction. Please see:
Abstract
There has been a belief that with the directing power of the market, the efficient state of a resourceallocating system can eventually be reached even in a case where the resource is distributed in a biased way. To mimic the realistic huge system for the resource allocation, we designed and conducted a series of economic experiments. From the experiments we found that efficient allocation can be realized despite a lack of communications among the participants or any instructions to them. To explain the underlying mechanism, an extended minority game model called the marketdirected resource allocation game (MDRAG) is constructed by introducing heterogeneous preferences into the strategybuilding procedures. MDRAG can produce results in good agreement with the experiments. We investigated the influence of agents' decisionmaking capacity on the system behavior and the phase structure of the MDRAG model as well. A number of phase transitions are identified in the system. In the critical region, we found that the overall system will behave in an efficient, stable, and unpredictable mode in which the market's invisible hand can fully play its role.
Most of the social, economic, and biological systems involving a large number of interacting agents can be regarded as complex adaptive systems (CAS) (1), because they are characterized by a high degree of adaptive capacities to the changing environment. The interesting dynamics and phase behaviors of these systems have attracted much interest among physical scientists. A number of microscopic CAS models have been proposed (2–6), among which the minority game (MG) (7–9) becomes a representative model. Along with the progress in the research of econophysics (10), MG has been mostly applied to simulate one kind of CAS, namely the stock market (11, 12). Alternatively, MG can also be interpreted as a multiagent system competing for a limited resource (13, 14) that distributes equally in 2 rooms. However, agents in the real world often have to face a competition to the limited resource, which distributes in different places in a biased manner. Examples of such phenomena include companies competing among markets of different sizes (15), drivers selecting different traffic routes (16), people betting on horse racing with the odds of winning a prize, and making decisions on which night to go to which bar (17).
From a global point of view, the ideal evolution of a resourceallocating system would be the following: Although each agent would compete against others only with a selfserving purpose, the system as a whole could eventually reach a harmonic balanced state where the allocation of resource is efficient, stable, and arbitragefree (which means that no one can benefit from the “misdistribution” of the resource). Note that during the process of evolution to this state, agents could neither have been told about the actual amount of the resources in a specific place nor could they have any direct and full communications, just as if there were an “invisible hand” directing them to cooperate with each other. Then, does this invisible hand always work? In practice, there is plenty of evidence that the invisible hand does have very strong directing power in places such as financial markets, although sometimes it does fail to work. Such temporary ineffectiveness implies that there must be some basic conditions required for the invisible hand to exert its full power. Through an experimental study and a numerical study with a marketdirected resource allocation game (MDRAG, which is an extended version of the MG model), we found that agents equipped with heterogeneous preferences as well as a decisionmaking capacity that matches with the environmental complexity are sufficient for the spontaneous realization of such a harmonic balanced state.
To illustrate the system behavior, we designed and conducted a series of economic experiments, in collaboration with university students. In the experiments, 89 students from different (mainly physics, mathematics, and economics) departments of Fudan University were recruited and randomly divided into 7 groups (Groups A–G, see Tables 1–4). The number of students in each group was just set for convenience and denoted by N in Tables 1–4. In the games played in the experiments, students were told that they had to make a choice among a number of rooms, in each round of a session, for sharing the different amounts of virtual money in different rooms. Students who got more than the global average, namely those belonging to the relative minority, would win the payoff. At the beginning of a session, participants were told the number of rooms (2 or 3) and in some cases, the different but fixed amount of virtual money in each room. In the following, M_{i} is used to denote the amount of virtual money in room i. A piece of global information about the payoff in the preceding round in all rooms is announced before a new round starts. In each round, the students must make their own choices without any kind of communication. The payoff per round for a student in room i is 2 points if M_{i}/N_{i} > ΣM_{i}/N, and −1 point otherwise. Here, N_{i} is the number of the students choosing room i. The total payoff of a student is the sum of payoffs of all rounds, which will be converted to money payoffs in Renminbi (RMB, or Chinese yuan) with a fixed exchange rate. Because the organizational and statistic procedures were done by a human, one session of 10 rounds took ≈20 min. More details can be found in the leaflet to the experiments in Appendix.
Three kinds of games, GAMEI, GAMEII, and GAMEIII, have been investigated. GAMEII differs from GAMEI in the global information being announced. In GAMEI, both the resource distribution M_{i} and the current population N_{i} in room i were announced, whereas only payoffs (2 or −1) in each room of the current round were conveyed to players in GAMEII. Note that the environmental complexity was increased in GAMEII, because to win the game, players would have to predict other players' decisions, and, in the meantime, infer the actual amount of virtual money in different rooms. In GAMEIII, the global information is the same as that of GAMEII, except that an abrupt change of amount of virtual money is introduced during the play of the game without an announcement. (On the contrary, all of the participants have already been told that each M_{i} is fixed.) No further information was given to the participants.
Results of 6 sessions of GAMEI, 4 of GAMEII, and 1 of GAMEIII are given in Tables 1–4. In Table 1, the results of GAMEI are listed, where the time average of the player number in room i is represented as 〈N_{i}〉. As the data show, a kind of cooperation seems to emerge in the game within 10 rounds. In particular, ratios of 〈N_{i}〉 converge to the ratios of M_{i}, implying that the system becomes efficient in delivering the resource even if it was distributed in a biased way. To the players, no room is better or worse in the long run; there is also no evidence that any of them could systematically beat the resource allocation “market.” One might naively think that the system could evolve to this state only because the participants knew the resource distribution before the play of the games and the population in each room during the play. However, results of GAMEII show that this explanation could not be correct. As shown in Table 2, although players who know neither the resource distribution nor the current populations in different rooms seem not to be able to adapt to the unknown environment during the first 10 or 15 rounds, eventually the relation 〈N_{1}〉/〈N_{2}〉 ≈ M_{1}/M_{2} is achieved again in groups C and F. For instance, Table 3 shows the track through which group F gradually found the balanced state under the environmental complexity M_{1}/M_{2} = 3. Furthermore, the results of GAMEIII support the conclusion of GAMEII, in which the system can reach this state even with an abrupt change of the unknown resource distribution during the play of the game, see the results of 21 to 45 rounds played by the G group in Table 4. It is surprising that players can “cooperate” even without direct communications or information about the resource distribution. We can define the source of a force that drives the players to get their quota evenly as the “invisible hand” of the resourceallocation market. In the sequel, however, we shall show that the effectiveness of this invisible hand relates to the heterogeneous preference and the adequate decisionmaking capacity of the participants of the game.
Model
To find out the mechanism behind this adaptive system of resource distribution, 2 multiagent models are used, and their results are compared with each other. The first model is the traditional MG, whereas the second one is an extended MG called a MDRAG. MG and MDRAG have a common framework: There are N agents who repeatedly join a resourceallocation market. The amounts of resource in 2 rooms are M_{1} and M_{2}. Before the game starts, each agent will choose S strategies to help him/her make a decision in each round of play. The strategy used in MG and MDRAG is typically a choice table that consists of 2 columns, as shown in Table 5. The left column is for the P possible economic situations, and the right side is for the corresponding room number, namely room 0 or room 1. Thus, if the current situation is known, an agent should immediately choose to enter the corresponding room. With a given P, there are totally 2^{P} different strategies. At each time step, based on a randomly given exogenous* economic state (18), each agent chooses between the 2 rooms with the help of the prediction of his/her bestscored strategy. After everyone has made a decision, agents in the same room will share the resource in it. Agents who earn more than the global average (M_{1} + M_{2})/N become the winners, and the room that they entered is denoted as the winning room. To a strategy in the game, a unit of score would be added if it had given a prediction of the winning room, no matter whether it was actually used or not.
On the other hand, MDRAG differs from MG in the strategybuilding procedures. In traditional MG, agents “randomly” choose S strategies from the strategy pool of 2_{p} size. Here, randomly means that each element of the right column of a strategy table is filled in with 0 or 1 equiprobably. By using this method, strategies of different preferences will have a binomial distribution. Here, the preference of a strategy is defined as the tendency or probability with which a specific room will be chosen when the strategy is activated. For a large P, the numbers of 0 and 1 in the right column are nearly equal. Hence, globally there would be no preference difference among agents who uniformly pick up these strategies. In MDRAG, however, we use another method to fill the strategy table to introduce heterogeneous preferences to the agents. First, K(0 ≤ K ≤ P), denoting the number of 0s in the right column, is randomly selected from the P + 1 integers. In other words, strategies with different preferences (different values of K) are chosen equiprobably from the strategy pool. Second, each element of the strategy's right column should be filled in by 0 with the probability K/P and by 1 with the probability (P − K)/P. It is clear that a strategy with an allzero right column can be picked with the probability 1/(P + 1) in MDRAG, whereas this could happen only with a probability of 1/2_{p} in the traditional MG and could practically never be chosen by any MG agents if NS ≪ 2_{p}.
To make descriptions easier to understand, explanations of the model parameters are provided. The ratio M_{1}/M_{2} represents the environmental complexity of the games. Note that if M_{1}/M_{2} = 1, agents need only to worry about other people's decision. Assuming that room 1 always contains more resources, the trivial case will be M_{1}/M_{2} > N − 1, because all of the agents can easily find out that going to room 1 would be the right choice under this situation. On the other hand, when the ratio is set 1 < M_{1}/M_{2} ≤ N − 1, the larger this ratio is, the more difficult it would be for the market to direct the system to the ideal state. Other parameters concern the decisionmaking capacity, which can be generalized into 3 elements (http://plato.stanford.edu/entries/decisioncapacity/), namely, (i) the possession of a set of values and goals necessary for evaluating different options; (ii) the ability to communicate and understand information; and (iii) the ability to reason and to deliberate about one's choices. The first element has already been built into both the models as the evaluation of the strategies with the minorityfavorable payoff function. The second element relates to the model parameter P. Because the total number of possible situations depends on the completeness of the perception of the world, we relate it to cognition ability. Finally, more strategies could be helpful if one needs to deliberate his/her choices of decisions, hence the strategy number S is related to the third element of the decisionmaking capacity, the ability of choice deliberation.
Results
Results of the economic experiments are compared with the simulation results of the traditional MG and MDRAG in Fig. 1. For each parameter set, we performed the simulation 200 times. In each of these simulations, the code was run over 400 time steps. The first half of the time evolution is for the equilibration of the system, whereas the remaining half is for doing the statistics. With a certain set of parameters (S = 8 and P = 16), MDRAG's results perfectly agree with the experimental data under higher environmental complexity. In other words, agents in both experiments and MDRAG can be directed by the market to cooperate with each other so that an efficient allocation of the biasedly distributed resource can be realized even without giving the agents full information or instructions. On the other hand, the traditional MG fails to reproduce the experimental results unless the distribution of resource is biased very weakly up to M_{1}/M_{2} = 3. Note that MDRAG differs from MG solely in the introduction of heterogeneous preferences in the strategies; hence, one may infer that the heterogeneity of agents' preferences is a significant factor to have the invisible hands be effective. This argument is further supported by numerical experiments in the 3room cases (with parameters P = 24, N = 120, and S = 10). Again, here MDRAG is superior to MG in bringing out the directing power of the market. Shown in Table 6, the ratio of 〈N_{1}〉:〈N_{2}〉:〈N_{3}〉 converges to M_{1}:M_{2}:M_{3} only in the equilibrium states of MDRAG.
Fig. 1 also shows that the decisionmaking capacity, in particular, the deliberation of choices (the parameter S), would be another factor having an influence on the effectiveness of the invisible hand. Typically, as the environmental complexity (M_{1}/M_{2}) increases, both MG and MDRAG will deviate from the experimental results. Nevertheless, the problem of MG is much more severe. As shown in the figure, even MG with extremely large S (S = 48, a situation that is inconsistent with the real system and will drastically increase the computational cost) can just work at a very low level of environmental complexity. At the same time, the result of MDRAG provides a perfect fit with the experimental data when S is large enough, but not too large for a given P value (the reason will be explained in the following discussion of Fig. 3). In a word, MG does not provide a good fit even for large S, whereas MDRAG can fit the data with a less demanding condition in terms of computational cost.
Discussion
Through a large number of numerical simulations, we have found the dependence of equilibrium states of the system on the model parameters, together with a number of phase transitions in the models. To explore this in more detail, 3 parameters are defined that describe system behaviors in 3 aspects, namely, efficiency, stability, and predictability. First the efficiency of resource allocation can be described as e = ∣〈N_{1}〉/〈N_{2}〉 − M_{1}/M_{2}∣/(M_{1}/M_{2}). Note that 0 ≤ e < 1 and a smaller e means a higher efficiency in the allocation of the resource. The stability of a system can be described by σ^{2}/N ≡ (1/2N)Σ_{i=1}^{2}〈(N_{i} − Ñ_{i})^{2}〉, which denotes the population fluctuation away from the optimal state.^{†} Here, Ñ_{i} = M_{i}N/ΣM_{i}, and 〈A〉 is the average of time series A_{t}. The predictability is related to H ≡ (1/2NP)Σ_{μ=1}^{P}Σ_{i=1}^{2}〈N_{i} − Ñ_{i}∣μ〉^{2}, in which 〈A∣μ〉 is the conditional average of A_{t}, given that μ_{t} = μ, one of the P possible economic situations. If σ^{2}/N ≠ H, it means that agents may take different actions at different times for the same economic situation (namely, the market behavior is unpredictable). For clarity, we describe the predictability of system by defining J = 1 − HN/σ^{2}. It is obvious that 0 ≤ J < 1 and a smaller J means a higher predictability.
The variation of system behavior along with the change of environmental complexity M_{1}/M_{2} is shown in Fig. 2. As shown in Fig. 2A, the system changes from an efficient state into an inefficient state at some critical value (M_{1}/M_{2})_{c} ≈ S. For other values of P, the system behavior stays the same as long as P is larger than M_{1}/M_{2}. In Fig. 2B, around the same critical value of M_{1}/M_{2}, σ^{2}/N changes from a decreasing function to an increasing function, giving the smallest fluctuation in the population distribution at the critical point. Meanwhile, the order parameter J also falls into zero at (M_{1}/M_{2})_{c}, suggesting that a phase transition, named the “M_{1}/M_{2} phase transition,” occurs at this critical point. To be more illustrative, when the environmental complexity is much smaller than the critical value, the system could reside in an efficient, unpredictable, but relatively unstable state. Getting closer to the phase transition point, the stability of system will be improved until the most stable state is reached. Then, after crossing the critical point, the decisionmaking capability of the whole system has been exhausted, and it will fall into an inefficient, predictable, and unstable state. At the vicinity of the critical point, as if participants of the game worried about being eliminated from the competition, the market inspires all of its guiding potential and leads the system to the ideal state for the resource allocation, a state that is both efficient and stable and where no unfair arbitrage chance can exist.
It is important to know that MDRAG and MG have totally different phase structures, which could be analyzed by comparing the S − P contours of the descriptive parameters for the 2 models, see Fig. 3. From the analysis, we could also know how the decisionmaking capacity influence the overall performance of the resource allocation system, in case the environmental complexity is fixed (M_{1}/M_{2} = 4). Features of the contour maps (Fig. 3) are summarized as the following (different M_{1}/M_{2}s do not change the conclusions):

(i) Compared with the traditional MG as a whole, MDRAG has a much wider range of parameters for the availability of the efficient, stable, and unpredictable states. In particular, there is almost no eligible region in Fig. 3A if we take the criterion of efficiency as e < 0.08. Also, the predictable region (J < 0.02) in Fig. 3F is much smaller than that of the MG's results in Fig. 3C. These facts indicate that MDRAG has a much better performance than MG as a resourceallocating system.

(ii) Patterns of the contour maps suggest that MG and MDRAG have totally different dependency on parameters. Fig. 3 A–C indicates that P and S are not independent in the traditional MG model, which confirms the previous findings (19). On the other hand, in MDRAG, there is always a region where the system behavior is almost controlled by the parameter S. In Fig. 3D, for large enough P, the system can reach the efficient state if S exceeds a critical value S_{p}, where S_{p} will converge to the limit value M_{1}/M_{2} with increasing P. For S < S_{p}, the system can never reach the efficient state no matter how P changes. For a very large P and S < M_{1}/M_{2}, it can be proved that the probability for agents to enter the richer room is S/(S + 1), so that the system stays in the inefficient states (〈N_{1}〉/〈N_{2}〉 < M_{1}/M_{2}).

(iii) Observing Fig. 3 D and F, one may find both an “S phase transition” and a “P phase transition.” As mentioned above, for large enough P, the increase of S can abruptly bring the system from the inefficient/predictable phase to the efficient/unpredictable phase, and it is named S phase transition. On the other hand, in the narrow region where S < M_{1}/M_{2}, the increase of P can also produce of a drastic change from the unpredictable phase to the predictable phase, and it is named P phase transition. The existence of the S phase transition can be explained by the fact that the number of available choices in decision making is a key factor for agents to find the right choice from strategies with an adequate heterogeneity of preferences. But for S ≫ P, it will also cause a slight decrease of the efficiency because of the conflicts of the different predictions from the equally good strategies with the same preference. This explains why MDRAG, S = 48 performs worse than MDRAG, S = 8, when P = 16 in Fig. 1. The P phase transition reflects that for some incompetent ability of choice deliberation, a critical value of the cognition ability can enhance the decisionmaking capacity to match the environmental complexity.

(iv) It is also noteworthy that the parameter α = 2_{P}/N, which is the main control parameter in the MG model (8, 9), no longer controls on the behavior of the MDRAG system. Varying N while keeping M_{1}/M_{2} as a constant, the basic feature, especially the critical position of the contour maps, will remain unchanged.
In aspects of the competition for resources, the feed of global information, and the inductive optimization of strategies, both MG and MDRAG may be regarded as eligible models for the economic experiments. However, MG fails to reproduce the experimental results in most cases. By simply accommodating a broader preference distribution of the strategies, MDRAG fits the experimental results without any coordinating capability of the agents. This enables us to comment on the possible mechanism of the invisible hand, and conditions under which the complex adaptive systems will spontaneously converge to the efficient states. The most important thing for the invisible hand to work is that different players of the economic games should have different preferences, just like the agents in the MDRAG games who have heterogeneous preferences in their strategies. Next, the players should also have an adequate capacity of decision making that matches the complexity of the environment. From the M_{1}/M_{2} phase transition in the MDRAG simulations, we could infer that there would be a failure in achieving the balanced efficient state if the game of the experiment were designed in too complicated a way, e.g., too many rooms or a toobiased distribution of the virtual money. Nevertheless, for the MDRAG model itself, because the model parameters can be tuned freely, we believe that the market directing power can always be brought out completely in this paradigm as long as there is enough computational power. To put it another way, when the experiment happens to be set at the critical range of players' decisionmaking capacity, just like a finely tuned MDRAG where parameters are set to be critical values of the phase transitions mentioned above, an idealized state of the resource allocating system can be realized, namely, the system is efficient, stable, and unpredictable; see the overlapped regions for small e, small σ^{2}/N, and finite J in Fig. 3 D–F.
Finally, although these intriguing conclusions are supported by the results of MDRAG simulations, there are still some important effects in the real world not included in the model, such as the difference in the decisionmaking capacities among the agents and the agents' responses to changes of the environment. One challenging task is to consider a suitable relation between agents' behavior and the distribution of resources (M_{1}/M_{2}), which may have an influence on the dynamic behavior of the whole system.
Acknowledgments
W.W. and J.H. acknowledge the partial support by the National Natural Science Foundation of China under Grants 10604014 and 10874025 and by Chinese National Key Basic Research Special Fund under Grant 2006CB921706. Y.C. acknowledges partial support by the Mathematics and Physics Platform of Fudan University and the support by Professor Ruibao Tao of the Department of Physics, Fudan University.
Appendix: Leaflet to the Economic Experiment

A group of persons are taking part in this experiment. The game situation is the same for each participant. In the experiments, any kinds of communication are not allowed.

At the beginning of the game, all of you will be told the kind of game (GAMEI, GAMEII, or GAMEIII) as well as the total number of the players (N), rooms (2 or 3), and play rounds.

In each round of the game, you have to choose and enter 1 of the rooms. The amount of virtual money in each room is different but fixed, represented by M_{i} (i = 1, 2, …).

You will be told each M_{i} (only in GAMEI).

In each round, you can choose a room to share the virtual money in it and get your quota, M_{i}/N_{i}, if you select room i. Here, N_{i} denotes the total number of players in room i.

You may make a new room choice in every round.

Your payoff per round: After the statistics of each round are done, you will receive a payoff that depends on the relation between your quota and the global average:

Your information per round:

 The current round number.

 N_{i} of each room in the preceding round (only in GAMEI, announced by the game organizer).

 Payoff (2 or −1) of each room in the preceding round (announced by the game organizer).

 Your rooms chosen and payoffs got in the preceding game rounds (recorded by yourself).

 Your cumulated payoffs (calculated by yourself).


The initial capital of each participant is 0 point. The exchange rate is 1 RMB per (positive) point.
Footnotes
 ^{1}To whom correspondence should be addressed. Email: jphuang{at}fudan.edu.cn

Author contributions: W.W., Y.C., and J.H. designed research; W.W. performed research; W.W., Y.C., and J.H. analyzed data; and W.W., Y.C., and J.H. wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

↵* The alternative is the use of endogenous binary history of the game results as the economic situations. We have confirmed that there would be no change in the simulation results.

↵† Large fluctuations in populations can cause a higher dissipation in the system. Hence, an efficient and stable state means an optimal state with a low waste in the resource allocation.
References
 ↵
 Holland JH
 ↵
 Grimm V,
 et al.
 ↵
 ↵
 Tesfatsion L
 ↵
 Fu D,
 et al.
 ↵
 ↵
 Arthur WB
 ↵
 ↵
 ↵
 Mantegna R,
 Stanley HE
 ↵
 ↵
 ↵
 ↵
 ↵
 Cody ML,
 Diamond JM
 ↵
 ↵
 Chakrabarti BK
 ↵
 ↵
 Johnson NF,
 Jefferies P,
 Hui PM
Citation Manager Formats
Article Classifications
 Physical Sciences
 Applied Physical Sciences
 Social Sciences
 Economic Sciences