birds: game theory simulator
Version 0.6.8,
Birds is an agent-based simulator of evolutionary population games given operator-defined evolutionary dynamics, selection criteria, and so on. Simulations consist of sequences of matches as follows:
As an operator, you must create a -player, -strategy payoff matrix, choose how many agents you wish to participate and the initial distribution of strategies, choose your evolutionary dynamic (e.g., best-reply), and that's about it. There are many methods for reproduction (it's easy-ish to add more—contact us for details), from the simplest case of a Moran process with payoffs being reproduction probabilities to various best-reply functions. A full list follows:
Results may be visualised in two ways: ergodic analysis (a single, ongoing mutation run) or aggragate analysis (many mutation runs with some sort of stopping criteria).
Each of these views has full support for being exported to publication-quality media (PDF, EPS, PS), web-quality media (PNG), or raw plotter (gnuplot) input for customisation.
The source code is ISC licensed ISO C, the algorithms are mature, and the system built to run on highly parallel machines. What's not to like?
For the time being, birds is distributed in source form or as a Mac OS X application bundle.
To run on Mac OS X Snow Leopard and after, simply download and unpack the bundle. You should then be able to double-click on the icon and start the system.
To compile and link birds, you'll need access to a modern UNIX system (i.e., having a
compiler and make) with GTK+3 libraries installed.
If you plan on exporting plots, you'll also need gnuplot and LaTeX.
While the system should in theory compile and run on any system with C and GTK+3 support (such as Microsoft Windows), to
date it has only been used on OpenBSD, Debian Wheezy
GNU/Linux, and Mac OS X.
Porting birds to non-UNIX systems should be fairly easy given its GTK+3 foundations. Please contact us if you've ported to any system not listed above.
To compile the system, simply run make in the source directory.
To install, run make install.
This will install into the default prefix, /usr/local.
This may be overridden by specifying the PREFIX environment variable while running make
install.
After this, you may invoke the birds front-end by its executable, birds.
That's it!
During runtime, birds looks for the following:
gnuplot (exporting plots)latex (exporting plots)dvipdfm (exporting plots)dvipng (exporting plots)dvips (exporting plots)birds (starting new simulations)
If any of these are not in your PATH environment variable, the stated functions will fail.
Sometimes silently (sorry!).
Start birds by invoking birds after installation.
You'll then be prompted to enter simulation parameters.
There are four broad categories of simulation parameters: game, equilibrium, simulation, and analysis.
If you enter any invalid values, the system will not allow you to continue.
(It won't give you an error—I'm working on this.)
Once you've configured your game, you cannot change the parameters; you can, however, review your game's parameters in
the Properties
window during runtime.
Game configuration refers to your game's general structure: player size, strategy size, payoffs, and so on. The parameters you set in this tab will change the layout of subsequent tabs (e.g., changing strategy size will nullify any equilibria you've set up), so be sure the information is correct before continuing.
When starting up, birds will scan its resources directory (~/tmp/birds/share/birds for UNIX installations or the
Resources directory of the application bundle for Mac OS X) for preset game configurations.
(See Saved Game Format for more information on creating preset games.)
The following well-known games are shipped with the system:
The default game, Custom
, has two players and two player populations, two strategies with payoffs set to zero,
and zero equilibria.
You probably want to change parts of this (hence custom
).
If you don't use Custom
, changing strategy or player sizes will reset preconfigured parameters to the default
Custom
payoffs.
You may specify a name for your game, which is used only for window and exported plot titles.
By default this is Untitled Game
.
Titles for exported graphs are piped through latex via gnuplot, so make sure to escape
appropriately, e.g., math as $\\delta$
.
Lastly, you can set the number of players for Custom
games.
Games are usually for two players, though three-player games aren't uncommon (e.g., Selten's horse).
birds supports arbitrary player counts, although the graphical display will probably get messy
if this gets too high.
If the game is a single-population game, check the box marked as such.
Single-population games are quite different from multi-population games, and have different Nash equilibria (e.g., the
hawk-dove game), so make sure you really mean this!
Control the number of player strategies, usually for a custom (non-preset) game. This must be greater than one. birds supports arbitrary strategy counts, although the graphical display will probably get messy if this gets too high. A single-population game needs equal strategy sizes. If you have inequal strategy sizes, the single-population status will be silently disregarded.
For applicable reproduction strategies, one must assign probabilities for the reproduction of a given player and strategy in the payoff matrix. This reproduction probability for player i, πi, is assigned in a bimatrix (column-player I, row-player II) as follows:
| I-a | I-b | |||
|---|---|---|---|---|
| II-a | πI(I-a, II-a) | πII(I-a, II-a) | πI(I-b, II-a) | πII(I-b, II-a) |
| II-b | πI(I-a, II-b) | πII(I-a, II-b) | πI(I-b, II-b) | πII(I-b, II-b) |
Additional players augment the left-hand side of the table; thus, each added player appends an entry to the right side of the payoff tuple.
The row- and column-players are reversed from their canonical normal-form game layout. However, the non-canonical scheme extends to >2 players much nicer.
By default, payoffs specified in this grid will be mapped linearly into the unit interval with the minimum player payoff
at 0 and remaining probabilities scaled within the interval between the maximum and minimum payoff.
(Birds uses reproduction probabilities, not raw payoffs.)
For example, the prisoner's dilemma (with strategies coördinate
and defect
) is translated as
follows:
| C | D | |
|---|---|---|
| C | 1, 1 → 0.5, 0.5 | 2, 0 → 1, 0 |
| D | 0, 2 → 0, 1 | 0, 0 → 0, 0 |
If truncation is selected, payoffs are not linearly mapped but assumed to be within the unit interval. Payoffs above and below this interval are truncated to the respective interval bound.
| C | D | |
|---|---|---|
| C | 1, 1 → 1, 1 | 2, 0 → 1, 0 |
| D | 0, 2 → 0, 1 | 0, 0 → 0, 0 |
In the broadest sense, dynamics consist of selection, reproduction, and death processes. Birds is bundled with a variety of dynamics.
The simplest reproduction is a Moran process with reroduction probabilities being the normalised payoff table values. In other words, agents are randomly selected and reproduce with the probabilities given by the selected strategy profile. To control for population size, offspring replace randomly-selected agents in their respective player populations. You may also specify a mutation probability in which the strategy of a reproducing individual will be drawn uniformly from her available strategies instead of the parent's. In other words, each strategy i is selected with probability qi as follows, where n is the number of the i player's strategies, is .
A consideration set is like a weighted best-reply
hybrid with no probability of payoff evolution and mutation.
There are some critical differences, however.
First, before running the best-reply routine, the agent's strategies are reduced to a consideration set
.
The consideration set is created by removing strategies with the probability given at configuration. If the
consideration set happens to be empty, the agent wakes up
and uses the full strategy set.
Then, the hybrid best-reply function selects
strategies in the consideration set with probability
.
Note that, if the consideration set strategies are not being played by the agent's population, this will result in a division by zero. This, if this happens, the weight factors are removed.
In the event of the weighted best-reply hybrid
(McKelvey, 1995; Hofbauer, 1996), per-player agents are randomly selected to play against each other.
You must select a probability of best-reply response with the remainder
relegating to payoff evolution.
In the best-reply case, a player
with utility function accepting a pure strategy and player population shares
will switch to her strategy with probability
given the sensitivity parameter
:
The two-speed evolution model (Alger and Weibull, 2012) a single agent is drawn from the single
population.
Prior to the mutation run, each agent is assigned an incumbent
or mutant
type corresponding to a morality
parameter , with only a single mutant at the start.
Then with the given probability, the agent switches her strategy (but not type) according to the weighted best-reply hybrid.
In the other case, the individual may change her type (and thus utility function) with probability:
The material payoff in the preference evolution is the payoff as given in the payoff matrix. The strategy evolution utility depends on the player's type.
In the event of weighted best-reply
(McKelvey, 1995), per-player agents are randomly
drawn.
Each individual switches to her
strategy with probability
given the logit probability
η, where a probability is equivalent to uniform random
response, and sensitivity as follows:
This uses the traditional best-reply dynamics where, unless randomy mutating, per-player randomly-drawn agents switch to the best-reply strategy of the current population mixture:
If the agent's current strategy is in the best-reply set, she does not change strategies. If there are multiple strategies in the best-reply set for player i, one is chosen at random.
The fictitious-play learning model (Young, 1998) causes the player proportions to be determined from a random selection of prior plays from a set of entries. The initial plays are randomly assigned.
The next tab configures simulation equilibria, represented as players' strategy population fractions and an equilibrium neighbourhood. These are used in the single-run view to record equilibrium visitation rates and timed-exit view to record distance from equilibrium at exit. Equilibria are labelled numerically throughout the system, so make sure to remember the equilibrium label.
Make sure that equilibrium neighbourhoods don't overlap.
The equilibrium neighbourhood defines a region above and below the equilibrium point. Thus, a strategy mixture x is within an equilibrium x̃ neighbourhood of 0.1 if each fraction xi ∈ x̃i ± 0.1.
If an equilibrium is on the polyhedron border, the neighbourhood should be adjusted accordingly.
The next tab configures individual runs of the simulation (which may be just one, in the single-run ergodic case). In general, a simulation run consists of an initial strategy distribution, a death process to control for population, and the run mode (single-run, multiple-run).
Specify initial population shares and total number of birds, to be evenly divided among populations.
If the total number of birds does not divide evenly into the number of populations, the last population acquires the
remainder.
When dividing shares into strategies, the last strategy acquires any roundoff.
Similarly, if the shares don't add to one, the last strategy gets the remainder.
By default, simulations start with a random mixture of agent strategies per population.
If running a single-population game, shares are only divided into the first player
's strategies.
If you specify that the initial shares be random, they will be randomised for each simulation run (the initial share values are ignored).
Set physical properties of the simulation. If the random seed (see Randomness) is is less than zero, a random number (from the system's random number generator as seeded by the time upon system start-up) will be selected as the random seed. If the simulation is non-ergodic, then you may also specify the number of threads you wish to execute.
The last tab configures analysis options.
This configures how a simulation is visualised/analysed.
The default one-shot (ergodic anslysis) option executes a single run forever.
The timed-exit option runs a simulation repeatedly until a given t matches, aggregating a number of statistics at time t into distributions.
The first-exit option runs a simulation repeatedly until it exits from the Initial Distribution neighbourhood or the maximum time is exceeded. It then aggregates statistics at this exit time into a distribution. The distribution neighbourhood is calculated as in the Equilibria section. The pure-strategy support exit option considers whether the process has exited the pure-strategy supports of the starting distribution shares: if any player's population fraction leaves the support neighbourhood, the run stops.
Configures which players and player shares are displayed on the two- or three-dimensional distribution of share rates.
If the game has only two players, the z-axis player is set to None
.
If the game has more than two players, the z-axis player is set to the third player.
Note that an assortative typed game will override these to be incumbant on the x-axis, mutant on the y-axis.
Setting these to be the same population share will simply show a diagonal line.
The birds system has several ways of analysing games during runtime. These analyses depend on the running-mode. Each mode is visualised very differently; furthermore, each analysis visualisation may be exported for offline analysis.
Each analysis view has a subset of the following menu options.
.pdf, .png,
.eps, .ps, .gnuplot, or .latex).
PDF is best for printing;
EPS and PS are best for including in publications (note: use EPS for LaTeX inclusion);
PNG is best for web;
and finally, the raw format is best for customisation.
For distributions, the exported plot is a CDF or PDF depending on which option is selected for the current
graphical view.
This analysis window shows several different views for one-shot ergodic games. The one-shot window is roughly divided according to the visualisation type.
The long-term window shows population share statistics over the entire duration of the run. Note that this window will necessarily hide time-local information, as it works by way of repeatedly averaging shares as the simulation advances.
Mean population shares over spans of time. Note that this view is normalised to the range of shown population shares. As the simulation advances, physical graph sections show larger mean spans: shares are continuously averaged out. The population share view is created as follows:
Although complex, this method of data collection uses a fixed amount of memory.
Bar-graph of population share means: at each time t, accumulate strategy population shares, displaying this accumulated fraction over the current number of matches.
Graph a distribution of strategy population shares. This complements the mean population share. At each time t, increment a bucket linearly mapped from a strategy's population share fraction. Display each strategy's bucket contents, normalising the graph height to each strategy curve. The number of buckets is fixed at k = 100. For example, a player population share of 0.0 (no individuals with the given strategy) maps into bucket one, while 0.5 (half the player population using that strategy) maps into fifty.
Analyse population dynamics over the last k = 256 number of matches. This allows time-local analysis without averaging as the simulation advances.
Fast-running simulations will likely advance too quickly for this to be meaningful.
Fraction of population strategies over time. These are un-normalised and refer to the exact population strategy at the given time.
Displays game-play dynamics of individuals added and removed from the simulation. A line in the positive direction (blue colour) indicates a number of added individuals; negative direction (red colour) indicates removed. For the Moran process, for example, the positive and negative directions will be equal. If individuals are neither added nor removed, the line remains at zero.
A bar-graph view of population strategy shares at the current time. That is, given the population shares shows the last k = 256 shares at t - k, this shows populations at the current t.
Display the visitation of equilibria as configured. Visitation is defined as a count of time wherein all strategy shares are within a set neighbourhood of a defined coördinate vector (i.e., equilibrium).
Given the current time t and a strategy share's visitation count k at a given equilibrium, show
k/t for each equilibrium.
Times when shares are not in equilibrium are collected under the none
bar.
Thus, as the simulation advances, these bars will display the limit behaviour.
This complements the mean visitation by showing its distribution. At each time t, increment the current Visitation Rates in a bucket mapped linearly from the rate fraction. The number of buckets is fixed at k = 100. For example, a equilibrium share of 0.0 (no visitation to the equilibrium) maps into bucket one, while 0.5 (half the time spent in that equilibrium) maps into fifty.
Visualise match statistics of the process. This may be used to approximate the stationary distribution of the stochastic process. A match consists of the strategy profile used when players are matched up at each time t. Strategy profiles are labelled in reverse-player order, so given player one with strategies {a, b, c} and player two with {d, e, f}, this would show, e.g., d:a.
For each strategy profile, display the fraction of matches in this profile up to the current match.
Display the distribution of match fractions collected by incrementing a linearly-mapped bucket from match profile's fractions at each match. The number of buckets is fixed at k = 100. For example, a profile frequency of 0.0 (no matches playing that strategy profile) maps into bucket one, while 0.5 (playing this profile half of the time) maps into fifty. If a match is not taken, it is not incremented and thus does not factor into the distribution.
Show the population shares given in the configuration as a
two- or three-dimensional distribution heatmap
.
For example, given a configuration for players' first strategies, the vertical line at 40% of the x-axis shows the
average probability of player two's strategy shares given player one being at 40%.
The bucket values are normalised and mapped into the light spectrum (Bruton, 1996).
Three-dimensional visualisation has several parameters for tuning output.
The vector field, if selected, shows the difference between initial and ending population shares for the given players' shares. Thus, if starting from 50%/50% for the given strategy profiles, ending in 50%/25% would result in a left-pointing arrow.
Analysis of a multi-run simulation where individual expire at a certain count of matches, at which point statistics are collected and visualised. Then the simulation restarts.
When each run is terminated at time t, increment buckets linearly mapped from the current strategy shares. The number of buckets is fixed at k = 100. For example, a strategy share of 0.0 (no individuals playing that strategy) for a given player strategy might map into bucket one, while 0.5 (half a player population playing that strategy) might map into five (implying ten buckets). This view shows both the mean and the distribution itself.
At the time of each run termination, record the maximum norm of each equilibrium from the current strategy shares. Increment buckets linearly mapped from these maximum norms (in the unit interval, since it records differences of population shares). The number of buckets is fixed at k = 100. For example, given a strategy share profile exactly in equilibrium (maximum norm of 0.0), increment the first bucket. The maximum distance (1.0) increments the last bucket.
Note that this is not scaled to the maximum norm: if the maximum possible distance is 0.5 (say, with matching pennies), then the distance is not adjusted to fill the window.
Visualise match statistics at the end of each run. This may be used to approximate the stationary distribution of the stochastic process. A match consists of the strategy profile used when players are matched up at each time t. Strategy profiles are labelled in reverse-player order, so given player one with strategies {a, b, c} and player two with {d, e, f}, this would show, e.g., d:a.
For each strategy profile, display the average fraction of matches in this profile as recorded at the end of each run.
Display the distribution of match fractions collected by incrementing a linearly-mapped bucket from match profile's fractions at the end of each run. The number of buckets is fixed at k = 100. For example, a profile frequency of 0.0 (no matches playing that strategy profile) maps into bucket one, while 0.5 (playing this profile half of the time) maps into fifty. If a match is not taken, it is not incremented and thus does not factor into the distribution.
Show the population shares given in the configuration as a
two- or three-dimensional distribution heatmap
.
For example, given a configuration for players' first strategies, the vertical line at 40% of the x-axis shows the
probability of player two's strategy shares at the given time of simulation run exit given player one being at 40%.
The bucket values are normalised and mapped into the light spectrum (Bruton, 1996).
The vector field, if selected, shows the difference between initial and ending population shares for the given players' shares of a two-dimensional visualisation. Thus, if starting from 50%/50% for the given strategy profiles, ending in 50%/25% would result in a left-pointing arrow.
Three-dimensional visualisation has several parameters for tuning output:
Given the starting strategy distribution x̃ for player i and neighbourhood δ, stop each run at the time t when there exists a strategy share y ∈ x such that y > x̃ + δ or y < x̃ - δ. A run is also stopped if it exceeds the maximum possible time. Map these times t into buckets, where bucket size is a fraction of the maximum possible time to run games. Exit times exceeding the maximum time are accumulated into the last bucket. The number of buckets is fixed at k = 100. Display this as a PDF or CDF.
If you specified the first exit from the initial distribution pure-strategy support, stop when the strategy shares of any player i leave the pure-strategy support within a neighbourhood of δ.
If you specify a large maximum time and the exit times are very small, the granularity of the buckets may be too large to be meaningful. If you specify a small maximum time, the distributions will crowd the right-hand side of the graph.
The birds system uses double-precision floating-point numbers for all floating-pointer number
representations (double types).
Consult your operating system for number limits.
Non-decimal numbers are encoded as maximum-sized integers for growable fields (unsigned long long).
There is no protection within the system for number overrun, so extremely long-running simulation operators should take
care to note no obvious integer wrapping or floating-point overflow.
Randomness plays a key factor in the birds system.
To ensure high-quality random numbers at reasonable speed, we use the Mersenne twister (Saito and
Matsumoto, 2011).
To avoid modulo bias when computing random numbers over intervals, we use repeated draws with truncation (inspired by in
OpenBSD's arc4random_uniform() generator.
The random number generator is seeded in one of two ways.
On Linux systems, Bob Jenkins' hash function mixes seconds
since epoch, remainder microseconds since epoch, and the process identifier.
On systems with proper random number sources (e.g., BSD systems), the native arc4random function is used.
birds reads preset games from the resources directory
When starting up, birds will scan its resources directory (~/tmp/birds/share/birds for UNIX installations or the
Resources directory of the application bundle for Mac OS X) on starting up.
These are UTF-8 encoded XML files with the following structure:
<?xml version="1.0"?>
<birds name="gamename">
<matrix>
<players>
<player name="1" strategies="2">
<stratname>a</stratname>
<stratname>b</stratname>
</player>
<player name="2" strategies="2">
<stratname>c</stratname>
<stratname>d</stratname>
</player>
</players>
<strategies>
<strategy>
<payoff>1</payoff>
<payoff>2</payoff>
</strategy>
<strategy>
<payoff>3</payoff>
<payoff>4</payoff>
</strategy>
<strategy>
<payoff>5</payoff>
<payoff>6</payoff>
</strategy>
<strategy>
<payoff>7</payoff>
<payoff>8</payoff>
</strategy>
</strategies>
<equilibria>
<equilibrium>
<probability>0</probability>
<probability>1</probability>
<probability>0</probability>
<probability>1</probability>
</equilibrium>
</equilibria>
</matrix>
</birds>
This sample game gamename has two players (noted with the player tag), each with two
strategies each.
If we'd specified a sp attribute for the birds element, such as
sp="true", the game would register as a single-population game.
Note that the name attribute and stratname element for player nodes are
optional.
If unspecified, they'll revert to numeric identifiers (ordered from one).
Strategy profiles are laid out as follows (with a three-player game to complete the example):
| I-a | I-b | ||
|---|---|---|---|
| III-a | II-a | Strategy 1 | Strategy 2 |
| II-b | Strategy 3 | Strategy 4 | |
| III-b | II-a | Strategy 5 | Strategy 6 |
| II-b | Strategy 7 | Strategy 8 |
Equilibria follow the strategy profiles, with equilibrium profiles in equilibrium in player-first,
strategy-second order.
Evolutionary selection against dominated strategies, Journal of Economic Theory 71(2), 558–573, 1996. Online: pzp.hhs.se.
Homo Moralis-Preference evolution under incomplete information and assortative matching,TSE Working Papers 12–281, Toulouse School of Economics (TSE). Online: ideas.repec.org.
RGB Values for Visible Wavelengths. Online: www.physics.sfasu.edu.
Quantal Response Equilibria for Normal Form Games, Games and Economic Behavior 10: 6–38 (1995). DOI: 10.1006/game.1995.1023.
The birds utility is multi-threaded in the sense of working threads – the stochastic processes
themselves – is separate from the graphical shell.
(Ergodic simulations always have only one working thread.)
This allows the simulation to run almost continuously.
The update model is two-step to minimise locking: first, worker threads periodically update their warm buffers; second,
the graphical shell merges the warm buffers into a cold buffer.
This requires locking only when the worker threads update their buffers, then when the graphical shell updates its
buffer.
Thus, all graphical operations use the cold buffer and needn't lock.
The birds system was written by Kristaps Dzonsons, k-Consulting, for Jörgen Weibull, Stockholm School of Economics, with financial support from the Knut and Alice Wallenberg Research Foundation. For questions regarding the system, bug reports, patches, contributions, and so on, please contact Kristaps.