Permalink
Fetching contributors…
Cannot retrieve contributors at this time
138 lines (116 sloc) 5.44 KB
title tags authors affiliations date bibliography
Nashpy: A Python library for the computation of Nash equilibria
Python
mathematics
economics
computer science
game theory
equilbrium
name orcid affiliation
Vincent Knight
0000-0002-4245-0638
1
name orcid affiliation
James Campbell
0000-0003-1100-1765
1
name index
Cardiff University, School of Mathematics, UK
1
13 August 2018
paper.bib

Summary

Game theory is the study of strategic interactions where the outcomes of choice depend on the choices of all participants. A key solution concept in the field is that of Nash Equilibrium [@nash1950equilibrium]. This solution concept corresponds to a coordinate at which no participant has any incentive to change their choice.

As an example, consider the game of Rock Paper Scissors which can be represented mathematically using the following matrix:

$$ A= \begin{pmatrix} 0 & -1 & 1 \ 1 & 0 & -1 \ -1 & 1 & 0 \ \end{pmatrix} $$

The rows and columns correspond to the actions available: Rock, Paper and Scissors. A value of 1 indicates that that specific row beats the corresponding column and similarly a value of -1 indicates a loss and a 0 indicates a tie. For example (A_{21}) shows that Paper (the second action) beats Rock (the first action. Using Nashpy the equilibrium behaviour can be computed:

>>> import nashpy as nash
>>> import numpy as np
>>> A = np.array([[0, -1, 1], [1, 0, -1], [-1, 1, 0]])
>>> game = nash.Game(A)
>>> for eq in game.support_enumeration():
...     print(eq)
(array([ 0.33...,  0.33...,  0.33...]), array([ 0.33...,  0.33...,  0.33...]))

As expected: both players should play each action randomly (each with probability 1/3).

Computing this equilibria for large games, situations where individuals have many strategic options available to them requires the use of software implementations of known algorithms. A number of algorithms exist to compute these Nash equilibria, for example the Lemke-Howson algorithm [@lemke1964equilibrium].

Statement of need

Access to these algorithms is non trival, an example of this includes the modelling of healthcare decisions [@knight2017measuring] where a bespoke theoretic result was used to design a specific algorithm for the computation of equilibria. Easily accessibly software would make that research more straightforward as no new algorithm would need to be implemented.

The most mature piece of software available for the computation of equilibria is Gambit [@mckelvey2006gambit]. Gambit includes a python wrapper to its core C functionality however is not currently portable for example Windows is not supported. There does exist a web interface with a Gambit back end: Game theory explorer however this is not practical for reproducible research.

Nashpy is a Python library with all dependencies being part of the standard scientific Python stack (numpy and scipy [@scipy]) thus it is portable. For example Windows support is regularly tested through a Windows continuous integration service (Appveyor).

Nashpy currently implements 3 algorithms for the computation of equilibria (currently only for 2 player games) and is extensively documented, including theoretic reference material on the algorithms: nashpy.readthedocs.io. Furthermore, the software is automatically tested using a combination of doc (this paper is also tested), unit, integration and property based tests with 100% coverage.

There are potential limitations associated with Nashpy, these are due to the complexity of the algorithms themselves. For example, support enumeration enumerates all potential pairs of strategy. For $n\times n$ sized square matrices it has complexity of the order of $\mathcal{O}\left({2^n}^2\right)$. All implementations provided in Nashpy ensure these effects are reduced: numpy [@scipy] provides C based implementations for vectorized performance. Furthermore, all algorithms are generators which ensures that not all equilibria must be found before one is returned. For example, below an 11 by 11 game is considered and timings computed are shown for relative comparison. Using the more efficient Lemke-Howson algorithm [@lemke1964equilibrium] an equilibrium is found approximately 3000 times faster.

>>> from pprint import pprint
>>> A = np.eye(11)
>>> game = nash.Game(A, A[::-1])
>>> pprint(next(game.support_enumeration()))  # 2.26 s ± 118 ms per loop
(array([ 0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.]),
 array([ 0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.]))
>>> pprint(next(game.lemke_howson_enumeration()))  # 734 µs ± 5.27 µs per loop
(array([ 0.5,  0. ,  0. ,  0. ,  0. ,  0. ,  0. ,  0. ,  0. ,  0. ,  0.5]),
 array([ 0.5,  0. ,  0. ,  0. ,  0. ,  0. ,  0. ,  0. ,  0. ,  0. ,  0.5]))

Nashpy is designed to be used by researchers but also students in courses in the fields of mathematics, computer science and/or economics. It is already currently being used in a final year course at Cardiff University. Due to the fact that the code is written entirely in Python and is open source, this makes it a positive teaching tool as students can read and understand implementation of the algorithms. Nashpy has been archived to Zenodo with the linked DOI: [@zenodo].

Acknowledgements

We acknowledge code contributions from Ria Baldevia as well as many helpful discussions with Nikoleta Glynatsi.

References