%Paper: ewp-game/9309001 %From: zame@platon.econ.vt.edu (William Zame) %Date: Thu, 30 Sep 93 15:45:32 EDT \documentstyle[11pt]{article} \newenvironment{definition}{{\bigskip}\noindent{\bf Definition }}{{}\bigskip} \newtheorem{theorem}{Theorem} \newenvironment{proof}{\noindent {\em Proof:\/}}{{$\Box$\bigskip}} \parskip=.1in \newcommand{\Rn}{{\bf R}^n} \newcommand{\Rm}{{\bf R}^m} \newcommand{\Rmn}{{\bf R}^{m+n}} \newcommand{\cl}{\hbox{\rm cl}\,} \newcommand{\vcl}{\hbox{vertcl}\,} \newcommand{\PE}{{\rm PE}} \newcommand{\SE}{{\rm SE}} \newcommand{\NE}{{\rm NE}} %\newcommand{\Prod}{\Pi} \newcommand{\gr}{{\rm Graph}} \newcommand{\PNE}{{\rm PNE}} \newcommand{\norm}[1]{\Vert #1 \Vert} \setlength{\evensidemargin}{.5in} \setlength{\oddsidemargin}{.5in} \setlength{\textwidth}{5.5in} \setlength{\topmargin}{0in} \setlength{\textheight}{8.0in} \setlength{\headheight}{0in} \setlength{\headsep}{0in} \setlength{\topsep}{0in} \setlength{\itemsep}{0in} \renewcommand{\baselinestretch}{1.0} \begin{document} \titlepage \title{\bf The Algebraic Geometry of\\ Perfect and Sequential Equilibrium} \author{Lawrence E. Blume\\ and\\ William R. Zame\thanks{Blume: Department of Economics, Cornell University, Ithaca, NY 14850. Zame: Department of Economics, The Johns Hopkins University, Baltimore, MD 21218 and Department of Economics, UCLA, Los Angeles, CA 90024. Financial support from the National Science Foundation, from the Center for Analytic Economics at Cornell University, and from the UCLA Academic Senate Committee on Research is gratefully acknowledged. Zame thanks the Department of Economics, VPI \& SU for hospitality and support during the final stages of preparation.}} \date{December 1989 \\ September 1993 \\(revised)} \maketitle \thispagestyle{empty} \pagebreak \thispagestyle{empty} \begin{center} {\Large \bf The Algebraic Geometry of \\ \smallskip Perfect and Sequential Equilibrium} \\ \bigskip Lawrence E. Blume and William R. Zame \\ \bigskip \bigskip {\Large \bf Abstract} \end{center} \medskip Two of the most important refinements of the Nash equilibrium concept for extensive form games with perfect recall are Selten's (1975) {\it perfect equilibrium\/} and Kreps and Wilson's (1982) more inclusive {\it sequential equilibrium\/}. These two equilibrium refinements are motivated in very different ways. Nonetheless, as Kreps and Wilson (1982, Section 7) point out, the two concepts lead to similar prescriptions for equilibrium play. For each particular game form, every perfect equilibrium is sequential. Moreover, for almost all assignments of payoffs to outcomes, almost all sequential equilibrium strategy profiles are perfect equilibrium profiles, and all sequential equilibrium outcomes are perfect equilibrium outcomes. We establish a stronger result: For almost all assignments of payoffs to outcomes, the sets of sequential and perfect equilibrium strategy profiles are identical. In other words, for almost all games each strategy profile which can be supported by beliefs satisfying the rationality requirement of sequential equilibrium can actually be supported by beliefs satisfying the stronger rationality requirement of perfect equilibrium. We obtain this result by exploiting the algebraic/geometric structure of these equilibrium correspondences, following from the fact that they are {\em semi-algebraic sets\/}; i.e., they are defined by finite systems of polynomial inequalities. That the perfect and sequential equilibrium correspondences have this semi-algebraic structure follows from a deep result from mathematical logic, the {\em Tarski -- Seidenberg Theorem\/}; that this structure has important game-theoretic consequences follows from deep properties of semi-algebraic sets. \bigskip \noindent {\large \bf Keywords\/}: Perfect Equilibrium, Sequential Equilibrium, Semi-Algebraic Sets, Tar\-ski -- Sei\-den\-berg Theorem. \bigskip \noindent {\large \bf Correspondent\/}: \begin{quote} Professor William R. Zame\\ Department of Economics\\ Pamplin Hall\\ V.P.I.\\ Blacksburg, VA 24061 \end{quote} \pagebreak \setcounter{page}{1} \section{Introduction} Two of the most important refinements of Nash equilibrium for extensive form games are {\it (trembling hand) perfect equilibrium\/} (Selten (1975)) and {\it sequential equilibrium\/} (Kreps and Wilson (1982)). These two equilibrium refinements are motivated in rather different ways, and correspond to rather different notions of rationality.\footnote{See Blume, Brandenburger, and Dekel (1991a,b) for a description of lexicographic beliefs and their role in describing perfect equilibrium, Myerson (1986) for a discussion of the axiomatics of expected utility with conditional probability systems, and McLennan (1989) for a characterization of sequential equilibrium using conditional probability systems.} Nonetheless, as Kreps and Wilson point out, these refinements lead to quite similar prescriptions for equilibrium play. In particular, every perfect equilibrium is sequential. Moreover, for each fixed game form, and for almost all assignments of payoffs to terminal nodes, all sequential equilibrium outcomes are perfect equilibrium outcomes, and almost all sequential equilibrium strategy profiles are perfect equilibrium strategy profiles. The main result of this paper improves these results in a significant way: We show that, for each game form and almost all assignments of payoffs to terminal nodes, {\it all\/} sequential equilibrium strategy profiles are perfect equilibrium strategy profiles. In other words, for almost all games, equilibria which can be supported by beliefs satisfying the rationality criteria of sequential equilibrium can actually be supported by beliefs satisfying the more stringent rationality criteria of perfect equilibrium. We obtain this result by exploiting the fact that the graphs of the perfect and sequential equilibrium correspondences have a special structure, because they are {\em semi-algebraic sets\/} (that is, they can each be written as the solution set to a finite number of polynomial inequalities). This fact allows us to make a connection between game theory and real algebraic geometry. We believe that, just as differential topology has proved to be the right tool for studying the fine structure of the Walrasian equilibrium correspondence, so will real algebraic geometry prove to be the right tool for studying the fine structure of game-theoretic equilibrium correspondences. The semi-algebraic nature of Nash equilibrium has been exploited by Kohlberg and Mertens (1986) to demonstrate that the set of Nash equilibria of any game has only a finite number of connected components, a crucial step in the demonstration that every game admits a stable component of the set of Nash equilibria. More recently, Schanuel, Simon and Zame (1991) have employed more sophisticated semi-algebraic techniques to examine the logarithmic and linear tracing procedures.\footnote{Schanuel, Simon and Zame also show that many of the usual game-theoretic equilibrium correspondences are semi-algebraic, and derive various consequences, including generic continuity.} Simon (1987) and Blume and Zame (1992) have also used a generalization of the theory of semi-algebraic sets to study continuous time games and local uniqueness of Walrasian equilibrium, respectively. In the next section we describe some of the machinery of semi-algebraic sets. Following that we discuss some applications of the semi-algebraic apparatus to non-cooperative game theory and discuss the necessary features of perfect and sequential equilibrium. The final section contains the statement and proof of our main theorem. %%%%%%%%%%%%%%%%%%%% \section{Semi-Algebraic Sets and Functions} Semi-algebraic sets in $\Rn$ are those sets which are defined by finite systems of polynomial inequalities: \begin{definition} A set $X\subset\Rn$ is {\em semi-algebraic\/} if it is the finite union of sets of the form $$ \{ x \in \Rn \ : \ f_1(x)=0, \ldots, f_k(x)=0\ \hbox{and}\ g_1(x)>0,\ldots,g_m(x)>0\} $$ where the $f_i$ and $g_j$ are polynomials with real coefficients. A function (or correspondence) $f:A\to B$ with semi-algebraic domain $A\subset\Rm$ and range $B\subset\Rn$ is {\em semi-algebraic\/} if its graph is a semi-algebraic subset of $\Rmn$ \end{definition} Obviously, polynomials are semi-algebraic, as are their inverse functions (or correspondences), and compositions of such. For example, the Euclidean norm $||\cdot||$ on $\Rn$ is semi-algebraic; its graph is $$ \gr(\norm{\cdot}) = \{(x,a) \ : \ x_1^2 +\cdots + x_n^2 - a^2 = 0\ \hbox{and}\ a > 0 \} \cup \{(0,0)\} $$ As might be expected, semi-algebraic sets and functions have a very special structure. For instance, each semi-algebraic set is the {\em finite\/} union of connected real-analytic manifolds (Hironaka (1975)). In particular, each semi-algebraic set has only a finite number of connected components, and has a well-defined dimension (the maximum of the dimensions of these manifolds). For our purposes, the following three additional properties of semi-algebraic sets are the crucial ones. \bigskip \noindent{\bf Topological Operations } {\it The closure, boundary and interior of a semi-algebraic set are again semi-algebraic sets.\/} (See Bochnak, Coste and Roy (1987), Proposition 2.2.2.) \bigskip \noindent{\bf Dimension } {\it If $X$ is semi-algebraic, then $\dim \, [ \cl X \ \backslash \ X] < \dim X$ and $\dim \cl X=\dim X$.\/} (See Bochnak, Coste and Roy (1987), Propositions 2.8.2 and 2.8.12.) \bigskip \noindent{\bf Generic Local Triviality } {\it Let $A, B$ be semi-algebraic sets and let \hbox{$f:A\to B$} be a continuous, semi-algebraic function. There is a (relatively) closed, lower-dimensional semi-algebraic subset $B_0\subset B$, (the ``critical set'') such that for each of the finite number of (relatively) open connected components $B_i$ of $B \backslash B_0$ there is a semi-algebraic set $C_i$ (the ``fiber'') and a semi-algebraic homeomorphism $h_i : B_i \times C_i \to f^{-1}(B_i)$ such that $f((h_i(b,c))=b$ for all $b\in B_i$ and $c\in C_i$.\/} (Hardt (1980); see also Bochnak, Coste and Roy (1987), Corollary 9.3.2.) \bigskip Generic local triviality says that, except for small sets, the domain and range of a semi-algebraic function $f$ can be broken up into pieces with the property that each piece in the domain ``is'' a product, and the restriction of $f$ to each of these pieces ``is'' the projection onto a factor. Generic local triviality serves the the same purposes for semi-algebraic functions that the Implicit Function Theorem and Sard's Theorem serve for smooth functions. Recall that the Implicit Function Theorem states that the inverse image of a neighborhood of a regular value ``is'' a product, and Sard's Theorem states that ``most'' values are regular. Generic local triviality says these things and more: \begin{itemize} \item The set of critical values is lower dimensional. \item The complement of the set of critical values has only a {\em finite\/} number of connected components. \item The critical set $B_0$ is itself semi-algebraic, and the restriction of $f$ to $f^{-1}(B_0)$ (the set of ``critical points'') is semi-algebraic. \end{itemize} In view of the third point, we may apply generic local triviality to the semi-algebraic mapping $f : f^{-1}(B_0) \to B_0$, and thereby derive implications for the critical set and the set of critical points. To illustrate the application of generic local triviality, we prove the following lemma on the continuity of semi-algebraic correspondences, which will be important later on. \bigskip \noindent {\bf Lemma } {\it Let $F:X\to Y$ be a semi-algebraic correspondence with compact values. Then $F$ is continuous at every point of the complement of a (relatively) closed, lower-dimensional, semi-algebraic subset of $X$.} \begin{proof} Let $G \subset X \times Y$ denote the graph of $F$, and write $\pi_X$ and $\pi_Y$ for the projections of $X \times Y$ onto $X$ and $Y$, repectively. Apply generic local triviality to the projection map $\pi_X$; write $X_0$ for the critical set, $X \backslash X_0 = \bigcup X_i$ for the decomposition of the complement of the critical set into connected components, $Z_i$ for the ``fiber'' of $X_i$, and $h_i$ for the semi-algebraic homeomorphism. Then $X_i$ is a connected, relatively open subset of $X$, and, for every $x \in X_i$, $$ F(x) = \pi_Y ((h_i(\{x\}\times Z_i)) $$ Since $h_i$ is a homeomorphism and $\pi_X((h_i(\{x\}\times Z_i)) = x$, it is evident that the restriction of $F$ to $X_i$ is continuous. Since $X_i$ is a relatively open set, $F$ is in fact continuous at each point of $X_i\,$. \end{proof} An important special case arises when $F$ is singleton-valued. \bigskip \noindent {\bf Corollary } {\it Let $f:X\to Y$ be a semi-algebraic function. Then $f$ is continuous at every point of the complement of a closed, lower-dimensional semi-algebraic subset of $X$.} \bigskip By definition a set is semi-algebraic if it can be defined by systems of polynomial equalities and inequalities. Of course, a given set may be defined in many different ways; the fact that a particular definition is not by polynomial inequalities does not exclude the possibility of an equivalent definition in terms of polynomial inequalities. What we would like therefore is a simple and powerful test for a set to be semi-algebraic. A remarkable theorem of mathematical logic, the Tarski -- Seidenberg Theorem (Tarski (1951), Seidenberg (1954)), provides what we want. The Tarski -- Seidenberg Theorem is concerned with the first-order theory of real closed fields; for our purposes, we only need to know what it tells us about the first-order theory of the real numbers.\footnote{Bewley and Kohlberg (1976a,b) have applied the Tarski -- Seidenberg Theorem to the real closed field of Puiseux series in order to establish some facts about zero-sum stochastic games. To the best of our knowledge, the first game-theoretic application of the Tarski -- Seidenberg Theorem was in Kohlberg's masters thesis at The Hebrew University. (We thank Abraham Neyman for this reference.)} In the interests of readability, the following exposition is informal. Formulas in the first-order theory of the real numbers are expressions involving variables and constants, the universal and existential quantifiers $\forall$ and $\exists$, the logical connectives $\land$ (and),$\lor$ (or), and $\neg$ (not), the operations $+$ (addition), $-$ (subtraction), $\cdot$ (multiplication), $/$ (division), and the relations $=$ (equality), greater than $>$ and less than $<$. (Note that we do not consider formulas involving sets or the ``belongs to'' relationship; it is this that distinguishes first-order formulas from higher order formulas.) We will not give a formal description of such formulas; intuitively we know what they are. (Formalities can be found in Chang and Keisler (1973), for example.) Here are some examples of first order formulas: \begin{itemize} \item[(1)] \qquad $x > 0 $ \item[(2)] \qquad $\forall y \ \exists x \ (x+y = 1) \land (x = y)$ \item[(3)] \qquad $\forall y \ y=1$ \item[(4)] \qquad $(x^2 + 4x = y) \land (y^3 = 3)$ \end{itemize} Of course, we have used the expressions $x^2$ and $y^3$ as shorthand for the longer expressions $x \cdot x$ and $y \cdot y \cdot y$. In the same spirit, we use the symbols for less than or equal $(\leq)$, greater than or equal $(\geq)$, implication $(\Rightarrow)$ and equivalence $(\iff)$ rather than the longer expressions they replace. Thus \begin{itemize} \item[(5)] \qquad $[\exists y \ (y > 0 \land xy = 3)] \Rightarrow x > 0$ \end{itemize} is also a first order formula. Variables which are quantified, such as $x$ and $y$ in formula (2) and $y$ in formulas (3) and (5), are said to be {\em bound\/}; unbound variables are {\em free\/}. (Note that a formula involving no variables is simply a conjunction and disjunction of real inequalities.) A formula with no free variables has a truth value, which might be true or false; both (2) and (3) above are false. Formulas which involve free variables have no truth value. However, if $\Phi$ is a formula in which only the variables $x_1,\ldots,x_n$ are free, substituting the real numbers $r_1,\ldots,r_n$ for $x_1,\ldots,x_n$ yields a formula $\Phi(r_1,\ldots,r_n)$ with no free variables; $(r_1,\ldots,r_n)$ {\it satisfies\/} $\Phi$ if $\Phi(r_1,\ldots,r_n)$ is true. The set of n-tuples satisfying $\Phi$ is said to be {\em defined\/} by $\Phi$; we write $\{x : \Phi(x)\}$ for this set. If $\{x : \Phi(x)\}$ is empty, $\Phi$ is {\em unsatisfiable\/}. Formulas $\Phi$ and $\Psi$ involving the same free variables are {\it equivalent\/} if they define the same sets.\footnote{This amounts to the same thing as logical equivalence.} By definition, a subset of $\Rn$ is semi-algebraic if and only if it is defined by a first-order formula with $n$ free variables and no bound variables. (For instance, formulas (1) and (4) above define semi-algebraic subsets of ${\bf R}^1$ and ${\bf R}^2$, respectively.) The Tarski -- Seidenberg Theorem allows us to identify {\em all\/} sets defined by first-order formulas as semi-algebraic. \bigskip \noindent {\bf Tarski -- Seidenberg Theorem } {\it Every first-order formula with $n$ free variables is equivalent to a first-order formula with $n$ free variables and no bound variables, and hence defines a semi-algebraic subset of $\Rn$.} %%%%%%%%%%%%%%%%% \section{Equilibrium} In this section we use the Tarski--Seidenberg Theorem to demonstrate that many important notions in non-cooperative game theory lead to semi-algebraic sets. We study $N$-person extensive form games with perfect recall. An {\em extensive form\/} is specified by a tuple $\Gamma=({\cal T},{\cal P},{\cal H},C,\rho)$ where ${\cal T}$ is a tree, ${\cal P}$ is the player partition, ${\cal H}$ is the information partition, $C$ is the labelling of choices and $\rho$ is the vector of probability distributions over moves of nature. (We treat $\rho$ as part of the game form, and not as a parameter.) The set of terminal nodes of the tree is denoted by $Z$. A {\em payoff function\/} for player $n$ is a function $u: Z \to {\bf R}$. Write $U_n = {\bf R}^Z$ for the space of player $n$'s payoff functions, and $U = \prod_n U_n = ({\bf R}^Z)^N$. The {\em game\/} $\Gamma(u)$ is specified by the extensive form $\Gamma$ and the payoffs $u \in U$. Let $S_n$ denote the set of (mixed) behavior strategies for player $n$, and let $I_n \subset S_n$ be the (finite) subset consisting of pure strategies. Write $S =\prod_{m=1}^N S_m$ and $S_{-n}= \prod_{m\neq n}S_m$. The sets $S, S_n, S_{-n}$ are all semi-algebraic (indeed, they are defined by {\em linear\/} inequalities). Fix a strategy $s_n$ for player $n$ and a terminal node $z \in Z$. The probability ${\rm Pr}\,\{z|s_n,s_{-n}\}$ that $z$ is reached (from the initial node), given that player $n$ plays according to $s_n$ and other players play according to $s_{-n}$, is a polynomial function of $s_n$ and $s_{-n}$ (because it is the product of the probabilities of those choices of player $n$ and all other players that describe the path from the root of ${\cal T}$ to $z$). In particular, the probabilities ${\rm Pr}\,\{z|s_n,s_{-n}\}$ are semi-algebraic on $S$. Hence, the expected utility functions $$ v_n(s_n,s_{-n},u) = \sum_z u_n(z){\rm Pr}\,\{z|s_n,s_{-n}\} $$ are semi-algebraic on $S \times U$. Of course, if we fix a strategy $\sigma_n \in S_n$, the probabilities ${\rm Pr}\,\{z|\sigma_n,s_{-n}\}$ are semi-algebraic on $S_{-n}$ and the expected utility functions $v_n(\sigma_n,s_{-n},u)$ are semi-algebraic on $S_{-n} \times U$. We show first that the set of Nash equilibria of a given game and the graph of the Nash equilibrium correspondence are semi-algebraic sets. We do this by explicitly writing down the polynomial inequalities that define these sets. A Nash equilibrium is a strategy profile with the property that no player can benefit by unilaterally changing his strategy. If a strategy is not optimal for a player, there is a pure strategy which does better. Thus the set of strategy profiles for which player $n$ is {\em not\/} optimizing is: $$ T_n (u) = \bigcup_{i_n \in I_n} \{ \, s : s \in S \ , \ \sum_{j_n \in I_n}v_n(j_n,s_{_n},u)s_n(j_n) < v_n(i_n,s_{-n},u) \, \} $$ Keep in mind that $S$ is a semi-algebraic set, so the expression $s\in S$ may be regarded as shorthand for the polynomial inequalities that define $S$. Now and in the future, we find it convenient to write $s \in S$ rather than to write the more cumbersome expressions involving the polynomial inequalities that define $S$. Thus $T_n(u)$ is written as the union of a finite number of sets (one for each pure strategy $i_n \in I_n$), each of which is defined by polynomial inequalities, and so $T_n(u)$ is a semi-algebraic set. Of course, the set of Nash equilibria for the game $\Gamma(u)$ is: $$ \NE(u) = S \ \backslash \ \bigcup_n T_n(u) $$ the complement of the set of all strategy profiles in which at least one player is not optimizing, so this too is a semi-algebraic set. To see that the graph of the Nash equilibrium correspondence is semi-algebraic, we proceed in the same manner. Set $$ V_n =\bigcup_{i_n \in I_n} \{ \, (s,u) : (s,u) \in S\times U \ ,\ \sum_{j_n \in I_n} v_n(j_n,s_{-n},u) s_n(j_n) < v_n(i_n,s_{-n},u) \, \} $$ This is evidently a semi-algebraic set. The graph of the Nash equilibrium correspondence is $$ \gr(\NE) = S\times U \ \backslash \ \bigcup_n V_n $$ and is, therefore, also a semi-algebraic set. Since a strategy profile is subgame-perfect if and only if it satisfies the Nash equilibrium condition in every subgame, we conclude, just as above, that the subgame-perfect equilibrium correspondence is defined by a finite number of polynomial inequalities. In summary, we have proved: \bigskip \noindent {\bf Theorem 1 } {\it For every extensive form $\Gamma$, the Nash and subgame-perfect equilibrium correspondences are semi-algebraic.} \bigskip Of course, the argument we have used is unnecessarily redundant; once we know that the graph $\gr(G)$ of a correspondence $G : U \to S$ is semi-algebraic, it follows immediately that the values $G(u)$ are all semi-algebraic, since $$ G(u)=\{s\in S\ :\ (u,s)\in G\} $$ Henceforth, we shall establish the semi-algebraic nature of correspondences, and leave the reader to infer the semi-algebraic nature of values. To talk about perfect and sequential equilibrium, we need some notation to describe perturbations. For each information set $h \in {\cal H}$, let $C(h)$ be the set of choices available at $h$, let $\Delta C(h)$ be the set of probability distributions over choices $C(h)$, and let $n(h)$ be the player to whom the information set $h$ belongs. Write ${\cal H}_n$ for the family of all information sets belonging to player $n$. If $h\in {\cal H}_n$, then each strategy $s_n \in S_n$ determines a probability distribution $s_n(h) \in \Delta C(h)$; write $s_n(h,c)$ for the probability assigned to the choice $c \in C(h)$. Write ${\bf C} = \cup_{h \in {\cal H}} C(h)$ for the set of all choices. A {\em perturbation\/} is a a function $\eta : {\bf C} \to {\bf R}_{++}$ such that $\sum_{c \in C(h)} \eta (c) < 1$ for each information set $h$. Given such a perturbation $\eta$, we define the {\em perturbed strategy set\/} for player $n$ to be $$ S_n(\eta) = \{\, s_n \in S_n : \forall c \in C(h) \ \forall h \in {\cal H}_n \ s_n(h,c) \geq \eta(c) \, \} $$ The {\em perturbed game\/} $\Gamma(u,\eta)$ is the game with extensive form $\Gamma$ and payoffs $u$, in which each player $n$ is constrained to choose strategies $s_n \in S_n(\eta)$. A {\em perturbed game equilibrium\/} for $\Gamma(u,\eta)$ is a strategy profile $s \in S(\eta) = \prod_n S_n(\eta)$ having the property that each player $n$'s strategy choice $s_n$ is a best response (among the strategies $S_n(\eta)$) to $s_{-n}$. The {\em perturbed game equilibrium correspondence\/} $\PNE: U \times {\bf R}_{++}^{\bf C} \to S$ is therefore: $$ \PNE(u,\eta) = \{\, s \in S(\eta) : \forall n \ \forall \sigma_n \in S_n(\eta) \ v_n(\sigma_n,s_{-n},u) \leq v_n(s_n,s_{-n},u)\,\} $$ Perfect equilibria are just limits of equilibria of perturbed games: \begin{definition} A strategy profile $s\in S$ is a {\em perfect equilibrium\/} of the game $\Gamma(u)$ if and only if there exist a sequence $\{\eta^t\}_{t=1}^{\infty}$ of perturbations and a sequence $\{s^t\}_{t=1}^{\infty}$ of strategy profiles such that $s^t\in \PNE(u,\eta^t)$ for each $t$ and $(\eta^t,s^t) \to (0,s)$. \end{definition} The definition of sequential equilibrium is a bit more complicated, since a sequential equilibrium consists of a strategy profile {\em and\/} a belief system. Since we are interested only in strategy profiles, however, it is convenient to use as the definition of sequential equilibrium the following result of Kreps and Wilson ((1982), Proposition 6). \bigskip \noindent {\bf Proposition A } {\it A strategy profile $s\in S$ is (the strategy part of) a sequential equilibrium of the game $\Gamma(u)$ if and only if there is a sequence $\{s^t\}_{t=1}^{\infty}$ of completely mixed strategies and a sequence $\{u^t\}_{t=1}^{\infty}$ of payoff functions such that \begin{itemize} \item $s^t \to s$ and $u^t \to u$ \item for all indices $t$, informations sets $h \in {\cal H}$, and choices $c,c'\in C_h$, if $s^t_h(c) > 0$ then $v_{n(h)}(c,s^t_{n(h)},u^t_{n(h)}) \geq v_{n(h)}(c',s^t_{n(h)},u^t_{n(h)})$ \end{itemize}} \bigskip Proposition A gives a characterization of sequential equilibrium in terms of ``test sequences''. The following result gives a more convenient characterization of sequential equilibrium in terms of ``perturbed games''. The proof simply adds utility perturbations to Selten's (1975) proofs of his Lemmas 11 and 12 and Theorem 7, which characterize perfect equilibrium in normal form games both in terms of test sequences and in terms of perturbed games. Details are left to the reader. \bigskip \noindent {\bf Proposition B } {\it A strategy profile $s\in S$ is (the strategy part of) a sequential equilibrium of the game $\Gamma(u)$ if and only if there is a sequence $\{(u^t,\eta^t,s^t)\}_{t=1}^{\infty} \subset\gr(\PNE)$ with limit $(u,0,s)$. } \bigskip Note that these characterizations of sequential equilibrium differ from the corresponding characterizations of perfect equilibrium only in that, for sequential equilibrium, we may tremble {\em payoffs\/} as well as strategies. With these definitions in hand, we now show that, for a given extensive form, all of these correspondences are semi-algebraic. \bigskip \noindent {\bf Theorem 2 } {\it For every extensive form $\Gamma$, the perturbed game correspondence $\PNE$, the perfect equilibrium correspondence $\PE$ and the sequential equilibrium correspondence $\SE$ are all semi-algebraic.} \begin{proof} The graph of $\PNE$ is: \begin{eqnarray*} \gr(\PNE) = \{\, (u,\eta,s) \in U \times {\bf R}^C_{++}\times S &: & s \in S(\eta) \ \forall n \ \forall \sigma_n \in S_n(\eta) \\ & & v_n(\sigma_n,s_{-n},u) \leq v_n(s_n,s_{-n},u)\, \} \end{eqnarray*} Keeping in mind our convention that expressions such as $s \in S(\eta)$ are shorthand for the first-order formulas that define the set $S(\eta)$, we see immediately that $\gr(\PNE)$ is defined by a first-order formula, so the Tarski -- Seidenberg Theorem implies that it is a semi-algebraic set.\footnote{Alternatively, it is easy to give an elementary argument along the lines of the argument we used for the Nash equilibrium correspondence.} For the perfect and sequential correspondences, the definitions we have given are not first-order, but we may rewrite them as $\delta$-$\epsilon$ statements and apply the Tarski -- Seidenberg Theorem. The graph of the perfect equilibrium correspondence is \begin{eqnarray*} \gr(\PE) \ =\ \{\, (u,s) \in U \times S &:& \forall \epsilon>0 \ \forall \delta > 0 \ \exists \eta \in {\bf R}_{++}^{\bf C} \ \exists s' \in S(\eta) {\rule[-.3cm]{0cm}{0cm} }\cr & & (u,\eta,s') \in \gr(\PNE) {\rule[-.3cm]{0cm}{0cm}\,}\cr & & \norm{\eta} < \delta\ \land \ \norm{s - s'} < \epsilon \ \} \end{eqnarray*} Clearly $\gr(\PE)$ is defined by a first-order formula and so, according to the Tarski -- Seidenberg Theorem, is semi-algebraic. The graph of the sequential equilibrium strategy correspondence is \begin{eqnarray*} \gr(\SE) = \{ (u,s) \in U \times S & : & \forall \epsilon > 0 \ \forall \delta > 0 \ \exists u' \in U \ \exists \eta \in {\bf R}_{++}^{\bf C} \ \exists s' \in S(\eta) {\rule[-.3cm]{0cm}{0cm} } {\rule[-.3cm]{0cm}{0cm} } \cr & & (u, \eta, s') \in \gr(\PNE) {\rule[-.3cm]{0cm}{0cm}}\cr & & \norm{\eta} < \delta \ \land \ \norm{u - u'} <\delta \ \land \ \norm{s - s'} < \epsilon \ \} \end{eqnarray*} Again, $\gr(\SE)$ is defined by a first-order formula and so, according to the Tarski-Seidenberg Theorem, is semi-algebraic. \end{proof} Note that the force of the Tarski -- Seidenberg Theorem is required in the above proofs precisely because the formulae for the graphs of PE and SE contain bound variables. Of course, similar arguments will also suffice to establish the semi-algebraic nature of many other equilibrium refinements.\footnote{Indeed, the only equilibrium refinement about which there is some question appears to be stable equilibrium, which is a set-valued solution concept.} The semi-algebraic nature of these various correspondences entails many consequences for their structure. For our purpose, the most important consequence is generic continuity. The following result is an immediate application of generic local triviality, as embodied in the Lemma of Section 2. \bigskip \noindent {\bf Theorem 3 } {\it For every extensive form $\Gamma$ there is a closed, lower dimensional semi-algebraic set $U_0 \subset U$ such that the Nash, subgame perfect,sequential, and perfect equilibrium correspondences are continuous at every point of $U \backslash U_0$.} \bigskip %%%%%%%%%%%%%%%%%% \section{Perfect and Sequential Equilibrium} In this section we establish the generic equality of the sets of perfect and sequential equilibrium strategy profiles. Our argument is based on the characterizations of perfect and sequential equilibrium strategies in terms of limit points of the graph $W = \gr(\PNE)$ of the perturbed equilibrium correspondence. The following definition will be useful. \begin{definition} The {\em vertical closure\/} of $W$ is the set $$ \vcl W=\{(u,\eta,s)\ :\ \exists \ \{ (u,\eta^t,s^t)\}_{t=1}^\infty \subset W \ , \ (u,\eta,s)=\lim_{t\to\infty} (u,\eta^t,s^t) \} $$ \end{definition} \\ \indent In words: the vertical closure of $W$ is the set of points which can be obtained as limits of sequences in $W$ that keep the payoff $u$ fixed. The definition of perfect equilibrium says that $s$ is a perfect equilibrium strategy profile of the game $\Gamma(u)$ if and only if $(u,0,s)$ is in the vertical closure of $W$. By contrast, Proposition B says that $s$ is a sequential equilibrium strategy profile of $\Gamma(u)$ if and only if $(u,0,s)$ is the limit of a sequence $\{(u^t,\eta^t,s^t)\}$ in $W$; that is, if and only if $(u,0,s)$ is in the (ordinary) closure of $W$. The generic coincidence of perfect and sequential equilibrium will therefore from the generic coincidence of $\cl W$ and $\vcl W$ at $\eta = 0$. It is clear from the definition that $\vcl W\subset\cl W$. For an arbitrary $W$, this would be all that could be said. As we have seen, however, $W$ is a semi-algebraic set, and so generic triviality enables us to say more. \bigskip \noindent {\bf Theorem 4 } {\it For every extensive form $\Gamma$ there is a closed, lower-dimensional set $U_0\subset U$ of payoffs such that the sets of perfect and sequential equilibrium strategy profiles coincide for all $u\in U \backslash U_0$. Moreover, the sets of perfect and sequential equilibrium strategies coincide for all payoffs $u$ at which the sequential equilibrium correspondence is lower hemi-continuous and the perfect equilibrium correspondence is upper hemi-continuous.} \bigskip Kreps and Wilson (1982) assert --- but do not prove --- that the sequential and perfect equilibria of a game $\Gamma(u)$ coincide at every $u$ where the perfect equilibrium correspondence is upper hemi-continuous. Our coincidence result, the second assertion of Theorem 4, is slightly weaker. Note that, because the sequential equilibrium correspondence is upper hemi-continuous and contains the perfect equilibrium correspondence, the perfect equilibrium correspondence must be upper hemi-continuous at each $u$ where it coincides with the sequential equilibrium correspondence. \bigskip \begin{proof} We first establish that certain functions are semi-algebraic. For $A$ a semi-algebraic set, write $D(x,A)$ for the (Euclidean) distance from $x$ to $A$. The graph of $D(x,A)$ is defined by a first-order formula: \begin{eqnarray*} \gr(D) = \{(x,d) : & x \in \Rn \ d\in {\bf R} \ d\geq 0 \ \forall\epsilon > 0\ \exists a\in A \ \forall b\in A {\rule[-.3cm]{0cm}{0cm}} \cr & \norm{x-a}^2 < (d+\epsilon)^2\ \land \ \norm{x-b}^2 \geq d^2 \ \} \end{eqnarray*} It follows from the Tarski -- Seidenberg Theorem that $D(x,A)$ is semi-algebraic. Define $f,g:U\times S\to {\bf R}$ by \begin{eqnarray*} f(u,s) &= & d{\Big (} (u,0,s)\, , \, W{\Big )} \cr g(u,s) &= &d{\Big (} (u,0,s)\, , \, W \cap \{(u',\eta,s') : u'=u\} {\Big )} \end{eqnarray*} The graph of the sequential equilibrium correspondence is $f^{-1}(0)$ and the graph of the perfect equilibrium correspondence is $g^{-1}(0)$. The exceptional set of games for which not all sequential equilibria are perfect is $$ E=\{u\ :\ \exists s \ f(u,s)=0 \ \land \ g(u,s)\not= 0 \}. $$ Clearly, $f$ and $g$ are semi-algebraic functions, so $E$ is a semi-algebraic set. We claim that it is lower-dimensional. To this end, define $ k(u)=\sup_s\{g(u,s) : f(u,s)=0\}$. The function $k$ is semi-algebraic and $E=\{u : k(u)\not= 0\}$. If $C$ is not lower-dimensional, there is a semi-algebraic open set $Q$ and an $\epsilon > 0$ with the property that $k\vert_Q> \epsilon$. The set $$ G=\{(u,s)\ :\ u\in Q\ \land\ f(u,s)=0\ \land\ g(u,s)\geq\epsilon\} $$ is semi-algebraic and its projection onto $Q$ is all of $Q$, so we can choose a semi-algebraic selection from this projection --- i{.}e{.} a semi-algebraic function $\beta : Q \to S$ with the property that $(u,\beta(u)) \in G$. From the generic continuity of semi-algebraic functions it follows that there is a semi-algebraic open set $Q' \subset Q$ on which $\beta$ is continuous. Let $u\in Q'$. Since $\beta(u)$ is a sequential equilibrium, there is a sequence $\{(u^t,\eta^t,s^t)\}_{t=1}^\infty$ in $W$ with limit $(u,0,\beta(u))$. From the continuity of $\beta$, $$ \Vert ( u^t,\eta^t,s^t ) - ( u^t,0,\beta(u^t) ) \Vert \ \to \ 0 $$ Thus for $t$ large enough, $g(u^t,\beta(u^t)) < \epsilon$, which contradicts the construction of $\beta$. We conclude that $E$ is lower-dimensional, as asserted. Set $U_0=\cl E$; this is a semi-algebraic set, and has the same dimension as $E$ (by the Dimension property). The argument above shows that $\SE(u) = \PE(u)$ for each $u \in U \backslash U_0$, so we have proved our first assertion. The second assertion rests on what we have already established and a simple observation about nested correspondences. Let $u$ be a payoff at which $\PE$ is upper hemi-continuous and $\SE$ is lower hemi-continuous. Lower dimensionality of $E$ (which entails density of its complement) means that we can find a sequence $\{u^n\}$ in the complement of $C$, converging to $u$. By definition of $E$, $\PE(u^n)=\SE(u^n)$ for each $n$. Upper hemi-continuity of $\PE$ at $u$ and lower hemi-continuity of $\SE$ at $u$ entail that $\PE(u) \supset \SE(u)$; since all perfect equilibria are sequential, we conclude that $\PE(u)=\SE(u)$ as desired. \end{proof} %\end{document} \pagebreak %%%%%%%%%%%%%%% \noindent {\Large \bf References} \bigskip \noindent Bewley, T. and E. Kohlberg (1976a), ``The asymptotic theory of stochastic games,'' {\it Mathematics of Operations Research\/}, {\bf 1}, 197--208. \noindent Bewley, T. and E. Kohlberg (1976b), ``The asymptotic solution of a recursion equation occurring in stochastic games,'' {\it Mathematics of Operations Research\/}, {\bf 1}, 321--336. \noindent Blume, L., A. Brandenburger and E. Dekel, (1991a), ``Lexicographic probabilities and choice under uncertainty,'' {\it Econometrica\/}, {\bf 59}, 61--80. \noindent Blume, L., A. Brandenburger and E. Dekel (1991b), ``Lexicographic probabilities and equilibrium refinements,'' {\it Econometrica\/}, {\bf 59}, 81--98. \noindent Blume, L. and W. Zame (1992), ``The algebraic geometry of competitive equilibrium,'' in W. Neuefeind and R. Reizman, eds., {\it Economic Theory and International Trade; Essays in Memoriam J. Trout Rader\/}, Springer-Verlag, Berlin. \noindent Bochnak, J., M. Coste and M-F. Roy (1987), {\it G\'eom\'etrie Alg\'ebrique R\'eelle\/}, Springer-Verlag, Berlin. \noindent Chang, C. and J. Keisler (1973), {\it Model Theory\/}, North Holland, Amsterdam. \noindent Hardt, R. (1980), ``Semi-algebraic local triviality in semi-algebraic mappings,'' {\it American Journal of Mathematics\/}, {\bf 102}, 291--302. \noindent Hironaka, H. (1975), ``Triangulations of algebraic sets,'' in R. Hartshorne, ed., {\it Algebraic Geometry; Arcata 1974\/}, American Mathematical Society, Providence. \noindent Kohlberg, E. and J.-F. Mertens (1986), ``On the strategic stability of equilibria,'' {\it Econometrica\/}, {\bf 54}, 1003-1038. \noindent Kreps, D. and R. Wilson (1982), ``Sequential equilibria,'' {\it Econometrica\/}, {\bf 50}, 863--894. \noindent McLennan, A. (1989), ``Consistent conditional systems in non-cooperative game theory,'' {\it International Journal of Game Theory\/}, {\bf 18}, 140--174. \noindent Myerson, R. (1986), ``Axiomatic foundations of Bayesian decision theory,'' Discussion Paper No. 671, J. L. Kellogg Graduate School of Management, Northwestern University. \noindent Schanuel, S., L. Simon and W. Zame, (1991), ``The algebraic geometry of games and the tracing procedure,'' in R. Selten, ed., {\it Game Equilibrium Models, vol. II: Methods, Morals and Markets\/}, Springer-Verlag, Berlin. \noindent Seidenberg, A. (1954), ``A new decision method for elementary algebra,'' {\it Annals of Mathematics\/}, {\bf 60}, 365--374. \noindent Selten, R. (1975), ``Reexamination of the perfectness concept for equilibrium points in extensive games,'' {\it International Journal of Game Theory}, {\bf 4}, 25--55. \noindent Simon, L (1987), ``Basic timing games,'' Working Paper, University of California at Berkeley. \noindent Tarski, A. (1951), {\it A Decision Method for Elementary Algebra and Geometry, 2nd ed.\/}, University of California Press, Berkeley. \end{document}