The Agency Platform

The Agency is a platform for creating and running agent-based applications. It consists of three components: Facilitator, Agent, and Message:

A typical customization would create extensions of all three classes.

Agency Components

Facilitator

The facilitator maintains a list of all agents. Agents are added to the list using the add method. This method provides an agent with a reference to the facilitator and a unique id number. The addAgents(n) method uses the abstract factory method (implemented in a Facilitator subclass) to create n agents, then adds these agents using the add method.

The facilitator provides synchronized services for delivering messages and for finding partners.

The facilitator's start method runs in two modes: multi-threaded and single-threaded. In multi-threaded mode each agent is started, then joined. In single-threaded mode the facilitator repeatedly iterates through the agents, calling each ones update method until all of the agents are dead.

Message

A message can be anything that implements the empty Message interface:

interface Message {}

Messages can be used to implement asynchronous method invocations. More generally, message passing is an alternative to memory sharing between agents. In this scheme each agent has private local memory that only it can update. Requests to update or query this memory must be sent as messages using the facilitator's send method. (The Actor model is a similar scheme.) Using messages in an agency customization is optional, but be warned that if agents share memory, then access to this memory must be carefully synchronized.

Agent

The Agent update method is abstract. It must be implemented in an extension. Typically, an update method requests a partner from the facilitator, then interacts with the partner. Examples of interactions include fighting, mating, game playing, and bargaining. Agents interact with partners either by message passing or calling partner methods.

Agents are active. This means that they extend Java's Thread class or implement the Runnable interface. The run method repeatedly calls the update method until the agent is dead. It's up to the update method to set the dead flag to true when it cannot do any more useful work.

(Be careful, most Agent methods need to be synchronized.)

Finding Partners

The call: facilitator.getPartner(a) returns a random agent p such that p != a, p.partner == null, and p.dead == false. The method sets the partner of a to p and the partner of p to a. When the interaction is complete both p.partner and a.partner are set to null. If a.partner != null, or no suitable partner can be found after several attempts, then a's partner remains set to null.

Multi-Threading in Java

There are lots of tricky synchronization issues in a multi-threaded application—deadlock, race conditions, starvation, etc. Consult my notes on synchronization in Java for details:

·       Synchronization in Java

A Start

Here's a sketch of the implementation: Agency.java

Customizations

Shared Resources: A Joint Bank Account

In this model a Bank.main creates, adds, and starts two agents: a producer and a consumer that share a joint bank account:

The producer deposits $5 into the bank account 10 times then halts. The consumer withdraws $10 10 times then halts.

A solution: Bank.java.

The output: BankOutput

Ultra Dome

Implement UltraDome as a customization of the agency platform.

Voting Patterns

A precinct is an NxN grid of voter agents. A voter has a randomly assigned party affiliation (Republican or Democrat) and an address (i.e., its row and column in the precinct). A voter, V, updates itself by asking each of its 3, 5, or 8 neighbors in the precinct what their party affiliation is. If a majority have a different party, the V switches to that party. A settable precinct flag determines what to do in the case of a tie.

Implement precincts and voters as a customization of the agency platform. Display the grid at the beginning of the run as a 2-dimensional array of Rs and Ds. Run the simulation for M cycles (try M = 100). Then display the grid again. What changes do you see? Does this explain the red-state/blue-state phenomenon?

Emergent Segregation

In the ES simulation the facilitator is a city containing an NxN grid of houses. Some of the houses are empty, some are occupied by citizen agents. A citizen agent has an attribute called color with one of two values: black or white, and an attribute called happy which is true or false. In the observation phase a citizen updates itself by computing the percentage of neighbors of the same color. If this number is below a global threshold percentage, then the agent sets its happy attribute to false. In the action phase an unhappy citizen asks the facilitator to move it to a random unoccupied house. At the beginning and end of the simulation the city displays itself as an NxN array of U(unoccupied), B (occupied by a black citizen), or W (occupied by a white citizen).

Thomas Schelling observed that for fairly low values of the happiness threshold, 33% for example, segregated neighborhoods still emerge.

(Run ES in single threaded mode for the best result.)

Game Playing Agents

In 1980 Robert Axelrod used agent-based modeling to demonstrate how cooperative behavior in societies could have evolved. He created a society of N prisoner agents. Each prisoner perpetually interacts with randomly selected other prisoners by playing one game of Prisoner's Dilemma. Here's how it works: prisoner A sends prisoner B a message: "defect," or "cooperate". Before looking at the message, B sends A a defect or cooperate message. If both cooperated, then both earn 3 points. If both defected, then both earn 1 point. Otherwise, the defector wins 5 points and the cooperator gets nothing.

Prisoners have different strategies for deciding to defect or cooperate. For example: always defect or always cooperate are two strategies. As one would expect, defectors score much higher than cooperators. Tit-for-tat strategy says defect if the opponent defected on the last encounter, otherwise cooperate.

Genetic programming can be used to evolve optimal strategies, just as it may have happened in human societies. In this model each agent remembers the last K messages of every opponent. For example, if a society consists of 5 prisoners—A, B, C, D, and E, and if each prisoner remembers the last 3 games played with each opponent, then A's memory might look like a 2-dimensional array, where 1 = cooperated and 0 = defected:

A's strategy is any function that maps 3-bits to 1. For example, A's strategy might look like this:

In other words, if A's current opponent defected 3 games ago, but cooperated in the last two games (row 6), then A will cooperate in the current game. What's the logic in this strategy? There is none. It's purely random.

Suppose A and E both have above average scores (i.e., money in human societies). They must be doing something right. As a result, they are attracted to each other. They get married and have a child: F. What will F's strategy be? Genetically speaking, it should be a blend of A and E's strategy. Notice that the strategy is completely determined by the last column, a sequence of 8 bits. If A's strategy is 01100001 and E's strategy is 10111001, then F inherits half of A's strategy and half of E's: 0110 + 1001 = 01101001. This might be a pretty good strategy. Of course Mother Nature isn't perfect, there's a very small chance that one of F's "genes" might get mutated by a stray gamma ray: 11101001. What kind of strategy will generations of selective breeding evolve? (Something close to tit-for-tat as it turns out.)

We may be able to learn something about optimal strategies from a single generation of 16 prisoners each with a memory of the previous two games. There are 16 possible strategies in this case. Distribute them among the 16 prisoners, let them play several hundred games, and print out each prisoner's score and strategy after it's over. Any conclusions?