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.     

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.     

Equilibrium play in matches: Binary Markov games

We study two-person extensive form games, or “matches,” in which the only possible outcomes (if the game terminates) are that one player or the other is declared the winner. The winner of the match is determined by the winning of points, in “point games.” We call these matches binary Markov games. We show that if a simple monotonicity condition is satisfied, then (a) it is a Nash equilibrium of the match for the players, at each point, to play a Nash equilibrium of the point game; (b) it is a minimax behavior strategy in the match for a player to play minimax in each point game; and (c) when the point games all have unique Nash equilibria, the only Nash equilibrium of the binary Markov game consists of minimax play at each point. An application to tennis is provided.     

Impermanent types and permanent reputations

We study the impact of unobservable stochastic replacements for the long-run player in the classical reputation model with a long-run player and a series of short-run players. We provide explicit lower bounds on the Nash equilibrium payoffs of a long-run player, both ex-ante and following any positive probability history. Under general conditions on the convergence rates of the discount factor to one and of the rate of replacement to zero, both bounds converge to the Stackelberg payoff if the type space is sufficiently rich. These limiting conditions hold in particular if the game is played very frequently.     

Reinterpreting mixed strategy equilibria: a unification of the classical and Bayesian views

We provide a new interpretation of mixed strategy equilibria that incorporates both von Neumann and Morgenstern's classical concealment role of mixing, as well as the more recent Bayesian view originating with Harsanyi. For any two-person game, G, we consider an incomplete information game, in which each player's type is the probability he assigns to the event that his mixed strategy in G is “found out” by his opponent. We show that, generically, any regular equilibrium of G can be approximated by an equilibrium of in which almost every type of each player is strictly optimizing. This leads us to interpret i's equilibrium mixed strategy in G as a combination of deliberate randomization by i together with uncertainty on j's part about which randomization i will employ. We also show that such randomization is not unusual: for example, i's randomization is nondegenerate whenever the support of an equilibrium contains cyclic best replies.     

Cyber Technology and the Arms Race

Cyber technology represents digital military capability with the purpose of causing damage to the military strength of a potential enemy. War using conventional weapons may be preceded by a strike using cyber technology. This paper introduces such technology into the theory of conflicts. The cost of war relative to the payoff from victory turns out to be crucial for the results on armament decisions. In the war game, two types of Nash equilibria may arise. One is subject to warfare while the other is not (‘equilibrium of terror’), depending on the perceived cost of war. In a symmetric war game, cyber capabilities are neutral with respect to the investments in conventional weapons, but they make wars more likely. Asymmetric access to cyber technology limits the international arms race with conventional weapons. A low success probability in the cyber programme encourages exercising the cyberattack option as the enemy may not have access to cyber capability. Uncertainty of the success of a cyber programme makes countries cautious when allocating resources not only to these programmes but also in conventional armament.     

Reputation and Perfection in Repeated Common Interest Games

We consider a wide class of repeated common interest games perturbed with one-sided incomplete information: one player (the informed player) might be a commitment type playing the Pareto dominant action. As discounting, which is assumed to be symmetric, and the prior probability of the commitment type go to zero, it is shown that the informed player can be held close to her minmax payoff even when perfection is imposed on the equilibrium.Journal of Economic LiteratureClassification Numbers: C73, D83.     

A spectrum of equilibration processes in game theory

In game theory, four dynamic processes converging towards an equilibrium are distinguished and ordered by way of agents' decreasing cognitive capacities. In the eductive process, each player has enough information to simulate perfectly the others' behavior and gets immediately to the equilibrium. In epistemic learning, each player updates his beliefs about others' future strategies, with regard to their sequentially observed actions. In behavioral learning, each player modifies his own strategies according to the observed payoffs obtained from his past actions. In the evolutionary process, each agent has a fixed strategy and reproduces in proportion to the utilities obtained through stochastic interactions. All along the spectrum, longer term dynamics makes up for weaker rationality, and physical relations substitute for mental interactions. Convergence, if any, is towards an always stronger equilibrium notion and selection of an equilibrium state becomes more sensitive to context and history. The processes can be mixed if associated to different periods, agents or mechanisms and deepened if obtained by formal reasoning principles.     

On the Relationship between Risk-Dominance and Stochastic Stability

In a 2 × 2 symmetric game with two symmetric equilibria, one risk-dominates another if and only if the equilibrium strategy is a unique best response to any mixture that gives itself at least a probability of one-half. In a two-person strategic form game, we call a Nash equilibriumglobally risk-dominantif it consists of strategies such that each one of them is a unique best response to any mixture that gives the other at least a probability of one-half. We show that if a weakly acyclic two-person game has a globally risk-dominant equilibrium, then this is the one that is selected by the stochastic equilibrium selection process of Young.Journal of Economic LiteratureClassification Numbers: C72, C73.     

Robust equilibria under non-common priors

This paper considers the robustness of equilibria to a small amount of incomplete information, where players are allowed to have heterogeneous priors. An equilibrium of a complete information game is robust to incomplete information under non-common priors if for every incomplete information game where each player's prior assigns high probability on the event that the players know at arbitrarily high order that the payoffs are given by the complete information game, there exists a Bayesian Nash equilibrium that generates behavior close to the equilibrium in consideration. It is shown that for generic games, an equilibrium is robust under non-common priors if and only if it is the unique rationalizable action profile. Set-valued concepts are also introduced, and for generic games, a smallest robust set is shown to exist and coincide with the set of a posteriori equilibria.     

Type correlated equilibria for games with payoff uncertainty

Summary Aumann's notion of correlated equilibrium is extended to games with payoff uncertainty. A type correlated equilibrium is a correlated equilibrium for Harsanyi's game in player-types. An equivalent definition is a probability distribution over types and actions which is consistent with the prior distribution over types, such that when each player observes its type and action, the observed action is optimal and no further information about other players' types is obtained. Any such equilibrium can be implemented by a type-independent correlation device when players' observations may be type-dependent. The type correlated equilibrium correspondence is shown to be upperhemicontinuous with respect to player information.Support from NSF grant IRI-8609208 is gratefully acknowledged. I am grateful to Maxwell Stinchcombe for comments on an earlier draft of this paper. Any remaining errors are my own.     

Nash equilibrium when players account for the complexity of their forecasts

Nash equilibrium is often interpreted as a steady state in which each player holds the correct expectations about the other players' behavior and acts rationally. This paper investigates the robustness of this interpretation when there are small costs associated with complicated forecasts. The model consists of a two-person strategic game in which each player chooses a finite machine to implement a strategy in an infinitely repeated 2×2 game with discounting. I analyze the model using a solution concept called Nash Equilibrium with Stable Forecasts (ESF). My main results concern the structure of equilibrium machine pairs. They provide necessary and sufficient conditions on the form of equilibrium strategies and plays. In contrast to the “folk theorem,” these structural properties place severe restrictions on the set of equilibrium paths and payoffs. For example, only sequences of the one-shot Nash equilibrium can be generated by any ESF of the repeated game of chicken.     

Alternating-Offer Bargaining with Two-Sided Incomplete Information

I study alternating-offer bargaining games with two-sided incomplete information about the players' discount rates. For both perfect Bayesian equilibrium and a rationalizability-style notion, I characterize the set of expected payoffs which may arise in the game. I also construct bounds on agreements that may be made. The set of expected payoffs is easy to compute and incorporate into applied models. My main result is a full characterization of the set of perfect Bayesian equilibrium payoffs for games in which the distribution over the players' discount rates is of wide support, yet is in a weak sense close to a point mass distribution. I prove a lopsided convergence result: each player cannot gain from a slight chance that she is a strong type, but the player can suffer greatly if there is a slight chance that she is a weak type.     

Representing equilibrium aggregates in aggregate games with applications to common agency

An aggregate game is a normal-form game with the property that each playerʼs payoff is a function of only his own strategy and an aggregate of the strategy profile of all players. Such games possess properties that can often yield simple characterizations of equilibrium aggregates without requiring that one solves for the equilibrium strategy profile. When payoffs have a quasi-linear structure and a degree of symmetry, we construct a self-generating maximization program over the space of aggregates with the property that the solution set corresponds to the set of equilibrium aggregates of the original n-player game. We illustrate the value of this approach in common-agency games where the playersʼ strategy space is an infinite-dimensional space of nonlinear contracts. We derive equilibrium existence and characterization theorems for both the adverse selection and moral hazard versions of these games.     

Learning by trial and error

A person learns by trial and error if he occasionally tries out new strategies, rejecting choices that are erroneous in the sense that they do not lead to higher payoffs. In a game, however, strategies can become erroneous due to a change of behavior by someone else. We introduce a learning rule in which behavior is conditional on whether a player experiences an error of the first or second type. This rule, called interactive trial and error learning, implements Nash equilibrium behavior in any game with generic payoffs and at least one pure Nash equilibrium.     

The analysis of a price war strategy under market demand growth

We use the finite repeated Prisoners' Dilemma game model herein to discuss how firms choose their optimal strategy under a price war with market demand growth. This model has two players: one is an R-type player and the other is a TFT-type player. Each player has two strategies to choose from: a preemption strategy and a “wait” strategy. Our results indicate that: (i) if the probability that the opponent is an R-type (TFT-type) player is high, then the time when the opponent adopts a preemption strategy will be early (late); (ii) Market demand growth is an incentive for cooperation among firms; (iii) if the market demand growth rate is high, then the R-type player will not have an evolutionary advantage. We use the competition between cell phone manufacturing firms Nokia and Motorola in China as an example. When Nokia is an R-type player and adopts a preemption strategy, Motorola should preferably use a preemption strategy rather than a “wait” strategy. However, as a TFT-type player, this will benefit Motorola under the situation of market demand growth.     

Difference-form contest success functions and effort levels in contests

We examine players' equilibrium effort levels in a contest with difference-form contest success functions in which two players compete with each other to win a prize. We show the following. At the pure-strategy Nash equilibrium of a simultaneous-move game, and in the subgame-perfect equilibrium of a sequential-move game, only one of the players expends effort or neither player expends effort. If one player's composite strength is far greater than the other player's, only the player with greater composite strength expends effort whether they move simultaneously or sequentially. If the players' valuations for the prize and their marginal probabilities of winning at (0, 0) are sufficiently small, neither player expends effort whether they move simultaneously or sequentially.     

Rational cooperation in the finitely repeated prisoners' dilemma

A common observation in experiments involving finite repetition of the prisoners' dilemma is that players do not always play the single-period dominant strategies (“finking”), but instead achieve some measure of cooperation. Yet finking at each stage is the only Nash equilibrium in the finitely repeated game. We show here how incomplete information about one or both players' options, motivation or behavior can explain the observed cooperation. Specifically, we provide a bound on the number of rounds at which Fink may be played, when one player may possibly be committed to a “Tit-for-Tat” strategy.     

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.     

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