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.     

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.     

Bayesian learning and convergence to Nash equilibria without common priors

Summary. Consider an infinitely repeated game where each player is characterized by a “type” which may be unknown to the other players in the game. Suppose further that each player's belief about others is independent of that player's type. Impose an absolute continuity condition on the ex ante beliefs of players (weaker than mutual absolute continuity). Then any limit point of beliefs of players about the future of the game conditional on the past lies in the set of Nash or Subjective equilibria. Our assumption does not require common priors so is weaker than Jordan (1991); however our conclusion is weaker, we obtain convergence to subjective and not necessarily Nash equilibria. Our model is a generalization of the Kalai and Lehrer (1993) model. Our assumption is weaker than theirs. However, our conclusion is also weaker, and shows that limit points of beliefs, and not actual play, are subjective equilibria. Received: March 3, 1995; revised version: February 17, 1997     

On the Number of Pure Strategy Nash Equilibria in Random Games

How many pure Nash equilibria can we expect to have in a finite game chosen at random? Solutions to the above problem have been proposed in some special cases. In this paper we assume independence among the profiles, but we allow either positive or negative dependence among the players' payoffs in a same profile. We provide asymptotic results for the distribution of the number of Nash equilibria when either the number of players or the number of strategies increases. We will show that different dependence assumptions lead to different asymptotic results. Journal of Economic Literature Classification Number C72.     

Cooperative Outcomes through Noncooperative Games

This paper shows the equivalence between the stable solution set of any cooperative game in characteristic form (G1) and the subgame perfect Nash equilibria in pure strategies of a certain noncooperative game (G2). Players of G1 are named "agents." G2 is played by different players ("principals") who compete in wages to attract agents. The equivalence result holds when there are enough principals (if the game is superadditive, two principals suffice). Finally, another related cooperative game (G3) is constructed with both principals and agents as players. For G2 and G3 the same result is then proven, for any number of principals. Journal of Economic Literature Classification Numbers: C71 and C72.     

The power of ESS: An experimental study

Abstract. Our experimental design mimics a traditional evolutionary game framework where players are matched pairwise to play a symmetric 33 bimatrix game that has two Nash equilibria. One equilibrium is an evolutionary stable state, or ESS; the other is an equilibrium in dominated strategies. Our primary experimental result is the observation that the ESS becomes extremely attractive when subjects have minimal information about the payoff functions, although the dominated equilibrium assures the highest equilibrium payoff. The attractiveness of the ESS is only moderate when players are completely informed about the 33 payoff matrix. Correspondence to: S.K. Berninghaus     

The local best response criterion: An epistemic approach to equilibrium refinement

The standard refinement criteria for extensive form games, including subgame perfect, perfect, perfect Bayesian, sequential, and proper, reject important classes of reasonable Nash equilibria and accept many unreasonable Nash equilibria. This paper develops a new refinement criterion, based on epistemic game theory, that captures the concept of a Nash equilibrium that is plausible when players are rational. I call this the local best response (LBR) criterion. This criterion is conceptually simpler than the standard refinement criteria because it does not depend on out-of-equilibrium, counterfactual, or passage to the limit arguments. The LBR is also informationally richer because it clarifies the epistemic conditions that render a Nash equilibrium reasonable. The LBR criterion appears to render the traditional refinement criteria superfluous.     

Equivalence and Invariance of the Index and Degree of Nash Equilibria

Associated with each component of the Nash equilibria of a game are its index and degree. Its index is the local degree of the displacement map whose roots are the Nash equilibria of the game. Its degree is the local degree of the projection map from the Nash graph to the space of games. We show that the index and the degree of each component are the same. Further, they are invariant to adding or deleting redundant strategies, so they depend only on the reduced normal form of the game. Applications include Kohlberg and Mertens' existence theorems for stable sets and a simple procedure for calculating the degree of a component.Journal of Economic LiteratureClassification Number: C72.     

Adaptation and complexity in repeated games

The paper presents a learning model for two-player infinitely repeated games. In an inference step players construct minimally complex inferences of strategies based on observed play, and in an adaptation step players choose minimally complex best responses to an inference. When players randomly select an inference from a probability distribution with full support the set of steady states is a subset of the set of Nash equilibria in which only stage game Nash equilibria are played. When players make ‘cautious’ inferences the set of steady states is the subset of self-confirming equilibria with Nash outcome paths. When players use different inference rules, the set of steady states can lie between the previous two cases.     

Partial exposure in large games

In this work we introduce the notion of partial exposure, in which the players of a simultaneous-move Bayesian game are exposed to the realized types and chosen actions of a subset of the other players. We show that in any large simultaneous-move game, each player has very little regret even after being partially exposed to other players. If players are given the opportunity to be exposed to others at the expense of a small decrease in utility, players will decline this opportunity, and the original Nash equilibria of the game will survive.     

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.     

Co-ordination, Spillovers, and Cheap Talk

We analyze the role of cheap-talk in two player games with one-sided incomplete information. We identify conditions under which (1) players can fully communicate and coordinate on efficient Nash equilibria of the underlying complete information game; and (2) players cannot communicate so cheap-talk does not alter the equilibrium set of the Bayesian game. We present examples that illustrate several issues that arise when there is two-sided incomplete information. Journal of Economic Literature Classification Numbers: C72, D82.     

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.     

On the Irrelevance of Risk Attitudes in Repeated Two-Outcome Games

We study equilibrium and maximin play in supergames consisting of the sequential play of a finite collection of stage games, where each stage game has two outcomes for each player. We show that for two-player supergames in which each stage game is strictly competitive, in any Nash equilibrium of the supergame, play at each stage is a Nash equilibrium of the stage game provided preferences over certain supergame outcomes satisfy a natural monotonicity condition. In particular, equilibrium play does not depend on risk attitudes. We establish an invariance result for games with more than two players when the solution concept is subgame perfection. Journal of Economic Literature Classification Numbers: C72, C9.     

Robust equilibria under non-common priors

This paper considers the robustness of equilibria to a small amount of incomplete information, where players are allowed to have heterogeneous priors. An equilibrium of a complete information game is robust to incomplete information under non-common priors if for every incomplete information game where each player's prior assigns high probability on the event that the players know at arbitrarily high order that the payoffs are given by the complete information game, there exists a Bayesian Nash equilibrium that generates behavior close to the equilibrium in consideration. It is shown that for generic games, an equilibrium is robust under non-common priors if and only if it is the unique rationalizable action profile. Set-valued concepts are also introduced, and for generic games, a smallest robust set is shown to exist and coincide with the set of a posteriori equilibria.     

Equilibrium play in matches: Binary Markov games

We study two-person extensive form games, or “matches,” in which the only possible outcomes (if the game terminates) are that one player or the other is declared the winner. The winner of the match is determined by the winning of points, in “point games.” We call these matches binary Markov games. We show that if a simple monotonicity condition is satisfied, then (a) it is a Nash equilibrium of the match for the players, at each point, to play a Nash equilibrium of the point game; (b) it is a minimax behavior strategy in the match for a player to play minimax in each point game; and (c) when the point games all have unique Nash equilibria, the only Nash equilibrium of the binary Markov game consists of minimax play at each point. An application to tennis is provided.     

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.     

Reputation with observed actions

Summary A single long-run player plays a fixed stage game (simultaneous orsequential move) against an infinite sequence of short-run opponents that play only once but can observe all past realized actions. Assuming that the probability distributions over types of long and short-run players have full support, we show that the long-run player can always establish a reputation for theStackelberg strategy and is therefore guaranteed almost his Stackelberg payoff in all Nash equilibria of the repeated game.The financial support of the National Science Foundation, Grant SES 90-7999, and of Consiglio Nazionale delle Ricerche is gratefully acknowledged. I wish to thank David Levine, Wolfgang Pesendorfer and Seminar Participants at UCLA, Universidad Carlos III de Madrid and University of Naples for useful discussions and suggestions.     

Voluntary Contributions to Multiple Public Projects

The problem of financing a set of discrete public goods (facilities, projects) by private contributions is studied. The corresponding cooperative game, the realization game , is shown to be convex. For the noncooperative setting we study a realization scheme that induces a strategic game. This contribution game is shown to be a generalized ordinal potential game ; a best–response in the contribution game implies a best response in a coordination game in which the payoff to all players is the utilitarian collective welfare function, i.e., the sum of the utility functions of the players. Strategy profiles maximizing utilitarian welfare are strong Nash equilibria of the contribution game. Each strong Nash equilibrium corresponds in a natural way with a core element of the realization game, and vice versa. Moreover, each strong Nash equilibrium is coalitional proof.     

Walrasian analysis via two-player games

We associate to any pure exchange economy a game with only two players, regardless of the number of consumers. In this two-player game, each player represents a different role of the society, formed by all the individuals in the economy. Player 1 selects feasible allocations trying to make Pareto improvements. Player 2 chooses an alternative from the wider range of allocations that are feasible in the sense of Aubin. The set of Nash equilibria of our game is non-empty and our main result provides a characterization of Walrasian equilibria allocations as strong Nash equilibria of the associated society game.