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 the impossibility of achieving no regrets in repeated games

Regret-minimizing strategies for repeated games have been receiving increasing attention in the literature. These are simple adaptive behavior rules that lead to no regrets and, if followed by all players, exhibit nice convergence properties: the average play converges to correlated equilibrium, or even to Nash equilibrium in certain classes of games. However, the no-regret property relies on a strong assumption that each player treats her opponents as unresponsive and fully ignores the opponents’ possible reactions to her actions. We show that if at least one player is slightly responsive, it is impossible to achieve no regrets, and convergence results for regret minimization with responsive opponents are unknown.     

Self-tuning experience weighted attraction learning in games

Self-tuning experience weighted attraction (EWA) is a one-parameter theory of learning in games. It addresses a criticism that an earlier model (EWA) has too many parameters, by fixing some parameters at plausible values and replacing others with functions of experience so that they no longer need to be estimated. Consequently, it is econometrically simpler than the popular weighted fictitious play and reinforcement learning models. The functions of experience which replace free parameters “self-tune” over time, adjusting in a way that selects a sensible learning rule to capture subjects’ choice dynamics. For instance, the self-tuning EWA model can turn from a weighted fictitious play into an averaging reinforcement learning as subjects equilibrate and learn to ignore inferior foregone payoffs. The theory was tested on seven different games, and compared to the earlier parametric EWA model and a one-parameter stochastic equilibrium theory (QRE). Self-tuning EWA does as well as EWA in predicting behavior in new games, even though it has fewer parameters, and fits reliably better than the QRE equilibrium benchmark.     

Individual Differences in EWA Learning with Partial Payoff Information

We extend experience-weighted attraction (EWA) learning to games in which only the set of possible foregone payoffs from unchosen strategies are known, and estimate parameters separately for each player to study heterogeneity. We assume players estimate unknown foregone payoffs from a strategy, by substituting the last payoff actually received from that strategy, by clairvoyantly guessing the actual foregone payoff, or by averaging the set of possible foregone payoffs conditional on the actual outcomes. All three assumptions improve predictive accuracy of EWA. Individual parameter estimates suggest that players cluster into two separate subgroups (which differ from traditional reinforcement and belief learning).     

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.     

Limited Foresight May Force Cooperation

This paper considers discounted repeated games with boundedly rational players. In each period, player i chooses his current action on the basis of his forecast about the forthcoming n _i action profiles; his assessment of the payoffs he will obtain next depends on his state of mind, which is non-deterministic. A limited forecast equilibrium is such that after every history the limited horizon forecasts formed by the players are correct. The set of all limited forecast equilibria is characterized and constructed. Application to the repeated prisoner's dilemma shows that limited foresight may sometimes induce purely cooperative paths while purely non-cooperative paths cannot arise.     

Learning with perfect information

For extensive form games with perfect information, consider a learning process in which, at any iteration, each player unilaterally deviates to a best response to his current conjectures of others' strategies; and then updates his conjectures in accordance with the induced play of the game. We show that, for generic payoffs, the outcome of the game becomes stationary, and is consistent with Nash equilibrium. In general, if payoffs have ties or if players observe more of each others' strategies than is revealed by plays of the game, the same result holds provided a rationality constraint is imposed on unilateral deviations: no player changes his moves in subgames that he deems unreachable, unless he stands to improve his payoff there. Moreover, with this constraint, the sequence of strategies and conjectures also becomes stationary, and yields a self-confirming equilibrium.     

A Folk Theorem for Repeated Sequential Games

We study repeated sequential games where players may not move simultaneously in stage games. We introduce the concept of effective minimax for sequential games and establish a Folk theorem for repeated sequential games. The Folk theorem asserts that any feasible payoff vector where every player receives more than his effective minimax value in a sequential stage game can be supported by a subgame perfect equilibrium in the corresponding repeated sequential game when players are sufficiently patient. The results of this paper generalize those of Wen (1994), and of Fudenberg and Maskin (1986). The model of repeated sequential games and the concept of effective minimax provide an alternative view to the Anti–Folk theorem of Lagunoff and Matsui (1997) for asynchronously repeated pure coordination games.     

Communication in Repeated Games with Private Monitoring

The paper considers repeated games where each player can be observed by only a subset of the other players, and where players can make public announcements about the behavior of the players they observed. We address the following question: What is the minimal level of observability that is required to obtain efficient outcomes? The main result is that the limit set of sequential equilibrium payoffs, when the discount factor tends to one, contains the set of individual rational payoffs whenever each player is observed by at leasttwoother players.Journal of Economic LiteratureClassification Number: C73.     

Heterogeneous quantal response equilibrium and cognitive hierarchies

We explore an equilibrium model of games where behavior is given by logit response functions, but payoff responsiveness and beliefs about others' responsiveness are heterogeneous. We study two substantively different ways of extending quantal response equilibrium (QRE) to this setting: (1) Heterogeneus QRE, where players share identical correct beliefs about the distribution of payoff responsiveness; and (2) Truncated QRE, where players have downward looking beliefs, systematically underestimating others' responsiveness. We show that the cognitive hierarchy model is a special case of Truncated QRE. We conduct experiments designed to differentiate these approaches. We find significant evidence of payoff responsive stochastic choice, and of heterogeneity and downward looking beliefs in some games.     

An experimental analysis of ultimatum bargaining

There are many experimental studies of bargaining behavior, but suprisingly enough nearly no attempt has been made to investigate the so-called ultimatum bargaining behavior experimentally. The special property of ultimatum bargaining games is that on every stage of the bargaining process only one player has to decide and that before the last stage the set of outcomes is already restricted to only two results. To make the ultimatum aspect obvious we concentrated on situations with two players and two stages. In the ‘easy games’ a given amount c has to be distributed among the two players, whereas in the ‘complicated games’ the players have to allocate a bundle of black and white chips with different values for both players. We performed two main experiments for easy games as well as for complicated games. By a special experiment it was investigated how the demands of subjects as player 1 are related to their acceptance decisions as player 2.     

Farsightedness in a Coalitional Great Fish War

We explore the implications of the farsightedness assumption on the conjectures of players in a coalitional Great Fish War model with symmetric players, derived from the seminal model of Levhari and Mirman (Bell J Econ 11:649–661, 1980). The farsightedness assumption for players in a coalitional game acknowledges the fact that a deviation from a single player will lead to the formation of a new coalition structure as the result of possibly successive moves of her rivals in order to improve their payoffs. It departs from mainstream game theory in that it relies on the so-called rational conjectures, as opposed to the traditional Nash conjectures formed by players on the behavior of their rivals. For values of the biological parameter and the discount factor more plausible than the ones used in the current literature, the farsightedness assumption predicts a wide scope for cooperation in non-trivial coalitions, sustained by credible threats of successive deviations that defeat the shortsighted payoff of any prospective deviator. Compliance or deterrence of deviations may also be addressed by acknowledging that information on the fish stock or on the catch policies actually implemented may be available only with a delay (dynamic farsightedness). In that case, the requirements are stronger and the sizes and number of possible farsighted stable coalitions are different. In the sequential move version, which could mimic some characteristics of fishery models, the results are not less appealing, even if the dominant player or dominant coalition with first move advantage assumption provides a case for cooperation with the traditional Nash conjectures.     

Scaling Up Learning Models in Public Good Games

We study three learning rules (reinforcement learning (RL), experience weighted attraction learning (EWA), and individual evolutionary learning (IEL)) and how they perform in three different Groves–Ledyard mechanisms. We are interested in how well these learning rules duplicate human behavior in repeated games with a continuum of strategies. We find that RL does not do well, IEL does significantly better, as does EWA, but only if given a small discretized strategy space. We identify four main features a learning rule should have in order to stack up against humans in a minimal competency test: (1) the use of hypotheticals to create history, (2) the ability to focus only on what is important, (3) the ability to forget history when it is no longer important, and (4) the ability to try new things.     

The single deviation property in games with discontinuous payoffs

We study equilibrium existence in normal form games in which it is possible to associate with each nonequilibrium point an open neighborhood, a set of players, and a collection of deviation strategies, such that at any nonequilibrium point of the neighborhood, a player from the set can increase her payoff by switching to the deviation strategy designated for her. An equilibrium existence theorem for compact, quasiconcave games with two players is established as an application of a general equilibrium existence result for qualitative games. A new form of the better-reply security condition, called the strong single deviation property, is proposed.     

Cycling in a stochastic learning algorithm for normal form games

In this paper we study a stochastic learning model for 2×2 normal form games that are played repeatedly. The main emphasis is put on the emergence of cycles. We assume that the players have neither information about the payoff matrix of their opponent nor about their own. At every round each player can only observe his or her action and the payoff he or she receives. We prove that the learning algorithm, which is modeled by an urn scheme proposed by Arthur (1993), leads with positive probability to a cycling of strategy profiles if the game has a mixed Nash equilibrium. In case there are strict Nash equilibria, the learning process converges a.s. to the set of Nash equilibria.     

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.     

Directed Networks with Spillovers

We study noncooperative network formation in two types of directed networks. In the first type, called the model with global spillovers, the payoff of a player depends on the number of links she forms as well as the total number of links formed by all other players. In the second type, called the model with local spillovers, the payoff of a player depends on the number of links she forms and the total number of links formed by her immediate neighbors, as well as the number of links formed by players outside her neighborhood. For both classes of games we investigate the existence of pure strategy Nash equilibria and characterize the Nash networks under a number of different second order conditions on the payoff function.     

Learning with bounded memory in games

We study learning with bounded memory in zero-sum repeated games with one-sided incomplete information. The uninformed player has only a fixed number of memory states available. His strategy is to choose a transition rule from state to state, and an action rule, which is a map from each memory state to the set of actions. We show that the equilibrium transition rule involves randomization only in the intermediate memory states. Such randomization, or less frequent updating, is interpreted as a way of testing the opponent, which generates inertia in the player's behavior and is the main short-run bias in information processing exhibited by the bounded memory player.     

Dissertation abstract: Essays on veto bargaining games

This dissertation experimentally analyzes the outcomes of multilateral legislative bargaining games in the presence of a veto player. The first essay examines veto power—the right of an agent to unilaterally block decisions but without the ability to unilaterally secure his/her preferred outcome. Using Winter’s (1996) theoretical framework, I consider two cases: urgent committees where the total amount of money to be distributed shrinks by 50% if proposals do not pass and non-urgent committees where the total amount of money shrinks by 5% if proposals do not pass. Committees with a veto player take longer to reach decisions (are less efficient) than without a veto player and veto players proposals generate less consensus then non-veto players proposals, outcomes on which the theory is silent. In addition, veto power in conjunction with proposer power generates excessive power for the veto player. This suggests that limiting veto players’ proposer rights (e.g., limiting their ability to chair committees) would go a long way to curbing their power, a major concern in committees in which one or more players has veto power. Finally, non-veto players show substantially more willingness to compromise than veto players, with players in the control game somewhere in between. I relate the results to the theoretical literature on the impact of veto power as well as concerns about the impact of veto power in real-life committees. The second essay discusses in detail the voting patterns in the veto and control games reported in the first essay. The empirical cumulative density functions of shares veto players accepted first degree stochastically dominates that of shares for the controls and the empirical cdfs of shares the controls accepted first degree stochastically dominate that of shares for non-veto players. Random effect probits support this conclusion as well. In addition, regressions imply favorable treatment of voting and proposing between non-veto players which, however, does not result in larger shares in the end. Coalition partners consistently demand more than the stationary subgame perfect Nash equilibrium share except for veto players in non-urgent committees. JEL Classification C7, D7, C78, D72 Dissertation Committee: John H. Kagel, Advisor Massimo Morelli Alan Wiseman Stephen Cosslett     

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.