Overview

This project contains Haskell implementations of the two algorithms described in the paper "Simple Search Methods for Find a Nash Equilibrium", by Ryan Porter, Eugene Nudelman, and Yoav Shoham.

Note that these are NOT the implementations that produced the experimental results described in that paper. Those, sadly, have been lost to the sands of time. These implementations are similar, but slower, probably because the author is (as of this writing) less skilled at Haskell than at C++.

Implementation

This project is setup as a Haskell Cabal package.

It makes use of several libraries that I found to extremely useful:

• Parsec for parsing
• QuickCheck for testing
• levmar, which provides a Haskell interface to a C implementation of the Levenberg-Marquardt optimization algorithm
• hmatrix-glpk, which provides a Haskell interface to linear programming functions provided by GLPK.

Status

2010-05-15: The two-player solver seems robust, and the n-player solver works on most games. However, it sometimes fails to find an equilibrium. The most common symptom is a "SmallGradient" result from levmar library, but I do not know the underlying cause. Two examples of problematic games are in the example-games directory (called "BadGame1.game" and "BadGame2.game").

Notes

The code has only been tested using GHC on Ubuntu.

Please contact Ryan W. Porter with any feedback. Since a primary motivation for creating this project was to explore Haskell, I would particularly appreciate any Haskell-specific feedback.