Stochastic Learning Dynamics and Speed of Convergence in Population Games

We study how long it takes for large populations of interacting agents to come close to Nash equilibrium when they adapt their behavior using a stochastic better reply dynamic. Prior work considers this question mainly for 2 × 2 games and potential games; here we characterize convergence times for general weakly acyclic games, including coordination games, dominance solvable games, games with strategic complementarities, potential games, and many others with applications in economics, biology, and distributed control. If players' better replies are governed by idiosyncratic shocks, the convergence time can grow exponentially in the population size; moreover, this is true even in games with very simple payoff structures. However, if their responses are sufficiently correlated due to aggregate shocks, the convergence time is greatly accelerated; in fact, it is bounded for all sufficiently large populations. We provide explicit bounds on the speed of convergence as a function of key structural parameters including the number of strategies, the length of the better reply paths, the extent to which players can influence the payoffs of others, and the desired degree of approximation to Nash equilibrium.     

Strongly Consistent Self‐Confirming Equilibrium

Fudenberg and Levine (1993a) introduced the notion of self‐confirming equilibrium, which is generally less restrictive than Nash equilibrium. Fudenberg and Levine also defined a concept of consistency, and claimed in their Theorem 4 that with consistency and other conditions on beliefs, a self‐confirming equilibrium has a Nash equilibrium outcome. We provide a counterexample that disproves Theorem 4 and prove an alternative by replacing consistency with a more restrictive concept, which we call strong consistency. In games with observed deviators, self‐confirming equilibria are strongly consistent self‐confirming equilibria. Hence, our alternative theorem ensures that despite the counterexample, the corollary of Theorem 4 is still valid.     

Berk–Nash Equilibrium: A Framework for Modeling Agents With Misspecified Models

We develop an equilibrium framework that relaxes the standard assumption that people have a correctly specified view of their environment. Each player is characterized by a (possibly misspecified) subjective model, which describes the set of feasible beliefs over payoff‐relevant consequences as a function of actions. We introduce the notion of a Berk–Nash equilibrium: Each player follows a strategy that is optimal given her belief, and her belief is restricted to be the best fit among the set of beliefs she considers possible. The notion of best fit is formalized in terms of minimizing the Kullback–Leibler divergence, which is endogenous and depends on the equilibrium strategy profile. Standard solution concepts such as Nash equilibrium and self‐confirming equilibrium constitute special cases where players have correctly specified models. We provide a learning foundation for Berk–Nash equilibrium by extending and combining results from the statistics literature on misspecified learning and the economics literature on learning in games.     

Robust Predictions for Bilateral Contracting with Externalities

The paper studies bilateral contracting between one principal and N agents when each agent's utility depends on the principal's unobservable contracts with other agents. We show that allowing deviations to menu contracts from which the principal chooses bounds equilibrium outcomes in a wide class of bilateral contracting games without imposing ad hoc restrictions on the agents' beliefs. This bound yields, for example, competitive convergence as N →∞ in environments in which an appropriately‐defined notion of competitive equilibrium exists. We also examine the additional restrictions arising in two common bilateral contracting games: the “offer game” in which the principal makes simultaneous offers to the agents, and the “bidding game” in which the agents make simultaneous offers to the principal.     

Bayesian Learning,Smooth Approximate Optimal Behavior,and Convergence to ε‐Nash Equilibrium

In this paper, I construct players' prior beliefs and show that these prior beliefs lead the players to learn to play an approximate Nash equilibrium uniformly in any infinitely repeated slightly perturbed game with discounting and perfect monitoring. That is, given any ε > 0, there exists a (single) profile of players' prior beliefs that leads play to almost surely converge to an ε‐Nash equilibrium uniformly for any (finite normal form) stage game with slight payoff perturbation and any discount factor less than 1.     

Congestion games with mixed objectives

We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the (non-)existence of pure Nash equilibria (PNE), the convergence of improvement dynamics, the quality of equilibria and show the complexity of the decision problem. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.     

Identification and Estimation of a Discrete Game of Complete Information

We discuss the identification and estimation of discrete games of complete information. Following Bresnahan and Reiss (1990, 1991), a discrete game is a generalization of a standard discrete choice model where utility depends on the actions of other players. Using recent algorithms to compute all of the Nash equilibria to a game, we propose simulation‐based estimators for static, discrete games. We demonstrate that the model is identified under weak functional form assumptions using exclusion restrictions and an identification at infinity approach. Monte Carlo evidence demonstrates that the estimator can perform well in moderately sized samples. As an application, we study entry decisions by construction contractors to bid on highway projects in California. We find that an equilibrium is more likely to be observed if it maximizes joint profits, has a higher Nash product, uses mixed strategies, and is not Pareto dominated by another equilibrium.     

Reputation in Continuous‐Time Games

We study reputation dynamics in continuous‐time games in which a large player (e.g., government) faces a population of small players (e.g., households) and the large player's actions are imperfectly observable. The major part of our analysis examines the case in which public signals about the large player's actions are distorted by a Brownian motion and the large player is either a normal type, who plays strategically, or a behavioral type, who is committed to playing a stationary strategy. We obtain a clean characterization of sequential equilibria using ordinary differential equations and identify general conditions for the sequential equilibrium to be unique and Markovian in the small players' posterior belief. We find that a rich equilibrium dynamics arises when the small players assign positive prior probability to the behavioral type. By contrast, when it is common knowledge that the large player is the normal type, every public equilibrium of the continuous‐time game is payoff‐equivalent to one in which a static Nash equilibrium is played after every history. Finally, we examine variations of the model with Poisson signals and multiple behavioral types.     

Reinforcement‐based vs. Belief‐based Learning Models in Experimental Asymmetric‐information Games

This paper examines the abilities of learning models to describe subject behavior in experiments. A new experiment involving multistage asymmetric‐information games is conducted, and the experimental data are compared with the predictions of Nash equilibrium and two types of learning model: a reinforcement‐based model similar to that used by Roth and Erev (1995), and belief‐based models similar to the ‘cautious fictitious play’ of Fudenberg and Levine (1995, 1998) These models make predictions that are qualitatively similar cycling around the Nash equilibrium that is much more apparent than movement toward it. While subject behavior is not adequately described by Nash equilibrium, it is consistent with the qualitative predictions of the learning models. We examine several criteria for quantitatively comparing the predictions of alternative models. According to almost all of these criteria, both types of learning model outperform Nash equilibrium. According to some criteria, the reinforcement‐based model performs better than any version of the belief‐based model; according to others, there exist versions of the belief‐based model that outperform the reinforcement‐based model. The abilities of these models are further tested with respect to the results of other published experiments. The relative performance of the two learning models depends on the experiment, and varies according to which criterion of success is used. Again, both models perform better than equilibrium in most cases.     

IS THE ENDOWMENT EFFECT AN EXPECTATIONS EFFECT?

A hallmark result within behavioral economics is that individuals' choices are affected by current endowments. A recent theory due to Kőszegi and Rabin ( 2006 , Quarterly Journal of Economics, 121, 1133–1165) explains such endowment effect with a model of expectations‐based reference‐dependent preferences. Departing from past work, we conduct complementary experiments to disentangle expectations—verified probabilistic beliefs held by subjects—from other features of endowment—such as “assignment” to a good—hence allowing us to compare the effect of expectations with that of other variations. While mere assignment can affect choices, we do not find a large role in the effect for Kőszegi–Rabin expectations.     

EXPLAINING GIFT‐EXCHANGE—THE LIMITS OF GOOD INTENTIONS

This paper explores the limitations of intention‐based social preferences as an explanation of gift‐exchange between a firm and a worker. In a framework with one self‐interested and one reciprocal player, gift‐giving never arises in equilibrium. Instead, any equilibrium in a large class of multistage games must involve mutually unkind behavior of both players. Besides gift‐exchange, this class of games also includes moral hazard models and the rotten kid framework. Even though equilibrium behavior may appear positively reciprocal in some of these games, the self‐interested player never benefits from reciprocity. We discuss the relation of these results to the theoretical and empirical literature on gift‐exchange in employment relations.     

Competition for a Majority

We define the class of two‐player zero‐sum games with payoffs having mild discontinuities, which in applications typically stem from how ties are resolved. For such games, we establish sufficient conditions for existence of a value of the game, maximin and minimax strategies for the players, and a Nash equilibrium. If all discontinuities favor one player, then a value exists and that player has a maximin strategy. A property called payoff approachability implies existence of an equilibrium, and that the resulting value is invariant: games with the same payoffs at points of continuity have the same value and ɛ‐equilibria. For voting games in which two candidates propose policies and a candidate wins election if a weighted majority of voters prefer his proposed policy, we provide tie‐breaking rules and assumptions about voters' preferences sufficient to imply payoff approachability. These assumptions are satisfied by generic preferences if the dimension of the space of policies exceeds the number of voters; or with no dimensional restriction, if the electorate is sufficiently large. Each Colonel Blotto game is a special case in which each candidate allocates a resource among several constituencies and a candidate gets votes from those allocated more than his opponent offers; in this case, for simple‐majority rule we prove existence of an equilibrium with zero probability of ties.     

Cursed Equilibrium

There is evidence that people do not fully take into account how other people's actions depend on these other people's information. This paper defines and applies a new equilibrium concept in games with private information, cursed equilibrium, which assumes that each player correctly predicts the distribution of other players' actions, but underestimates the degree to which these actions are correlated with other players' information. We apply the concept to common‐values auctions, where cursed equilibrium captures the widely observed phenomenon of the winner's curse, and to bilateral trade, where cursedness predicts trade in adverse‐selections settings for which conventional analysis predicts no trade. We also apply cursed equilibrium to voting and signalling models. We test a single‐parameter variant of our model that embeds Bayesian Nash equilibrium as a special case and find that parameter values that correspond to cursedness fit a broad range of experimental datasets better than the parameter value that corresponds to Bayesian Nash equilibrium.     

Rushes in Large Timing Games

We develop a continuum player timing game that subsumes standard wars of attrition and pre‐emption games, and introduces a new rushes phenomenon. Payoffs are continuous and single‐peaked functions of the stopping time and stopping quantile. We show that if payoffs are hump‐shaped in the quantile, then a sudden “rush” of players stops in any Nash or subgame perfect equilibrium. Fear relaxes the first mover advantage in pre‐emption games, asking that the least quantile beat the average; greed relaxes the last mover advantage in wars of attrition, asking just that the last quantile payoff exceed the average. With greed, play is inefficiently late: an accelerating war of attrition starting at optimal time, followed by a rush. With fear, play is inefficiently early: a slowing pre‐emption game, ending at the optimal time, preceded by a rush. The theory predicts the length, duration, and intensity of stopping, and the size and timing of rushes, and offers insights for many common timing games.     

What Happens in the Field Stays in the Field: Exploring Whether Professionals Play Minimax in Laboratory Experiments

The minimax argument represents game theory in its most elegant form: simple but with stark predictions. Although some of these predictions have been met with reasonable success in the field, experimental data have generally not provided results close to the theoretical predictions. In a striking study, Palacios‐Huerta and Volij ( 2008 ) presented evidence that potentially resolves this puzzle: both amateur and professional soccer players play nearly exact minimax strategies in laboratory experiments. In this paper, we establish important bounds on these results by examining the behavior of four distinct subject pools: college students, bridge professionals, world‐class poker players, who have vast experience with high‐stakes randomization in card games, and American professional soccer players. In contrast to Palacios‐Huerta and Volij's results, we find little evidence that real‐world experience transfers to the lab in these games—indeed, similar to previous experimental results, all four subject pools provide choices that are generally not close to minimax predictions. We use two additional pieces of evidence to explore why professionals do not perform well in the lab: (i) complementary experimental treatments that pit professionals against preprogrammed computers and (ii) post‐experiment questionnaires. The most likely explanation is that these professionals are unable to transfer their skills at randomization from the familiar context of the field to the unfamiliar context of the lab.     

Tenable Strategy Blocks and Settled Equilibria

When people interact in familiar settings, social conventions usually develop so that people tend to disregard alternatives outside the convention. For rational players to usually restrict attention to a block of conventional strategies, no player should prefer to deviate from the block when others are likely to act conventionally and rationally inside the block. We explore two set‐valued concepts, coarsely and finely tenable blocks, that formalize this notion for finite normal‐form games. We then identify settled equilibria, which are Nash equilibria with support in minimal tenable blocks. For a generic class of normal‐form games, our coarse and fine concepts are equivalent, and yet they differ from standard solution concepts on open sets of games. We demonstrate the nature and power of the solutions by way of examples. Settled equilibria are closely related to persistent equilibria but are strictly more selective on an open set of games. With fine tenability, we obtain invariance under the insertion of a subgame with a unique totally mixed payoff‐equivalent equilibrium, a property that other related concepts have not satisfied.     

Efficiency in Repeated Games Revisited: The Role of Private Strategies

Most theoretical or applied research on repeated games with imperfect monitoring has focused on public strategies: strategies that depend solely on the history of publicly observable signals. This paper sheds light on the role of private strategies: strategies that depend not only on public signals, but also on players' own actions in the past. Our main finding is that players can sometimes make better use of information by using private strategies and that efficiency in repeated games can be improved. Our equilibrium private strategy for repeated prisoners' dilemma games consists of two states and has the property that each player's optimal strategy is independent of the other player's state.     

Who's Who in Networks. Wanted: The Key Player

Finite population noncooperative games with linear‐quadratic utilities, where each player decides how much action she exerts, can be interpreted as a network game with local payoff complementarities, together with a globally uniform payoff substitutability component and an own‐concavity effect. For these games, the Nash equilibrium action of each player is proportional to her Bonacich centrality in the network of local complementarities, thus establishing a bridge with the sociology literature on social networks. This Bonacich–Nash linkage implies that aggregate equilibrium increases with network size and density. We then analyze a policy that consists of targeting the key player, that is, the player who, once removed, leads to the optimal change in aggregate activity. We provide a geometric characterization of the key player identified with an intercentrality measure, which takes into account both a player's centrality and her contribution to the centrality of the others.     

Belief‐Free Equilibria in Games With Incomplete Information

We define belief‐free equilibria in two‐player games with incomplete information as sequential equilibria for which players' continuation strategies are best replies after every history, independently of their beliefs about the state of nature. We characterize a set of payoffs that includes all belief‐free equilibrium payoffs. Conversely, any payoff in the interior of this set is a belief‐free equilibrium payoff. The characterization is applied to the analysis of reputations.     

Bargaining,Reputation, and Equilibrium Selection in Repeated Games with Contracts

Consider a two‐person intertemporal bargaining problem in which players choose actions and offers each period, and collect payoffs (as a function of that period's actions) while bargaining proceeds. This can alternatively be viewed as an infinitely repeated game wherein players can offer one another enforceable contracts that govern play for the rest of the game. Theory is silent with regard to how the surplus is likely to be split, because a folk theorem applies. Perturbing such a game with a rich set of behavioral types for each player yields a specific asymptotic prediction for how the surplus will be divided, as the perturbation probabilities approach zero. Behavioral types may follow nonstationary strategies and respond to the opponent's play. In equilibrium, rational players initially choose a behavioral type to imitate and a war of attrition ensues. How much should a player try to get and how should she behave while waiting for the resolution of bargaining? In both respects she should build her strategy around the advice given by the “Nash bargaining with threats” (NBWT) theory developed for two‐stage games. In any perfect Bayesian equilibrium, she can guarantee herself virtually her NBWT payoff by imitating a behavioral type with the following simple strategy: in every period, ask for (and accept nothing less than) that player's NBWT share and, while waiting for the other side to concede, take the action Nash recommends as a threat in his two‐stage game. The results suggest that there are forces at work in some dynamic games that favor certain payoffs over all others. This is in stark contrast to the classic folk theorems, to the further folk theorems established for repeated games with two‐sided reputational perturbations, and to the permissive results obtained in the literature on bargaining with payoffs as you go.