<p>We have developed a user-friendly browser-based system to input and solve 2-player strategic-form and extensive-form games:</p>

<p><a href="http://www.gametheoryexplorer.org/" rel="nofollow">http://www.gametheoryexplorer.org/</a> (GTE)</p>

<p>Currently, we support:</p>

<ul>
<li><p>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 <a href="http://cgm.cs.mcgill.ca/~avis/C/lrs.htmlW" rel="nofollow">http://cgm.cs.mcgill.ca/~avis/C/lrs.htmlW</a>); and</p></li>
<li><p>finding one equilibrium using Lemke's algorithm (which works on the strategic-form representation or on the sequence-form representation for extensive-form games).</p></li>
</ul>

<p>You can use lrs separately offline to solve larger bimatrix games.</p>

<p>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</p>

<p>gte@nash.lse.ac.uk</p>

<p>For a paper that covers the basic theory and a number of methods for enumeration of equilibria, see </p>

<p>D. Avis, G. Rosenberg, R. Savani , and B. von Stengel (2010).
<a href="http://cgi.csc.liv.ac.uk/~rahul/papers/avisetal.pdf" rel="nofollow" title="Enumeration of Nash Equilibria for Two-Player Games">Enumeration of Nash Equilibria for Two-Player Games</a>.
Economic Theory 42, 9-37.</p>

<p>For a paper that describes GTE and what it can do, see</p>

<p>R. Savani and B. von Stengel (2014).
<a href="http://www.maths.lse.ac.uk/Personal/stengel/TEXTE/largeongte.pdf" rel="nofollow">Game Theory Explorer - Software for the Applied Game Theorist</a>.
Computational Management Science, 29 pages, to appear. <a href="http://arxiv.org/abs/1403.3969" rel="nofollow">arXiv version</a></p>

<p>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.</p>

CC BY-SA 3.0
2014-03-15T20:04:46.753Z
2014-03-18T07:00:53.363Z
2014-03-18T07:00:53.363Z
Rahul Savani
<p>As far as I remember there is a simple exponential time algorithm for computing  a Nash Equilibrium (NE) for 2 player games.</p>

<ol>
<li>Guess the support of the NE mixed strategy for each player.</li>
<li>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).</li>
</ol>

<p>This algorithm can be programmed quite easily assuming access to a linear solver.</p>

CC BY-SA 3.0
2014-03-17T07:32:00.867Z
To be more specific about the system of linear equations: if $P$ is the *other* player's payoff matrix, then a player's equilibrium action profile is $P_S^{-1} \cdot \langle 1, \dots, 1 \rangle^T$ (normalized) on the chosen support set and $0$ off it (in this equation, $P_S$ denotes the principal submatrix of $P$ gained by keeping only the rows and columns chosen in the support set $S$).  It's also worth mentioning that you may assume that the two players have equal support size.
GMB
CC BY-SA 3.0
2014-03-17T07:38:47.577Z
Also, that equation might fail if the equilibrium value is $0$ (because $P_S$ will be singular).  You can dodge this problem by adding $1$ to each entry of $P$, which won't change the equilibrium action profiles.
GMB
CC BY-SA 3.0
2014-03-16T19:54:46.437Z
2014-03-16T19:54:46.437Z
Zouzias
<p>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.  </p>

CC BY-SA 3.0
2012-12-28T08:32:54.723Z
You can use the following web-based software to enumerate all equilibria of general bimatrix games, which includes zero-sum games: http://banach.lse.ac.uk/.
Rahul Savani
CC BY-SA 3.0
2012-10-12T18:16:50.937Z
The general question is hard, see for example the following paper and its references: http://arxiv.org/abs/1104.3760. Your problem has very small numbers, so it might be solvable after all, perhaps with more computational effort than what you'd expect.
Yuval Filmus
CC BY-SA 3.0
2012-10-12T18:20:33.113Z
Did you mean linear program? That's what it sounds like when you say "system with 3 variables and 5 constraints". If it's a zero-sum game, computing the mixed strategy equilibrium is easy, and can be done with the simplex method and linear programming. If it's not a zero-sum game, computing the Nash Equilibrium, is in general hard, but should be possible with such small numbers. You haven't given us enough information to be able to answer your question properly.
Peter Shor 
CC BY-SA 3.0
2012-10-12T18:31:48.220Z
Yes I have a linear program and I am trying to find a way to calculate the mixed strategy without using the simplex method.I tried to look for dominant strategies to make the problem smaller but I am not able.The game is a 3x3 game but it is not a zero sum game.
nikosdi
CC BY-SA 3.0
2012-10-12T20:43:16.133Z
If general linear programs were solvable by some easy method that wasn't the simplex method instead of the simplex method, everybody would be using it. For a 3x3, you might be able to simplify it by inspection (as you are trying to do), but you also might not.
Peter Shor 
CC BY-SA 3.0
2012-10-14T02:37:43.347Z
@Peter Criss-cross? I always wondered whether it is actually used (and what exactly does it do).
Yuval Filmus
CC BY-SA 3.0
2012-10-15T21:36:02.320Z
Ok I have found out that we haven't cover this topics on our lectures.I understood that if I can't make my problem smaller (e.g dominant strategies) it is very difficult to find a Nash Equilibrium.It is better if i delete the question?
nikosdi
<linear-programming><gt.game-theory>
Compute Nash Equilibrium for 2-player games
nikosdi
# Compute Nash Equilibrium for 2-player games

(Asked by: username_0 on 2012-10-12)

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.

**Tags:** linear-programming, gt.game-theory
> **Comments:**
> **username_2**: The general question is hard, see for example the following paper and its references: http://arxiv.org/abs/1104.3760. Your problem has very small numbers, so it might be solvable after all, perhaps with more computational effort than what you'd expect.  
> **username_3**: Did you mean linear program? That's what it sounds like when you say "system with 3 variables and 5 constraints". If it's a zero-sum game, computing the mixed strategy equilibrium is easy, and can be done with the simplex method and linear programming. If it's not a zero-sum game, computing the Nash Equilibrium, is in general hard, but should be possible with such small numbers. You haven't given us enough information to be able to answer your question properly.  
> **username_0**: Yes I have a linear program and I am trying to find a way to calculate the mixed strategy without using the simplex method.I tried to look for dominant strategies to make the problem smaller but I am not able.The game is a 3x3 game but it is not a zero sum game.  
> **username_3**: If general linear programs were solvable by some easy method that wasn't the simplex method instead of the simplex method, everybody would be using it. For a 3x3, you might be able to simplify it by inspection (as you are trying to do), but you also might not.  
> **username_2**: @Peter Criss-cross? I always wondered whether it is actually used (and what exactly does it do).  
> **username_0**: Ok I have found out that we haven't cover this topics on our lectures.I understood that if I can't make my problem smaller (e.g dominant strategies) it is very difficult to find a Nash Equilibrium.It is better if i delete the question?  
> **username_1**: You can use the following web-based software to enumerate all equilibria of general bimatrix games, which includes zero-sum games: http://banach.lse.ac.uk/.  

---

## 2 answers

### Answer by username_1 on 2014-03-15. Score: 7 | Accepted answer

We have developed a user-friendly browser-based system to input and solve 2-player strategic-form and extensive-form games:

<http://www.gametheoryexplorer.org/> (GTE)

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

gte@nash.lse.ac.uk

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](http://cgi.csc.liv.ac.uk/~rahul/papers/avisetal.pdf "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](http://www.maths.lse.ac.uk/Personal/stengel/TEXTE/largeongte.pdf).
Computational Management Science, 29 pages, to appear. [arXiv version](http://arxiv.org/abs/1403.3969)

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.


---

### Answer by username_4 on 2014-03-16. Score: 2

As far as I remember there is a simple exponential time algorithm for computing a Nash Equilibrium (NE) for 2 player games.

1. Guess the support of the NE mixed strategy for each player.
2. 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.

> **Comments:**
> **username_5**: To be more specific about the system of linear equations: if $P$ is the *other* player's payoff matrix, then a player's equilibrium action profile is $P_S^{-1} \cdot \langle 1, \dots, 1 \rangle^T$ (normalized) on the chosen support set and $0$ off it (in this equation, $P_S$ denotes the principal submatrix of $P$ gained by keeping only the rows and columns chosen in the support set $S$).  It's also worth mentioning that you may assume that the two players have equal support size.  
> **username_5**: Also, that equation might fail if the equilibrium value is $0$ (because $P_S$ will be singular).  You can dodge this problem by adding $1$ to each entry of $P$, which won't change the equilibrium action profiles.  

---

