Agents Manual

Agents is an acronym for "A Game theoretic Evolutionary Network Traffic Simulator". Agents is a tool to simulate the behaviour of selfish agents in traffic networks by applying dynamics from Evolutionary Game Theory. It features the well known replicator dynamics as well as an extension for old, i.e., outdated, information, the BNN dynamics and the logit dynamics. For an introduction into evolutionary game theory applied to traffic networks we refer to

Simon Fischer and Berthold Vöcking: On the Evolution of Selfish Routing. In: Proceedings of the 12th European Symposium on Algorithms (ESA) 2004, LNCS 3221, Springer-Verlag, pages 323-334.

Table of Contents

• A Brief Introduction
• The User Interface
• The Network Panel
• The Dynamics Panel
• The Simplex Panel
• The Plotter
  
• Copyright Note

A Brief Introduction

We want to simulate the following process. We are given a network with source s and sink t. There is an infinite number of selfish agents that want to route their traffic from s to t and they may choose an arbitrary simple path connecting these two nodes. Now, the latency of an edge e depends on the load of this edge, denoted by x_e. The more crowded a link is, the longer it takes to pass that link.

The agents play the following game. At each step, an agent chooses a random opponent and compares her fitness with the opponent's fitness. If she does better than the opponent, nothing happens. If she does worse, she adopts the oponent's strategy with probability proportional to the latency difference. In the fluid limit this process leads to the well-known replicator dynamics:

Here, x_p is the population share using path p and l_p is the total latency of that path. Finally, the dot indicates the derivative with respect to time and the bar indicates the average.

Other aspects can be taken into account, e.g., random mutation or information getting outdated. This yields to a variety of possible dynamics.

The User Interface

The Network Panel

This panel shows a visual representation of the network. Nodes are depicted as circles and edges are lines between the circles. Thickness and colour of the edges indicates load. Edges are labelled with their latency functions, where x represents the load on the edge.

Nodes can be moved around by dragging them with the left mouse button and new edges can be inserted using the right mouse button.

Right-clicking the panel brings up a context menu from which the network editor can be launched. Nodes can be selected using a drop-down list. The main part of the frame displays a list of outgoing edges. The text box right of these nodes specifies the latency functions that are of the form aixi+... where exponentiation is written as ^. New edges and nodes can be inserted using the buttons.

The Dynamics Panel

This panel can be used to select and start the dynamics. Thy type of dynamics can be selected by using a drop-down list. In the upper portion of this panel, settings for the dynamics, depending on the type, can be made.

• Replicator dynamics: The well known replicator dynamics. No settings.
• (alpha,beta)-Exploration-Replication dynamics: This dynamics consists of a sampling and a migration step: For the sampling step, each agents decides whether to make an exploration step or a replication step. The first happens with probability beta whereas the second happens with (1-beta). In an exploration step, a strategy is chosen uniformly at random, and in a replication step, another agent is sampled uniformly at random. In the migration step, the agent imitates the sampled strategy with a probability which equals the relative payoff gain.
• Mutation dynamics: Introduces a small amount of mutation, i.e., every agent switches to a random strategy with probability mu.
• Logit dynamics: A smooth approximation of the best reply dynamics. epsilon is an approximation parameter.
• BNN dynamics: The Brown-von Neumann-Nash dynamics. No parameters.
• Imitate better dynamics: An imitation dynamics where an agent imitates its opponent with probability 1 if the opponent is better than the agent itself and with probability 0 otherwise.
• Strategy sampling dynamics: Similar to the replicator dynamics, but samples strategies uniformly at random (instead of weighted by the respective population share).
• Bulletin board dynamics: This dynamics is superior to the old information dynamics, since it allows for the simulation of all the other dynamics under old information. At the beginning of a phase, all payoffs are posted on a bulletin board and agents behave as if this were the current payoff.
• Delay dynamics: Similar to the bulletin board dynamics, other dynamics can be plugged into the delay dynamics. Here, the payoffs used for the agents choice rules are some fixed time interval behind.

In the central portion of the panel, the start vector can be selected. Clicking on Normalize will normalize the vector such that it sums up to 1. Perturb will add a small amount of random noise and normalize the vector.

The Go button starts the simulation. The delay slider will select the speed of the simulation. Setting this to zero performs simulations with maximum speed but may slow down your machine. Colors can be selected manually or automatically assigned to each new plot.

The Simplex Panel

Solution orbits are plotted on this panel. Also, clicking inside the simplex will select a starting vector for the dynamics panel. The plots are projected to three dimensions that can be selected using the drop-down lists. Each dimension refers to a path between sink and source. The dot inside the simplex indicates a fixed point of the dynamics.

The Plotter

Here, certain potential functions are plotted. Among these are the well-known potential functions by Rosenthal and the conditional entropy which can be used for applying Lyapunov's method.

Copyright Note

Agents is distributed under the GNU Public License. In particular, Agents comes with ABSOLUTELY NO WARRANTY; This is free software, and you are welcome to redistribute it under certain conditions. For details see the file LICENSE.

The most recent release is always available from the Agents homepage at Sourceforge: http://jagents.sf.net.