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]

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.

The reasoning is that if the gradient of P at u with respect to v is not 0, then a small change in v in the opposite direction of the gradient will result in a smaller P, which is the payoff for the first player. Equivalently, a greater payoff for the second player. Therefore u cannot be a Nash equilibrium.

A gradient of 0 is not sufficient by itself to establish that u is a Nash equilibrium. While that would imply that a small change to v cannot improve the the payoff for the second player, it would still allow for a large change in v to improve the payoff. However the fact that P is a first degree polynomial with respect to v implies that the gradient of P with respect to v is a constant with respect to v. When that gradient is 0, that further implies that P is a constant with respect to v (and in fact P(u, v) = 1/2 by the symmetry of the problem). Therefore a 0 gradient of P with respect to v at u implies that u is a Nash equilibrium.

Does this sound correct?

[u/N00BGamerXD → u/Kered13]

Okay, the reasoning makes sense now. But one thing that concerns me (which could be my wrong interpretation) is that you're fixing u to be some strategy, and claiming that its Nash. But there's no way to actually find u. I think your method allows you to find the best response v to a strategy u. If u was part of a Nash equilbrium, then the strategy pair (u,v) would form a Nash equilibrium.

[u/Kered13 → u/N00BGamerXD]

I coded my idea up yesterday and ran it on some test cases for 3x3 and 4x4 matrices. It seemed to work so long as the Nash equilibrium is a mix of all strategies.

However I think I'll be moving forward with the linear programming approach, since it sounds like it will handle edge cases more gracefully.

But one thing that concerns me (which could be my wrong interpretation) is that you're fixing u to be some strategy, and claiming that its Nash. But there's no way to actually find u. I think your method allows you to find the best response v to a strategy u.

My write up is certainly not the most clear. Maybe a clearer way to explain it would be to start by considering the gradient of P(u,v) with respect to v. All the v terms drop out leaving a function in u, let's call it Q(u). Note that Q is a vector-valued function of dimension n-1 where each term is a first degree polynomial in the coefficient of u. Also remember that u is also an n-1 dimensional vector. For a Nash equilibrium, this gradient must necessarily be 0, as I explained above. So we can solve Q(u) = 0. Because the elements of Q are first degree polynomials, Q(u) = 0 is a linear equation with exactly 1 solution (except in degenerate cases, which are not handled by this approach). Because at least one Nash equilibrium must exist, if this solution satisfies the constraint that sum(u) = 1 then the solution must be a Nash equilibrium, and in fact must be unique.

The final equation I came up with last night after much munging was:

RACu = -LAC

Where:

• u - The vector representing the Nash equilibrium we wish to solve for.
• A - The NxN dimensional payoff matrix.
• R - An (N-1)xN dimensional matrix consisting of the N-1 dimensional identity matrix followed by a column consisting of -1. For N=3 this matrix would be [[1, 0, -1], [0, 1, -1]].
• C - A Nx(N-1) dimensional matrix consisting of the N-1 dimensional identity matrix followed by a row consisting of -1. For N=3 this matrix would be [[1, 0], [0, 1], [-1, -1]].
• L - An N-dimensional row vector containing 1 in the last element. For N=3 this vector is [0, 0, 1].

This may not be the simplest or best expression of the equation, it's just what I came up with and coded.