How many different states of Nash equilibrium?

Question

So there is this quite well known Prisoner's dilemma where two parties can both defect and cooperate (and get points based on their decisions). In my presently used example I take it that cooperating player always gets $2$ points while defecting player gets $3$ points against cooperating opponent and $0$ points against defecting opponent.

So basically I have my $N^2$ imaginary players placed on a $N \times N$ periodic square lattice and every player (representing a single strategy) takes part in eight interactions (as described above) against adjacent elements. The sum of points received during eight mentioned interactions represents the success of a player.

Finally every player compares the points in one's neighborhood (i. e. himself and eight adjacent elements) and copies the strategy which was the most successful.

What is interesting is that system tends to come to a state where strategies do not change (it is obvious that if two consecutive iterations were identical then the same can be said about all further iterations) or in other words we reach the Nash equilibrium.

But what can one say about the sheer number of different states of Nash equilibrium? I can start with $2^{N^2}$ different states and computational experiments reveal that there is quite a few different states of equilibrium to be reached, but I am interested in purely mathematical point of view. What kind of evaluation, approximation, lower bound is possible? I would be thankful for your observations.

Answer 1

I assume a "strategy" consists of a play in Period 1, since everything is deterministic after that.

Now the answer has to depend on what people are maximizing. You obviously can't have them maximize the sum of their (infinitely many) one-period scores, so presumably you're going to have to introduce a discount rate, i.e. have them maximize $$\sum\beta^iS_i$$ where $i$ is the score in the $i$th period.

For the rest, I'll assume you've got a true Prisoner's Dilemma (which would require different scoring than you've got --- is that a typo?)

When $\beta$ is small, so you pretty much care only about the current period, the only Nash equilibrium is for everyone to defect. In particular, not every steady state is a Nash equilibrium (consider the case where everyone cooperates.)

For larger $\beta$, the only reason to cooperate is so that others will cooperate in the future, but you can cause others to cooperate in the future only if your strategy is more successful than those of their neighboring defectors. That means that (in the first period) cooperators are going to have to have a lot of cooperating neighbors, but of course those cooperating neighbors are a good incentive to defect. (I'm continuing to assume a true Prisoner's Dilemma). So I'm not entirely sure of this, but I suspect that in most cases, all-defect will still be the only equilibrium.

Edited to add: Your comment tells me that you meant the scoring to be as in your first paragraph (so there's no Prisoner's Dilemma here). Under that assumption, with small $\beta$, the condition for equilibrium is that each cooperator has at most five cooperating neighbors and each defector has at least six cooperating neighbors. So the question becomes: How many ways can you distribute C's and D's on an integer lattice in such a way that each C neighbors at most 5 C's and each D neighbors at least six C's. This in turn has nothing to do with game theory. Starting from such a configuration, we can ask whether increasing $\beta$ creates an incentive for anyone to switch strategies. The only way there can be a payoff from switching is if you have a neighbor P such that a) you are P's most successful neighbor and b) P's second most successful neighbor is playing the opposite strategy from you. Given any sort of symmetry at all, it's easy to see this can't happen --- so if there are additional equilibria in the case of large $\beta$, they're going to be very hard to describe.