Sunday, 24 March 2013

Open Source and/or Free Game Theory Software

Last week I posted some python code I've been putting together:
  • The github repo is here
  • A website with user guide and some videos is here
The code is currently a collection of 4 tools that can solve 4 type of game theoretical problems:
  • Shap.py which calculate the shapley value in a cooperative game;
  • Gale_Shapley.py an implementation of the extended Gale Shapley algorithm for matching games;
  • lrs_nash.py a (clumsy) python wrapper for the lrs library which can be used to solve normal form games. (If anyone wants to contribute to how I speak to the c library please do! - I sadly know pretty much no c yet...)
  • Abm.py which can be used to carry out agent based models of normal form games (to see emergent behaviour).
Here's a screencast demonstrating that last program:


The point of this blog post is to list some of the other pieces of software available that can be used in Game Theory.

List of game theory tools


  1. The lrs library
What it does: This is a self-contained ANSI C implementation as a callable library of the reverse search algorithm for vertex enumeration/convex hull problems and comes with a choice of three arithmetic packages. Basically it's a really smart package that does a lot of things. One of those things is solving normal form games.

Ease of use: Pretty straight forward on a *nix machine. Download a tar file and make the contents of the unpack directory. To use the package you simply pass it a couple of text files as arguments.
  1. The banach.lse.ac.uk/ website.
What it does: This is actually just an online interface making use of the above mentioned lrs library to solve normal form games.

Ease of use: Very very easy. Just point and click and enter in your normal form game.
As far as I can tell that website was put together by +Rahul Savani who is actually connected to the next item on this list.
  1. The Gambit library
What it does: As a disclaimer I haven't actually used Gambit yet. Here's the blurb from the website: Gambit is a library of game theory software and tools for the construction and analysis of finite extensive and strategic games. Gambit is designed to be portable across platforms, and runs on Linux, Mac OS X, and Windows. Reading through the website it looks like it can be used to solve normal and extensive form games. Development seems fairly active with various suggestions (including an implementation of the lrs library) for contributions. It basically looks like a C++ library with a nice GUI also available.

Ease of use: Can't say :) When I get a moment I'm sure I'll try it out...
  1. My Sage interact for 2 by 2 games
What it does: If you're not familiar with +Sage Mathematical Software System I can't recommend it enough. It's an open source mathematics package (Maple, Mathematica etc). It's a very powerful package with a very active community of developers and users. One of the neat tools is the interact website which lets you put up small bits of code online for anyone to use. This is one of those small bits of code that can be used to solve any 2 by 2 game ("any" is a bit of a lie as someone has pointed out that it crashes for some sets of inputs). It's very basic and solves the game algebraically. I actually put this together as a teaching tool (interacts are great for that) and here's the screencast I shared with my students:



Ease of use: Pretty easy, it's again a simple point and click interface available in a browser but it is very limited: it just solves 2 by 2 games.
  1. William Spaniel's calculator
What it does: I've only played with this for a couple of minutes so I won't comment too much but it looks like a solver implemented in VBA for excel for 2 by 2 games. It also looks at the repeated game aspect a bit looking at whether or not a game is a Prisoners Dilemma and what discount factor would be needed to induce cooperation in an infinitely repeated game context.

Ease of use: On a personal level I don't really like opening up an excel file unless I have to (as it usually starts up the various updates and what not) and this also won't run on linux (unless using wine etc...). Having said that it does do what it says on the tin. The VBA seems to be nicely written so that all the results are just shown immediately without the need to run any macros.
  1. My Sage interact for the Shapley value
What it does: This is another code snippet on the +Sage Mathematical Software System interact site which I wrote to accompany a screencast I did for my students showing how to calculate the Shapley value for a cooperative game (note that there's a small error at 3:51):


Ease of use: This is again pretty easy to use. It's a point and click interface in a web browser where one simply says how many players are in the game as well as the characteristic function.
  1. The Gametheory.net list
A list of (mainly Java) programs. Mostly normal form games (some of which are constrained to zero sum games). I haven't tried many of these but I'll mention this one which is written in javascript and lets you play (and find equilibria) for zero sum games of size up to 5 by 5.
  1. Some github repos
A quick search seems to identify two repos on github that are connected to game theory (I restricted my search to python):
Both these repos seem concerned with normal form games but I have not used them.

Conclusions


There is a fair bit of stuff out there for solving normal form games (and the screenshots of Gambit's GUI seem to show a nice ability to handle extensive form games). For larger scale games it seems that something that makes use of the lrs library is the best bet. There does not seem to be much in the form of agent based models and/or other type of games (such as the Gale Shapley algorithm or code to handle the calculation of the Shapley value in cooperative games apart from my humble contributions). In the gametheory.net list there is broken link to something that supposedly would calculate voting indices.

Everything that is out there is pretty easy to use though and there's a lot of open source stuff that people could contribute to :)

On a personal level I'm hoping to continue to develop my packages and I would really like to implement them in +Sage Mathematical Software System at some point if only to have them available as a great and easy to access teaching tool.

I'm sure I must have missed some so I apologise for that (and would love to know about them).

(Here's another game theory related list: A reading list)