I want to compute a mixed strategy that will be the Nash Equilibrium of the game. I have used my knowledge in order to create the system for the mixed strategy. I concluded on a system with 3 variables and 5 constrains.I am not able to solve this system using the common Gaussian Elimination method.This system is a linear program from what I can imagine.I have searched google for similar examples but all the examples was on 2-player games with only 2 strategies per player.In those games was quite easy to compute the mixed strategy.I am thinking of using the simplex method for finding the NE but I am thinking that this is weird for such a small game... Are there simpler method that can be used in computing a NE profile? Thank you.
We have developed a user-friendly browser-based system to input and solve 2-player strategic-form and extensive-form games:
Currently, we support:
finding all equilibria via polyhedral vertex enumeration (which works on the strategic-form representation, which is converted to in the case of extensive-form games; this uses David Avis' lrs http://cgm.cs.mcgill.ca/~avis/C/lrs.htmlW); and
finding one equilibrium using Lemke's algorithm (which works on the strategic-form representation or on the sequence-form representation for extensive-form games).
You can use lrs separately offline to solve larger bimatrix games.
The GTE project is under active development (supported by the Google Summer of Code in 2011, 2012, and 2014), so please provide feedback and/or let us know if you would like to contribute) at
For a paper that covers the basic theory and a number of methods for enumeration of equilibria, see
D. Avis, G. Rosenberg, R. Savani , and B. von Stengel (2010). Enumeration of Nash Equilibria for Two-Player Games. Economic Theory 42, 9-37.
For a paper that describes GTE and what it can do, see
R. Savani and B. von Stengel (2014). Game Theory Explorer - Software for the Applied Game Theorist. Computational Management Science, 29 pages, to appear. arXiv version
Zouzias' answer gives a good description of how to use support enumeration, which works fine for small examples. The methods in the paper above and used in GTE will in general be much quicker than support enumeration for finding extreme equilibria. In addition, GTE will find the complete set of equilibria (which can include convex combinations of extreme equilibria) by finding maximal cliques in a bipartite graph.
As far as I remember there is a simple exponential time algorithm for computing a Nash Equilibrium (NE) for 2 player games.
- Guess the support of the NE mixed strategy for each player.
- Assuming that you know the support, you now have to compute the weights of selecting each pure strategy. This can be written down as a system of linear equations, which can be solved efficiently. More precisely, the system of linear equations encodes the constraints of a mixed strategy being a NE (i.e., each strategy on its support is best response, sums up to one, etc).
This algorithm can be programmed quite easily assuming access to a linear solver.