Evolutionary Stability of Pure-Strategy Equilibria in Finite Games

Sufficient conditions for pure-strategy Nash equilibria of finite games to be (Lyapunov) stable under a large class of evolutionary dynamics, the regular monotonic selection dynamics, are discussed. In particular, it is shown that in almost all finite extensive-form games, all the pure-strategy equilibria are stable. In such games, all mixed-strategy equilibria close to pure-strategy equilibria are also stable.Journal of Economic LiteratureClassification Numbers: C70, C72.     

The number of pure Nash equilibria in a random game with nondecreasing best responses

We randomly draw a game from a distribution on the set of two-player games with a given size. We compute the distribution and the expectation of the number of pure-strategy Nash equilibria of the game conditional on the game having nondecreasing best-response functions. The conditional expected number of pure-strategy Nash equilibria becomes much larger than the unconditional expected number as the size of the game grows.     

Fictitious play property of the Nash demand game

We show that the Nash demand game has the fictitious play property. We also show that almost every fictitious play process and its associated belief path converge to a pure-strategy Nash equilibrium in the Nash demand game.     

Learning behavior and mixed-strategy Nash equilibria

The paper considers whether an adaptive justification, like those commonly available for non-interactive optimization models, can be found for the mixed-strategy Nash equilibrium. Although it is known that such a justification is frequently available for pure-strategy equilibria, it is shown that all members of a wide class of behaviorally plausible learning mechanisms must fail to converge in ‘almost all’ games in which the equilibrium involves mixed strategies. An exact formal analogy is developed, which allows these learning mechanisms to be viewed as discrete ta?tonnement processes in properly chosen competitive exchange economies. In the analogy, the instability derives from the independence of excess demand functions (except at the boundaries) from ‘own’ prices. This independence arises because of the linearity in probabilities of von Neumann-Morgenstern risk preferences, and therefore does not extend to pure-strategy equilibria in general. Thus, assuming that agents will play equilibrium strategies implicitly assumes more sophistication when the equilibrium involves mixed strategies than when it involves only pure strategies.     

Supply function equilibria: Step functions and continuous representations

In most electricity markets generators must submit step-function offers to a uniform price auction. These markets are often modelled as simpler pure-strategy Supply Function Equilibria (SFE) with continuous supply functions. Critics argue that the discreteness and discontinuity of the required steps drastically change Nash equilibria, invalidating predictions of the SFE model. We prove that there are sufficient conditions, offered quantities can be continuously varied, offered prices are selected from a finite set, and the density of the additive demand shock is not too steep, where the resulting stepped SFE converges to the continuous SFE as the number of steps increases, reconciling the apparently very disparate approaches to modelling electricity markets.     

Symmetry-breaking in two-player games via strategic substitutes and diagonal nonconcavity: A synthesis

This paper is an attempt to develop a unified approach to symmetry-breaking in strategic models arising in industrial organization by constructing two general classes of two-player symmetric games that always possess only asymmetric pure-strategy Nash equilibria. These classes of games are characterized in some abstract sense by two general properties: payoff nonconcavities and some form of strategic substitutability. Our framework relies on easily verified assumptions on the primitives of the game, and relies on the theory of supermodular games. The underlying natural assumptions are satisfied in a number of two-stage models with an investment decision preceding product market competition. To illustrate the generality and wide scope for application of our approach, we present some existing models dealing with R&D, capacity expansion and information provision, which motivated this study.     

Competitive behavior in market games: Evidence and theory

We explore whether competitive outcomes arise in an experimental implementation of a market game, introduced by Shubik (1973) [21]. Market games obtain Pareto inferior (strict) Nash equilibria, in which some or possibly all markets are closed. We find that subjects do not coordinate on autarkic Nash equilibria, but favor more efficient Nash equilibria in which all markets are open. As the number of subjects participating in the market game increases, the Nash equilibrium they achieve approximates the associated competitive equilibrium of the underlying economy. Motivated by these findings, we provide a theoretical argument for why evolutionary forces can lead to competitive outcomes in market games.     

Unique equilibrium in rent-seeking contests with a continuum of types

It is shown that rent-seeking contests with continuous and independent type distributions possess a unique pure-strategy Nash equilibrium.     

A global Newton method to compute Nash equilibria

A new algorithm is presented for computing Nash equilibria of finite games. Using Kohlberg and Mertens’ structure theorem we show that a homotopy method can be represented as a dynamical system and implemented by Smale's global Newton method. The algorithm is outlined and computational experience is reported.     

Equilibria in rent-seeking contests with homogeneous success functions

Summary. We characterize pure-strategy Nash equilibria for symmetric rent-seeking contests in which the contest success function is homogeneous of degree zero. The equilibrium strategies have a simple form. We give sufficient conditions for existence of an equilibrium.Received: 11 February 2003, Revised: 27 August 2004, JEL Classification Numbers: D72. Correspondence to: Andrew J. YatesWe thank Douglas Nelson, Jac Heckelman, and two anonymous referees for helpful comments.     

A characterization of strategic complementarities

I characterize games for which there is an order on strategies such that the game has strategic complementarities. I prove that, with some qualifications, games with a unique equilibrium have complementarities if and only if Cournot best-response dynamics has no cycles; and that all games with multiple equilibria have complementarities. As applications of my results, I show that: (1) generic 2×2 games either have no pure-strategy equilibria, or have complementarities; (2) generic two-player finite ordinal potential games have complementarities.     

Discontinuous stable games and efficient Nash equilibria

In the recent paper by the author [Scalzo, V., 2010. Pareto efficient Nash equilibria in discontinuous games. Economics Letters 107, 364-365], a class of discontinuous games where efficient Nash equilibria exist has been defined. In the present paper, we complete the previous investigation and recognize a class of discontinuous games where the efficient Nash equilibria are stable with respect to perturbations of the characteristics of players.     

Homotopy methods to compute equilibria in game theory

This paper presents a survey of the use of homotopy methods in game theory. Homotopies allow for a robust computation of game-theoretic equilibria and their refinements. Homotopies are also suitable to compute equilibria that are selected by various selection theories. We present the relevant techniques underlying homotopy algorithms. We give detailed expositions of the Lemke–Howson algorithm and the van den Elzen–Talman algorithm to compute Nash equilibria in 2-person games, and the Herings–van den Elzen, Herings–Peeters, and McKelvey–Palfrey algorithms to compute Nash equilibria in general n-person games. We explain how the main ideas can be extended to compute equilibria in extensive form and dynamic games, and how homotopies can be used to compute all Nash equilibria.     

Menu theorems for bilateral contracting

This paper studies bilateral contracting where multiple principals negotiate contracts with multiple agents independently. It is shown that pure-strategy equilibrium allocations relative to any ad hoc set of feasible mechanisms are supported by pure-strategy perfect Bayesian equilibria relative to the set of menus. This paper also shows that all equilibrium allocations to any ad hoc set of feasible mechanisms are supported by correlated equilibria relative to the set of menus, where a state is a probability distribution function over payoff-relevant variables. Furthermore, all equilibrium allocations relative to the set of menus persist even if principals use more complex mechanisms.     

The supercore for normal-form games

This paper analyzes the supercore of a system derived from a normal-form game. For the case of a finite game with pure strategies, we define a sequence of games and show that the supercore coincides with the set of Nash equilibria of the last game in that sequence. This result is illustrated with the characterization of the supercore for the n-person prisoner's dilemma. With regard to the mixed extension of a normal-form game, we show that the set of Nash equilibrium profiles coincides with the supercore for games with a finite number of Nash equilibria.     

Mixed-strategy equilibria in the Nash Demand Game

In the Nash Demand Game, each of the two players announces the share he demands of an amount of money that may be split between them. If the demands can be satisfied, they are; otherwise, neither player receives any money. This game has many pure-strategy equilibria. This paper characterizes mixed-strategy equilibria. The condition critical for an equilibrium is that players’ sets of possible demands be balanced. Two sets of demands are balanced if each demand in one set can be matched with a demand in the other set such that they sum to one. For Nash’s original game, a complete characterization is given of the equilibria in which both players’ expected payoffs are strictly positive. The findings are applied to the private provision of a discrete public good.     

Testing the TASP: An experimental investigation of learning in games with unstable equilibria

We report experiments studying mixed strategy Nash equilibria that are theoretically stable or unstable under learning. The Time Average Shapley Polygon (TASP) predicts behavior in the unstable case. We study two versions of Rock-Paper-Scissors that include a fourth strategy, Dumb. The unique Nash equilibrium is identical in the two games, but the predicted frequency of Dumb is much higher in the game where the NE is stable. Consistent with TASP, the observed frequency of Dumb is lower and play is further from Nash in the high payoff unstable treatment. However, Dumb is played too frequently in all treatments.     

On the asymptotic uniqueness of bargaining equilibria

This note reexamines the connection between the asymmetric Nash bargaining solution and the equilibria of strategic bargaining games. A first example shows non-convergence to the asymmetric Nash bargaining solution. A second example demonstrates the possibility of multiple limits.     

Near-efficient equilibria in contribution-based competitive grouping

We examine theoretically and experimentally how competitive contribution-based group formation affects incentives to free-ride. We introduce a new formal model of social production, called a “Group-based Meritocracy Mechanism” (GBM), which extends the single-group-level analysis of a Voluntary Contribution Mechanism (VCM) to multiple groups. In a GBM individuals are ranked according to their group contributions. Based on this ranking, participants are then partitioned into equal-sized groups. Members of each group share their collective output equally amongst themselves according to a VCM payoff function. The GBM has two pure-strategy Nash equilibria. One is non-contribution by all; this equilibrium thus coincides with the VCM's equilibrium. The second equilibrium is close to Pareto optimal. It is asymmetric and quite complex from the viewpoint of experimental subjects, yet subjects tacitly coordinate this equilibrium reliably and precisely. Extensions of the basic GBM model to incorporate various features of naturally occurring group formation are suggested in the conclusion.     

Determinacy of equilibrium outcome distributions for zero sum and common utility games

We show the generic finiteness of probability distributions induced on outcomes by the Nash equilibria in two player zero sum and common interest outcome games.