An Evolutionary Interpretation of Mixed-Strategy Equilibria

A convincing interpretation of mixed-strategy equilibria describes them as steady states in a large population in which players use pure strategies but the population as a whole mimics a mixed strategy. I study the conditions under which an evolutionary, stochastic learning process converges to the appropriate distribution over pure strategies in the population. I find that not all mixed equilibria can be justified as the result of an evolutionary process even if the equilibrium is unique. For symmetric 2 × 2 and 3 × 3 games I give necessary and sufficient conditions for convergence, which are related to the concept of an ESS, and forn × ngames I give a sufficient condition.Journal of Economic LiteratureClassification Numbers: C73, D83.     

A Note on the Probability of k Pure Nash Equilibria in Matrix Games

A formula is derived for the probability that a "randomly selected" n-person matrix game has exactly k pure strategy equilibria. It is shown that for all n ≥ 2, this probability converges to e⁻¹/k! as the sizes of the strategy sets of at least two players increase without bound. Thus the number of pure strategy equilibria in large random n-person matrix games is approximately Poisson distributed with mean one. The latter is a known result obtained by a new proof in this note. Journal of Economic Literature Classification Number: C72.     

Fictitious play in ‘one-against-all’ multi-player games

Summary. A compound game is an (n + 1) player game based on n two-person subgames. In each of these subgames player 0 plays against one of the other players. Player 0 is regulated, so that he must choose the same strategy in all n subgames. We show that every fictitious play process approaches the set of equilibria in compound games for which all subgames are either zero-sum games, potential games, or games. Received: July 18, 1997; revised version: December 4, 1998     

A Noncooperative Analysis of Hotelling's Location Game

We study the location equilibrium in Hotelling's model of spatial competition. As d'Aspremontet al.have shown, with quadratic consumer transportation cost the two sellers will seek to move as far away from each other as possible. We show that the location game possesses an infinity of mixed strategy Nash equilibria. In these equilibria coordination failure invalidates the principle of “maximum differentiation” and firms may even locate at the same point.Journal of Economic LiteratureClassification Numbers: C72, D43, L11.     

Voting with abstention

Most voting models in the literature neglect abstention, but is such a simplification justified? I investigate this question in a model with outside pressure on voters. For sequential voting (e.g., roll call votes), with and without an abstention option, there is a unique subgame perfect equilibrium, which implies that true majorities always succeed. Abstention can be an equilibrium strategy for some voters, in particular under complex decision rules (e.g., weighted voting, double majorities). Simultaneous voting often has a unique pure strategy equilibrium but also a plethora of mixed and pure/mixed strategy equilibria. Therefore, only with equilibrium selection, can we evaluate the consequences of neglecting abstention. For equal weight voting, equilibria selected by the procedure of Harsanyi and Selten change completely with an abstention option, even if abstention itself is not or rarely used. With small enough outside pressure, however, the selected equilibrium honors true majorities in both cases.     

Evolution and Mixed Strategies

Selten (1980, J. Theoret. Biol., 84, 93–101) showed that no mixed equilibria are evolutionarily stable when players can condition their strategies on their roles in a game. Alternatively, Harsanyi's (1973, Int. J. Game Theory, 2, 1–23) purification argument implies that all mixed equilibria are approximations of strict, and hence evolutionarily stable, equilibria of games with slightly perturbed payoffs. This paper reconciles these results: Approximations of mixed equilibria have high invasion barriers, and hence are likely to persist, when payoff perturbations are relatively important and role identification is relatively noisy. When payoff perturbations are unimportant and role identification is precise, approximations of mixed equilibria will have small invasion barriers and are unlikely to persist. Journal of Economic Literature Classification Numbers: C70, C78.     

Reinterpreting mixed strategy equilibria: a unification of the classical and Bayesian views

We provide a new interpretation of mixed strategy equilibria that incorporates both von Neumann and Morgenstern's classical concealment role of mixing, as well as the more recent Bayesian view originating with Harsanyi. For any two-person game, G, we consider an incomplete information game, in which each player's type is the probability he assigns to the event that his mixed strategy in G is “found out” by his opponent. We show that, generically, any regular equilibrium of G can be approximated by an equilibrium of in which almost every type of each player is strictly optimizing. This leads us to interpret i's equilibrium mixed strategy in G as a combination of deliberate randomization by i together with uncertainty on j's part about which randomization i will employ. We also show that such randomization is not unusual: for example, i's randomization is nondegenerate whenever the support of an equilibrium contains cyclic best replies.     

Non-Additive Beliefs and Strategic Equilibria

This paper studies n-player games where players' beliefs about their opponents' behaviour are modelled as non-additive probabilities. The concept of an “equilibrium under uncertainty” which is introduced in this paper extends the equilibrium notion of Dow and Werlang (1994, J. Econom. Theory64, 305–324) to n-player games in strategic form. Existence of such an equilibrium is demonstrated under usual conditions. For low degrees of ambiguity, equilibria under uncertainty approximate Nash equilibria. At the other extreme, with a low degree of confidence, maximin equilibria appear. Finally, robustness against a lack of confidence may be viewed as a refinement for Nash equilibria. Journal of Economic Literature Classification Numbers: C72, D81.     

Unstable and stable steady-states in the Kiyotaki-Wright model

Summary. I provide new results concerning dynamics for a version of the Kiyotaki-Wright model (1989) in which strategies (either mixed or pure) are restricted so that agents play the same strategy for each opportunity set. My results demonstrate the importance of examining stability in such models, because they show that many steady states focused on in the literature are not stable. Furthermore, I exhibit examples of two-period-convergent equilibria in which agents are indifferent among media of exchange. Consequently, their endogenous transaction pattern is analog to the coexistence of assets whose acceptability or “liquidity” varies inversely with their rates of return. Received: June 21, 1996; revised version: December 2, 1996     

Electoral competition with privately-informed candidates

This paper formulates and analyzes a general model of elections in which candidates receive private signals about voters' preferences prior to committing to political platforms. We fully characterize the unique pure-strategy equilibrium: After receiving her signal, each candidate locates at the median of the distribution of the median voter's location, conditional on the other candidate receiving the same signal. Sufficient conditions for the existence of pure strategy equilibrium are provided. Though the electoral game exhibits discontinuous payoffs for the candidates, we prove that mixed strategy equilibria exist generally, that equilibrium expected payoffs are continuous in the parameters of the model, and that mixed strategy equilibria are upper hemicontinuous. This allows us to study the robustness of the median voter theorem to private information: Pure strategy equilibria may fail to exist in models “close” to the Downsian model, but mixed strategy equilibria must, and they will be “close” to the Downsian equilibrium.     

Undominated Nash Implementation with Collusion and Renegotiation

This article looks at implementation in economic environments when agents have perfect information about the state of the world, but cannot commit not to renegotiate bad outcomes or to collude against each other. If renegotiation satisfies a weak condition of disagreement point monotonicity, then any Pareto-efficient social choice function can be implemented if there are at least three agents who play undominated Nash equilibria. The mechanism does not use modulo or integer games, has no bad mixed strategy equilibria, and is “bounded.”Journal of Economic LiteratureClassification Number: D71.     

Learning to Learn, Pattern Recognition, and Nash Equilibrium

The paper studies a large class of bounded-rationality, probabilistic learning models on strategic-form games. The main assumption is that players “recognize” cyclic patterns in the observed history of play. The main result is convergence with probability one to a fixed pattern of pure strategy Nash equilibria, in a large class of “simple games” in which the pure equilibria are nicely spread along the lattice of the game. We also prove that a necessary condition for convergence of behavior to a mixed strategy Nash equilibrium is that the players consider arbitrarily long histories when forming their predictions.Journal of Economic LiteratureClassification Numbers: C72, D83.     

Strong equilibrium in cost sharing connection games

We study network games in which each player wishes to connect his source and sink, and the cost of each edge is shared among its users either equally (in Fair Connection Games—FCG's) or arbitrarily (in General Connection Games—GCG's). We study the existence and quality of strong equilibria (SE)—strategy profiles from which no coalition can improve the cost of each of its members—in these settings. We show that SE always exist in the following games: (1) Single source and sink FCG's and GCG's. (2) Single source multiple sinks FCG's and GCG's on series parallel graphs. (3) Multi source and sink FCG's on extension parallel graphs. As for the quality of the SE, in any FCG with n players, the cost of any SE is bounded by H(n) (i.e., the harmonic sum), contrasted with the Θ(n) price of anarchy. For any GCG, any SE is optimal.     

Mixed equilibria in runoff elections

We demonstrate that the Hotelling–Downs model with runoff voting always admits symmetric mixed strategy equilibria for any (even or odd) number of office-motivated candidates (provided they are at least four). In specific, (a) we show that the game does not admit any symmetric atomless equilibrium, (b) we fully characterize a class of symmetric atomic mixed equilibria which exist for any distribution of the voters' ideal policies and (c) we argue that these equilibria are more robust than pure strategy equilibria to introduction of uncertainty about the voters' preferences.     

Sequential Equilibrium and Competition in a Diamond–Dybvig Banking Model

Within the framework of a Diamond–Dybvig model [J. Polit. Econ.91(1983), 401–419], but with explicitly modelling the autarky choice during the planning period, we demonstrate that a mixed strategy bank run equilibrium that does not rely on sunspots may coexist with the sunspot run equilibrium previously studied in the literature. In a version of the model with multiple banks, there exist sequential equilibria that imply positive profits. However, the zero-profit contract in which runs never occur can be supported as the unique equilibrium outcome if the agents play pure strategies only and their beliefs are restricted to be consistennt with a forward induction argument.Journal of Economic LiteratureClassification Numbers: C72, G21     

A game theoretical approach to the international debt overhang

We consider an international financial problem called debt overhang, by which we mean a situation where a sovereign country has borrowed money from foreign banks and has been unable to fulfill the scheduled repayments for some period. The problem is formulated as a noncooperative game withn lender banks as players where each decides either to sell its loan exposure to the debtor country at the present price of debt on the secondary market, or to wait and keep its exposure. This game has many pure and mixed strategy Nash equilibria. We show, however, that in any Nash equilibrium, the resulting secondary market price remains almost the same as the present price for a large number of banks. We also obtain the comparative statics result that in a mixed strategy equilibrium, a bank with a smaller loan exposure has a greater tendency to sell than one with a larger loan exposure. We discuss the implications of these results for the functioning of the secondary market and the resolution of debt overhang.We thank J. Crémer, H. Haller, S. Mendes, and the referees of this Journal for helpful comments on earlier drafts.     

Commitment Robust Equilibria and Endogenous Timing

This paper investigates which equilibria of a game are still viable when players have the opportunity to commit themselves. To that end we study a model of endogenous timing in which players face the trade-off between committing early and moving late. It is shown that mixed (resp. pure) equilibria of the original game are subgame perfect (resp. persistent) in the timing game only when no player has an incentive to move first. Consequently, mixed equilibria are viable only if no player has an incentive to move first. One needs strong evolutionary solution concepts to draw that conclusion for pure equilibria.Journal of Economic LiteratureClassification Number: C72.     

Random belief equilibrium in normal form games

In defining random belief equilibrium (RBE) in finite, normal form games we assume a player's beliefs about others' strategy choices are randomly drawn from a belief distribution that is dispersed around a central strategy profile, the focus. At an RBE: (1) Each chooses a best response relative to her beliefs. (2) Each player's expected choice coincides with the focus of the other players' belief distributions. RBE provides a statistical framework for estimation which we apply to data from three experimental games. We also characterize the limit-RBE as players' beliefs converge to certainty. When atoms in the belief distributions vanish in the limit, not all limit-RBE (called robust equilibria) are trembling hand perfect Nash equilibria and not all perfect equilibria are robust.     

A note on asymmetric and mixed strategy equilibria in the search-theoretic model of fiat money

Summary. The simple search-theoretic model of fiat money has three symmetric Nash equilibria: all agents accept money with probability 1; all agents accept money with probability 0; and all agents accept money with probability y in (0,1). Here I construct an asymmetric pure strategy equilibrium, payoff-equivalent to the symmetric mixed strategy equilibrium, where a fraction N in (0,1) of agents always accept money and 1-N never accept money. Counter to what has been conjectured previously, I find N > y. I also introduce evolutionary dynamics, and show that the economy converges to monetary exchange iff the initial proportion of agents accepting money exceeds N. Received: September 10, 1997; revised version: April 24, 1998     

A Note on Best Response Dynamics

We investigate the relationship between the continuous time best response dynamic, its perturbed version, and evolutionary dynamics in relation to mixed strategy equilibria. We find that as the level of noise approaches zero, the perturbed best response dynamic has the same qualitative properties as a broad class of evolutionary dynamics. That is, stability properties of equilibria are robust across learning dynamics of quite different origins and motivations. Journal of Economic Literature Classification Numbers: C72, D83.