\documentclass{amsart} \usepackage{amssymb,harvard} %\usepackage{showkeys} \newtheorem{theorem}{\indent Theorem} \newtheorem{proposition}{\indent Proposition} \newtheorem{lemma}{\indent Lemma} \newtheorem{corollary}[theorem]{\indent Corollary} \newtheorem{conjecture}[theorem]{\indent Conjecture} \theoremstyle{definition} \newtheorem{definition}{\indent Definition} \newtheorem{assumption}{\indent Assumption} %% %\def\bibindent{\hangindent=3pc \hangafter=1 \noindent} \newcommand{\fignumber}[1]{\refstepcounter{figure} \bigskip \begin{center} Figure \thefigure \end{center} \label{fig:#1} } \newcommand{\figref}[1]{\ref{fig:#1}} %% %%end of definitions %% \begin{document} \title{Foundations of Strategic Equilibrium} \thanks{Prepared for the \emph{Handbook of Game Theory with Economic Applications} edited by Robert J. Aumann and Sergiu Hart. We are grateful to Jean-Fran\c{c}ois Mertens from whom we have learnt much of what is written here. The detailed comments of Robert Aumann clarified much of the expression, and not a little of the content, of the chapter. We are also grateful to the reviewers, one of whom, in particular, made a large number of detailed and helpful comments.} \author{John Hillas} \author{Elon Kohlberg} \date{June, 1996} \maketitle \renewcommand{\thepage}{\roman{page}} \tableofcontents \newpage \renewcommand{\thepage}{\arabic{page}} \setcounter{page}{1} \section{Introduction} \label{sec:intro} The central concept of noncooperative game theory is that of the \emph{strategic equilibrium} (or Nash equilibrium, or noncooperative equilibrium). In this chapter we discuss some of the conceptual issues surrounding this concept and its refinements. Many of these issues have received increasing attention in the last few years. We are not at all comprehensive in covering the approaches that have been taken to the question. In particular, we focus almost exclusively on the ``purely rational'' approach and say almost nothing about other approaches. We do survey some of the issues and approaches that do not fit neatly into the core of our argument in Section~\ref{sec:other}. Though we do examine the idea of correlated equilibrium in Section~\ref{sec:correl}, most of our discussion is in the context of independent strategies. Aumann (1987a) and, in a somewhat different style, Nau and McCardle~(1990) argue that correlated equilibrium is a better expression of rationality in games. We don't take any position on that issue here. However many of the issues and concepts we do discuss in terms of the refinements of equilibrium are not as well developed for correlated equilibrium as they are in the setting where stochastic independence of the solution is assumed. (See however our discussion of the work of Aumann and Brandenburger~(1991) in Section~\ref{sec:epistemic} for one example of a theorem in which this independence is proved rather than assumed.) There is some literature on the refinement of correlated equilibrium. Myerson~(1986a and 1986b) was one of the first to examine issues of perfection and sequential rationality in the context of correlated equilibrium. More recently Dhillon and Mertens~(1991) reexamined the issue of perfection. There are also a number of comments in the work of Mertens (1987,1989,1991b) on strategic stability indicating how the theory would be developed allowing correlation. This chapter is rather informal. Not everything is defined precisely and there is little use, except in examples, of symbols. We hope that this will not give our readers any problem. We do not seek to give an introduction to the concept of strategic equilibrium here. Indeed we believe that one shouldn't worry too much about the foundations of this concept, or perhaps any concept, until one has some familiarity with its use and power. Readers who need or want formal definitions of the concepts we discuss here could consult the chapters by Hart~(1992) and van Damme~(1994) in this Handbook. \section{Pre-equilibrium Ideas} \label{sec:pre-eq} Before discussing the idea of equilibrium in any detail we shall look at some weaker conditions. We might think of these conditions as necessary implications of assuming that the players know the game, including the rationality and knowledge of the others. Of course, if each player knows the knowledge of the others then all that they know will be common knowledge, in the sense of Aumann (1976). \subsection{Iterated Dominance and Rationalizability} \label{sec:itdom} Consider the problem of a player in some game. Except in the most trivial cases the set of strategies that he will be prepared to play will depend on his assessment of what the other players will do. However it \emph{is} possible to say a little. If some strategy was strictly preferred by him to another strategy $s$ whatever he thought the other players would do, then he surely would not play $s$. And this remains true if it was some lottery over his strategies that was strictly preferred to $s$. We call a strategy such as $s$ a \emph{strictly dominated strategy}. Perhaps we could say a little more. A strategy $s$ would surely not be played unless there was some assessment of the manner in which the others might play that would lead $s$ to be (one of) the best. This is clearly at least as restrictive as the first requirement. (If $s$ is best for some assessment it cannot be strictly worse than some other strategy for all assessments.) In fact, if the set of assessments of what the others might do is convex (as a set of probabilities on the vectors of pure strategies of the others) then the two requirements are equivalent. This will be true if there is only one other player, or if a player's assessment of what the others might do permits correlation. However, the set of product distributions over the product of two or more players' pure strategy sets is not convex. Thus we have two cases: one in which we eliminate strategies that are strictly dominated, or equivalently never best against some distribution on the vectors of pure strategies of the others; and one in which we eliminate strategies that are never best against some product of distributions on the pure strategy sets of the others. In either case we have identified a set of strategies that we argue a rational player would not play. But since everything about the game, including the rationality of the players, is assumed to be common knowledge no player should put positive weight, in his assessment of what the other players might do, on such a strategy. And we can again ask: Are there any strategies that are strictly dominated when we restrict attention to the assessments that put weight only on those strategies of the others that are not strictly dominated. If so, a rational player who knew the rationality of the others would surely not play such a strategy. And similarly for strategies that were not best responses against some assessment putting weight only on those strategies of the others that are best responses against some assessment by the others. And we can continue for an arbitrary number of rounds. If there is ever a round in which we don't find any new strategies that will not be played by rational players commonly knowing the rationality of the others, we would never again ``eliminate'' a strategy. Thus, since we start with a finite number of strategies, the process must eventually terminate. We call the strategies that remain \emph{iteratively undominated} or \emph{correlatedly rationalizable} in the first case; and \emph{rationalizable} in the second case. The term rationalizable strategy and the concept were introduced by Bernheim~(1984) and Pearce~(1984). The term correlatedly rationalizable strategy and the concept were explicitly introduced by Brandenburger and Dekel~(1987), who also show the equivalence of this concept to what we are calling iteratively undominated strategies, though both the concept and this equivalence are alluded to by Pearce~(1984). The issue of whether or not the assessments of one player of the strategies that will be used by the others should permit correlation has been the topic of some discussion in the literature. Aumann~(1987) argues strongly that they should. Others have argued that there is at least a case to be made for requiring the assessments to exhibit independence. For example, Bernheim~(1986) argues as follows. \begin{quotation} Aumann has disputed this view [that assessments should exhibit independence]. He argues that there is no \emph{a priori} basis to exclude any probabilistic beliefs. Correlation between opponents' strategies may make perfect sense for a variety of reasons. For example, two players who attended the same ``school'' may have similar dispositions. More generally, while each player knows that his decision does not directly affect the choices of others, the substantive information which leads him to make one choice rather than another also affects his beliefs about other players' choices. Yet Aumann's argument is not entirely satisfactory, since it appears to make our theory of rationality depend upon some ill-defined ``dispositions'' which are, at best, extra-rational. What is the ``substantive information'' which disposes an individual towards a particular choice? In a pure strategic environment, the only available substantive information consists of the features of the game itself. This information is the same, regardless of whether one assumes the role of an outside observer, or the role of a player with a particular ``disposition''. Other information, such as the ``school'' which a player attended, is simply extraneous. Such information could only matter if, for example, different schools taught different things. A ``school'' may indeed teach not only the information embodied in the game itself, but also ``something else''; however, differences in schools would then be substantive only if this ``something else'' was substantive. Likewise, any apparently concrete source of differences or similarities in dispositions can be traced to an amorphous ``something else'', which does not arise directly from considerations of rationality. \end{quotation} This addresses Aumann's ideas in the context of Aumann's arguments concerning correlated equilibrium. Without taking a position here on those arguments, it does seem that in the context of a discussion of rationalizability the argument for independence is not valid. In particular, even if one accepts that one's opponents actually choose their strategies independently and that there is nothing substantive that they have in common outside their rationality and the roles they might have in the game, another player's assessment of what they are likely to play could exhibit correlation. Consider the three player game of \figref{staghunt}. Here Players 1 and~2 play a game having two pure strategy equilibria. This game has been much discussed in the literature as the ``Stag Hunt'' game. (See \citeasnoun{aumann-nash}, for example.) For our purposes here all that is relevant is that it is not clear which equilibrium that Players 1 and~2 will play and that which equilibrium is more likely has something to do with how rational players in general would think about playing a game. If players in general tend to ``play safe'' then the equilibrium $(B,R)$ seems likely, while if they tend to coordinate on efficient equilibria then $(T,L)$ seems likely. Player~3 has a choice that does not affect the payoffs of Players 1 and~2, but whose value to him does depend on the choices of 1~and~2. If Players 1 and~2 play $(B,R)$ then Player~3 does best by choosing $E$, while if they play $(T,L)$ then Player~3 does best by choosing $W$. \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{cc} \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 9,9,1 & 0,7,0 \\ \cline{2-3} B & 7,0,0 & 8,8,1 \\ \cline{2-3} \multicolumn{1}{c}{} & \multicolumn{2}{c}{W} \end{array} & \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 9,9,0 & 0,7,0 \\ \cline{2-3} B & 7,0,0 & 8,8,1 \\ \cline{2-3} \multicolumn{1}{c}{} & \multicolumn{2}{c}{E} \end{array}\\ \end{array} $$ } \fignumber{staghunt} \end{figure} Now suppose that Player~3 knows that the other players were independently randomly chosen to play the game and that they have no further information about each other and that they choose their strategies independently. Now if it is common knowledge that the players were rational and if there were a commonly known distribution of what players in such a situation did then such a distribution should form a Nash equilibrium. On the other hand if they don't know the distributions then it seems natural to allow them to have nondegenerate distributions over the distributions of what rational players commonly knowing the rationality of the others do in such a game. Now, the action taken by Player~1 will, in general, give Player~3 some information on which he will update his distribution over the distributions of what rational players do. And this will lead to correlation in his assessment of what Players 1 and~2 will do in the game. Indeed, in this setting, requiring independence essentially amounts to requiring that players be certain about things about which we are explicitly allowing them to be wrong. We indicated earlier that the set of product distributions over two or more players' strategy sets was not convex. This is correct, but somewhat incomplete. It is possible to put a linear structure on this set that would make it convex. In fact, this is exactly what we do in the proof of the existence of equilibrium below. What we mean is that if we think of the product distributions as a subset of the set of all probability distributions on the vectors of pure strategies and use the linear structure that is natural for that latter set then the set of product distributions is not convex. If instead we use the product of the linear structures on the spaces of distributions on the individual strategy spaces, then the set of product distributions will indeed be convex. The nonconvexity however reappears in the fact that with this linear structure the expected payoff function is no longer linear---or even quasi-concave. \subsection{Strengthening Rationalizability} \label{sec:strength} There have been a number of suggestions as to how to strengthen the notion of rationalizability. Many of these involve some form of the iterated deletion of (weakly) dominated strategies, that is, strategies such that some other (mixed) strategy does at least as well whatever the other players do, and strictly better for some choices of the others. The difficulty with such a procedure is that the order in which weakly dominated strategies are eliminated can affect the outcome at which one arrives. Now it is certainly possible to give a definition that unambiguously determines the order but such a definition implicitly rests on the assumption that the other players will view a strategy eliminated in a later round as infinitely more likely than one eliminated earlier. Having discussed in the previous section the reasons for rejecting the requirement that a player's beliefs over the choices of two of the other players be independent we shall not again discuss the issue but shall allow correlated beliefs in all of the definitions we discuss. This has two implications. The first is that our statement below of Pearce's notion of cautiously rationalizable strategies will not be his original definition but rather the suitably modified one. The second is that we shall be able to simplify the description by referring simply to rounds of deletions of dominated strategies rather than the somewhat more complicated notions of rationalizability. Even before the definition of rationalizability, Moulin~(1979) suggested using as a solution an arbitrarily large number of rounds of the elimination of all weakly dominated strategies for all players. Moulin actually proposed this as a solution only when it led to a set of strategies for each player such that whichever of the allowable strategies the others were playing the player would be indifferent among his own allowable strategies. A somewhat more sophisticated notion is that of \emph{cautiously rationalizable strategies} defined by Pearce~(1984). The set of such strategies is the set obtained by the following procedure. One first eliminates all strictly dominated strategies, and does this for an arbitrarily large number of rounds until one reaches a game in which there are no strictly dominated strategies. One then has a single round in which all weakly dominated strategies are eliminated. One then starts again with another (arbitrarily long) sequence of rounds of elimination of strictly dominated strategies, and again follows this with a single round in which all weakly dominated strategies are removed, and so on. For a finite game such a process ends after a finite number of rounds. Each of these definitions has a certain apparent plausibility. Nevertheless they are not well motivated. Each depends on an implicit assumption that a strategy eliminated at a later round is much more likely than a strategy eliminated earlier. And this in turn depends on an implicit assumption that in some sense the strategies deleted at one round are equally likely. For suppose we could split one of the rounds of the elimination of weakly dominated strategies and eliminate only part of the set. This could completely change the entire process that follows. \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{X} & \multicolumn{1}{c}{Y} & \multicolumn{1}{c}{Z} \\ \cline{2-4} A & 1,1 & 1,0 & 1,0 \\ \cline{2-4} B & 0,1 & 1,0 & 2,0 \\ \cline{2-4} C & 1,0 & 1,1 & 0,0 \\ \cline{2-4} D & 0,0 & 0,0 & 1,1 \\ \cline{2-4} \end{array} $$ } \fignumber{split} \end{figure} Consider, for example, the game of Figure~\figref{split}. The only cautiously rationalizable strategies are $A$ for Player~1 and $X$ for Player~2. In the first round strategies $C$ and $D$ are (weakly) dominated for Player~1. After these are eliminated strategies $Y$ and $Z$ are strictly dominated for Player~2. And after these are eliminated strategy $B$ is strictly dominated for Player~1. However, if $(A,X)$ is indeed the likely outcome then perhaps strategy $D$ is, in fact, much less likely than strategy $C$, since, given that 2 plays $X$, strategy $C$ is one of Player~1's best responses, while $D$ is not. Suppose that we start by eliminating just $D$. Now, in the second round only $Z$ is strictly dominated. Once $Z$ is eliminated, we eliminate $B$ for Player~1, but nothing else. We are left with $A$ and $C$ for Player~1 and $X$ and $Y$ for Player~2. There seems to us one slight strengthening of rationalizability that is well motivated. It is one round of elimination of weakly dominated strategies followed by an arbitrarily large number of rounds of elimination of strictly dominated strategies. This solution is obtained by Dekel and Fudenberg~(1990), under the assumption that there is some small uncertainty about the payoffs, by B\"{o}rgers~(1994), under the assumption that rationality was ``almost'' common knowledge, and by Ben-Porath~(1995) for the class of generic extensive form games with perfect information. The papers of Dekel and Fudenberg and of B\"{o}rgers use some approximation to the common knowledge of the game and the rationality of the players in order to derive, simultaneously, admissibility and some form of the iterated elimination of strategies. Ben-Porath obtains the result in extensive form games because in that setting a natural definition of rationality implies more than simple ex ante expected utility maximization. An alternative justification is possible. Instead of deriving admissibility, we include it in what we mean by rationality. A choice $s$ is admissibly rational against some conjecture $c$ about the strategies of the others if there is some sequence of conjectures putting positive weight on all possibilities and converging to $c$ such that $s$ is maximizing against each conjecture in the sequence. Now common knowledge of the game and of the admissible rationality of the players gives precisely the set we described. The argument is essentially the same as the argument that common knowledge of rationality implies correlated rationalizability. \section{The Idea of Equilibrium} \label{sec:idea} In the previous section we examined the extent to which it is possible to make predictions about players' behavior in situations of strategic interaction based solely on the common knowledge of the game, including in the description of the game the players' rationality. The results are rather weak. In some games these assumptions do indeed restrict our predictions, but in many they imply few, if any, restrictions. To say something more, a somewhat different point of view is productive. Rather than starting from only knowledge of the game and the rationality of the players and asking what implications can be drawn, one starts from the supposition that there is some established way in which the game will be played and asks what properties this manner of playing the game must satisfy in order not to be self-defeating, that is, so that a rational player, knowing that the game will be played in this manner, does not have an incentive to behave in a different manner. This is the essential idea of a strategic equilibrium, first defined by John Nash~(1950,1951). There are a number of more detailed stories to go along with this. The first was suggested by von Neumann and Morgenstern~(1944), even before the first definition of equilibrium by Nash. It is that players in a game are advised by game theorists on how to play. In each instance the game theorist, knowing the player's situation, tells the player what the theory recommends. The theorist does offer a (single) recommendation in each situation and all theorists offer the same advice. One might well allow these recommendations to depend on various ``real-life'' features of the situation that are not normally included in our models. One would ask what properties the theory should have in order for players to be prepared to go along with its recommendations. This idea is discussed in a little more detail in the introduction of the chapter on ``Strategic Equilibrium'' in this Handbook (van Damme, 1994). Alternatively, one could think of a situation in which the players have no information beyond the rules of the game. We'll call such a game a \emph{Tabula-Rasa game}. If a player's optimal choice depends on the actions of the others then, since he doesn't know those actions we might argue that he will form some probabilistic assessment of them. We might go on to argue that since the players have precisely the same information they will form the same assessments about how choices will be made. Again, one could ask what properties this common assessment should have in order not to be self-defeating. The first to make the argument that players having the same information should form the same assessment was Harsanyi (1967-1968, Part III). Aumann~(1974, p. 92) labeled this view the Harsanyi doctrine. Yet another approach is to think of the game being preceded by some stage of ``pre-play negotiation'' during which the players may reach a non-binding agreement as to how each should play the game. One might ask what properties this agreement should have in order for all players to believe that everyone will act according to the agreement. One needs to be a little careful about exactly what kind of communication is available to the players if one wants to avoid introducing correlation. B\'{a}r\'{a}ny~(1992) and Forges~(1990) show that with at least four players and a communication structure that allows for private messages any correlated equilibrium ``is'' a Nash equilibrium of the game augmented with the communication stage. There are also other difficulties with the idea of justifying equilibria by pre-play negotiation. See Aumann (1990). Rather than thinking of the game being played by a fixed set of players one might think of each player as being drawn from a population of rational individuals who find themselves in similar roles. The specific interactions take place between randomly selected members of these populations, who are aware of the (distribution of) choices that had been made in previous interactions. Here one might ask what distributions are self-enforcing, in the sense that if players took the past distributions as a guide to what the others choices were likely to be, the resulting optimal choices would (could) lead to a similar distribution in the current round. One already finds this approach in Nash (1950). A somewhat different approach sees each player as representing a whole population of individuals, each of whom is ``programmed''(for example, through his genes) to play a certain strategy. The players themselves are not viewed as rational, but they are assumed to be subject to ``natural selection,'' that is, to the weeding out of all but the payoff-maximizing programs. Evolutionary approaches to game theory were introduced by Manyard Smith and Price (1973). In most of the rest of this chapter we shall consider only interpretations that involve rational players. We shall return to discuss the evolutionary interpretation briefly in Section~\ref{sec:evol}. \subsection{Self-Enforcing Plans} \label{sec:plans} One interpretation of equilibrium sees the focus of the analysis as being the actual strategies chosen by the players, that is, their plans in the game. An equilibrium is defined to be a self-enforcing profile of plans. At least a necessary condition for a profile of plans to be self-enforcing is that each player, given the plans of the others should not have an alternate plan that he strictly prefers. This is the essence of the definition of an equilibrium. As we shall soon see, in order to guarantee that such a self-enforcing profile of plans exists we must consider not only deterministic plans, but also random plans. That is, as well as being permitted to plan what to do in any eventuality in which he might find himself, a player is explicitly thought of as planning to use some lottery to choose between such deterministic plans. Such randomizations have been found by many to be somewhat troubling. Arguments are found in the literature that such ``mixed strategies'' are less stable than pure strategies. (There is, admittedly, a precise sense in which this is true.) And, in the early game theory literature there is discussion as to what precisely it means for a player to choose a mixed strategy and why players may choose to use such strategies. See, for example, the discussion in Luce and Raiffa (1957, pp. 74--76). Harsanyi~(1973) provides an interpretation that avoids this apparent instability and, in the process, provides a link to the interpretation of Section~\ref{sec:assess}. Harsanyi considers a model in which there is some small uncertainty about the players' payoffs. This uncertainty is independent across the players, but each player knows his own payoff. The uncertainty is assumed to be of a form such that it is represented by a probability distribution with a continuously differentiable density. If for each player and each vector of pure actions (that is, strategies in the game without uncertainty) the probability that the payoff is close to some particular value is high, then we might consider the game close to the game in which the payoff is exactly that value. Conversely, we might consider the game in which the payoffs are known exactly to be well approximated by the game with small uncertainty about the payoffs. Harsanyi shows that in a game with such uncertainty about payoffs all equilibria are essentially pure, that is, each player plays a pure strategy with probability~1. Moreover, with probability~1, each player is playing his unique best response to the strategies of the other players; and the expected mixed actions of the players will be close to an equilibrium of the game without uncertainty. Harsanyi also shows, modulo a small technical error later corrected by van Damme~(1991), that any regular equilibrium can be approximated in this way by pure equilibria of a game with small uncertainty about the payoffs. We shall not define a regular equilibrium here. Nor shall we give any of the technical details of the construction, or any of the proofs. The reader should instead consult Harsanyi~(1973), van Damme~(1991), or van Damme~(1994). \subsection{Self-Enforcing Assessments} \label{sec:assess} Let us consider again Harsanyi's construction described in the previous section. In an equilibrium of the game with uncertainty no player consciously randomizes. Given what the others are doing the player has a strict preference for one of his available choices. However the player does not know what the others are doing. He knows that they are not randomizing---like him they have a strict preference for one of their available choices---but he does not know precisely their payoffs. Thus, if the optimal actions of the others differ as their payoffs differ, the player will have some probabilistic assessment of the actions that the others will take. And, since we assumed that the randomness in the payoffs was independent across players, this probabilistic assessment will also be independent, that is, it will be a vector of mixed strategies of the others. The mixed strategy of a player does not represent a conscious randomization on the part of that player, but rather the uncertainty in the minds of the others as to how that player will act. We see that even without the construction involving uncertainty about the payoffs, we could adopt this interpretation of a mixed strategy. This interpretation has been suggested and promoted by Bob Aumann for some time (for example Aumann, 1987a, Aumann and Brandenburger, 1995) and is, perhaps, becoming the preferred interpretation among game theorists. There is nothing in this interpretation that compels us to assume that the assessments over what the other players will do should exhibit independence. Nevertheless, we shall \emph{assume} that the assessments are independent. Thus the focus of the analysis becomes, not the choices of the players, but the assessments of the players about the choices of the others. The basic consistency condition that we impose on the players' assessments is this: A player reasoning through the conclusions that others would draw from their assessments, should not be led to revise his own assessment. More formally, Aumann and Brandenburger (1995, p. 1177) show that if each player's assessment of the choices of the others is independent across the other players, if any two players have the same assessment as to the actions of a third, and if these assessments, the game, and the rationality of the players are all mutually known, then the assessments constitute a strategic equilibrium. (A fact is \emph{mutually known} if each player knows the fact and knows that the others know it.) We discuss this and related results in more detail in Section~\ref{sec:epistemic}. \section{The Mixed Extension of a Game} \label{sec:mixed} Before discussing exactly how rational players assess their opponents' choices, we must reflect on the manner in which the payoffs represent the outcomes. If the players are presumed to quantify their uncertainties about their opponents' choices, then in choosing among their own strategies they must, in effect, compare different lotteries over the outcomes. Thus for the description of the game it no longer suffices to ascribe a payoff to each outcome, but it is also necessary to ascribe a payoff to each lottery over outcomes. Such a description would be unwieldy unless it could be condensed to a compact form. One of the major achievements of von Neumann and Morgenstern~(1944) was the development of such a compact representation (``cardinal utility''). They showed that if a player's ranking of lotteries over outcomes satisfied some basic conditions of consistency, then it was possible to represent that ranking by assigning numerical ``payoffs'' just to the outcomes themselves, and by ranking lotteries according to their expected payoffs. See the chapter by Fishburn (1994) in this handbook for details. Assuming such a scaling of the payoffs, one can expand the set of strategies available to each player to include not only definite (``pure'') choices but also probabilistic (``mixed'') choices, and extend the definition of the payoff functions by taking the appropriate expectations. The strategic form obtained in this manner is called the \emph{mixed extension} of the game. Recall from Section~\ref{sec:assess} that we consider a situation in which each player's assessment of the strategies of the others can be represented by a product of probability distributions on the others' pure strategy sets, that is, by a mixed strategy for each of the others. And that any two players have the same assessment about the choices of a third. Denoting the (identical) assessments of the others as a probability distribution (mixed strategy) over a player's (pure) choices, we may describe the consistency condition as follows: Each player's mixed strategy must place positive probability only on those pure strategies which maximize the player's payoff given the others' mixed strategies. Thus a profile of consistent assessments may be viewed as a strategic equilibrium in the mixed extension of the game. Let us consider an example (Figure~\figref{exist}). Player 1 chooses the row and player 2 (simultaneously) chooses the column. The resulting (cardinal) payoffs are indicated in the appropriate box of the matrix, with player 1's payoff appearing first. \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 2,0 & 0,1 \\ \cline{2-3} B & 0,1 & 1,0 \\ \cline{2-3} \end{array} $$ } \fignumber{exist} \end{figure} What probabilities could characterize a self-enforcing assessment? A (mixed) strategy for player 1 (that is, an assessment by 2 of how 1 would play) is a vector $(x, 1-x)$, where $x$ lies between $0$ and $1$ and denotes the probability of playing $T$. Similarly, a strategy for 2 is a vector $(y, 1-y)$. Now, given $x$, the payoff-maximizing value of $y$ is indicated in Figure~\figref{exist}a, and given $y$ the payoff-maximizing-value of $x$ is indicated in Figure~\figref{exist}b. When the figures are combined as in Figure~\figref{exist}c, it is evident that the game possesses a single equilibrium, namely $x = \frac{1}{2}, y = \frac{1}{3}$. Thus in a self-enforcing assessment Player 1 must assign a probability of $\frac{1}{3}$ to 2's playing $L$, and player 2 must assign a probability of $\frac{1}{2}$ to 1's playing~$T$. \begin{figure}[htbp] \begin{center} \makebox[0in]{ \begin{tabular}{ccc} \begin{picture}(130,130)(-15,-15) \thicklines \put(0,0){\vector(1,0){110}} \put(0,0){\vector(0,1){110}} \put(110,-2){\makebox(0,0)[t]{$x$}} \put(100,-2){\makebox(0,0)[t]{$1$}} \put(50,-2){\makebox(0,0)[t]{$\frac{1}{2}$}} \put(-2,100){\makebox(0,0)[r]{$1$}} \put(-2,110){\makebox(0,0)[r]{$y$}} \put(0,100){\line(1,0){50}} \put(50,100){\line(0,-1){98}} \put(50,2){\line(1,0){50}} \end{picture} & \begin{picture}(130,130)(-15,-15) \thicklines \put(0,0){\vector(1,0){110}} \put(0,0){\vector(0,1){110}} \put(110,-2){\makebox(0,0)[t]{$x$}} \put(100,-2){\makebox(0,0)[t]{$1$}} \put(-2,100){\makebox(0,0)[r]{$1$}} \put(-2,110){\makebox(0,0)[r]{$y$}} \put(-2,33){\makebox(0,0)[r]{$\frac{1}{3}$}} \put(2,0){\line(0,1){33}} \put(2,33){\line(1,0){98}} \put(100,33){\line(0,1){67}} \end{picture} & \begin{picture}(130,130)(-15,-15) \thicklines \put(0,0){\vector(1,0){110}} \put(0,0){\vector(0,1){110}} \put(110,-2){\makebox(0,0)[t]{$x$}} \put(100,-2){\makebox(0,0)[t]{$1$}} \put(50,-2){\makebox(0,0)[t]{$\frac{1}{2}$}} \put(-2,100){\makebox(0,0)[r]{$1$}} \put(-2,110){\makebox(0,0)[r]{$y$}} \put(0,100){\line(1,0){50}} \put(50,100){\line(0,-1){98}} \put(50,2){\line(1,0){50}} \put(-2,33){\makebox(0,0)[r]{$\frac{1}{3}$}} \put(2,0){\line(0,1){33}} \put(2,33){\line(1,0){98}} \put(100,33){\line(0,1){67}} \end{picture} \\[20pt] Figure~\figref{exist}a & Figure~\figref{exist}b & Figure~\figref{exist}c \end{tabular} } \end{center} \end{figure} Note that these assessments do not imply a recommendation for action. For example, they give player 1 no clue as to whether he should play $T$ or $B$ (because the expected payoff to either strategy is the same). But this is as it should be: it is impossible to expect rational deductions to lead to definite choices in a game like Figure~\figref{exist}, because whatever those choices would be they would be inconsistent with their own implications. (Figure~\figref{exist} admits no pure-strategy equilibrium.) Still, the assessments do provide the players with an a priori evaluation of what the play of the game is worth to them, in this case $\frac{2}{3}$ to 1 and $\frac{1}{2}$ to 2. The game of Figure~\figref{exist} is an instance in which our consistency condition completely pins down the assessments that are self-enforcing. In general, we cannot expect such a sharp conclusion. \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{C} & \multicolumn{1}{c}{R} \\ \cline{2-4} T & 8,5 & 0,0 & 6,3 \\ \cline{2-4} B & 0,0 & 7,6 & 6,3 \\ \cline{2-4} \end{array} $$ } \fignumber{mult} \end{figure} Consider, for example, the game of Figure~\figref{mult}. There are three equilibrium outcomes: (8,5), (7,6) and (6,3) (for the latter, the probability of $T$ must lie between .5 and .6). Thus, all we can say is that there are three different consistent ways in which the players could view this game. Player 1's assessment would be: Either that Player~2 was (definitely) going to play $L$, or that layer~2 was going to play $C$, or that Player~2 was going to play $R$. Which one of these assessments he would, in fact, hold is not revealed to us by means of equilibrium analysis. \section{The Existence of Equilibrium} \label{sec:exist} We have seen that, in the game of Figure~\figref{exist}, for example, there may be no pure self-enforcing plans. But what of mixed plans, or self-enforcing assessments? Could they too be refuted by an example? The main result of non-cooperative game theory states that no such example can be found. \begin{theorem}[Nash 1950, 1951] The mixed extension of every finite game has at least one strategic equilibrium. \end{theorem} (A game is \emph{finite} if the player set as well as the set of strategies available to each player is finite.) \begin{proof}[Sketch of Proof] The proof may be sketched as follows. (It is a multi-dimensional version of Figure~\figref{exist}c.) Consider the set-valued mapping (or correspondence) that maps each strategy profile, $x$, to all strategy profiles in which each player's component strategy is a \emph{best response} to $x$ (that is, maximizes the player's payoff given that the others are adopting their components of $x$). If a strategy profile is contained in the set to which it is mapped (is a \emph{fixed point}) then it is an equilibrium. This is so because a strategic equilibrium is, in effect, defined as a profile that is a best response to itself. Thus the proof of existence of equilibrium amounts to a demonstration that the ``best response correspondence'' has a fixed point. The fixed-point theorem of Kakutani~(1941) asserts the existence of a fixed point for every correspondence from a convex and compact subset of Euclidean space into itself, provided two conditions hold. One, the image of every point must be convex. And two, the graph of the correspondence (the set of pairs $(x,y)$ where $y$ is in the image of $x$) must be closed. Now, in the mixed extension of a finite game, the strategy set of each player consists of all vectors (with as many components as there are pure strategies) of non-negative numbers that sum to 1; that is, it is a simplex. Thus the set of all strategy profiles is a product of simplices. In particular, it is a convex and compact subset of Euclidean space. Given a particular choice of strategies by the other players, a player's best responses consist of all (mixed) strategies that put positive weight only on those pure strategies that yield the highest expected payoff among all the pure strategies. Thus the set of best responses is a subsimplex. In particular, it is convex. Finally, note that the conditions that must be met for a given strategy to be a best response to a given profile are all weak polynomial inequalities, so the graph of the best response correspondence is closed. Thus all the conditions of Kakutani's theorem hold, and this completes the proof of Nash's theorem. \end{proof} Nash's theorem has been generalized in many directions. Here we mention two. \begin{theorem}[Fan 1952, Glicksberg 1952] Consider a strategic form game with finitely many players, whose strategy sets are compact subsets of a metric space, and whose payoff functions are continuous. Then the mixed extension has at least one strategic equilibrium. \end{theorem} (Here ``mixed strategies'' are understood as Borel probability measures over the given subsets of pure strategies). \begin{theorem}[Debreu 1952] Consider a strategic form game with finitely many players, whose strategy sets are convex compact subsets of a Euclidean space, and whose payoff functions are continuous. If, moreover, each payoff function is quasi-concave in the player's own strategy, then the game has at least one strategic equilibrium. \end{theorem} (A real-valued function on a Euclidean space is \emph{quasi-concave} if, for each number $a$, the set of points at which the value of the function is at least $a$ is convex.) Theorem 2 may be thought of as identifying conditions on the strategy sets and payoff functions so that the game is like a finite game, that is, can be well approximated by finite games. Theorem 3 may be thought of as identifying conditions under which the strategy spaces are like the mixed strategy spaces for the finite games and the payoff functions are like expected utility. \section{Correlated Equilibrium} \label{sec:correl} We have argued that a self-enforcing assessment of the players' choices must constitute an equilibrium of the mixed extension of the game. But our argument has been incomplete: we have not explained why it is sufficient to assess each player's choice separately. Of course, the implicit reasoning was that, since the players' choices are made in ignorance of one another, the assessments of those choices ought to be independent. In fact, this idea is subsumed in the definition of the mixed extension, where the expected payoff to a player is defined for a product distribution over the others' choices. Let us now make the reasoning explicit. We shall argue here in the context of a Tabula-Rasa game, as we outlined in Section~\ref{sec:idea}. Let us call the common assessment of the players implied by the Harsanyi doctrine the \emph{rational assessment}. Consider the assessment over the pure-strategy profiles by a rational observer who knows as much about the players as they know about each other. We claim that observation of some player's choice, say Player~1's choice, should not affect the observer's assessment of the other players' choices. This is so because, as regards the other players, the observer and Player~1 have identical information and---by the Harsanyi doctrine---also identical analyses of that information, so there is nothing that the observer can learn from the player. Thus, for any player, the conditional probability, given that player's choice, over the others' choices is the same as the unconditional probability. It follows (Aumann and Brandenburger 1995, Lemma 4.6, p.~1169) that the observer's assessment of the choices of all the players must be the product of his assessments of their individual choices. In making this argument we have taken for granted that the strategic form encompasses all the information available to the players in a game. This assumption, of ``completeness,'' ensured that a player had no more information than was available to an outside observer. Aumann (1974, 1987) has argued against the completeness assumption. His position may be described as follows: It is impractical to insist that every piece of information available to some player be incorporated into the strategic form. This is so because the players are bound to be in possession of all sorts of information about random variables which are strategically irrelevant (that is, which cannot affect the outcome of the game). Thus he proposes to view the strategic form as an incomplete description of the game, indicating the available ``actions'' and their consequences; and to take account of the possibility that the actual choice of actions may be preceded by some unspecified observations by the players. Having discarded the completeness assumption (and hence the symmetry in information between player and observer), we can no longer expect the rational assessment over the pure-strategy profiles to be a product distribution. But what can we say about it? That is, what are the implications of the rational assessment hypothesis itself? Aumann (1987) has provided the answer. He showed that a distribution on the pure-strategy profiles is consistent with the rational assessment hypothesis if and only if it constitutes a correlated equilibrium. Before going into the details of Aumann's argument, let us comment on the significance of this result. At first blush, it might have appeared hopeless to expect a direct method for determining whether a given distribution on the pure-strategy profiles was consistent with the hypothesis: after all, there are endless possibilities for the players' additional observations, and it would seem that each one of them would have to be tried out. And yet, the definition of correlated equilibrium requires nothing but the verification of a finite number of linear inequalities. Specifically, a distribution over the pure-strategy profiles constitutes a \emph{correlated equilibrium} if it imputes positive marginal probability only to such pure strategies, $s$, as are best responses against the distribution on the others' pure strategies obtained by conditioning on $s$. Multiplying throughout by the marginal probability of $s$, one obtains linear inequalities (if $s$ has zero marginal probability, the inequalities are vacuous). Consider, for example, Figure~\figref{exist}. Denoting the probability over the $ij$th entry of the matrix by $p_{ij}$, the conditions for correlated equilibrium are as follows: \[ 2p_{11}\geq p_{12},\ p_{22}\geq 2p_{21},\ 2p_{21}\geq p_{11}, \text{ and } p_{12}\geq p_{22} \] There is a unique solution: $p_{11}=p_{21}=1/6$, $p_{12}=p_{22}=1/3$. So in this case, the correlated equilibria and the Nash equilibria coincide. For an example of a correlated equilibrium that is not a Nash equilibrium, consider the distribution $1/2(T,L)+1/2(B,R)$ in Figure~\figref{bos}. The distribution over II's choices obtained by conditioning on $T$ is $L$ with probability~1, and so $T$ is a best response. Similarly for the other pure strategies and the other player. \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 3,1 & 0,0 \\ \cline{2-3} B & 0,0 & 1,3 \\ \cline{2-3} \end{array} $$ } \fignumber{bos} \end{figure} For a more interesting example, consider the distribution that assigns weight $1/6$ to each non-zero entry of the matrix in Figure~\figref{mv}. (This example is due to Moulin and Vial~(1978)). The distribution over II's choices obtained by conditioning on $T$ is $C$ with probability $1/2$ and $R$ with probability $1/2$, and so $T$ is a best response (it yields~1.5 while $M$ yields~0.5 and $B$ yields~1). Similarly for the other pure strategies of Player~1, and for Player~II. \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{C} & \multicolumn{1}{c}{R} \\ \cline{2-4} T & 0,0 & 1,2 & 2,1 \\ \cline{2-4} M & 2,1 & 0,0 & 1,2 \\ \cline{2-4} B & 1,2 & 2,1 & 0,0 \\ \cline{2-4} \end{array} $$ } \fignumber{mv} \end{figure} It is easy to see that the correlated equilibria of a game contain the convex hull of its Nash equilibria. What is somewhat less obvious is that the containment may be strict (Aumann 1974), even in payoff space. The game of Figure~\figref{mv} illustrates this: the unique Nash equilibrium assigns equal weight, $1/3$, to every pure strategy, and hence gives rise to the expected payoffs $(1,1)$; whereas the correlated equilibrium described above gives rise to the payoffs $(1.5,1.5)$. Let us now sketch the proof of Aumann's result. By the rational assessment hypothesis, a rational observer can assess in advance the probability of each possible list of observations by the players. Furthermore, he knows that the players also have the same assessment, and that each player would form a conditional probability by restricting attention to those lists that contain his actual observations. Finally, we might as well assume that the player's strategic choice is a function of his observations (that is, that if the player must still resort to a random device in order to decide between several payoff-maximizing alternatives, then the observer has already included the various outcomes of that random device in the lists of the possible observations). Now, given a candidate for the rational assessment of the game, that is, a distribution over the matrix, what conditions must it satisfy if it is to be consistent with some such assessment over lists of observations? Our basic condition remains as in the case of Nash equilibria: by reasoning through the conclusions that the players would reach from their assessments, the observer should not be led to revise his own assessment. That is, conditional on any possible observation of a player, the pure strategy chosen must maximize the player's expected payoff. As stated, the condition is useless for us, because we are not privy to the rational observer's assessment of the probabilities over all the possible observations. However, by lumping together all the observations inducing the same choice, $s$, (and by noting that, if $s$ maximized the expected payoff over a number of disjoint events then it would also maximize the expected payoff over their union), we obtain a condition that we can check: that the choice of $s$ maximizes the player's payoff against the conditional distribution given $s$. But this is precisely the condition for correlated equilibrium. To complete the proof, note that the basic consistency condition has no implications beyond correlated equilibria: Any correlated equilibrium satisfies this condition relative to the following assessment of the players' additional observations: Each player's additional observation is the name of one of his pure strategies, and the probability distribution over the possible lists of observations (that is, over the entries of the matrix) is precisely the distribution of the given correlated equilibrium. For the remainder of this chapter we shall restrict our attention to uncorrelated strategies. The issues and concepts we discuss concerning the refinement of equilibrium are not as well developed for correlated equilibrium as they are in the setting where stochastic independence of the solution is assumed. \section{The Extensive Form} \label{sec:extensive} The strategic form is a convenient device for defining strategic equilibria: it enables us to think of the players as making single, simultaneous choices. However, actually to describe ``the rules of the game,'' it is more convenient to present the game in the form of a tree. The \emph{extensive form} is a formal representation of the rules of the game. It consists of a rooted tree whose nodes represent decision points (an appropriate label identifies the relevant player), whose branches represent moves and whose endpoints represent outcomes. Each player's decision nodes are partitioned into \emph{information sets} indicating the player's state of knowledge at the time he must make his move: the player can distinguish between points lying in different information sets but cannot distinguish between points lying in the same information set. Of course, the actions available at each node of an information set must be the same, or else the player could distinguish between the nodes according to the actions that were available. This means that the number of moves must be the same and that the labels associated with moves must be the same. Random events are represented as nodes (usually denoted by open circles) at which the choices are made by Nature, with the probabilities of the alternative branches included in the description of the tree. The information partition is said to have \emph{perfect recall} (Kuhn 1953) if the players remember whatever they knew previously, including their past choices of moves. In other words, all paths leading from the root of the tree to points in a single information set, say player $i$'s, must intersect the same information sets of player $i$ and must display the same choices by player $i$. The extensive form is ``finite'' if there are finitely many players, each with finitely many choices at finitely many decision nodes. Obviously, the corresponding strategic form is also finite (there are only finitely many alternative ``books of instructions''). Therefore, by Nash's theorem, there exists a mixed-strategy equilibrium. But a mixed strategy might seem a cumbersome way to represent an assessment of a player's behavior in an extensive game. It specifies a probability distribution over complete plans of action, each specifying a definite choice at each of the player's information sets. It may seem more natural to specify an independent probability distribution over the player's moves at each of his information sets. Such a specification is called a \emph{behavioral strategy}. Is nothing lost in the restriction to behavioral strategies? Perhaps, for whatever reason, rational players do assess their opponents' behavior by assigning probabilities to complete plans of action, and perhaps some of those assessments cannot be reproduced by assigning independent probabilities to the moves? Kuhn's Theorem~(1953) guarantees that, in a game with perfect recall, nothing, in fact, is lost. It says that in such a game every mixed strategy of a player in a tree is equivalent to some behavioral strategy, in the sense that both give the same distribution on the endpoints, whatever the strategies of the opponents. For example, in the (skeletal) extensive form of Figure~\figref{beh}, while it is impossible to reproduce by means of a behavioral strategy the correlations embodied in the mixed strategy $.1\mbox{\it TLW} + .1\mbox{\it TRY} + .5\mbox{\it BLZ} + .1\mbox{\it BLW} + .2\mbox{\it BRX}$, nevertheless it is possible to construct an equivalent behavioral strategy, namely $((.2,.8),(.5,0,.5),(.125,0,.25,.625))$. \begin{figure}[htbp] \begin{center} \begin{picture}(210,100)(-90,-10) \put(0,0){\line(1,1){50}} \put(0,0){\line(-1,1){80}} \put(-50,50){\line(0,1){30}} \put(-50,50){\line(1,1){30}} \put(50,50){\line(1,2){15}} \put(50,50){\line(4,3){40}} \put(50,50){\line(-1,2){15}} \put(50,50){\line(-4,3){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(-50,50){\circle*{4}} \put(2,-2){\makebox(0,0)[t]{1}} \put(52,48){\makebox(0,0)[tl]{1}} \put(-57,48){\makebox(0,0)[tl]{1}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{$B$}} \put(27,65){\makebox(0,0)[tr]{$W$}} \put(72,65){\makebox(0,0)[tl]{$Z$}} \put(36,77){\makebox(0,0)[tr]{$X$}} \put(64,77){\makebox(0,0)[tl]{$Y$}} \put(-70,70){\makebox(0,0)[tr]{$L$}} \put(-52,65){\makebox(0,0)[br]{$C$}} \put(-30,70){\makebox(0,0)[tl]{$R$}} \end{picture} \end{center} \fignumber{beh} \end{figure} To see the general validity of the theorem, note that the distribution over the endpoints is unaffected by correlation of choices that anyway cannot occur at the same ``play'' (that is, on the same path from the root to an endpoint). Yet this is precisely the type of correlation that is possible in a mixed strategy but not in a behavioral strategy. (Correlation among choices lying on the same path is possible also in a behavioral strategy. Indeed, this possibility is already built into the structure of the tree: if two plays differ in a certain move, then (because of perfect recall) they also differ in the information set at which any later move is made and so the assessment of the later move can be made dependent on the earlier move.) Kuhn's Theorem allows us to identify each equivalence class of mixed strategies with a behavioral strategy---or sometimes, on the boundary of the space of behavioral strategies, with an equivalence class of behavioral strategies. Thus, in games with perfect recall, for the strategic choices of payoff-maximizing players there is no difference between the mixed extension of the game and the ``behavioral extension'' (where the players are restricted to their behavioral strategies). In particular, the equilibria of the mixed and of the behavioral extension are equivalent, so either may be taken as the set of candidates for the rational assessment of the game. Of course, the equivalence of the mixed and the behavioral extensions implies the existence of equilibrium in the behavioral extension of any finite game with perfect recall. It is interesting to note that this result does not follow directly from either Nash's theorem or from Debreu's theorem. The difficulty is that the convex structure on the behavioral strategies does not reflect the convex structure on the mixed strategies, and therefore the best-reply correspondence need not be convex. For example, in Figure~\figref{notconvex}, the set of optimal strategies contains $(T,R)$ and $(B,L)$ but not their behavioral mixture $(\frac{1}{2}T + \frac{1}{2}B, \frac{1}{2}L + \frac{1}{2}R)$. This corresponds to the difference between the two linear structures on the space of product distributions on strategy vectors that we discussed at the end of Section~\ref{sec:itdom}. \begin{figure}[tbp] \begin{center} \begin{picture}(150,130)(-50,-10) %Fig notconvex \put(0,0){\line(1,1){90}} \put(0,0){\line(-1,1){40}} \put(50,50){\line(-1,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{1}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{$B$}} \put(28,70){\makebox(0,0)[tr]{$L$}} \put(72,70){\makebox(0,0)[tl]{$R$}} \put(-40,43){\makebox(0,0)[b]{$1$}} \put(10,93){\makebox(0,0)[b]{$1$}} \put(90,93){\makebox(0,0)[b]{$0$}} \end{picture} \end{center} \fignumber{notconvex} \end{figure} \section{Refinement of Equilibrium} \label{sec:refine} Let us review where we stand: Assuming that in any game there is one particular assessment of the players' strategic choices that is common to all rational decision makers (``the rational assessment hypothesis''), we can deduce that that assessment must constitute a strategic equilibrium (which can be expressed as a profile of either mixed or behavioral strategies). The natural question is: Can we go any further? That is, when there are multiple equilibria, can any of them be ruled out as candidates for the self-enforcing assessment of the game? At first blush, the answer seems to be negative. Indeed, if an assessment stands the test of individual payoff maximization, then what else can rule out its candidacy? And yet, it turns out that it \emph{is} possible to rule out some equilibria. The key insight was provided by Selten~(1965). It is that irrational assessments by two different players might each make the other look rational (that is, payoff maximizing). \begin{figure}[htbp] \begin{center} \begin{picture}(150,130)(-50,-10) %Fig subgame \put(0,0){\line(1,1){90}} \put(0,0){\line(-1,1){40}} \put(50,50){\line(-1,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{2}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{$B$}} \put(28,70){\makebox(0,0)[tr]{$L$}} \put(72,70){\makebox(0,0)[tl]{$R$}} \put(-40,43){\makebox(0,0)[b]{$2,5$}} \put(10,93){\makebox(0,0)[b]{$4,1$}} \put(90,93){\makebox(0,0)[b]{$0,0$}} \end{picture} \end{center} \fignumber{subgame} \end{figure} A typical example is that of Figure~\figref{subgame}. The assessment $(T,R)$ certainly does not appear to be self-enforcing. Indeed, it seems clear that Player~1 would play $B$ rather than $T$ (because he can bank on the fact that Player~2---who is interested only in his own payoff---will consequently play $L$). And yet $(T,R)$ constitutes a strategic equilibrium: Player~1's belief that Player~2 would play $R$ makes his choice of $T$ payoff-maximizing, while Player~2's belief that Player~1 would play $T$ makes his choice of $R$ (irrelevant hence) payoff-maximizing. Thus Figure~\figref{subgame} provides an example of an equilibrium that can be ruled out as a self-enforcing assessment of the game. (In this particular example there remains only a single candidate, namely $(B,L)$.) By showing that it is sometimes possible to narrow down the self-enforcing assessments beyond the set of strategic equilibria, Selten opened up a whole field of research: the \emph{refinement} of equilibrium. \subsection{The Problem of Perfection} \label{sec:problem} We have described our project as identifying the self-enforcing assessments. Thus we interpret Selten's insight as being that not all strategic equilibria are, in fact, self-enforcing. We should note that this is not precisely how Selten described the problem. Selten explicitly sees the problem as the prescription of disequilibrium behavior in ``unreached parts of the game'' (Selten 1975, p.\ 25). Harsanyi and Selten (1988, p.\ 17) describe the problem of imperfect equilibria in much the same way. Kreps and Wilson~(1982) are a little less explicit about the nature of the problem but their description of their solution suggests that they agree. ``A sequential equilibrium provides at each juncture an equilibrium in the subgame (of incomplete information) induced by restarting the game at that point''~(p.~864). Also Myerson seems to view his definition of proper equilibrium as addressing the same problem as addressed by Selten. However he discusses examples and defines a solution explicitly in the context of normal form games where there are no unreached parts of the game. He describes the program as eliminating those equilibria that ``may be inconsistent with our intuitive notions about what should be the outcome of a game'' (Myerson 1978, p.\ 73). The description of the problem of the refinement of strategic equilibrium as looking for a set of necessary and sufficient conditions for self-enforcing behavior does nothing without specific interpretations of what this means. Nevertheless it seems to us to tend to point us in the right direction. Moreover it does seem to delineate the problem to some extent. Thus in the game of Figure~\figref{tenone} we would be quite prepared to concede that the equilibrium $(B,R)$ was unintuitive while at the same time claiming that it was quite self-enforcing. \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 10,10 & 0,0 \\ \cline{2-3} B & 0,0 & 1,1 \\ \cline{2-3} \end{array} $$ } \fignumber{tenone} \end{figure} \subsection{Equilibrium Refinement versus Equilibrium Selection} \label{sec:refvssel} There is a question separate from but related to that of equilibrium refinement. That is the question of equilibrium selection. Equilibrium refinement is concerned with establishing necessary conditions for reasonable play, or perhaps necessary and sufficient conditions for ``self-enforcing.'' Equilibrium selection is concerned with narrowing the prediction, indeed to a single equilibrium point. One sees a problem with some of the equilibrium points, the other with the \emph{multiplicity} of equilibrium points. The central work on equilibrium selection is the book of Harsanyi and Selten~(1988). They take a number of positions in that work with which we have explicitly disagreed (or will disagree in what follows): the necessity of incorporating mistakes; the necessity of working with the extensive form; the rejection of forward induction type reasoning; the insistence on subgame consistency. We are, however, somewhat sympathetic to the basic enterprise. Whatever the answer to the question we address in this chapter there will remain in many games a multiplicity of equilibria, and thus some scope for selecting among them. And the work of Harsanyi and Selten will be a model for those who undertake this enterprise. \section{Admissibility and Iterated Dominance} \label{sec:adit} It is one thing to point to a specific equilibrium, like $(T,R)$ in Figure~\figref{subgame}, and claim that ``clearly'' it cannot be a self-enforcing assessment of the game; it is quite another matter to enunciate a principle that would capture the underlying intuition. One principle that immediately comes to mind is \emph{admissibility}, namely that rational players never choose dominated strategies. (As we discussed in the context of rationalizability in Section~\ref{sec:strength} a strategy is dominated if there exists another strategy yielding at least as high a payoff against any choice of the opponents and yielding a higher payoff against some such choice.) Indeed, admissibility rules out the equilibrium $(T,R)$ of Figure~\figref{subgame} (because $R$ is dominated by $L$). Furthermore, the admissibility principle immediately suggests an extension, \emph{iterated dominance}: If dominated strategies are never chosen, and if all players know this, all know \emph{this}, and so on, then a self-enforcing assessment of the game should be unaffected by the (iterative) elimination of dominated strategies. Thus, for example, the equilibrium $(T,L)$ of Figure~\figref{itdom} can be ruled out even though both $T$ and $L$ are admissible. (See Figure~\figref{itdom}a.) \begin{figure}[htbp] \begin{center} \begin{picture}(200,180)(-50,-10) %Fig itdom \put(0,0){\line(1,1){140}} \put(0,0){\line(-1,1){40}} \put(50,50){\line(-1,1){40}} \put(100,100){\line(-1,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(100,100){\circle*{4}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{2}} \put(104,98){\makebox(0,0)[tl]{1}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{$B$}} \put(28,70){\makebox(0,0)[tr]{$L$}} \put(72,70){\makebox(0,0)[tl]{$R$}} \put(78,120){\makebox(0,0)[tr]{$U$}} \put(122,120){\makebox(0,0)[tl]{$D$}} \put(-40,43){\makebox(0,0)[b]{$2,5$}} \put(10,93){\makebox(0,0)[b]{$0,0$}} \put(60,143){\makebox(0,0)[b]{$4,1$}} \put(140,143){\makebox(0,0)[b]{$-1,-1$}} \end{picture} \end{center} \fignumber{itdom} \end{figure} \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 2,5 & 2,5 \\ \cline{2-3} BU & 0,0 & 4,1 \\ \cline{2-3} BD & 0,0 & -1,-1 \\ \cline{2-3} \end{array} $$ } \bigskip \begin{center} Figure~\figref{itdom}a \end{center} \end{figure} At this point we might think we have nailed down the underlying principle separating self-enforcing equilibria from ones that are not self-enforcing. (Namely, that rational equilibria are unaffected by deletions of dominated strategies). However, nothing could be further from the truth: First, the principle cannot possibly be a general property of self-enforcing assessments, for the simple reason that it is self-contradictory; and second, the principle fails to weed out \emph{all} the equilibria that appear not to be self-enforcing. \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 2,0 & 1,0 \\ \cline{2-3} M & 0,1 & 0,0 \\ \cline{2-3} B & 0,0 & 0,1 \\ \cline{2-3} \end{array} $$ } \fignumber{selfc} \end{figure} On reflection, one realizes that admissibility and iterated dominance have somewhat inconsistent motivations. Admissibility says that whatever the assessment of how the game will be played, the strategies that receive zero weight in this assessment nevertheless remain relevant, at least when it comes to breaking ties. Iterated dominance, on the other hand, says that some such strategies, those that receive zero weight because they are inadmissible, are irrelevant and may be deleted. To see that this inconsistency in motivation actually leads to an inconsistency in the concepts, consider the game of Figure~\figref{selfc}. If a self-enforcing assessment were unaffected by the elimination of dominated strategies then Player~1's assessment of Player~2's choice would have to be $L$ (delete $B$ and then $R$) but it would also have to be $R$ (delete $M$ and then $L$). Thus the assessment of the outcome would have to be both $(2,0)$ and $(1,0)$. \begin{figure}[htbp] \begin{center} \begin{picture}(200,180)(-50,-10) %Fig irrat \put(0,0){\line(1,1){140}} \put(0,0){\line(-1,1){40}} \put(50,50){\line(-1,1){90}} \put(100,100){\line(-1,1){40}} \put(0,100){\line(1,1){40}} \put(0,100){\line(0,1){40}} \put(100,100){\line(0,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(100,100){\circle*{4}} \put(0,100){\circle*{4}} \multiput(0,100)(5,0){21}{\circle*{2}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{1}} \put(50,97){\makebox(0,0)[t]{2}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{$B$}} \put(28,70){\makebox(0,0)[tr]{$U$}} \put(72,70){\makebox(0,0)[tl]{$D$}} \put(78,120){\makebox(0,0)[tr]{$L$}} \put(98,120){\makebox(0,0)[br]{$C$}} \put(122,120){\makebox(0,0)[tl]{$R$}} \put(-22,120){\makebox(0,0)[tr]{$L$}} \put(-2,120){\makebox(0,0)[br]{$C$}} \put(22,120){\makebox(0,0)[tl]{$R$}} \put(-40,43){\makebox(0,0)[b]{$5,4$}} \put(140,143){\makebox(0,0)[b]{$6,3$}} \put(100,143){\makebox(0,0)[b]{$7,6$}} \put(60,143){\makebox(0,0)[bl]{$0,0$}} \put(40,143){\makebox(0,0)[br]{$6,3$}} \put(0,143){\makebox(0,0)[b]{$0,0$}} \put(-40,143){\makebox(0,0)[b]{$8,5$}} \end{picture} \end{center} \fignumber{irrat} \end{figure} \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{C} & \multicolumn{1}{c}{R} \\ \cline{2-4} T & 5,4 & 5,4 & 5,4 \\ \cline{2-4} BU & 8,5 & 0,0 & 6,3 \\ \cline{2-4} BD & 0,0 & 7,6 & 6,3 \\ \cline{2-4} \end{array} $$ } \bigskip \begin{center} Figure~\figref{irrat}a \end{center} \end{figure} To see the second point, consider the game of Figure~\figref{irrat}. As is evident from the normal form of Figure~\figref{irrat}a, there are no dominance relationships among the strategies, so all the equilibria satisfy our principle, and in particular those in which Player~1 plays $T$ (for example, $(T, .5L+.5C)$). And yet those equilibria appear not to be self-enforcing: indeed, if Player~1 played $B$ then he would be faced with the game of Figure~\figref{mult}, which he assesses as being worth more than 5 (recall that any self-enforcing assessment of the game of Figure~\figref{mult} has an outcome of either $(8,5)$ or $(7,6)$ or $(6,3)$); thus Player~1 must be expected to play~$B$ rather than~$T$. In the next section, we shall concentrate on the second problem, namely how to capture the intuition ruling out the outcome $(5,4)$ in Figure~\figref{irrat}. \section{Backward Induction} \label{sec:bi} \subsection{The Idea of Backward Induction} \label{sec:ideabi} Selten (1965,1975) proposed several ideas that may be summarized as the following \emph{principle of backward induction}: \medskip \emph{A self-enforcing assessment of the players' choices in a game tree must be consistent with a self-enforcing assessment of the choices from any node (or, more generally, information set) in the tree onwards.} \medskip This is a multi-person analog of ``the principle of dynamic programming'' (Bellman~1957), namely that an optimal strategy in a one-person decision tree must induce an optimal strategy from any point onward. The force of the backward induction condition is that it requires the players' assessments to be self-enforcing even in those parts of the tree that are ruled out by their own assessment of earlier moves. (As we have seen, the equilibrium condition by itself does not do this: one can take the ``wrong'' move at a node whose assessed probability is zero and still maximize one's expected payoff.) The principle of backward induction indeed eliminates the equilibria of the games of Figures \figref{subgame} and~\figref{itdom} that do not appear to be self-enforcing. For example, in the game of Figure~\figref{itdom} a self-enforcing assessment of the play starting at Player~1's second decision node must be that Player~1 would play $U$, therefore the assessment of the play starting at Player~2's decision node must be $BU$, and hence the assessment of the play of the full game must be $BRU$, that is, it is the equilibrium $(BU,R)$. Backward induction also eliminates the outcome $(5,4)$ in the game of Figure~\figref{irrat}. Indeed, any self-enforcing assessment of the play starting at Player~1's second decision node must impute to Player~1 a payoff greater than 5, so the assessment of Player~1's first move must be $B$. And it eliminates the equilibrium $(T,R,D)$ in the game of Figure~\figref{Selten} (which is taken from Selten 1975). Indeed, whatever the self-enforcing assessment of the play starting at Player~2's decision node, it certainly is not $(R,D)$ (because, if Player~2 expected Player~3 to choose $D$, then he would maximize his own payoff by choosing $L$ rather than $R$). \begin{figure}[htbp] \begin{center} \begin{picture}(250,180)(-150,-10) %Fig Selten \put(0,0){\line(1,1){90}} \put(0,0){\line(-1,1){140}} \put(50,50){\line(-1,1){90}} \put(-100,100){\line(1,1){40}} \put(0,100){\line(1,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(-100,100){\circle*{4}} \put(0,100){\circle*{4}} \multiput(0,100)(-5,0){21}{\circle*{2}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{2}} \put(-50,97){\makebox(0,0)[t]{3}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{$B$}} \put(28,70){\makebox(0,0)[tr]{$L$}} \put(72,70){\makebox(0,0)[tl]{$R$}} \put(-22,120){\makebox(0,0)[tr]{$U$}} \put(22,120){\makebox(0,0)[tl]{$D$}} \put(-122,120){\makebox(0,0)[tr]{$U$}} \put(-78,120){\makebox(0,0)[tl]{$D$}} \put(-140,143){\makebox(0,0)[b]{$0,0,0$}} \put(-60,143){\makebox(0,0)[br]{$3,2,2$}} \put(-40,143){\makebox(0,0)[bl]{$0,0,1$}} \put(40,143){\makebox(0,0)[b]{$4,4,0$}} \put(90,93){\makebox(0,0)[b]{$1,1,1$}} \end{picture} \end{center} \fignumber{Selten} \end{figure} There have been a number of attacks (Basu 1988, 1990, Ben-Porath 1995, Reny 1992a, 1993) on the idea of backward induction along the following lines. The requirement that the assessment be self-enforcing implicitly rests on the assumption that the players are rational and that the other players know that they are rational, and indeed, on higher levels of knowledge. Also, the requirement that a self-enforcing assessment be consistent with a self-enforcing assessment of the choices from any information set in the tree onwards seems to require that the assumption be maintained at that information set and onwards. And yet, that information set might only be reached if some player has taken an irrational action. In such a case the assumption that the players are rational and that their rationality is known to the others should not be assumed to hold in that part of the tree. For example, in the game of Figure~\figref{counter} there seems to be no compelling reason why Player~2, if called on to move, should be assumed to know of Player~1's rationality. Indeed, since he has observed something that contradicts Player~1 being rational, perhaps Player~2 \emph{must} believe that Player~1 is not rational. \begin{figure}[htbp] \begin{center} \begin{picture}(200,180)(-50,-10) %Fig counter \put(0,0){\line(1,1){140}} \put(0,0){\line(-1,1){40}} \put(50,50){\line(-1,1){40}} \put(100,100){\line(-1,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(100,100){\circle*{4}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{2}} \put(104,98){\makebox(0,0)[tl]{1}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{$B$}} \put(28,70){\makebox(0,0)[tr]{$L$}} \put(72,70){\makebox(0,0)[tl]{$R$}} \put(78,120){\makebox(0,0)[tr]{$U$}} \put(122,120){\makebox(0,0)[tl]{$D$}} \put(-40,43){\makebox(0,0)[b]{$3,3$}} \put(10,93){\makebox(0,0)[b]{$1,1$}} \put(60,143){\makebox(0,0)[b]{$0,0$}} \put(140,143){\makebox(0,0)[b]{$2,2$}} \end{picture} \end{center} \fignumber{counter} \end{figure} The example however does suggest the following observation: the part of the tree following an irrational move is anyway irrelevant (because a rational player is sure not to take such a move), so whether or not rational players can assess what would happen there has no bearing on their assessment of how the game would actually be played (for example, in the game of Figure~\figref{counter} the rational assessment of the outcome is $(3,3)$, regardless of what Player~2's second choice might be). While this line of reasoning is quite convincing in a situation like that of Figure~\figref{counter}, where the irrationality of the move $B$ is self evident, it is less convincing in, say Figure~\figref{itdom}. There, the rationality or irrationality of the move $B$ becomes evident only after consideration of what would happen if $B$ \emph{were} taken, that is, only after consideration of what in retrospect appears ``counterfactual'' (Binmore 1990). One approach to this is to consider what results when we no longer assume that the players are known to be rational following a deviation by one (or more) from a candidate self-enforcing assessment. Reny~(1992a) and, though it is not the interpretation they give, Fudenberg, Kreps, and Levine~(1988) show that such a program leads to few restrictions beyond the requirements of strategic equilibrium. We shall discuss this a little more at the end of Section~\ref{sec:perfect}. And yet, perhaps one can make some argument for the idea of backward induction. The argument of Reny~(1992a), for example, allows a deviation from the candidate equilibrium to be an indication to the other players that the assumption that all of the players were rational is not valid. In other words the players are no more sure about the nature of the game than they are about the equilibrium being played. We may recover some of the force of the idea of backward induction by requiring the equilibrium to be robust against a little strategic uncertainty. Thus we argue that the requirement of backward induction results from a series of tests. If indeed a rational player, in a situation in which the rationality of all players is common knowledge, would not take the action that leads to a certain information set being reached then it matters little what the assessment prescribes at that information set. To check whether the hypothesis that a rational player, in a situation in which the rationality of all players is common knowledge, wouldn't take that action we suppose that he would and see what could arise. If all self-enforcing assessments of the situation following a deviation by a particular player would lead to him deviating then we reject the hypothesis that such a deviation contradicts the rationality of the players. And so, of course, we reject the candidate assessment as self-enforcing. If however our analysis of the situation confirms that there is a self-enforcing assessment in which the player, if rational, would not have taken the action, then our assessment of him not taking the action is confirmed. In such a case we have no reason to insist on the results of our analysis following the deviation. Moreover, since we assume that the players are rational and our analysis leads us to conclude that rational players will not play in this part of the game we are forced to be a little imprecise about what our assessment says in that part of the game. This relates to our discussion of sets of equilibria as solutions of the game in Section~\ref{sec:sets}. This modification of the notion of backward induction concedes that there may be conceivable circumstances in which the common knowledge of rationality of the players would, of necessity, be violated. It argues, however, that if the players are sure enough of the nature of the game, including the rationality of the other players, that they abandon this belief only in the face of truly compelling evidence, that the behavior in such circumstances is essentially irrelevant. The principle of backward induction is completely dependent on the extensive form of the game. For example, while it excludes the equilibrium $(T,L)$ in the game of Figure~\figref{itdom}, it does not exclude the same equilibrium in the game of Figure~\figref{itdom}a (that is, in an extensive form where the players simultaneously choose their strategies). Thus one might see an inconsistency between the principle of backward induction and von Neumann and Morgenstern's reduction of the extensive form to the strategic form. We would put a somewhat different interpretation on the situation. The claim that the strategic form contains sufficient information for strategic analysis is not a denial that some games have an extensive structure. Nor is it a denial that valid arguments, such as backward induction arguments, can be made in terms of that structure. Rather the point is that, were a player, instead of choosing through the game, required to decide in advance what he will do, he could consider in advance any of the issues that would lead him to choose one way or the other during the game. And further, these issues will affect his incentives in precisely the same way when he considers them before playing as they would had he considered them during the play of the game. In fact, we shall see in Section~\ref{sec:fibi} that the sufficiency of the normal form substantially strengthens the implications of backward induction arguments. We put off that discussion for now. We do note however that others have taken a different position. Selten's position, as well as the position of a number of others, is that the reduction to the strategic form is unwarranted, because it involves loss of information. Thus Figures \figref{irrat} and~\figref{irrat}a represent fundamentally different games, and $(5,4)$ is indeed not self-enforcing in the former but possibly is self-enforcing in the latter. (Recall that this equilibrium cannot be excluded by the strategic-form arguments we have given to date, such as deletions of dominated strategies, but can be excluded by backward induction in the tree). \subsection{Subgame Perfection} \label{sec:subgame} We now return to give a first pass at giving a formal expression of the idea of backward induction. The simplest case to consider is of a node such that the part of the tree from the node onwards can be viewed as a separate game (a ``subgame''), that is, it contains every information set which it intersects (in particular, the node itself must be an information set). Because the rational assessment of any game must constitute an equilibrium, we have the following implication of backward induction (\emph{subgame perfection,} Selten 1965): \medskip \emph{The equilibrium of the full game must induce an equilibrium on every subgame.} \medskip The subgame-perfect equilibria of a game can be determined by working from the ends of the tree to its root, each time replacing a subgame by (the expected payoff of) one of its equilibria. We must show that indeed a profile of strategies obtained by means of step-by-step replacement of subgames with equilibria constitutes a subgame-perfect equilibrium. If not, then there is a smallest subgame in which some player's strategy fails to maximize his payoff (given the strategies of the others). But this is impossible, because the player has maximized his payoff given his own choices in the subgames of the subgame, and those he is presumed to have chosen optimally. For example, in the game of Figure~\figref{itdom}, the subgame whose root is at Player~1's second decision node can be replaced by $(4,1)$, so the subgame whose root is at Player~2's decision node can also be replaced by this outcome, and similarly for the whole tree. Or in the game of Figure~\figref{irrat}, the subgame (of Figure~\figref{mult}) can be replaced by one of its equilibria, namely $(8,5), (7,6)$ or $(6,3)$. Since any of them give Player~1 more than 5, Player~1's first move must be $B$. Thus all three outcomes are subgame perfect, but the additional equilibrium outcome, $(5,4)$, is not. Because the process of step-by-step replacement of subgames by their equilibria will always yield at least one profile of strategies, we have the following result. \begin{theorem}[Selten 1965] Every game tree has at least one subgame-perfect equilibrium. \end{theorem} Subgame perfection captures only one aspect of the principle of backward induction. We shall consider other aspects of the principle in Sections \ref{sec:seq} and~\ref{sec:perfect}. \subsection{Sequential Equilibrium} \label{sec:seq} To see that subgame perfection does not capture all that is implied by the idea of backward induction it suffices to consider quite simple games. While subgame perfection clearly isolates the self-enforcing outcome in the game of Figure~\ref{fig:subgame} it does not do so in the game of Figure~\ref{fig:subgamealt}, in which the issues seem largely the same. And we could even modify the game a little further so that it becomes difficult to give a presentation of the game in which subgame perfection has any bite. (Say, by having Nature first decide whether Player~1 obtains a payoff of 5 after $M$ or after $B$ and informing Player~1, but not Player~2.) \begin{figure}[htbp] \begin{center} \begin{picture}(200,130)(-50,40) %Fig subgamealt %\put(0,25){\line(4,3){100}} %\put(0,25){\line(-1,1){40}} %\put(0,25){\line(0,1){75}} \put(50,50){\line(1,1){50}} \put(50,50){\line(-1,1){50}} \put(50,50){\line(-5,2){70}} \put(100,100){\line(-1,1){40}} \put(100,100){\line(1,1){40}} \put(0,100){\line(-1,1){40}} \put(0,100){\line(1,1){40}} \put(50,50){\circle*{4}} \put(100,100){\circle*{4}} \put(0,100){\circle*{4}} \multiput(0,100)(5,0){21}{\circle*{2}} \put(54,48){\makebox(0,0)[t]{1}} \put(50,97){\makebox(0,0)[t]{2}} \put(15,62){\makebox(0,0)[tr]{$T$}} \put(18,80){\makebox(0,0)[tr]{$M$}} \put(82,80){\makebox(0,0)[tl]{$B$}} \put(78,120){\makebox(0,0)[tr]{$L$}} \put(122,120){\makebox(0,0)[tl]{$R$}} \put(-22,120){\makebox(0,0)[tr]{$L$}} \put(22,120){\makebox(0,0)[tl]{$R$}} \put(-20,81){\makebox(0,0)[b]{$2,5$}} \put(140,143){\makebox(0,0)[b]{$0,0$}} \put(60,143){\makebox(0,0)[bl]{$4,1$}} \put(40,143){\makebox(0,0)[br]{$0,0$}} \put(-40,143){\makebox(0,0)[b]{$5,1$}} \end{picture} \end{center} \fignumber{subgamealt} \end{figure} One way of capturing more of the idea of backward induction is by explicitly requiring players to respond optimally at all information sets. The problem is, of course, that, while in the game of Figure~\ref{fig:subgamealt} it is clear what it means for Player~2 to respond optimally, this is not generally the case. In general, the optimal choice for a player will depend on exactly which node of his information set has been reached. And, at an out of equilibrium information set this may not be determined by the strategies of his opponents. The concept of sequential equilibrium recognizes this by defining an equilibrium to be a pair consisting of a behavioral strategy and a system of beliefs. A \emph{system of beliefs} gives, for each information set, a probability distribution over the nodes of that information set. The behavioral strategy is said to be \emph{sequentially rational} with respect to the system of beliefs if, at every information set at which a player moves, it maximizes the conditional payoff of the player, given his beliefs at that information set and the strategies of the other players. A system of beliefs is said to be \emph{consistent} with a behavioral strategy if it is the limit of a sequence of beliefs each being the actual conditional distribution on nodes of the various information sets induced by a sequence of completely mixed behavioral strategies converging to the given behavioral strategy. A \emph{sequential equilibrium} is a pair such that the strategy is sequentially rational with respect to the beliefs and the beliefs are consistent with the strategy. The idea of a strategy being sequentially rational appears quite straightforward and intuitive. However the concept of consistency is somewhat less natural. Kreps and Wilson (1982) attempted to provide a more primitive justification for the concept, but, as was shown by Kreps and Ramey (1987) this justification was fatally flawed. Kreps and Ramey suggest that this throws doubt on the notion of consistency. (They also suggest that the same analysis casts doubt on the requirement of sequential rationality. At an unreached information set there is some question of whether a player should believe that the future play will correspond to the equilibrium strategy. We shall not discuss this further.) Recent work has suggested that the notion of consistency is a good deal more natural than Kreps and Ramey suggest. In particular Kohlberg and Reny~(1994) show that it follows quite naturally from the idea that the players' assessments of the way the game will be played reflects certainty or stationarity in the sense that it would not be affected by the actual realizations observed in an identical situation. Related ideas are explored by Battigalli~(1994) and Swinkels~(1994). We shall not go into any detail here. The concept of sequential equilibrium is a strengthening of the concept of subgame perfection. Any sequential equilibrium is necessarily subgame perfect, while the converse is not the case. For example, it is easy to verify that in the game of Figure~\ref{fig:subgamealt} the unique sequential equilibrium involves I choosing $M$. And a similar result holds for the modification of that game involving a move of Nature discussed above. Notice also that the concept of sequential equilibrium, like that of subgame perfection, is quite sensitive to the details of the extensive form. For example in the extensive form game of Figure~\ref{fig:seq-a} there is a sequential equilibrium in which Player~1 plays $T$ and Player~2 plays $L$. However in a very similar situation (we shall later argue strategically identical)---that of Figure~\ref{fig:seq-b}---there is no sequential equilibrium in which Player~1 plays $T$. The concepts of extensive form perfect equilibrium and quasi-perfect equilibrium that we discuss in the following section also feature this sensitivity to the details of the extensive form. In these games they coincide with the sequential equilibria. \begin{figure}[htbp] \begin{center} \begin{picture}(200,130)(-50,40) %Fig seq-a %\put(0,25){\line(4,3){100}} %\put(0,25){\line(-1,1){40}} %\put(0,25){\line(0,1){75}} \put(50,50){\line(1,1){50}} \put(50,50){\line(-1,1){50}} \put(50,50){\line(-5,2){70}} \put(100,100){\line(-1,1){40}} \put(100,100){\line(1,1){40}} \put(0,100){\line(-1,1){40}} \put(0,100){\line(1,1){40}} \put(50,50){\circle*{4}} \put(100,100){\circle*{4}} \put(0,100){\circle*{4}} \multiput(0,100)(5,0){21}{\circle*{2}} \put(54,48){\makebox(0,0)[t]{1}} \put(50,97){\makebox(0,0)[t]{2}} \put(15,62){\makebox(0,0)[tr]{$T$}} \put(18,80){\makebox(0,0)[tr]{$M$}} \put(82,80){\makebox(0,0)[tl]{$B$}} \put(78,120){\makebox(0,0)[tr]{$L$}} \put(122,120){\makebox(0,0)[tl]{$R$}} \put(-22,120){\makebox(0,0)[tr]{$L$}} \put(22,120){\makebox(0,0)[tl]{$R$}} \put(-20,81){\makebox(0,0)[b]{$3,5$}} \put(140,143){\makebox(0,0)[b]{$2,0$}} \put(60,143){\makebox(0,0)[bl]{$1,1$}} \put(-40,143){\makebox(0,0)[br]{$2,0$}} \put(40,143){\makebox(0,0)[b]{$4,1$}} \end{picture} \end{center} \fignumber{seq-a} \end{figure} \begin{figure}[htbp] \begin{center} \begin{picture}(200,180)(-50,-10) %Fig seq-b \put(0,0){\line(1,1){140}} \put(0,0){\line(-1,1){40}} \put(50,50){\line(-1,1){90}} \put(100,100){\line(-1,1){40}} \put(0,100){\line(1,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(100,100){\circle*{4}} \put(0,100){\circle*{4}} \multiput(0,100)(5,0){21}{\circle*{2}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{1}} \put(50,97){\makebox(0,0)[t]{2}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{\it IN}} \put(28,70){\makebox(0,0)[tr]{$M$}} \put(72,70){\makebox(0,0)[tl]{$B$}} \put(78,120){\makebox(0,0)[tr]{$L$}} \put(122,120){\makebox(0,0)[tl]{$R$}} \put(-22,120){\makebox(0,0)[tr]{$L$}} \put(22,120){\makebox(0,0)[tl]{$R$}} \put(-40,43){\makebox(0,0)[b]{$3,5$}} \put(140,143){\makebox(0,0)[b]{$2,0$}} \put(60,143){\makebox(0,0)[bl]{$1,1$}} \put(40,143){\makebox(0,0)[br]{$4,1$}} \put(-40,143){\makebox(0,0)[b]{$2,0$}} \end{picture} \end{center} \fignumber{seq-b} \end{figure} \subsection{Perfect Equilibrium} \label{sec:perfect} The sequential equilibrium concept is closely related to a similar concept defined earlier by Selten~(1975), the perfect equilibrium. Another closely related concept, which we shall argue is in some ways preferable, was defined by van Damme~(1984) and called the quasi-perfect equilibrium. Both of these concepts, like sequential equilibrium, are defined explicitly on the extensive form, and depend essentially on details of the extensive form. (They can, of course, be defined for a simultaneous move extensive form game, and to this extent can be thought of as defined for normal form games.) When defining these concepts we shall assume that the extensive form games satisfy perfect recall. Myerson~(1978) defined a normal form concept that he called proper equilibrium. This is a refinement of the concepts of Selten and van Damme when those concepts are applied to normal form games. Moreover there is a remarkable relation between the normal form concept of proper equilibrium and the extensive form concept quasi-perfect equilibrium. Let us start by describing the definition of perfect equilibrium. The original idea of Selten was that however close to rational players were they would never be perfectly rational. There would always be some chance that a player would make a mistake. This idea may be implemented by approximating a candidate equilibrium strategy profile by a nearby completely mixed strategy profile and requiring that any of the deliberately chosen actions, that is, those given positive probability in the candidate strategy profile, be optimal, not only against the candidate strategy profile, but also against the nearby mixed strategy profile. If we are defining extensive form perfect equilibrium, a strategy is interpreted to mean a behavioral strategy and an action to mean an action at some information set. More formally, a profile of behavioral strategies $b$ is a perfect equilibrium if there is a sequence of completely mixed behavioral strategy profiles $\{b^t\}$ such that at each information set and for each $b^t$, the behavior of $b$ at the information set is optimal against $b^t$, that is, is optimal when behavior at all other information sets is given by $b^t$. If the definition is applied instead to the normal form of the game the resulting equilibrium is called a \emph{normal form perfect equilibrium}. Like sequential equilibrium, (extensive form) perfect equilibrium is an attempt to express the idea of backward induction. Any perfect equilibrium is a sequential equilibrium (and so is a subgame perfect equilibrium). Moreover the following result tells us that, except for exceptional games, the converse is also true. \begin{theorem}[Kreps and Wilson 1982, Blume and Zame 1994] For any extensive form, except for a closed set of payoffs of lower dimension than the set of all possible payoffs, the sets of sequential equilibrium strategy profiles and perfect equilibrium strategy profiles coincide. \end{theorem} The concept of normal form perfect equilibrium, on the other hand, can be thought of as a strong form of admissibility. In fact for two player games the sets of normal form perfect and admissible equilibria coincide. In games with more players the sets may differ. However there is a sense in which even in these games normal form perfection seems to be a reasonable expression of admissibility. Mertens~(1987) gives a definition of the admissible best reply correspondence that would lead to fixed points of this correspondence being normal form perfect equilibria, and argues that this definition corresponds ``to the intuitive idea that would be expected from a concept of `admissible best reply' in a framework of independent priors.'' (Mertens 1987, p. 15.) Mertens~(1991b) offers the following example in which the set of extensive form perfect equilibria and the set of admissible equilibria have an empty intersection. The game may be thought of in the following way. Two players agree about how a certain social decision should be made. They have to decide who should make the decision and they do this by voting. If they agree on who should make the decision that player decides. If they each vote for the other then the good decision is taken automatically. If each votes for himself then a fair coin is tossed to decide who makes the decision. A player who makes the social decision is not told if this is so because the other player voted for him, or because the coin toss chose him. The extensive form of this game is given in Figure~\figref{mertensa}. The payoffs are such that each player prefers the good outcome to the bad outcome. However, if the bad outcome is chosen a player will feel slightly worse if he was the one who made the decision, than if it was the other player. We could associate, for example the payoff $(10,10)$ to the outcome $G$, $(0,1)$ to $B_1$, and $(1,0)$ to $B_{2}$. \begin{figure}[htbp] \begin{center} \begin{picture}(0,250)(0,-20) %Fig mertensa \put(0,0){\line(1,1){190}} \put(0,0){\line(-1,1){190}} \put(50,50){\line(-1,1){48}} \put(-50,50){\line(0,1){50}} \put(-150,150){\line(1,1){40}} \put(-50,150){\line(1,1){40}} \put(50,150){\line(-1,1){40}} \put(150,150){\line(-1,1){40}} \put(-90,190){\line(1,-1){88}} \put(90,190){\line(-1,-1){88}} \multiput(-50,50)(5,0){21}{\circle*{2}} \multiput(-150,150)(5,0){21}{\circle*{2}} \multiput(50,150)(5,0){21}{\circle*{2}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(-50,50){\circle*{4}} \put(-150,150){\circle*{4}} \put(-50,150){\circle*{4}} \put(50,150){\circle*{4}} \put(150,150){\circle*{4}} \put(0,100){\circle{4}} \put(4,-2){\makebox(0,0)[t]{1}} \put(0,48){\makebox(0,0)[t]{2}} \put(100,148){\makebox(0,0)[t]{1}} \put(-100,148){\makebox(0,0)[t]{2}} \put(22,20){\makebox(0,0)[tl]{me}} \put(-22,20){\makebox(0,0)[tr]{him}} \put(-72,70){\makebox(0,0)[tr]{me}} \put(72,70){\makebox(0,0)[tl]{him}} \put(-48,70){\makebox(0,0)[tl]{him}} \put(28,70){\makebox(0,0)[tr]{me}} \put(-18,122){\makebox(0,0)[bl]{$\frac{1}{2}$}} \put(18,122){\makebox(0,0)[br]{$\frac{1}{2}$}} \multiput(-172,170)(100,0){4}{\makebox(0,0)[tr]{$R$}} \multiput(-128,170)(100,0){4}{\makebox(0,0)[tl]{$W$}} \multiput(-190,192)(100,0){4}{\makebox(0,0)[b]{$G$}} \put(-50,102){\makebox(0,0)[b]{$G$}} \multiput(-110,192)(100,0){2}{\makebox(0,0)[b]{$B_{2}$}} \multiput(90,192)(100,0){2}{\makebox(0,0)[b]{$B_{1}$}} \end{picture} \end{center} \fignumber{mertensa} \end{figure} In this game the only admissible equilibrium has both players voting for themselves and taking the right choice if they make the social decision. However, any perfect equilibrium must involve at least one of the players voting for the other with certainty. At least one of the players must be at least as likely as the other to make a mistake in the second stage. And such a player, against such mistakes, does better to vote for the other. \subsection{Perfect Equilibrium and Proper Equilibrium} The definition of perfect equilibrium may be thought of as corresponding to the idea that players really do make mistakes, and that in fact it is not possible to think coherently about games in which there is no possibility of the players making mistakes. On the other hand one might think of the perturbations as instead encompassing the idea that the players should have a little strategic uncertainty, that is, they should not be completely confident as to what the other players are going to do. In such a case a player should not be thought of as being uncertain about his own actions or planned actions. This is (one interpretation of) the idea behind van Damme's definition of quasi-perfect equilibrium. That definition is largely the same as the definition of perfect equilibrium. The definitions differ only in that, instead of the limit strategy $b$ being optimal at each information set against behavior given by $b^t$ at \emph{all} other information sets, it is required that $b$ be optimal at all information sets against behavior at other information sets given by $b$ for information sets that are owned by the same player who owns the information set in question, and by $b^t$ for other information sets. The assumption of perfect recall guarantees that this requirement of optimality is well defined. That is, the player does not take account of his own ``mistakes,'' except to the extent that they may make one of his information sets reached that otherwise would not be. This change in the definition leads to some attractive properties. Like perfect equilibria, quasi-perfect equilibria are sequential equilibrium strategies. But, unlike perfect equilibria, quasi-perfect equilibria are always normal form perfect, and thus admissible. Mertens~(1991b) argues that quasi-perfect equilibrium is precisely the right mixture of admissibility and backward induction. Also, as we remarked earlier, there is a relation between quasi-perfect equilibria and proper equilibria. A \emph{proper equilibrium} (Myerson 1978) is defined to be a limit of $\varepsilon$-proper equilibria. An \emph{$\varepsilon$-proper equilibrium} is a completely mixed strategy vector such that for each player if, given the strategies of the others, one strategy is strictly worse than another the first strategy is played with probability at most $\varepsilon$ times the probability with which the second is played. In other words, more costly mistakes are made with lower frequency. Van Damme~(1984) proved the following result. (Kohlberg and Mertens~(1986) proved a similar result, replacing quasi-perfect with sequential.) \begin{theorem} A proper equilibrium of a normal form game is quasi-perfect in any extensive form game having that normal form. \end{theorem} van Damme actually states his theorem a little differently referring simply to a pair of games, one an extensive form game and the other the corresponding normal form. (He is also more explicit about the sense in which a quasi-perfect equilibrium, a behavioral strategy profile, \emph{is} a proper equilibrium, a mixed strategy profile.) Thus he correctly states that the converse of his theorem is not true. There are such pairs of games and quasi-perfect equilibria of the extensive form that are in no sense equivalent to a proper equilibrium of the normal form. Kohlberg and Mertens~(1986) state their theorem in the same form as we do, but refer to sequential equilibria rather than quasi-perfect equilibria. They too correctly state that the converse is not true. For any normal form game one could introduce dummy players, one for each profile of strategies having payoff one at that profile of strategies and zero otherwise. In any extensive form having that normal form the set of sequential equilibrium strategy profiles would be the same as the set of equilibrium strategy profiles originally. \begin{figure}[htbp] \begin{center} \begin{picture}(250,180)(-150,-10) %Fig vd \put(0,0){\line(1,1){90}} \put(0,0){\line(-1,1){140}} \put(50,50){\line(-1,1){90}} \put(-100,100){\line(1,1){40}} \put(0,100){\line(1,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(-100,100){\circle*{4}} \put(0,100){\circle*{4}} \multiput(0,100)(-5,0){21}{\circle*{2}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{1}} \put(-50,97){\makebox(0,0)[t]{2}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{$B$}} \put(28,70){\makebox(0,0)[tr]{$U$}} \put(72,70){\makebox(0,0)[tl]{$D$}} \put(-22,120){\makebox(0,0)[tr]{$L$}} \put(22,120){\makebox(0,0)[tl]{$R$}} \put(-122,120){\makebox(0,0)[tr]{$L$}} \put(-78,120){\makebox(0,0)[tl]{$R$}} \put(-140,143){\makebox(0,0)[bl]{$4,1$}} \put(-60,143){\makebox(0,0)[br]{$1,0$}} \put(-40,143){\makebox(0,0)[bl]{$0,0$}} \put(40,143){\makebox(0,0)[br]{$0,1$}} \put(90,93){\makebox(0,0)[b]{$2,2$}} \end{picture} \end{center} \fignumber{vd} \end{figure} \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{r|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 4,1 & 1,0 \\ \cline{2-3} BU & 0,0 & 0,1 \\ \cline{2-3} BD & 2,2 & 2,2 \\ \cline{2-3} \end{array} $$ } \bigskip \begin{center} Figure~\figref{vd}a \end{center} \end{figure} \begin{figure}[htbp] \begin{center} \begin{picture}(0,180)(0,-10) %Fig vd2 \put(0,0){\line(1,1){140}} \put(0,0){\line(-1,1){140}} \put(50,50){\line(-1,1){90}} \put(-100,100){\line(1,1){40}} \put(0,100){\line(1,1){40}} \put(100,100){\line(-1,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(-100,100){\circle*{4}} \put(0,100){\circle*{4}} \put(100,100){\circle*{4}} \multiput(-100,100)(5,0){41}{\circle*{2}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{1}} \put(-50,97){\makebox(0,0)[t]{2}} \put(-22,20){\makebox(0,0)[tr]{$BD$}} \put(28,70){\makebox(0,0)[tr]{$T$}} \put(72,70){\makebox(0,0)[tl]{$BU$}} \put(-22,120){\makebox(0,0)[tr]{$L$}} \put(22,120){\makebox(0,0)[tl]{$R$}} \put(-122,120){\makebox(0,0)[tr]{$L$}} \put(-78,120){\makebox(0,0)[tl]{$R$}} \put(78,120){\makebox(0,0)[tr]{$L$}} \put(122,120){\makebox(0,0)[tl]{$R$}} \put(-140,143){\makebox(0,0)[bl]{$2,2$}} \put(-60,143){\makebox(0,0)[br]{$2,2$}} \put(-40,143){\makebox(0,0)[bl]{$4,1$}} \put(40,143){\makebox(0,0)[br]{$1,0$}} \put(60,143){\makebox(0,0)[bl]{$0,0$}} \put(140,143){\makebox(0,0)[br]{$0,1$}} \end{picture} \end{center} \fignumber{vd2} \end{figure} However it is not immediately clear that the converse of the theorem as we have stated it is not true. Certainly we know of no example in the previous literature that shows it to be false. For example, van Damme~(1991) adduces the game given in extensive form in Figure~\figref{vd} and in normal form in Figure~\figref{vd}a to show that a quasi-perfect equilibrium may not be proper. The strategy $(BD,R)$ is quasi-perfect, but not proper. Nevertheless there is a game---that of Figure~\figref{vd2}---having the same normal form, up to duplication of strategies, in which that strategy is not quasi-perfect. Thus one might be tempted to conjecture, as we did in an earlier version of this chapter, that given a normal form game, any strategy vector that is quasi-perfect in any extensive form game having that normal form would be a proper equilibrium of the normal form game. A fairly weak version of this conjecture is true. We fix not only the equilibrium under consideration but also the sequence of completely mixed strategies converging to it. \begin{theorem} \label{theorem:MSS} An equilibrium $\sigma$ of a normal form game $G$ is supported as a proper equilibrium by a sequence of completely mixed strategies $\{\sigma^k\}$ with limit $\sigma$ if and only if $\{\sigma^k\}$ induces a quasi-perfect equilibrium in any extensive form game having the normal form $G$. \end{theorem} \begin{proof}[Sketch of Proof] This is proved in Hillas~(1996). A slightly weaker version of this theorem is proved in Mailath, Samuelson and Swinkels (1995), using quite different methods. The if direction is implied by van Damme's proof. (Though not quite by the result as he states it, since that leaves open the possibility that different extensive forms may require different supporting sequences.) The other direction is quite straightforward. One first takes a subsequence such that the conditional probability on any subset of a player's strategy space converges. (This conditional probability is well defined since the strategy vectors in the sequence are assumed to be completely mixed.) Thus $\{\sigma^k\}$ defines, for any subset of a player's strategy space, a conditional probability on that subset. And so the sequence $\{\sigma^k\}$ partitions the strategy space $S_n$ of each player into the sets $S^0_n, S^1_n, \dots , S^J_n$ where $S^j_n$ is the set of those strategies that receive positive probability conditional on one of the strategies in $S_n\backslash (\cup_{ij$ and is assigned probability arbitrarily greater than any such strategy. Thus $\{\sigma^k\}$ supports $\sigma$ as a proper equilibrium. \end{proof} However, the conjecture as we originally stated it---that is, without any reference to the supporting sequences of completely mixed strategies---is not true. Consider the game of Figure~\figref{counter_example}. The equilibrium $(A,V)$ is not proper. To see this we argue as follows. Given that Player~1 plays $A$, Player~2 strictly prefers $W$ to $Y$ and $X$ to $Y$. Thus in any $\varepsilon$-proper equilibrium $Y$ is played with at most $\varepsilon$ times the probability of $W$, and also at most $\varepsilon$ times the probability of $X$. The fact that $Y$ is less likely than $W$ implies that Player~1 strictly prefers $B$ to $C$, while the fact that $Y$ is less likely than $X$ implies that Player~1 strictly prefers $B$ to $D$. Thus in an $\varepsilon$-proper equilibrium $C$ and $D$ are both played with at most $\varepsilon$ times the probability of $B$. This in turn implies that Player~2 strictly prefers $Z$ to $V$, and so there can be no $\varepsilon$-proper equilibrium in which $V$ is played with probability close to 1. Thus $(A,V)$ is not proper. \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} \[ \begin{array}{r|c|c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{V} & \multicolumn{1}{c}{W} & \multicolumn{1}{c}{X} & \multicolumn{1}{c}{Y} & \multicolumn{1}{c}{Z} \\ \cline{2-6} A & 1,1 & 3,1 & 3,1 & 0,0 & 1,1 \\ \cline{2-6} B & 1,1 & 2,0 & 2,0 & 0,0 & 1,2 \\ \cline{2-6} C & 1,1 & 1,0 & 2,1 & 1,0 & 1,0 \\ \cline{2-6} D & 1,1 & 2,1 & 1,0 & 1,0 & 1,0 \\ \cline{2-6} \end{array} \] } \bigskip \fignumber{counter_example} \end{figure} Nevertheless, in any extensive form game having this normal form there are perfect---and quasi-perfect---equilibria equivalent to $(A,V)$. The idea is straightforward and not at all delicate. In order to argue that $(A,V)$ was not proper we needed to deduce, from the fact that Player~2 strictly prefers $W$ to $Y$ and $X$ to $Y$ that $Y$ is played with much smaller probability than $W$, and much smaller probability than $X$. However there is no extensive representation of this game in which quasi-perfection has this implication. For example, consider an extensive form in which Player~2 first decides whether to play $W$ and, if he decides not to, then decides between $X$ and $Y$. Now if all we may assume is that Player~2 strictly prefers $W$ to $Y$ and $X$ to $Y$ then we cannot rule out that Player~2 strictly prefers $X$ to $W$. And in that case it is consistent with the requirements of either quasi-perfectness or perfectness that the action $W$ is taken with probability $\varepsilon^2$ and the action $Y$ with probability $\varepsilon$. This results in the strategy $Y$ being played with substantially greater probability than the strategy $W$. Something similar results for any other way of structuring Player~2's choice. See Hillas~(1996) for greater detail. \subsection{Uncertainties about the Game} Having now defined normal form perfect equilibrium we are in a position to be a little more explicit about the work of Fudenberg, Kreps, and Levine~(1988) and of Reny~(1992a), which we mentioned in Section~\ref{sec:ideabi}. These papers, though quite different in style, both show that if an out of equilibrium action can be taken to indicate that the player taking that action is not rational, or equivalently, that his payoffs are not as specified in the game, then any normal form perfect equilibrium is self-enforcing. Fudenberg, Kreps and Levine also show that if an out of equilibrium action can be taken to indicate that the game was not as originally described---so that others' payoffs may differ as well---then \emph{any} strategic equilibrium is self-enforcing. \section{Forward Induction} \label{sec:for} In the previous section we examined the idea of backward induction, and also combinations of backward induction and admissibility. If we suppose that we have captured the implications of this idea, are there any further considerations that would further narrow the set of self-enforcing assessments? Consider the game of Figure~\figref{KM} (Kohlberg and Mertens 1982 and 1986). Here, every node can be viewed as a root of a subgame, so there is no further implication of ``backward induction'' beyond ``subgame perfection''. Since the outcome $(2,5)$ (that is, the equilibrium where Player~1 plays $T$ and the play of the subgame is $(D,R)$) is subgame perfect, it follows that backward induction cannot exclude it. \begin{figure}[htbp] \begin{center} \begin{picture}(200,180)(-50,-10) %Fig KM \put(0,0){\line(1,1){140}} \put(0,0){\line(-1,1){40}} \put(50,50){\line(-1,1){90}} \put(100,100){\line(-1,1){40}} \put(0,100){\line(1,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(100,100){\circle*{4}} \put(0,100){\circle*{4}} \multiput(0,100)(5,0){21}{\circle*{2}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{1}} \put(50,97){\makebox(0,0)[t]{2}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{$B$}} \put(28,70){\makebox(0,0)[tr]{$U$}} \put(72,70){\makebox(0,0)[tl]{$D$}} \put(78,120){\makebox(0,0)[tr]{$L$}} \put(122,120){\makebox(0,0)[tl]{$R$}} \put(-22,120){\makebox(0,0)[tr]{$L$}} \put(22,120){\makebox(0,0)[tl]{$R$}} \put(-40,43){\makebox(0,0)[b]{$2,5$}} \put(140,143){\makebox(0,0)[b]{$1,4$}} \put(60,143){\makebox(0,0)[bl]{$0,0$}} \put(40,143){\makebox(0,0)[br]{$0,0$}} \put(-40,143){\makebox(0,0)[b]{$4,1$}} \end{picture} \end{center} \fignumber{KM} \end{figure} \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 2,5 & 2,5 \\ \cline{2-3} BU & 4,1 & 0,0 \\ \cline{2-3} BD & 0,0 & 1,4 \\ \cline{2-3} \end{array} $$ } \bigskip \begin{center} Figure~\figref{KM}a \end{center} \end{figure} On the other hand, this outcome cannot possibly represent a self-enforcing assessment of the game. Indeed, in considering the contingency of Player~1's having played $B$, Player~2 must take it for granted that Player~1's subsequent move was $U$ and not $D$ (because a rational Player~1 will not plan to play $B$ and then $D$, which can yield a maximum of 1, when he can play $T$ for a sure 2). Thus the assessment of Player~1's second move must be $U$, and hence the assessment of Player~2's move must be $L$, which implies that the assessment of the whole game must be $(4,1)$. Notice that this argument does not depend on the order in which Players 1 and 2 move in the subgame. If the order was reversed so that Player~2 moved first in the subgame the argument could be written almost exactly as it has been requiring only that ``was $U$ and not $D$'' be changed to ``will be $U$ and not $D$.'' Thus a self-enforcing assessment of the game must not only be consistent with deductions based on the opponents' rational behavior in the future (backward induction) but it must also be consistent with deductions based on the opponents' rational behavior in the past (forward induction). A formal definition of forward induction has proved a little elusive. One aspect of the idea of forward induction is captured by the idea that a solution should not be sensitive to the deletion of a dominated strategy, as we discussed in Section~\ref{sec:adit}. Other aspects depend explicitly on the idea of a solution as a set of equilibria. Kohlberg and Mertens~(1986) give such a definition; and Cho and Kreps~(1987) give a number of definitions in the context of signaling games, as do Banks and Sobel~(1987). We shall leave this question for the moment and return to it in Sections \ref{sec:fortwo}, \ref{sec:stfi}, and~\ref{sec:fibi}. \section{Ordinality and Other Invariances} \label{sec:ordand} In the following section we shall look again at identifying the self-enforcing solutions. In this section we examine in detail part of what will be involved in providing an answer, namely, the appropriate domain for the solution correspondence. That is, if we are asking simply what behavior (or assessment of the others' behavior) is self-enforcing, which aspects of the game are relevant and which are not? We divide the discussion into two parts, the first takes the set of players (and indeed their names) as given, while the second is concerned with changes to the player set. The material in this section and the next is a restatement of some of the discussion in and of some of the results from Kohlberg and Mertens (1982, 1986) and Mertens (1987, 1989, 1991a, 1991b, 1991c, 1992). Recall that we are asking only a rather narrow question: what solutions are self-enforcing. Or, equivalently, what outcomes are consistent with the individual incentives of the players (and the interaction of those incentives)? Thus if some change in the game does not change the individual incentives then it should not change the set of solutions that are self-enforcing. The following two subsections give some formal content to this informal intuition. Before that, it is well to emphasize that we make no claim that a solution in any other sense, or the strategies that will actually be played, should satisfy the same invariances. This is a point that has been made in a number of places in the papers mentioned above,% \footnote{Perhaps most starkly in Mertens (1987, p. 6) where he states ``There is here thus no argument whatsoever according to which the choice of equilibrium should depend only on this or that aspect of the game.''} but is worth repeating. It is also worth reminding the reader at this point that we are taking the ``traditional'' point of view, that all uncertainty about the actual game being played has been explicitly included in the description of the game. Other analyses take different approaches. Harsanyi and Selten~(1988) assume that with any game there are associated error probabilities for every move, and focus on the case in which all errors have the same small probability. Implicit, at least, in their analysis is a claim that one cannot think coherently, or at least cannot analyze, a game in which there is no possibility of mistakes. Others are more explicit. Aumann~(1987b) argues that \begin{quote} to arrive at a strong form of rationality (one must assume that) irrationality cannot be ruled out, that the players ascribe irrationality to each other with small probability. True rationality requires `noise'; it cannot grow on sterile ground, it cannot feed on itself only. \end{quote} We differ. Moreover, if we are correct and it is possible to analyze sensibly games in which there are no possibilities of mistakes, then such an analysis is, in theory, more general. One can apply the analysis to a game in which all probabilities of error (or irrationality) are explicitly given. \subsection{Ordinality} \label{sec:ord} Let us now consider a candidate solution of a game. This candidate solution would not be self-enforcing if some player, when he came to make his choices, would choose not to play as the solution recommends. That is, if given his beliefs about the choices of the others, the choice recommended for him was not rational. For fixed beliefs about the choices of the others this is essentially a single agent decision problem, and the concept of what is rational is relatively straight forward. There remains the question of whether all payoff maximizing choices, or just admissible ones, are rational, but for the moment we don't need to take a position on that issue. Now consider two games in which, for some player, for any beliefs on the choices of the others the set of that player's rational choices is the same. Clearly if he had the same beliefs in both games then those recommendations that would be self-enforcing (rational) for him in one game would also be self-enforcing in the other. Now suppose that this is true for all the players. If the beliefs of the players are consistent with the individual incentives in one of the games they will also be in the other, since given those beliefs the individual decision problems have, by assumption, the same solutions in the two games. Thus a combination of choices and beliefs about the others' choices will be self-enforcing in one game if and only if it is self-enforcing in the other. Moreover, the same argument means that if we were to relabel the strategies the conclusion would continue to hold. A solution would be self-enforcing in the one game if and only if its image under the relabeling was self-enforcing in the other. Let us flesh this out and make it a little more formal. Previously we have been mainly thinking of the mixed strategy of a player as the beliefs of the other players about the pure action that the player will take. On the other hand there it is difficult to think how we might prevent a player from randomizing if he wanted to. (It is not even completely clear to us what this might mean.) Thus the choices available to a player include, not only the pure strategies that we explicitly give him, but also all randomizations that he might decide to use, that is, his mixed strategy space. A player's beliefs about the choices of the others will now be represented by a probability distribution over the product of the (mixed) strategy spaces of the other players. Since we are not using any of the structure of the mixed strategy spaces, we consider only probability distributions with finite support. Let us consider an example to make things a little more concrete. Consider the games of Figure~\figref{staghunt2}a and Figure~\figref{staghunt2}b. The game of Figure~\figref{staghunt2}a is the Stag Hunt game of Figure~\figref{staghunt} that we discussed in Section~\ref{sec:itdom}. The game of Figure~\figref{staghunt2}b is obtained from the game of Figure~\figref{staghunt2}a by subtracting 7 from Player~1's payoff when Player~2 plays $L$ and subtracting 7 from Player~2's payoff when Player~1 plays $T$. This clearly does not, for any assessment of what the other player will do, change the rational responses of either player. Thus the games are ordinally equivalent, and the self-enforcing behaviours should be the same. \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{ccc} \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 9,9 & 0,7 \\ \cline{2-3} B & 7,0 & 8,8 \\ \cline{2-3} \multicolumn{3}{c}{} \\[10pt] \multicolumn{3}{c}{\text{\refstepcounter{figure} Figure \thefigure{}a \label{fig:staghunt2}}} \end{array} & \makebox[2cm]{\ } \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 2,2 & 0,0 \\ \cline{2-3} B & 0,0 & 8,8 \\ \cline{2-3} \multicolumn{3}{c}{} \\[10pt] \multicolumn{3}{c}{\text{Figure \figref{staghunt2}b}} \end{array}\\ \end{array} $$ } \end{figure} There remains the question of whether we should restrict the players' beliefs to be independent across the other players. We argued in Section~\ref{sec:pre-eq} that in defining rationalizability the assumption of independence was not justified. That argument is perhaps not compelling in the analysis of equilibrium. And, whatever the arguments, the assumption of independence seems essential to the spirit of Nash equilibrium. In any case the analysis can proceed with or without the assumption. For any such probability distribution the set of rational actions of the player is defined. Here there are essentially two choices: the set of that player's choices (that is, mixed strategies) that maximize his expected payoff, given that distribution; or the set of admissible choices that maximize his payoff. And if one assumes independence there is some issue of how exactly to define admissibility. Again, the analysis can go ahead, with some differences, for any of the assumptions. For the rest of this section we focus on the case of independence and admissibility. Further, we assume a relatively strong form of admissibility. To simplify the statement of the requirement, the term belief will always mean an independent belief with finite support. We say a player's choice is an \emph{admissible best reply} to a certain belief $p$ about the choices of the others if, for any other belief $q$ of that player about the others, there are beliefs $\tilde{q}$ arbitrarily close to $p$ and having support containing the support of $q$, such that the player's choice is expected payoff maximizing against~$\tilde{q}$. The statement of this requirement is a little complicated. The idea is that the choice should be optimal against some completely mixed strategies of the other players close to the actual strategy of the others. However, because of the ordinality requirement we do not wish to use the structure of the strategy spaces, so we make no distinction between completely mixed strategies and those that are not completely mixed. Nor do we retain any notion of one mixed strategy being close to another, except information that may be obtained simply from the preferences of the players. Thus the notion of ``close'' in the definition is that the sum over all the mixed strategies in the support of either $p$ or $\tilde{q}$ of the difference between $p$ and $\tilde{q}$ is small. One now requires that if two games are such that a relabeling of the mixed strategy space of one gives the mixed strategy space of the other and that this relabeling transforms the best reply correspondence of the first game into the best reply correspondence of the second then the games are equivalent in terms of the individual incentives and the (self-enforcing) solutions of the one are the same as the (appropriately relabeled) solutions of the other. Mertens~(1987) shows that this rather abstract requirement has a very concrete implementation. Two games exhibit the same self-enforcing behavior if they have the same pure strategy sets and the same best replies for every vector of completely mixed strategies, this remains true for any relabeling of the pure strategies, and also for any addition or deletion of strategies that are equivalent to existing mixed strategies. That is, the question of what behavior is self-enforcing is captured completely by the reduced normal form, and by the best reply structure on that form. And it is only the best reply structure on the interior of the strategy space that is relevant. If one dropped the assumption that beliefs should be independent one would require a little more, that the best replies to any correlated strategy of the others should be the same. And if one thought of the best replies as capturing rationality rather than admissible best replies, one would need equivalence of the best replies on the boundary of the strategy space as well. \subsection{Changes in the Player Set} \label{sec:changes} We turn now to questions of changes in the player set. We start with the most obvious. While, as Mertens~(1991c) points out, the names of the players may well be relevant for what equilibrium is actually played, it is clearly not relevant for the prior question of what behavior is self-enforcing. That is, the self-enforcing outcomes are anonymous. Also it is sometimes the case that splitting a player into two agents does not matter. In particular the set of self-enforcing behaviors does not change if a player is split into two subsets of his agents, provided that in \emph{any} play, whatever the strategies of the players at most one of the subsets of agents moves. This requirement too follows simply from the idea of self-enforcing behavior. Given the player's beliefs about the choices of the others, if his choice is not rational then it must be not rational for at least one of the subsets, and conversely. Moreover the admissibility considerations are the same in the two cases. It is the actions of Nature and the other players that determines which of the agents actually plays. Now, at least in the independent case, the beliefs of the others over the choices of the player that are consistent with the notion of self-enforcing behavior and the beliefs over the choices of the subsets of the agents that are consistent with the notion of self-enforcing behavior may differ. But only in the following way. In the case of the agents it is assumed that the beliefs of the others are the independent product of beliefs over each subset of the agents, while when the subsets of the agents are considered a single player no such assumption is made. And yet, this difference has no impact on what is rational behavior for the others. Which of the agents plays in the game is determined by the actions of the others. And so, what is rational for one of the other players depends on his beliefs about the choices of the rest of the other players and his beliefs about the choices of each agent of the player in question conditional on that agent actually playing in the game. And the restrictions on these conditional beliefs will be the same in the two cases. Notice that this argument breaks down if both subsets of the agents might move in some play. In that case dependence in the beliefs may indeed have an impact. Further, the argument that the decision of the player is decomposable into the individual decisions of his agents in not correct. We now come to the final two changes, which concern situations in which subsets of the players can be treated separately. The first, called the decomposition property, says that if the players of a game can be divided into two subsets and that the players in each subset play distinct games with no interaction with the players in the other subset---that is, the payoffs of the one subset do not depend on the actions of the players in the other subset---then the self-enforcing behaviors in the game are simply the products of the self-enforcing behaviors in smaller games. Mertens~(1989) puts this more succinctly as ``if disjoint player sets play different games in different rooms, one can as well consider the compound game as the separate games.''~(p. 577) Finally, we have the small worlds axiom, introduced in Mertens~(1991a) and proved for stable sets in Mertens~(1992). This says that if the payoffs of some subset of the players do not depend on the choices of the players outside this subset, then the self-enforcing behavior of the players in the subset is the same whether one considers the whole game or only the game between the ``insiders.'' These various invariance requirements can be thought of as either restrictions on the permissible solutions or as a definition of what constitutes a solution. That is, they define the domain of the solution correspondence. Also, the requirements become stronger in the presence of the other requirements. For example, the player splitting requirement means that the restriction to nonoverlapping player sets in the decomposition requirement can be dispensed with. (For details see Mertens (1989, p.~578).) And, ordinality means that in the decomposition and small worlds requirements we can replace the condition that the payoffs of the subset of players not change with the condition that their best replies not change, or even that their admissible best replies not change. \section{Strategic Stability} \label{sec:stable} We come now to the concept of strategic stability introduced by Kohlberg and Mertens~(1986) and reformulated by Mertens (1987, 1989, 1991a, 1991b, 1992) and Govindan and Mertens~(1993). This work is essentially aimed at answering the same question as the concepts of Nash equilibrium and perfect equilibrium, namely, what is self-enforcing behavior in a game. We argued in the previous section that the answer to such a question should depend only on a limited part of the information about the game. Namely, that the answer should be ordinal, and satisfy other invariances. To this extent, as long as one does not require admissibility, Nash equilibrium is a good answer. Nash equilibria are, in some sense, self-enforcing. However, as was pointed out by Selten (1965, 1975), this answer entails only a very weak form of rationality. Certainly, players choose payoff maximizing strategies. But these strategies may prescribe choices of strategies that are (weakly) dominated and actions at unreached information sets that seem clearly irrational. Normal form perfect equilibria are also invariant in all the senses we require, and moreover are also clearly admissible, even in the rather strong sense we require. However, they do not always satisfy the backward induction properties we discussed in Section~9. Other solutions that satisfy the backward induction property do not satisfy the invariance properties. Sequential equilibrium is not invariant. Even changing a choice between three alternatives into two binary choices can change the set of sequential equilibria. Moreover, sequential equilibria may be inadmissible. Extensive form perfect equilibria too are not invariant. Moreover they too may be inadmissible. Recall that in Section~\ref{sec:perfect} we examined a game (that of Figure~17) of Mertens~(1991b) in which \emph{all} of the extensive form perfect equilibria are inadmissible. Quasi-perfect equilibria, defined by van Damme~(1984), and proper equilibria, defined by Myerson~(1978) are both admissible and satisfy backward induction. However, neither is ordinal---quasi-perfect equilibrium depends on the particular extensive form and proper equilibrium may change with the addition of mixtures as new strategies---and proper equilibrium does not satisfy the player splitting requirement. We shall see in the next subsection that it is impossible to satisfy the backward induction property for any ordinal single valued solution concept. This leads us to consider set valued solutions and, in particular, to strategically stable sets of equilibria. \subsection{The Requirements for Strategic Stability} \label{sec:req} We are seeking an answer to the question: What are the self-enforcing behaviors in a game? As we indicated, the answer to this question should satisfy the various invariances we discussed in Section~\ref{sec:ordand}. We also require that the solution satisfy stronger forms of rationality than Nash equilibrium and normal form perfect equilibrium, the two ``non correlated'' equilibrium concepts that do satisfy those invariances. In particular, we want our solution concept to satisfy the admissibility condition we discussed in Section~\ref{sec:adit}, and some form of the iterated dominance condition we also discussed in Section~\ref{sec:adit}, the backward induction condition we discussed in Section~\ref{sec:bi}, and the forward induction condition we discussed in Section~\ref{sec:for}. We also want our solution to give some answer for all games. As we indicated above, it is impossible for a single valued solution concept to satisfy these conditions. In fact, two separate subsets of the conditions are inconsistent for such solutions. Admissibility and iterated dominance are inconsistent, as are backward induction and invariance. \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 3,2 & 2,2 \\ \cline{2-3} M & 1,1 & 0,0 \\ \cline{2-3} B & 0,0 & 1,1 \\ \cline{2-3} \end{array} $$ } \fignumber{adid} \end{figure} To see the inconsistency of admissibility and iterated dominance consider the game in Figure~\figref{adid} (taken from Kohlberg and Mertens (1986, p. 1015)). Strategy $B$ is dominated (in fact, strictly dominated) so by the iterated dominance condition the solution should not change if $B$ is deleted. But in the resulting game admissibility implies that $(T,L)$ is the unique solution. Similarly, $M$ is dominated so we can delete $M$ and then $(T,R)$ is the unique solution. To see the inconsistency of ordinality and backward induction consider the game of Figure~\figref{orbi} (taken from Kohlberg and Mertens (1986, p. 1018)). Nature moves at the node denoted by the circle going left with probability $\alpha$ and up with probability $1-\alpha$. Whatever the value of $\alpha$ the game has the reduced normal form of Figure~\figref{orbi}a. (Notice that strategy $Y$ is just a mixture of $T$ and $M$.) Since the reduced normal form does not depend on $\alpha$, ordinality implies that the solution of this game should not depend on $\alpha$. And yet, in the extensive game the unique sequential equilibrium has Player~2 playing $L$ with probability $(4-3\alpha)/(8-4\alpha)$.) \begin{figure}[htbp] \begin{center} \begin{picture}(300,230)(-150,-60) %Fig orbi \put(-50,-50){\line(1,1){190}} \put(-50,-50){\line(-1,1){40}} \put(0,0){\line(0,1){100}} \put(0,0){\line(-2,1){98}} \put(-102,52){\line(-1,1){48}} \put(-100,52){\line(0,1){48}} \put(100,100){\line(-1,1){40}} \put(0,100){\line(1,1){40}} \put(0,100){\line(-1,1){40}} \put(-100,100){\line(1,1){40}} \put(-100,100){\line(-1,1){40}} \put(0,0){\circle*{4}} \put(-50,-50){\circle*{4}} \put(100,100){\circle*{4}} \put(0,100){\circle*{4}} \put(-100,100){\circle*{4}} \put(-100,50){\circle{4}} \multiput(-100,100)(5,0){41}{\circle*{2}} \put(4,-2){\makebox(0,0)[tl]{1}} \put(-46,-52){\makebox(0,0)[t]{1}} \put(30,97){\makebox(0,0)[t]{2}} \put(-72,-30){\makebox(0,0)[tr]{$T$}} \put(52,50){\makebox(0,0)[tl]{$B$}} \put(2,50){\makebox(0,0)[l]{$M$}} \put(-48,27){\makebox(0,0)[bl]{$Y$}} \put(-98,75){\makebox(0,0)[l]{$1-\alpha$}} \put(-127,73){\makebox(0,0)[tr]{$\alpha$}} \put(78,120){\makebox(0,0)[tr]{$L$}} \put(122,120){\makebox(0,0)[tl]{$R$}} \put(-22,120){\makebox(0,0)[tr]{$L$}} \put(22,120){\makebox(0,0)[tl]{$R$}} \put(-122,120){\makebox(0,0)[tr]{$L$}} \put(-78,120){\makebox(0,0)[tl]{$R$}} \put(-90,-7){\makebox(0,0)[b]{$1,-1$}} \put(-150,103){\makebox(0,0)[b]{$1,-1$}} \put(140,143){\makebox(0,0)[b]{$2,-2$}} \put(60,143){\makebox(0,0)[bl]{$-2,2$}} \put(40,143){\makebox(0,0)[br]{$-2,2$}} \put(-40,143){\makebox(0,0)[b]{$2,-2$}} \put(-60,143){\makebox(0,0)[br]{$-2,2$}} \put(-140,143){\makebox(0,0)[b]{$2,-2$}} \end{picture} \end{center} \fignumber{orbi} \bigskip %\end{figure} %\begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 1,-1 & 1,-1 \\ \cline{2-3} M & 2,-2 & -2,2 \\ \cline{2-3} B & -2,2 & 2,-2 \\ \cline{2-3} \end{array} $$ } \bigskip \begin{center} Figure~\figref{orbi}a \end{center} \end{figure} Thus it may be that elements of a solution satisfying the requirements we have discussed would be sets. However we would not want these sets to be too large. We are still thinking of each element of the solution as, in some sense, a single pattern of behavior. In generic extensive form games we might think of a single pattern of behavior as being associated with a single equilibrium outcome, while not specifying exactly the out of equilibrium behavior. One way to accomplish this is to consider only connected sets of equilibria. In the definition of Mertens discussed below the connectedness requirement is strengthened in a way that corresponds, informally, to the idea that the particular equilibrium should depend continuously on the ``beliefs'' of the players. Without a better understanding of exactly what it means for a set of equilibria to be the solution we cannot say much more. However some form of connectedness seems to be required. In Section~\ref{sec:defin} we shall discuss a number of definitions of strategic stability that have appeared in the literature. All of these definitions are motivated by the attempt to find a solution satisfying the requirements we have discussed. As we have just seen such a solution must of necessity be set valued, and we have claimed that such sets should be connected. For the moment, without discussing the details of the definition we shall use the term strategically stable sets of equilibria (or simply stable sets) to mean one of the members of such a solution. \subsection{Comments on Sets of Equilibria as Solutions to Non-Cooperative Games} \label{sec:sets} We saw in the previous subsection that single valued solutions could not satisfy the requirements that were implied by a relatively strong form of the notion of self-enforcing. There are two potential responses to this observation. One is to abandon the strong conditions and view the concept of Nash equilibrium or normal form perfect equilibrium as the appropriate concept. The other is to abandon the notion that solutions to noncooperative games should be single valued. It may seem that the first is more natural, that perhaps the results of Section~\ref{sec:req} tell us that there is some inconsistency between the invariances we have argued for and the backward induction requirements as we have defined them. We take the opposite view. Our view is that these results tell us that there is something unwarranted in insisting on single valued solutions. Our own understanding of the issue is very incomplete and sketchy and this is reflected in the argument. Nevertheless the issue should be addressed and we feel it is worthwhile to state here what we \emph{do} know, however incomplete. Consider again the game of Figure~\figref{counter}. In this game the unique stable set contains all the strategy profiles in which Player~1 chooses $T$. The unique subgame perfect equilibrium has Player~2 choosing $R$. Recall our interpretation of mixed strategies as the assessment of others of how a player will play. In order to know his best choices Player~1 does not need to know anything about what Player~2 will choose, so there is no need to make Player~1's assessment precise. Moreover from Player~2's perspective one could argue for either $L$ or $R$ equally well on the basis of the best reply structure of the game. They do equally well against $T$ while $L$ is better against $BU$ and $R$ is better against $BD$. Neither $BU$ nor $BD$ are ever best replies for Player~1, so we cannot distinguish between them on the basis of the best reply correspondence. What then of the backward induction argument? We have said earlier that backward induction relies on an assumption that a player is rational whatever he has done at previous information sets. This is perhaps a bit inaccurate. The conclusion here is that Player~1, being rational, will not choose to play $B$. The ``assumption'' that Player~2 at his decision node will treat Player~1 as rational is simply a test of the assumption that Player~1 will not play $B$. Once this conclusion is confirmed one cannot continue to maintain the assumption that following a choice of $B$ by Player~1, Player~2 will continue to assume that Player~1 is rational. Indeed he cannot. In this example Player~1's choices in the equilibrium tells us nothing about his assessment of Player~2's choices. If there is not something else---such as admissibility considerations, for example---to tie down his assessment then there is no basis to do so. Consider the slight modification of this game of Figure~\figref{sets}. In this game it is not so immediately obvious that Player~1 will not choose $B$. However if we assume that Player~1 does choose $B$, believes that Player~2 is rational, and that Player~2 still believes that Player~1 is rational we quickly reach a contradiction. Thus it must not be that Player~1, being rational and believing in the rationality of the other, chooses $B$. Again we can no longer maintain the assumption that Player~1 will be regarded as rational in the event that Player~2's information set is reached. Again both $L$ and $R$ are admissible for Player~2. In this case there is a difference between $BU$ and $BD$ for Player~1---$BD$ is admissible while $BU$ is not. However, having argued that a rational Player~1 will choose $T$ there is no compelling reason to make any particular assumption concerning Player~2's assessment of the relative likelihoods of $BU$ and $BD$. The remaining information we have to tie down Player~1's assessment of Player~2's choices is Player~1's equilibrium choice. Since Player~1 chooses $T$, it must be that his assessment of Player~2's choices made this a best response. And this is true for any assessment that puts weight no greater than a half on $L$. Again this set of strategies is precisely the unique strategically stable set. \begin{figure}[htbp] \begin{center} \begin{picture}(200,180)(-50,-10) %Fig sets \put(0,0){\line(1,1){140}} \put(0,0){\line(-1,1){40}} \put(50,50){\line(-1,1){40}} \put(100,100){\line(-1,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(100,100){\circle*{4}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{2}} \put(104,98){\makebox(0,0)[tl]{1}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{$B$}} \put(28,70){\makebox(0,0)[tr]{$L$}} \put(72,70){\makebox(0,0)[tl]{$R$}} \put(78,120){\makebox(0,0)[tr]{$U$}} \put(122,120){\makebox(0,0)[tl]{$D$}} \put(-40,43){\makebox(0,0)[b]{$3,3$}} \put(10,93){\makebox(0,0)[b]{$4,1$}} \put(60,143){\makebox(0,0)[b]{$0,0$}} \put(140,143){\makebox(0,0)[b]{$2,2$}} \end{picture} \end{center} \fignumber{sets} \end{figure} \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{r|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 3,3 & 3,3 \\ \cline{2-3} BU & 4,1 & 0,0 \\ \cline{2-3} BD & 4,1 & 2,2 \\ \cline{2-3} \end{array} $$ } \bigskip \begin{center} Figure~\figref{sets}a \end{center} \end{figure} These examples point to the fact that there may be something unwarranted in specifying single strategy vectors as ``equilibria.'' We have emphasized the interpretation of mixed strategy vectors as representing the uncertainty in one player's mind about what another player will do. In many games there is no need for a player to form a very precise assessment of what another player will do. Put another way, given the restrictions our ordinality arguments put on the ``questions we can ask a player'' we cannot elicit his subjective probability on what the others will do. Rather we must be satisfied with less precise information. As we said, this is at best suggestive. In fact, if there are more than two players there are real problems. In either of the examples discussed we could add a player with a choice between two strategies, his optimal choice varying in the stable set and not affecting the payoffs of the others. Here too we see a sense in which the set valued solution does represent the strategic uncertainty in the interaction among the players. However we do not see any way in which to make this formal, particularly since the notion of a ``strategic dummy'' is so elusive. For example, we could again amend the game by adding another game in which the third player interacts in an essential way with the other two and, say, having nature choose which of the two games will be played. \subsection{Forward Induction} \label{sec:fortwo} We discussed in general terms in Section~\ref{sec:for} the idea of forward induction; and discussed one aspect of this idea in Section~\ref{sec:adit}. We are now in a position to be a little more explicit about another aspect of the idea. The idea that the solution should not be sensitive to the (iterated) deletion of dominated strategies was that since it was known that players are never willing to choose such strategies it should not make a difference if such strategies were removed from the game. This suggests another aspect of forward induction. If, in the solution in question, there is some strategy of a player that the player would never be willing to choose then it should not make a difference if such a strategy were removed from the game. In fact, like the deletion of a dominated strategy, it is clear that the deletion of a strategy that a player is never willing to play in the solution must change the situation. (It can, for example change undominated strategies into dominated ones, and vice versa.) So our intuition is that it should not matter much. This is reflected in the fact that various versions of this requirement have been stated by requiring, for example, that a stable set \emph{contain} a stable set of the game obtained by deleting such a strategy, or by looking at equilibrium outcomes in generic extensive form games, without being explicit about what out of equilibrium behavior is associated with the solution. There is one aspect of this requirement that has aroused some comment in the literature. It is that in deleting dominated strategies we delete weakly dominated strategies. In deleting strategies that are inferior in the solution we delete only strategies that are strictly dominated at all points of the solution. In the way we have motivated the definition this difference appears quite naturally. The weakly dominated strategy is deleted because the player would not in any case be willing to choose it. In order to be sure that the player would not anywhere in the solution be willing to choose the strategy it is necessary that the strategy be strictly dominated at all points of the solution. Another way of saying almost the same thing is that the idea that players should not play dominated strategies might be thought of as motivated by a requirement that the solution should not depend on the player being absolutely certain that the others play according to the solution. Again, the same requirement implies that only strategies that are dominated in some neighbourhood of the solution be deleted. \subsection{The Definition of Strategic Stability} \label{sec:defin} There have been a number of definitions of strategic stability proposed, the first and most widely known that of Kohlberg and Mertens~(1986). They consider Selten-type perturbations to the normal form of a game and call a closed set of equilibria strategically stable if it is minimal with respect to the property that all small perturbations have equilibria close to the set. They explicitly viewed this definition as a first pass and were well aware of its shortcomings. In particular the sets so defined might fail to satisfy quite weak versions of backward induction. They give an example, due to Faruk Gul, of a game with such a stable set that does not yield the same outcome as the unique subgame perfect equilibrium. Moreover such sets are often not connected. A minor modification of this definition somewhat expanding the notion of a perturbation remedies part of these deficiencies. Such a definition essentially expands the definition of a perturbation enough so that backward induction is satisfied while not so much as to violate admissibility, as the definition of fully stable sets by Kohlberg and Mertens does. This modification was known to Kohlberg and Mertens and was suggested in unpublished work of Phil Reny. It was independently discovered and called, following a suggestion of Mertens, fully stable sets of equilibria in Hillas~(1990). While remedying some of the deficiencies of the original definition of Kohlberg and Mertens this definition does not satisfy at least one of the requirements given above. The definition defines different sets depending on whether two agents who never both move in a single play of a game are considered as one player or two. Hillas~(1990) also gave a different modification to the definition of strategic stability in terms of perturbations to the best reply correspondence. That definition satisfied the requirements originally proposed by Kohlberg and Mertens, though there is some problem with invariance and an error in the proof of the forward induction properties. This is discussed in Vermeulen, Potters, and Jansen~(1994) and \citeasnoun{HJPV-corrections}. Related definitions are given in Vermeulen, Potters, and Jansen~(1994) and \citeasnoun{HJPV-definitions}. In a series of papers Mertens (1987, 1989, 1991a, and 1992) gave and developed another definition---or, more accurately, a family of definitions---of strategic stability that satisfies all of the requirements we discussed above. The definitions we referred to in the previous paragraph are, in our opinion, best considered as rough approximations to the definitions of Mertens. Stable sets are defined by Mertens in the following way. One again takes as the space of perturbations the Selten-type perturbations to the normal form. The stable sets are the limits at zero of some connected part of the graph of the equilibrium correspondence above the interior of a small neighbourhood of zero in the space of perturbations. Apart from the minimality in the definition of Kohlberg and Mertens and the assumption that the part of the graph was connected in the definition of Mertens, the definition of Kohlberg and Mertens could be stated in exactly this way. One would simply require that the projection map from the part of the equilibrium correspondence to the space of perturbations be onto. Mertens strengthens this requirement in a very natural way, requiring that the projection map not only be onto, be also be nontrivial in a stronger sense. The simplest form of this requirement is that the projection map not be homotopic to a map that is not onto, under a homotopy that left the projection map above the boundary unchanged. However such a definition would not satisfy the ordinality we discussed in Section~\ref{sec:ord}. Thus Mertens gives a number of variants of the definition all involving coarser notions of maps being equivalent. That is, more maps are trivial (equivalent to a map that isn't onto) and so fewer sets are stable. These definitions require that the projection map be nontrivial either in homology or in cohomology, with varying coefficient modules. Mertens shows that, with some restrictions on the coefficient modules, such definitions are ordinal. One also sees in this formulation the similarities of the two aspects of forward induction we discussed in the previous section. In Mertens' work they appear as special cases of one property of stable sets. A stable set contains a stable set of the game obtained by deleting a strategy that is nowhere in the relevant part of the graph of the equilibrium correspondence played with more than the minimum required probability. Govindan and Mertens~(1993) give a definition of stability directly in terms of the best reply correspondence. One can think of the set of equilibria as the intersection of the graph of the best reply correspondence with the diagonal. To define stable sets one looks at the graph of the best reply correspondence in a neighbourhood of the diagonal. It is required that a map that takes points consisting of a strategy and a best reply to that strategy to the strategy space in the following way be essential. The points on the diagonal are projected straight onto the strategy space. Other points are taken to the best reply and then shifted by some constant times the difference between the original strategy vector and the best reply. As long as this constant is large enough the boundary of the neighbourhood will be taken outside the strategy space (at which point the function simply continues to take the boundary value). The form of the essentiality requirement in this paper is that the map be essential in \u{C}ech cohomology. Loosely, the requirement says that the intersection of the best reply correspondence with the diagonal should be essential. Govindan and Mertens show that this definition gives the same stable sets as the original definition of Mertens in terms of the graph of the equilibrium correspondence with the same form of essentiality. \subsection{Strengthening Forward Induction} \label{sec:stfi} In this section we discuss an apparently plausible strengthening of the forward induction requirement that we discussed in Section~\ref{sec:for} that is not satisfied by the definitions of stability we have given. Van Damme~(1989) suggests that the previous definitions of forward induction do not capture all that the intuition suggests. Van Damme does not, in the published version of the paper, give a formal definition of forward induction but rather gives \begin{quote} a (weak) property which in my opinion should be satisfied by any concept that is consistent with forward induction.\dots The proposed requirement is that in generic 2-person games in which player $i$ chooses between an outside option or to play a game $\Gamma$ of which a unique (viable) equilibrium $e^*$ yields this player more than the outside option, only the outcome in which $i$ chooses $\Gamma$ and $e^*$ is played in $\Gamma$ is plausible. \end{quote} He gives the example in Figure~\figref{vd3} to show that strategic stability does not satisfy this requirement. In this game there are three components of normal form perfect equilibria, $(BU,L)$, $\{(T,(q,1-q,0)\mid \frac{1}{3} \leq q \leq \frac{2}{3} \}$, and $\{(T,(0,q,1-q)\mid \frac{1}{3} \leq q \leq \frac{2}{3} \}$. (Player 2's mixed strategy gives the probabilities of $L$, $C$, and $R$, in that order.) All of these components are stable (or contain stable sets) in any of the senses we have discussed. Since $(U,L)$ is the unique equilibrium of the subgame that gives Player~1 more than his outside option the components in which Player~1 plays $T$ clearly do not satisfy van Damme's requirement. \begin{figure}[htbp] \begin{center} \begin{picture}(200,180)(-50,-10) %Fig vd3 \put(0,0){\line(1,1){140}} \put(0,0){\line(-1,1){40}} \put(50,50){\line(-1,1){90}} \put(100,100){\line(-1,1){40}} \put(0,100){\line(1,1){40}} \put(0,100){\line(0,1){40}} \put(100,100){\line(0,1){40}} \put(0,0){\circle*{4}} \put(50,50){\circle*{4}} \put(100,100){\circle*{4}} \put(0,100){\circle*{4}} \multiput(0,100)(5,0){21}{\circle*{2}} \put(4,-2){\makebox(0,0)[t]{1}} \put(54,48){\makebox(0,0)[tl]{1}} \put(50,97){\makebox(0,0)[t]{2}} \put(-22,20){\makebox(0,0)[tr]{$T$}} \put(22,20){\makebox(0,0)[tl]{$B$}} \put(28,70){\makebox(0,0)[tr]{$U$}} \put(72,70){\makebox(0,0)[tl]{$D$}} \put(78,120){\makebox(0,0)[tr]{$L$}} \put(98,120){\makebox(0,0)[br]{$C$}} \put(122,120){\makebox(0,0)[tl]{$R$}} \put(-22,120){\makebox(0,0)[tr]{$L$}} \put(-2,120){\makebox(0,0)[br]{$C$}} \put(22,120){\makebox(0,0)[tl]{$R$}} \put(-40,43){\makebox(0,0)[b]{$2,2$}} \put(140,143){\makebox(0,0)[b]{$0,3$}} \put(100,143){\makebox(0,0)[b]{$3,2$}} \put(60,143){\makebox(0,0)[bl]{$0,0$}} \put(40,143){\makebox(0,0)[br]{$3,0$}} \put(0,143){\makebox(0,0)[b]{$0,2$}} \put(-40,143){\makebox(0,0)[b]{$3,3$}} \end{picture} \end{center} \fignumber{vd3} \end{figure} \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{C} & \multicolumn{1}{c}{R} \\ \cline{2-4} T & 2,2 & 2,2 & 2,2 \\ \cline{2-4} BU & 3,3 & 0,2 & 3,0 \\ \cline{2-4} BD & 0,0 & 3,2 & 0,3 \\ \cline{2-4} \end{array} $$ } \bigskip \begin{center} Figure~\figref{vd3}a \end{center} \end{figure} It isn't clear if van Damme intends to address the question we ask, namely, what outcomes are self-enforcing. (Recall that he doesn't claim that outcomes not satisfying his condition are not self-enforcing, but rather that they are not plausible.) Nevertheless let us address that question. There does not seem, to us, to be a good argument that the outcome in which Player~1 plays $T$ is not self-enforcing. There are two separate ``patterns of behavior'' by Player~2 that lead Player~1 to play $T$. To make matters concrete consider the patterns in which Player~2 plays $L$ and $C$. Let us examine the hypothesis that Player~1 plays $T$ because he is uncertain whether Player~2 will play $L$ or $C$. If he is uncertain (in the right way) this is indeed the best he can do. Further at the boundary of the behavior of Player~2 that makes $T$ the best for Player~1 there is an assessment of Player~2's choices that make $BU$ best for Player~1 and another assessment of Player~2's choices that make $BD$ best for Player~1. If Player~2 can be uncertain as to whether Player~1 has deviated to $BU$ or to $BD$ then indeed both strategies $L$ and $C$ can be rationalized for Player~2, as can mixtures between them. To be very concrete, let us focus on the equilibrium $(T,(\frac{1}{3},\frac{2}{3},0)$. In this equilibrium Player~1 is indifferent between $T$ and $BD$ and prefers both to $BU$. It seems quite consistent with the notion of self-enforcing that Player~2, seeing a deviation by Player~1, should not be convinced that Player~1 had played $BU$. In a sense we have done nothing more than state that the stable sets in which Player~1 plays $T$ satisfy the original statement of forward induction given by Kohlberg and Mertens~(1986). The argument does however suggest to us that there is something missing in a claim that the stronger requirement of van Damme is a necessary implication of the idea of self-enforcing. To be much more explicit would require a better developed notion of what it means to have set-valued solutions, as we discussed in Section~\ref{sec:sets}. Before leaving this example, we shall address one additional point. Ritz\-berger (1994) defines a vector field, which he calls the Nash field, on the strategy space. This definition loosely amounts to moving in (one of) the direction(s) of increasing payoff. Using this structure he defines an index for isolated zeros of the field (that is, equilibria). He extends this to components of equilibria by taking the sum of indices of regular perturbations of the Nash field in a small neighbourhood of the component. He points out that in this game the equilibrium $(BU,L)$ has index $+1$, and so since the sum of the indices is $+1$ the index of the set associated with Player~1 playing $T$ must have index zero. However, as we have seen there are two separate stable sets in which Player~1 plays $T$. Now these two sets are connected by a further set of (nonperfect) equilibria. The methods used by Ritzberger seem to require us to define and index for this component in its entirety. As we said above both of the connected subsets of normal form perfect equilibria are stable in the sense of Mertens' reformulation. And it would seem that there might be some way to define an index so that these sets, considered separately, would have nonzero index, $+1$ and $-1$. Ritzberger comments that ``the reformulation of Stable Sets (Mertens, 1989) eliminates the component with zero index'' and speculates that ``as a referee suggested, it seems likely that sets which are stable in the sense of Mertens will all be contained in components whose indices are non-zero.'' However his claim that neither of the sets are stable is in error and his conjecture is incorrect. It seems to us that the methods used by Ritzberger force us to treat two patterns of behavior, that are separately quite well behaved, together and that this leads, in some imprecise sense, to there indices canceling out. There seems something unwarranted in rejecting an outcome on this basis. \subsection{Forward Induction and Backward Induction} \label{sec:fibi} The ideas behind forward induction and backward induction are closely related. As we have seen backward induction involves an assumption that players assume, even if they see something unexpected, that the other players will choose rationally in the future. Forward induction involves an assumption that players assume, even if they see something unexpected, that the other players chose rationally in the past. However, a distinction between a choice made in the past whose outcome the player has not observed, and one to be made in the future goes very much against the spirit of the invariances that we argued for in Section~\ref{sec:ordand}. In fact, in a much more formal sense there appears to be a relationship between backward and forward induction. In many examples---in fact, in all of the examples we have examined---a combination of the invariances we have discussed and backward induction gives the results of forward induction arguments and, in fact, the full strength of stability. Consider again the game of Figure~\figref{KM} that we used to motivate the idea of forward induction. The game given in extensive form in Figure~\figref{KM2} and in normal form in Figure~\figref{KM2}a has the same reduced normal form as the game of Figure~\figref{KM}. In that game the unique equilibrium of the subgame is $(BU,L)$. Thus the unique subgame perfect equilibrium of the game is $(BU,L)$. Recall that this is the same result that we argued for in terms of forward induction in Section~\ref{sec:for}. \begin{figure}[htbp] \begin{center} \begin{picture}(300,230)(-150,-60) %Fig KM2 \put(-50,-50){\line(1,1){190}} \put(-50,-50){\line(-1,1){40}} \put(0,0){\line(0,1){100}} \put(0,0){\line(-2,1){98}} \put(-102,52){\line(-1,1){48}} \put(-100,52){\line(0,1){48}} \put(100,100){\line(-1,1){40}} \put(0,100){\line(1,1){40}} \put(0,100){\line(-1,1){40}} \put(-100,100){\line(1,1){40}} \put(-100,100){\line(-1,1){40}} \put(0,0){\circle*{4}} \put(-50,-50){\circle*{4}} \put(100,100){\circle*{4}} \put(0,100){\circle*{4}} \put(-100,100){\circle*{4}} \put(-100,50){\circle{4}} \multiput(-100,100)(5,0){41}{\circle*{2}} \put(4,-2){\makebox(0,0)[tl]{1}} \put(-46,-52){\makebox(0,0)[t]{1}} \put(30,97){\makebox(0,0)[t]{2}} \put(-72,-30){\makebox(0,0)[tr]{$T$}} \put(52,50){\makebox(0,0)[tl]{$BD$}} \put(2,50){\makebox(0,0)[l]{$BU$}} \put(-48,27){\makebox(0,0)[bl]{$X$}} \put(-98,75){\makebox(0,0)[l]{$\frac{1}{4}$}} \put(-127,73){\makebox(0,0)[tr]{$\frac{3}{4}$}} \put(78,120){\makebox(0,0)[tr]{$L$}} \put(122,120){\makebox(0,0)[tl]{$R$}} \put(-22,120){\makebox(0,0)[tr]{$L$}} \put(22,120){\makebox(0,0)[tl]{$R$}} \put(-122,120){\makebox(0,0)[tr]{$L$}} \put(-78,120){\makebox(0,0)[tl]{$R$}} \put(-90,-7){\makebox(0,0)[b]{$2,5$}} \put(-150,103){\makebox(0,0)[b]{$2,5$}} \put(140,143){\makebox(0,0)[b]{$1,4$}} \put(60,143){\makebox(0,0)[bl]{$0,0$}} \put(40,143){\makebox(0,0)[br]{$0,0$}} \put(-40,143){\makebox(0,0)[b]{$4,1$}} \put(-60,143){\makebox(0,0)[br]{$0,0$}} \put(-140,143){\makebox(0,0)[b]{$4,1$}} \end{picture} \end{center} \fignumber{KM2} \end{figure} \begin{figure}[htbp] {\renewcommand{\arraystretch}{1.5} $$ \begin{array}{c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{L} & \multicolumn{1}{c}{R} \\ \cline{2-3} T & 2,5 & 2,5 \\ \cline{2-3} BU & 4,1 & 0,0 \\ \cline{2-3} BD & 0,0 & 1,4 \\ \cline{2-3} X & \frac{5}{2},4 & \frac{3}{2},\frac{15}{4} \\ \cline{2-3} \end{array} $$ } \bigskip \begin{center} Figure~\figref{KM2}a \end{center} \end{figure} This is perhaps not too surprising. After all this was a game originally presented to illustrate in the most compelling way possible the arguments in favor of forward induction. Thus the issues in this example are quite straightforward. Two rounds of the deletion of weakly dominated strategies gives the same result. What is a little surprising is that the same result occurs in cases in which the arguments for forward induction are less clear cut. A number of examples are examined in Hillas~(1994) with the same result, including the examples presented by Cho and Kreps~(1987) to argue against the strength of some definitions of forward induction and strategic stability. We shall illustrate the point with one further example. We choose the particular example both because it is interesting in its own right and because in the example the identification of the stable sets seems to be driven mostly by the definition of stability and not by an obvious forward induction logic. The example is from Mertens~(1991b). It is a game with perfect information and a unique subgame perfect equilibrium---though the game is not generic. Moreover there are completely normal form arguments that support the unique subgame perfect equilibrium. In spite this the unique strategically stable set of equilibria consists of all the admissible equilibria, a set containing much besides the subgame perfect equilibrium. The extensive form of the game is given here in Figure~\figref{JF} and the normal form in Figure~\figref{JF}a. \begin{figure}[htbp] \renewcommand{\baselinestretch}{1} \small \normalsize \begin{center} \begin{picture}(350,180)(0,-80) \put(0,0){\line(1,0){300}} \put(0,0){\line(1,2){25}} \put(75,0){\line(1,2){25}} \put(75,0){\line(1,-2){25}} \put(150,0){\line(1,2){25}} \put(225,0){\line(1,2){25}} \put(0,0){\circle*{4}} \put(75,0){\circle*{4}} \put(150,0){\circle*{4}} \put(225,0){\circle*{4}} \put(0,-12){$1$} \put(60,-12){$2$} \put(145,-12){$1$} \put(220,-12){$2$} \put(30,50){$0,0$} \put(105,50){$0,0$} \put(105,-50){$1,-1$} \put(180,50){$-2,-1$} \put(255,50){$-3,0$} \put(305,0){$-1,1$} \put(5,25){$T$} \put(20,25){$x_1$} \put(79,25){$L$} \put(93,25){$y_2$} \put(93,-30){$y_1$} \put(150,25){$M$} \put(170,25){$x_2$} \put(180,-12){$B$} \put(180,-22){$x_3$} \put(245,25){$y_4$} \put(255,-12){$R$} \put(255,-22){$y_3$} \end{picture} \end{center} \fignumber{JF} \end{figure} \begin{figure}[htbp] \begin{center} {\renewcommand{\arraystretch}{1.5} \begin{tabular}{cc|c|c|c|c|} \multicolumn{3}{c}{} & \multicolumn{1}{c}{$L$} & \multicolumn{1}{c}{$R$} & \multicolumn{1}{c}{} \\ \multicolumn{2}{c}{} & \multicolumn{1}{c}{$y_1$} & \multicolumn{1}{c}{$y_2$} & \multicolumn{1}{c}{$y_3$} & \multicolumn{1}{c}{$y_4$} \\ \cline{3-6} $T$ & $x_1$ & $0,0$ & $0,0$ & $0,0$ & $0,0$ \\ \cline{3-6} $M$ & $x_2$ & $1,-1$ & $0,0$ & $-2,-1$ & $-2,-1$ \\ \cline{3-6} $B$ & $x_3$ & $1,-1$ & $0,0$ & $-1,1$ & $-3,0$ \\ \cline{3-6} \end{tabular} } \end{center} \bigskip \begin{center} Figure~\figref{JF}a \end{center} \end{figure} The unique subgame perfect equilibrium of this game is $(T,R)$. Thus this is also the unique proper equilibrium---though the uniqueness of the proper equilibrium does involve an identification of duplicate strategies that is not required for the uniqueness of the subgame perfect equilibrium---and so $(T,R)$ is a sequential equilibrium of any extensive form game having this normal form. Nevertheless there are games having the same \emph{reduced} normal form as this game for which $(T,R)$ is not sequential, and moreover the outcome of any sequential equilibrium of the game is not the same as the outcome from $(T,R)$. Suppose that the mixtures $X = 0.9T + 0.1M$ and $Y = 0.86L + 0.1y_1 + 0.04y_4$ are added as new pure strategies. This results in the normal form game of Figure~\figref{JF2}a. The extensive form game of Figure~\figref{JF2} has this normal form. It is straightforward to see that the unique equilibrium of the simultaneous move subgame is $(M,Y)$ in which the payoff to Player~I is strictly positive (0.02) and so in any subgame perfect equilibrium Player~1 chooses to play ``in''---that is, $M$, or $B$, or $X$---at his first move. Moreover in the equilibrium of the subgame the payoff to Player~2 is strictly negative ($-0.14$) and so in any subgame perfect equilibrium Player~2 chooses to play $L$ at his first move. Thus the unique subgame perfect equilibrium of this game is $(M,L)$. \begin{figure}[htbp] \begin{center} \begin{picture}(350,180)(50,-80) \put(0,0){\line(1,0){150}} \put(0,0){\line(1,2){25}} \put(75,0){\line(1,2){25}} \put(0,0){\circle*{4}} \put(75,0){\circle*{4}} \put(0,-12){$2$} \put(60,-12){$1$} \put(30,50){$0,0$} \put(105,50){$0,0$} \put(5,25){$L$} \put(79,25){$T$} \put(150,0){\mbox{ \renewcommand{\arraystretch}{1.5} \begin{tabular}{c|c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{$y_1$} & \multicolumn{1}{c}{$R$} & \multicolumn{1}{c}{$y_4$} & \multicolumn{1}{c}{$Y$} \\ \cline{2-5} $M$ & $1,-1$ & $-2,-1$ & $-2,-1$ & $0.02,-0.14$ \\ \cline{2-5} $B$ & $1,-1$ & $-1,1$ & $-3,0$ & $-0.02,-0.1$ \\ \cline{2-5} $X$ & $0.1,-0.1$ & $-0.2,-0.1$ & $-0.2,-0.1$ & $0.002,-0.014$ \\ \cline{2-5} \end{tabular} } } \end{picture} \end{center} \fignumber{JF2} \end{figure} \begin{figure}[htbp] \begin{center} {\renewcommand{\arraystretch}{1.5} \begin{tabular}{c|c|c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{$y_1$} & \multicolumn{1}{c}{$L$} & \multicolumn{1}{c}{$R$} & \multicolumn{1}{c}{$y_4$} & \multicolumn{1}{c}{$Y$} \\ \cline{2-6} $T$ & $0,0$ & $0,0$ & $0,0$ & $0,0$ & $0,0$ \\ \cline{2-6} $M$ & $1,-1$ & $0,0$ & $-2,-1$ & $-2,-1$ & $0.02,-0.14$ \\ \cline{2-6} $B$ & $1,-1$ & $0,0$ & $-1,1$ & $-3,0$ &$-0.02,-0.1$ \\ \cline{2-6} $X$ & $0.1,-0.1$ & $0,0$ & $-0.2,-0.1$ & $-0.2,-0.1$ & $0.002,-0.014$ \\ \cline{2-6} \end{tabular} } \end{center} \bigskip \begin{center} Figure~\figref{JF2}a \end{center} \end{figure} This equilibrium is far from the unique backward induction equilibrium of the original game. Moreover its outcome is also different. Thus, if one accepts the arguments that the solution(s) of a game should depend only on the reduced normal form of the game and that any solution to a game should contain a ``backward induction'' equilibrium, then one is forced to the conclusion that in this game the solution must contain much besides the subgame perfect equilibrium of the original presentation of the game. \section{An Assessment of the Solutions} \label{sec:solution} We offer here a few remarks on how the various solutions we have examined stand up. As we indicated in Section~\ref{sec:ordand} we do not believe that the kinds of invariance we discussed there should be controversial. (We are aware that for some reason in some circles they are, but have every confidence that as the issues become better understood this will change.) On the other hand we have less attachment to or confidence in our other maintained assumption, that of stochastic independence. We briefly discussed in the introduction our reasons for adopting that assumption in this chapter. Many of the issues we have discussed here in the context of strategic equilibrium have their analogs for correlated equilibrium. However the literature is less well developed---and our own understanding is even more incomplete. The most straightforward, and in some ways weakest, requirement beyond that of equilibrium is admissibility. If one is willing to do without admissibility the unrefined strategic equilibrium seems a perfectly good self-enforcing outcome. Another way of thinking about this is given in the work of Fudenberg, Kreps, and Levine~(1988). If the players are permitted to have an uncertainty about the game that is of the same order as their strategic uncertainty---that is, their uncertainty about the choices of the others given the actual game---then any strategic equilibrium appears self-enforcing in an otherwise strong manner. There are a number of different ways that we could define admissibility. The standard way leads to the standard definition of admissible equilibrium, that is, a strategic equilibrium in undominated strategies. A stronger notion takes account of both the strategy being played and the assumption of stochastic independence. In Section~\ref{sec:ord} we gave a definition of an admissible best reply correspondence such that a fixed point of such a correspondence is a normal form perfect equilibrium. Again Fudenberg, Kreps, and Levine give us another way to think about this. If the players have no uncertainty about their own payoffs but have an uncertainty about the payoffs (or rationality) of the others that is of the same order as their strategic uncertainty then any normal form perfect equilibrium is self-enforcing. Reny's~(1992a) work makes much the same point. To go further and get some version of the backward induction properties that we discussed in Section~\ref{sec:bi} one needs to make stronger informational assumptions. We claimed in Section~\ref{sec:ideabi} that the idea of an equilibrium being robust to a little strategic uncertainty in the sense that the strategic uncertainty should be when possible of a higher order than the uncertainty about the game led us towards backward induction. At best this was suggestive. However as we saw in Section~\ref{sec:fibi} it takes us much further. In combination with the invariances of Section~\ref{sec:ordand} it seems to imply something close to the full strength of strategic stability. As yet we have seen this only in examples, but the examples include those that were constructed precisely to show the unreasonableness of the strength of strategic stability. We regard these examples to be, at worst, very suggestive. Mertens~(1989) described his attitude to the project that led to his work on strategic stability as follows: \begin{quote} I should say from the outset that I started this whole series of investigations with substantial scepticism. I had (and still have) some instinctive liking for the bruto Nash equilibrium, or a modest refinement like admissible equilibria, or normal-form perfect equilibria.~(pp.~582--583) \end{quote} It is not entirely coincidental that we arrive at a similar set of preferred solutions. Our approaches have much in common and our work has been much influenced by Mertens. \section{Other Approaches} \label{sec:other} In this chapter we have examined one approach to thinking about the foundations of strategic equilibrium. There are, of course, other approaches. In this section we examine a small selection of these. We first mention very briefly two approaches and then examine two others in just a little more detail. One approach that is quite different from that adopted here views, either explicitly or implicitly, the common assessment of the way in which the game will be played as resulting from a long series of observations of the way similar games have been played in the past. This kind of work looks at how players will learn from their observations and what the steady states of such learning processes will be. Such work includes Fudenberg and Kreps (1988, 1991a,b) and Fudenberg and Levine (1993a,b). Somewhat more closely related to our approach is the work of Mailath, Samuelson, and Swinkels (1992, 1993, 1994) on the relation between extensive form structures and strategic form structures. This work shows that many of the considerations that are traditionally thought of as questions relating to the extensive form can be addressed quite explicitly in the strategic form. This work is at least consistent with our argument for reduced normal form invariance. In the following two sections we briefly examine one example of an epistemic approach to equilibrium and a very small part of the literature on evolutionary approaches to equilibrium. \subsection{Epistemic Conditions For Equilibrium} \label{sec:epistemic} There have been a number of papers relating the concept of strategic equilibrium to the beliefs or knowledge of the players. One of the most complete and successful is by Aumann and Brandenburger (1995). In the context of a formal theory of \emph{interactive belief systems} they find sets of sufficient conditions on the beliefs of the players for strategic equilibrium. In keeping with the style of the rest of this paper we shall not develop the formal theory but shall rather state the results and sketch some of the proofs in an informal style. Of course, we can do this with any confidence only because we know the formal analysis of Aumann and Brandenburger. There are two classes of results. One concerns the actions or the plans of the players and the other the conjectures of the players concerning the actions or plans of the other players. These correspond to the two interpretations of strategic equilibrium that we discussed in Section~\ref{sec:idea}. The first class consists of a single result. It is quite simple; its intuition is clear; and its proof is, as Aumann and Brandenburger say, immediate. \begin{theorem} \label{theorem:ab1} Suppose that each player is rational and knows his own payoff function and the vector of strategies chosen by the others. Then these strategies form a strategic equilibrium. \end{theorem} The results involving conjectures are somewhat more involved. The reader is warned that while the results we are presenting are precisely Aumann and Brandenburger's we are presenting them with a quite different emphasis. In fact, the central result we present next appears in their paper as a comment well after the central arguments. They give central place to the two results that we give as corollaries (Theorems A and B in their paper). \begin{theorem} \label{theorem:ab2} Suppose that each player knows the game being played, knows that all the players are rational, and knows the conjectures of the other players. Suppose also that \begin{enumerate} \item[a)] the conjectures of any two players about the choices of a third are the same, and \item[b)] the conjecture of any player about the choices of two other players are independent. \end{enumerate} Then the vector of conjectures about each player's choice forms a strategic equilibrium. \end{theorem} The proof is, again, fairly immediate. Suppositions a) and b) give immediately that the conjectures ``are'' a vector of mixed strategies, $\sigma$. Now consider the conjecture of player~$n'$ about player~$n$. Player~$n'$ knows player~$n$'s conjecture, and by a) and b) it is $\sigma$. Also player~$n'$ knows that player~$n$ is rational. Thus his conjecture about player $n$'s choices, that is, $\sigma_n$, should put weight only on those choices of player~$n$ that maximize $n$'s payoff given $n$'s conjecture, that is, given $\sigma$. Thus $\sigma$ is a strategic equilibrium. \hfill \framebox[6pt] \bigskip \begin{corollary} \label{coroll:ab3} Suppose that there are only two players, that each player knows the game being played, knows that both players are rational, and knows the conjecture of the other player. Then the pair of conjectures about each player's choice forms a strategic equilibrium. \end{corollary} The proof is simply to observe that for games with only two players the conditions a) and b) are vacuous. \hfill \framebox[6pt] \begin{corollary} \label{coroll:ab4} Suppose that the players have a common prior that puts positive weight on the event that a particular game $g$ is being played, that each player knows the game and the rationality of the others, and that it is common knowledge among the players that the vector of conjectures takes on a particular value $\varphi$. Then the conjectures of any two players about the choices of a third are the same, and the vector consisting of, for each player~$n$, the conjectures of the others about player~$n$'s choice forms a strategic equilibrium. \end{corollary} We shall not prove this result. It is clear that once it is proved that the conjectures of any two players about the choices of a third are the same and that the conjectures of any player about the choices of two other players are independent the rest of the result follows from Theorem~\ref{theorem:ab2}. The proof that the conjectures of any two players about the choices of a third are the same is essentially an application of Aumann's (1976) ``agreeing to disagree'' result. The proof that the conjectures of any player about the choices of two other players are independent involves further work, for which we refer the reader to Aumann and Brandenburger's paper. \subsection{Evolutionary Approaches} \label{sec:evol} There is, by now, a large literature on the game theoretic approach to evolutionary biology. This is described in detail in the chapter on ``Game Theory and Evolutionary Biology,'' by Hammerstein and Selten (1994) in this Handbook. We shall not replicate that by going into that area at all here. There is however a smaller literature on models that while evolutionary are explicitly not biological. Since these models are perhaps of some relevance to applications in economics and other social sciences we mention some of them here. Jeroen Swinkels in a series of papers has shown that an evolutionary approach may lead to some of the same results as one based on strong assumptions about rationality. Swinkels (1992a, 1992b) considers a definition that while motivated by dynamic considerations is actually static. He modifies the definition of an evolutionarily stable strategy from the biological game theory literature in two ways. First, motivated by the idea of being in an economic environment rather than a biological one he restricts attention to entrant strategies that are best responses to the population that results from their entrance. Secondly, motivated by a desire to avoid, as much as possible, problems of nonexistence and by the idea that evolutionary considerations may not tie down out of equilibrium behavior, he considers sets of strategy profiles rather than single strategy profiles. Swinkels (1992a) shows that, given some regularity conditions, sets defined in this way satisfy many of the properties we have discussed above. They contain a proper equilibrium and satisfy the forward induction property defined in Kohlberg and Mertens (1986). Swinkels (1992b) shows that, again given regularity conditions, a set that is stable against invasion by this kind of entrant must be stable against the kind of perturbations used by Kohlberg and Mertens to define hyperstability---and hence also those used to define full stability and stability---and those used to define stability in Hillas (1990). Swinkels (1993) shows that for some classes of dynamics, and given some regularity conditions, any set that is asymptotically stable is stable against the perturbations used by Kohlberg and Mertens to define hyperstability. N\"{o}ldeke and Samuelson show that it is possible to use evolutionary models to imply even more. Theirs is a model of both learning and mutation. They find that the limiting distributions of the processes they study satisfy a version---in some senses even a stronger version---of the forward induction requirement, suggested by van Damme, that we discussed in Section~\ref{sec:fibi}. \nocite{*} \newpage \bibliographystyle{hillas} \bibliography{steq} \end{document}