Ig Nobel Prize goes to research on self-organizing slime mold

The behavior of slime mold, a fungus-like organism, has been one of the most famous models of selforganization. Slime mold begin life as amoeba-like cells, each wandering around in random walk behavior. But under certain environmental conditions they suddenly change their behavior and aggregate to a single multi-cellular body; with the help of chemical signals they self-organize into a network of protoplasmic strands. This emergent behavior can solve complex tasks like creating shortest interconnections between food sources in a maze.

Fuligo septica slime mold
(not dog vomit ;-)
from Wikipedia.org/CC license

A research team in Japan discovered that if they placed food piles (oat flakes) around a central slime mold in the same layout as 36 outlying cities around Tokyo, the mold created a network connecting the food sources that looked similar to the existing rail system. By introducing also topographical barriers, the results were even more similar.
Out of this team, Mark Fricker and Dan Bebber recently received the Ig Nobel award in transportation. The Ig Nobel Prizes are given annually for ten achievements that "first make people laugh, and then make them think.". But they are also a show that makes people's interested in science, so the Ig Nobel award might be considered more than just a Nobel Prize parody. However, the slime mold result being awarded there shows that many people still perceive complex systems result as something strange, funny, or improbable. Still, it is great to see research on self-organizing systems awarded!

• A. Tero, S. Takagi, T. Saigusa, K. Ito, D. P. Bebber, M. D. Fricker, K. Yumiki, R. Kobayashi, and T. NakagakiRules for Biologically Inspired Adaptive Network Design, Science 22 January 2010, Vol. 327. no. 5964, pp. 439 - 442.
  
• K. Harmon, Slime mold validates efficiency of Tokyo rail network Scientific American Observations Blog, Jan, 2010.
• The Ig® Nobel Prizes
  

Maxis' forgotten game

Maxis has quite a record in providing interesting simulation games since they came out with SimCity. The game SimLife: The Genetic Playground, however, never became a hit. In the game you can simulate an ecosystem including a climate simulation, a plant groth model and a complex model of animals including herbivores (plant eaters), carnivores (meat eaters), and filter feeders. Not enough, they added an evolution model including genes and phenotypes for all plants and animals.
At this point it becomes clear why this game was without success: it is more a research simulation than an actual game. The number of statistics and graphs also support this impression. Moreover, I guess that the actual processing power at the beginning of the nineties did not allow for extensive simulation experiments. Another distinctive feature between a game and a scientific experiment: a game is designed to give the player a fair chance of success (at least in the lower level). In contrast, SimLife simulations tend to end up in extinct animals and low-diversity flora very often. For example, Spore (from Electronic Arts, which bought Maxis some time ago) has a similar scenario, but is designed as a game. I was not really able to create a stable ecology with more than 5 different species, but still I prefer SimLife over Spore.



In overall, SimLife is interesting from a complex systems point of view even still today. If you want to try it, find it at some abandonware site and run it using an emulator, e.g. dosbox.

• DOSBox, an x86 emulator with DOS
  
• Simlife@Wikipedia
  

Evolving cooperative behavior with neural controllers

In a computer experiment, we have investigated the evolution of cooperative behavior in multi-player games. Players were randomly mixed into groups and had the chance to increase their investment by paying money into a pot where it was multiplied. However, the payout money was evenly distributed to all of the players regardless of their contribution. So a freerider could get money without paying into the pot as long as some others did.
The players were controlled by a neural network that controlled the setting strategy. Using our evolutionary design tool FREVO, we evolved the behavior in order to maximize the profit for each player. There was a pool of players controlled by neural networks. After several rounds, the more successful (thus richer) individuals were allowed to stay in the pool and produce more offspring than the less successful ones.
In the first scenario the payout was the pot times three. So if, everybody would cooperate, you can earn your money gets tripled. If the maximum bet was 20$ this means a 60$ return, in other words a 40$ revenue. But if everybody in a group pays in, it's even better to defect - let's say five out of six cooperate, you get a 50$ revenue.
The game was played iteratively 10 rounds. Originally, we expected a strategy like Tit-for-Tat to evolve and prevail. However, defection turned out to be the only stable strategy. For each system state, individuals with the defecting gene could make more revenue. In other words, ruthless behavior paid off.
The situation changed, when we introduced a "synergy factor" into the payoffs. This meant that the money of cooperating players was not multiplied linearly, but over proportionally. Assume you are working with some colleagues on a common project, let's say writing a book. If you alone invest enough time into you chapter, the book still sucks because of the other chapters which are lame or missing. If half of the authors cooperate, the book might be accepted by a mediocre publisher, but still would not be that promising. But if everybody cooperates, the result is not double the revenue of the 50% case but much more!
In the experiment we reflected this issue by a quadratic factor in the pot function. Evolving the stable strategies again showed that after some generations of defecting players, cooperation evolved as a stable strategy!

This still gives hope for our civilization - although reading the daily newspaper does not always feed this hope.

• I. Fehérvári and W. Elmenreich. Towards evolving cooperative behavior with neural controllers.In IFIP Fourth International Workshop on Self-Organizing Systems, 2009.
• Public Goods Game@Wikipedia
• Prisoner's Dilemma@Wikipedia
• FREVO - a tool for engineering self-organizing systems
• Our project DEMESOS

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