Collective Problem Solving: Functionality beyond the Individual-
(LA-UR-98-2227 web version)
|
|
|
|
A model system is proposed and studied for the collective solution of a sequential problem using self-organizing dynamics. The model system is a large population of non-interacting agents that solve a maze using simple rules of movement. The collective solution is a combination of the solutions of the agents and performs better than the average individual agent.
The system exhibits a rich set of properties associated with complex adaptive systems (persistent disequilibrium, emergent properties, information condensation, robust performance, redundant subsystems) and is ideal as a model system for future research in a broad variety of fields. The rich results from a model that is so simple suggests that much of the complex behavior and function that we ascribe to social systems is due to the collective combination of simple processes, and not from a single function of a complex process.
The major conclusion that functionality of the whole requires contributions from all of the diverse population (and is degraded for any reduction of participation) supports the thesis that cooperation and symbiosis are the dominant processes in nature, rather than selection and competition. The study also gives insights into why specific mechanisms have evolved in biological or social systems that enables large collectives to solve problems beyond the functionality of the individual. The application of these ideas to a real world system provides specific guidelines for the development of a collective problem-solving resource for humankind using self-organizing distributed information systems, the Internet
Self-organizing, emergent or complex systems are a challenge to define with precision, likely due to the nature of the systems (complexity) but also due to the large variety of expressions. To present a common viewpoint, and to aid later discussion, we list common attributes and features. The attributes are:
- 1. Distributed resources, processes and information
- 2. Absent (or limited) centralized control, planning or prediction
- 3. Diversity (often redundant) of dynamics, capabilities or "goals"
- 4. Dynamics of persistent disequilibrium
- 5. Mechanisms for information loss, filtering or condensation
- 6. Limited connectivity of typically local extent
And global features are:
- a. Global functions or solutions from local actions or rules
- b. Robust, resilient, adaptable, fault-tolerant systems
- c. Function of the whole not dependent on individual subsystems
- d. Scalable without loss of function
Note that we will not use the words "complex adaptive systems" in the present study because of their popular application to any emergent system. We choose instead to use collective, self-organizing systems to describe distributed systems with discrete subsystems (entities) that exhibit emergent properties. Examples of these systems are diverse: in physical systems where atomic-scale entities determine macroscopic properties, in biological systems where individuals or subsystems contribute to a higher collective function such as for evolution and social insects, in human systems where individuals or organizations contribute to large scale structures. Each of these examples is well described by the lists above. To understand some of the specific attributes common to these systems and to introduce some concepts that will be used later, we will focus on the well studied, but often unrecognized, physical examples of self-organization.
Let us examine the dynamical system of atoms in a gas as modeled by hard spheres (meaning that the atoms contain no internal structure and only interact on contact). On an atomic scale, the atoms are in constant motion (item 4 above) and over any small time interval interact with atoms nearby but not atoms at any distance (6). In the determination of their dynamics, there is no global control (2), only local interactions (a). All necessary information to characterize completely the system is contained in the atoms: their position and velocity (1). Their velocities and local number density will not be single valued, but a distribution (3) that varies with atoms and in space. On a macroscopic scale, the hard sphere gas exhibits global properties. But if we look at a single atom, we cannot determine its global properties, e.g., viscosity. It is only through the collective dynamics that the property of viscosity is measurable and defined. Hence, viscosity is an emergent property of this system. And this global property is not dependent on any single atom; if one were removed, the viscosity would still be defined and unchanged (5, b, c). And finally, the system functions at any macroscopic size (d).
Kinetic or statistical mechanics theory of gases have long been established, e.g., see (Wu, 1979). These theories assume the system is comprised of collections (a collection of just one type, hard spheres, in the above example) of identical entities with dynamics governed by the same set of rules or equations (Hamiltonian equations in our hard sphere model). At the level of atoms, the system is deterministic (paths of the atoms given the same starting conditions are identically reproduced). But at a practical level, the motions are stochastic (initial conditions cannot be sufficiently controlled nor the equations accurately solved to reproduce the identical paths). Because of the stochastic variations of a collection of entities, global properties are defined from ensemble averages over many realizations, where a realization is the state (which may vary with time) resulting from an identical set of entities starting from different initial conditions. Each realization results from one selection of initial conditions. The process of applying the ensemble average to determine a global property selectively uses information from part of the entire system (such as the dynamics of the atoms in the above example) and discards other information that is not needed (such as the history of a single atom).
The above physical system is an example of a self-organizing system in which significant progress has been made in its characterization, understanding and theory. Two achievements made this possible: a general set of model equations that govern the dynamics of the system and a model system that is sufficiently simple so that the system as a whole can be studied. Ideally we wish to achieve the same for other self-organizing systems.
In computer and cognitive science, model systems and their associated governing equations, such as continuous dynamical systems theory and discrete cellular automata, have provided insight into theories of complexity, information flow, and the formation of hierarchical systems (e.g., (Crutchfield, 1994)). Similar advances have been made in biological self-organizing systems (e.g., (Kauffman, 1993)). Particularly absent to date are simple model systems that have relevance to collective decision making processes in human systems, particularly ones involving sequential paths. One pioneering work was by Axelrod in his repeated application of the Prisoner’s Dilemma (Axelrod, 1994).
The second motivation for the present study is to provide support for an effort to develop smart distributed information systems, like the Internet, as an essential problem solving resource for humankind (Johnson et al., 1998; Kantor & Johnson, 1997). This capability will be an enhancement of the self-organizing social dynamics that has guided human groups, organizations, and societies for millennia (Adams, 1988). The heightened capability is due to the unique properties of the Net, the integration of the diversity of knowledge use and the accuracy of transmission of knowledge. As our world becomes more complex, self-organizing solutions to problems will become essential as our understanding of the world either fails or cannot respond rapidly enough to changes (Slater & Bennis, 1964). The present work supports the effort in three ways: 1) to demonstrate how large groups of individuals can contribute effectively to a collective decision under ideal Net-like conditions, 2) to provide guidance in the development of the methodologies needed for this capability and 3) to provide data for the testing of these methodologies prior to their implementation on the Net.
In the following section an overview of the method is presented in order to provide a context for the later sections. Then, the problem domain and the description of the model system are presented. The next section on the simulations summarizes the results with minimal discussion. The next section discusses the simulation results within the context of the general topics of: 1) emergent properties and self-organizing systems, 2) diversity as an essential requirement in these systems, 3) comparison of traditional and self-organizing approaches to problem solving, 4) the balance of noise and coherence, 5) speculations on the evolution of these systems and 6) the usefulness of the results to real world applications.
Overview of the Model ProblemIn the following study, an individual agent represents a single person, organization or government within a larger structure. The individual is one of many similar decision making agents that is localized in either physical or knowledge space. They are identical in the sense that they have the same capabilities and have access to the same information. They differ only in their learned behavior, and their consequential experience and performance. The individual’s goal is to make a series of sequential decisions that define a path through a problem domain. Similarly, the maze is a bounded system that defines the options for the individual at a particular point in the decision process. The maze could represent a spatial problem, such as an actual maze, or a conceptual problem, such as a sequence of decisions by individuals in an organization leading to some goal. The maze has a starting and end point (goal) for all the individuals. For now, individuals are taken to be independent - they do not interact in any way with one another. We isolate the individuals, because we are interested in the dynamics of collective decision making, in the absence of the complexities of shared learning, cooperation and competition.
Simulations are done for a large number of individuals (100 to 2000). In the first of two sequential phases, the Learning Phase, the individuals use a set of Learning Rules that specify (1) their movement through the maze and (2) how they modify their own path preference at each node (these are called the Nodal Path Preferences or Nodal Preferences). All individuals use the same set of Learning Rules and only have available local information at any time. They have no global sense of the maze or their goal and explore the maze until they just happen to reach the goal. Once the Individual Nodal Preferences are determined for all the individuals, they are not modified by any later use, i.e., there is no more learning after the Learning Phase is completed.
Another set of rules, the Application Rules, then use the Nodal Preferences to find the optimal path of each individual or, as discussed next, of a collection of individuals. The Application Rules select the preferred path based on typically the largest magnitude of the Nodal Preferences at a node. Because random choices are made in the rules between paths of equal preference, a diversity of areas frequented in the maze and a diversity of total path lengths (performance) are created. The meaning of an optimal path will be discussed later, but for now the path resulting from the Application Phase is a measure of the performance of the individual. In general, the individual’s optimal path is not necessarily reproducible or unique: if the individual solves for their optimal path many times, the path may differ from solution to solution due to the random selection between choices of equal preference. Hence, a path from one simulation of the Application Phase represents a single realization of many possible realizations for that individual.
To motivate the division of the solution method in to two parts, the following analogy is made. When an ant is looking for food, it first forages by searching the space. Not knowing where the food is located, it searches until the food is found. This process corresponds to the Learning Phase. Once the food is located, the ant is able to use the pheromones laid down in the earlier foraging to optimize its path to the food on the return trip. This process corresponds to the Application Phase. Typically the Learning and Application Phases are joined in a dynamic process where learning occurs during the application process, but by dividing the solution into two phases the resulting system is more amenable to study by its simplicity.
Once the Individual Nodal Preferences are found from the Learning Phase, these are combined at each node in different ways to create Collective Nodal Preferences. The same set of the Application Rules is then used to determine a collective solution. As for the individual solution, the collective solution is not unique. Different choices are examined for the modification of the Individual Nodal Preferences in the creation of the Collective Nodal Preferences. For example, the simplest construction of a Collective Nodal Preference is the average of the Individual Nodal Preferences at each node for all of the individuals in a sample population. The collective solution using this simple Collective Nodal Preference is called the reference simulation and is used for comparison to other choices of generating the Collective Nodal Preferences. To evaluate the improvement of the collective solution, the collective advantage is the relative performance of the collective over the average performance of the individuals in the collective as determined from the Individual Application Phase.
A pivotal development in the method was the determination of the final Rules for both the Learning and Application Phases. This was an evolutionary process, governed by the following guidelines:
- All Rules use only information that is locally available. No global information is used.
- Keep the Rules as simple as possible, even if performance is reduced.
- Chose a set of rules that are not sensitive to small changes in the parameters.
- Chose parameters that minimize the randomness of the individual solutions.
- Construct Rules that result in final Nodal Preferences for a link between two nodes to have a preferred direction (larger value at one node).
- When all else fails, pick a random node to go to.
- Pick rules that eliminate infinite paths.
No absolute justification can be made for the final choice of the Rules, but the following thoughts motivated the above guidelines. The first guideline is a necessary requirement for a self-organizing system as listed earlier; it also assures the method will scale without additional computational burden. The second guideline is motivated by the belief that simple rules can lead to sophisticated behavior, and the desire to have a system of Rules that might be tractable by a theory. The third guideline is a desire for a stable and robust solution, to minimize simulation difficulties. The fourth through sixth guidelines were found from experience to strengthen the convergence of the collective solution. It was found that the primary problem was not finding a good solution, but avoiding infinite paths (since individuals are not allowed to die). At first examination, it would appear that these guidelines can not all be satisfied, especially the ones that would compromise the performance of the final solution. But remarkably, the final choice of Rules satisfied all of the above guidelines.
Problem Domain and ApproachThe domain for the simulations is a connected, undirected graph with arbitrary connectivity (edges in graph theory) between nodes or vertices. To simplify the solution space, the following are assumed: (1) a node cannot be connected to itself, (2) the connectivity is fixed (does not change during the simulation), and (3) at least one path (sequence of connected edges) must join the start and end nodes. Otherwise, the graph is unrestricted: a node can have any number of connections to other nodes, from zero (if it is not a start or end node) to all the other nodes in the system.
We note that currently in the problem definition, a "length" is not associated with edges, and the only information associated with a link is the logical connectivity between two nodes. Hence the path "lengths" refer to the number of connections or edges in the path, not the actual length of a path. Because no lengths are associated with the edges, the graph can be presented in any dimensional space. This treatment is ideal for the representation of a knowledge space, such as the Internet.
The problem domain or "maze" is established from the graph by defining a start and end node. The goal of the agents in the simulations is to begin at the "start" node and finish at the "end" node, thereby "solving" the maze.Fig 1 shows the example maze with 35 nodes. Two of the minimum paths out of a total of 14 unique minimum paths are highlighted. Note that the maze has three primary minimum solution paths, where a primary path has a common portion of the path that does not change. The maze in Fig. 1 will be used for all later simulations, unless noted.
Fig. 1. The example maze. Two of the 14 minimum length paths are highlighted.
At each node in the maze and for each individual, a Nodal Path Preference, a scalar number, is stored for the end of each link connected to that node. It is called a preference, because the link where this value is relatively large, in comparison to the other preferences at that node, will be the most likely choice of a path. Together, all the Nodal Path Preferences for one individual can be described as a directed graph overlaying the undirected graph that constitutes the maze. (A directed edge has two values associated with the two ends.) There is a set of Nodal Path Preferences for each individual, and because the individuals are independent, each individual has access only to its own Nodal Path Preferences.
Let 
be
the Nodal Path Preference for individual m for link i to j by
link q. (Note that we use P for the an individual and ü for
the collective; we use bold symbol for these variables when it is being used
to describe more than a single value, i.e., when the subscripts are absent.
The index m is for members, i and j for nodes, and p and q for
edges.) Once P is determined from the Learning Phase, it is
never modified.
Although P is associated with a single individual, it is best thought of as being a property of the maze. An individual only has access to values of P local to its current position. This perspective is consistent with the earlier analogy of an ant solution to a maze using pheromones as a path marker; the pheromones are a property of the maze. The individual, which is an agent that moves through the maze, does not carry the information of P with them. While global access could be given in an alternative scheme, we restrict the access to P in order to develop a local method.
Learning Phase Rules: Exploring the Domain
The individual begins at the start node and P is initialized to 0.0. The following rules determine the choice of a next node, call it j, and the modifications of P, when an individual is at node i:
- If the current node is the end node then stop.
- If there exists any connecting node with
- - Choose a link randomly from the set of links with a value of
- - Set
- (or any value greater than zero and less than one),
- - Set all other links with
- (or any value greater than or equal to zero and less than one).
- If all links have
- - Choose a link with the maximum value of
where * means the results are indifferent to this choice. The above set of rules is called the Learning Rules. The strategy of the development of this set of rules was discussed earlier. In retrospect, it was found that these rules can be motivated by the previous ant analogy during the process of foraging for food. By marking its trial through space, an ant attempts to explore the space completely by not repeating past choices when possible and by leaving information behind that enables the last choice, presumably the best, to be chosen once food is found. We note that while the ant analogy did not motivate the creation of the above rules, in retrospect, these rules gave good results and were most simple of all the ones examined. This P is not modified after the end of the individual's exploration of the maze.
Application Phase Rules: Applying Knowledge of the Domain
The individual begins at the start node. The following rules determine the choice of a next node, call it j, when an individual is at node i:
- If i is the end node, then stop.
- From the set of links connected to i that have not already been tried:
- - Choose j randomly from the links that have a maximum value of (the maximum value can be zero) and if possible, exclude from this choice the last node occupied.
- - Mark the link to j as having been tried and exit.
- If all the links have been tried
- - Pick j at random from all links and exit.
The Application Rules select for the maximum value of ,
excluding the node just vacated or the ones that have already been tried.
Again we can motivate these rules by the ant analogy during the process of
returning to food found after foraging. The ant will select the path with
the strongest pheromone track, excluding the trail that it came from. Note
that the values of P are not modified in this phase,
i.e., there is no learning during the Application Phase. In some sense the
rules of the Learning Phase are reversed: the maximum values of P are
used first, and if they fail to find the path, then a random search is used.
Also note that only local information is used.
Alternative Application Rules: Probabilistic Selection
In the Application Rules above, the guiding principle was to select the maximum value of P at a node when possible. An alternative would be to select from the Nodal Preferences based on a probabilistic selection: randomly select from the links such that over many selections the frequency of selection will duplicate the values in P. The significance of this alternative principle is discussed later. This option is implemented by defining a cumulative distribution function, C, such that:
for p = 1 to Ni (1)
where Ni is the number of links connected to node i. A link is selected by finding a random number, r, between 0 and 1 and then finding a link q such that:
for q = 1 to Ni (2)
where 
is
0. In the Application Rules, performance of the method was improved if returning
to the node that was just vacated (backstepping) was eliminated from the
possible choices. This option can be examined in the probabilistic approach
by setting the contribution to 
for
this link to zero in Eq. 1.
Forming a Collective Nodal Path Preference: ü
By applying the above Learning Phase to many individuals, a population of P are found, which differ both in exploration of different parts of the maze and in different degrees of "performance" as determined from the path length in the individual Application Phase. For a collection of individuals (an ensemble) P can then be combined at each node in various ways to create Collective Nodal Path Preferences, ü. Then the same set of the Application Rules, as given above for an individual, is used to determine a path through the maze for the collective.
For example, a simple Collective Nodal Preference is the average of the Individual Path Preferences at each node for all of the individuals in a sample population.
(3)
where the sum is over the values of m in the set {g} and Ng is the number of members in {g}. We attach the superscript * to ü to identify it as the value of ü used for the reference simulation. As we shall see in the results in the next section, this simple average results in a collective simulation that typically finds a minimum path of the maze when the Learning and Application Rules are used for a sufficiently large population in the collective.
Other ways of constructing ü are a modification (as described below) of the P of the individuals that make up the collective. Because P represents an individual’s preferences or opinions at a juncture in a decision process, a psychological interpretation can be associated with the modification. For example, ücan be created from only the maximum values of P in Eq. 3 at a node from each individual, setting to zero the values of P that are less than the maximum. The interpretation is a situation where an individual contributes to the collective decision only the opinions that are strongest, omitting the less important ones.
In the study of different ways of combining the individual's contribution to form a collective preference, we consider two types of degradation: noise in the contribution and loss of information of a contribution.
Noise is the random replacement of information contributed by the individual to the collective decision. Because it replaces valid information, noise represents false or inconsistent information. The emphasis of the usage of noise is the random introduction of false information. The magnitude of the noise is relative to the information that it replaces.
The effect of noise is implemented in the simulations by
the random replacement of by
a small value (0.1 is used but the results are insensitive to this value
if it is less than unity) with a specified frequency in the creation of ü. For
example, for a frequency of 0.3, any Nodal Preference will, on average, be
replaced by 0.1 in Eq. 3 thirty percent of the time.
Loss is the selective reduction of information contributed by the individual to the collective decision. For example, loss can be the selective elimination of some individuals out of a set of contributing individuals (an ensemble set, defined in the next subsection) or by the selective modification of the information contributed by an individual, as in the example in the last subsection of the elimination of weaker opinions. The emphasis of loss is the selective reduction of information. The effect of loss is to reduce the information available to the collective, but loss does not add false information to the collective decision.
To simplify the many possible options, the following formalism captures many of the options for loss discussed later.
(4)
(5)
(6)
where
. (7)
and where a is the attenuation of the maximum value (a Ò0), b is the reduction of the dynamic range (maximum minus minimum) (0Ób Ó1) and t is the value of P ' below which the contribution to ü is zero, otherwise it is unchanged. For b=1, the limiting expression for Eq. 6 is
(8)
Eq. 3 for the reference simulation is reproduced in Eq. 8 with a = 1 and t = 0. These equations are constructed such that the maximum before and after the "flattening" of Pmi using b < 1 is unchanged. Therefore, in the limit of b=0, only the maximum value of Pmi is selected:
. (9)
Statistics in the collective solution
Even though all individuals are identical in their capabilities and their access to information, the random choices in the rules of the Learning Phase lead to a diversity of paths and performance. Consequently, the simulations of the collectives made up of this diverse population of individuals exhibit path lengths which have variation or randomness depending on the different individuals contributing to a collective of a fixed size. This is particularly true when a few individuals make up the collective. These variations occurred in both in the number of steps in the path length and in the path taken in the maze.
A collective solution comprised of a fixed number of individuals can differ in two ways. First by the different individuals that contribute to the collective preference as selected from the entire population, and, secondly, by the different random numbers that are used within a fixed set of individuals. The second difference means that if two different sets of random numbers are used in two collective simulations with the identical set of individuals, different collective results can occur. This is equivalent to the earlier observation that different results can occur for an individual in the Application Phase for different choices of random numbers. Because this variation closely duplicates the approach of the statistical mechanics, we will borrow the formalism to describe the results and averages used in the collective solutions.
In order to collect statistics on the first type of variation, we define an ensemble for a collective as a set {g} of members in a collective as found from a random sampling of individuals from the entire population of individuals without duplication. For example, one ensemble of a collective with 5 individuals is (3,22,6,81,15) from a population of 100. Another ensemble is (24, 3,10,5,29). And so on. We define a realization of an ensemble as the collective solution for a given ensemble. For a given ensemble size, there also can be many realizations, either from different member compositions or from different random numbers. A collection of ensembles with the same number of individuals is called an ensemble set. The average of the results of a collective simulation over an ensemble set is the ensemble average. Statistics for the simulations are collected for ensemble averages for the range of individuals from 1 to the maximum ensemble size.
Thus, two additional gradations are added to the original formalism of statistical mechanics. One is that there is a size associated with each ensemble. In classical statistical mechanics an ensemble is made up of all the entities of the system. The corresponding concept in the present approach is the individual ensemble average as an average of the realizations of all the individuals in the population. Secondly, there are two types of realizations possible: one results from the different composition of members (initial conditions) and another from a different set of random numbers.
Simulation resultsThe results of the simulations using the Learning Phase and then the Application Phase defined in the last section are presented. The coding for all the simulations was done within Mathematica, and execution time was ten minutes for the reference simulation and a few hours for the simulations with thousands of members.
The Learning Phase was applied to a large population using the Learning Rules and a variety of random walk methods (Table 1). The first random walk method in Table 1 is just the random selection of a new node at the current location. The no-backstep random walk is the random selection of a new node excluding the node that was just vacated. And the non-repeating random walk is the selection, if possible, of only untried links. Also, in the table are the statistics for simulations for 1000 individuals, indicating the large samples needed for reasonable statistics. Note that the sample range will not converge as the population rises, as this is a measure of the extremes of the distribution: the greater the ensemble, the greater the extreme. Note the order of average path length for the four methods. Because the Learning Rules capture both the no-backstep and non-repeating options, in addition to other features, it performs the best of the four.
Table 1. Path Lengths for a variety of methods for a population of 100 (except as noted). The simulation marked by * uses a different series of random numbers than the others.
|
|
|
|
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Simulations using the Application Rules
In Table 2 the results of the simulations using the Application Rules are shown for the four methods listed in Table 1. In order to apply the Application Rules to the simulations that use the random walk methods, P was generated for these methods by initializing P to zero and then incrementing the Pmiq by 1 each time the link q is used by individual m at node i in the random walk.
In all cases the path length and standard deviation are improved by using the information from the Learning Phase. Note that the results of the optimized random walk simulations (no-backstep and non-repeating) are similar in performance and are close to the results in the Learning Phase using the Learning Rules. Essentially the combination of the Application Rules on the optimized random walk methods comes close to duplicating the Learning Rules.
Table 2. Path Lengths for the Application Phase for a population of 100 (except as noted) for a variety of P from the different methods listed in Table 1. For comparison, the quantities in brackets are similar values from the Learning Phase from Table 1.
|
|
|
|
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Correlation between Performance in the Learning and Application Phases
Because the Learning Phase and Application Phase are separate, the cross-correlation between the performance in the Learning Phase with the performance in the Application Phase can be assessed. The Pearson's correlation coefficient between the number of steps in the Learning and Application phase is 0.12 for a population of 1000, indicating a weak correlation in the two sets of data. This information is shown graphically in Fig. 2. Note that 1000 individuals are represented in the figure, but fewer symbols appear because many of the data occupy the same coordinate. The absence of a diagonal dominance in the plot supports the weak correlation between the two sets of data. We can conclude for these results that "slow" learners are not necessarily "poor" performers.
One notable aspect in the plot is the absence above the line where performance in the Learning Phase is equal to the performance in the Application Phase. Because the Application Rules preferentially select against options that have not been explored, the Application path will usually not be longer than the Learning path. Hence this region of the cross-plot should be sparsely populated. Because this region is actually void, this indicates that the Application Rules never select paths that have not been already explored (the maximum in Rule 2 is never zero). This is a reasonable result because the Learning Phase continues until the end node is found, and therefore a solution must exist within the values of P. By construction, the Application Rules must find at least the prior solution.
The above discussion illustrates an important property of the Application Rules. If a path in the Learning Phase crossed its earlier path, then the Application Rules will eliminate the loop and select the most recent (in terms of steps) path. If the Learning Phase never crosses its own path, then the Application Rules will duplicate the Learning Phase path.
Fig. 2. Cross plot of the performance (number of steps) in the Learning Phase versus the Application Phase for each member of a population of 1000.
Simulations using the Alternative Application Rules: Probabilistic Selection
As an alternative to the Application Rules that select for the maximum of the P, Table 3 shows the results of the probabilistic selection. Generally there is little change using the probabilistic approach over the standard Application Rules (later we will see that this is not true for the collective results). The large change in the standard deviation when backstepping is removed from the probabilistic approach is due to one result with a very high path length (182) when compared to the next highest result (23). This increases the deviation but has little affect on the mean. Excluding the one point results in the two probabilistic methods being almost identical.
Table 3. Path Lengths using the Probabilistic Selection, compared to the standard Application Phase, for a population of 100, all using the same P from the Learning Rules.
|
|
|
|
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Collective Solutions: Chaos and Diversity
The collective solutions, as described in the prior section, are examined using Eq. 3 with the Learning and Application Rules. In the later sections, noise and loss effects are considered.
Fig. 3 shows the effect of including larger numbers of individuals in the collective solution, one realization for each ensemble. Although significant variation occurs, particularly for smaller collectives, the collective solution is always better than the average individual when a collective has 20 or more individuals. This will be more apparent in later figures which include ensemble averages over many realizations.
Also shown in Fig. 3 are two different selections of the ensembles of different size. The differences in the two curves are due to a lesser extent from random choices made in the Application Rules, and to a greater extent, from the combination of different sets of individuals that make up the collective. For example, an ensemble with 5 members is shown for two ensembles: (3,22,6,81,15) and (24, 3,10,5,29). With fewer members in the ensemble, the potential diversity in the contributions of the individuals can be more apparent. We use diversity to describe both types of experience in different regions of the maze and different levels of performance.
Fig. 3. The path lengths (number of steps) for two different selections for the increasing series of ensembles.
Another approach to creating an increasing series of ensembles is to add an individual onto an existing ensemble: e.g., (5), (5,66), (5,66,35), (5,66,55,99), etc. This cumulative ensemble illustrates the effect of the addition of a single individual on an existing collective solution (Fig. 4). Not surprisingly, the effect of an individual is greater for smaller collectives than larger ones. Even so, the simulations continue to show sensitivity to the addition of a single individual, even in very large collectives. This is essentially a demonstration of the chaotic nature of the system: an infinitesimal change in ü can lead to a large effect in the global path length. In fact, the full chaotic nature of the system is not captured Fig. 4. For a given path length there are many paths of the same length, e.g., the two highlighted paths in Fig. 1. In an animation of the actual paths shown in Fig. 4, a major change in the path through the maze can occur for the addition of one individual, without a change in path length. This is a consequence of the multiple primary paths through the maze and the resultant indeterminacy of the selection of one of these paths over another.
It is observed that the solution tends towards the minimum path for larger numbers of individuals in the collective. This is a surprising result, given that the rules for both phases were specifically chosen to use only local information.
Fig 4. Path Lengths for a series of collective solutions that adds an individual onto the list of individuals in the previous ensemble, for two different samplings of 100 (same population as in Tables 1 and 2).
Quicktime Animation of the results (red curve) in Fig. 4. Note that the minimum path length in Fig. 4 is comprised of two of the three primary paths for the minimum length through the maze.
To ascertain the effect of the random choices in the Application Phase on the collective solutions, different seeds for the random number generator were used for the Application Phase for 20 identical ensembles (those that made up the solid curve in Fig 4). For a given ensemble, the 20 simulations have the identical members contributing to the collective (this is a degenerate ensemble set in which each ensemble is composed of the same individuals). The only difference in the simulations were the random numbers used in choices that had equal preference (multiple maxima in ü at a node). In Fig 5, the resulting ensemble average length is shown for the 20 identical ensembles (compare to the solid curve in Fig 4). In Fig. 5, the standard deviation (solid curve) of the 20 simulations is shown, showing that the only deviation occurs at points 2-5 and 61 on the abscissa. These results illustrate that sensitivity exists in the solution, but gives no information about the degree of sensitivity. The same study was repeated, but relaxing the test for the maximum of ü at a node in the Application Rules to be within 10 percent of the maximum. These results are also presented in Fig. 5. Two conclusions can be made: that the simulations are sensitive to changes in Application Rules, but that the effect is to moderate the results, with a decreasing effect for larger numbers in the ensemble.
Fig. 5. Average path length and standard deviation for 20 simulations of the ensembles in Fig 4 with different random numbers. The "fuzzy" curve is with the effect of a 10% relaxation in the maximum value test in the Application Rules.
The Use of Probabilistic Selection on ü
In the subsection on the Individual Application Phase, the Probabilistic selection method was shown to result in path lengths that were only slightly degraded from the average performance of the Application Rules (15.9 versus 12.8 in Table 3). The identical Probabilistic selection method is now applied to ü. As seen in Fig. 6, the Probabilistic method produces significantly degraded results for larger sizes of collectives, particularly for the Probabilistic option where backstepping is allowed.
In the Probabilistic simulation with backstepping, the cause of the increased path length with larger collectives is a result of the ü becoming more uniform (isotropic) at a node. At the isotropic limit of equal preferences, the Probabilistic solution degenerates to a random walk with a path length around 128 (see Table 1). While ü does not become isotropic for infinite collectives, the difference in the minimum and maximum weightings at a node does decrease, causing side paths, which increase the final path length, to become more likely. Both Probabilistic approaches in Fig. 6 were extended to 500 members in the collective; the curve for the Probabilistic method without backstepping behaved similarly as in Fig. 6, but for the Probabilistic method with backstepping the mean and the variation continued to grow.
In the Probabilistic solutions without backstepping, apparently the effect of not returning to the node just vacated is sufficient to prevent the solution from shifting to the random walk solution. The reason for this major difference between the two Probabilistic solutions is not fully understood.
Fig. 6. Comparison of path lengths for the two options for the Probabilistic Selection (Table 3) and the Application Rules for a cumulative ensemble. The reference simulation for the Application Rules, the solid line, is the same as the solid line in Fig. 4.
The prior sections established variations in the realizations of the collective solutions. Henceforth, the results of the collective simulations will be presented as ensemble average of ensemble sets, specifically for an ensemble set with fifty ensembles selected from a population of 100 individuals. For example, the results for the first data point is an ensemble average of fifty simulations with one individual participating, each randomly selected without repeating from a population of 100 members (same as Table 1 and 2). The second point is fifty simulations with two individuals contributing to ü, each pair randomly selected from the population of 100, and so on.
To easily identify the relative improvement of the collective over the performance of the individual, the collective path lengths are normalized by the average of the performance of the individuals making up the ensemble set. Because the deviation is relatively low for the Application Rules (Table 2), the actual path lengths are approximately the normalized value times 12.8.
In Fig. 7, the reference simulation is shown for a collective with the ü* in Eq. 3. Two of the 50 curves that make up Fig. 7 are from Fig 3. Also shown in Fig. 7 is another ensemble set of 50 simulations with ensembles of individuals and with a different sequence of random numbers, but which are taken from the identical population of 100 individuals. We see the variation of the results is still high at low numbers of individuals but low at higher numbers of individuals. Fig. 7 indicates that the collective, on average, does better than the average individual for a collective greater than 5 members and that the collective finds a minimum path with collectives of 20 members or greater.
Fig 7. Normalized path length for two selections of ensemble sets. Each point on a curve is an average of 50 simulations of the ensemble set. Normalization uses the average path length of the Individual Application Phase of the individuals in the ensemble set.
Comparison of the Averaged Collective Solutions for Different P
How is the collective solution, using the same Application Rules, affected by P from different methods in the Learning Phase? In Table 4 is a summary of the three sets of simulations: the Learning Phase, the Individual Application Phase and the Collective Application Phase. The only difference between the simulation sets is that P is generated by four different methods, as listed. The number for the Individual Application Phase is an average over 100 simulations, one for each individual P, as taken from Table 3. The number for the Collective Application Phase is from a single simulation using 100 individuals contributing to ü. In Table 4 are also listed the standard deviation of the 50 ensembles for the collective path length with 20 members.
Table 4. Path Lengths for the Application Phase for different Learning Phases for a population of 100. All use the Application Rules. The quantities in the parentheses are the standard deviation.
|
|
|
|
|
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
In terms of the collective advantage in the Application Phase, the Non-Repeating Random Walk shows the greatest improvement at 3.6. In Figs. 8 and 9 are shown the actual and normalized path lengths for the four methods in the Learning Phase as a function of the number of individuals in the ensemble. What is most notable from these results is that P for the Random Walk solution does not result in an improvement over the individual solution and, in fact, shows no trend towards converging to a limiting solution for any number of members. It is not understood why there is no improvement with the collective solution for the random walk. Out of the many different methods (hundreds) for the Learning Phase, only the P from the Random Walk solution resulted in a degradation of the collective solution.
Fig. 8. Path lengths for the four choices of P in Table 4.
Fig. 9. Normalized path lengths for the four choices of P.
Comments on Loss and Noise in the Collective
For the rest of this section, results are presented that show the effect of noise and loss of information on the performance of the collective. Specifically, we wish to explore the possibility that failures in communication or even policies of exclusion are the cause of degradation of the collective solutions in traditional ways of cooperation. Before proceeding, a few comments about the general nature of the simulation can be made.
In general, the collective solution is remarkably robust. Degradation of the individual's contribution, however implemented, generally had no effect or postponed the convergence to the minimal solution. In fact, the challenge quickly became trying to find ways to degrade the collective solution. Equally important, and possibly related, was that no alterations were found which generally improved the collective solution in comparison to the simple average over P; the robustness and the optimal performance appear to be fundamental properties of the system.
The Effects of Random Noise on a Collective
Noise in this context, as defined earlier, is the random replacement of valid information in the individual’s contribution to the collective, thereby creating false information. Fig. 10 shows the effect of the addition of noise in the simulations with different frequencies: 0.0, 0.3, 0.7, and 0.9, where 0.0 represents the reference simulation. These results were insensitive to the magnitude of the noise (0.1), as long as it was less than one.
Fig. 10 illustrates the remarkable insensitivity of the collective solution at the addition of noise at low frequencies. Even at higher frequencies, the tendency is only to delay the advantage of the collective to larger numbers of individuals. Although not shown, the collective solution degrades to the Non-Repeating Random Walk solution (Table 2) at frequencies of addition above 0.95 for collectives with 50 members, a verification of the robustness of the collective solution. Also note that an individual (one on the abscissa) is much more sensitive to noise than the collective. This occurs because noise adds false information that leads an individual to parts of the maze for which they have no experience from the Learning Phase. In unexplored regions of the maze, the Application Rules degenerate to a random walk approach and lead to significantly longer path lengths. For collectives, particularly large collectives, experience is available throughout the entire maze and, therefore, the collective cannot be misdirected by false information to unknown parts of the maze. This is a clear demonstration how diversity, or in this case of experience, assists the collective decision.
Fig. 10. The effect of the random replacement of the individual's Nodal Preference for different frequencies of replacement.
The Effects of Loss on a Collective
As defined earlier, loss is the selective reduction of information contributed by the individual to the collective decision. Unlike noise, there are almost unlimited possibilities for loss in the present context. The few examples presented below are one of many that were examined and were chosen either because they have a significant degrading effect or because they have a relevant or interesting interpretation in the context of a decision by a collective.
One less interesting loss mechanism is the effect of a in Eq. 6 with b = 1 and t = 0. The resulting collective solutions are identical to the reference simulations (Fig. 7) for any value of a greater than zero. This insensitivity is easily understood by the observation that because the Application Rules contain no parameters that would set a scale, the results must be insensitive to a uniformly applied multiplicative constant. This observation eliminates a whole class of loss mechanisms where the magnitude of the individual preference is reduced for all contributors, either selectively at certain nodes or uniformly across the maze. In the next subsections the effect is examined of changing the magnitudes of preferences selectively of an individual at a node.
Reduction or loss of the extremes of an individual’s contribution
What happens if the nodal preferences of each individual are flattened so that the difference between the maximum and minimum values is reduced (b < 1 with a = 1 and t = 0 in Eq. 6)? Fig. 11 shows the results with b=0.1. Except for collectives with two individuals, this loss of information has little effect on the collective solution. The effect of flattening the preferences might be interpreted as reducing the extremes of opinions.
The effect on the couple is subtle but relevant to later results. It was generally found that couples have a lower performance than individuals or larger collectives. The source of the degradation appears to be that with only two contributors, particularly with high performers, there often is direct opposition of a preferred path. As a consequence, the collective solution is degraded by the indeterminacy between two preferred paths. With the addition of more individuals, particularly of different levels of performance, the conflict is moderated and the collective functions better. Here, the same effect is achieved for the couple by the flattening of each individual’s preferences.
Fig. 11. The effect of reducing the extremes of the preferences of an individual. Note that the same individuals contribute each point in both curves, only their contributions to the ü differ.
Loss of minor preferences or opinions
What happens if only the maximum preferences of an individual at a node are contributed to ü (b=0.0001, t= 0.9999)? Fig. 12 shows the effect is similar to the one discussed in the last subsection for couples: by emphasizing the dominant preferences, greater variation in performance is introduced and generally the collective has a lower performance. Interestingly, the individual and couple solution (first and second point) is unchanged. For the individual this signifies that the Application Rules are always selecting the maximum preference. For the couple, this reinforces the comments at the end of the last subsection. Note also that the variation caused by this loss becomes less for larger numbers in the collective.
Fig. 12. The effect of contributing only the strongest preferences to the collective.
Complete loss of extremes of the individual
What happens if the individual’s contributions at each node are made isotropic (b = 0), i.e., all nodes (not edges) that have been visited in the Learning Phase have preferences of equal importance? This has the opposite effect as the loss of minor preferences in the last example and is the limit of the loss of extremes in the first example. The social analogy might be an individual that cannot distinguish between important or unimportant contributions.
As seen in Fig. 13, the loss of individual preference is extremely disruptive to the collective; in fact, no improvement is observed for larger collectives. Had all the nodal preferences been made equal, the Non-Repeating Random Walk would be recovered. But because nodes that have not been visited are unchanged, some information is retained from the Learning Phase, sufficient to give about a 20 percent improvement over the Non-Repeating Random Walk result (Table 1). Also in Fig. 13 are shown the results when just the non-zero preferences are replaced with unity; this simulation limits the collective to portions of the maze for which some prior experience exists. While not as disruptive as the option with b = 0, this also emphasizes the importance of differentiation of an individual’s preferences.
Fig. 13. The effect of an individual with an inability to distinguish between major and minor preferences.
This concludes the study of modifying uniformly all individual preferences. The general observation can be made that any modification of this type has either no effect or is detrimental. This is contrary to a reasonable expectation that some type of filtering would enhance the collective effect. As will be further reinforced in the next sections, the collective advantage appears to rely on an unfiltered diversity of experience. The implications of these observations are discussed in detail later.
Another major degradation of the collective's performance was the random selection and use of the nodal preference of one of the contributing individuals, with a different individual selected at each node (see Fig. 14). This is still characterized as a loss mechanism, even though it involves a random selection, because no false information is added. The degradation is severe, resulting in a solution much worse than the average individual and showing no tendency to improve with larger numbers in the collective.
This implementation is probably the worst case of leadership in a collective decision, but illustrates how the change of a dominant individual during a sequential solution process can yield results much worse than that of an average individual in a system with diversity. Although not examined, a better alternative would be to select one individual for many steps in the maze. But this approach, at best, would only duplicate the performance of an individual and not show the advantages of a collective solution.
Fig. 14. The effect of randomly selecting a "leader" at each node from the collective.
The Effects of Diversity of Goals of the Individual
One of the observed properties of distributed, self-organizing systems is the ability to find solutions in the presence of conflicting information. To model this type of problem in the present system, 33 individuals each were trained in the Learning Phase on three different end nodes in the maze (In Fig. 1, nodes 21, 27 and 35 as counted from the start node going right, then across again going to the right). We then have the population as a whole find each of these end nodes and compare the performance of the collective relative to the average performance of the individual.
Fig. 17 shows the performance of the collective for the three different goals. Clearly the collective does much better than the average individual, but the results are less impressive than they appear. The average individual performances for the Application Phase with end nodes {21, 27, 35} is {67, 17, 35}, compared to the minimum path length {9, 7, 9}. The individuals do poorly in the Application Phase compared to the prior simulations, because in order to find a node outside their experience from the Learning Phase, the Application Rules degenerate to an optimized Random Walk solution to find the end node.
The collective path length with 100 members is {10, 14, 12} respectively, all longer than the minimum path lengths. This performance, which is worse than was previously observed for the unmodified collective solution, is because the simple method for generating a collective decision assumes that the population is trained on the same goal as will be used in the Application Phase. In the present circumstances the training on a goal different than the end node leads to conflicting information about the optimal path in the maze. It is not understood how the collective resolves this conflict and achieves a reasonable solution, far better than the average individual’s performance. More studies of this type are needed to better understand the dynamics of the system. This example is presented as a demonstration that the proposed model system can be used to examine an important feature of self-organizing systems, that of finding solutions in the presence of conflicting information.
Fig. 17. The performance of a collective solution in the presence of conflicting information.
(Text and two figures deleted - see paper for replacement text)
Study of Maze Complexity with Fixed Individual Ability
All of the above studies examined different individual or collective capabilities while keeping the problem domain fixed (Fig. 1). In this subsection, exploitative results are presented for alternative mazes while holding fixed the individual and collective approach (using the Learning and Application Rules with ü* in Eq. 3) for a population of 500 individuals.
Because the performance of the average individual and the collective were comparable in the reference simulations, one question that arises in the prior studies is: How does the collective advantage depend on the individual performance? This question is addressed by simulations on increasingly larger mazes. To simplify the study, coding was developed that randomly generates mazes of arbitrary size. Fig. 18 shows four mazes of different sizes used in the study. Table 5 shows the summary of simulations based on the Learning and Application Rules, including the result for larger numbers in the collective for the reference simulation. Fig 19 shows how performance of the collective solution changes with the different mazes. The simulation for maze number 6 has been extended to 2000 members in the collective, and the collective solution reached 12 with 2000 members and is still declining.
The following tentative conclusions can be drawn: 1) a simple maze to a good individual solver is a trivial problem, and minimal improvement is obtained in the collective solution. 2) The rate of improvement of the collective declines as the maze size is increased (larger numbers of individuals are needed to collectively solve harder problems). 3) The relative improvement of the collective over the individual reaches a maximum and then declines again as the maze size increases. Because performance of the collective is dependent on the problem domain, in particular the number and kind of multiple paths, the present study of this issue is incomplete. Hence the conclusions are tentative until characterization of the problem domains and their effect on the collective solution is studied.
Fig. 18. Four randomly generated mazes. The start and end points are the lower left and upper right in each maze, respectively.
Table 5. Path lengths for mazes of different sizes (From Figs. 1 and 18) for a population of 500 individuals using the Learning and Application Rules. (Colors correspond to those in Fig. 19.)
|
|
|
|
|
|
|---|---|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Discussion and Implications
Fig. 19. The normalized path lengths for different mazes using the same Learning and Applications rules with ü*.
In this section the implications, sometimes speculative, of the simulation results are presented. If there is a main theme, it is that we, as social scientists, psychologists, humanists, may not have exploited an alternative explanation for the high functionality of human, and in general biological, collective decision making systems: high functionality can result from simple interactions of a diverse population. Possibly the acceptance of this explanation has been the absence of a simple model system from which we can increase our understanding of systems with collective problem solving. An alternative statement of this theme is: How do we solve problems that are greater than the traditional resources we have available? How can we take advantage of this resource? How is it to be encouraged and developed?
Emergent Properties of a Self-Organizing System
Because the minimum path requires global information about the structure of the maze, the minimum path or any "shorter" path is a global property of the maze. Because global information is not used in the Rules for either phase, the occurrence of a short or minimum path in the simulations is an emergent property of the system. Alternatively, nothing in the Rules can predict that a short path through the maze would be found.
One of the fundamental concepts of self-organizing systems is that local behavior or activity contributes to a higher functionality or structure than is locally observable or expressed. In the current simulations, the agents in the Learning Phase are functioning in a simple way. But by adding the structure of combining their learned information together, a higher functionality, a minimum path, results. Because of the simplicity of the rules and dynamics, this represents a model system for the study of self-organization in higher dimensions.
In the beginning of this paper are listed features of collective, self-organizing systems. The current simulations capture all of the attributes, and arguably most of the features. The simulations are distributed either in physical space or logical space, without centralized control of any form. They exhibit, and indeed require, diversity in experience and performance (see the next section). The current system does not have dynamics in the typical sense of having changes of state with respect to time; instead, the system disequilibrium is expressed by the sensitivity of the global state (the path through the maze) to small changes in the local state (nodal preferences). The combination of averaging the individual solutions is a mechanism for condensation of information. The connectivity in the system is limited and localized in the structure of the domain and in the interactions between entities (none). Because the ensemble sets involve subsets of the entire population and were shown to result in a minimum solution, the function of the whole is not dependent on the individual. The question whether the system scales without loss of function is presently unresolved, but the results are suggestive that this is true. The insensitivity to noise and some forms of loss suggest that the system is robust. The study on conflicting information suggests that the system is resilient and adaptable.
We conclude that the model system captures the breath and depth of the attributes and features of a collective, self-organizing system. This is remarkable, given the simplicity of the system.
Diversity: An Essential Attribute of Collective Self-Organizing Systems
The need for diversity in the collective solution is in itself shown to have multifarious components. There are two primary levels of diversity of information that can be defined in the present simulations: diversity of learning experience of individuals of the domain space (domain diversity) and diversity of preferences of an individual at one place in the domain space (nodal diversity). Both are measures of the extent of the sampling (learning), either in domain space or nodal space. Within each of these usages of diversity, the relative magnitudes (importance) of the sampling can be examined.
Within the context of the current system, the domain diversity is the breath of the sampling of alternative paths through the maze as a whole, but says nothing about the frequency of this sampling. Similarly the nodal diversity is the breath of the sampling of different paths at a node in the maze, but says nothing about the relative magnitudes of the preferences of the paths. Domain diversity is a global property of the system; nodal diversity is a local property. The present simulations give insight into how each of these affects the functioning of the collective solution.
Domain diversity is close to the general usage in biological evolution (Kauffman, 1993), and the mechanisms by which it contributes to self-organizing dynamics are understood and need not be discussed here. In the present simulations it is apparent, but not proved, that domain diversity leads to the collective advantage. One indication that the domain diversity is important is the lack of sensitivity of the collective to noise (false information). Because false information can lead to less explored regions, domain diversity provides the collective with contingencies that are not available to the individual or narrowly focused group.
The associated aspect of domain diversity, the relative importance of the different global paths, is captured in the present simulations, which examined the effect of limiting the contributions of learners or performers of different levels. We make this association, because, for example, a high performer in the Application Phase, who is also a slow learner, has extensive experience in less preferred parts of the maze (since performance in the Learning and Application Phases is uncorrelated) but will still choose one path through the maze over all others. These studies demonstrated that the collective performs better when individuals with a distribution of performance are included, rather than a subset. But the studies also show that the full inclusion of the population is not essential to the functioning of the collective. We can tentatively conclude that the domain diversity is essential, and the system is sensitive, but not disastrously so, to the magnitudes of the domain diversity.
Similarly, the simulations provide insight into the effects of nodal diversity and the importance of the relative magnitude of the nodal diversity. These results are unexpected and may not be generally appreciated. The studies on the replacement of nodal preferences with random noise (which alters the nodal diversity) and the studies on the elimination of minor preferences of an individual suggest that the collective solution is not significantly degraded if the nodal diversity is reduced. Only the stability of the solution and the convergence to final solution was effected by the change in nodal diversity. The effect of the relative importance of the magnitude of the nodal diversity was examined in detail and provided significant insight. Significant degradation was found if all non-zero nodal contributions are made equal. Taken together, the importance of nodal diversity is minimal, but the distribution within this diversity is essential.
Overall we can conclude that the present collective self-organizing system requires domain diversity, but not the magnitudes of the domain diversity. In contrast, the system requires information on the magnitudes of nodal diversity, but is not highly sensitive to nodal diversity itself. In either case, including the additional information improves the stability or performance of the collective solution. In the next section, we consider the implications of diversity on traditional problem solving, but for the present argument, it is sufficient to state that the proposed model problem enables the full spectrum of diversity to be studied.
Self-Organizing Versus Traditional Approaches to Problem Solving
The initial motivation for developing the simulations of collective decision making was to better understand the reason for some of the failure modes of traditional problem-solving approaches. Our experience is that the functionality of cooperative teams declines as they become larger, despite the fact that greater resources are available. The current simulations, despite their simplicity, give some insight into why large committees function poorly.
The main conclusion of the simulations is that any loss or modification of the information contributed by the individual to the collective decision either degraded the collective advantage or had no effect. In no case was there found to be an advantage in modifying the information contributed by the individual. Certainly one of the effects of traditional decision making in teams is the loss of participation by less aggressive individuals or by the loss of contributions contrary to the consensus at the moment. Also the dynamics of group consensus often alters the contribution of the individual either through miscommunication or by modification of the individual. Therefore we can make a general observation that part of the degradation of a large team is simply the loss of either the domain diversity or nodal diversity of the contributions of the individual to the whole.
The results also suggest that more specific problems may be the source. Three specific degradations of the collective advantage were observed: 1) when individuals were limited to only their dominant opinions or when they could only express their opinions uniformly (isotropically), 2) when a random individual dominated the contribution to the collective at different points in the sequential decision process, or 3) when slow learners or low performers are excluded from contributing. Arguably, each of these occurs to some degree in the traditional processes of decision making.
The intent of the present studies is not to provide any definitive recommendations about improving traditional problem solving. Instead, the intent to is provide an alternative viewpoint into the mechanisms operating in collective problem solving and to suggest a model system by which further research can be done.
Noise and Coherence in Collective Systems
A necessary attribute of a self-organizing system is the presence of noise or chaotic dynamics. The presence of "persistent disequilibrium" enables the system to be responsive to small changes in state by preventing a single steady-state solution from dominating all others (e.g., epilepsy is a dysfunction of the brain due a single dominant resonance in the brain waves). At the same time, the system must also limit the "disequilibrium" and be able to express properties of coherence. The challenge in these systems, then, is achieving a balance between the chaos and coherence. The current simulations contribute to large prior area of study for complex dynamical systems, but in the context of collective, self-organizing systems. We note that in the current simulations, the chaotic nature of the dynamics has been documented, but a complete study of the advantages of chaos must be deferred until non-steady state simulations are done. We assume in the present argument that these advantages can be demonstrated.
The current simulations express a chaotic nature in the selection of a minimum path when multiple minimum path lengths exist in a maze. The collective solution has an indeterminacy in selecting one path over another and a small change in a critical nodal preference value can drastically change the global path through the mesh. Because another minimum path is selected, the global performance is not degraded. Two studies were done which demonstrate that this chaotic behavior is bounded in the present system. The system was shown to have extreme stability in response to the introduction of noise (the study of noise added to the Nodal Preferences). Also the system was found to be stable to a relaxation of using only the maximum value of the Nodal Preferences (Fig. 5). Other studies for the full collective solution as in Fig. 7, which are not reported here, show that the collective solution is indifferent to this relaxation of the Application Rules. If a full relaxation occurs, as in the Probabilistic Selection approach, then the collective advantage is lost. The selection of the maximum Nodal Preference in the Application Rules appears to be the source of the ability of the collective to dampen the chaotic behavior, and this is discussed in the next section. We conclude that the current system exhibits the desirable feature of chaotic behavior, but not at the expense of sacrificing global coherence.
Evolution of Collective, Self-Organizing Systems
To better understand the choice of a maximum preference in the Application Rules, the Probabilistic approach was examined. The results based on the two methods showed that for an individual there was little difference between the two, but for the collective only the maximum selection resulted in a collective advantage. Because of these differences, this led to the general question of how collective systems might require different Rules, in comparison to self-organizing systems which do not involve sequential processes.
To the author’s knowledge, most physical systems use a Probabilistic sampling in either the governing equations or characterization of their dynamics, whether the system is continuous or discrete. Even deterministic systems, such as planetary motion, are being treated as probabilistic systems to account for their chaotic nature (Prigogine, 1998). The example given in the Introduction of a molecular gas is an example of a discrete self-organizing system. Turbulence in a macroscopic fluid is an example of a continuum system (here the emergent properties are the global structures and stochastics of the turbulence). In both of these systems, the ensemble average of many realizations is over a broad distribution, resulting from a probabilistic sampling of the possible space. Exceptions to the use of probabilistic sampling in physical systems are human creations, such as a transistor. To give an idea of how different physical problems might be with maximum sampling, a direct analogy to the present simulations is the flow of water through a "maze" of pipes. If the flow system could select a maximum state instead of a Probabilistic sample, water would only flow down the largest pipe and not down all pipes. Biological systems with sequential processes are in direct contrast to these physical systems in which the selection of a maximum state characterizes the selection process. The premiere examples are the working of the neurons in the brain or the selection of competing pheromone trails by an ant. Realizations within an ensemble average represent a narrow global state, similar to the present simulations of the model problem.
We speculate that the ability to select a maximum state in collective biological systems has evolved as a necessary capability to enable the functioning of a collective self-organizing system, which in turn has the desirable feature of being able to solve problems of greater complexity.
Another motivation for the present studies was to support the development of the Internet described in the Introduction. The simulations demonstrate that under ideal circumstances larger numbers of individuals can contribute to a collective decision and more complex problems can be solved.
The challenge of the implementation of these ideas is to develop methodologies on the Net that minimally do not inhibit the self-organizing process and, at best, activate the process. The results of the simulations suggest that the more diversity that can be captured, both in breath (domain) and depth (nodal), the more optimally the system will perform and will be stable. In addition, the simulations predict that it is essential to prioritize the "depth" of the contributions of an agent (either individual or knowledge system), or at least capture their most significant contributions, at the expense of losing the less important ones. If all of the individual contributions are equally weighted, the collective self-organization will converge to a less optimal solution or not at all.
The question of how much and what information to capture of an individual is of critical importance. Unlike in the present simulations where the state information is the location of the individual and the single set of Nodal Preferences, a system capturing human existence in even a limited knowledge space is relatively unbounded and significant reduction is necessary to capture even part of an individual’s interests. This is one of the greatest challenges, and the simulations suggest that depth of a representation of an individual can be sacrificed without disabling the functionality of the whole.
There are many outstanding questions to the viability of using self-organization for problem identification or solving. Often in sequential problem solving, there is a challenge of having the right information at the right time - a synchronicity problem. If the right information is not present when it is needed, a linear solution method will fail. To some degree, the redundancy of self-organizing systems lessens this problem. And possibly the use of agents for people will also enable their contributions to be present even when they themselves are not. The dynamic version of the current simulations is expected to address these questions.
Another critical concern is how can we tolerate the inherent randomness of the system. For example, in the current simulations it was necessary to take averages of many realizations in order to make meaningful comparisons. In real life this multiple "running" the system may not be an option. Can we tolerate the randomness of the solution when a failure of the system may have severe consequences? As in the simulation of the random leader (Fig. 14), would it not be better to have a "poor" leader, but one that is more predictable? Again, the partial answer to this question is the redundancy of the system, such that many realizations are being tested at one time and the ensemble average is not random but a stable, well-defined solution.
The ultimate answer to many of the concerns about the inappropriateness of a self-organizing approach to social or organizational issues is that self-organizing systems occur because often there are no alternatives. Self-organizing systems occur in nature when the global system is too complex or the centralized problem solver is lacking in capability. Because our world is quickly becoming more complex, often changing faster than we can evaluate the changes, the process of collective self-organization may be the only option.
ConclusionsIn the present work the solution of sequential problems by collective, self-organizing systems is studied within the context of a simple model system - a collective solution using non-interacting agents which solve a maze by two simple, sequential sets of rules. Despite the simplicity of the system, the richness of the dynamics and global properties are sufficient to address many questions to a variety of researchers. The results support the original premise that much of society's complex behavior can be explained by the collective interaction of simple processes. The proposed model problem provides a contained system by which researchers can study collective social dynamics, without sacrificing relevance to real world applications.
Highlights of the conclusions illustrate the breath of issues that can be studied. For the study of complex systems of sequential processes: the system dynamics and properties exhibits a rich list of attributes associated with self-organizing systems, including performance of the whole greater than the individual. For the study of population diversity: the simulations demonstrate the importance of diversity of experience and performance in the functioning of the collective; without exception, the more information provided by the individual to the collective, the better the collective performed. For the study of group decision making: the modifications of the contributions of the individual that were most disruptive to the collective were when the individual was indecisive or when a random leader dominated the collective solution or when the learning by the individual is derived from a random, suboptimal process.
The primary differences between the present work and prior explorations in complex adaptive systems are best seen by comparing the approach to information condensation. The Genetic Algorithms (GA) studies (Koza, 1994; Mitchell, 1996) select among different initial domain states and evolve emergent information. The present system combines to create emergent information from a diversity of individual states. The essential difference is how information condensation constructs higher structures. As is demonstrated in the current simulations, any selection or modification reduces the functionality of the whole. When this difference is applied to real systems, the implications are profound. The ideas presented in the current study are consistent with the growing thesis within evolutionary theories that competition or selection is not the dominant mechanism in nature (Gould, 1979). Instead, the mechanisms are primarily cooperation and symbiosis (Margulis & Fester, 1991). For completeness we note that the GA studies are traditionally one dimensional but time dependent; the current studies are multidimensional but steady. The present work solves sequential decision problems, and GA solves for global properties from complex initial states. In the context of methodology, the closest prior research is the simulations of agents, particularly ones motivated by ant colonies. The primary difference is less one of domain or methods for processing information, but more one of the goals of the research. The agent simulations often focus on solving a particular problem optimally, such as the Traveling Salesman problem (Dorrigo & Gambardella, 1997), where the current simulations are focused on developing a simple model system as relevant to the general problem of sequential decision making.
The idea that human processes are driven by inherently random dynamics, much like biological evolution, is coming into general appreciation (Allen, 1994). But the application of these observations to our interpretation of history or to the development of future policies has been limited by understanding of the basic processes and their consequences. Because of the simplicity of the present study, we can begin to be specific about the chaotic nature of collective, self-organizing systems and how these system have possibly evolved mechanisms that enable the collective to function in the presence of noise and at a higher functionality than the individual. An increased understanding of these chaotic but self-organizing processes will enable us to replace what has been an act of faith in the potential of these systems to solve problems with a deep understanding of the advantages and risks. With this greater understanding, we will be able to develop capabilities and policies that will enhance functioning of the system to the benefit of all.
There is a breadth of future research that is possible from the foundation presented here. The simple, static model is a proper starting point of a substantive theory of these systems. The addition of time-dependent simulations is a necessary next step to address some of the unresolved questions in the current study, such as the role of chaos in robustness and resilience of the system. By including the interaction of the individuals during any part of the simulations, cooperative learning and problem solving, and the associated concepts of competition, can be studied. By providing a feedback of the collective to the individual, issues of satisfying the needs of an individual relative to the collective can be examined. By adding to the individual's state information, such as group identification, a hierarchical structure can be created to examine self-organization at a variety of levels. We note also that although the current domain is discrete, the approach is fully applicable to continuous domains.
AcknowledgmentsThe author wishes to thank the members of the Symbiotic Intelligence Project, particularly Steen Rasmussen, Luis Rocha, Cliff Joslyn, Marianna Kantor and Steve Smith, for their insightful comments and also Chrissa Constantine for her editorial assistance. This work was supported by funding from the Department of Energy.
ReferencesAdams, R. N. (1988). The Eighth Day: Social Evolution as the Self-Organization of Energy. Austin, TX: Univ. of Texas Press, Austin.
Allen, P. M. (1994). Evolutionary Complex Systems: The Self-Organization of Communities. In F. Fang & M. Sanglier (Eds.), Complexity and Self Organization in Social and Economic Systems, Beijing, China: Springer.
Axelrod, R. (1994). The Evolution of Cooperation: Basic Books.
Crutchfield, J. P. (1994). The Calculi of Emergence: Computation, Dynamics and Induction. Paper presented at the Complex Systems&emdash;from Complex Dynamics to Artificial Reality, Numazu, Japan.
Dorrigo, M., & Gambardella, L. M. (1997). Ant Colonies for the Traveling Salesman Problem. Accepted for publication in BioSystems, 1997.
Gould, S. J. (1979). The Spandrels of San Marco and the Panglossian Paradigm: a Critique of the Adaptationist Programme. Proceedings of the Royal Society of London, B 105.
Johnson, N., Rasmussen, S., Joslyn, C., Rocha, L., Smith, S., & Kantor, M. (1998). Symbiotic Intelligence: Self-organizing knowledge on distributed networks driven by human interactions. In C. Adami, R. K. Belew, H. Kitano, & C. E. Taylor (Eds.), Artificial Life 6,: MIT Press.
Kantor, M., & Johnson, N. L. (1997). Research Directions for the Next Generation Internet: Emergent Knowledge on the Internet (LA-UR-97-1200). Paper presented at the Workshop on Research Directions for the Next Generation Internet (May 13-14, 1997), Vienna, Virginia.
Kauffman, S. (1993). The Origins of Order: Self Organization and Selection in Evolution: Oxford University Press.
Margulis, L., & Fester, R. (Eds.). (1991). Symbiosis as a Source of Evolutionary Innovation: Speciation and Morphogenesis: MIT Press.
Prigogine, I. (1998). The End of Certainty: Time, Chaos, and the New Laws of Nature. N.Y.: The Free Press.
Slater, P., & Bennis, W. (1964). Democracy is Inevitable. Harvard Business Review (March-April (reissued September&emdash;October 1990)).
Wu, T. (1979). Kinetic Equations of Gases and Plasmas. Reading, MA: Addison-Wesley.
Publications | Talks | Interests:
Past & Present | Symbiotic Intelligence
Project
Contact | Science of Diversity | Home | Links | Diversity Documents | Norman Johnson New Topics: Infectious Idea Spread using Epidemiological Modeling | Collective Intelligence in the presence of bias and misinformation Community, Coexistence and Pre-conflict Minimization Projects | The CISS (Coexistence in Suggestive Simulations) Project ©2013 Norman L. Johnson |
