Infinite horizon common interest games with perfect information

We consider infinite horizon common interest games with perfect information. A game is a K-coordination game if each player can decrease other players' payoffs by at most K times his own cost of punishment. The number K represents the degree of commonality of payoffs among the players. The smaller K is, the more interest the players share. A K-coordination game tapers off if the greatest payoff variation conditional on the first t periods of an efficient history converges to 0 at a rate faster than K^−t as t→∞. We show that every subgame perfect equilibrium outcome is efficient in any tapering-off game with perfect information. Applications include asynchronously repeated games, repeated games of extensive form games, asymptotically finite horizon games, and asymptotically pure coordination games.     

Convergence and approximation results for non-cooperative Bayesian games: Learning theorems

Summary LetT denote a continuous time horizon and {G ^t :tT} be a net (generalized sequence) of Bayesian games. We show that: (i) if {x ^t : tT} is a net of Bayesian Nash Equilibrium (BNE) strategies for G^t we can extract a subsequence which converges to a limit full information BNE strategy for a one shot limit full information Bayesian game, (ii) If {x ^t : tT} is a net of approximate or _t-BNE strategies for the game G^t we can still extract a subsequence which converges to the one shot limit full information equilibrium BNE strategy, (iii) Given a limit full information BNE strategy of a one shot limit full information Bayesian game, we can find a net of _t-BNE strategies {x ^t : tT} in {G ^t :tT} which converges to the limit full information BNE strategy of the one shot game.We wish to thank Larry Blume, Mark Feldman, Jim Jordan, Charlie Kahn, Stefan Krasa, Gregory Michalopoulos, Wayne Shafer, Bart Taub, and Anne Villamil for several useful discussions. The financial support of the University of Illinois at Urbana-Champaign Campus Research Board is gratefully acknowledged.     

The One-Shot-Deviation Principle for Sequential Rationality

This article analyzes the fictitious play process originally proposed for strategic form games by Brown (1951) and Robinson (1951). We interpret the process as a model of preplay thinking performed by players before acting in a one-shot game. This model is one of bounded rationality. We discuss how fictitious play should then be defined for extensive form games and conclude that this is somewhat problematic. We therefore study two alternative definitions. For either of these, under a weak condition of initial uncertainty, a convergence point of a fictitious play sequence is a sequential equilibrium. For generic games of perfect information initial uncertainty also implies convergence of fictitious play.Journal of Economic LiteratureClassification Number: C72.     

Fictitious Play in Extensive Form Games

This article analyzes the fictitious play process originally proposed for strategic form games by Brown (1951) and Robinson (1951). We interpret the process as a model of preplay thinking performed by players before acting in a one-shot game. This model is one of bounded rationality. We discuss how fictitious play should then be defined for extensive form games and conclude that this is somewhat problematic. We therefore study two alternative definitions. For either of these, under a weak condition of initial uncertainty, a convergence point of a fictitious play sequence is a sequential equilibrium. For generic games of perfect information initial uncertainty also implies convergence of fictitious play.Journal of Economic LiteratureClassification Number: C72.     

Fictitious play in 2×n games

It is known that every discrete-time fictitious play process approaches equilibrium in nondegenerate 2×2 games, and that every continuous-time fictitious play process approaches equilibrium in nondegenerate 2×2 and 2×3 games. It has also been conjectured that convergence to the set of equilibria holds generally for nondegenerate 2×n games. We give a simple geometric proof of this for the continuous-time process, and also extend the result to discrete-time fictitious play.     

Dynamics in near-potential games

We consider discrete-time learning dynamics in finite strategic form games, and show that games that are close to a potential game inherit many of the dynamical properties of potential games. We first study the evolution of the sequence of pure strategy profiles under better/best response dynamics. We show that this sequence converges to a (pure) approximate equilibrium set whose size is a function of the “distance” to a given nearby potential game. We then focus on logit response dynamics, and provide a characterization of the limiting outcome in terms of the distance of the game to a given potential game and the corresponding potential function. Finally, we turn attention to fictitious play, and establish that in near-potential games the sequence of empirical frequencies of player actions converges to a neighborhood of (mixed) equilibria, where the size of the neighborhood increases according to the distance to the set of potential 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.     

Learning Dynamics in Games with Stochastic Perturbations

Consider a generalization of fictitious play in which agents′ choices are perturbed by incomplete information about what the other side has done, variability in their payoffs, and unexplained trembles. These perturbed best reply dynamics define a nonstationary Markov process on an infinite state space. It is shown, using results from stochastic approximation theory, that for 2 × 2 games it converges almost surely to a point that lies close to a stable Nash equilibrium, whether pure or mixed. This generalizes a result of Fudenherg and Kreps, who demonstrate convergence when the game has a unique mixed equilibrium. Journal of Economic Literature Classification Numbers: 000, 000, 000.     

On the Coalition-Proofness of the Pareto Frontier of the Set of Nash Equilibria

This article shows that the Pareto efficient frontier of the Nash equilibrium set of games with strategic substitutes is coalition-proof under the following conditions: (1) the game has three players, or, alternatively, a player's payoff depends on her own strategy and on the sum (but not on the composition) of other players' strategies; (2) an increase in a player's strategy either raises all other players' payoffs monotonically or reduces them monotonically; and (3) each player's payoff is strictly concave in her own strategy. Under these conditions, the Pareto dominance refinement is equivalent to the coalition-proof Nash equilibrium refinement.Journal of Economic LiteratureClassification Number: C72.     

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.     

Sowing Doubt Optimally in Two-Person Repeated Games

Consider a two-person repeated game, where one of the players, P1, can sow doubt, in the mind of his opponent, as to what P1's payoffs are. This results in a two-person repeated game with incomplete information. By sowing doubt, P1 can sometimes increase his minimal equilibrium payoff in the original game. We prove that this minimum is maximal when only one payoff matrix, the negative of the payoff matrix of the opponent, is added (the opponent thus believes that he might play a zero-sum game). We obtain two formulas for calculating this maximal minimum payoff. Journal of Economic Literature Classification Numbers: C7, D8.     

The Partnered Core of a Game without Side Payments

A payoff for a game is partnered if it admits no asymmetric dependencies. We introduce the partnered core of a game without side payments and show that the partnered core of a balanced game is nonempty. The result is a strengthening of Scarf's Theorem on the nonemptiness of the core of a balanced game without side payments. In addition, it is shown that if there are at most a countable number of points in the partnered core of a game then at least one core point isminimallypartnered, meaning that no player requires any other player in particular to obtain his part of the core payoff.Journal of Economic LiteratureClassification Number: C71.     

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.     

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.     

Stochastic better-reply dynamics in finite games

In this paper, we analyze a model where individuals from finite populations are repeatedly drawn to play a finite game and in every period choose a weakly better reply to a sample distribution from a finite history of past play. For all finite games and sufficiently incomplete information, we prove convergence to minimal sets closed under better replies. This result complements previous findings in a deterministic continuous-time framework and implies convergence to strict Nash equilibria in many well-known classes of games.     

Minimum Memory for Equivalence between Ex Ante Optimality and Time-Consistency

I give a necessary and sufficient condition on memory of a player in an extensive game for equivalence between ex ante optimality and time-consistency (for all payoff assignments). The condition is called A-loss recall and requires that each loss of a player's memory can be traced back to some loss of memory of his own action. A-loss recall is also shown to be a necessary and sufficient condition for the existence of a time-consistent strategy (for all payoff assignments) if the player is conscious-minded. Journal of Economic Literature Classification Numbers: C72, D80.     

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     

A decomposition algorithm for N-player games

An N-player game can be decomposed by adding a coordinator who interacts bilaterally with each player. The coordinator proposes profiles of strategies to the players, and his payoff is maximized when players’ optimal replies agree with his proposal. When the feasible set of proposals is finite, a solution of an associated linear complementarity problem yields an equilibrium of the approximate game and thus an approximate equilibrium of the original game. Computational efficiency is improved by using vertices of a triangulation of the players’ strategy space for the coordinator’s pure strategies. Computational experience is reported.     

Conditional Universal Consistency

Players choose an action before learning an outcome chosen according to an unknown and history-dependent stochastic rule. Procedures that categorize outcomes, and use a randomized variation on fictitious play within each category are studied. These procedures are “conditionally consistent:” they yield almost as high a time-average payoff as if the player knew the conditional distributions of actions given categories. Moreover, given any alternative procedure, there is a conditionally consistent procedure whose performance is no more than epsilon worse regardless of the discount factor. We also discuss cycles, and argue that the time-average of play should resemble a correlated equilibrium. Journal of Economic Literature Classification Numbers: C72, C73, C63, D83.