This paper is a real classic that I noticed had yet to appear on this site. Every economist knows a Nash equilibrium attains when no player can improve his payoff by deviating from his strategy. There are two concerns. First, if the equilibrium prescribes a mixed strategy, then why would anyone randomize, by which we mean make important decisions on the basis of a coin flip? And second, how much need I know about the other player for Nash to obtain?
We can think of this in terms of common and mutual knowledge. I know something in some state of the world if I believe that event happens with probability 1 (in other works in this literature, I believe it happens with absolute certainty; don’t concern yourself with this difference). You and I, or the group of us, mutually know something if we all believe it with probability 1. You and I, or the group of us, commonly know something if we all believe it with prob. 1, we all believe with prob. 1 that we all believe it with prob. 1, and so on ad infinitum. It is tempting to believe, and many economists did basically until this paper was published, that common knowledge of the game form (who gets what payoffs from what actions?) and common knowledge of rationality (players maximize given their information) are implied by Nash equilibria. The logic is something like: I play mixed strategy X because I think you will play Y, which you play because you think I will play X because I think you will play Y, and so on.
This logic is not correct. Let a “conjecture” be a belief about what another person will do in a game. In a two player game, if the game form, rationality of the players, and each player’s conjecture is mutually known, the conjectures form a Nash equilibrium. There is no common knowledge at all! The proof is actually really simple. First, if conjectures are mutually known to be Q, then the conjectures actually are Q – this follows almost immediately from the definition of “known”. Next, note that is some action a(i) for player i is assigned positive probability by player j in his conjecture Q(j), then a(i) must be maximizing in the game form given i’s conjecture Q(i) about what j will do. What this sentence says is that j knows the following events “i is rational” and “i is using conjecture Q(i)” happen with probability 1 given the current state, and the event “i plays action a(i)” happens with positive probability given the current state. Since two of those events have probability 1 and the third has positive probability, their intersection has positive probability. In the state where that intersection attains, i is rationally playing a(i) given conjecture Q(i), hence a(i) is an optimal action given what i conjectures j will do. In the same manner, ever action a(j) with positive probability is an optimal action for j given what j conjectures i will do. This is the definition of a Nash equilibrium.
This result is perhaps not too surprising. Why would Nash play require common knowledge of rationality, for instance? If you know what I conjecture you are going to do, and you know my payoff function, and you know that I am rational, then you know what “best respond” means for me, and you know that I will best respond given my conjecture about how you will play. Likewise, I know that you will best respond given your conjecture about how I will play. So if we think of mixed strategies as “conjectures held by our opponents in a game which are mutually known” rather than “conscious randomization devices”, we have a nice interpretation of Nash equilibrium.
With more than 2 players, the situation is a little trickier. We need a common prior about the state, and we need common knowledge of the conjectures. This common knowledge needs to be over the conjectures each player has about what all other players will do, not common knowledge about what each individual player will do; that is, common knowledge that player 1 conjectures that player 2 will mix evenly between A and B, and player 3 will mix evenly between a and b is not sufficient. We need common knowledge that player 1 conjectures, say, that Aa happens 20 percent of the time, Ab 30% of the time, Ba 30 percent of the time and Bb 20 percent of the time. Exact details about why these assumptions are needed can be found in the paper, but the important part here is that, again, common knowledge of rationality is not one of the required conditions for Nash equilibrium to obtain.
http://www.ratio.huji.ac.il/dp_files/dp57.pdf (Final Econometrica version – Aumann is quite good at putting final, ungated copies of his research online. He also appears, in the hallway of our department, in the best economist portrait of all time. Rather than staring blandly at the camera and smiling, Aumann appears like a Biblical character deep in thought while playing a particularly rigorous game of chess.)