Computational Game Theory in Sagemath

2015-07-27

Speakers

• Hannah Lorrimore, Cardiff University

• James Campbell, Cardiff University

• Tobenna P. Igwe, University of Liverpool, (Google Summer of Code)

• Vincent Knight, Cardiff University

Abstract

Game Theory is the study of rational interaction and is getting increasingly important in CS. Ability to quickly compute a solution concept for a nontrivial (non-)cooperative game helps a lot in practical and theoretic work, as well as in teaching. This talk will describe and demonstrate the game theoretic capabilities of Sagemath (http://www.sagemath.org/), a Python library, described as having the following mission: 'Creating a viable free opensource alternative to Magma, Maple, Mathematica and Matlab'.

The talk will describe algorithms and classes that are implemented for the computation of Nash equilibria in bimatrix games. These include:

• A support enumeration algorithm;

• A reverse search algorithm through the lrs library;

• The Lemke-Howson algorithm using the Gambit library (https://github.com/gambitproject/gambit).

In addition to this, demonstrations of further capabilities that are actively being developed will also be given:

• Tests for degeneracy in games;

• A class for extensive form games which include the use of the graph theoretic capabilities of Sage.

The following two developments which are being carried out as part of a Google Summer of Code project will also be demonstrated:

• An implementation of the Lemke-Howson algorithm;

• Extensions to N player games;

Demonstrations will use the (free) online tool cloud.sagemath which allows anyone with connectivity to use Sage (and solve game theoretic problems!). Cloud.sagemath also serves as a great teaching and research tool with access to not only Sage but Jupyter (Ipython) notebooks, R, LaTeX and a variety of other software tools.

The talk will concentrate on strategic non-cooperative games but matching games and characteristic function games will also be briefly discussed.