%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}

