The Purification Theorem

Note: The numerator of the last line at 14:30 in the video should be 10 + Ɛ – Ɛ2. Following this into the next slide results in the fraction going to 5/6, as the lecture claims.

Throughout this unit, we have seen a deep connection between mixed strategies from complete information environments and pure strategies in incomplete information environments. This lecture formalizes the connection: mixed strategy Nash equilibria in complete information games are a close approximation of pure strategy Bayesian Nash equilibria in games with a small amount of incomplete information.

For some, this connection is a major reassurance. There are three ways one can interpret mixed strategy Nash equilibria. The first is that players actually mix as the equilibrium describes. Those who participate in games competitively have an intuitive understanding that this is something that happens in practice, but outsiders are sometimes skeptical.

A second interpretation is that mixed strategies form population parameters. Rather than think of a game as between two fixed players, we could think of an interaction occurring between two randomly drawn players from within a larger population. In video games, this arises whenever a player queues for a match against someone else. In every day life, meeting a car across the intersection and deciding who has right of way is a similar application. Then everyone is playing optimal pure strategies if the distribution of those pure strategies matches the mixed strategy Nash equilibrium. This is not always a useful response to critics, as some games do not draw from larger populations.

The third interpretation is that there is uncertainty over types, and that the mixed strategy Nash equilibrium is simulating that uncertainty. This lecture explains the logic underlying that interpretation.

Takeaway Points

  1. The purification theorem says that almost all mixed strategy Nash equilibria in a complete information game are the limit of pure strategy Bayesian Nash equilibria in an incomplete information game that converges to the complete information game.
  2. To see this in action, begin with a mixed strategy Nash equilibrium. Then take the corresponding game and slightly disturb one of the payoffs as private information. There is a pure strategy cutpoint Bayesian Nash equilibrium in that incomplete information game. As the disturbance goes to zero, the probabilities of taking each action match the probabilities of the mixed strategy Nash equilibrium.
  3. This is sometimes known as Harsanyi purification, named after John Harsanyi. He won a Nobel Prize in Economics in part for his work on the purification theorem.

Back to Game Theory 101