Binary Games with State Dependent Stochastic Choice

This paper studies a stochastic equilibrium selection model for binary coordination games. Players switch strategies stochastically so that the mistake probabilities are fully dependent on the population states. A probabilistic behavior is said to be aspiration (imitation, resp.) oriented if strategy switches are mainly driven by the aspiration (imitation, resp.) effect. In general, a strategy switch by one player generates externalities on others. Strategies in a coordination game can be classified according to the relative magnitude of their externality effects. It is shown that the selection outcome for a linear coordination game is determined in a specific way by the balance of the risk dominance, the aspiration/imitation, and the externality effects. It is also shown that an aspiration (imitation, resp.) oriented behavior tends to select payoff dominant (maxmin, resp.) equilibrium and that risk dominant equilibrium is always selected if and only if the aspiration and the imitation effects exactly cancel each other out, which in turn makes the selection process insensitive to externality effects. Journal of Economic Literature Classification Number: C72.     

Learning to play games in extensive form by valuation

Game theoretic models of learning which are based on the strategic form of the game cannot explain learning in games with large extensive form. We study learning in such games by using valuation of moves. A valuation for a player is a numeric assessment of her moves that purports to reflect their desirability. We consider a myopic player, who chooses moves with the highest valuation. Each time the game is played, the player revises her valuation by assigning the payoff obtained in the play to each of the moves she has made. We show for a repeated win-lose game that if the player has a winning strategy in the stage game, there is almost surely a time after which she always wins. When a player has more than two payoffs, a more elaborate learning procedure is required. We consider one that associates with each move the average payoff in the rounds in which this move was made. When all players adopt this learning procedure, with some perturbations, then, with probability 1 there is a time after which strategies that are close to subgame perfect equilibrium are played. A single player who adopts this procedure can guarantee only her individually rational payoff.     

Exploitable actions of believers in the “law of small numbers” in repeated constant-sum games

In repeated fixed-pair constant-sum games with unique equilibria in mixed strategies, such as matching pennies, the subgame perfect equilibrium is repeating the stage-game mixed-strategy equilibrium action. In such games rational players avoid strategies that are exploitable, in that current actions either deviate systematically from the equilibrium action probabilities or fail to be serially independent of past actions. I revisit classic experiments and find that subjects’ actions are sometimes exploitable because they are serially dependent. Subjects have difficulty in producing serially independent actions and in recognizing serially dependent sequences due to a bias called local representativeness.     

Match choice and Ghettoization in evolutionary games

I study how having a choice about who to play affects the conventions that arise in a population playing a 2×2 common interest game. Match choice allows agents playing “fragile but efficient” strategies to isolate themselves, raising their returns but making it harder for outsiders to duplicate their success. When agents are myopic, the second effect dominates: long run play can shift toward either the risk-dominant equilibrium (with common interests in matching) or toward the inefficient equilibrium (with opposing interests in matching). In contrast, when agents are patient, supra-Nash payoffs can be sustained.     

On Failing to Cooperate When Monitoring Is Private

I consider a repeated prisoners' dilemma where in each period, each player receives an imperfect private signal about his opponent's current action. I show that when players are patient enough, any equilibrium where players use trigger strategies (i.e., do not revert to cooperation once they have started defecting) yields players a value arbitrarily close to the mutual minimax. I also examine the robustness of the result to perturbations of the game. Journal of Economic Literature Classification Numbers: C72.     

Repeated games with one-memory

We study the extent to which equilibrium payoffs of discounted repeated games can be obtained by 1-memory strategies. We establish the following in games with perfect (rich) action spaces: First, when the players are sufficiently patient, the subgame perfect Folk Theorem holds with 1-memory. Second, for arbitrary level of discounting, all strictly enforceable subgame perfect equilibrium payoffs can be approximately supported with 1-memory if the number of players exceeds two. Furthermore, in this case all subgame perfect equilibrium payoffs can be approximately supported by an ε-equilibrium with 1-memory. In two-player games, the same set of results hold if an additional restriction is assumed: Players must have common punishments. Finally, to illustrate the role of our assumptions, we present robust examples of games in which there is a subgame perfect equilibrium payoff profile that cannot be obtained with 1-memory. Thus, our results are the best that can be hoped for.     

On the existence of subgame-perfect equilibrium in infinite-action games of perfect information

We study infinite-action games of perfect information with finitely or countably many players. It is assumed that payoff functions are continuous, strategy sets are compact, and constraint correspondences are continuous. Under these assumptions we prove the existence of subgame-perfect equilibria in pure strategies which are measurable functions. If for any date t, the subgame that is played from date t on depends on the history up to t only as this history affects some vector of “state” variables, then equilibrium strategies admit a “closed-loop” representation as measurable functions of the “state” trajectories.     

EVOLUTIONARY DRIFT IN PREFERENCE AND EQUILIBRIUM SELECTION*

This paper studies the situation where myopic players repeatedly face a society with two actions where their common fitness exhibits economies of scale. Both states in which all players choose the same actions are equilibria. In each period, players adjust their actions based on their preferences, which are in turn shaped by natural selection. The preferences of the players need not match the underlying fitness. When rare mutations are introduced into the evolutionary process, their preferences may drift without affecting equilibrium behaviour. This paper shows that these drifts influence the results of equilibrium selection.     

Coordination need not be a problem

In a game of common interest there is one action vector that all players prefer to every other. Yet there may be multiple Pareto-ranked Nash equilibria in the game and the “coordination problem” refers to the fact that rational equilibrium play cannot rule out Pareto-dominated equilibria. In this paper, I prove that two elements — asynchronicity and a finite horizon — are sufficient to uniquely select the Pareto-dominant action vector (in subgame perfect equilibrium play). Asynchronicity may be exogenously specified by the rules of the game. Alternatively, in a game where players choose when to move, asynchronicity may emerge as an equilibrium move outcome.     

A learning-based model of repeated games with incomplete information

This paper tests a learning-based model of strategic teaching in repeated games with incomplete information. The repeated game has a long-run player whose type is unknown to a group of short-run players. The proposed model assumes a fraction of ‘short-run’ players follow a one-parameter learning model (self-tuning EWA). In addition, some ‘long-run’ players are myopic while others are sophisticated and rationally anticipate how short-run players adjust their actions over time and “teach” the short-run players to maximize their long-run payoffs. All players optimize noisily. The proposed model nests an agent-based quantal-response equilibrium (AQRE) and the standard equilibrium models as special cases. Using data from 28 experimental sessions of trust and entry repeated games, including 8 previously unpublished sessions, the model fits substantially better than chance and much better than standard equilibrium models. Estimates show that most of the long-run players are sophisticated, and short-run players become more sophisticated with experience.     

On Learning to Cooperate

This paper shows that experimentation can have the effect of inducing outcomes that are “far” from Nash in a learning model similar to that studied by D. Fudenberg and D. K. Levine (1993, Econometrica61, 547-573). The game under consideration is a version of a finitely repeated prisoner's dilemma, and the average length of players' lifetimes is arbitrarily large, but fixed. If the number of stages in the prisoner's dilemma is sufficiently large, then experimentation induces cooperation within the society on an arbitrarily large scale, even though the beliefs of almost all players are eventually within an arbitrary η>0 of being correct at all of the information sets in the game. Journal of Economic Literature Classification Numbers: C72.     

Drugs,guns, and targeted competition

We consider a dynamic competition game involving three players, in which each player can vary the extent of his competition on a per-rival basis. We call such competition targeted. We show that if the players are myopic, then the weaker players eventually lose the game to their strongest rival. If instead the players are sufficiently far-sighted, then all three players converge in their power and stay in the game. We develop our model in application to drug wars, but the approach of targeted competition can be applied to competition between firms or political parties, or to warfare.     

How Communication Improves Efficiency in Bargaining Games

We study a double auction with two-sided private information and preplay communication, for which Myerson and Satterthwaite (1983, J. Econ. Theory28, 265–281) showed that all equilibria are inefficient and the Chatterjee–Samuleson linear equilibrium is most efficient. Like several others, we find that players use communication to surpass equilibrium levels of efficiency, especially when the communication is face-to-face. Our main contribution is an analysis of how communication helps the parties achieve such high levels of efficiency. We find that when preplay communication is allowed, efficiency above equilibrium levels is a result of what we call “dyadic” strategies that allow the parties to coordinate on a single price that reflects both parties' valuations. Journal of Economic Literature Classification Numbers: C78, D82.     

A Robust Folk Theorem for the Prisoner's Dilemma

We prove the folk theorem for the Prisoner's dilemma using strategies that are robust to private monitoring. From this follows a limit folk theorem: when players are patient and monitoring is sufficiently accurate, (but private and possibly independent) any feasible individually rational payoff can be obtained in sequential equilibrium. The strategies used can be implemented by finite (randomizing) automata. Journal of Economic Literature Classification Numbers: C72, C73, D82.     

Fault tolerance in large games

A Nash equilibrium is an optimal strategy for each player under the assumption that others play according to their respective Nash strategies, but it provides no guarantees in the presence of irrational players or coalitions of colluding players. In fact, no such guarantees exist in general. However, in this paper we show that large games are innately fault tolerant. We quantify the ways in which two subclasses of large games – λ-continuous games and anonymous games – are resilient against Byzantine faults (i.e. irrational behavior), coalitions, and asynchronous play. We also show that general large games have some non-trivial resilience against faults.     

Belief-Based Equilibria in the Repeated Prisoners' Dilemma with Private Monitoring

We analyze repeated prisoners' dilemma games with imperfect private monitoring and construct mixed trigger strategy equilibria. Such strategies have a simple representation, where a player's action only depends upon her belief that her opponent(s) are continuing to cooperate. When monitoring is almost perfect, the symmetric efficient outcome can be approximated in any prisoners' dilemma game, while every individually rational feasible payoff can be approximated in a class of such games. The efficiency result extends when there are more than two players. It requires that monitoring be sufficiently accurate but does not require very low discounting when a public randomization device is available. Journal of Economic Literature Classification Numbers: C73, D82.     

Cooperative interim contract and re-contract: Chandler's M-form firm

Summary. At an interim stage players possessing only their private information freely communicate with each other to coordinate their strategies. This results in a core strategy, which is interpreted as an equilibrium set of players' alternative type-contingent contract offers to their fellows. From this set of offers each player then chooses an optimal one and engages in some subsequent action, thus possibly revealing some private information to the others. Now with new information thus obtained from each other, the players play a new game to re-write their contract. In all of the optimization and gaming just described, Bayesian incentive compatibility plays a central role. These ideas are formulated within a model of a profit-center game with incomplete information which formally describes interaction of the asymmetrically informed profit-centers in Chandler's multidivisional firm. Received: May 17, 1996; revised version: January 14, 1997     

Professionals Play Minimax

The implications of the Minimax theorem are tested using natural data. The tests use a unique data set from penalty kicks in professional soccer games. In this natural setting experts play a one-shot two-person zero-sum game. The results of the tests are remarkably consistent with equilibrium play in every respect: (i) winning probabilities are statistically identical across strategies for players; (ii) players' choices are serially independent. The tests have substantial power to distinguish equilibrium play from disequilibrium alternatives. These results represent the first time that both implications of von Neumann's Minimax theorem are supported under natural conditions.     

Implementation,Elimination of Weakly Dominated Strategies and Evolutionary Dynamics

This paper studies convergence and stability properties of T. Sjöström's (1994, Games Econom. Behav.6, 502–511) mechanism, under the assumption that boundedly rational players find their way to equilibrium using monotonic evolutionary dynamics and best-reply dynamics. This mechanism implements most social choice functions in economic environments using as a solution concept one round of deletion of weakly dominated strategies and one round of deletion of strictly dominated strategies. However, there are other sets of Nash equilibria, whose payoffs may be very different from those desired by the social choice function. With monotonic dynamics, all these sets of equilibria contain limit points of the evolutionary dynamics. Furthermore, even if the dynamics converge to the “right” set of equilibria (i.e., the one which contains the solution of the mechanism), it may converge to an equilibrium which is worse in welfare terms. In contrast with this result, any interior solution of the best-reply dynamics converges to the equilibrium whose outcome the planner desires. Journal of Economic Literature Classification Numbers: C72, D70, D78.     

Testing threats in repeated games

Under most game-theoretic solution concepts, equilibrium beliefs are justified by off-equilibrium events. I propose an equilibrium concept for infinitely repeated games, called “Nash Equilibrium with Tests” (NEWT), according to which players can only justify their equilibrium beliefs with events that take place on the equilibrium path itself. In NEWT, players test every threat that rationalizes a future non-myopic action that they take. The tests are an integral part of equilibrium behavior. Characterization of equilibrium outcomes departs from the classical “folk theorems”. The concept provides new insights into the impact of self-enforcement norms, such as reciprocity, on long-run cooperation.