Purification

Abstract

Many complete information games have equilibria only in mixed strategies, where players are required to randomize over pure strategies among which they are indifferent according to a fixed probability distribution. Harsanyi showed that, if such a game were perturbed – with each player observing an idiosyncratic independent payoff shock with continuous support – then the perturbed games will have pure strategy equilibria which will converge to the mixed strategy equilibrium as the perturbations become small. We review the strong conditions on perturbations under which Harsanyi’s result holds and discuss weaker conditions on perturbations which ensure the existence of pure strategy equilibria without approximating all mixed equilibria of the unperturbed game.

In a mixed strategy equilibrium of a complete information game, players randomize between their actions according to a particular probability distribution, even though they are indifferent between their actions. Two criticisms of such mixed strategy equilibria are (a) that players do not seem to randomize in practice, and (b), if a player were to randomize, why would he or she choose to do so according to probabilities that make other players indifferent between their strategies?

Since many games have no pure strategy equilibria, it is important to provide a more compelling rationale for the play of mixed strategy equilibria.

Harsanyi (1973) gave a ‘purification’ interpretation of mixed strategy equilibrium that resolves these criticisms. The complete information-game payoffs are intended as an approximate description of the strategic situation, but surely do not capture every consideration in the minds of the players. In particular, suppose that a player has some small private inclination to choose one action or another independent of the specified payoffs, but this information is not known to the other players. Then the behaviour of such players will look – to their opponents and to outside observers – as if they are randomizing between their actions, even though they do not experience the choice as randomization. Because of the private payoff perturbation, they will not in fact be indifferent between their actions, but will almost always be choosing a strict best response. Harsanyi’s remarkable purification theorem showed that all equilibria (pure or mixed) of almost all complete information games are the limit of pure strategy equilibria of perturbed games where players have independent small shocks to payoffs.

There are other inpts of mixed strategy play: Reny and Robson (2004) present an analysis that unifies the purification interpretation with the ‘classical’ interpretation that players randomize because they think that there is a small chance that their mixed strategy may be observed in advance by other players. But Harsanyi’s purification theorem justly provides the leading interpretation of mixed strategy equilibria among game theorists today.

I first review Harsanyi’s theorem. Harsanyi’s result applies to regular equilibria of complete information games with independent payoff shocks; since many equilibria of interest (especially in dynamic games) are not regular, Harsanyi’s result cannot be relied upon in many economic settings of interest; I therefore briefly review what little is known about such extensions.

Harsanyi’s theorem has two parts: (a) pure strategy equilibria always exist in suitably perturbed versions of a complete information game; and (b) for any regular equilibrium of a complete information game and any sequence of such perturbed games converging to the complete information game, there is a sequence of pure strategy equilibria converging to the regular equilibrium. An important literature has ignored the latter approachability question and focused on the former pure strategy existence qst, identifying conditions on an information structure – much weaker than Harsanyi’s – to establish the existence of pure strategy equilibria. I conclude by reviewing these papers.

Harsanyi’s th

Consider two players engaging in the symmetric coordination game below.

	A	B
A	2,2	0,0
B	0,0	1,1

As well as the pure strategy Nash equilibria (A,A) and (B,B), this game has a symmetric mixed strategy Nash equilibrium where each player chooses A with probability $\frac{1}{3}$ and B with probability $\frac{2}{3}$.

But suppose that, in addition to these common knowledge payoffs, each player I observes a payoff shock depending on the action he or she chooses. Thus,

	A	B
A	2 + ε.η1A, 2 + ε.η2A	ε.η1A, ε.η2B
B	ε.η1B, ε.η2A	1 + ε.η1B, 1 + ε.η2B

where ε > 0 is a commonly known parameter measuring the size of payoff shocks and (η_1A,η_1B) and (η_2A,η_2B) are distributed independently of each other, and player i observes only (η_iA,η_iB). Finally, assume that, for each player i, η_i = η_iA − η_iB is distributed according to a continuous density f on the real line with corresponding c.d.f. F.

This perturbed game is one with incomplete information, where a player’s strategy is a function s_i : ℝ → {A, B}. In equilibrium, each player will follow a threshold strategy of the form

$$ {s}_i\left({\eta}_i\right)=\left\{\begin{array}{l}A,\kern0.36em \mathrm{if}\kern0.5em {\eta}_i\ge {z}_i\\ {}B,\kern0.36em \mathrm{if}\kern0.5em {\eta}_i<{z}_i\end{array}\right.. $$

Under such a strategy, the ex ante probability that player i will choose action B is π_I = F(z_i), and the probability he or she will choose A is 1 − π_i. Thus we can re-parameterize the strategy as

$$ {s}_i\left({\eta}_i\right)=\left\{\begin{array}{l}A,\kern0.36em \mathrm{if}\kern0.5em {\eta}_i\ge {F}^{-1}\left({\uppi}_i\right)\\ {}B,\kern0.36em \mathrm{if}\kern0.5em {\eta}_i<{F}^{-1}\left({\uppi}_i\right)\end{array}\right.. $$

Let us look for a strategy profile (s₁,s₂) of the incomplete information game, parameterized by (π₁,π₂), that forms an equilibrium of the incomplete information game. Since player 1 thinks that player 2 will choose action A with probability 1 − π₂ and action B with probability π₂, player 1’s expected payoff gain from choosing action A over action B is then

$$ 2\left(1-{\uppi}_2\right)+\varepsilon .{\eta}_1-{\pi}_2. $$

Thus player 1’s best response must be to follow a threshold strategy with threshold

$$ {F}^{-1}\left({\uppi}_i\right)=\frac{3{\pi}_2-2}{\varepsilon } $$

or

$$ \varepsilon {F}^{-1}\left({\uppi}_1\right)=3{\uppi}_2-2. $$

Symmetrically, we have

$$ \varepsilon {F}^{-1}\left({\uppi}_2\right)=3{\uppi}_1-2. $$

Thus, there will be a symmetric equilibrium where both players choose action B with probability π if and only if

$$ \varepsilon {F}^{-1}\left(\uppi \right)=3\uppi -2. $$

For small ε, this equation has three solutions tending 0, $\frac{2}{3}$ and 1 as ε → 0. These solutions correspond to the three symmetric Nash equilibria of the above complete information game, respectively: (a) both always choose A, (b) both choose B with probability $\frac{3}{2}$, and (c) both always choose B.

Harsanyi’s purification theorem generalizes the logic of this example. If we add small independent noise to each player’s payoffs, then each player will almost always have a unique best response and thus the perturbed game will have a pure strategy equilibrium. There is a system of equations that describes equilibria of the unperturbed game. If that system of equations is regular, then a small perturbation of the system of equations will result in a nearby equilibrium.

I will report a statement of Harsanyi’s result due to Govindan, Reny and Robson (2003), which weakens a number of the technical conditions in the original theorem.

Consider an I player complete information game where each player i has a finite set of possible actions A_i and a payoff function g_i : A →ℝ where A = A₁ × · × A_I . An equilibrium α ∈ Δ(A₁) × · × Δ(A_I) is a regular Nash equilibrium of the complete information game if the Jacobian determinant of a continuously differentiable map characterizing equilibrium is non-zero at α (see van Damme 1991, Definition 1.5.1, p. 39).

The μ-perturbed game is then an incomplete information game where each player i privately observes a vector η_i ∈ ℝ^|A|. Player i’s payoff in the incomplete information game if action profile a is chosen is then g_i(a)+ η_ia; thus η_i is a private value shock. Each η_i is independently drawn according to a measure μ_i, where each μ_i assigns probability 0 to i’s expectation of η_i being equal under any pair of i’s pure strategies a_i and ${a}_i^{\prime }$, given any mixed strategy profile of the other players; Govindan, Reny and Robson (2003) note that this weak condition is implied by μ_i being absolutely continuous with respect to Lebesgue measure on ℝ^|A|. A pure strategy for player i in the μ-perturbation is a function s_i : ℝ^|A| → A_i. A pure strategy profile s induces a probability distribution over actions V_s ∈ Δ(A), where

$$ {\nu}_s(a)=\underset{\mu }{\mathbf{\Pr}}\left\{\eta :{s}_i\left({\eta}_i\right)={a}_i\mathrm{for}\ \mathrm{each}\ i\right\} $$

Theorem

(Harsanyi 1973; Govindan et al. 2003) Suppose that α is a regular Nash equilibrium of the complete information game and that, for each i, ${\mu}_i^n$ converges to a point mass at 0 ∈ ℝ^|A|. Then for all ε > 0 and all large enough n, the μ-perturbed game has a pure strategy equilibrium inducing a distribution on A that is within ε of α, that is,

$$ \mid {\nu}_s(a)-\prod_{i=1}^I{\alpha}_i\left({a}_i\right)\mid \le \varepsilon $$

for all a ∈ A.

The pure strategy equilibria are ‘essentially strict’, that is, almost all types have a strict best response. An elegant proof in Govindan, Reny and Robson (2003) simplifies Harsanyi’s original proof.

Dynamic Games

Harsanyi’s theorem applies only to regular equilibria of a complete information game. Harsanyi noted that all equilibria of almost all finite complete information games are regular, where ‘almost all’ means with probability one under Lebesgue measure on the set of payoffs. Of course, normal form games derived from general extensive form games are not generic in this sense. This raises the question of whether mixed strategy equilibria of extensive form games are purifiable in Harsanyi’s sense.

Here is an economic example suggesting why this is an important qst. Consider an infinite overlapping generations economy where agents live for two periods; the young are endowed with two units of an indivisible and perishable consumption good, and the old have no endowment. Each young agent has the option of transferring one unit of consumption to the current old agent. Each agent’s utility function is strictly increasing in own consumption when young and old, and values smoothed consumption (one when young, one when old) strictly more highly than consuming the endowment (two when young, none when old). Under perfect information, this game has a ‘social security’ subgame perfect Nash equilibrium where each young agent transfers one unit to the old agent if and only if no young agent failed to do so in the past. But suppose instead that each young agent observes only whether the previous young agent made a transfer, and restrict attention to subgame perfect Nash equilibria. Then Bhaskar (1998) has shown that there is no pure strategy equilibrium with a positive probability of transfers (in fact, this conclusion remains true if all agents only observe history of any commonly known finite length). To see why, suppose there was such an equilibrium: if the young agent at date t does not transfer, then the young agent at date t + 1 must punish by not making a transfer; but the young agent at date t + 2 did not observe the date t outcome, and so will think that the young agent at date t + 1 deviated, and will therefore not make transfers; so the young agent at date t + 1 would have an incentive to make transfers, and not to punish as required by the equilibrium strategy.

However, Bhaskar shows that there are mixed strategy equilibria with positive transfers. In particular, there is an equilibrium where the young always transfers in the first period or if he or she observed transfers in the previous period, and randomizes between making transfers or not if he or she did not observe transfers. This strategy profile attains the efficient outcome and involves mixing off the equilibrium path only. It is natural to ask whether this equilibrium can be ‘purified’: suppose that each young agent obtains a small ‘altruism’ payoff shock that makes transfers to the old slightly attractive. The mixed strategy might then be the limit of pure strategy equilibria where the more altruistic agents make the transfers and the less altruistic agents do not. However, Bhaskar shows that the mixed strategy equilibria cannot be purified. The logic of Harsanyi’s purification result breaks down because the equilibrium is not regular.

Very little is known in general about purifiability of mixed strategy equilibria in extensive form games. Results will presumably depend on the regularity of the equations characterizing equilibria and the modelling of payoff choices in the extensive form (for example, do shocks occur at the beginning of the game or at each decision node?). The best hope of a positive purification result would presumably be in finite dynamic games, where Harsanyi’s regularity techniques might be applied. But Bhaskar (2000) gives an example of a simple finite extensive form game where mixed strategy equilibria are not purifiable because of the non-regularity of equilibria even for generic assignment of payoffs to terminal nodes. Mixed strategy equilibria play an important role in recent developments of the theory of repeated games. Bhaskar, Mailath and Morris (2006) report some positive and negative purification results in that context.

Purification Without Approachability

Harsanyi’s purification theorem has two parts. First, the ‘purification’ part: all equilibria of the perturbed game are essentially pure; second, the ‘approachability’ part: every equilibrium of a complete information game is the limit of equilibria of such perturbed games. For the first part, Harsanyi’s theorem uses the assumption of sufficiently diffuse independent payoff shocks. Only the second part required the strong regularity properties of the complete information game equilibria.

Radner and Rosenthal (1982) addressed a weaker version of the purification part of Harsanyi’s theorem, asking what conditions on the information system of an incomplete information game will ensure that for every equilibrium (perhaps mixed) there exists an outcome equivalent pure strategy equilibrium. Thus they did not ask that every equilibrium be essentially pure and they did not seek to approximate mixed strategy equilibria of any unperturbed game. Each agent observing a signal with an atomless independent distribution is clearly sufficient for such a ‘purification existence’ result (whether or not the signal is payoff relevant). But what if there is correlation?

A simple example from Radner and Rosenthal (1982) illustrates the difficulty. Suppose that two players are playing matching pennies and each player i observes a payoff-irrelevant signal x_i, where (x₁,x₂) are uniformly distributed on $\left\{\left({x}_1,{x}_2\right)\in {\mathbb{R}}_{+}^2|0\le {x}_1\le {x}_2\le 1\right\}$ . In any equilibrium, almost all types of each player must assign probability $\frac{1}{2}$ to his or her opponent choosing each action (otherwise, that player would be able to obtain a payoff greater than his or her value in the zero sum game). Yet it is impossible to generate pure strategies of the players that make this property hold true. Another illustration of the importance of correlation for purification occurs in Carlsson and van Damme (1993), where it is shown that, while small independent noise leads to Harsanyi’s purification result, small highly correlated noise leads to the selection of a unique equilibrium (the comparison is made explicitly in their Appendix B).

Radner and Rosenthal (1982) show the existence of a pure strategy equilibrium if each player observes a payoff-irrelevant signal with an atomless distribution and each player i’s payoff-irrelevant signal and payoff-relevant information (which may be correlated) are independent of each other player’s payoff-irrelevant signal. This result extends if players observe additional finite private signals which are also uncorrelated with others’ atomless payoff-irrelevant signals. Their method of proof builds on the argument of Schmeidler (1973) showing the existence of a pure strategy equilibrium in a game with a continuum of players. Radner and Rosenthal (1982) also present a number of counter-exs – in addition to the matching pennies example above – with non-existence of pure strategy equilibrium. Milgrom and Weber (1985) show the existence of a pure strategy equilibrium if type spaces are atomless and independent conditional on a finite valued common state variable with payoff interdependence occurring only via the common state variable. Their result – which neither implies nor is implied by the Radner and Rosenthal (1982) conditions – has been used in many applications. Aumann et al. (1983) show that, if every player has a conditionally atomless distribution over others’ types (that is, his or her conditional distribution has no atoms for almost every type), there exists a pure strategy ε-equilibrium. Their theorem thus covers the matching pennies example described above.

The existence of such purifications deals with one of the two criticisms of mixed strategy equilibria raised above: people do not appear to randomize. In particular, in any such purification the ‘randomization’ represents the uncertainty in a player’s mind about how other players will act, rather than deliberate randomization. This interpretation of mixed strategies was originally emphasized by Aumann (1974).

See Also

• Global Games

• Mixed Strategy Equilibrium