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
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 xe. 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, xp is the population share using path p and lp 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
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
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.
In the central portion of the panel, the start vector can be
selected. Clicking on
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.Top
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.Top
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: