MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I don’t see any space here for Nash equilibrium considerations. Every player copies the strategy which was the most successful in the previous iteration not because it is a result of his rational decision (utility maximization) but it’s simply assumed in the model that players act so. I believe we can only reasonably consider steady states in this model. – Waldemar Jul 23 '13 at 12:38
Waldemar: I assume a strategy consists of a play in Period 1. – Steven Landsburg Jul 23 '13 at 12:45
Steven, perhaps, you’re right. However, the sentence “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” makes me not so sure. – Waldemar Jul 23 '13 at 12:51
I admit that Waldemar does have a point. It is true that everything following the initial state is deterministic but the process of copying adjacent elements is supposed to be equivalent to maximizing utility (yes, it is probably as bad as summing infinitely many scores). Consequently one might as well consider these as simply steady states. – Pranasas Jul 23 '13 at 14:22
up vote 2 down vote accepted

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.

share|cite|improve this answer
Thank you for your answer. There does not seem to be a typo in scoring (I believe you are referring to $T > R > P > S$ payoffs condition which is regularly ignored in some sources). You made it pretty clear when it comes to utility function of a type $\sum\beta^iS_i$ and I honestly appreciate it. Yet another way to look at it is that the process of copying adjacent elements is equivalent to maximizing utility (even though it might be perceived as a degradation of Nash equilibrium making it the same as a steady state). – Pranasas Jul 23 '13 at 14:41
I don't see why copying adjacent elements would have anything to do with maximizing utility. I also don't understand the phrase "degradation of Nash equilibrium". – Steven Landsburg Jul 23 '13 at 15:09
Also, if you don't intend this to be a Prisoner's Dilemma, then of course you shouldn't call it one. – Steven Landsburg Jul 23 '13 at 15:09
What if utility function is defined as a function which is maximized by copying adjacent elements (no matter how mathematically complicated)? And you're right about my provided scoring being not appropriate for Prisoner's dilemma - so does the scoring make it a nameless problem? – Pranasas Jul 23 '13 at 15:45
???? So you've set up a game where utility is maximized by following the rules? Obviously, then, of course anything that obeys the rules is a Nash equilibrium. Where's the math problem? – Steven Landsburg Jul 23 '13 at 15:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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