{'fraction_non_alphanumeric': 0.029928226425314855, 'fraction_numerical': 0.010608044057238298, 'mean_word_length': 4.601517067003793, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, '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}}
Indirect Coordination Mechanism of MAS

There has recently been a large amount of research on the difficulty of constructing centralized control type systems, such as the next generation intelligent transport systems, artificial market systems, and next generation electronic auction systems, etc, with the expansion of the Internet, ubiquitous information communication infrastructures, complex web services, and grid computing technologies. Usually, the distributed system is constructed by many modules, and it is better that each module be more autonomous. And an agent is an autonomous module, so these systems should be constructed as multi-agent systems (MASs), from the viewpoints of efficiency, adaptability and robustness. In a MAS, the interaction mechanism between agents, and the range of view of each agent are important factors. For example, in grid computing and the web services, a system works by cooperating agents throughout the Internet, so each agent needs a wide-ranging view. On the other hand, each car and trader agent, for example, in a next generation intelligent transport system, artificial market system, or next generation electronic auction system basically behave selfishly and interact competitively for their own benefit due to a limited amount of resources. In this competitive situation, each agent does not want give information to other agents and do not interact directly. As a result, the range of view of each agent may narrow. However, even in a competitive system in which agents scramble for limited resources, the goal of the system itself is to provide higher benefits for all agents (the system must not cause a disparity in wealth). For example, in next generation intelligent transport systems, though the goal of each car navigation agent is to reach a destination faster, the system’s goal is for all cars to be able to move both efficiently and faster. In the artificial market systems, though the goal of each trader agent is to get higher benefits, the system’s goal is for all agents to benefit and not cause any disparity in wealth. Most conventional MASs are completely based on cooperated interactions. In the future, however, it is believed that some systems will be based on cooperative, but in which each agent is competitive.

The load of interactions between agents may increase in MASs based on direct interaction when the number of agent becomes too large. Moreover, a more complex interaction may be necessary if synchronized interaction is required. Therefore, when the number of agent increases, a MAS based on direct interaction may lose adaptability and robustness when new agents join dynamically and when some agents suddenly become inactive. In contrast, in a MAS based on indirect interaction, each agent has a relatively narrow range of view and the interaction between agents is indirect through, for example, the environment (the real world). For example, in nature, ants interact with each other by using pheromones. We call this "stigmergy [1]". A typical interaction model based on indirect interaction is the ant colony optimization algorithm (ACO). The ant colony optimization algorithm is one of the most well-known models of pheromone communication derived from the swarming behavior of ants in nature. Ant colony optimization is recognized as being extremely robust against and adaptable to dynamic changes in the environment, and various kinds of optimization problems have been solved using ACO-based approaches [2] . Another indirect interaction model is particle swarm optimization (PSO) [3]. PSO are population-based optimization algorithms modelled after the simulation of social behavior of bird flocks [4]. In a PSO system, a swarm of individuals (particles) fly through the search space. Each particle represents a candidate solution to the optimization problem. The position of a particle is influenced by the best position visited by itself. The goal of ACO and PSO is to get higher benefit of all agents as a whole and not to take care about each agent's benefit. In contrast, in newer systems that are larger and more complex, such as next generation intelligent transport systems, the goal is not only to obtain more benefits of all agents as a whole but also focus on obtaining benefits for each individual agent. The El Farol Bar problem [5] and Minority Game (MG) [6] are good examples of newer MASs. Minority Game is a competitive multi-agent based simulation environment for analyzing the dynamics of social economy. In MG, many agents play a simple competitive binary decision game. Even though they have no range of view and behave selfishly, certain coordinative elements emerge from the viewpoint of the agents as a whole. The most important element of MG is to make coordination a behavior rule of each agent. This rule may not be applicable to other MASs, but it is important to analyse the dynamics of MG and the behavior of each agent to find out the general-purpose behavior rules of agents.

Minority Game (MG)
First, we review the rules of MG (see Fig. 1(a)). There are n (odd number) autonomous agents, each of which independently chooses between two alternatives (group-0 or group-1) according to its personalized behavioral rules, that is, it does not see other agents' behaviors. After all of the agents choose one or the other, the agents that finish in the minority group are considered to be winners. This is one round of the game. Each winner agent is awarded one point, and the total number of winner agents is the profit in this round of the game for this multi agent system. Therefore, the more winner agents the better, that is, the smaller the difference between the number of agents in the majority and minority groups, the better. The each agent makes its selection by using one of multiple strategy tables that it holds (s tables). The entities in the table contain all combinations of m past history of the minority group choices and next decisions that corresponds to each of the combinations for the next round (see Fig. 1(b)). At the beginning of the game, each agent prepares s (s < 2) strategy tables, and 0 or 1 is allocated randomly in the next decision entries of each strategy table.
After the game starts, we cannot modify the entries of each table.
In the first round of the game, we initially set the past combinations of the winning group at random, for example, [1|1|0], and each agent randomly chooses one of its holding s strategy tables and sees the next decision entry corresponding to [1|1|0] (see Fig. 1(b)). In this case, the past combinations of the winning group is [1|1|0], so this agent sees the [1|1|0] entry and select group-1 in the next round of the game. Then if the agent becomes winner, one point is assigned to the agent and also the selected strategy table. If the agent loses, one point is deducted from the selected tables. After the score of the strategy tables for all agents are updated, the past combinations of the winning group is updated from [1|1|0] to [1|0|1] because group-1 is the winner-group in this round of the game. In the second and subsequent rounds, each agent selects the strategy table that has the highest score. The round is repeated a predetermined number of times, and the final result of the game is the total number of points acquired by the winner-agents.

Coordinated behaviors
The following overall order emerged through such simple rules. First, the standard deviation of the number of winning agents is shown in Fig. 2(a). The game was played for the number of rounds described below with the agents possessing various numbers of strategy tables, s = {2, 5, 10, 16, 32, 64} and each strategy table consists of various m, m = 3 to 16. One trial for each parameter pair, {s, m}, is 10,000 rounds of the game; ten trials were conducted for each pair. As for the simulation, we ran the game with 201 agents. Figure 2(b) shows the mean number of winning agents. The horizontal lines in Figs. 2(a) and (b) represent the standard deviation and mean value when all of the agents made random choices at all times. These graphs show that, for the lower values of s, the standard deviation was lowest and the mean number of winning agents was highest when m was from three to six. Figure 3 shows the ranking of the 201 agents by their average score. In the case where each agent randomly selected group-0 or group-1, all of the agents were able to get approximately 4750 points. In contrast, the mean score was especially high when the standard deviation was small (m=3, 4, 5) and, although some differences between agents can be seen in the scores, all or almost all of the agents were able to achieve stable high scores. This means that some kind of coordinated behavior among the agents was driving the winning-group ratio closer to 100:101 in these cases. The most interesting characteristic is that, although we would expect behavior based on longer histories to be more efficient, m larger than ten produced results that were the same as those of random behavior. As for n and m, there is a constant relationship between m and σ 2 /2n (σ is the standard deviation of Fig. 2(a)). In this chapter, we ran the game with 101, 201, and 301 agents.

Key elements for emergence of coordination
In MG, the following two rules are thought to be important elements for coordination to occur: (i) all agent must see the same entry of their strategy tables according to the past combinations of the winning group and (ii) each strategy table's point is changed like a random walk.

Winner-group history
To verify whether the past combinations of the winning group is necessary or not, we performed the following simulations: In the normal algorithm, when the past combinations of the winning group is [0|1|0], all agents see [0|1|0] entry of their holding strategy tables, and each agent selects one of its holding strategy tables, depending on their points. At this point, we performed the simulation to answer the following questions: 1. If each agent is allowed to select an entry of strategy tables randomly, can coordinated behavior occur? 2. If only one agent, agent-A, is allowed to select an entry by its own rule and the other agents use the same entry as agent-A, can coordinated behavior occur? In other words, all agents do not obey the past combinations of the winning group, but they see the same entry of their strategy table. 3. If we intentionally generate a random winner group history, can coordinated behavior? Figure 4 shows the results. The same type of coordinated behavior as with the normal algorithm could be formed in situations (2) and (3). These results show that the past combinations of the winning group itself may not be important for the emergence of coordination. As for (1), when each agent randomly selected a strategy table entry, their behaviors were the same as those based on the random group selection. Therefore, we can infer that an important point concerning strategy tables is that, in the normal algorithm, the rule that all agents depend on the past combinations of the winning group placing an adequate constraint on agents. In other words, if we can place an adequate constraint on agents like in situation (2) or (3), we may be able to use any kind of rule. Applying an adequate constraint to agents also means decreasing their freedom.

Discussion about m value
At this point let's think about why the difference between the number of agents in minorityand majority-group becomes a little in relatively small m. To begin with, since the total of 0 and 1 becomes stochastically equal because 0 and 1 of each strategy table is stored at random, so the total of 0 and 1 that each agent selects corresponding to the past combinations of the winning group must become stochastically equal too. Therefore, in each game, difference between the total of agent in minority-group and majority-group always must become a little, and if the game is repeated many times, almost all agent's winningratio will become approximately equal. That is, when m is small it is regarded that the row of 0 and 1 of each strategy table is near to above situation. And in this case, difference between the total of agent in minority-group and majority-group always becomes little and almost all agents' winning-ratio will become equal and high. On the other hand, when m becomes large the number of entries of strategy tables increases at the rate of 2 m . And at this point, let's think about the following hypothesis: Even if the total of 0 and 1 in each table becomes equal stochastically the existence probability of combination that the difference in the total of 0 and 1 in the next decision of same entry of all the agents becomes large becomes large in big m. So, when m becomes big the difference between the number of agents in minority-and majority-group cannot become a little and result may become as same as random selection case.
To verify this hypothesis, we calculated the average and standard deviation of the total of 0 when each agent would select all the past combinations of the winning group combinations in several m (n = 101). For each m value, we executed the game under 100 kinds of strategy tables and calculated average. Then, the following relation was confirmed (see Table 1); when m became large the average of total of 0 became low, this means there were big difference between total of 0 and 1 in big m, and the standard deviation became also large, this means the average was not steady in each game in big m. As a result, it can be understood that winning-ratio becomes nearly 50% steady when m is small.

Importance of indirect coordination
In MG, indirect interaction between agents is also considered to be an important element for coordination to occur. Each agent decides its behavior based on the results of each round, and its decision indirectly influences the behaviors of the other agents. In the algorithm, if the agent wins, one point is added to the selected strategy table, and if it loses one point is subtracted like a random walk. For example let us consider one agent and its two strategy tables,  Figure 6 shows the results of our investigation of this question. Unfortunately, coordinated behavior did not emerge in any of these versions. Therefore, it became apparent that the means of selecting a strategy table is closely related to the initial combinations of the strategy tables of each agent.

Discussion
As mentioned before, the scoring rule for strategy tables is similar to a random walk, that is when an agent wins, the selected strategy table's score is increased by 1 point and in case of losing, 1 point is subtracted. It is known that when a certain value changes, such as a random walk, the probability density histogram of the period when there are 0 or more points follows a power-law. We investigated how each agent selects strategy tables in detail. Figures 6(a) and (b) show the transitions of the scores for each strategy table held by the 25th-place agent of m = 3 in a coordinated situation, and the 200th-place agent of m=14 in a non-coordinated situation when the game was played with 201 agents (n=201) and each agent has two strategy tables (s=2). As Fig. 3 shows, the winning percentage goes below 50% for even the best winner agent, so the total score of each strategy table declines.
The 25th-place agent in Fig. 6(a) not only used both strategy tables in alternate shifts but also used only one table continuously. An important point is that there is no typical period for continual use of only one table. That is, the "self-similarity characteristic (power-law)" can be seen in the strategy table selection behavior of an agent in a coordinated situation. Figure 7 shows histograms of the continuously used periods of only one strategy table of all agents by log-log scale (for (a) n = 101, and (b) n = 301). The power law can be seen in both cases of m=3 (graphs were nearly straight lines). In Fig. 6(b), self-similarity cannot be seen in the results for the 200th-place agent. This result suggests that some typical continuously used periods by only one table are in the agent in a non-coordinated situation. Interestingly, the histograms for agents with m =7 show a mix of coordinated and non-coordinated situations; some agents were similar to the graphs of m =3, while others were similar to those of m=14.

Consistent constraints and power-law
From 3.1 and 3.2, we can assume that an adequate consistent constraint to all agents and a behavior rule forming a power law feature are both important assumptions for coordination to occur. Note that coordination occurs when m is small. When m is large, the coordination cannot occur due to the construction rule of the strategy table. The rules of MG may not be applied to other MASs. However, these two assumptions may be considered as important general methodologies for coordination, especially the latter assumption. When a system performs most effectively at critical a point, a power law feature can be observed. Therefore, it is necessary to analyze the dynamics of MG more in more detail.

Improvement of winning percentage using power-law feature
As shown in Fig. 8, there is a consistent relationship between the slope of the power-law and the score of each agent, and this relationship is maintained regardless of various values of n and m. That is, each agent can know its rough position among the group by seeing whether its own strategy table selection obeys the power-law or not. A possible ways to change the agent behavior without changing the strategy usage rule and random walk-based point rule is to renew the next decision entries of the strategy tables. The problem is how to decide when each agent renews its strategy tables.
www.intechopen.com Fig. 9. Scores of three kinds of evaluation-criteria.
We conducted the following are experiment in which each agent renews its strategy tables using three criteria. We executed the game with 101 agents (n = 101, s=2). After 10,000 rounds (10,000 rounds is one turn) of the game were played, each agent's behavior efficiency was evaluated with the following criteria, and each agent, which is identified as inefficient, renews its strategy tables. Then the next turns continue cyclically. In the experiment we repeated the renewing process 10 times, so 100,000 rounds were executed in total. We prepared the three criteria as follows: 1. Since the agent with its power-law slope at nearly 0 has a high winning-ratio, we randomly select u number of agents whose power-law slope is lower than in the previous turn, and they renew their strategy tables. Since the calculation of each agent's power-law is computable only from its behavior, each agent does not need to know global information such as the total number of agents in the game. However, since this criterion uses only the change in slope, even an agent with a high winning-ratio may renew its strategy tables. 2. We randomly select u number of agents whose power-law slope is lower than a certain value (0.75), and they renew their strategy tables. We use the following knowledge that is, there is a consistent relationship between the power-law slope and the winningration of each agent (Fig. 8), and this consistent relationship does not depend on the total number of participating agents in the game. Each agent knows its approximate position without knowing the total number of participating agents, and the only agents with low winning-ratios can renew their strategy tables. However, it is necessary to know that the adequate threshold value is 0.75 beforehand. 3. We select u number of agents with low scores, and they renew their strategy tables. It is necessary for each agent to know the following global information, each agent's score and the number of participating agents. This criterion can be thought of as the best way to select agents to renew their strategy tables. We prepared this criterion for comparing it to (1) and (2). Figure 9 shows the scores of 101 agents of nine kinds of evaluation settings. We executed three kinds of games (u =5, u =10, and u =20) for each evaluation criterion. As mentioned above, in each situation, the strategy table renewing process was repeated 10 times and the scores of the agents after each renewing process was plotted in the graph of each evaluation setting. As a result, the winning-ratio improved for most agents in all nine evaluations settings. This result means that each agent can know its efficiency by seeing only its behavior without global information. As for u, u=5 was little better than u=10 and u=20. The reason is that if we select too many agents, many renewed strategy tables may destroy the current strategy table's combinations of high winning-ratio agents, and thus the effect of renewing may be lost. While (3) uses some global information and focuses only on the score transition of an agent, (1) and (2) focus on agent behavior. This result shows that focusing on agent behavior is as effective as using the global information.

Conclusions
We discussed indirect coordination of MASs. Unlike direct coordination MASs, which are usually constructed from the top-down, indirect coordination MASs are constructed from the bottom-up. It is difficult to design a concrete common coordination algorithm for various applications from the bottom-up, that is, each coordination algorithm is strongly dependent on each application. However, we know that common constraints and the power-law based rule may commonly be the important assumptions for coordination in indirect coordination MASs. Moreover, we have succeeded in improving the efficiency of each agent's behavior in MG by changing the behavior rules within the range where these assumptions were not changed. This game is a competitive game for the acquisition of limited resources, so the rule of MG may be applicable for the other similar problems, but it is necessary to analyze not only individual agent dynamics but also all agents' dynamics of various kinds of indirect coordination MASs to clarify assumptions for coordination to occur.