Evolutionary Dynamics

Replicator Dynamics are a math formula meant to simplify the dynamics of evolution. But, we can code, we don't have to simplify.

In this video I show how to simulate simple evolutionary dynamics with more detail than before. The program, it turns out, is simpler than before.

Replicator Dynamics Implementation

In tomorrow's lecture I will be talking about replicator dynamics in games. The video below shows you how to implement it:

Fictitious Play

Next week we will finish with cooperative games and start with 'learning in games'.

Fictitious play is very easy and fun to implement in NetLogo. See how in this video:

Preferential Attachement Graphs and Stochastic Choice

I noticed in the last homework that some of you had problems getting a preferential attachment graph to work, or making stochastic choice. The video below shows how to do this. This will also be useful for HW3.



The code I wrote in that video is prefattachvideo.nlogo.

Spatial Prisoner's Dilemma

In the video below I show how to implement the Spatial Prisoner's Dilemma in NetLogo. This game, and variations of it, is often studied as it is a good model of how 'traits' might move through a population. Note that the 'space' need not be physical: it could be a social network (where the space is how close people are to each other), a computer network (hops), etc.

Game Theory Famous Games

There are certain 2-player games that come up a lot in the real world and have thus been much studied. They are:

The Prisoner's Dilemma:



The Battle of the Sexes:



The Pig and the Piglet:

Stanford Game Theory Course

If you don't like my lectures you can also take the Stanford Game Theory class offered free by Coursera and taught by some of the same guys that wrote the other Multiagent Systems textbook, Shoham and Leyton-Brown. I have watched many of their video lectures and they seem to cover pretty much the same material we will be covering in this section of the class.

I also found this youtube playlist which has all the videos from the class.

Game Theory Solution Concepts

What is the 'correct' solution to a strategic-form game? Well, there are many viable solution concepts.

There is the Pareto Optimal solution (aka 'efficient')



There is the social welfare solution:



There is the maxmin strategy:



And, there is everyone's favorite, the Nash equilibrium:

Game Theory

This week we start our discussion of Game Theory. Here is a quick intro:

Distributed Constraint Optimization

In today's class I will finish explaining how distributed breakout works, and we will probably also cover Distributed Constraint Optimization (DCOP)



Most of the DCOP algorithms are improvements (or parallelizations, if that's a word) on the basic branch-and-bound search algorithm, which I implement below:

Distributed Breakout

Distributed Breakout is one of my favorite algorithms because the basic technique is so simple, so easy to distributed, and, while lacking an optimality guarantee, in practice it is surprisingly effective (unreasonably so!)

Here is a quick implementation in NetLogo:

Asynchronous Backtracking

Another approach to solving distributed constraint satisfaction problems is via search, as with the Asynchronous backtracking algorithm:

Filtering and Hyper-Resolution Algorithms

Today we discussed the Filtering algorithm. Below is a simple implementation in NetLogo:



And, we also discussed the Hyper-resolution rule:

Constraint Satisfaction: Centralized and Distributed

On Monday we will start the next chapter which covers Distributed Constraint Satisfaction and Optimization algorithms. The videos below cover some of this material:


A straight-forward way to solve a Constraint Satisfaction problem is via Depth-First Search:



This is how it looks like when you implement DFS in NetLogo:

Partially-Observable Markov Decision Processess

On Wednesday's lecture we discussed POMDPs. Here is a quick review:

Value Iteration in NetLogo: Finding Optimal Policies for Markov Decision Processes

On Wednesday I will talk about policies and the Value Iteration algorithm.

In the video below you can watch me implement the value iteration algorithm in NetLogo.


If that is too long to watch (it is!) then the one below gives you an overview of the finished implementation.

Agent-Based Modeling Tools

I chose to use NetLogo for this class because it lets us build models very quickly without having to worry about all the graphical, GUI, or plotting code. There are many agent-based modeling libraries and platforms out there. NetLogo is the best at getting a novice from knowing nothing to having fun with his custom-built model.

The Mason Java library is good for large-scale simulations, of the type you would run on a 'supercomputer'. The Repast Java library and IDE is another popular library that integrates with eclipse. Obviously, you have to know Java to use either one of these.

NetLogo Tutorials

On Wednesday's lecture I will give a quick introduction to NetLogo. You should install it and start learning how to use it. The best way is to go to "Help->User Manual" and read the whole thing. I also have some video tutorials which you might find useful, starting with the ones below.

All of the homeworks consist of you writing a NetLogo program that implements a given algorithm or problem, starting with the first one, so, you will want to get proficient fast.










The NetLogo models page has the models that implement the algorithms in the book. These are good for you to play with (change paramaters/code) and get a better understanding of the algorithm and emergent behavior of the system.

Utility Theory

Our first meeting is on Monday. On that day we I will be talking about the class, the history of multiagent systems, and getting started on the first chapter of our textbook.

The first chapter talks about utility functions:


Markov Decision Processes


and Value Iteration

Game Theory

If you want to get an early start on this class then checkout the coursera game theory class. It is taught in part by Yoav Shoham, professor at Stanford, who wrote that other Multiagent Systems book. This class, like theirs will start by covering Game Theory concepts.

I might do some of my own videos.

We will then read some papers and try to build some fun agent-based models, using NetLogo.