CharityWorld-JASSS

This applet requires Java 1.4.1 or higher. You may obtain the latest Java plugin from Sun's Java site.

created with NetLogo
view/download model file: CharityWorld-JASSS.nlogo

WHAT IS IT?

CharityWorld-JASSS is a model designed to show the emergent effects of floating-point errors in agent-based models. This is done by showing how the model behaves dramatically differently using floating-point arithmetic and using real arithmetic. CharityWorld-JASSS also illustrates how floating-point problems can be avoided by using two simple techniques: Tolerance Windows, and Round to n significant digits.

CharityWorld-JASSS is a model of wealth redistribution in which a number of spatially embedded agents begin with a highly unequal distribution of wealth. This unequal distribution is then redistributed by the agents using a simple local rule determining when and to whom money should be given. Each of the four quadrants in the grid represents a different implementation of the same model.

CharityWorld-JASSS is an unofficial and reduced version of CharityWorld. CharityWorld-JASSS should be used for illustration purposes only. You can find the official version of CharityWorld (written in Objective-C) in http://www.macaulay.ac.uk/fearlus/floating-point/charity-world/.

HOW IT WORKS

In CharityWorld-JASSS, the big square grid in the centre is divided into four different quadrants. Each of the quadrants represents a different implementation of the same model. What relates the four implementations is that they behave in exactly the same way for any parameterisation IF RUN UNDER REAL ARITHMETIC (i.e. with no floating-point errors). The four implementations are mathematically equivalent in real arithmetic (which is why we say that they are different implementations of the same model), but they are very different in floating-point arithmetic.

THE MODEL

In this section we explain the model (which is run in each of the quadrants) in a way that would suffice to implement it in real arithmetic. However, as you will see, this description could lead to implementations that behave differently in floating-point arithmetic (differently one from another, and each one of them differently from the correct behaviour).

In this model there is a grid of default size 13x13 (each of the quadrants) which is filled with stationary agents, one per cell. Agents are endowed with an initial wealth of 2 coins.

At the beginning of the simulation agents participate in a lottery for which they have to pay 2 coins as the ticket price. The agent at the centre of the grid happens to be the winner of the lottery so, after the lottery has taken place (i.e. after clicking on Conduct lottery), its wealth in coins is equal to the number of agents times 2, while the other agents' wealth is 0.

At any point in time an agent is locally rich (if and only if the agent is richer than its neighbourhood average), locally average (if and only if the agent's wealth is equal to its neighbourhood average), or locally poor (if and only if the agent is poorer than its neighbourhood average). An agent's neighbours are defined using the Moore neighbourhood, which consists of those agents with whom the agent shares an edge or a corner. Thus, an agent which is not at the edge of the grid has 8 neighbours. The grid does not wrap around.

Our agents have a strong craving for equality, so if they are locally rich, they are prepared to donate a coin to their neighbours who are not locally rich. More specifically, an agent considers its neighbours in ascending order of wealth, and gives one coin to each of them (one neighbour at a time) as long as the donating agent is locally rich and the considered neighbour is not locally rich. This process is called the cycle of redistribution.

Scheduling in the model works as follows: at every time-step a locally rich agent is selected at random and told to perform one cycle of redistribution.

So, to clarify things, the first cycle of redistribution in a simulation run should consist of the lottery winner (who is the only locally rich agent right after the lottery has taken place) giving one coin to each of its neighbours (who are not locally rich). Subsequent cycles of redistribution will also be conducted by the lottery winner until one of its neighbours becomes locally rich and is selected (at random) to perform the cycle of redistribution. At that point, wealth will spread even further, eventually making other neighbouring agents locally rich, and therefore turning them into potential donors. The question is: will wealth be completely redistributed using only this simple local rule?

WHAT IS DIFFERENT IN EACH QUADRANT

Different quadrants implement different equations to assess whether an agent is locally rich, average, or poor. The four equations implemented in CharityWorld-JASSS are all mathematically equivalent in real arithmetic, but can give different results in floating-point arithmetic.

a) Exclusive Mean (bottom-right quadrant): The two quantities that are compared are the particular agent's wealth, and the average wealth in the neighbourhood (excluding the particular agent's wealth in the calculation of the average).

my-wealth <---IS COMPARED WITH---> (sum map [wealth-of ?] my-neighbours) / (length my-neighbours)

b) Exclusive Total (top-right quadrant): The two quantities that are compared are the particular agent's wealth multiplied by the number of agents in its neighbourhood (excluding itself), and the total wealth in the neighbourhood (excluding the particular agent's wealth).

my-wealth * (length my-neighbours) <---IS COMPARED WITH---> (sum map [wealth-of ?] my-neighbours)

c) Inclusive Mean (bottom-left quadrant): The two quantities that are compared are the particular agent's wealth, and the average wealth in the neighbourhood (including the particular agent's wealth in the calculation of the average).

my-wealth <---IS COMPARED WITH---> ((sum map [wealth-of ?] my-neighbours) + my-wealth) / ((length my-neighbours) + 1)

d) Inclusive Total (top-left quadrant): The two quantities that are compared are the particular agent's wealth multiplied by the number of agents in its neighbourhood (including itself), and the total wealth in the neighbourhood (including the particular agent's wealth).

my-wealth * ((length my-neighbours) + 1) <---IS COMPARED WITH---> ((sum map [wealth-of ?] my-neighbours) + my-wealth)

When using coin values that prevent errors from happening (e.g. integers), the 4 algorithms above give always the same answer. The behaviour of the model in real arithmetic is also independent of the particular coin value used. Thus, the four of them will also exhibit exactly the same behaviour for any coin value that does not cause errors (as long as the same random seed is used). On the contrary, when using coin values that cause floating-point errors to happen (e.g. 0.1, 0.2, 0.3, or 0.4), each implementation most often gives a different result (if the model is run for long enough), and the four of them are incorrect.

TECHNIQUES TO DEAL WITH FLOATING-POINT ERRORS


HOW TO USE IT

1. Choose a coin value.
This parameter determines the value of the coin used to calculate every agent's wealth.
Please realise that if the model ran without any rounding errors, then the value of the coin would not make any difference whatsoever. Using binary numbers like 0.5, 1.0, 1.5, 2.0, or any other multiple of 0.5, prevents any errors from happening. Thus, the behaviour of the model using any of those numbers is exactly the same (using the same random seed). On the contrary, using numbers like 0.1, 0.2, 0.3, 0.4, 0.6, 0.7, ... causes the appearance of rounding errors and of its undesirable consequences in the emergent properties of the model.

2. Click on Start over.
At this point every agent will be endowed with 2 coins.

3. Optionally, input your own random seed by clicking on Change random seed.
To replicate runs, use the same random seed.

4. Click on Conduct lottery.
Every agent gives the 2 coins to the agent in the centre.

5. Click on Conduct cycles of redistribution repeatedly.
A locally rich agent is selected at random and asked to perform the cycle of redistribution.

6. Explore the two display modes: The button Update grid is provided to compare snapshots of the two types of graphs above that refer to the same time-step. When the model is running, the grid is updated every time-step automatically.

7. Explore the effects of using different techniques to deal with floating-point errors:

THINGS TO NOTICE

Under real arithmetic, it can be proved that every simulation run should behave in exactly the same way no matter the coin value or the particular implementation of the model (as long as the same random seed is used). It can also be proved that, under real arithmetic, every simulation run should eventually terminate with all the agents having the initial wealth of 2 coins (wealth is eventually completely redistributed irrespective of the coin value, the particular implementation, or the random seed). These results can be checked using coin values that are multiples of 0.5, for which simulations run without errors.

Under floating-point arithmetic, however, the story is very different. There are many parameter values (in fact most of them) for which the coin value makes a difference, the specific implementation makes a difference, and wealth is never redistributed. Some coin values that show this type of behaviour are: 0.1, 0.2, 0.3, 0.4, 0.6, 0.7, 0.8, and 0.9.

THINGS TO TRY

An immediate way of appreciating the impact of floating-point errors in this model is to choose a coin value of 0.4, set the display mode to Relative (local) wealth, and click on Start over (without using any technique to deal with floating-point errors). At this point every agent has a wealth of 0.8, so every agent should be locally average, and should not do anything if the Conduct cycles of redistribution repeatedly button was clicked. However, due to floating-point errors, some agents see themselves as locally rich, some as locally-average, and some as locally-poor (depending on the number of neighbours). Thus, some of them are willing to give some money to others even though they all have exactly the same amount of money! As a matter of fact, if you click on Conduct cycles of redistribution repeatedly (without clicking on Conduct lottery before) coins are indefinitely interchanged in every implementation!! This is caused only by floating-point errors. Such an undesirable behaviour can be prevented by using e.g. tolerance windows with epsilon = 0.001, or round to n significant digits with significant-digits = 6 and epsilon = 0.001.

You can also check that when the coin value is a multiple of 0.5 (no floating-point errors occur), simulation runs terminate with all the wealth redistributed, and the behaviour of the model is exactly the same in the four quadrants and for any of those coin values (remember to use the same random seed). On the contrary, when using a coin value of 0.7, the behaviour of the model is incorrect (it never terminates), and is different between implementations (but it should not be). Such an undesirable behaviour can be prevented by using e.g. tolerance windows with epsilon = 0.001, or round to n significant digits with significant-digits = 6 and epsilon = 0.001.

IMPORTANT NOTE

It is important to remark that the floating-point problems that this model illustrates are caused strictly by the use of floating point arithmetic, not by the use of Netlogo in particular. FLOATING-POINT PROBLEMS ARE BY NO MEANS SPECIFIC ONLY TO NETLOGO. NetLogo, like most programming environments, operates according to the IEEE 754 standard for floating-point arithmetic. You can expect the exact same behaviour if you implement this model in any other platform that follows the IEEE 754 standard.

EXTENDING THE MODEL

CharityWorld-JASSS is an unofficial and reduced version of CharityWorld. CharityWorld-JASSS should be used only for illustration purposes. The official version of CharityWorld, which was created by Gary Polhill and Luis Izquierdo, is more flexible and includes many extensions to this reduced version. You can find the official version of CharityWorld (written in Objective-C) in http://www.macaulay.ac.uk/fearlus/floating-point/charity-world/.

CharityWorld is written in a manner that follows a fairly standard simple Swarm model implementation, with the exception that all floating point numbers are represented using objects rather than the standard double C data type. These objects all belong to the class DoubleSimple, which contains a double instance variable, and methods to replace the arithmetic operators {+, -, *, /} and the comparison operators. Subclasses of DoubleSimple implement various techniques to deal with floating-point problems (e.g. tolerance windows, offsets, interval arithmetic, strings...), and DoubleSimple features creation methods that cause all new floating point objects to belong to one of these subclasses rather than DoubleSimple itself. The user can therefore specify which subclass of Double-Simple they wish to use throughout a particular simulation, and hence which technique will be used to manage floating point issues.

For a detailed description of CharityWorld, see:
Polhill, J.G., Izquierdo, L.R. and Gotts, N.M. (2006)
What every agent-based modeller should know about floating point arithmetic.
Environmental Modelling & Software, 21 (3), March 2006. pp. 283-309.
http://www.sciencedirect.com/science/journal/13648152

LICENCE

CharityWorld-JASSS is a model designed to show the emergent effects of floating-point errors in agent-based models.
Copyright (C) 2005 Luis R. Izquierdo & J. Gary Polhill

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You can download a copy of the GNU General Public License by clicking here; you can also get a printed copy writing to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

Contact information:
Luis R. Izquierdo
University of Burgos, Spain.
e-mail: luis@izquierdo.name

CREDITS AND REFERENCES

CharityWorld-JASSS has been implemented by Luis R. Izquierdo & J. Gary Polhill. We would like to thank Segismundo S. Izquierdo for his helpful comments and suggestions.

If you are interested in the effects of floating-point errors on agent-based models you might also want to read the following papers:

Polhill, J.G., Izquierdo, L.R. and Gotts, N.M. (2006)
What every agent-based modeller should know about floating point arithmetic.
Environmental Modelling & Software, 21 (3), March 2006. pp. 283-309.
http://www.sciencedirect.com/science/journal/13648152

Polhill, J.G., Izquierdo, L.R. and Gotts, N.M. (2005)
The ghost in the model (and other effects of floating point arithmetic).
Journal of Artificial Societies and Social Simulation 8(1).
http://jasss.soc.surrey.ac.uk/8/1/5.html

Polhill, J.G. and Izquierdo, L.R. (2005)
Lessons learned from converting the Artificial Stock Market to interval arithmetic.
Journal of Artificial Societies and Social Simulation 8(2).
http://jasss.soc.surrey.ac.uk/8/2/2.html