Pols 905: Complex adaptive systems

Spring 2005

Paul Johnson pauljohn@ku.edu http://lark.cc.ku.edu/ pauljohn

Office: 312 Blake Hall 864-9086
Office Hours: T&R 1:30-3:00 (except when meetings conflict) & by appointment

Course Objective: To introduce the philosophy and technology that support agent-based modeling. Examples will be drawn from many disciplines. The course will introduce computing approaches in a GNU software environment.

Technical Prerequisites:

Does this course emphasize computer programming? It depends on which kind of research paper you want to do. People who already have a good working knowledge of C will have some advantages. The Swarm Simulation Toolkit is written in Objective-C, which is C with some additional commands. There are many other simulation libraries that you could use instead.

Grading/Requirements

(80%) Everybody is required to write a research paper. The paper must be distributed to the teacher and all students and there will be an in class (10-30 minute) presentation. There are 2 options for the research paper:

  1. Create a simulation model and write a research report about it. Papers will be presented to the class at the end of the semester. Papers of this sort have, in the past, been submitted to journals, and some have been published! The model need not be done in Swarm. Any language, C, SAS, Matlab, Mathematica, or any pre-packaged kit, like StarLogo can be used. We should discuss it.
  2. Write a comprehensive literature review that includes every article or book about simulation in some subfield in any science.
(10%) Weekly exercises/tutorials

(10%) Class discussion/participation.

If you want to create a new model

There are 2 recipes for success.

  1. Create some kind of theory and build a model of it and write it up. This may be the most satisfying over the long run, but it is also the most painful in the short run.
  2. Find some model that has already been done, then get the code for it, or write code for it, and then add some features and write a paper about your modeling experience. During the past 2 years, I've accumulated a pretty good set of code that you can use for this purpose. I have code that can allow you to replicate and explore some classic models, like
I have code for other models that you can explore and play with, including

I have partially-done models that might be interesting to work on, including

I suggest that we might work together on the programming part of the exercise and then co-author at the end if that seems appropriate.

E-mail List:The instructor has worked his personal fingers to the bone creating an archived email list for this class. Everybody is required to join and participate. Any question worth asking is worth writing down and sending through the list, so everybody can see, answer, and learn from each other. I've got the signup/access info on the class homepage, which is: http://lark.cc.ku.edu/~pauljohn/ps905

Pols 909 Weekly Schedule


Contents

1 (Jan 24) Introduction

In Class:
High powered techni-color dream show!
You might make a mental note to check these out at some point

Paul Johnson, ``Simulation Modeling in Political Science,'' American Behavioral Scientist, 42,10, August, 1999.

Robert Axelrod. 1997. Advancing the Art of Simulation in the Social Sciences. In Rosaria Conte, et al., eds. Simulating Social Phenomena, Berlin: Springer, pp. 21-40.

2 (Jan. 31) Complexity before there was complexity theory

Thomas Schelling, Macromotives and Microbehavior. The vital chapters are 1 and 4, but you might skim over 2 & 3 on the way, and chapter 7 is a classic on N-person Prisoner's Dilemmas. (Avid readers might look at Thomas C. Schelling. 1973. ``Dynamic Models of Segregration.'' Journal of Mathematical Sociology, 1:143-186.)

Mark Granovetter. 1978. "Threshold Models of Collective Behavior." American Journal of Sociology, 83 (May): 1420-1443.
In Class:
demonstration of Swarm model of Schelling's segregation theory.

3 (Feb. 7) Cellular Automata: The Grand-daddy of 'em all.

Explanation.
The Cellular Automaton (CA) is the ``basic framework'' from which many approaches/metaphors flow. The most famous of these is Conway's ``Game of Life''. Schelling's tipping model of segregation can also be viewed as a CA.
BEFORE CLASS
 
  1. Read this:

    1. Game of life: John Sprague. 1974. Class notes on John Conway's Game of Life.
    2. Nigel Gilbert and Klaus G. Troitzsch. 1999. Chapter 7, ``Cellular Automata''. Simulation for the Social Scientist. Buckingham: Open University Press. pp. 120-141. (the last part on Lisp is not needed)
    3. Andrzej Nowak and Maciej Lewenstein. Modeling Social Change With Cellular Automata. In Modeling and Simulation in the Social Sciences from a Philosophical Point of View. Hegselmann et al., eds. Kluwer, Boston, pp. 249-285
  2. Snoop about on the internet for references to Conway's game of life.
  3. Please seriously consider doing the ``ConwayIntro'' exercise that I'll written up. It gives the exact commands you can use to build and run a Conway model for yourself in Swarm. Look on the course homepage.

Optional: (There are many articles by these same folks)

Andrzej Nowak, Jacek Szamrej, and Bibb Latane, ``From Private Attitude to Public Opinion: A Dynamic Theory of Social Impact.'' 1990. Psychological Review 97(3): 362-376.

Measuring Emergent Social Phenomena: Dynamism Polarization, and Clustering as Order Parameters of Social Systems. Latane, Bibb, Nowak, Adrzej and Liu, James H. (1994) Behavioral Science, v39, pp1-24.

Social dilemmas exist in space. Nowak, Adrzej, Latane, Bibb and Lewenstein, Maciej. (1994) Pp 269-289 in Social Dilemmas and Cooperation. Schulz, U., Ablers, W. and Mueller, U. (eds). Springer-Verlag.

Clustering processes in economic transition. Nowak, Adrzej, Urbaniak, Jakub and Zienkowski, Leszek. (1996) Pp 42-61.

In Class:
Demonstration of the Social Impact model I've prepared with Swarm. I've made a number of enhancements to the model that incorporate features that cannot be incorporated into the CA representation of the model, so you can see the limitations and the strengths of the CA framework.

4 (Feb. 14) Maybe you like Turtles!

Before Class:
read as much as you can in the small Resnik book, then try out Starlogo-2.1 on a computer. I will have Starlogo available on the Linux systems in the Political Science Labs. In the Lab, I will make it so that Starlogo runs if you open a terminal and type ``starlogo-unix.'' It can be easily installed on your own computers. It does require the free (but large) Sun Java Runtime Environment, which you may already have. I've found the instructions do not exactly match the actual ``how to'' run this, but it does seem to work (after investing only 30 minutes!)
Mitchel Resnik. 1997. Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds. MIT Press/Bradford Books.
In Class:
Demo of StarLogo

5 (Feb. 21) The Big/Small Comlexity Picture

Readings:

  1. See Lou Gross's excellent notes which overview the field of agent-based modeling. This is extremely useful.
    http://lark.cc.ku.edu/ pauljohn/ps905/GrossLectureNotes.fmt
  2. Mitchell Waldrop, Complexity.
    This is the story of Santa Fe Institute legends Chris Langton, Stuart Kauffman, & Brian Arthur. It will introduce you to a lot of the jargon that goes on with the ``complex adaptive systems'' material. Everybody should choose one of these authors and try to really understand what they were working on and why it is important.

6 (Feb. 28). How do get started with computer modeling?

I'd suggest you consult this nicely written book by Volker Grimm and Steven F. Railsback. Forthcoming. Individual-based Modeling and Ecology:

Chapter 6: Modeling Examples

Chapter 7: Formulating Individual-based Models

Chapter 8: Software for Individual-based Models
I have the authors' permission to share this to you in a pdf file that is called G-R_12MaySubmittal.pdf.

Many of these themes are echoed in this fine essay:

Glen E. Ropella, Steven Railsback, and Steven Jackson, ``Software Engineering Considerations for Individual-based Models,'' Natural Resource Modeling, V. 15(1) Spring 2002. (There's a pdf available called RopellaEtAl_NRM.pdf).

6.1 (For Term paper option 1) If you want to actually build a model

This is where you have to start to learn about programming. You should probably learn C (or Java, which is similar). I don't think there is any easy way to do this, one must try to work on example code, then read books to understand why the code works, or does not. In C or Java, one declares variables by their type (e.g., int, float, double, char), they do math with symbols like (+,-,/,%), use conditionals like (&& and ||) and have if/then statements.

1. The classic C book, by the creators of C, is:
Kernighan, Brian W. and Dennis M. Ritchie. 1988. The C Programming Language. 2nd ed. Englewood Cliffs, NJ: Prentice Hall. Chaps. 1-3.

2. I found this very readable and it helped a lot when learning C.

Steven Kochan. 1994. Programming in Ansi C, 2nd ed. Indianapolis: Sams Publishing. Chaps. 4-6.

In these chapters, you will get a treatment of variable types, loops, conditional statements, and other basics.

For Java users, there are some excellent readings as well. I'd suggest

Bruce Eckel's Thinking in Java, which is available free online or for money in bookstores, or

Horstmann and Cornell's Core Java Fundamentals (this is from the Sun company itself)

Step 1.
Get to the nitty gritty
  1. Choose a language
  2. Get a compiler & computer environment set up
  3. Work on some example programs.
If you are a ``clean slate,'' consider using Linux as your operating system, Emacs as your editor, C (and the extensions of Objective-C) as your language, gcc as your compiler. You could use Java.

Read about Unix environments and shells. I have an online notes about this http://www.ku.edu/~pauljohn

Step 2
Hello, world!
Every program I have ever heard of comes with a small demonstration program that you can type in and compile and when you run it, all it does is print out to the screen ``Hello World'' or some other trite message. For your chosen language, find the Hello World program and run it.

Here's such a program for C

http://www.ku.edu/~pauljohn/SwarmFaq/WorkingExampleCode/c/hello_world.c

In a terminal, compile it

# gcc hello_world.c -o hello_world

and then run the program with

# ./hello_world

Then run it again, this time diverting the output from the screen into a file

# ./hello_world >> PaulTrappedOutput.txt

Then email me the file at pauljohn@ku.edu.

Step 3.
Do More Exercises! I have some C exercises and Java exercises floating around
If you are using Swarm, work on the first steps of the tutorial in swarmapps. Those are called simpleCBug and simpleObjCBug.

6.2 (For Term Paper Option 2) Play Around with Starlogo, test out their examples.

Get a copy of the play-along workbook, Vanessa Stevens Colella, Erik Klopfer, and Mitchel Resnik, Adventures in Modeling: Exploring Complex, Dynamic Systems with StarLogo. Teachers College Press (Columbia University)

7 (Mar. 7) Artificial Societies

Readings: Joshua Epstein and Robert Axtell. 1996. Growing Artificial Societies

In_class:
Swarm Sugar Scape in detail, adding a predator.

8 (March 14) Object-Oriented Programming

Objective C Programming

Reading 1. Larkin, Don and Greg Wilson, 1993. Object-Oriented Programming and the Objective-C Language. Redwood City: NeXT Software, chapters 1-3. You can read this online, in html or Adobe pdf format. See the SwarmOnlineFaq for current links. If you have the printed book, that refers to pp. 1-88. If you are reading online in HTML, I mean the chapters called ``Introduction'', ``Object-Oriented Programming'' and ``The Objective-C Language''.

Exercise: Swarm Tutorial: do the rest.

simpleSwarmBug, parts 1-3

simpleObserverBug, parts 1-2

simpleBatchBug, parts 1-3

Recommendation. Download a copy of the Swarm Documentation in html format, or some other format you like.

9 (March 28) Swarm

1. Nelson Minar, Roger Burkhart, Chris Langton, Manor Askenazi. 1996. The Swarm Simulation System: A Toolkit for Building Multi-agent Simulations. http://www.swarm.org

2. Paul Johnson, Alex Lancaster, Benedikt Stefansson. Swarm User Guide. Available at http://lark.cc.ku.edu/ pauljohn/Swarm/Beta/SwarmUserGuide. There is an html version ``userbook.html'' and a postscript version (userbook.ps).

3. Swarm Development Group, ``Brief Overview of Swarm''. That's the first part of the Swarm Documentation Set.

10 (April 4)More Swarm if necessary

Swarm UserGuide Part II (Scheduling) and III Batch Swarm and Model Presentation

Here are some example applications you could consider

  1. Ginger Booth. 1997. Gecko: A Continuous 2D World for Ecological Modeling. Artificial Life 3: 147-163.
    This extends the previous article, that you might also consider:
    Oswald Schmidt and Ginger Booth. 1997. Modelling food web complexity: The consequences of individual based, spatially explicit behavioural ecology on trophic interactions. Evolutionary Ecology 11: 379-398.
  2. Jan-Ulrich Kreft, Ginger Booth, and Julian W.T. Wimpenny. 1998. BacSim, a simulator for individual-based modeling of bacterial colony growth. Microbiology 144: 3275-3287.
  3. Doug Donalson and R. M. Nisbet. 1999. Population dynamics and spatial scales: effects of system size on population persistence. Ecology. 80: 2492-2507.

11 (April 11) Artificial Stock Market and other ``how to'' advice

Please see http://artstkmkt.sourceforge.net.

Paul E. Johnson, ``Agent-Based Modeling: What I Learned From the Artificial Stock Market,'' Social Science Computer Review, V 20(2) Summer 2002, p. 174-186.

W.Brian Arthur, John H. Holland, Blake LeBaron, Richard Palmer, and Paul Tayler. Asset Pricing Under Endogenous Expectations in an Artificial Stock Market. SFI working paper.
In Class:
The ASM code base and possible extensions

12 (April 18)The Opinion Formation Model

  1. Axelrod, Robert. 1997. ``Chapter 7: Dissemiating Culture'' and ``Appendix A: Replication of Agent Based Models'' In Robert Axelrod, The Complexity of Cooperation. Princeton, NJ: Princeton University Press.
  2. Chapters 6 & 7 in Robert Huckfeldt, Paul Johnson, and John Sprague. 2004. Political Disagreement. New York: Cambridge University Press.

13 In Praise of the Prisoner's Dilemma

Reading 1. (If you have not read this yet, do it now) Robert Axelrod. 1981. The Evolution of Cooperation among Egoists. American Political Science Review 75 306-318.
If you find that article too forbidding, it was given a book-length treatment in
Axelrod, Robert. 1984. The Evolution of Cooperation. New York:Basic Books.

Here are a some of short articles on the PD. This is a truly massive field of study:

  1. Nowak, M. and K. Sigmund. 1992. Tit for tat in heterogeneous populations. Nature, 355: 250-253.
  2. Nowak M. and K. Sigmund. 1993. A strategy of win-shift, lose-stay that outperforms tit-for-tat in the Prisoners' Dilemma game. Nature, 364: 56-57.
  3. Ken Binmore. Review of The Complexity of Cooperation by Robert Axelrod. Journal of Artificial Societies and Social Simulation, I. This is ON-LINE: http://www.soc.surrey.ac.uk/JASSS/1/1/review1.html.
  4. Martin Nowak and Robert May. 1992. Evolutionary games and spatial chaos. Nature, vol 359 (Oct. 29): 131-134.
  5. Bernardo Huberman and Natalie Glance. 1993. Evolutionary Games and Computer Simulations. Proc. Natl. Acad. Sci. USA, 90 (August): 7716-7718.
  6. Nowak, Martin, Bonhoeffer, S. and May, R.M. 1984. Spatial games and the maintenace of cooperation. Proc. Natl. Acad. Sci. (USA), v91, pp4877-4881. 1994.
I wish somebody who has seen the PD material before would do some ``reading up'' on the spatial Prisoner's Dilemma literature. Here is a little list of things that I'm aware of:

Nowak, M.A. and R. May. 1993. The spatial dilemmas of evolution. International Journal of Bifurcation and Chaos, 3: 35-78. (I have a copy of this, our library does not)

Lindgren, Kristian. 1991. Evolutionary Phenomena in Simple Dynamics. In Christopher G. Langton, J. Doyne Farmer, S. Rasmussen and C. Taylor, eds. Artificial Life II. Reading, Mass.: Addison-Wesley, pp. 295-312.

Lomberg, Bjorn. 1996. Nucleus and Shield: The evolution of social structure in the iterated Prisoner's Dilemma. American Sociological Review 61: 278-307.

Steven Majeski, Greg Linen, COrina Linden, and Aaron SPitzer. 1999. Agent Mobility and the Evolution of Cooperative Communities'' Complexity 5(1): 16-24.

Steven Majeski, Greg Linden, Corina Linden, and Aaron Spitzer. 1999. A Spatial Iterated Prisoners Dilemma Game Simulation with Movement. In R Conte, R Hegselman, and P. Terna, eds. Simulating Social Phenomena. Berlin: Springer-Verlag, 161-167.

14 Voting Models.

Ken Kollman, John H. Miller, and Scott E. Page. 1992. Adaptive Parties in Spatial Elections. American Political Science Review 86: 929-937.

Kollman, Ken, John H. Miller, and Scott E. Page. 1998. Political parties and electoral landscapes. BritishJournal of Political Science 28: 139-158.

Johnson, Paul E. 1996. Unraveling in a Variety of Institutional Settings. Journal of Theoretical Politics 8(3): 299-300.

Kollman, Ken, John H. Miller, and Scott E. Page. 1997b. Political Institutions and Sorting in a Tiebout Model. American Economic Review 87 (December): 977-992.

Kollman, Ken, John H. Miller, and Scott E. Page. 1997a. Computational Political Economy. In W. Brian Arthur, Steven N. Durlauf, and David A. Lane (eds.) The Economy as an Evolving Complex System II. Reading, MA: Addison-Wesley, pp. 461-490.

15 Killing time to fill up the semester

Outlooks on Computer Modeling.

(This is a reading week to allow a ``catch-up'' period on the programming issues)

Reading 1. Paul Johnson, Rational Actors Versus Adaptive Agents. 1998. I have copies available online at http://lark.cc.ku.edu/ pauljohn/ResearchPapers/APSA98-MTHDS. Reading 2. John Casti. 1997. Would Be Worlds, pp. 13-30.

Reading 3. Steve Bankes, 1993. Exploratory Modeling For Policy Analysis. Operations Research. 41: 435-449.

Reading 4. John Holland and John Miller. 1991. Artificial adaptive agents and economic theory. American Economic Review. 81: 365-70.

Reading 4-alternate. Richard K. Belew, Melanie Mitchell, and David H. Ackley. 1996. Computation and the Natural Sciences. In R.K.Belew and M. Mitchell, eds. Adaptive Individuals in Evolving Populations. (Addison-Wesley), pp. 431-440.

Reading 6. Robert Axelrod. 1997. The Complexity of Cooperation, pp. 3-6.

Reading 7. John L. Casti. 1996. Seeing the Light at the El Farol. Complexity. pp. 7-10.

In case you are interested, there is much more on ElFarol:

W. Brian Arthur. 1994. Inductive Reasoning and Bounded Rationality. American Economic Review 84: 406-411

(and the related ``minority game'') D.Challet and Y.-C. Zhang. Emergence of Cooperation and Organization in an Evolutionary Game. This and more can be found at this web site: http://www.unifr.ch/econophysics. Look for the link to the Minority Game, and then to Damien Challet's site. He has preprints of everything. Get a postscript reader for .ps files. (There's a free reader called GhostView if you are on a Windoze machine).

16 Alternative Time Killing Material

Nicholaas J. Vriend. 1995. Self-Organization of Markets: An Example of a Computational Approach. Computational Economics 8: 205-231.

Peter Albin and Duncan K Foley. 1992. Decentralized, Dispersed Exchange Without an Auctioneer. Journal of Economic Behavior and Organization. 18: 27-51.

Robert Hoffmann and Nigel Waring. The Localization of Interaction and Learning in the Repeated Prisoner's Dilemma. SFI Working Paper 96-09-xx.

14. Topics of student interest/ Presentations

15. Topics of student interest/ Presentations Watts, Duncan and Strogatz, Steven H. Collective dynamics of 'small-world' networks. Nature, v393, 440-443. 1998. Reality Rules: picturing the world in mathematics. Casti, J. L. New York : J. Wiley, c1992. Would-Be Worlds: How Simulation is Changing the Frontiers of Science. Casti, John. Wiley, NY. 1997. Abbrev: WBW Hidden Order: How Adaptation Builds Complexity. Holland, John H. The MIT Press, 1995. Emergence: From Chaos to Order. Holland, John H. Addison Wesley, Reading MA. 1998. Out of Control Kelly, Kevin. Addison Wesley. 1996. How Nature Works: the science of self-organized criticality. Bok, Per. Springer-Verlag. 1996.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -no_navigation -contents_in_navigation -no_subdir -split 0 -show_section_numbers /tmp/lyx_tmpdir32499GB1j6J/lyx_tmpbuf0/syllabus05.tex

The translation was initiated by Paul Johnson on 2005-01-24


Paul Johnson 2005-01-24