CSCE 782: Problem Set 2

The Garbage Problem

For this problem set you will implement and analyze a distributed garbage allocation problem that I just made up (inspired by the routing problem in the Internet).

In our world the agents are the patches of the NetLogo environment. Each agent gets penalized for any garbage that is within its borders. But, an agent can choose to fling its garbage over to one of its four neighbors (North, South, East, West). The flinging will work only if the neighbor in question is not currently blocking the fence, if he is blocking then the garbage will just bounce and remain in the agent's patch.

The number of garbage units that appear at each time step is taken from a poisson distribution with a given mean (use a slider) and each lives for a number of ticks taken from a normal distribution of a given mean (use a slider).

The basic go loop is as follows:

1. Generate new garbage and kill the ones that have reached the end of their lifetime.
2. Reduce the utility-values of all patches proportionally to the number of garbage pieces in them as well as the time the garbage has been in this pathch. That is, if the garbage is here for the first time then reduce it by 1, if its the second time then reduce by 2, and so on. Increase the utility of everyone else by 1.
3. Each decides which of its 4 neighbors, if any, it will block and which direction it will try to fling the garbage, if it has any.
4. Figure out where the garbage landed.

For visualization purposes you should set the color of the patches proportional to their utility. I also want to see a plot of the total utility over time.

Analysis

You should analyze this problem carefully to determine what is an agents' best strategy. You will then implement at least two different strategies and compare them. That is, let all players play strategy 1 and check the total utility, then check for the case where they all play 2. Finally, check for evolutionary stability. Thas is, if everyone is playing strategy 1 will one agent playing strategy 2 outperform them all by a large margin? (and vice-versa for strategy 2 being invaded by a strategy 1 mutant).

Background

You might be wondering how this is like the routing problem. Well, the Internet is composed of private networks all of which send and receive packets from each other. However, a network is really only interested in serving its customers thus any packet that comes from an external network and is also destined to another external network is like garbage to that network – it does not want it. A naively selfish network would simple drop (block) all such packets. In practice, however, network companies realize the higher good that comes from having a working Internet so they cooperate, but not before signing some highly complex and secret agreements as to how many packets they will route for the other guy, how fast, to which neighbor, etc.