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.     

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.     

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.     

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.     

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.     

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.     

Consistency of beliefs and epistemic conditions for Nash and correlated equilibria

A consistency condition (action-consistency) on the interim beliefs of players in a game is introduced. Action-consistency is weaker than common priors and, unlike common priors, is characterized by a “no-bets” condition on verifiable events. Using action-consistency, we provide epistemic conditions to Nash and correlated equilibria weakening the common knowledge restrictions in Aumann and Brandenburger [Aumann, R., Brandenburger, A., 1995. Epistemic conditions for Nash equilibrium. Econometrica 63, 1161–1180] and Aumann [Aumann, R., 1987. Correlated equilibrium as an expression of Bayesian rationality. Econometrica 55, 1–18].     

Games with Imperfectly Observable Commitment

[1]claims that, in models of commitment, “the first-mover advantage is eliminated when there is aslightamount of noise associated with the observation of the first-mover's selection.” We show that the validity of this claim depends crucially on the restriction to pure strategy equilibria. The game analyzed by Bagwell always has a mixed equilibrium that is close to the Stackelberg equilibrium when the noise is small. Furthermore, an equilibrium selection theory that combines elements from the theory of[7]with elements from the theory of [6], actually selects this “noisy Stackelberg equilibrium.”Journal of Economic LiteratureClassification Number: C72.     

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.     

An experiment on learning with limited information: nonconvergence, experimentation cascades, and the advantage of being slow

We present the results of an experiment on learning in a continuous-time low-information setting. For a dominance solvable version of a Cournot oligopoly with differentiated products, we find little evidence of convergence to the Nash equilibrium. In an asynchronous setting, characterized by players updating their strategies at different frequencies, play tends toward the Stackelberg outcome which favors the slower player. Convergence is significantly more robust for a “serial cost sharing” game, which satisfies a stronger solution concept of overwhelmed solvability. As the number of players grows, this improved convergence tends to diminish, seemingly driven by frequent and highly structured experimentation by players leading to a cascading effect in which experimentation by one player induces experimentation by others. These results have implications both for traditional oligopoly competition and for a wide variety of strategic situations arising on the Internet.     

On ‘Informationally Robust Equilibria’ for Bimatrix Games

Informationally robust equilibria (IRE) are introduced in Robson (Games Econ Behav 7: 233–245, 1994) as a refinement of Nash equilibria for strategic games. Such equilibria are limits of a sequence of (subgame perfect) Nash equilibria in perturbed games where with small probability information about the strategic behavior is revealed to other players (information leakage). Focusing on bimatrix games, we consider a type of informationally robust equilibria and derive a number of properties they form a non-empty and closed subset of the Nash equilibria. Moreover, IRE is a strict concept in the sense that the IRE are independent of the exact sequence of probabilities with which information is leaked. The set of IRE, like the set of Nash equilibria, is the finite union of polytopes. In potential games, there is an IRE in pure strategies. In zero-sum games, the set of IRE has a product structure and its elements can be computed efficiently by using linear programming. We also discuss extensions to games with infinite strategy spaces and more than two players. The authors would like to thank Marieke Quant for her helpful comments.     

Coherent behavior in noncooperative games

A new concept of mutually expected rationality in noncooperative games is proposed: joint coherence. This is an extension of the “no arbitrage opportunities” axiom that underlies subjective probability theory and a variety of economic models. It sheds light on the controversy over the strategies that can reasonably be recommended to or expected to arise among Bayesian rational players. Joint coherence is shown to support Aumann's position in favor of objective correlated equilibrium, although the common prior assumption is weakened and viewed as a theorem rather than an axiom. An elementary proof of the existence of correlated equilibria is given, and relationships with other solution concepts (Nash equilibrium, independent and correlated rationalizability) are also discussed.     

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.     

Sequential, nonzero-sum “Blotto”: Allocating defensive resources prior to attack

The strategic allocation of resources across multiple fronts has long been studied in the context of Blotto games in which two players simultaneously select their allocations. However many allocation problems are sequential. For example, a state trying to defend against a terrorist attack generally allocates some or all of its resources before the attacker decides where to strike. This paper studies the allocation problem confronting a defender who must decide how to distribute limited resources across multiple sites before an attacker chooses where to strike. Unlike many Blotto games which only have very complicated mixed-strategy equilibria, the sequential, nonzero-sum “Blotto” game always has a very simple pure-strategy subgame perfect equilibrium. Further, the defender always plays the same pure strategy in any equilibrium, and the attacker's equilibrium response is generically unique and entails no mixing. The defender minmaxes the attacker in equilibrium even though the game is nonzero-sum, and the attacker strikes the site among its best replies that minimizes the defender's expected losses.     

Quasi-weightings, Trading, and Desirability Relations in Simple Games

We investigate the problem of simultaneously characterizing various classes of simple games in three different ways: (i) the existence of “quasi-weightings” in which smaller numerical values are assigned to losing coalitions than are assigned to winning ones, (ii) the robustness of “winningness” with respect to trades involving groups of players, and (iii) the acyclicity of certain strict “orderings” that intuitively correspond to the idea of one player being more desirable than another.Journal of Economic LiteratureClassification Number: C71.     

Bounding the inefficiency of equilibria in nonatomic congestion games

Equilibria in noncooperative games are typically inefficient, as illustrated by the Prisoner's Dilemma. In this paper, we quantify this inefficiency by comparing the payoffs of equilibria to the payoffs of a “best possible” outcome. We study a nonatomic version of the congestion games defined by Rosenthal [Int. J. Game Theory 2 (1973) 65], and identify games in which equilibria are approximately optimal in the sense that no other outcome achieves a significantly larger total payoff to the players—games in which optimization by individuals approximately optimizes the social good, in spite of the lack of coordination between players. Our results extend previous work on traffic routing games.     

Infinite Histories and Steady Orbits in Repeated Games

We study a model of repeated games with the following features: (a) Infinite histories. The game has been played since days of yore, or is so perceived by the players: (b) Turing machines with memory. Since regular Turing machines coincide with bounded recall strategies (in the presence of infinite histories), we endow them with "external" memory; (c) Nonstrategic players. The players ignore complicated strategic considerations and speculations about them. Instead, each player uses his/her machine to update some statistics regarding the others′ behaviour, and chooses a best response to observed behaviour. Relying on these assumptions, we define a solution concept for the one shot game, called steady orbit. The (closure of the) set of steady orbit payoffs strictly includes the convex hull of the Nash equilibria payoffs and is strictly included in the correlated equilibria payoffs. Assumptions (a)–(c) above are independent to a large extent. In particular, one may define steady orbits without explicitly dealing with histories or machines.     

The Role of Absolute Continuity in “Merging of Opinions” and “Rational Learning”

D. Blackwell and L. Dubins (1962, Ann. Math. Statist.38, 882–886) showed that opinions merge when priors are absolutely continuous. E. Kalai and E. Lehrer (1993, Econometrica61, 1019–1045) use this result to show that players in a repeated game eventually play like a Nash equilibrium. We provide an alternative proof of merging of opinions that clarifies the role of absolute continuity while casting doubt on the relevance of the result. Persistent disagreement, the opposite of merging, allows the construction of a sequence of mutually favorable “bets.” By a law of large numbers, both agents are certain they will win these bets on average. This certain disagreement violates absolute continuity. Journal of Economic Literature Classification Numbers: C11, C69, C72, D83.     

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.     

War and peace: Third-party intervention in conflict

This paper develops a simple sequential-move game to characterize the endogeneity of third-party intervention in conflict. We show how a third party's “intervention technology” interacts with the canonical “conflict technologies” of two rival parties in affecting the sub-game perfect Nash equilibrium outcome. From the perspective of deterrence strategy, we find that it is more costly for a third party to support an ally to deter a challenger from attacking (i.e., to maintain peace or acquiescence), as compared to the alternative case when the third party supports the ally to gain a disputed territory by attacking (i.e., to create war), ceteris paribus. However, an optimally intervening third party can be either “peace-making”, “peace-breaking”, or neither depending on the characteristics of the conflict and the stakes the third party holds with each of the rival parties.