Learning in games with strategic complementarities revisited

Fictitious play is a classical learning process for games, and games with strategic complementarities are an important class including many economic applications. Knowledge about convergence properties of fictitious play in this class of games is scarce, however. Beyond games with a unique equilibrium, global convergence has only been claimed for games with diminishing returns [V. Krishna, Learning in games with strategic complementarities, HBS Working Paper 92-073, Harvard University, 1992]. This result remained unpublished, and it relies on a specific tie-breaking rule. Here we prove an extension of it by showing that the ordinal version of strategic complementarities suffices. The proof does not rely on tie-breaking rules and provides some intuition for the result.     

The Statistical Mechanics of Best-Response Strategy Revision

This paper compares local and global strategic interaction when players update using the (myopic) best-response rule. I show that randomizing the order in which players update their strategic choice suffices to achieve coordination on the risk-dominant strategy in symmetric 2 × 2 coordination games. The "persistant randomness" which is necessary to achieve similar coordination with global interaction is replaced under local interaction by spatial variation in the initial condition. An extension of the risk-dominance idea gives the same convergence result for K × K games with strategic complementarities. Similar results for K × K pure coordination games and potential games are also presented. Journal of Economic Literature Classification Number: C78.     

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.     

Two equivalence results for two-person strict games

A game is strict if for both players, different profiles have different payoffs. Two games are best response equivalent if their best response functions are the same. We prove that a two-person strict game has at most one pure Nash equilibrium if and only if it is best response equivalent to a strictly competitive game, and that it is best response equivalent to an ordinal potential game if and only if it is best response equivalent to a quasi-supermodular game.     

Equilibrium play and best response to (stated) beliefs in normal form games

We report experimental results on a series of ten one-shot two-person 3×3 normal form games with unique equilibrium in pure strategies played by non-economists. In contrast to previous experiments in which game theory predictions fail dramatically, a majority of actions taken coincided with the equilibrium prediction (70.2%) and were best-responses to subjects' stated beliefs (67.2%). In constant-sum games, 78% of actions taken were predicted by the equilibrium model, outperforming simple K-level reasoning models. We discuss how non-trivial game characteristics related to risk aversion, efficiency concerns and social preferences may affect the predictive value of different models in simple normal form games.     

Coordination between a sophisticated and fictitious player

Successful coordination is a common and important social problem. Achieving it relies on the players’ ability to accurately anticipate future choices from known information. Individuals may not only lack this cognitive ability, but differ in it. Fictitious Play is an adaptive behavior where a myopic best response to the historical play of an opponent is selected. I consider the interaction between a fictitious player and a sophisticated player in 2 × 2 coordination games. The existence of coordination, the selection of equilibria, and the payoffs generated are analyzed.     

A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence

This paper uses properties of the logistic quantal response equilibrium correspondence to compute Nash equilibria in finite games. It is shown that branches of the correspondence may be numerically traversed efficiently and securely. The method can be implemented on a multicomputer, allowing for application to large games. The path followed by the method has an interpretation analogous to that of Harsanyi and Selten's Tracing Proecdure. As an application, it is shown that the principal branch of any quantal response equilibrium correspondence satisfying a monotonicity property converges to the risk-dominant equilibrium in 2 × 2 games.     

Infection and immunization: A new class of evolutionary game dynamics

Building upon a central paradigm of evolutionary game theory, namely the invasion barrier, we propose the new Infection and Immunization Dynamics (InfImmDyn), modelling a plausible adaptation process in a large population. For general games, this yields a novel refinement of the Nash equilibrium concept based on dynamical arguments, close in spirit to Nash's original “mass action” idea in his Ph.D. thesis. For partnership games, InfImmDyn exhibits a better asymptotic behavior compared to other popular procedures like Fictitious Play and Replicator Dynamics. We establish even support separation of InfImmDyn in finite time, which can never be achieved by any interior-point method like those mentioned above. In fact, this property has not yet been established for any other evolutionary game dynamics.     

Best response equivalence

Two games are best-response equivalent if they have the same best-response correspondence. We provide a characterization of when two games are best-response equivalent. The characterizations exploit a dual relationship between payoff differences and beliefs. Some “potential game” arguments [Games Econ. Behav. 14 (1996) 124] rely only on the property that potential games are best-response equivalent to identical interest games. Our results show that a large class of games are best-response equivalent to identical interest games, but are not potential games. Thus we show how some existing potential game arguments can be extended.     

Unfolding Social Hierarchies

Consider a large population of finitely-lived agents organized into n different hierarchical levels. Every period, all those placed at each level are randomly matched to play a given symmetric game. Based on the resulting outcome, a ρ-fraction of agents who (within their own level) attain the highest payoffs are promoted upwards. On the other hand, newcomers replacing those who die every period enter at the lowest level and choose irreversibly the strategy to be played for the rest of their life. This choice is made, with some noise, by imitating one of the strategies adopted at the highest level.  In this setup, the unique long-run behavior of the system is fully characterized for the whole class of 2×2 coordination games and two alternative variations of the model. The results crucially depend on the key “institutional” parameters ρ and n. In particular, it is shown that inefficient behavior prevails in the long run (even when risk-dominated) if promotion is only mildly selective—high ρ—and the social system is quite hierarchical—large n. In a stylized manner, these parameter conditions may be viewed as reflecting a sort of institutional deficiency that impairs economic performance. Journal of Economic Literature Classification Numbers: C70, C72, C73, D72.     

The Core of Large Differentiable TU Games

For suitable non-atomic TU games ν, the core can be determined by computing appropriate derivatives of ν, yielding one of two stark conclusions: either core(ν) is empty or it consists of a single measure that can be expressed explicitly in terms of derivatives of ν. In this sense, core theory for a class of games may be reduced to calculus. Journal of Economic Literature Classification Number: C71.     

A characterization of strategic complementarities

I characterize games for which there is an order on strategies such that the game has strategic complementarities. I prove that, with some qualifications, games with a unique equilibrium have complementarities if and only if Cournot best-response dynamics has no cycles; and that all games with multiple equilibria have complementarities. As applications of my results, I show that: (1) generic 2×2 games either have no pure-strategy equilibria, or have complementarities; (2) generic two-player finite ordinal potential games have complementarities.     

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     

A family of supermodular Nash mechanisms implementing Lindahl allocations

Summary. We present a family of mechanisms which implement Lindahl allocations in Nash equilibrium. With quasilinear utility functions this family of mechanisms are supermodular games, which implies that they converge to Nash equilibrium under a wide class of learning dynamics. Received: April 27, 2000; revised version: January 16, 2001     

Strategic correlativity and network games

We consider the strategic correlativity principle in strategic form games and potential games, which indicate the relationship between an arbitrary pair of players under correlated equilibria. Importantly, the strategies of a pair of players are positively correlated when their expected payoff functions are supermodular, while negatively correlated when their expected payoff functions are submodular. Furthermore, we extend the strategic correlativity principle to strategic form games and potential games in social networks, and investigate the monotonicity of correlated equilibrium in each player's own degree.     

Hierarchical thinking and learning in rank order contests

We analyze a class of coordination games in which the Kth player to submit an entry wins a contest. These games have an infinite number of symmetric equilibria and the set of equilibria does not change with K. We run experiments with 15 participants and with K=3, 7, and 11. Our experiments show that the value of K affects initial submissions and convergence to equilibrium. When K is small relative to the number of participants, our experiments show that repeated play converges to or near zero. When K is large, an equilibrium is often not reached as a result of repeated play. We seek explanations to these patterns in hierarchical thinking and direction learning.      

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.     

Market Games in Large Economies with a Finite Number of Types

We study market games derived from an exchange economy with a continuum of agents, each having one of finitely many possible types. The type of agent determines his initial endowment and utility function. It is shown that, unlike the well-known Shapley–Shubik theorem on market games (Shapley and Shubik in J Econ Theory 1:9–25, 1969), there might be a (fuzzy) game in which each of its sub-games has a non-empty core and, nevertheless, it is not a market game. It turns out that, in order to be a market game, a game needs also to be homogeneous. We also study investment games – which are fuzzy games obtained from an economy with a finite number of agents cooperating in one or more joint projects. It is argued that the usual definition of the core is inappropriate for such a model. We therefore introduce and analyze the new notion of comprehensive core. This solution concept seems to be more suitable for such a scenario. We finally refer to the notion of feasibility of an allocation in games with a large number of players. Some of the results in this paper appear in a previous draft distributed by the name “Cooperative investment games or Population games”. An anonymous referee of Economic Theory is acknowledged for his/her comments     

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.