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.     

Finitely Many Players with Bounded Recall in Infinitely Repeated Games

We study the set of limit points of equilibrium payoffs in n-player repeated games, with bounded recall, when the memory capacities of all the players grow to infinity. Two main issues are explored: (i) whether differential information enables players to play correlatively, and (ii) the extent to which boundedly rational players can learn others′ behavior patterns and conceal their own. Journal of Economic Literature Classification Number: 026.     

Approximate efficiency in repeated games with correlated private signals

This paper presents repeated games with hidden moves, in which players receive imperfect private signals and are able to communicate. We propose a conditional probability approach to solve the learning problem in repeated games with correlated private signals and delayed communication. We then apply this approach to symmetric n-player games to obtain an approximate efficiency result.     

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.     

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.     

Coordination, “Magic,” and Reinforcement Learning in a Market Entry Game

Previous experimental studies have documented quick convergence to equilibrium play in market entry games with a large number of agents. The present study examines the effect of the available information in a 12-player game in an attempt to account for these findings. In line with the prediction of a simple reinforcement learning model (Roth and Erev, 1995,Games Econ. Behav.8, 164–212), quick convergence to equilibrium is observed even given minimal information (unknown payoff rule). However, in violation of the basic model, information concerning other players' payoff increases the number of entrants. The information effect can be described by a variant of the basic reinforcement learning model assuming that the additional information changes the player's reference point.Journal of Economic LiteratureClassification Number: C7, C92.     

Transient and asymptotic dynamics of reinforcement learning in games

Reinforcement learners tend to repeat actions that led to satisfactory outcomes in the past, and avoid choices that resulted in unsatisfactory experiences. This behavior is one of the most widespread adaptation mechanisms in nature. In this paper we fully characterize the dynamics of one of the best known stochastic models of reinforcement learning [Bush, R., Mosteller, F., 1955. Stochastic Models of Learning. Wiley & Sons, New York] for 2-player 2-strategy games. We also provide some extensions for more general games and for a wider class of learning algorithms. Specifically, it is shown that the transient dynamics of Bush and Mosteller's model can be substantially different from its asymptotic behavior. It is also demonstrated that in general—and in sharp contrast to other reinforcement learning models in the literature—the asymptotic dynamics of Bush and Mosteller's model cannot be approximated using the continuous time limit version of its expected motion.     

Stochastic imitation in finite games

In this paper we model an evolutionary process with perpetual random shocks, where individuals sample population-specific strategy-payoff pairs and imitate the most successful behavior. For finite n-player games we prove that in the limit, as the perturbations tend to zero, only strategy-tuples in minimal sets closed under single better replies will be played with positive probability. If the strategy-tuples in one such minimal set have strictly higher payoffs than all outside strategy-tuples, then the strategy-tuples in this set will be played with probability one in the limit, provided the minimal set is a product set and the sample is sufficiently large.     

Representing equilibrium aggregates in aggregate games with applications to common agency

An aggregate game is a normal-form game with the property that each playerʼs payoff is a function of only his own strategy and an aggregate of the strategy profile of all players. Such games possess properties that can often yield simple characterizations of equilibrium aggregates without requiring that one solves for the equilibrium strategy profile. When payoffs have a quasi-linear structure and a degree of symmetry, we construct a self-generating maximization program over the space of aggregates with the property that the solution set corresponds to the set of equilibrium aggregates of the original n-player game. We illustrate the value of this approach in common-agency games where the playersʼ strategy space is an infinite-dimensional space of nonlinear contracts. We derive equilibrium existence and characterization theorems for both the adverse selection and moral hazard versions of these games.     

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.     

On the folk theorem with one-dimensional payoffs and different discount factors

Proving the folk theorem in a game with three or more players usually requires imposing restrictions on the dimensionality of the stage-game payoffs. Fudenberg and Maskin (1986) assume full dimensionality of payoffs, while Abreu et al. (1994) assume the weaker NEU condition (“nonequivalent utilities”). In this note, we consider a class of n-player games where each player receives the same stage-game payoff, either zero or one. The stage-game payoffs therefore constitute a one-dimensional set, violating NEU. We show that if all players have different discount factors, then for discount factors sufficiently close to one, any strictly individually rational payoff profile can be obtained as the outcome of a subgame-perfect equilibrium with public correlation.     

Correlated Equilibrium in Stochastic Games

We study the existence of uniform correlated equilibrium payoffs in stochastic games. The correlation devices that we use are either autonomous (they base their choice of signal on previous signals, but not on previous states or actions) or stationary (their choice is independent of any data and is drawn according to the same probability distribution at every stage). We prove that any n-player stochastic game admits an autonomous correlated equilibrium payoff. When the game is positive and recursive, a stationary correlated equilibrium payoff exists. Journal of Economic Literature Classification Numbers: C72, C73.     

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.     

Correlated Nash equilibrium

We modify the epistemic conditions for Nash equilibrium only to accommodate Gilboa and Schmeidler's [I. Gilboa, D. Schmeidler, Maxmin expected utility with nonunique prior, J. Math. Econ. 18 (1989) 141-153] maxmin expected utility preferences, and identify the equilibrium concept in n-player strategic games that characterizes the modified epistemic conditions. The epistemic characterization supports the equilibrium concept as a minimal generalization of Nash equilibrium, in the sense that it deviates from Nash equilibrium only in terms of players' attitude towards ambiguity. Consequently, comparing it with Nash equilibrium constitutes a ceteris paribus study of the effects of ambiguity on how a game is played. For example, with ambiguity, (beliefs about) action choices are in general correlated.     

Abreu–Matsushima Mechanisms: Experimental Evidence

Abreu–Matsushima mechanisms can be applied to a broad class of games to induce any desired outcome as the unique rationalizable outcome. We conduct experiments investigating the performance of such mechanisms in two simple coordination games. In these games one pure-strategy equilibrium is “focal”; we assess the efficacy of Abreu–Matsushima mechanisms for implementing the other pure-strategy equilibrium outcome. Abreu–Matsushima mechanisms induce some choices consistent with the desired outcome, but more choices reflect the focal outcome. Moreover, “strengthening” the mechanism has a perverse effect when the desired outcome is a Pareto-dominated risk-dominated equilibrium.Journal of Economic LiteratureClassification Number: C7.     

Fictitious play in ‘one-against-all’ multi-player games

Summary. A compound game is an (n + 1) player game based on n two-person subgames. In each of these subgames player 0 plays against one of the other players. Player 0 is regulated, so that he must choose the same strategy in all n subgames. We show that every fictitious play process approaches the set of equilibria in compound games for which all subgames are either zero-sum games, potential games, or games. Received: July 18, 1997; revised version: December 4, 1998     

Contests with a stochastic number of players

We study Tullock's (1980) n-player contest when each player has an independent probability 0 < p 1 of participating. A unique symmetric equilibrium is found for any n and p and its properties are analyzed. In particular, we show that for a fixed n > 2 individual equilibrium spending as a function of p is single-peaked and satisfies a single-crossing property for any two different numbers of potential players. However, total equilibrium spending is monotonically increasing in p and n. We also demonstrate that ex-post over-dissipation is a feature of the pure-strategy equilibrium in our model. It turns out that if the contest designer can strategically decide whether to reveal the actual number of participating players or not, then the actual number of participants is always revealed.     

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.     

Regularity of pure strategy equilibrium points in a class of bargaining games

Summary. We develop an index theory for the Stationary Subgame Perfect (SSP) equilibrium set in a class of n-player sequential bargaining games with probabilistic recognition rules. For games with oligarchic voting rules (a class that includes unanimity rule), we establish conditions on individual utilities that ensure that for almost all discount factors, the number of SSP equilibria is odd and the equilibrium correspondence lower-hemicontinuous. For games with general, monotonic voting rules, we show generic (in discount factors) determinacy of SSP equilibria under the restriction that the agreement space is of dimension one. For non-oligarchic voting rules and agreement spaces of higher finite dimension, we establish generic determinacy for the subset of SSP equilibria in pure strategies. The analysis also extends to the case of fixed delay costs. Lastly, we provide a sufficient condition for uniqueness of SSP equilibrium in oligarchic games.Received: 13 May 2004, Revised: 1 March 2005, JEL Classification Numbers: C62, C72, C78.I thank John Duggan and participants of the 2003 annual meeting of the American Political Science Association, Philadelphia, PA, the Political Economy Seminar at Northwestern University, and the Economic Theory seminar at the University of Rochester for helpful comments.     

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.