Luong (Louie) Hoang

lhoang [at] mit [dot] edu



Game Theory Solver Academic Project

This is a solver for various types of games from Game Theory. The main purpose of the program is to solve for optimal strategies that each player can take, and to help visualize the overall structure of each game with flow diagrams, envelope diagrams, etc... Visualization work is done with OpenGL, both 2D and 3D diagrams are possible (where applicable). The application can solve or suggest solutions to some classes of zero-sum and non-zero-sum games. It can find optimal strategies, mixed strategies, equalizing strategies, envelope solutions and saddle points, etc... Here's an example screenshot of the flow diagram for Prisoners' Dilemma illustrating a dominant strategy equilibrium:

Prisoners' Dilemma Flow Diagram Prisoners' Dilemma flow diagram as a result of rational decisions

Flow diagram visualization works with almost any type of games as long as it's "visualizable" (i.e. < 3-person game). In 3D view, users can navigate around the model to see the complete graph. Here's a sample screenshot:

Flow Diagram for a 3-person Non-Zero-Sum Game Flow Diagram for a 3-person Non-Zero-Sum Game

Here's another screenshot of the lower envelope solution for a different 2-person zero-sum game where the first player wants to maximize his minimum expected payoffs:

Lower Envelope Solution Lower Envelope Solution for a 2-person zero-sum game

For easy reference, currently players' names are hardcoded as Rose and Colin (and Larry if there are 3 players). The program takes in a simple text file as input which describes the players' playoffs in the game and how many strategies each has. For example, a 2-person zero-sum game where the first player (Rose) has 2 strategies and the second (Colin) has 4 strategies would be entered in the following format:
2     4
1    -4     3     -6
2    -5     2     -2
Here if Rose chooses strategy 1 and Colin chooses strategy 2 then the payoff would be -4 to Rose (or 4 for Colin), and so on. Once the application completes, there will be an output file with more details on solutions or suggested solutions. Games where every player has more than 2 strategies are not currently "solvable" (unfortunately I haven't had time to make the extension).

To download the program (which should be compatible with most versions of Windows, although not yet tested in some), click here or here. Additionally, the source code is available on Github. For those who are interested in working with the code, there's a UML drawing of the framework named "Framework Design.jpg" in the repository which should help with understanding the overall structure. Additionally, the source code also contains a Dev-C++ project file, which is the original development environment that it was built in.