3
$\begingroup$

I've been attempting to teach myself some game theory and in the process, some linear programming.

While muddling through this, I've been attempting to use a variety of simplex methods to attempt to find mixed-strategy Nash equilibria in zero-sum games.

Unfortunately, most of my computations end up with incomplete, or seemingly wrong answers.

Is the simplex method (or two-phase, or dual simplex) appropriate for attempting to find mixed-strategy Nash equilibria, and if so, what is the proper way to set up the starting tableaux?

I've attempting starting with something like this (example is RPS):

\begin{bmatrix}0 & 0 & 0 & -1 & -1 & 0\\1 & 1 & 1 & 0 & 1 & 1\\0.5 & 0 & 1 & 1 & 0 & 0.5\\1 & 0.5 & 0 & 1 & 0 & 0.5\\0 & 1 & 0.5 & 1 & 0 & 0.5\end{bmatrix}

or

\begin{bmatrix}0 & 0 & 0 & -1 & -1 & -1 & -1 & 0\\1 & 1 & 1 & 1 & 0 & 0 & 0 & 1\\0.5 & 0 & 1 & 0 & 1 & 0 &0 & 0.5\\1 & 0.5 & 0 & 0 & 0 & 1 & 0 & 0.5\\0 & 1 & 0.5 & 0 & 0 & 0 & 1 & 0.5\end{bmatrix}

or

\begin{bmatrix}0 & 0 & 0 & 0 & -1 & -1 & -1 & 0\\0 & 0 & 0 & -1 & 0 & 0 & 0 & 0\\1 & 1 & 1 & 1 & 0 & 0 & 0 & 1\\0.5 & 0 & 1 & 0 & 1 & 0 &0 & 0.5\\1 & 0.5 & 0 & 0 & 0 & 1 & 0 & 0.5\\0 & 1 & 0.5 & 0 & 0 & 0 & 1 & 0.5\end{bmatrix}

And this seems simple enough to solve, but anything more complex, or examples with dominated strategies often seem to be unsolveable.

$\endgroup$
1
$\begingroup$

Do you mean in finite games? If so, since otherwise it is hopeless, as far as I understand computing all equilibria is a hard problem. There is couple of good surveys here and here, recent handbook chapter and you might be interested in Gambit..

$\endgroup$
  • $\begingroup$ As I understand it, yes I am solely looking at finite games. Simple selection strategies like RPS or fighting game character selections based on matchup win rates. $\endgroup$ – Bryan O'Malley Feb 3 '17 at 1:57
  • $\begingroup$ I've seen a couple of those linked articles before. Most mention the Lemke-Howson algorithm. That seems to be the standard, however I approached this with the simplex algorithm first as it seemed simpler to learn and apply. To the point of my question - is there a way to apply the simplex method to these sorts of problems (if so, what?), or should I just move on and begin learning Lemke-Howson? $\endgroup$ – Bryan O'Malley Feb 3 '17 at 2:00
  • $\begingroup$ I never thought about using simplex method in this context. To derive what, the best response? Then I guess you probably can. But I am not an expert here. On the other hand if some method is recurring in the literature, there is probably a reason for it. $\endgroup$ – Jan Feb 3 '17 at 2:14
  • $\begingroup$ I recommend looking at Dorfman, Samuelson and Solow, Linear Programming and Economic Analysis (also known as DOSSO). Chapter 16 is Interrelations between Linear Programming and Game Theory and tells how to convert games into linear programming problems, and vice versa. $\endgroup$ – Trurl Feb 3 '17 at 22:20
  • $\begingroup$ This book? amazon.com/Programming-Economic-Analysis-Computer-Science/dp/… $\endgroup$ – Bryan O'Malley Feb 4 '17 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.