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.

A tool for engineering self-organizing systems

A main problem in engineering self-organizing systems is to find the respective behavior for the interaction of the components so that the intented behavior emerges. We address this problem in the DEMESOS project. As an outcome of the project, we have just released a first version of our Framework for Evolutionary Design (FREVO). The tool is very generic and can be applied to find a (possibly distributed) solution (i.e. a configuration for a controller) for a defined problem (i.e. a simulation giving a fitness function) using an optimization algorithm. An example of its use was to breed the neural network controllers for an agent-based robot soccer team (see http://wwwu.uni-klu.ac.at/welmenre/papers/fehervari-2009-evolutionary-methods-in-self-organizing-system-design.pdf).
FREVO is released under the GPL open source license. The framework, some sample components, and a tutorial can be accessed at the project webpage http://www.frevotool.tk.

Self-organizing systems can solve real-world problems

On January 12, 2010, a horrible earthquake struck Haiti, devastating many houses, streets and bridges. This changed infrastructure makes it very difficult for the rescue and support teams to plan the transport of supplies and medical goods, since the standard street maps became inaccurate. To quickly adapt to these problems, the OpenStreetMap community distributedly updated their map information and integrated various data sources, thus providing an accurate mapping almost in real time (see http://wiki.openstreetmap.org/wiki/WikiProject_Haiti). This example shows that self-organizing approaches are especially of interest in catastrophic scenarios, where traditional hierarchically structured systems are missing the necessary level of robustness and adadptivity.

At IWSOS'09 in Zurich

We went to Zurich, Switzerland to attend IWSOS 2009, the Fourth International Workshop on Self-Organizing Systems, which was held in December 9-11 2009. I gave a talk on A Survey of Models and Methods for Self-Organizing Networked Systems, which was joint work together with Raissa D'Souza, Christian Bettstetter, and Hermann de Meer. My colleague István presented a poster on Towards evolving cooperative behavior with neural controllers were we researched on the initial conditions which are necessary to evolve cooperative behavior.

A review on the Lakeside Research Days 2009

Beginning of last summer we organized the Lakeside Research Days 2009 at the Labeside Labs in Klagenfurt. The days, which took place for the second time, were an intensive one-week workshop full of discussions, talks, and group work on the topic of self-organizing systems. The speakers, all deeply involved in self-organizing systems research, included Alain Barrat, Christian Bettstetter, Francis Heylighen, Hermann de Meer, Raissa D'Souza, Marc Timme, Anne van Rossum, and myself. The event was very successful in providing new insights, creating ideas, enabling cooperations and, in general, creating the joy of science reminding me why I became a researcher.
Our colleague Christian Philipp made an excellent short movie capturing the atmosphere and spirit of the event:

The self-organizing student protest at University of Vienna

On October 22, hundreds of protesting students occupied the Audi Max lecture room at the University of Vienna in order to create more awareness for their situation and their demands for a better university. Actually, the quality of the studies decreased when Austrian goverment de facto waived the tuition fees creating a flood of national and international students into particular studies. Since that date, the students still occupy the lecture room.
While I am very sceptic that their demands for a high quality study with a low student-to-professor ratio together with an unlimited offering of studies at no charge can be ever fulfilled within a reasonable budget, I am very impressed by the organizational structure of the protesters.
The Audi Max has a nominal capacity of 800 persons, thus without any kind of organization, the communication and coordination would not work. The traditional approach would be to elect a leader and a group of sub-leaders, etc. in order to build a hierarchically structured organization. Interestingly, the protesters are not organized like this. Instead their movement is self-organized, but structured into several task forces. This makes a lot of sense, since the people powering the protest are not always there - some might lose interest or stay away for some time, while others might join. Thus, while a service, like for example the press information is stable, its establishing components might be not. This is a nice analogy to bodily organs consisting of cells that die and reproduce in a much faster pace than the time span for which the organ is operable.
Furthermore, the students organize two plenum conferences everyday where the task forces coordinate. This plenum is as well based on a grassroots democracy. While there are elected moderators for the discussion, there is no permanent hierarchy in the organization. Yet, the system is effective and stable.
By the way, this is only one out of probably thousands and thousands examples for self-organizing systems. In a paper at IWSOS'09, we investigated how we can design or model such systems.

IEEEXtreme 24 hours programming contest

I was asked to act as a proctor for the team "Quit pro Code" at the IEEEXtreme 2009 contest. Since the tasks of a proctor (mainly to take care of the team(s)) are small comparable to those who are actively participating, I had some time to analyze the contest and learn about its philosophy.
The team of three programmers was given a set of problems which they have to implement in their favorite programming language (at least C,C++,Java were supported). All problems came with an exact specification and a set of test cases. The evaluation of a solution was performed automatically via the Mooshak tool. Given that the contest organizers had chosen their testcases well, this meant that a solution had to be perfect up to the last bit and, in some cases, also performant enough in order to give points.
It was interesting to note that time appeared not to be a limiting factor for the success in the contest. How fast problems have been solved only influenced the ranking between teams with the same amount of points. Basically, this was a good choice, since it gave a motivation for the teams to sleep and eat regularly within the 24 hours in order to stay focused.
None of the exercises involved writing large or even moderate-sized programs. As far as I could see, the solutions of my team usually were below a length of 200 LOC. The trickiness was more in deriving the idea for the possible solution and implementing it well without errors. Also creating test cases with good coverage was a very demanded skill in the contest.
To conclude, although I thought before that the IEEEXtreme contest is an event for code "hackers", my opinion is now that some classic rules of software engineering still hold true for this event. The requirement that a solution had to be exactly correct did not allow for a sloppy or ad-hoc programming style, and thus the classic stages like specification of operational and performance qualification, design specification, implementation, black box and white box testing and validation could be observed. Since a team member spent only 2-3 hours on one problem, I could observe miniature software projects evolving in a fast-forward manner.
By the way, the team Quit pro Code finished place 25th out of over 700 participants from all over the world. So, I am very proud of the team that I was allowed to proctor!

See also

• Sixth IEEE Xtreme Programming Contest: Bunnies in the Forest (Experiences from IEEE Xtreme 2012)

The discussion on the flood of new students at Austria's universities

Recently, the Austrian goverment has decided to waive tuition fees for most students from European Union (EU) if they are within a given time plan. Students from outside of the EU pay half of what they have paid so far.
Many newspapers reported now about a consequence of this action - Austria's universities are overrun by students, which compromizes the quality of the studies. Very controversial, Austrian universities have also shown to be attractive for students from Germany who did not get approved at universities in their home country.
Unfortunately, newspapers have concentrated on complaining about the situation for overrun studies (typically psychology or communication science). However, this is not the case in general. It is worth mentioning that the University of Klagenfurt offers a technical study on "Information Technology" in English language, where currently only a few number of students fill the lecture rooms.
Although the study is of high quality and the teacher-to-student ratio is excellent, the curriculum does not attract too many students, neither national nor international. A main reason therefore is, in my opinion, the lack of information about this possibility. I don't want to be pathetic, but I get the impression that newspapers always forget that the University of Klagenfurt even has a technical faculty. And it seems that journalists prefer articles that make noise about a problem and stir up old Austrian-German ressortiments rather than providing potential students the information how to avoid this problem by choosing a study that is not overrun...