Correlated equilibrium existence for infinite games with type-dependent strategies

Under study are games in which players receive private signals and then simultaneously choose actions from compact sets. Payoffs are measurable in signals and jointly continuous in actions. This paper gives a counter-example to the main step in Cotter?s [K. Cotter, Correlated equilibrium in games with type-dependent strategies, J. Econ. Theory 54 (1991) 48-69] argument for correlated equilibrium existence for this class of games, and supplies an alternative proof.     

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.     

Repeated signaling games

I analyze a class of repeated signaling games in which the informed player's type is persistent and the history of actions is perfectly observable. In this context, a large class of possibly complex sequences of signals can be supported as the separating equilibrium actions of the “strong type” of the informed player. I characterize the set of such sequences. I also characterize the sequences of signals in least cost separating equilibria (LCSE) of these games. In doing this, I introduce a state variable that can be interpreted as a measure of reputation. This gives the optimization problem characterizing the LCSE a recursive structure. I show that, in general, the equilibrium path sequences of signals have a simple structure. The shapes of the optimal sequences depend critically on the relative concavities of the payoff functions of different types, which measure the relative preferences towards payoff smoothing.     

Greediness and equilibrium in congestion games

We study the class of congestion games for which the set of Nash equilibrium is equivalent to the set of strategy profiles played by greedy myopic players. We show these two coincide iff such games are played over extension-parallel graphs.     

On games with identical equilibrium payoffs

Summary. This paper compares the sets of Nash, coalition- proof Nash and strong Nash equilibrium payoffs of normal form games which are closely related. We propose sufficient conditions for equivalent or closely related games to have identical sets of equilibrium payoffs. Received: April 23, 1999; revised version: November 23, 1999     

Strongly robust equilibrium and competing-mechanism games

This paper formulates the notion of a strongly robust equilibrium relative to a set of mechanisms specified in any competing-mechanism game of complete information with multiple principals and multiple agents. It shows that when agents’ efforts are contractible, any strongly robust pure-strategy equilibrium relative to single-incentive contracts persists, regardless of the continuation equilibrium that agents play upon any principal's deviation to any complex mechanism.     

Scale functions in equilibrium selection games

We present here an evolutionary game model, and address the issue of equilibrium selection working with the scale function of a diffusion process describing the dynamics of population processes with mutation modeled as white noise. This model is the same as the one in Foster and Young (1990) but with a different interpretation at the boundaries and with different mutation modelings. First, we justifiably assume that the boundaries of the solution of the stochastic differential equation are absorbing so that the first boundary of the interval [0,1] hit will determine the equilibrium selected. Then, working with the scale function, we obtain for 2×2 symmetric games and different mutation parameters, some new and interesting equilibrium selection results. The aim of this article is to describe another method of approach in evolutionary games with mutation which we believe will prove to be very useful in studying more general normal form games and different mutation modelings.     

The equilibrium set of two-player games with complementarities is a sublattice

Summary. I prove that the equilibrium set in a two-player game with complementarities, and totally ordered strategy spaces, is a sublattice of the joint strategy space. Received: May 31, 2001; revised version: October 4, 2002     

Fast convergence in evolutionary equilibrium selection

Stochastic best response models provide sharp predictions about equilibrium selection when the noise level is arbitrarily small. The difficulty is that, when the noise is extremely small, it can take an extremely long time for a large population to reach the stochastically stable equilibrium. An important exception arises when players interact locally in small close-knit groups; in this case convergence can be rapid for small noise and an arbitrarily large population. We show that a similar result holds when the population is fully mixed and there is no local interaction. Moreover, the expected waiting times are comparable to those in local interaction models.     

On equilibrium existence in payoff secure games

We propose a single framework for studying the existence of approximate and exact pure strategy equilibria in payoff secure games. Central to the framework is the notion of a multivalued mapping with the local intersection property. By means of the Fan-Browder collective fixed point theorem, we first show an approximate equilibrium existence theorem that covers a number of known games. Then a short proof of Reny’s (Econometrica 67:1029–1056, 1999) equilibrium existence theorem is provided for payoff secure games with metrizable strategy spaces. We also give a simple proof of Reny’s theorem in its general form for metric games in an appendix for the sake of completeness.     

An equilibrium closure result for discontinuous games

For games with discontinuous payoffs Simon and Zame (Econometrica 58:861–872, 1990) introduced payoff indeterminacy, in the form of endogenous sharing rules, which are measurable selections of a certain payoff correspondence. Their main result concerns the existence of a mixed Nash equilibrium and an associated sharing rule. Its proof is based on a discrete approximation scheme “from within” the payoff correspondence. Here, we present a new, related closure result for games with possibly noncompact action spaces, involving a sequence of Nash equilibria. In contrast to Simon and Zame (Econometrica 58:861–872, 1990), this result can be used for more involved forms of approximation, because it contains more information about the endogenous sharing rule. With such added precision, the closure result can be used for the actual computation of endogenous sharing rules in games with discontinuous payoffs by means of successive continuous interpolations in an approximation scheme. This is demonstrated for a Bertrand type duopoly game and for a location game already considered by Simon and Zame. Moreover, the main existence result of Simon and Zame (Econometrica 58:861–872, 1990) follows in two different ways from the closure result.     

Nash equilibrium in games with incomplete preferences

Summary. This paper investigates Nash equilibrium under the possibility that preferences may be incomplete. I characterize the Nash-equilibrium-set of such a game as the union of the Nash-equilibrium-sets of certain derived games with complete preferences. These games with complete preferences can be derived from the original game by a simple linear procedure, provided that preferences admit a concave vector-representation. These theorems extend some results on finite games by Shapley and Aumann. The applicability of the theoretical results is illustrated with examples from oligopolistic theory, where firms are modelled to aim at maximizing both profits and sales (and thus have multiple objectives). Mixed strategy and trembling hand perfect equilibria are also discussed.Received: 22 September 2003, Revised: 24 June 2004, JEL Classification Numbers: D11, C72, D43.I would like to thank Jean-Pierre Benôit, Juan Dubra, Alejandrio Jofre, Debraj Ray, Kim-Sau Chung and the seminar participants at NYU and at the Universidad de Chile for their comments. I am most grateful to Efe Ok, for his comments, criticism, suggestions and questions.     

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.     

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.     

Generic determinacy of Nash equilibrium in network-formation games

This paper proves the generic determinacy of Nash equilibrium in network-formation games: for a generic assignment of utilities to networks, the set of probability distributions on networks induced by Nash equilibria is finite.     

The structure of the Nash equilibrium sets of standard 2-player games

Summary. In this paper I study a class of two-player games, in which both players action sets are [0,1] and their payoff functions are continuous in joint actions and quasi-concave in own actions. I show that a no-improper-crossing condition is both necessary and sufficient for a finite subset A of to be the set of Nash equilibria of such a game.Received: 21 November 2002, Revised: 9 September 2004, JEL Classification Numbers: C65, C72.I am grateful to an editor of the journal and an anonymous referee for their very helpful comments. I also would like to thank the seminar participants at City University of Hong Kong, Georgia State University, Northwestern University, and Rice University.     

Uniqueness of equilibrium for smooth multistage concave games

Smooth, noncooperative, multistage, concave games are formulated so that a new uniqueness condition—based on the Poincaré-Hopf theorem—can be applied. The new condition is the weakest to appear in the uniqueness literature. The uniqueness subgame perfect equilibrium is obtained and examples are given.     

The convergence of least squares learning in stochastic temporary equilibrium models

Summary. This paper provides conditions for the almost sure convergence of the least squares learning rule in a stochastic temporary equilibrium model, where regressions are performed on the past values of the endogenous state variable. In contrast to earlier studies, (Evans and Honkapohja, 1998; Marcent and Sargent, 1989), which were local analyses, the dynamics are studied from a global viewpoint, which allows one to obtain an almost sure convergence result without employing projection facilities. Received: April 7, 2001; revised version: September 5, 2001     

Non-computable strategies and discounted repeated games

Summary A number of authors have used formal models of computation to capture the idea of bounded rationality in repeated games. Most of this literature has used computability by a finite automaton as the standard. A conceptual difficulty with this standard is that the decision problem is not closed. That is, for every strategy implementable by an automaton, there is some best response implementable by an automaton, but there may not exist any algorithm forfinding such a best response that can be implemented by an automaton. However, such algorithms can always be implemented by a Turing machine, the most powerful formal model of computation. In this paper, we investigate whether the decision problem can be closed by adopting Turing machines as the standard of computability. The answer we offer is negative. Indeed, for a large class of discounted repeated games (including the repeated Prisoner's Dilemma) there exist strategies implementable by a Turing machine for whichno best response is implementable by a Turing machine.The work was begun while Nachbar was a visitor at The Center for Mathematical studies in Economics and Management Science at Northwestern University; he is grateful for their hospitality. We are also grateful to Robert Anderson and Neil Gretsky and to seminar audiences at UCLA for useful comments, and to the National Science Foundation and the UCLA Academic Senate Committee on Research for financial support. This paper is an outgrowth of work reported in Learning and Computability in Discounted Supergames.