chaos Comes To New Mexico
By Matt Pike
Since the evolution of man into a social and political creature, much of our time as humans is spent interacting with other individuals. In order to try to increase our effectiveness in our dealings with others, we often attempt to formulate means of predicting what others will do. Much of academic thought, and study in the behavioral sciences, is dedicated towards developing an understanding of humans and how they make decisions. Brian Arthur addresses some of these issues in their application to economics. He points out that traditional models of rational reasoning and prediction are insufficient because these methods only scratch the surface of what is actually occurring within the complex system of complex human minds interacting with other equally complex minds. The ability to apply deductive reasoning and logic depends on a simplification of the interacting factors into logical symbols of language that then facilitate the application of learned formulas. It also demands complete information about what is occurring within the system. In the real world, however, humans seldom have complete information, and thus cannot utilize deductive reasoning to infer what is occurring, so instead rely upon inductive reasoning. Humanity has developed an amazing ability to recognize patterns, and use this recognition to predict what is going to happen next. Brian Arthur gives the example of a chess player who studies his opponent to try and ascertain what type of player he is, looking for indications in previous moves and trying to infer patterns of thought which will grant him the advantage of being able to predict his opponent.
Economics is similar to this, since much of its field of study is learning to predict how markets will respond to stimuli, and each market is made up of many independent actors making their own decisions. For this reason, it is important for economists to try to accurately predict how individuals make their decisions and how they employ inductive reasoning. The individuals within a market find themselves trying to base their decisions on what they think others will do, while the others are trying to do the same thing. Thins results in a tremendously complex system where every factor affects every other factor. Arthur constructed the El Farol problem as a means to simulate what occurs within a situation where there are many actors acting over a period of time, each trying to base their decision on what they believe the others will do.
His simulation is named after a bar in Santa Fe, New Mexico. He proposes a model where there is a town population of one-hundred people, who are all interested in going to the bar on any given night. The townspeople will only have a good time, however, if fewer than sixty people are there. This necessitates that the townspeople each try to predict what the other actors will do, but all the information available to them is the attendance record from the previous evenings. So, each townsperson attempts to analyze what has happened in the past in order to allow them to predict what the other decision-makers will do. The methods that the agents employ in making their decisions have an affect on each subsequent time interval, and thus on each agents future predictions.
For the sake of addressing this problem, Polyas Method offers a procedure that can be used. In step one, it is imperative to understand what the problem entails. This situation is indicative of what occurs in any number of real world situations, and thus the specific location, the fact that this occurs within a bar, and for that matter, the exact numbers involved can be disregarded in terms of the simulations applicability. To isolate, and thus construct, one specific simulation, however, the number of townspeople and the timeframes are kept as proposed in the problem. The aim of the computer program is to simulate 100 actors interacting with each other over a period of 100 evenings, where 60% attendance constitutes the bar being too crowded. There must be a variety of decision-making structures, because the problem is setup such that if all actors utilize one method of prediction, the result will be exactly the opposite. For example, if all actors believe no one is going to the bar, then everyone will attend, and no one will have a good time. So numerous prediction functions are essential for simulating real life interaction.
In developing a strategy for addressing this problem, it becomes obvious that there are many different ways to go about this. Many of the particulars within this problem can be changed, or addressed differently, and given the level of complex interaction within the problem, it seems likely that any change will affect the entire system. Owing to this complexity, it is important to isolate what elements of the system are to be studied. For example, Bruce Edmonds (See Bibliography) focused on the learning and communication between agents. His model reduced the population to 10, but incorporated genetic programming algorithms to attempt to simulate real life learning of the actors. He also included parameters to permit for the weekly communication between the agents indicating whether they were planning on attending. His examination focused on a smaller scale, concerned with fewer individuals, but more interaction between them. This paper, however, is more concerned with the dynamics of the larger system, and thus will employ a random selection of predictive rules to be used by the agent from a fixed set of possible predictors, to simulate how the agent arrives at a decision.
The program will need to include a record of how many people attended each night, both for the purposes of output data and results of the experiment, and also for use as data for the application of the prediction rules by the agents. Given that all of the simulation is occurring within a time frame, an overarching time structure should be present in the programming code, within which each actor makes her decision. A variable needs to be set up to keep track of how many people have decided to attend for any given night. There also needs to be some structure to facilitate the selection of which rule the person is going to employ for any given selection instance. This rule must be selected and processed for each agent, with the results of all the agents being summed for each time interval, and then stored to the overall time record. Finally, the program must output the results to a graphical display for analysis. Once these basics have been accomplished, elements can be changed and added for purposes of comparison.
Because of its ease of graphics output construction, this program was written in Visual Basic 6.0. The code assigns an array to act as the time record entitled sim , which stores each nights attendance for later access. The simulation runs for 100 values of the array, and each value cycles through 100 actors, called Person , to determine whether each one goes or not. The program generates a random number that decides which rule the person will employ. The rule then accesses the data contained in the array and returns a prediction of how many people the person thinks will be attending the bar that night. If the prediction is less then 61, the person decides to attend, and the variable Attend is incremented. After all 100 actors have decided whether to go for a night, the total number attending is then stored to the array. The program then graphs the results and (hopefully) prints them for review.
In programming this, it became obvious that there were many different ways to structure the program, but this seemed the most reliable, (as it was the first method that did not crash the computer!) Another method would have been create a general super-class of actor, complete with all data methods, functions, and members, which would then be employed in particular inheritance subsets to generate each actors decision. This application is much better suited to C++ and so was eliminated from the program.
After the initial encoding took place, much time was required for troubleshooting, debugging, and redesigning before the program would actually work. To try to isolate problems, I began by simplifying the code to try and get the most basic skeleton program functional. It seemed logical that adding code into an already working module would aid in the identification of problems. At some point, almost accidentally, the program compiled and ran. This initial running had the different prediction rules completely eliminated, having been replaced with a simple yes or no decision corresponding to each case. This first graph bounced all over the place with very little discernable trend. It appeared that it was not varied enough however, with most values being close to the middle of the range. Given that the problem rests upon the agents using various means to predict the attendance for the evening, I added the prediction rules back into the code, thinking this would serve to extend the range of the graph.
Instead, the prediction rules as I had them at written at that point seemed to somehow institute a pattern within the simulation, and the resulting graph fluctuated from extremely high attendance to extremely low in almost exact alternation, (See figure 1.1). This predictability rules involved mainly analyzing what happened the previous evening in the simulation. In hindsight, this makes sense because having such a limited range of prediction rules means that the actors will coalesce into one group oscillating between attendances and staying home.
In an effort to escape this patterned response, the rules were changed to incorporate averaging of different nights within the last 4 evenings as a rule for prediction. The graph was still patterned overall, but had occasional double-spikes at random intervals. (See figure 1.2) It would seem that the review of different periods of time affects the cycle by which the graph oscillates, perhaps a four-day prediction rule oscillates on eight-day cycles. At this point in time, I also noticed that even with a highly patterned graph, every time the simulation was run, the spikes and falls of the graph would be in different places. As a means to verify this (Polyas Step 4), the program was reconfigured not to clear a graph before adding another, which resulted in a roughly rectangular block entirely filled in after enough trials were run. (See figure 1.3)
I started searching for ways to remove any trace of a predictable rhythm and it was truly amazing to see how attempts to enact a certain change in the graph, such as narrow the scale, would have entirely different effects. Even though the simulation results werent showing as absolute chaos as Id expected, attempts to change those results resulted in chaotic changes owing to the complexity of the overall system. It was impossible to predict what effect changing the prediction rules would have. So I began to play with many variations of the rules trying to generate a system with less order, which more closely resembled a real life situation.
Changing the rules to include progressively more variation in which array values were used for the prediction resulted in more variety in the graph. The patterns of oscillation grew more intermittent replaced by more separating variance. The extreme bottom values of the graph started shifting throughout the graph so that a bottom attendance value fluctuated. The peak values, however, remained constant at 100, indicating that somehow the system was set up such that if many people were going to go, all of the actors came to same decision and all went. Again, trying to address this met with many unpredictable changes.
In comparing my results with those put forth by Arthur, it becomes apparent that my simulation has much more variance, since his graph operated mainly within the 40-75 region, with each nights attendance hovering close to 60. My simulation however, varies tremendously from approximately 15 all the way up to 100. Given the constraints of the problem itself, it would seem unlikely that any nights attendance would reach 100, but this probably has to do with the lack of incorporated learning of the actors. This lack could additionally explain the increased variance, since logically, the purpose behind an actors ability to learn is to increase the accuracy of their predictions. This simulation appears to be employing somewhat inefficient prediction techniques. One question is whether the chaotic graph does indeed still fluctuate around the key 60 mark. To analyze this, a line at 60 was added to the output. (See figure 1.4) The results are indeed centered around 60, they are simply more extreme in their deviation from it.
With further adaptations to the program, it appears that the more conditions and possible cases that are added the greater the chaos factor of the resulting graph. It became apparent that most of the conditions I had set where comprised of even numbers. The array values the rules examined consisted of pairs such as ((currentValue 2) +(currentValue 4)) /2. this was not intentional, but perhaps a subconscious tendency within me. Upon seeing this however, I change the rules to include even and odd numbered review factors, and there was a notable increase in the irregularity of the resulting graphs as a result. It would seem that the use of even numbers was responsible for the alternating pattern on a fixed cycle. I would speculate that the same type of thing is still occurring here as well, but the cycle has become much more complex. Somehow, this change also toned down the variance a little, confining many of values closer to 60 than in past trials. I selected figure (1.5) as an example because it appears as though it is going to converge at 60 half way through, then spikes back out into randomness again. I found this interesting and wonder if the (attempted) convergence is indicative of the system, or is simply a random coalescing of chaos into something that appears ordered to our observations.
The observable trend here is that as the program becomes more complex and more involved, a more chaotic graph results. This simulation just begins to scratch the surface of the possibility for this problem. A tremendous amount of further adaptations and research is warranted. First of all, it should be noted that the computer system used in the simulation is incapable of generating truly random numbers. They may be statistically random, but in fact are still generated by an ordered process. To address this, perhaps the use of a sampled value from an audio waveform recorded from a live radio broadcast, where the broadcaster is unaware that this occurring, could be used as a random input. Or with a research grant of $500 million, a prototype quantum computer could be used to generate a truly and atomically chaotic seed.
The program itself has massive potential for refinement, and could be made to more closely resemble the real life situation. For example, if a multidimensional array were created where each actor stored their own individual data, additional aspects could be considered. If an actor has not attended in several days, they are more likely to want to attend, even if their prediction is that it will be slightly more crowded than is ideal. Additionally, if an actor has been going to the bar for twenty days straight, they may need a break, where no matter how un-crowded they predict the bar will be, they will not attend.
A distinction should also be drawn in the data for total number of males and females attending. If a women reviews the data and finds a good ratio of men to women has occurred in the past, this may affect her desire to go. If this distinction is drawn, something should also be included to consider the possibility that part of the population is homosexual, and therefore the ratios are reversed. A clause could be included in the program that if the bar is over 90% full, a fight breaks out and the following week, 10 people are to upset by the violence to have any interest in attending.
Obviously, there could be many factors at work for any one individual to decide whether to attend or not, so a system should be devised where each actor uses several different means to decide whether to go each night, and then a comparative weighting of each factor results in an average or total desire to go. In real life, humans combine inductive and deductive reasoning, trying to predict various aspects they believe will occur, but then weighing the advantages and disadvantages of each.
A genetic programming algorithm that facilitates learning by the actors should also be included, since a static actor can hardly be said to represent reality. Edmonds incorporation of communication is also a good idea, but I fail to see why such methods cannot be applied to a larger system with more factors as well. One of the most fascinating things about the El Farol problem is that it can take many different forms and can be interpreted in many different ways. For a problem that simulates chaos, it makes sense for chaos to exist in its interpretation. What people are going to see as most important in the problem is the result of a complex interplay of the numerous differing aspects of their personality.
An important factor in determining the extent to which a system is chaotic is too observe it from many different distances . At the level this simulation examines the results, it appears unpredictable. If one scales the graph down to a small enough level, it appears as a straight line, centered over 60. Additionally, the program fails to permit examining the graph at a more microscopic level, but if this were possible, presumably the minds of each individual actor would be equally complex and chaotic. This is similar to what is encountered in a fractal pattern where things have the same characteristics on both a small and a large scale. Additionally, how precisely the variation is measured will have an impact on the observations that result. For example, if someone starts measuring the perimeter of a small, natural island with a six foot stick, they will get a very different result than if they measure it on a millimeter scale. In seems that some element of the meaning of problems involving chaos and complexity must exist in the degree of their chaotic variance. One of the most interesting part of this simulation for me was in comparing two different trials of the same program. The contrast that occurs in two examples that occur under the exact same external conditions is truly remarkable, but perhaps if that contrast could be isolated into a mathematical equation of its own, additional meaning could be gained.
In broader analysis of chaos and complexity in the universe, there are theories that propose that things operate in exactly the same chaotic manner on the atomic level as they do at the level of the universe. If one considers things like Multiple World Theory, as put forth by quantum mechanics, perhaps what we experience is simply a shifting from one running of the simulation to the next. Perhaps our universe is simply one running of a massive El Farol problem, and other universes exist that are identical, except with a different seed, or differing level of complexity. If the variance that occurs in the chaotic systems we experience could be isolated, perhaps this knowledge could be inferred to broader things outside the realm of our known universe, such as time travel, dimensional shifting, and the existence of a God.
Bibliography
Arthur, Brian. 1994. Inductive Reasoning and Bounded Rationality . American Economic Association Papers, 84, 406-411
Paper which first proposed the problem and why it is needed. Contains basic description of the setting and structure of the problem, as well as thoughts on the nature of human reasoning and computer simulations.
Edwards, Bruce. Gossip, Sexual Recombination and the El Farol Bar: Modelling the Emergence of Heterogeneity . Centre for Policy Modelling. Manchester Metropolitan University.
Provides expansion on the problem and variations in which it may be adapted to allow more accurate simulation. Provides analysis of the resulting complex-chaotic system as well as in-depth programming requirements and structures. Includes discussion of the theory of a genetic programming algorithm, and ideas about its implentation.
Liberty, Jesse. 1999. Sams Teach Yourself C++. Macmillan Computer Publishing.
Reference for C++ containing syntax and programming information, as well as object-oriented problem solving and simulation constuction ideas. Discussion of utilizion of C++ computer programs to emulate real life situations.
http://www.cs.caltech.edu/~yale/ec126/elFarol/
Website containing discussion and setup of the problem, as well as a java applet which allows the running of one possible adaptation.
http://ideas.uqam.ca/ideas/data/Papers/scescecf9812.html
This paper reviews the El Farol problem and surveys previous solutions, which typically involve complex learning algorithms. A simple adaptive strategy is proposed, and the strategy is investigated by simulation. The algorithm is analyzed in a few simple cases.
Online C++ programming resource with links, tutorials, and help message board.
Aitken, Peter. 1998. Visual Basic 6 Programming Blue Book. Coriolis Technology Press.
Programming reference book. Very heavy to carry everywhere for a month.
Best programming resource on the net! Every language, and a question forum.
APPENDIX
Final Modified Visual Basic Source Code
**********************************
Dim i As Integer
Dim Attend As Integer
Dim Person As Integer
Dim Predict As Integer
Private Sub Command1_Click()
Dim sim(1 To 100) As Integer
'dimensions an array which will represent time, and hold
'each nights attendance
For i = 1 To 100
'loops for each array value
Attend = 0
For Person = 1 To 100
'sets loop for each actors decision-making
Predict = 0
Dim decide As Single
Randomize
decide = Rnd
'various prediction rules selected randomly
Select Case decide
Case Is < 0.1
If i > 10 Then
Predict = (sim(i - 2) + sim(i - 7) + sim(i - 10)) / 3
Else
Predict = sim(i - 1)
End If
Case 0.1 To 0.3
If i > 20 Then
Predict = (sim(i - 7) + sim(i - 8) + sim(i - 17) + _
sim(i - 20)) / 4
Else
Predict = (sim(i - 1) + sim(i - 2)) / 2
End If
Case 0.3 To 0.5
If i > 4 Then
Predict = (sim(i - 3) + sim(i - 4)) / 2
End If
Case 0.5 To 0.8
If i > 6 Then
Predict = (sim(i - 3) + sim(i - 5) + sim(i - 6)) / 3
Else: Predict = 100
End If
Case 0.8 To 0.9
Predict = sim(i)
Case Is > 0.9
Attend = Attend
End Select
If Predict < 61 Then
Attend = Attend + 1
End If
'tests prediction against desired result
'if favorable, actor decides to attend
Next Person
sim(i) = Attend
'stores each night's attendance to the array
Next i
Call DrawAxis
'Graphing procedure
For i = 3 To 99
Picture1.Line (i, sim(i))-(i + 1, sim(i + 1))
Next i
End Sub
Public Sub DrawAxis()
Picture1.Cls
Picture1.Scale (-5, 105)-(105, -5)
Picture1.Line (0, 100)-(0, 0)
Picture1.Line (0, 0)-(100, 0)
Picture1.Line (0, 60)-(100, 60)
End Sub
Private Sub Cmdprint_Click()
Form1.PrintForm
End Sub
© Copyright Matthew Pike, 2000-2005