search

Socrats / EGTTools

Toolbox for Evolutionary Game Theory.
GNU General Public License v3.0
82 stars 19 forks source link
cpp evolutionary-dynamics evolutionary-game-theory python simulation social-dynamics

readme

EGTtools

Toolbox for Evolutionary Game Theory

PyPI version Documentation Status Build Join the chat at https://gitter.im/EGTTools/community Binder DOI

EGTtools provides a centralized repository with analytical and numerical methods to study/model game theoretical problems under the Evolutionary Game Theory (EGT) framework.

This library is composed of two parts:

The second typed is used in cases where the state space is too big to solve analytically, and thus require estimating the model parameters through monte-carlo simulations. The C++ implementation provides optimized computational methods that can run in parallel in a reasonable time, while Python bindings make the methods easily accecible to a larger range of researchers.

Table of Contents

  1. Requirements
  2. Downloading sources
  3. Examples of usage
  4. Documentation
  5. Caveats
  6. Citing
  7. Licence
  8. Acknowledgements

Requirements

To be able to install EGTtools, you must have:

Downloading sources

When cloning the repository you should also clone the submodules so that pybind11 is downloaded. You can do that by running:

git clone --recurse-submodules -j8 https://github.com/Socrats/EGTTools.git

Installation

With pip

You can install egttools directly from PyPi with:

pip install egttools

Currently, only the Linux build supports OpenMP parallelization for numerical simulations. This should normally be ok for most applications, since numerical simulations are heavy and should be run on High Power Computing (HPC) clusters which normally run Linux distributions.

We are investigating how to provide support for OpenMP in both Windows and Mac. In the meantime, if you really want to run numerical simulations on either of the two platforms, you should follow the compilation instructions below and try to link OpenMP for your platform yourself. Please, if you manage to do so, open an issue or a pull request with your solutions.

Note: For Apple M1 (arm64) you should install using pip install egttools --no-deps so that pip does not install the dependencies of the package. You should then install these dependencies through a virtual environment created with miniforge (see Caveats for more information on why this is necessary). Once you have miniforge installed you can do the following (assuming that you are in the base miniforge environment):

conda create -n egtenv python=3.9
conda activate egtenv
conda install numpy
conda install scipy
conda install matplotlib
conda install networkx
conda install seaborn

Build from source

To build egttools from source follow the following steps.

To install all required packages run:

python -m venv egttools-env
source egttools-env/bin/activate
pip install -r requirements.txt

Or with anaconda:

conda env create -f environment.yml
conda activate egttools-env

Also, to make your virtual environment visible to jupyter:

conda install ipykernel # or pip install ipykernel
python -m ipykernel install --user --name=egttools-env

You can build EGTtools in your virtual environment by running:

pip install build
cd <path>
python -m build

Where <path> represents the path to the EGTtools folder. If you are running this while inside the EGTtools folder, then <path> is simply ./.

Finally, you can install EGTtools in development mode, this will allow the installation to update with new modifications to the package:

python -m pip install -e <path>

If you don't want development mode, you can skip the option -e.

Examples of usage

The Analytical example is a jupyter notebook which analyses analytically the evolutionary dynamics in a (2-person, 2-actions, one-shot) Hawk-Dove game.

The Numerical example is a jupyter notebook which analyses through numerical simulations the evolutionary dynamics in a (2-person, 2-actions, one-shot) Hawk-Dove game.

The Invasion example is a jupyter notebook calculates the fixation probabilities and stationary distribution of a Normal Form Game with 5 strategies and then plots an invasion diagram.

The Plot 2 Simplex is a jupyter notebook that shows how to use EGTtools to plot the evolutionary dynamics in a 2 Simplex (a triangle), both for infinite and finite populations.

You can also check all these notebooks and a bit more on this tutorial repository

For example, assuming the following payoff matrix:

A=\begin{pmatrix} -0.5 & 2 \\ 0 & 0 \end{pmatrix}

You can plot the gradient of selection in a finite population of (Z=100) individuals and assuming and intensity of selection \beta=1 in the following way:

import numpy as np
from egttools.analytical import PairwiseComparison
from egttools.games import Matrix2PlayerGameHolder

beta = 1;
Z = 100;
nb_strategies = 2;
A = np.array([[-0.5, 2.], [0., 0.]])
pop_states = np.arange(0, Z + 1, 1)

game = Matrix2PlayerGameHolder(nb_strategies, payoff_matrix=A)

# Instantiate evolver and calculate gradient
evolver = PairwiseComparison(population_size=Z, game=game)
gradients = np.array([evolver.calculate_gradient_of_selection(beta, np.array([x, Z - x])) for x in range(Z + 1)])

Afterwards, you can plot the results with:

from egttools.plotting import plot_gradients

plot_gradients(gradients, figsize=(4, 4), fig_title="Hawk-Dove game stochastic dynamics",
               marker_facecolor='white',
               xlabel="frequency of hawks (k/Z)", marker="o", marker_size=20, marker_plot_freq=2)

Gradient of selection

And you can plot the stationary distribution for a mutation rate \mu=1eˆ{-3} with:

import matplotlib.pyplot as plt
from egttools.utils import calculate_stationary_distribution

transitions = evolver.calculate_transition_matrix(beta, mu=1e-3)
stationary_with_mu = calculate_stationary_distribution(transitions.transpose())
fig, ax = plt.subplots(figsize=(5, 4))
fig.patch.set_facecolor('white')
lines = ax.plot(np.arange(0, Z + 1) / Z, stationary_with_mu)
plt.setp(lines, linewidth=2.0)
ax.set_ylabel('stationary distribution', size=16)
ax.set_xlabel('$k/Z$', size=16)
ax.set_xlim(0, 1)
plt.show()

Stationary distribution

We can obtain the same results through numerical simulations. The error will depend on how many independent simulations you perform and for how long you let the simulation run. While a future implementation will offer an adaptive method to vary these parameters depending on the variations between the estimated distributions, for the moment it is important that you let the simulation run for enough generations after it has achieved a steady state. Here is a comparison between analytical and numerical results:

from egttools.numerical import PairwiseComparisonNumerical
from egttools.games import NormalFormGame

# Instantiate the game
game = NormalFormGame(1, A)
numerical_evolver = PairwiseComparisonNumerical(Z, game, 1000000)

# We do this for different betas
betas = np.logspace(-4, 1, 50)
stationary_points = []
# numerical simulations
for i in range(len(betas)):
    stationary_points.append(numerical_evolver.stationary_distribution(30, int(1e6), int(1e3),
                                                                       betas[i], 1e-3))
stationary_points = np.asarray(stationary_points)
# Now we estimate the probability of Cooperation for each possible state
state_frequencies = np.arange(0, Z + 1) / Z
coop_level = np.dot(state_frequencies, stationary_points.T)

Lastly, we plot the results:

from sklearn.metrics import mean_squared_error

mse = mean_squared_error(1 - coop_level_analytical, coop_level)

# Finally, we plot and compare visually (and check how much error we get)
fig, ax = plt.subplots(figsize=(7, 5))
# ax.scatter(betas, coop_level, label="simulation")
ax.scatter(betas, coop_level_analytical, marker='x', label="analytical")
ax.scatter(betas, coop_level, marker='o', label="simulation")
ax.text(0.01, 0.535, 'MSE = {0:.3e}'.format(mse), style='italic',
        bbox={'facecolor': 'red', 'alpha': 0.5, 'pad': 10})
ax.legend()
ax.set_xlabel(r'$\beta$', fontsize=15)
ax.set_ylabel('Cooperation level', fontsize=15)
ax.set_xscale('log')
plt.show()

Comparison numerical analytical

Finally, you may also visualize the result of independent simulations:

init_states = np.random.randint(0, Z + 1, size=10, dtype=np.uint64)
output = []
for i in range(10):
    output.append(evolver.run(int(1e6), 1, 1e-3,
                              [init_states[i], Z - init_states[i]]))
# Plot each year's time series in its own facet
fig, ax = plt.subplots(figsize=(5, 4))

for run in output:
    ax.plot(run[:, 0] / Z, color='gray', linewidth=.1, alpha=0.6)
ax.set_ylabel('k/Z')
ax.set_xlabel('generation')
ax.set_xscale('log')

Comparison numerical analytical

Plotting the dynamics in a 2 Simplex

EGTtools can also be used to visualize the evolutionary dynamics in a 2 Simplex. In the example bellow, we use the egttools.plotting.plot_replicator_dynamics_in_simplex which calculates the gradients on a simplex given an initial payoff matrix and returns a egttools.plotting.Simplex2D object which can be used to plot the 2 Simplex.

import numpy as np
import matplotlib.pyplot as plt
from egttools.plotting import plot_replicator_dynamics_in_simplex

payoffs = np.array([[1, 0, 0],
                    [0, 2, 0],
                    [0, 0, 3]])
type_labels = ['A', 'B', 'C']

fig, ax = plt.subplots(figsize=(10, 8))

simplex, gradient_function, roots, roots_xy, stability = plot_replicator_dynamics_in_simplex(payoffs, ax=ax)

plot = (simplex.add_axis(ax=ax)
        .draw_triangle()
        .draw_gradients(zorder=0)
        .add_colorbar()
        .add_vertex_labels(type_labels)
        .draw_stationary_points(roots_xy, stability)
        .draw_trajectory_from_roots(gradient_function,
                                    roots,
                                    stability,
                                    trajectory_length=15,
                                    linewidth=1,
                                    step=0.01,
                                    color='k', draw_arrow=True,
                                    arrowdirection='right',
                                    arrowsize=30, zorder=4, arrowstyle='fancy')
        .draw_scatter_shadow(gradient_function, 300, color='gray', marker='.', s=0.1, zorder=0)
        )

ax.axis('off')
ax.set_aspect('equal')

plt.xlim((-.05, 1.05))
plt.ylim((-.02, simplex.top_corner + 0.05))
plt.show()

2 Simplex dynamics in infinite populations

The same can be done for finite populations, with the added possibility to plot the stationary distribution inside the triangle (see simplex plotting and simplified simplex plotting for a more in depth examples).

Documentation

The analytical module contains classes and functions that you may use to investigate the evolutionary dynamics in N-player games. For now only the replicator dynamics (for infinite populations) and the Pairwise Comparison imitation process (for finite populations) are implemented.

When your state-space is too big (in finite populations), it might become computationally hard to solve the system analytically. Thus, we provide an efficient numerical module written in C++ and compiled to Python. You may use it to estimate the fixation probabilities and stationary distribution through Monte-Carlo simulations, or perform individual runs of the Moran process.

You can find more information in the ReadTheDocs documentation.

Caveats

  1. On Apple M1 (arm64) you should install (for the moment) miniforge, create a conda environment using it, and install EGTtools from the conda environment.

  2. In MacOSX it is assumed that you have Homebrew installed.

  3. You should install libomp with homebrew brew install libomp if you want to have support for parallel operations ( there is a big difference in computation time).

  4. You must have Eigen 3.3.* installed.

  5. You do not need any of the above if you install EGTtools through pip install egttools --no-deps. However, on Apple M1 (arm64) you still need to install the dependencies through miniforge, since only there you can find a scipy wheel that supports this architecture.

Citing

If you use EGTtools in your publications, please cite it in the following way with bibtex:

@article{Fernandez2023,
  author = {Fernández Domingos, Elias and Santos, Francisco C. and Lenaerts, Tom},
  title = {EGTtools: Evolutionary game dynamics in Python},
  journal = {iScience},
  volume = {26},
  number = {4},
  pages = {106419},
  year = {2023},
  issn = {2589-0042},
  doi = {https://doi.org/10.1016/j.isci.2023.106419}
}

Or in text format:

Fernández Domingos, E., Santos, F. C. & Lenaerts, T. EGTtools: Evolutionary game dynamics in Python. iScience 26, 106419 (2023).

And to cite the current version of EGTtools you can use:

@misc{Fernandez2020,
  author = {Fernández Domingos, Elias},
  title = {EGTTools: Toolbox for Evolutionary Game Theory (0.1.12)},
  year = {2022},
  month = {Dec},
  journal = {Zenodo},
  doi = {10.5281/zenodo.7458631}
}

Moreover, you may find our article at here.

Licence

Acknowledgements