A short proof of Harsanyi's purification theorem

doi:10.1016/S0899-8256(03)00149-0

Games and Economic Behavior

Volume 45, Issue 2, November 2003, Pages 369-374

https://doi.org/10.1016/S0899-8256(03)00149-0 Get rights and content

Abstract

A short proof of more general version of Harsanyi's purification theorem is provided through an application of a powerful, yet intuitive, result from algebraic topology.

References (6)

R.J. Aumann et al.
Approximate purification of mixed strategies
Math. Oper. Res.
(1983)
A. Dold
Lectures on Algebraic Topology
(1972)
J.C. Harsanyi
Games with randomly disturbed payoffs: a new rationale for mixed-strategy equilibrium points
Int. J. Game Theory
(1973)

There are more references available in the full text version of this article.

Cited by (21)

Regular potential games
2020, Games and Economic Behavior
Citation Excerpt :
If all equilibria of a game are regular, then the number of NE strategies in the game has been shown to be finite and, curiously, odd (Harsanyi, 1973a; Wilson, 1971). Regular equilibria have also been studied in the context of games of incomplete information, where, as part of Harsanyi's celebrated purification theorem (Harsanyi, 1973b; Govindan et al., 2003; Morris, 2008), they have been shown to be approachable. A game is said to be regular if all equilibria in the game are regular.
A fundamental problem with the Nash equilibrium concept is the existence of certain “structurally deficient” equilibria that (i) lack fundamental robustness properties, and (ii) are difficult to analyze. The notion of a “regular” Nash equilibrium was introduced by Harsanyi. Such equilibria are isolated, highly robust, and relatively simple to analyze. A game is said to be regular if all equilibria in the game are regular. In this paper it is shown that almost all potential games are regular. That is, except for a closed subset with Lebesgue measure zero, all potential games are regular. As an immediate consequence of this, the paper also proves an oddness result for potential games: In almost all potential games, the number of Nash equilibrium strategies is finite and odd. Specialized results are given for weighted potential games, exact potential games, and games with identical payoffs. Applications of the results to game-theoretic learning are discussed.
On the learning and stability of mixed strategy Nash equilibria in games of strategic substitutes
2016, Journal of Economic Behavior and Organization
This paper analyzes the learning and stability of mixed strategy Nash equilibria in games of strategic substitutes (GSS), complementing recent work done in the case of strategic complements (GSC). Mixed strategies in GSS are of particular interest because it is well known that such games need not exhibit pure strategy Nash equilibria. First, we establish bounds on the strategy space which indicate where randomizing behavior may occur in equilibrium. Second, we show that mixed strategy Nash equilibria are generally unstable under a wide variety of learning rules. Multiple examples are given.
Regularity and robustness in monotone Bayesian games
2015, Journal of Mathematical Economics
Correlated equilibrium existence for infinite games with type-dependent strategies
2011, Journal of Economic Theory
Under study are games in which players receive private signals and then simultaneously choose actions from compact sets. Payoffs are measurable in signals and jointly continuous in actions. This paper gives a counter-example to the main step in Cotterʼs [K. Cotter, Correlated equilibrium in games with type-dependent strategies, J. Econ. Theory 54 (1991) 48–69] argument for correlated equilibrium existence for this class of games, and supplies an alternative proof.
Evolutionary equilibrium in Bayesian routing games: Specialization and niche formation
2010, Theoretical Computer Science
In this paper we consider Nash equilibria for the selfish task allocation game proposed in Koutsoupias, Papadimitriou (1999) [26], where a set of $n$ users with unsplittable tasks of different size try to access $m$ parallel links with different speeds. In this game, a player can use a mixed strategy (where he uses different links with a positive probability); then he is indifferent between the different link choices. This means that the player may well deviate to a different strategy over time. We propose the concept of evolutionary stable strategies (ESS) as a criterion for stable Nash equilibria, i.e. equilibria where no player is likely to deviate from his strategy. An ESS is a steady state that can be reached by a user community via evolutionary processes in which more successful strategies spread over time. The concept has been used widely in biology and economics to analyze the dynamics of strategic interactions.
We first define a symmetric version of a Bayesian parallel links game where every player is not assigned a task of a fixed size but instead is assigned a task drawn from a distribution, which is the same for all players. We establish that the ESS is uniquely determined for a given symmetric Bayesian parallel links game (when it exists). Thus evolutionary stability places strong constraints on the assignment of tasks to links.
We characterize ESS for the Bayesian parallel links game, and investigate the structure of evolutionarily stable equilibria: In an ESS, links acquire niches, meaning that there is minimal overlap in the tasks served by different links. Furthermore, all links with the same speed are interchangeable for every task with weight $w$ : Every player must place a task with weight $w$ on links having the same speed with the same probability. Also, bigger tasks must be assigned to faster links and faster links must have a bigger load. Finally, we introduce a clustering condition–roughly, distinct links must serve distinct tasks–that is sufficient for evolutionary stability, and can be used to find an ESS in many models.
Purification in the infinitely-repeated prisoners' dilemma
2008, Review of Economic Dynamics
This paper investigates the Harsanyi [Harsanyi, J.C., 1973. Games with randomly disturbed payoffs: A new rationale for mixed-strategy equilibrium points. International Journal of Game Theory 2 (1), 1–23]-purifiability of mixed strategies in the repeated prisoners' dilemma with perfect monitoring. We perturb the game so that in each period, a player receives a private payoff shock which is independently and identically distributed across players and periods. We focus on the purifiability of one-period memory mixed strategy equilibria used by Ely and Välimäki [Ely, J.C., Välimäki, J., 2002. A robust folk theorem for the prisoner's dilemma. Journal of Economic Theory 102 (1), 84–105] in their study of the repeated prisoners' dilemma with private monitoring. We find that any such strategy profile is not the limit of one-period memory equilibrium strategy profiles of the perturbed game, for almost all noise distributions. However, if we allow infinite memory strategies in the perturbed game, then any completely-mixed equilibrium is purifiable.

View all citing articles on Scopus

View full text

A short proof of Harsanyi's purification theorem

Abstract

Approximate purification of mixed strategies

Math. Oper. Res.

Lectures on Algebraic Topology

Games with randomly disturbed payoffs: a new rationale for mixed-strategy equilibrium points

Int. J. Game Theory