Saturday 30 March 2013

Concatenating and removing duplicates from two files

I'm posting this mainly to remind myself how to do this as I keep on forgetting (anyone with good *nix-foo won't learn anything here).

I've been running code for a long time gathering data for a paper I will one day perhaps have time to write. I analyse the csv file routinely thanks to a sleep command and everything is synced in a dropbox folder so if I'm bored I can take a look at this kind of graph every now and then:




(You can see that a particular measure for whatever I'm working on has arrived at steady state.)

Anyway! That's not the point.

The point is that at some point every now and then dropbox will get conflicted copies:


Concatenating (use cat)

First of all I need to gather those two csv files together:

cat Output_file_with_permute.csv Output_file_with_permute\ \(Vince\ Knight\'s\ conflicted\ copy\ 2013-03-06\).csv > fixed.csv

We can check that we do indeed have all the files together using grep -c . to count the number of rows in each file:

cat Output_file_with_permute.csv | grep -c .
cat Output_file_with_permute\ \(Vince\ Knight\'s\ conflicted\ copy\ 2013-03-06\).csv | grep -c .
cat fixed.csv | grep -c .

The output is shown (31499=9702+21798):




Now we need to make sure we don't have any duplicates in fixed.csv.

Removing duplicates

This is really simple using the sort and uniq commands:

sort fixed.csv | uniq > fixed_Output_file.csv

This sorts the file and using the uniq command to just output the unique ones.

If I count how many files are in the new file:

cat fixed_Output_file.csv | grep -c .

I get 21797 rows so it looks like the conflicted file didn't have any rows that the main file was missing.

I've used all this before when I had code running on multiple machines which obviously created a bunch of conflicted copies (because of how dropbox does things) with relevant data all over the place.

The final step is to simply clean all this up by removing the unwanted files:

mv fixed_Output_file.csv Output_file_with_permute.csvrm fixed.csv
rm Output_file_with_permute\ \(Vince\ Knight\'s\ conflicted\ copy\ 2013-03-06\).csv

As I said above the main reason I've written this post is to try and make sure I remember how to do this (I've had to google this everytime I need to do this)...

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)

Tuesday 5 March 2013

Game Theory Reading List

I've just finished putting the finishing touches to a course that I'm teaching with a flipped classroom approach which required me spending a fair amount of time putting together some screencasts and various other resources (the class website can be found here).

That's now done and the course is about to start. I'm more or less immediately starting to work on a course I'm teaching next academic year: a 3rd year undergraduate game theory course. I currently teach some basic game theory on our MSc course which just covers some normal form game stuff. I'm really looking forward to prepping and teaching this course.

I've actually compiled a list of 19 books but some of those I have on my kindle so here's a picture of some of the actual books:



To get started I thought I'd compile a list of books that could be of interest to the students. I have read a lot of these, flicked through some and am more or less aware of the existence of others. I thought I'd categorise some of these and might well at some part start reviewing them (similarly to my previous blog series which was ultimately inspired by +Theron Hitchman's series of posts reviewing differential geometry books). The 3 categories are:

  1. Helpful books to deal with the content of the course;
  2. Interesting books to delve in to further concepts from the course;
  3. Other cool books.
1. Helpful books to deal with the content of the course

The course is an introductory course to game theory looking at concepts such as normal form games, evolutionary game theory and games with incomplete information. Here's the books that I feel could prove helpful to students:

- "An Introduction to Game Theory" by Martin Osborne
- "A primer in Game Theory" by Robert Gibbons
- "Game Theory 101: The basics" by William Spaniel


2. Interesting books to delve in to further concepts from the course

Here are some books that could be of further interest to the student, perhaps considering a certain aspect of the course in detail and/or looking in to other things:

- "Selfish routing and the price of anarchy" by +Tim Roughgarden
- "Algorithmic Game Theory" by Noam Nissan, +Tim Roughgarden, Eva Tardos and Vijay Vazirani
- "Chases and escapes" by Nahin
- "Differential Games" by Isaacs
- "The stable marriage problem: structure and algorithms" by Gusfield and Irving
- "Game Theory Evolving" by Herbert Gintis
- "Games and information: An introduction to Game Theory" by Eric Rasmusen


3. Other cool books

Here are some books that don't necessarily fit with the course but are worth a read:

- "The complexity of cooperation" by Robert Axelrod
- "Rock paper scissor: game theory in everyday life" by Fisher
- "Game Theory: A non technical introduction" by Morton Davis
- "Theory of Games and Economic Behaviour" by von Neumann and Morgenstern


If there are any books that anyone thinks I have missed off this list please let me know!