Pols 909

Look here, I'm working on it!

Paul Johnson pauljohn@ku.edu http://lark.cc.ku.edu/~pauljohn
508 Blake Hall 864-9086
Office Hours: M T W 10:30-11:30 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

(70%) 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.

(20%) 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."

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

2. Background

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. Read about Unix environments and shells. I have an online course about this. You should look at the first main section of this document:

http://lark.cc.ku.edu/cgiwrap/pauljohn/UnixAndSASFAQ

Even if you don't have an account on lark.cc.ku.edu, you can still make use of most of the advice in here.

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

Exercise 2.1. Get access to a GNU environment. That means either install Cygnus B-20 (and Emacs) on a Windows PC or gain acces to a Linux system (or install Linux on your computer) with the gcc compiler or get an account on lark.cc.ku.edu. There is help in the SwarmFaq if you want to use either of the first two alternatives. For additional information on setting up Cygwin and Emacs, there is a very nice site here: http://sunsite.auc.dk/jde/install.html#Installing Cygnus Unix Utilities . Note, most of his advice is good. I just use c:\home\pauljohn for my account name, I don't put user in front of it.

There is a Swarm CD I can lend you. It has most of these things.

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 wise to install an X Server on the system from which you will access lark. There is a free X Server called MIX, I have a guide to installing it on my personal homepage in the section on Blake Hall Documentation. I can also give you copies of the free version of MIX, which may be hard to find.

Exercise 2.2. 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...

3. C Programming.

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.

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

Exercises 3.1-3.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:

Exercise3-1.c
Exercise3-2

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.

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.

4. 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 4.1. Install Swarm. (See SwarmOnlineFaq)

Exercise 4.2. Swarm Tutorial (from swarmapps package)

Do these three parts.

For these, you read the README, and to build the executable you type "make" (that runs the make program) and then to run the program you type ./program-name. I expect you will cry and whine about getting this up and running.

Exercise 4.3. Download a copy of the Swarm Documentation in html format (at the current time, the newest is for 2.0.1): ftp://ftp.santafe.edu/pub/swarm/swarmdocs-2.0.1/set-2.0.1-html.tar.gz. Since you have a GNU environment handy, use it to un-gzip and untar this file. I think your tar in Cygnus is full-fledged GNU power, so try this to look at the package "tar tzvf set-2.0.1-html.tar.gz" and, to unpack, replace the t by an x. Otherwise, you have to do the separate gunzip and tar steps, these are outlined here in question 9 in http://lark.cc.ku.edu/~pauljohn/SwarmFaq/Swarm-Unix-FAQ.html

5. 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 wrote a tutorial for a recently published book. I'm doing my best to get a hold of it.

Exercise 5.1. Do more steps in the Swarm tutorial.

6. 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 5. Joshua Epstein and Robert Axtell. 1996. Growing Artificial Societies, Chapter 1.

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

7. Swarm Scheduling and Other Stuff

Reading 1. Swarm UserGuide Part II.

Reading 2. Epstein & Axtell, Chapter 2-4.

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. Currently, it is: ftp://ftp.santafe.edu/pub/swarm/users-contrib/anarchy/sss-2.0.tar.gz

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

8. 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. Reading 4. To be announced (probably from the Luna/Stefansson volume).

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

9. 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)

Exercise 9 I'm working on a version of the Tipping Model that you can play with. Stay tuned for information. I'm also looking around for a Game of Life. Perhaps we will leave the Swarm World for that.

10. More stuff on CAs and 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. 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:

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