Pols 909

Spring 2003

Paul Johnson pauljohn@ku.edu http://lark.cc.ku.edu/~pauljohn
508 Blake Hall 864-9086
Office Hours: T W R 1:30-3:00 (except when meetings conflict) & by appointment

Course Objective: To introduce the philsophy and technology that support agent-based modeling. Examples from all areas of study are open for discussion. The course will introduce computing approaches in a GNU software environment.

Technical Prerequisites:This is not a programming course, but it has an awful lot of programming content. It will introduce many programming ideas and it will work at a fundamental level. We will assume most people don't know much about programming at the start. But everyone is expected to learn and to ask questions until they understand (see the email list!). People who already have a good working knowledge of C will have a leg-up on the other students, and I hope they will lend a helping hand now and then.

The Swarm Simulation Toolkit is written in Objective-C, which is C with some additional commands. The most recent versions of Swarm have something called "multi language support". So, if you know Java, you can write your agent model in java, and then link against the swarm libraries, which are written in Objective-C. The usage of Java is an exciting breakthrough, but because it is extremely recent, it is not so well documented as the Objective-C models.

Grading/Requirements

(80%) Everybody is required to write a "term paper" about a simulation model they have created. This must be presented in class in a 10-30 minute presentation. The model need not be done in Swarm. Any language, C, SAS, Matlab, Mathematica, or any pre-packaged kit, like StarLogo can be used.

(10%) Weekly exercises/tutorials

(10%) Class discussion/participation and/or brief presentations. Some parts of the syllabus below say "I wish somebody would look into this."

About the Papers

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 models that might be interesting to work on, including

My fear is that you will get over your head, give up, then turn in a piece of crap. It is important to get started early on a paper topic because you will quickly find that you have an awful lot to learn about computer programming and modeling. 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. That's how Brichoux and I ended up working together. But I am not willing to work with anybody who insists on using Microsoft Windows.

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/ps909

Pols 909 Weekly Schedule

1. Introduction

Readings: Waldrop, Complexity, through p. 198

2. (Feb. 3) What is that complexity thing?

Readings: Waldrop, Complexity, 199-end.

3. (Feb. 10) Artificial Societies

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

4. (Feb. 17) More Overview

Reading 1. Thomas Schelling, Macromotives and Microbehavior, pp. 11-43, 81-165. This book offers is a classic statement of many of the original premises of agent-based modeling) (Avid readers might look at Thomas C. Schelling. 1973. Dynamic Models of Segregration. Journal of Mathematical Sociology, 1:143-186.)

Reading 2. Paul Johnson, "Simulation Modeling in Political Science," American Behavioral Scientist, 42,10, August, 1999.

Reading 1. 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.

5. (Feb. 24) Cellular Automata.

Explanation. The CA is the "basic framework" from which many approaches/metaphors flow. The most famous of these is Conway's "Game of Life". Another is Schelling's Tipping model of segregation.

Reading 1. Game of life: John Sprague. 1974. Notes on John Conway's Game of Life.

Reading 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)

Reading 3. Andrzej Nowak and Maciej Lewenstein. Modeling Social Change With Cellular Automata. In Modeling and Simulation in the Social Sciences from a Philosophical Pint of View. Hegselmann et al., eds. Kluwer, Boston, pp. 249-285

(There are many articles by these same folks)

Social Impact Model CodeI have written a Swarm model to represent a model described in one of the early papers on the Social Impact Model (1990). Perhaps it would be interesting if you took that code and tried to fancy it up a bit and write a paper. I've already made a number of enhancements to the model that incorporate features that cannot be incorporated into the CA representation of the model.

6. (March 3). Yeah, but how do they do that?

This is where you have to start to learn about some serious programming. You need to learn either C/Objective-C or Java. I know both, but suggest you learn C to start, but if you want to know only Java, I'm not going to argue with you. If someone here decides to be a Java user, I suggest using the Sun Java Development Kit version 2.1.1 or later.

Reading for C learners. Read about variables and loops in C. There are many many C books and web sites. C is a basic language and Java has many elements in common with it, so don't worry that this is a useless exercise. Please do your best to learn about types of variables (int, float, char), the use mathematical calculations (+,-,/,%), use of conditional statements like if and the usage of for and while loops.

Pick one of these two books. I have copies of each available for your inspection.

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. Steven Kochan. 1994. Programming in Ansi C, 2nd ed. Indianapolis: Sams Publishing. Chaps. 4-6. (Yes, chapters 1-3 are not required).

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

In the first section of the SwarmOnlineFaq, I have begun to compile a list of online resources for C programming. Some are quite excellent.

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) You need to test this out! so

Step 1: Get access!

Get access to a GNU environment. I'm not endorsing or supporting any effort to use Microsoft Windows as a platform for programming. In my experience, it is just too crappy to do anything useful. So learn how to use the Linux systems in the lab or use the Unix system lark.cc.ku.edu. Learn to use the editor called Emacs. The only compiler worth knowing about is gcc (the GNU compiler collection, renamed from "GNU C compiler").

In the process of working on examples, you will have to log in and try it out. If you have only been a pointer-and-clicker all your life, we may need some hand-holding for you. You will develop some valuable personal skills!

Read about Unix environments and shells. I have an online course about this. I have migrated my support materials for Unix and Linux away from the old FAQ-O-Matic to a new Twiki based site, which is still under construction.

http://www.ku.edu/cgiwrap/pauljohn/twiki/view

Also look at Benedikt Stefansson's "Bash Help" page, a copy of which I like so much I have a copy saved on lark: http://lark.cc.ku.edu/~pauljohn/SwarmFaq/benediktBashHelp.html

One goal here is to learn that you can compile stuff "directly" by using gcc or you can use a convenient program called "make" to automate some of the work. Make is needed when a programming exercise starts to get big--require the integration of code in many files.

If you are going to use Lark this semester, let me know. I'll make sure there is a working copy of Swarm on there. It is necessary to install an X Server on the system from which you will access lark.

Step 2: Simple Exercise Prove to me that you have gained access by getting the file:

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

and saving it in a directory that you have created in your GNU environment. Then "compile" the program by typing the commmand (after the shell prompt, which I symbolize as #)

# 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

This puts the output in "PaulTrappedOutput.txt".

Then email me the file at pauljohn@ku.edu. You can attach files to emails with pine, a common unix mail reader, or Netscape, or just about any email program...

Step 3. Do More Exercises

Exercises 6.1-6.xx: I'm working/looking to steal some example C programs for you to look at/play around with. I'm not expecting that you will write programs from scratch, rather you can look at examples, tinker with them, break them, fix them, etc. I'm going to name these like so:

Exercise6-1.c
Exercise6-2.c

and so forth. Some of these are likely to be directories that contain more than one file. I want these things to highlight the individual effect of various particular statements, like for, if, while, printf, and so forth.

7. (March 10) Artificial Stock Market and other "how to" advice

In March, I expect to have a visiting student from Austria who specializes in the Artifical Stock Market.

I'm digging up some references on the ASM.

One reading for this week will be this fine essay

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. (Available online if you want to read a next-to-final draft).

Other General Advice about modeling:

Glen E. Ropella, Steven Railsback, and Steven Jackson, "Software Engineering Considerations for Individual-based Models," Natural Resource Modeling, V. 15(1) Spring 2002. Online here: http://lark.cc.ku.edu/~pauljohn/ps909/Agent-Based_Models/RopellaEtAl_NRM.pdf

See Lou Gross's excellent notes:

http://lark.cc.ku.edu/~pauljohn/ps909/Agent-Based_Models/GrossLectureNotes.fmt

Exercise7. Swarm Tutorial. Look over the apps in the swarmapps package. Especially the Swarm Tutorial. Hopefully I'll have a version by then that runs with the current Swarm. Or else you will learn first hand how to update software.

Do these three parts.

8.(March 24) 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

Exercise 8 Swarm Tutorial: do the rest.

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

9. Swarm: Introduction and Overview.

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

Reading 2. Paul Johnson, Alex Lancaster, Benedikt Stefansson. Swarm User Guide. Available at http://lark.cc.ku.edu/~pauljohn/Swarm/Beta/SwarmUserGuide/userbook.html. Look over Part I, which is an overview/introduction. That site also has the same document in postscript format (userbook.ps). The Swarm User Guide is an evolving project, your input is appreciated.

Reading 3. Swarm Development Group, "Brief Overview of Swarm". That's the first part of the Swarm Documentation Set you already downloaded.

Reading 4. Benedikt Stefansson, .

Exercise 9.1. .

10. 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/APSA98-Methods.html. I have some hard copies laying around somewhere.

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: econophysics site. 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).

11. Swarm Scheduling and Other Stuff

Reading 1. Swarm UserGuide Part II.

Exercise 7.1. Get & Compile the SwarmSugarScape code, play around with it. This is the file called "sss-2.X.tar.gz" or something like that in the Swarm ftp.

Make sure you notice the way agents are created and the queue used to "recycle" them.

Exercise 7.2. Get my ballet dancing model, which has dynamic scheduling.

Exercise 7.3 If you really want to get the full survey on dynamic scheduling, look at the example programs "pjrepeaterX" in the WorkingExampleCode section of the SwarmFaq section of the web site.

12. Batch Swarm and Model Presentation

Reading 1. Swarm User's Guide, Part III.

Reading 2. 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.

Reading 3. 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.

Reading 4. Doug Donaldson. 1999. Ecology.

Exercise 12.1. To be announced. It will be available at this link:

13. More stuff on Opinion Formation

Reading 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. Reading 2. I have a long-suffering project with Robert Huckfeldt and John Sprague on this model. By the time this section arrives, I will have book chapters to share with you. Until then, the best overview of the project we have is this convention paper we presented at Brown University. Other things: Johnson, Paul. 1999. Protests, elections, and other forms of contagion. Available ONLINE http://lark.cc.ku.edu/~pauljohn/ResearchPapers/APSA99/APSA99-2.html Exercise 10. There are at least three different implementations of the Axelrod culture model that are relatively current. Get the files for these programs, try to compile them, run them, do your best to dig around, find how they are different. Write a page about what you have learned. Here are the culture implementations:

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.

Reading 2. Here are a couple of short ones:

Nowak, M. and K. Sigmund. 1992. Tit for tat in heterogeneous populations. Nature, 355: 250-253.

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.

Reading 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.

Reading 4. Martin Nowak and Robert May. 1992. Evolutionary games and spatial chaos. Nature, vol 359 (Oct. 29): 131-134.

Reading 5. Bernardo Huberman and Natalie Glance. 1993. Evolutionary Games and Computer Simulations. Proc. Natl. Acad. Sci. USA, 90 (August): 7716-7718.

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.

Majeski...

13. 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.

14. Models about Learning.

To be announced

Some possible readings include:
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.

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.