Simple search methods for finding a Nash equilibrium

We present two simple search methods for computing a sample Nash equilibrium in a normal-form game: one for 2-player games and one for n-player games. Both algorithms bias the search towards supports that are small and balanced, and employ a backtracking procedure to efficiently explore these supports. Making use of a new comprehensive testbed, we test these algorithms on many classes of games, and show that they perform well against the state of the art—the Lemke–Howson algorithm for 2-player games, and Simplicial Subdivision and Govindan–Wilson for n-player games.     

Iterated strict dominance in general games

We offer a definition of iterated elimination of strictly dominated strategies (IESDS^*) for games with (in)finite players, (non)compact strategy sets, and (dis)continuous payoff functions. IESDS^* is always a well-defined order independent procedure that can be used to solve Nash equilibrium in dominance-solvable games. We characterize IESDS^* by means of a “stability” criterion, and offer a sufficient and necessary epistemic condition for IESDS^*. We show by an example that IESDS^* may generate spurious Nash equilibria in the class of Reny's better-reply secure games. We provide sufficient/necessary conditions under which IESDS^* preserves the set of Nash equilibria.     

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.     

Evolutionary stability and lexicographic preferences

We explore the interaction between evolutionary stability and lexicographic preferences. To do so, we define a limit Nash equilibrium for a lexicographic game as the limit of Nash equilibria of nearby games with continuous preferences. Nash equilibria of lexicographic games are limit Nash equilibria, but not conversely. Modified evolutionarily stable strategies (Binmore and Samuelson, 1992. J. Econ. Theory 57, 278–305) are limit Nash equilibria. Modified evolutionary stability differs from “lexicographic evolutionarily stability” (defined by extending the common characterization of evolutionary stability to lexicographic preferences) in the order in which limits in the payoff space and the space of invasion barriers are taken.     

The symmetric multiple prize all-pay auction with complete information

This paper extends the analysis of the n-player all-pay auction with complete information to cover the case of m≤n prizes, valued in weakly decreasing order, but symmetrically across players. We provide a complete characterization of the Nash equilibrium distributions for this class of auctions and provide an exact expression for the expected revenue generated.     

Communication equilibrium payoffs in repeated games with imperfect monitoring

We characterize the set of communication equilibrium payoffs of any undiscounted repeated matrix-game with imperfect monitoring and complete information. For two-player games, a characterization is provided by Mertens, Sorin, and Zamir (Repeated games, Part A (1994) CORE DP 9420), mainly using Lehrer's (Math. Operations Res. (1992) 175) result for correlated equilibria. The main result of this paper is to extend this characterization to the n-player case. The proof of the characterization relies on an analogy with an auxiliary 2-player repeated game with incomplete information and imperfect monitoring. We use Kohlberg's (Int. J. Game Theory (1975) 7) result to construct explicitly a canonical communication device for each communication equilibrium payoff.     

Characterizing belief-free review-strategy equilibrium payoffs under conditional independence

This paper proposes and studies a tractable subset of Nash equilibria, belief-free review-strategy equilibria, in repeated games with private monitoring. The payoff set of this class of equilibria is characterized in the limit as the discount factor converges to one for games where players observe statistically independent signals. As an application, we develop a simple sufficient condition for the existence of asymptotically efficient equilibria, and establish a folk theorem for N-player prisoner?s dilemma. All these results are robust to a perturbation of the signal distribution, and hence remain true even under almost-independent monitoring.     

Cournot–Nash equilibria in continuum games with non-ordered preferences

In the usual framework of continuum games with externalities, we substantially generalize Cournot–Nash existence results [Balder, A unifying approach to existence of Nash equilibria, Int. J.Game Theory 24 (1995) 79–94; On the existence of Cournot–Nash equilibria in continuum games, J. Math. Econ. 32 (1999) 207–223; A unifying pair of Cournot–Nash equilibrium existence results, J. Econ. Theory 102 (2002) 437–470] to games with possibly non-ordered preferences, providing a continuum analogue of the seminal existence results by Mas-Colell [An equilibrium existence theorem without complete or transitive preferences, J. Math. Econ. 1 (1974) 237–246], Gale and Mas-Colell [An equilibrium existence theorem for a general model without ordered preferences, J. Math. Econ. 2 (1975) 9–15], Shafer and Sonnenschein [Equilibrium in abstract economies without ordered preferences, J. Math. Econ. 2 (1975) 345–348], Borglin and Keiding [Existence of equilibrium actions and of equilibrium: a note on the “new” existence theorems, J. Math. Econ. 3 (1976) 313–316] and Yannelis and Prabhakar [Existence of maximal elements and equilibria in linear topological spaces, J. Math. Econ. 12 (1983) 233–245].     

A general structure theorem for the Nash equilibrium correspondence

I consider n-person normal form games where the strategy set of each player is a non-empty compact convex subset of an Euclidean space, and the payoff function of player i is continuous in joint strategies and continuously differentiable and concave in the player i's strategy. No further restrictions (such as multilinearity of the payoff functions or the requirement that the strategy sets be polyhedral) are imposed. I demonstrate that the graph of the Nash equilibrium correspondence on this domain is homeomorphic to the space of games. This result generalizes a well-known structure theorem in [Kohlberg, E., Mertens, J.-F., 1986. On the strategic stability of equilibria. Econometrica 54, 1003–1037]. It is supplemented by an extension analogous to the unknottedness theorems in [Demichelis S., Germano, F., 2000. Some consequences of the unknottedness of the Walras correspondence. J. Math. Econ. 34, 537–545; Demichelis S., Germano, F., 2002. On (un)knots and dynamics in games. Games Econ. Behav. 41, 46–60]: the graph of the Nash equilibrium correspondence is ambient isotopic to a trivial copy of the space of games.     

On the (non-)lattice structure of the equilibrium set in games with strategic substitutes

This paper studies models where the optimal response functions under consideration are not increasing in endogenous variables, and weakly increasing in exogenous parameters. Such models include games with strategic substitutes, and include cases where additionally, some variables may be strategic complements. The main result here is that the equilibrium set in such models is a non-empty, complete lattice, if, and only if, there is a unique equilibrium. Indeed, for a given parameter value, a pair of distinct equilibria are never comparable. Therefore, with multiple equilibria, some of the established techniques for exhibiting increasing equilibria or computing equilibria that use the largest or smallest equilibrium, or that use the lattice structure of the equilibrium set do not apply to such models. Moreover, there are no ranked equilibria in such models. Additionally, the analysis here implies a new proof and a slight generalization of some existing results. It is shown that when a parameter increases, no new equilibrium is smaller than any old equilibrium. (In particular, in n-player games of strategic substitutes with real-valued action spaces, symmetric equilibria increase with the parameter.)      

A game of timing and visibility

We consider the following abstraction of competing publications. There are n players in the game. Each player i chooses a point x_i in the interval [0,1], and a player's payoff is the distance from its point x_i to the next larger point, or to 1 if x_i is the largest. For this game, we give a complete characterization of the Nash equilibrium for the two-player game, and, more important, we give an efficient approximation algorithm to compute numerically the symmetric Nash equilibrium for the n-player game. The approximation is computed via a discrete version of the game. In both cases, we show that the (symmetric) equilibrium is unique. Our algorithmic approach to the n-player game is non-standard in that it does not involve solving a system of differential equations. We believe that our techniques can be useful in the analysis of other timing games.     

On the Generic Finiteness of Equilibrium Outcomes in Plurality Games

In this paper we prove that for generic (noncooperative) voting games under plurality rule the set of equilibria that induce a mixed distribution over the outcomes (i.e., with two or more candidates elected with positive probability) is finite and, furthermore, each of these equilibria is regular. From that we deduce the finiteness of the set of equilibrium distributions over outcomes. Furthermore we offer an example (S. Govindan and A. McLennan, 1997, “On the Generic Finiteness of Equilibrium Outcome Distributions in Game Forms,” mimeo) that shows the impossibility of extending such results to a general framework, even just to voting games. Journal of Economic Literature Classification Numbers: C72, D72.     

Equilibrium Selection inn-Person Coordination Games

This paper investigates several approaches to equilibrium selection and the relationships between them. The class of games we study aren-person generalized coordination games with multiple Pareto rankable strict Nash equilibria. The main result is that all selection criteria select the same outcome (namely the risk dominant equilibrium) in two-person games, and that most equivalences break for games with more than two players. All criteria select the Pareto efficient equilibrium in voting games, of which pure coordination games are special cases.Journal of Economic LiteratureClassification Numbers: C70, C72, D82.     

Congestion games with malicious players

We study the equilibria of non-atomic congestion games in which there are two types of players: rational players, who seek to minimize their own delay, and malicious players, who seek to maximize the average delay experienced by the rational players. We study the existence of pure and mixed Nash equilibria for these games, and we seek to quantify the impact of the malicious players on the equilibrium. One counterintuitive phenomenon which we demonstrate is the “windfall of malice”: paradoxically, when a myopically malicious player gains control of a fraction of the flow, the new equilibrium may be more favorable for the remaining rational players than the previous equilibrium.     

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.     

Better-reply dynamics and global convergence to Nash equilibrium in aggregative games

We consider n-person games with quasi-concave payoffs that depend on a player's own action and the sum of all players' actions. We show that a discrete-time, stochastic process in which players move towards better replies—the better-reply dynamics—converges globally to a Nash equilibrium if actions are either strategic substitutes or strategic complements for all players around each Nash equilibrium that is asymptotically stable under a deterministic, adjusted best-reply dynamics. We present an example of a 2-person game with a unique equilibrium where the derivatives of the best-reply functions have different signs and the better-reply dynamics does not converge.     

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.     

Extensive Form Games with Uncertainty Averse Players

Nash equilibrium presumes that the beliefs of a player are represented by a probability measure. Motivated by the Ellsberg Paradox and relevant experimental findings demonstrating that this representation of beliefs may be unrealistic, this paper generalizes Nash equilibrium in finite extensive form games to allow for preferences conforming to the multiple priors model developed by Gilboa and Schmeidler [Journal of Mathematical Economics, 18 (1989), 141–153]. The implications of this generalization for strategy choices and welfare are studied. Journal of Economic Literature Classification Numbers: C72, D81.     

Minimum-Effort Coordination Games: Stochastic Potential and Logit Equilibrium

This paper revisits the minimum-effort coordination game with a continuum of Pareto-ranked Nash equilibria. Noise is introduced via a logit probabilistic choice function. The resulting logit equilibrium distribution of decisions is unique and maximizes a stochastic potential function. In the limit as the noise vanishes, the distribution converges to an outcome that is analogous to the risk-dominant outcome for 2 × 2 games. In accordance with experimental evidence, logit equilibrium efforts decrease with increases in effort costs and the number of players, even though these parameters do not affect the Nash equilibria. Journal of Economic Literature Classification Numbers: C72, C92.     

Asymptotic expected number of Nash equilibria of two-player normal form games

The formula given by McLennan [The mean number of real roots of a multihomogeneous system of polynomial equations, Amer. J. Math. 124 (2002) 49–73] is applied to the mean number of Nash equilibria of random two-player normal form games in which the two players have M and N pure strategies respectively. Holding M fixed while N→∞, the expected number of Nash equilibria is approximately . Letting M=N→∞, the expected number of Nash equilibria is , where is a constant, and almost all equilibria have each player assigning positive probability to approximately 31.5915 percent of her pure strategies.