Prisoner's Dilemma at the swimming pool

At my vacation I was witness of "beach chair reserving behavior". As soon as the pool opens, some guests reserve their beach chairs by putting towels on a couple of beach chairs. Then they go for breakfast or whatever. So, some time later, there are several empty but reserved beach chairs around the pool. Wanting no trouble, people have to sit on the ground. Doing some quick count during the day, I noticed that there were 20 beach chairs and - surprise! - in average only 20 people at the pool. So the system would work pretty well if nobody reserved the chairs and thus getting a good chance to find an empty chair when needed. For all the participants this would be a relief: the beach chair blockers don't have to get up so early in the morning and the others suffer less of beach chair shortage.

This can be modelled as a game theoretic problem, namely the multiplayer Prisoner's Dilemma. The Prisoners Dilemma is named after a fictional story where two suspects are interrogated regarding a major crime. The police have insufficient evidence for a conviction, so they offer the prisoners separately a deal: if one confesses (defects), he goes free (temptation payoff) and the other one gets a high conviction (sucker payoff). However, if both confess, both get punished (punishment payoff). If no one confesses, both get a less severe verdict, in overall the best for everyone (reward payoff).

The following table shows the possible strategies and payoffs (exemplified with the payoffs 0,1,2,3, the higher the better):

	Prisoner B stays silent (cooperate)	Prisoner B tells (defect)
Prisoner A stays silent (cooperate)	(2,2) both get off with small sentence	(0,3) Player A gets punished for everything, Player B goes free
Prisoner A tells (defect)	(3,0) Player A goes free, Player B gets punished for everything	(1,1) both get punished

At the pool, we have the case of a multiplayer Prisoner's Dilemma with the options to reserve a beach chair in the morning or to refrain from this behavior.

	Most others do not reserve chairs (cooperate)	Most others do reserve chairs (defect)
Player does not reserve chair (cooperate)	(2,2) all get a fair chance for a beach chair when needed	(0,3) player must sit on the ground, some others enjoy their reserved chairs
Player does reserve chair (defect)	(3,0) player has guaranteed beach chair, others are suffering slightly	(1,1) only chance to get a chair is reserving in the morning, worse situation than in upper left case

Unfortunately, with a sufficient number of defecting players (people who reserve a beach chair early in the morning) there is no merit in not reserving - you will go without a pool chair then (sucker payoff). So the only feasible strategy is to struggle for any free one in the morning and probably get one chair reserved for your family of 4 people. Another problem is that the people are constantly changing. So even if a cooperative behavior could be agreed on, there might be the arrival of a new bunch of defectors the next day, who would then feel themselves lucky to get all the chairs they desire so easily. There is certainly a tempation to reserve if nobody reserves, because then you have your beach chair guaranteed (otherwise there is still the chance that you get none, if already more than 20 people are at the pool). So, defecting is a stable strategy, although it is in overall worse for the whole group - this a tragedy of the commons.

Self-organizing music

Bacterial Orchestra by Olle Corméer and Martin Lübcke is a self-organizing evolutionary music installation. Several hardware units (cells) listen to their surroundings and pick up sounds, eventually integrating them into their own 'genom'. By analyzing the rythm, each cell decides which tunes to keep and which (possibly mis-sounding) tunes to drop. Thus, over time a strange but interesting music evolves.
As a follow-up to the Bacterial Orchestra, the group has now brought their approach to smartphones where each cell lives on a mobile phone.
That way different people can gather with their mobiles and together create a musical organism. It will evolve in the same way as Bacterial Orchestra, but the social component will give it additional extra dynamics.

• About Bacterial Orchestra at the authors web page
• About Public Epidmic No 1 at the authors web page.
• Video on test of Public Epidmic No 1
• Download their App for Apple iPhone

Evolving a self-organizing soccer team

This video shows the evolution of coordinated behavior of simulated robot soccer players. In the simulation, each soccer player is controlled by a neural network. The neural networks are evolved using an evolutionary algorithm, so generation after generation the strategy improves.
After a few hundred generations, the players of a team adopt a useful behavior. The used approach did not include a trainer telling them how to play or specifying predefined roles for the players such as being a defender, midfielder or striker. Still, during a game, different behavior of the players emerges. Thus, similar to biological systems, the entities take up different roles in a self-organizing way. Since the agents are not predefined, such systems have a high robustness against failure of come of the entities.

• I. Fehérvári and W. Elmenreich. Evolving neural network controllers for a team of self-organizing robots. Journal of Robotics, 2010.
• The DEMESOS project www.demesos.tk
• Software used for the evolutionary algorithm: FREVO www.frevotool.tk

Sometimes, self-organizing systems fail

New World army ants are known for their self-organized swarm raids accross the forest searching for food. They form a dense carpet of ants being able to attack much larger animals like larger insects and even lizards. In order to form the swarm, the ants orient themselves by tactual stimulation and by chemical trails laid by other ants. While this system is very effective, it has a potential mode of failure. Sometimes, these ants can get trapped in a circular movement, where the tactual stimulation and the chemical trails will lead to a positive feedback towards moving in a circle. Such behavior has been observed several times in natural environment, it is also relatively easy to reproduce the behavior under lab conditions. In a paper from 1944, T.C. Schneirla elaborates the initial conditions for circling army ants. Under heavy rainfall, these ants tend to move together in a small area. After the rainfall, ants at the margin of the huddle will tend to move around first. They will mostly follow the peripheral of the group due to tactual stimulation and thus create a circular trail of chemicals, which will be followed by the other ants. Army ants have been observed to be circling until they die of dehydration. This example shows that even systems which are evolved and hardened by billions of years of evolution (for organisms in general, ants came into existence about 130 million years ago when they split from the wasps) can be trapped in unwanted behavior.

• Circling ants oberved in Brasilian jungle
• Short video on army ants
• BBC Documentation on army ants
• T.C. Schneirla (1944). A unique case of circular milling in ants. American Museum Novitates, (1253), 1-26.
• Ant Death Spiral @ theantroom.blogspot.com 

The DEMESOS project

DEMESOS stands for Design Methods for Self-Organizing Systems and is a research project funded by Lakeside Labs. The goal of the DEMESOS research project is to elaborate basic concepts for a straightforward generic design process for creating self-organizing solutions, consisting of the stages modeling, simulation and iteration, validation, re-iteration or deployment. A way to achieve this is to evolve control systems as distributed cyberbrains controlling the agents of a complex system.

• The DEMESOS project
• FREVO frevo.sourceforge.net
• Wilfried's Webpage (further papers & research)
• Lakeside Labs (Klagenfurt, Austria)

The dark side of self organization

When reading books or articles on self-organization, they usually emphasize its amazing effects. Animals develop beautiful skin patterns, social insects achieve wonderful tasks with their hive mind and cities organize themselves despite of lack of central management. Much more sparsely, the more dangerous, negatives examples can be found. To give just a few: The principle of pulse coupled oscillators causes perodic cycle oscillators to globally synchronize even if the oscillators are only localla coupled. An example for this is the handclapping of an audience, but to some extend, also the synchronized regular military step of marching armies. On structures that itself can exhibit an oscillation behavior this can lead to the resonance disaster. In 1850, 485 french soldiers walked over a suspenion bridge in military step which led to resonance oscillations and finally made the brigde collapse; 226 soldiers died. Similar events happened in 1831 to Broughton's suspenion bridge and to Millennium Bridge in London (which did not crash, but moved heavily because of just 160 people). For this reason, the German Straßenverkehrsordnung contains a special paragraph prohibiting military step on brigdes.
Another example for unwanted self organization is the emergence of traffic jams from small disturbations in dense traffic flow. Assuming one driver has to break a little bit, this would cause the following car to come too close, the respective driver has to brake even harder to compensate. This means an even stronger decceleration for the next car and so on. On a global scale, a wave of stopped or slowed down cars can be observed running in the opposite direction of the traffic. Regulating the cars down to a lower speed limit can avoid the emergence of this problem and therefore increase traffic troughput depite to a reduced speed limit.
Finally, many of us experience another annoyance of an application of self-organizing complex systems. Social networks like facebook apply knowledge from network theory and data mining to extract information out of local social interactions. A user might not wanted to have disclosed this infromation in many cases. The problem is here that the robustness of self-organizing systems does not allow to fool the system. Even if you keep information like your job or your place of residence for yourself (or state it incorrectly), this information can be retrieved indirectly via an analysis of the information given by your contacts - Facebook knows you. So in this case there is only one solution - quit facebook! Even this step is difficult, Facebook normally offers only a soft deactivation of the account while keeping all your data. The function for deleting your account is well hidden: you might want to go to use the official form for deleting your facebook account. You are welcome.

Calculating one-dimensional binary cellular automata using a Commodore 64

Were the homecomputers of the mid 80ies good for doing any practical work? For example, would they have been useful in doing research on complex systems? I think, the answer is yes! As a proof of concept, I have quickly implemented a short program in Commodore Basic V2.0 that lets you explore the behavior of binary cellulary automata specified by Wolfram's code. Wolfram's work dates also back to the 1980ies, but has recently gained much attention due to his book A new kind of science.

100 DIM K(8)
110 INPUT"ENTER RULE NUMBER";R
120 N=1
130 FOR I=1 TO 8
140 IF R AND N THEN K(I)=1
150 N=N*2
160 NEXT
170 INPUT"USE RANDOM LINE AS SEED";A$:RN=0:IF A$="Y" THEN RN=1
300 PRINT CHR$(147)
310 IF RN=0 THEN POKE 1043,160:GOTO 340
320 FOR I=1024 TO 2023:IF RND(0)<0.5 THEN POKE I,160
330 NEXT
340 FOR L=1024 TO 1944 STEP 40
350 A=0:IF PEEK(L+39)=160 THEN A=4
360 B=0:IF PEEK(L)=160 THEN B=2
370 FOR P=0 TO 39
380 C=0:IF PEEK(L+1+P)=160 THEN C=1
385 IF P=39 THEN C=0:IF PEEK(L)=160 THEN C=1
390 IF K(A+B+C+1) THEN POKE L+P+40,160
400 A=B*2:B=C*2
410 NEXT
420 NEXT

The program displays the results of a simulation block code on the 1000 character 64 screen. Below is the result of simulating rule 30.