Purification theorem

In game theory, the purification theorem was contributed by Nobel laureate John Harsanyi in 1973.^[1] The theorem aims to justify a puzzling aspect of mixed strategy Nash equilibria: that each player is wholly indifferent amongst each of the actions he puts non-zero weight on, yet he mixes them so as to make every other player also 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 emerge as ever improving approximations of a game that is not observed by the theorist who designed the original, idealized game.

The apparently mixed nature of the strategy is actually just the result of each player playing a pure strategy with threshold values that depend on the ex-ante distribution over the continuum of payoffs that a player can have. As that continuum shrinks to zero, the players strategies converge to the predicted Nash equilibria of the original, unperturbed, complete information game.

The result is also an important aspect of modern-day inquiries in evolutionary game theory where the perturbed values are interpreted as distributions over types of players randomly paired in a population to play games.

Example

Consider the Hawk–Dove game shown here. The game has two pure strategy equilibria (Defect, Cooperate) and (Cooperate, Defect). It also has a mixed equilibrium in which each player plays Cooperate with probability 2/3.

Suppose that each player i bears an extra cost a_i 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 a_i ≤ a* is (a* + A)/2A. If player 2 Cooperates when a₂ ≤ a*, then player 1's expected utility from Cooperating is −a₁ + 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 a₁ ≤ 2 - 3(a*+A)/2A. Seeking a symmetric equilibrium where both players cooperate if a_i ≤ 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

${\displaystyle \Pr(a_{i}\leq a^{*}}={\frac {{}{1}{2+3/A}}{2}+A}{2}}}{2}}A}}={\frac{A}{4A^{2}+6A}+{\frac {1}{2}.}$

A → 0으로, 이것은 완전한 정보 게임의 혼합 전략에서와 같은 확률인 2/3에 접근한다.

따라서, 우리는 혼합된 전략 평형을 순수한 전략의 결과라고 생각할 수 있고, 그들의 보상에 대해 약간의 사적인 정보를 가지고 있는 플레이어들이 뒤따른다.

기술적 세부사항

Harsani의 증거는 각 선수의 동요가 다른 선수들과 독립적이라는 강한 가정을 포함하고 있다. 그러나 정리를 보다 일반화시키기 위한 추가 정비가 시도되었다.^[2][3]

정리의 주요 결과는 주어진 게임의 모든 혼합된 전략이 같은 순서의 혼란된 게임을 사용하여 정화될 수 있다는 것이다. 그러나, 동요의 독립성 외에도, 그것은 이 순서의 게임이 완전하게 측정되는 것에 대한 일련의 보상에 의존한다. 병적인 성격의 게임들이 있는데, 그 게임들은 이 조건이 지켜지지 않는다.

이러한 게임의 주요 문제는 두 가지 범주 중 하나로 분류된다. (1) 게임의 다양한 혼합 전략들은 혼란스러운 게임의 다른 순서에 의해 정화된다. (2) 게임의 일부 혼합 전략들은 약하게 지배하는 전략을 포함한다. 약하게 지배하는 전략을 포함하는 어떤 혼합 전략도 이 방법을 사용하여 정화할 수 없다. 약하게 지배하는 전략이 최선의 대응이 아닌 전략을 상대편이 수행할 가능성이 있다면, 약하게 지배하는 전략을 결코 실행하기를 바라지 않을 것이기 때문이다. 따라서 한계는 불연속성을 수반하기 때문에 이를 지탱하지 못한다.^[4]

참조