Purification Theorem
Game theory provides tools for analyzing situations in which players make decisions that are interdependent. This interdependence causes each player to consider the other player’s possible decisions in formulating strategy. A solution to a game describes the optimal decisions of the players, who may have similar, opposed, or mixed interests, and the outcomes that may result from these decisions.
A pure strategy determines all your moves during the game (and should therefore specify your moves for all possible other players’ moves). A mixed strategy is a probability distribution over all possible pure strategies (some of which may get zero weight). After a player has determined a mixed strategy at the beginning of the game, using a randomising device, that player may pick one of those pure strategies and then stick to it.
Nobel laureate John Harsanyi in 1973 introduced the purification theorem which explains a perplexing aspect of mixed strategy: Nash equilibrium. A Nash Equilibrium is a collection of strategies, one for each player where there is no benefit for any player to switch strategies. In this situation, all players the game are satisfied with their game choices at the same time, so the game remains at equilibrium. Each player is completely indifferent to each of the acts to which he assigns non-zero weight, but he mixes them in such a way that every other player is equally indifferent.
The mixed strategy equilibria are explained as being the limit of pure strategy equilibria for a disturbed game of incomplete information in which the payoffs of each player are known to themselves but not their opponents. The idea is that the predicted mixed strategy of the original game emerges as ever improving approximations of a game that is not observed by the theorist who designed the original, idealized game.
The strategy’s seemingly mixed nature is just the result of each player employing a pure strategy with threshold values based on the ex-ante distribution throughout the range of payoffs available to them. The players’ strategies converge to the predicted Nash equilibria of the original, unperturbed, comprehensive information game as the continuum shrinks to zero.
Hawk-Dove Game has two pure strategy equilibria (Defect and Cooperate) (Cooperate, Defect). It also has a mixed equilibrium, in which each player has a 2/3 chance of playing Cooperate.
Suppose that each player i bears an extra cost ai from playing Cooperate, which is uniformly distributed on [−A, A]. Players only know their own value of this cost. So this is a game of incomplete information which we can solve using Bayesian Nash equilibrium.
The probability that ai ≤ a* is (a* + A)/2A.
If player 2 Cooperates when a2 ≤ a*,
then player 1’s expected utility from Cooperating is −a1 + 3(a* + A)/2A + 2(1 − (a* + A)/2A);
his expected utility from Defecting is 4(a* + A)/2A.
He should therefore himself Cooperate when a1 ≤ 2–3(a*+A)/2A.
Seeking a symmetric equilibrium where both players cooperate if ai ≤ a*,
we solve this for a* = 1/(2 + 3/A). Now we have worked out a*,
we can calculate the probability of each player playing Cooperate as
__________
As A → 0, this approaches 2/3, the same probability as in the mixed strategy in the complete information game.
Thus, we can think of the mixed strategy equilibrium as the outcome of pure strategies followed by players who have a small amount of private information about their payoffs.
The result is also relevant to current evolutionary game theory research, in which perturbed values are viewed as distributions over different sorts of players who are randomly partnered in a population to play games.
Harsanyi’s proof is based on the strong assumption that each player’s perturbations are independent of the perturbations of the other players. However, various improvements have been proposed in order to make the theorem more universal. The basic consequence of the theorem is that all of a game’s mixed strategy equilibria can be purified using the same perturbed game sequence. It does, however, rely on the set of payoffs for this sequence of games being of full measure, in addition to perturbation independence. There are several pathological games for which this criterion does not hold true.
The key problem with these games is that the different mixed strategies of the game are purified by different sequences of perturbed games. Also that certain mixed strategies of the game include weakly dominated strategies. No mixed strategy including a weakly dominated strategy can be purified this way because if there is ever a non-zero chance that the opponent would play a strategy for which the weakly dominated strategy is not the optimum response, one will never want to play the weakly dominated strategy. As a result, the limit does not hold since it has a discontinuity. 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.
