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.
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ The general question is hard, see for example the following paper and its references: 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. $\endgroup$– Yuval FilmusOct 12, 2012 at 18:16
-
3$\begingroup$ 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. $\endgroup$– Peter ShorOct 12, 2012 at 18:20
-
$\begingroup$ 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. $\endgroup$– nikosdiOct 12, 2012 at 18:31
-
7$\begingroup$ 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. $\endgroup$– Peter ShorOct 12, 2012 at 20:43
-
1$\begingroup$ @Peter Criss-cross? I always wondered whether it is actually used (and what exactly does it do). $\endgroup$– Yuval FilmusOct 14, 2012 at 2:37
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
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. 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.
$\begingroup$
$\endgroup$
2
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.
-
1$\begingroup$ 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. $\endgroup$– GMBMar 17, 2014 at 7:32
-
$\begingroup$ 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. $\endgroup$– GMBMar 17, 2014 at 7:38