3.5 Cellular Automata

Note: This is an excerpt from a draft of my thesis, A Computer Model of National Behavior. The introduction and table of contents
are also available

3.5 Cellular Automata

Cellular Automata (CA) attempt to model complex changing environments by assuming they are built up of large numbers of small units that hold values and follow simple rules. These units are called cells, in the simplest CA models a cell can store only a 0 or a 1, and these values can change as the system runs. More complex CA systems allow for much more information to be stored in each cell. Cells are arranged in grids, called latices, in any number of dimensions. CA were initially devised in the 1940s by John von Neumann, whose pioneering work in game theory has already been mentioned. Though some CA insights are used in this model, CA theory by itself fails to correctly model national behavior.

Nearly forty years after cellular automata theory was first proposed, Stephen Wolfram segregated all CA systems in to four classes based on their behavior. Class 1 cellular automata nearly always end in one unique state regardless of initial values. Class 2 leads to a series of patterns that repeat periodically or are stable. Class 3 is aperiodic and chaotic, constantly cycling between seemingly random patterns that are somewhat similar to the initial state. The last class, Class 4, usually lead to the extinction of all values in the system except possibly for a small number of cells.

The implications of these four classes to the behavior of nations is arresting. These four seem to cover all known political science theories. In linear theories, political history is going in one direction to a happy (Class 1) or sad (Class 4) end. Alternatively, time is strictly (Class 2) or loosely (Class 3) cyclical. Otheraspects of CA seem also to fit a national model. Nations occupy places, which might be simplified into cells. In this model nations follow simple rules, and rules are central to CA.

The last important feature of cellular automata is self-reproduction, which further argues in favor of CA approach. This reproduction would allow for generations of nations and the CA’s purposeful reproduction would seem to allow modeling many colonizations efforts. Nonetheless, CA theory fails as an appropriate paradigm for this model on several counts.

First, the lattices needed for CA are too restrictive. By definition they have to be regular, so the grid of cells has to follow a consistent design. However, the political landscape is not laid out this way. One region can have many neighbors, while another otherwise similar one can have only a few. For example, a very low resolution model of Europe might define each place to be a sovereign state. So then some places would have only one neighbor (such as The Holy See or San Marino), some might have two (such as Andorra) and some might have many (such as Slovakia). Though a counterargument can be made that this is an inappropriate scale, even this argument confirms that CA is inappropriate because it predefines what scales are appropriate.

Second, too much data would be stored per cell. Cells are not necessarily limited to boolean or numeric data, but the amount of data that would be needed is nonetheless far more than customary. Population, change in population, wealth, change in wealth, ideology, and other fields will need to be stored. These are only some of the fields stored in the relatively simple version of the model that will be attempted here. Successful CA systems are built on true simplicity, which is a goal perhaps out of reach of this approach.

Third, the CA concept of neighborhood is inappropriate for this model. A neighborhood is the collection of cells that are affected by any one cell, and neighbors are the cells affected by this one cell. Implementations can be different, but normally neighborhoods are defined to be a von Neumann neighborhood (the four cells above, below, to the left, and to the right of a cell) or a Moore neighborhood (which is a von Neumann neighborhood plus the four cells diagonal to the central cell).

medium_von_neumann_neighborhood.2.gif
Graphic 4. von Neumann Neighborhood
medium_moore_neighborhood.2.gif
Graphic 5. Moore Neighborhood

The concept can be expanded somewhat by saying that a cell can affect cells more than one cell away, and even by saying that the effect of a cell falls off with distance, but without significant modification this approach fails to be useful in modeling a complex system.

Advances in communications clearly illustrate this problem. Consider the modern United States of America. America can project maximum force evenly over the entire globe, and more subtle forces can be exerted that are almost as balanced. How would this be modeled in a CA system? First, as discussed above the scale would be inappropriate, and the country would have to be composed of many small cells. A less fine scale would not allow for true CA, because CA assumes that global results emerge from aggregate behavior of many small cells. There has to be a mechanism to allow for joint action. Provinces do not declare war, but the countries they are part of do. CA, by relying on cell-based decision making, does not allow for this. It might be possible to massage the CA model to allow for action like this, but it would go against the philosophy of CA and perhaps even be self-defeating.

Fourth, the CA approach would considerably complicate the modeling of the relationship between nations and places. Explained more fully in the section “Nations-in-Places,” this relationship rationalizes the interaction between nations and places. For a model of most of Europe a few hundred of these relations suffice. However, using a regular lattice thousands of cells will be needed just to create an accurate map of the contours of the continent. Trying to model this with CA would lead to an incredible amount of logic needed for any movement of time. Assuming a hundred cell by hundred cell grid, which seems the minimum for a continental simulation, this gives us ten thousand cells. For every movement, every neighborhood will need to change, and these changes will then have to be factored into the behavior of the nations themselves This might be a benefit if one needed to justify use of a supercomputer, but for a project that will need to complete in reasonable time on reasonable hardware the CA method is out of reach.

Fifth, CA would conflict with other goals of this simulation. Wolfram defines CA systems as “… simple discrete deterministic.” This collides with the objective of this study. Instead of modeling nations as complex living beings, simple rules and values would be used. Instead of modeling nations with fuzzy logic, whole values would have to be used. Instead of the unpredictability of free choice, the outcome of the model could be mathematically proven before it is even run.

For all of these reasons, CA is not currently appropriate as a tool for this model.

Computer Science Thesis Index

3.4 Game Theory

Note: This is an excerpt from a draft of my thesis, A Computer Model of National Behavior. The introduction and table of contents
are also available

3.4 Game Theory

Related to the earlier discussion of war and computer games, game theory is a heavily mathematical approach to rational conflict. Roger McCain states that “Game theory is a distinct and interdisciplinary approach to the study of human behavior. The disciplines most involved in game theory are mathematics, economics and the other social and behavioral sciences.”

The most promising aspect of game theory is that it models competition between rational actors. Spangler breaks game theory into three parts. The interaction can be for “zero sum,” “positive sum,” or “negative sum” games. In zero sum games, the gain of one can only come from the loss of others. In positive sum games, all players can end better off, while in negative sum games all of the players can end the game worse off. Lastly using formal game theory would allow rigorous examination of the model. However, ultimately game theory cannot be much used in the construction of the model adopted by this thesis.

Game theory closely examines competition. Questions such as “What is rational when not all information is known,” “How often is cooperation rational,” and “Are moral rules emerged from rational competition” are asked by the field. All of this is directly applicable to the model. To be valid, the model will have to model nations acting rationally, which is a direct concern of game theory.

Game theory’s applicability to zero sum and non zero sum games is also alluring. In the real world, nations fight wars where each side temporarily sacrifices its own long term growth in order to hurt even more the health of the other. However, many aspects of the real world are not like this. A growing world economy allows all nations to be wealthier than before, which allows them to support more people and have more absolute power. It would be very useful to use a formal guide such as game theory which has this flexibility built in to it.

The formal logic underlying game theory is also an advantage. Like any mathematical statement, a game can be evaluated for a value. It can also be logically tested to see if it is true or false. This would remove some subjectivity from the model, and open the door to further formal methods, such as Z or predicate calculus.

Sadly, this last benefit is also a significant drawback. It must be stressed that game theory is an advanced subdiscipline of mathematics. A comprehensive utilization of game theory would be more appropriate for a dissertation. It would require expertise beyond the scope of this project. Therefore, while the basic lessons of game theory should be remembered throughout this thesis and ensuing model, the use of the mathematics of game theory will not be incorporated into the model used in this thesis.

Computer Science Thesis Index