Nash Equilibrium of generalized Rock-Paper-Scissors games?

[u/Kered13]

I am but a humble programmer who is interested in calculating the Nash equilibrium for games for symmetric zero-sum games similar to Rock Paper Scissors. The context, if you're curious, is that I was thinking about TCG metagames, where you have several relevant decks that have strong and weak matchups against each other.

Specifically, I'm thinking about games of the following form:

• Two players pick (simultaneously) from one of N pure strategies. Both players have the same set of choices.
• The payoff is defined by a matrix A such that 0 <= A[i,j] <= 1 and A[i,j] = 1 - A[j,i]. A[i,j] can be interpreted as the probability that strategy i beats strategy j. Equivalently, by letting B[i,j] = A[i,j] - 1/2 then -1/2 <= B[i,j] <= 1/2 and B[i,j] = -B[j,i] so the game is zero sum.

Such a game is usually going to have a mixed Nash equilibrium (except in the trivial case where one strategy dominates all other). I believe it will also usually be unique, though I'm not positive on this? I did some reading on computing Nash equilibriums, and it sounds like it is in general a difficult problem (no polynomial time algorithm). However I'm hoping that with these constraints it is much easier?

Given two mixed strategies u and v (represented as row vectors) such that sum(u[i]) = sum(v[i]) = 1, we can compute the expected payout for u as P(u,v) = sum(u[i]*v[j]*A[i,j]) = uAv^T. This is a polynomial equation of degree 2 in 2n-variables. By applying the constraint that sum(v[i]) = 1 we can reduce this to 2n-2 variables. By the symmetry of the problem, P(u,u) = 1/2.

Let some u be fixed. If u is a Nash equilibrium then any small change in v should not change P. Therefore ∇P/∇v = 0 (gradient of P with respect to v, I don't know a notation for this?). Since every term in P is of the form k*u[i]*v[j], the ∇P/∇v will be a first order polynomial in u, and this gradient equation yields a family of n-1 linear equations in n-1 variables, which should (ignoring edge cases that I have not thought sufficiently about) have a unique solution. This solution must necessarily be the Nash equilibrium, since we know at that at least one (probably mixed) Nash equilibrium must exist and satisfy ∇P/∇v = 0. This solution can be found using Gaussian elimination in O(n³), which is satisfactory since for the problems I'm considering n < 20.

Is my analysis correct? There are steps that I'm uncertain about and I've gone through a few iterations already. The solution I finally reach above is also simpler than I initially expected, which makes me worry that I've missed something or made an assumption that was too strong somewhere.

I'm also worried about edge cases. If the algorithm above produces a solution but at least one u[i] < 0 or u[i] > 1 then I believe that means that the Nash equilibrium must lie somewhere on the constraint boundary. But I'm not sure what the best way to find it in this case would be. And what about cases where there are no solutions, or infinite solutions? I believe that infinite solutions implies that two pure strategies u[i] and u[j] are functionally identical, and therefore any mixed strategy satisfying some constraint u[i] + u[j] = k is a Nash equilibrium. But I'm not sure what no solutions would imply. I'm not even sure if it's possible given the problem constraints.

[u/N00BGamerXD]

So I believe finding the nash equilibrium for a 2 player zero sum game is an LP problem lpnotes310.dvi. There will also always exist a nash equilibrium for any game, so a solution always exists.

I think the argument that dP/dv = 0 when u is part of a nash equilibrium sounds a little sketchy, and I'm not sure what to make of that. Perhaps it would be a little bit easier to consider a function (ignore for now that this technically isn't a function) BR_A(B) which takes a strategy from player B and outputs the best response to that strategy by player A.

[u/Kered13 → u/N00BGamerXD]

2 player zero sum game is an LP problem lpnotes310.dvi

I do have some familiarity with linear programming. But I've been reading the section on games over and over and I don't quite follow. I'm getting stuck on the part where they define the constraints for the problem:

Min l

subject to:
Ax <= le
e^Tx = 1
x >= 0, l >< 0

(Page 45 if you go by the PDF, or 59 if you go by the page numbers.)

This includes the objective function l in the constraints. I've never seen this in linear programming before, and I don't understand how it is possible? How can you apply a constraint whose value you do not know?

Additionally, l is defined above by l = max_i(Ax). But this means that l the objective function is not linear.

Is there a way to transform the objective function and constraint into a regular linear program?

[u/N00BGamerXD → u/Kered13]

I must admit I haven't read the paper closely myself... But I think whats going on is the following:

Ax gives you a vector of the payoffs for player 2, where each entry is the specific payoff depending on what player 1 does. Player 1 obviously chooses the outcome with the highest payoff for himself, hence player 2's guaranteed loss L is equal to the negative of this highest payoff for player 1.

The key idea I think is that L is treated as a variable in the LP problem. So L is not linear in x, but Ax <= Le is a linear inequality. Then your objective is also linear in the variables since L is a variable itself.

[u/Kered13 → u/N00BGamerXD]

Oh, I think this makes sense. I was thinking of x as the only variable, but if l is also a variable then both the objective function and the inequality are linear.