Full text of DOI:10.1111/1468-0262.00156

Ž
.
Econometrica, Vol. 68, No. 5 September, 2000 , 1231᎐1248
GENERICITY AND MARKOVIAN BEHAVIOR IN
STOCHASTIC GAMES
1
BY HANS HALLER AND ROGER LAGUNOFF
This paper examines Marko¨ perfect equilibria of general, finite state stochastic games.
Our main result is that the number of such equilibria is finite for a set of stochastic game
payoffs with full Lebesgue measure. We further discuss extensions to lower dimensional
stochastic games like the alternating move game.
KEYWORDS: Stochastic games, Markov perfect equilibria, genericity.
1. INTRODUCTION
IF A FINITE ACTION STAGE GAME is infinitely repeated, then the standard theory
of repeated games has little to say about what will happen. It is well known from
the Folk Theorem that payoffs that dominate the minmax payoff can be
supported as perfect equilibria if players are patient enough.2 Moreover, the
indeterminacy problem extends to more general models of intertemporal play.
Ž
.
Dutta 1995 proves a Folk Theorem for stochastic games satisfying a full
Ž
.
dimensionality condition. Stochastic games, introduced by Shapley 1953 , are
general models of intertemporal play in which the stage game evolves according
to a transition function that maps probabilistically the current state and action
profile into next period’s state.
Ž
.
One approach taken to address the indeterminacy problem considers strategic
behavior of finite complexity. Various forms of finite automata, for example, are
shown to reduce multiplicity in some repeated games.3 One natural class of
simple automata receiving considerable attention is the class of Markovian
strategies. Markovian strategies rule out the possibility to extend memory, by
using states of the automaton, beyond what is encoded in the states of the game.
Hence, players condition only on payoff-relevant information.4 The present
paper establishes a genericity result with respect to Markov perfect equilibria
Ž
.
MPE in stochastic games. Specifically, we show that the set of Markov perfect
1 We would like to thank, without implicating, Prajit Dutta, Daniel Kahn, Andrew McLennan,
Lones Smith, and especially Akihiko Matsui for helpful conversations. We are also grateful to an
editor and three anonymous referees for very helpful and detailed comments and suggestions.
2
Ž
.
Ž
.
See Aumann 1981 and Fudenberg and Maskin 1986 .
3
Ž
.
Ž
.
See, for example, Abreu and Rubinstein 1988 , Kalai, Samet, and Stanford 1988 , and Cho and
Ž
.
Li 1999 , among others. The aforementioned work first fixes bounds on states, then examines
Ž
.
outcomes arising from them. Without fixing the bounds a priori, Kalai and Stanford 1988 show that
in the standard repeated game any perfect equilibrium can be approximated by strategies that are
finitely complex in the sense that they are implementable by finite-state automata.
4
Ž
.
Ž
.
Recent work focussing on Markovian behavior includes Dutta 1996 , Maskin and Tirole 1997 ,
Ž
.
and Fudenberg and Maskin 1995 .
1231

1232
HANS HALLER AND ROGER LAGUNOFF
equilibria is finite for a set of stochastic game payoffs with full Lebesgue
measure.
In the special case where the stochastic game is a standard repeated game,
this result is not surprising. Since players’ Markov strategies do not condition on
the past, the Markov perfect equilibria of repeated games consist of infinite
repetitions of Nash equilibria of the stage game. In that case, one can apply the
Ž
.
Ž
.
well known result of Wilson 1971 and Harsanyi 1973 who show that the
number of Nash equilibria in any normal form game is generically finite with
respect to payoffs.5 Hence, in a trivial sense, Markov perfect equilibria break
the extreme multiplicity in repeated games by preventing all intertemporal
reactions.
However, the Harsanyi-Rosenmuller-Wilson result cannot be directly applied
¨
to general stochastic games. Unlike in normal form games, players’ payoffs span
an infinite horizon and are not linear in strategies. Nevertheless, with some
effort, the recursive structure of Markovian behavior admits a proof of generic
Ž
.
finiteness similar in spirit to techniques used by Debreu 1970 .
Section 2 gives a brief account of various notions of genericity. While ‘‘generic
finiteness’’ does not eliminate multiplicity, it demonstrates that MPE are locally
isolated, and so comparative statics exercises for small changes are well defined.
Section 3 introduces definitions and notation. Section 4 describes the main
result. There, we examine the logic of the result, and give a formal proof.
Besides the unsurprising case of repeated games, our result applies to many
nontrivial stochastic games of interest. Examples include resource extraction
Ž
Ž
..
Ž
games e.g., Levhari and Mirman 1980 , capital accumulation games e.g.,
Ž
..
Ž
Dutta and Sundaram 1992 , and strategic learning models e.g., Bergemann
and Valimaki 1996 .
Ž
..
One particular stochastic game to which our result does not apply is the
alternating move game. In these games, two players move in sequence; each
player can only revise his decision in alternate periods. Examples are the
Ž
.
duopoly price and Cournot quantity games studied in Benabou 1989 and
Ž
.
Maskin and Tirole 1987, 1988a,b . As it turns out, these alternating move games
are nongeneric in the fully dimensional state-dependent payoff space. Section 5
discusses reasons for this and examines potential extensions to lower dimen-
sional games. A companion paper, Haller and Lagunoff 1997 , in fact, extends
the genericity result to the alternating move game. An Appendix contains details
of the proof.
Ž
.
Note that unlike in repeated games, the Markov restriction in general
stochastic games may encode enough information to construct useful punish-
ments and support cooperation. For instance, MPE may be shown to support
cooperation in certain state-dependent versions of repeated Prisoner’s Dilemma.
5 Other analyses of genericity in games include Rosenmuller 1971 , Kreps and Wilson 1982 ,
Ž
.
.
Ž
.
¨
Ž
.
Ž
.
Ž
Ž
.
Blume and Zame 1994 , Park 1997 , Govidan and McLennan 1998a , Keiding 1997 , McKelvey
Ž
.
Ž
.
Ž
.
Ž
.
and McLennan 1997 , McLennan 1997 , Quint and Shubik 1997 , McLennan and Park 1999 . The
last five derive generic upper bounds for the number of equilibria.

STOCHASTIC GAMES
1233
One example is the alternating move Prisoner’s Dilemma game. Each player can
alter his behavior only in every other period. It is not difficult to show that
mixed strategy punishments may be used to enforce cooperation when players
are patient enough. Alternatively, a slight modification of the standard repeated
Prisoner’s Dilemma game adds a state variable that can support cooperation. In
this modification, a nontrivial state variable varies depending on whether or not
a defection has been observed. The stage payoffs can then be made to vary
across states by adding a very small number to each of the stage game payoffs in
Ž
.
state D the state in which someone defected . This perturbed game now has a
payoff relevant state variable that can clearly be used to trigger an infinite
‘‘Nash-threats’’ punishment should a defection ever occur.
Ž
.
In other types of stochastic games Dutta 1996 establishes existence of
efficient MPE. His result utilizes a sufficient condition called ‘‘state symmetry’’
that requires that all individuals essentially rank the states in the same way in
Ž
.
their preferences in the symmetric optimum. For example, common pool
resource extraction problems satisfy state symmetry.6 The intuition is that
efficiency is attainable when players are patient since individuals’ ranking over
continuation payoffs coincide.
2. GENERICITY CONCEPTS
We have argued that choosing the appropriate parameter space is crucial. For
this reason the choice of genericity concept also warrants attention. There are
two notions of genericity: one is measure-theoretic, and the other is topological.
Our concept of genericity is full Lebesgue measure, the standard measure-theo-
retical notion of genericity in a Euclidean space or a suitable subset thereof.
The term ‘‘generic’’ is meant to capture the fact that a property holds ‘‘for
almost all parameters.’’ More formally, a property is called generic for a family
of models indexed by parameters bgB if the property holds for a generic
subset A of B. The standard notion of genericity in the measure-theoretical
sense assumes that B is a measurable subset of a Euclidean space ޒl with
l
l
lŽ .
␭ B )0 where ␭ is Lebesgue measure on ޒ . Then a measurable subset A of
lŽ
.
B is considered generic relative to B, if ␭ B_A s0. This definition general-
izes to other spaces B endowed with a canonical measure. However, the space B
may lack a canonical measure or, at least, it may be difficult to agree on one.
The concept of ‘‘prevalence’’ in Anderson and Zame 1997 extends the mea-
sure-theoretical notion of genericity to infinite dimensional parameter sets B
that are convex subsets of a topological vector space where an analog of
Lebesgue measure is unavailable.
Ž
.
An alternative is a topological notion of genericity provided that B is a
topological space. In the topological context, A;B is called generic if A is
open and dense relative to B. The question of what constitutes a natural
6 The alternating move Prisoner’s Dilemma game does not.

1234
HANS HALLER AND ROGER LAGUNOFF
topology for the economic model is, in part, a pragmatic one. See Hildenbrand
Ž
.
Ž
.
1974, p. 96 and Grandmont et al. 1974 .
Since, in our case, B is a Euclidean space, both concepts of genericity are
applicable. But as a rule, they do not coincide.7 In order to facilitate compar-
Ž
.
Ž
.
isons with Wilson 1971 , Harsanyi 1973 , and others, we therefore opt for the
measure-theoretic notion with Lebesgue measure as the canonical measure.
Whether our main result, Theorem 1, would go through as well when the
topological notion were used, is an open question. For more on genericity
Ž
.
notions, see Mas-Colell 1985 .
3. THE GENERAL MODEL
3.1. Stochastic Games
Here we define the general class of stochastic games with finite states. Let
1
ꢀ
4
ꢀ
K 4
Ns 1, . . . , n denote a finite set of players. Let ⍀s ␻ , . . . , ␻ denote a finite
set of states. In each state ␻, denote a finite set of actions by Si␻ for each player
i. Without loss of generality, we will assume that the sets Si␻ that index
Ž
state-contingent actions are mutually disjoint so that an action si sometimes
denoted si␻ for clarity is known to come from a particular Si␻ .
.
Note that standard formulations of stochastic games typically specify state-
invariant action sets. Ordinarily, this entails no loss of generality since the action
sets can always be enlarged without changing the strategic properties of the
game. However, our concern is with genericity, and so the addition of redundant
actions is problematic as it changes the maximal dimension of the game. Hence,
our formulation requires state-dependence.
The set of action profiles in state ␻ is given by S 'S1␻ = иии =Sn␻ , and
␻
n
<
<
<
<
Syi ␻ s=j/ i Sj␻ . Let mi␻ s Si␻ and m s S sŁis1 mi␻ denote the respec-
␻
␻
tive cardinalities. To simplify notation, we will write mj 'm
j
for js1, . . . , K.
␻
< <
Finally, set SsD S and ms S sÝ
m . Action profiles are denoted by
␻
␻
␻ g ⍀
␻
s, or when necessary by s .
␻
Ž
.
Let U s denote i’s payoff of action profile s gS in state ␻. Player i’s
payoffs can be summarized by an m=1 state dependent column vector U given
i
␻
␻
␻
i
by
w
Ž .xT
U s U s
i
i
sgS
T
nm
w x
Ž
.
where и denotes the transpose of the vector. Let Us U gޒ
denote the
i
payoff vector of all the players.
7
w
x
For example, the set of rational numbers in Bs 0, 1 has Lebesgue measure zero. Therefore,
the set A of irrational numbers in B is a measure-theoretically generic subset of B. This implies
that A is dense in B. Yet, A fails to be open in B and, hence, is not a topologically generic subset
of B strictu sensu. However, A is a residual subset of B. On the other hand, an open and dense
subset of B need not be measure-theoretically generic. Such an example can be obtained through a
Ž
.
Cantor-like construction: cf. Example 4.5 in Gilles, et al. 1998 .

STOCHASTIC GAMES
1235
Ž
.
The state evolves over time according to a transition function Q : Sª⌬ ⍀ .
Ž
.
We write Q ␻ЈNs to denote the probability that the game enters state ␻Ј
␻
given that the current action profile is s gS in state ␻.
␻
␻
Time is assumed discrete, ts0, 1, 2, . . . , and each player i is assumed to use a
discount factor ␦i g 0, 1 . There is an initial distribution ␲ of states at ts0
Ž
.
given by the 1=K vector
1
w
Ž
.
Ž
K .x
␲s ␲ ␻ , . . . , ␲ ␻
.
In particular, let ␲ denote the Dirac vector that assigns all mass to state ␻. A
␻
²
:
stochastic game ⌫ is summarized by the tuple N, ⍀, S, U, Q, ␦1, . . . , ␦n, ␲ .
Notice that a standard repeated game has a trivial stochastic game represen-
8
ꢀ
4
tation in which there is a single state, ⍀s ␻ . A simple example of a nontrivial
stochastic game is a resource extraction game such as the one described in
Ž
.
Dutta 1996 . There are two firms: ns2, and the state ␻ describes the current
Ž
amount of a natural resource remaining e.g., the amount of oil left in the
.
ground . The extraction rate for firm i is given by si, which is assumed to be
w
x
Ž
.
chosen from a finite grid in 0, 1 . The transition is deterministic: Q ␻ЈNs s1
␻
w
Ž
.x
Ž .
whenever ␻Јs 1y␪ s1 qs2 ␻ where ␪ и is a function of the two firms’
Ž
.
extraction rates and s1, s2 ss gS . Finally, i’s payoff is his profit given by
␻
␻
Ž
.
w ŽŽ
.
.
Ž .x
U s s p s1 qs2 ␻ yc si si ␻
i
␻
Ž .
Ž .
the extraction rate, and s1, s2 ss gS .
where p и is the inverse demand, c и is the firm’s marginal cost as a function of
Ž
.
␻
␻
Since our concern is in how the equilibrium set depends on payoffs, we use
the notation ⌫ U to account for the explicit dependence on payoffs. We refer
to the stochastic game form, ⌫ и , as the stochastic game structure without
Ž .
Ž .
having specified payoffs.
Ž .
Let s t denote the profile of actions in period t. A standard notation denotes
the complete history of play at time tq1 by htq1 s s 0 , s 1 , . . . , s t . A
beha¨ior strategy for player i maps each history h and each state ␻ into a mixed
Ž Ž . Ž .
Ž ..
Ž
.
strategy in ⌬ Si␻ . A perfect equilibrium is a profile of behavior strategies such
that each individual’s behavior strategy maximizes the expected discounted
ϱ
␶
yt
t
payoff Et Ý
1y␦i ␦i U s ␶ Nh , ␻ after every history ht and in every
w
Ž
. Ž Ž .. x
␶st
state ␻ that can be reachedi from ht via Q.
Ž
.
A result of Dutta 1995 proves a Folk Theorem for the general class of
stochastic games. He shows that any payoff that dominates a certain long-run
minimax can be arbitrarily approximated by perfect equilibrium payoffs for
sufficiently patient players if the individually rational set of payoffs does not vary
across histories, and if the game satisfies a full dimensionality requirement.9
8 Equivalently, there may be many states, but Q places all mass on a single state regardless of the
conditioning state and profile.
9 In stochastic games the relevant minmax must be taken over behavior strategies rather than
stage game strategies. Dutta defines a limiting minmax as ␦i ª1 in order to obtain a reference point
that is invariant to discount factor. His result requires that the individually rational payoff set
Ž
.
relative to this minmax be invariant across histories and that its convex hull have full dimension
with respect to the number of players.

1236
HANS HALLER AND ROGER LAGUNOFF
The application of Dutta’s result here generically resolves the multiplicity
issue in stochastic games when all perfect equilibria are considered. However,
we will restrict our attention to the special class of strategies known as
Marko¨ian strategies. These are strategies that depend only on payoff relevant
information.
3.2. Marko¨ian Beha¨ior
In the stochastic game the payoff relevant part of history is the current state.
Ž
.
Ž
.
A Marko¨ian strategy for player i is given by fi g= ⌬ Si␻ . We write fi si N␻
␻
to denote the probability that i assigns to si gSi␻ when the current state is ␻.
The players’ choices of Markovian strategies induce a joint Markov distribution
f defined by
n
Ž
.
Ž .
f s N␻ .
f sN␻ s
Ł
i
i
i
s1
Let F denote the set of all joint Markov distributions. Given a joint Markov
Ž
.
strategy profile fgF the dynamic payoff Vi fN␻ to player i in state ␻ is
expressed recursively by
Ž .
1
Ž
.
Ž
. Ž
.
Ž .
Ž
.
Ž
.
Vi fN␻ s
f sN␻ 1y␦ U s q␦
V fN␻Ј Q ␻ЈNs .
Ý
i Ý
␻ Ј
i
i
i
s
gS
␻
Ž
.
A Marko¨ perfect equilibrium MPE of stochastic game ⌫ is perfect equilibrium
in Markov strategies. Existence of MPE in finite state stochastic games is well
established see, for example, Friedman 1986, Theorem 4.2 . It is also well
known that one best response to Markovian strategies fyi s fj
vian strategy. Therefore, f is an MPE whenever
Ž
Ž
..
Ž .
is a Marko-
j/ i
ˆ
ˆ
᭙i, ᭙fi , ᭙␻.
Ž
.
V fN␻ GV
i Ž
f
, f N␻ ,
.
i
yi
i
4. GENERIC FINITENESS OF MPE
4.1. The Main Result
Fix a stochastic game form ⌫ и , and for each payoff vector Ugޒnm, let
Ž .
Ž .
Ž .
E U denote the set of MPE of ⌫ U . The main result of the paper is the
following theorem.
nm
Ž .
THEOREM: Gi¨en ⌫ и , there exists a set U:ޒ
such that
the set U has full Lebesgue measure in ޒnm and
Ž .
i
Ž .
Ž .
Ž .
ii for all UgU, the set E U of MPE of ⌫ U is a finite set.
We remark, first, that the conclusion of the theorem does not depend on the
discount factors. The set of MPE is finite regardless of how patient are the
players. Naturally, the players’ patience does determine which finite set of

STOCHASTIC GAMES
1237
Ž
.
payoffs can be supported. Maskin and Tirole 1997 prove a genericity result for
MPE of finite horizon stochastic games. This is equivalent to setting ␦i s0 after
some time t. Their notion of genericity applies to the fully dimensional state
dependent payoffs. Hence, their result is a finite horizon analog of ours. For this
reason, the backward induction techniques used in their proof cannot be applied
here.
Note, second, that in the standard repeated game, the set of MPE coincides
with repetitions of Nash equilibria of the stage game. Hence, the result implies
the Harsanyi-Rosenmuller-Wilson extension to MPE of repeated games.
¨
The proof is organized into three key steps. The first establishes a genericity
result for the closure of the set of completely mixed MPE. An MPE f is
completely mixed if the joint Markov profile satisfies, for each ␻ and each
Ž
.
U
oŽ .
sgS , f sN␻ )0. Let E U denote the set of completely mixed MPE of
␻
Ž .
o Ž
.
oŽ .
⌫ U . Let E
denote the closure of E U . The first step then shows the
following result.
nm
Ž .
PROPOSITION: Gi¨en ⌫ и , there exists a set U with full measure in ޒ
such
that for each UgU, the set Eo
Marko¨ strategies.
U
Ž
.
consists of isolated points in F, the set of joint
The second step replaces ‘‘isolated points’’ by ‘‘finitely many points,’’ utilizing
a standard compactness argument. The final step yields the Theorem as a
corollary. The intuition behind it is that MPE that are not completely mixed are,
in fact, completely mixed on a smaller support. Hence, we examine the reduced
stochastic game with restricted support, and note that the previous results apply.
Since there are only finitely many supports, generic finiteness holds for all MPE.
The next two subsections introduce relevant notation and outline the logic of
the proof.
4.2. Some Notation
For our purposes, it will prove more convenient to express payoffs in terms of
sums and products of matrices. First, for any joint Markov distribution f let Pf
denote the K=m matrix induced by f:
1
1
1 1
1
1
f s N␻
иии f sm
N␻
0
иии
иии
Ž
.
Ž
.
␻
␻
1 2
2
Ž
.
0
иии
0
f s N␻
␻
Pf s
.
.
.
.
.
.
0
0
иии
иии
0
иии
0
2
.
.
.
2
f sm
2
N␻
иии
.
.
.
Ž
.
␻
.
.
.
.
.
.
0
K
.
1
␻
K
K
иии f sm
K
N␻
Ž
f s
.
0
K
N␻
Ž
.
␻

1238
HANS HALLER AND ROGER LAGUNOFF
Next, write Q as an m=K transition matrix for the stochastic game, given by
1
1 1
2
1 1
K
1 1
Ž
.
Ž
.
Ž
.
Q ␻ Ns
␻
Q ␻ Ns
,
Q ␻ Ns
иии
иии
иии
␻
␻
1
21
Ž
.
Q ␻ Ns
␻
.
.
.
.
.
.
1
.
.
.
.
.
.
Q ␻1 Nsm
1
Ž
.
␻
Qs
.
.
.
.
1
1 2
Ž
.
Q ␻ Ns
␻
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
K
K
Q ␻1 Nsm
K
иии
иии Q ␻ K Nsm
K
Ž
.
Ž
.
␻
␻
Ž .
Now, the dynamic payoffs in ⌫ U can be expressed as linear functions of
payoff parameters:
ϱ
t
Ž .
2
Ž
.
Ž
.
t Ž
.
Vi fN␻ s␲ и
1y␦i ␦i Pf и Q и Pf иU
Ý
␻
i
t
s0
'␲ и Af иU .
␻
i
Ž .
Ž
.
i
Clearly, the right-hand side of 2 is smooth in the pair f, U . But notice that
Ž
.
for player i and state ␻, the probabilities fi si N␻ , si gSi␻ , have to satisfy
Ž Ž .
si N␻ s1, hence cannot vary independently. For the case of completely
Ýs
f
i
miixed MPEᎏwhich will be assumed in the first stepᎏone gets around this
ꢀ
4
problem by fixing some action di␻ gSi␻ for player i. Let Di s di␻ : ␻g⍀
denote the set of ‘‘normalizing actions’’ for player i. By varying ␻g⍀ and
is1, . . . , n we pin down Kn normalizing equations satisfying
Ž .
3
Ž
.
Ž
.
fi di␻ N␻ s1y
fi si N␻ ,
␻g⍀ ,
is1, . . . , n.
Ý
ꢀ
4
sigSi _ di␻
␻
Finally, for si fDi, the K=m matrix
Ѩ
Ž
.
w
x
Af
B si N␻ s
f
Ž
.
Ѩ fi si N␻
is especially relevant to the proof.
4.3. An Outline of the Argument
Now we are ready to draw a more detailed road map for the proof. The first
step, showing the Proposition, is the critical one. To understand its logic, it is
useful to compare it to Harsanyi’s, by now standard, result for normal form
games. He obtains a system of equations by examining first order necessary
conditions for Nash equilibrium. In normal form games, strategies enter linearly

STOCHASTIC GAMES
1239
in payoffs. Harsanyi exploits this linearity to derive an explicit mapping from
equilibrium strategies to payoffs. Sard’s Theorem asserts that the regular values
of this map have full measure. The linearity of the system is again used to show
that the corresponding regular strategies are locally isolated in the simplex.
Like Harsanyi, we also proceed from a system of equations derived from first
w
x
order necessary conditions, Df Vi s0, for Markov perfection. We then would
w
w xx
have to show full rank of the Jacobian matrix DU Df Vi . It turns out that the
first order necessary conditions translate into a system of myKn equations
Ž .
4
Ž .
␲ и B si N␻ иU s0
␻
f
i
Ž
where is1, . . . , n, ␻g⍀, si fDi, m'Ýi mi 'Ýi Ý mi␻ this step is Lemma
␻
.
1 . To economize on notation, we rewrite the system of equations as a single
vector equation M f, U s0 that is satisfied for any pair f, U with fgE
this step is Lemma 2 i . The main task at hand is to show that ѨMrѨU has full
rank Lemma 2 ii . However, here a difficulty arises which prevents us from
simply adapting Harsanyi’s result. Unlike in normal form games, our system is
not linear. Rather, players’ dynamic payoffs in stochastic games are shown to be
rational functions of Markovian strategies. This necessitates a lengthy and
Ž
.
Ž ..
Ž
.
o Ž
.
U
Ž
Ž
Ž ..
Ž
.
tedious proof of the full rank condition on the system M и, и perturbed by U.
Since, roughly, M maps F=ޒnm to ޒmyK n, we can apply the Implicit
Ž
.
Function Theorem to derive locally an implicit, smooth map⌿ from strategies,
i.e. F to an myKn-dimensional subspace of ޒnm so that points on the graph of
Ž
.
this map satisfy the first order necessary conditions for MPE Lemma 3 .
Ž
.
From there, the logic if not the details is more standard. Sard’s and Fubini’s
Theorems are used to show that regular values of ⌿ have full measure in ޒnm
Ž
.
and that the corresponding regular points are locally isolated Lemmas 4 and 5 .
Throughout most of the proof, until and including Lemma 5, local analysis is
performed. A subsequent countability argument yields a global result as asserted
in the Proposition. As pointed out earlier, two more steps remain to complete
the proof of the Theorem.
Ž
.
An alternative route to genericity results has been taken by Balasko 1988
who performs global analysis from the very beginning. While more elegant, it
would not spare us the tedious proof of the full rank assertion of Lemma 2
below. A second alternative route, suggested by a referee, has been taken
Ž
.
Ž
.
recently by Blume and Zame 1994 and Govindan and McLennan 1998a,b
who rely on the theory of semi-algebraic sets. A semi-algebraic set is a set
characterized by a finite system of polynomial inequalities. Such systems turn
Ž
out to have appealing generic properties the Blume and Zame paper is a good
.
reference . If, as we conjecture, the implicit function ⌿ in our proof is semi-
algebraic, then these properties may be used to simplify the latter part of our
Ž
.
proof though not the cumbersome Lemma 2 and imply a potentially stronger
result.10 By preferring the more familiar perturbation methods of Debreu 1970
Ž
.
10 One of the referees outlined an argument that uses semi-algebraic methods on the Bellman
Ž .
equation 1 . If successful, this might lead to a still shorter proof.

1240
HANS HALLER AND ROGER LAGUNOFF
Ž
.
and Harsanyi 1973 , we make the local arguments explicit rather than embed
them in the semi-algebraic results.
4.4. A Proof
Ž .
Let ⌫ и be as hypothesized. We are going to prove the Proposition first.
Ž
.
Choose a normalization Ds D1, . . . , Dn . Notice that F is a compact and
full-dimensional convex subset of the myKn-dimensional affine subspace of
ޒm given by 3 .
Ž .
oŽ .
LEMMA 1: For any Ugޒnm, let fgE U . Then it satisfies each of the myKn
Ž .
Ž .
equations described by 4 , subject to 3 .
The proofs of this and all subsequent Lemmata are contained in the Ap-
pendix.
We now define the following neighborhood of F. Let ⑀)0 and define the
open set F⑀ such that fgF⑀ implies:
Ž .
Ž .
for each i, y⑀-fi si N␻ for si gSi␻ , ␻g⍀;
i
Ž .
Ž
.
ii ÝS fi si N␻ -1q⑀.
i␻
Clearly F⑀ contains the compact set F where the topological notions are
Ž .
relative to the affine subspace given by 3 . For sufficiently small ⑀, all the
subsequent differential geometry and topology arguments are valid on F⑀. By
⑀
Ž
.
extending the analysis to F for the time being, we allow the values fi si N␻ and
Ž
.
fi di␻ N␻ to become zero or slightly negative. We do, however, maintain the
o
Ž .
Ž .
Ž .
restrictions 3 . Replacing ⑀ by 0 in i and ii yields the convenient notation F
for the interior of F that contains the completely mixed MPE.
From now on, we work with the mapping M associated with the left-hand side
⑀
nm
of 4 , i.e. M : F =ޒ ªޒmyK n where
Ž .
Ž .
Ž
.
Ž
.
5
Mis f, U s␲ и B si␻ N␻ иU .
␻
f
i
i␻
LEMMA 2: Let Ugޒnm. Then:
Ž .
Ž .
M f, U s0 for all fgE U ;
o Ž
.
i
ii ѨMrѨU has full rank myKn at f, U for all fgF⑀.
Ž .
Ž
.
Lemmata 1 and 2 are used to establish the next three Lemmata which
collectively lay the groundwork for local properties of profiles in Eo U . Call
Ž
.
1
2
2
1
2
Ž
.
ꢀ
4
ꢀ
4
Cs C , C a suitable partition of 1, . . . , m , if C jC s 1, . . . , m , and C l
C sл, with C smyKn. Given a suitable partition C, we decompose the
1
2
<
<
vectors Ugޒnm accordingly: Us UC1 , UC 2
Ž
.
.
0
0
⑀
nm
0
0
Ž
.
Ž .
satisfy M f , U s0. Then there exist a
LEMMA 3: Let f , U gF =ޒ
1
2
Ž
.
suitable partition Cs C , C and
Ž .
i
open neighborhoods NF , NC1 and NC 2 of f 0, UC01 and UC02 , respecti¨ely, and
Ž .
ii a locally smooth mapping ⌿ : NF = NC1 ªNC 2
Ž
.
such that if UC 2 s⌿ f, UC1 , then UC 2 is the unique sub¨ector in NC 2 that sol¨es the
Ž
.
equation M f, UC1 , UC 2 s0.

STOCHASTIC GAMES
1241
0
0
⑀
nm
0
0
Ž
.
Ž
.
Now let again f , U gF =ޒ
with M f , U s0. Fix the neighbor-
hoods NF , NC 2 , and NC1 and the mapping ⌿ obtained in Lemma 3. Call
Ž
Ž
.
.
f, UC1 g NF = NC1 an f-regular point of ⌿ , if Ѩ⌿rѨ f has full rank myKn at
Ž
.
f, UC1 . Call f, UC1 g NF =NC1 an f-critical point of ⌿ otherwise. Call UC 2 g NC 2
Ž
.
Ž
.
an f-critical ¨alue of ⌿ , if UC 2 s⌿ f; UC1 with f; UC1 an f-critical point of ⌿.
LEMMA 4: There exists a correspondence Z : NC1 ªªNC 2 such that for each
UC1 g NC1
Ž .
,
Ž .
the set Z UC1 has Lebesgue measure zero in NC 2 and
i
Ž . .
Ž
.
Ž
ii the set of f-critical ¨alues of ⌿ и, UC1 coincides with Z UC1 .
Ž
.
Clearly, the Lemma implies that the set of f-critical values of ⌿ и, UC1 has
0
0
Ž
.
Lebesgue measure zero in NC 2 . Now fix NF , NC 2 , NC1 with f , U g NF = NC 2
Ž .
= NC1 as before with Z и as in Lemma 4.
ꢀ
Ž
.
Ž
.4
LEMMA 5: Let Zs UC1 , UC 2 g NC1 =NC 2 NUC 2 gZ UC1 be the graph of Z.
Ž .
i
Z is measurable and has Lebesgue measure zero in NC1 = NC 2
.
ii If Us UC1 , UC 2 g NC1 = NC 2 and UfZ, then the elements of NF U '
fg NF : M f, U s0 are isolated points.
Ž .
Ž
.
Ž .
ꢀ
Ž
.
4
We now utilize the results of the previous three lemmata to establish the
Proposition.
PROOF OF PROPOSITION: We assume without loss of generality that NF is an
open box with rational valued end-points. Similarly, we assume NC 'NC1 = NC 2
to be an open box in ޒnm, again with rational valued end-points. Consequently,
0
0
Ž
.
determines a
application of Lemmata 3᎐5 to all qualifying pairs f , U
␶
␶
␶
Ž
.
sequence of triples NF 0, NC0, Z , ␶s1, 2, . . . , such that:
⑀
nm
0
0
Ž .
Ž
.
␶
Ž
.
a
for each pair f , U gF =ޒ
with M f , U s0, there exists some
0
0
␶
Ž
.
␶ with f , U g NF = NC ;
␶
⑀
Ž .
Ž
.
b
for each ␶, NF is a relatively open subset of F ;
␶
c
for each ␶, NC is an open subset of ޒnm
for each ␶, Z is a measure zero subset of NC ;
;
Ž .
␶
␶
Ž .
d
␶
␶
␶
Ž .
Ž .
for each ␶ and Ug NC _Z , the elements of NF U are isolated points.
␶
e
Next define ZDϱ sD Z where the subscript D indicates that the set depends
␶
ϱ
Ž
.
on the normalization Ds D1, . . . , Dn . Observe that ZD has Lebesgue measure
zero in ޒnm. There are finitely many conceivable normalizations. Let Zϱ be the
union of the finitely many sets ZDϱ, i.e., Zϱ sDD ZDϱ. Then Zϱ has also
Lebesgue measure zero in ޒnm. Therefore, the set U'ޒnm _Zϱ has full
measure in ޒnm
.
Ž . o Ž
Now fix Ug U. By Lemma 2 i , E U :D NF U , and so by Lemma 5 the
.
Ž .
␶
␶
points in Eo U are isolated points in F .
Q.E.D.
⑀
Ž
.
PROOF OF THEOREM: Utilizing the same full measure set U constructed in the
proof of the Proposition, we claim that Eo
U
Ž
.
is finite for all Ug U. Fix any

1242
HANS HALLER AND ROGER LAGUNOFF
Ug U. Since Eo
U
Ž
.
is a closed subset of the compact set F, it is also compact.
It can therefore be covered by a family of open, nonempty, pairwise disjoint sets
Nf , fgEo
in which Nf lEo U s f . By compactness, there exists a finite
. Ž . ꢀ 4
U
Ž
subcovering. But since each Nf contains no points in Eo U other than f, this is
Ž
.
only possible if Eo U itself is finite. Since the choice of Ug U is arbitrary, the
claim is shown.
Ž
.
It remains to deal with MPE that are not completely mixed. Let T:S denote
an arbitrary support for a joint Markov profile. That is, T is of the form
TsD = Ti␻ where Ti␻ :Si␻ , each i and ␻. Let FT denote the compact
␻
i
subsimplex of F that contains all Markov profiles with support T:
T
ꢀ
Ž
.
4
F s fgF : sgS _T«f sN␻ s0 .
␻
Let ޒT denote the lower dimensional Euclidean space that obtains when S is
c
replaced by T. Then ޒnm sޒT =ޒT . For UT gޒT, consider the restricted
T Ž
.
²
:
oŽ
.
stochastic game ⌫ UT s ⍀, T, UT , QT , ␲ . Let E UT ;F denote the set of
joint profiles in FT whose restrictions to T are completely mixed MPE of the
T Ž
.
reduced game ⌫ UT . By the Proposition, there exists a generic subset UT of
ޒT such that for all UT g UT , Eo UT consists of locally isolated points in FT,
Ž
.
and so by the above compactness argument, it is a finite set. By Fubini’s
c
Theorem, UT =ޒT is a generic subset of ޒmn
.
T c
Ž .
Now for Ug UT =ޒ , let UT denote its restriction to T. Then fgE U has
oŽ
.
Ž .
support T if and only fgE UT . Consequently, ⌫ U has finitely many MPE
with support T. However, there are only finitely many supports. Hence, the
assertion of the Theorem holds.
Q.E.D.
5. LOWER DIMENSIONAL GAMES
In light of our result several issues should be addressed. First, while the
theorem covers generic ‘‘full dimensional’’ stochastic games in ޒnm, there are a
number of interesting stochastic games that have been studied in the literature
that are not covered by the result. A case in point is the Markov analysis of
two-player alternating move games examined in a series of papers by Maskin
Ž
.
Ž
.
and Tirole 1987, 1988a, 1988b . For instance, in the 1988a paper, each firm
sets capacity given the temporarily fixed capacity of rivals. See also Lagunoff and
Ž
.
Matsui 1997 .
The alternating move game has a straightforward stochastic game representa-
Ž .
tion: fix a stage game with action sets S1 and S2 , and with ui s denoting i’s
stage game payoff when profile sgS1 =S2 is chosen. At the beginning of odd
periods, player 1 has a chance to revise his action, whereas at the beginning of
even periods player 2 has a chance to revise her own action. Formally, let
ꢀ
4
⍀sS1 jS2. Further let Si␻ s ␻ , if ␻gSi, and Si␻ sSi, if ␻fSi. Q is given
Ž
.
Ž
.
by Q ␻ЈNs s1 in case ␻gSi, ␻ЈgSj, sj␻ s␻Ј, i/j; and by Q ␻ЈNs s0
␻
␻

STOCHASTIC GAMES
1243
FIGURE 1.
otherwise. The state dependent payoffs assume the form
Ž
.
.
ui ␻, sj␻
if ␻gSi ;
if ␻fSi .
Ž
.
s
U s
i
␻
½
Ž
ui si␻ , ␻
To see why the existing result does not apply in these games, consider an
alternating move game derived from the stage game in Figure 1.
Letting arrows denote the transition laws, Figure 2 exhibits the stochastic
game.
In this example, the state dependent payoff vectors reside in ޒ24. But in ޒ24,
the representation of repeated alternating moves in Figure 2 is clearly not a
‘‘generic’’ stochastic game; the alternating move game admits not more than 12
FIGURE 2.

1244
HANS HALLER AND ROGER LAGUNOFF
degrees of freedomᎏthe dimension of the original stage game. Clearly, in the
alternating move game, ‘‘genericity’’ should refer to the lower dimensional
payoffs of the original stage game. In a related paper, Haller and Lagunoff
Ž
.
1997 , we show that the set of MPE of the 2-player, alternating move game is
indeed generically finite with respect to stage game payoffs. For other types of
games and equilibrium concepts, some lower dimensional genericity results also
Ž
.
exist. Examples are Govindan and McLennan 1998b for extensive game forms,
and Park 1997 for signalling games.
Ž
.
Dept. of Economics, Virginia Polytechnic Institute and State Uni¨ersity, Blacks-
burg, VA 24061-0316, U.S.A.; haller@¨t.edu
and
Dept. of Economics, Georgetown Uni¨ersity, Washington, D.C. 20057-1036,
U.S.A.; lagunofr@gusun.georgetown.edu
Manuscript recei¨ed February, 1998; final re¨ision recei¨ed June, 1999.
APPENDIX
PROOF OF LEMMA 1: Let Ugޒnm and fgEo U . Then for each i, each ␻g⍀, and si gSi␻
,
Ž
.
Ž
.
.
Ѩ Vi fN␻
s0.
Ž
Ѩ fi si N␻
Ž .
f t N␻ s1
i i
Ý
ti
Ž .
Since the dynamic payoff functions Vi assumes the form 2 and the normalization D is chosen, this
system of equations translates into the myKn equations
Ž
.
Ž
.w
Ž
.
x
i
fi si N␻ fi di␻ N␻ ␲ и B si N␻ иU s0
␻
f
where si fDi and
Ž .
holds. Since fgEo U , we can drop the multipliers fi si N␻ fi di␻ N␻ and
Ž .
3
Ž
.
Ž
.
Ž
.
obtain 4 .
Q.E.D.
PROOF OF LEMMA 2: Let f k ªf satisfy f k gEo
U
and hence by Lemma 1 and 5 , M f , U s0
k
Ž
.
Ž .
Ž
.
Ž
.
Ž .
for each k. Since M is smooth, M f, U s0, which shows assertion i .
⑀
Ž
.
Ž
.
Fix a pair f, U gF . We begin by analyzing the derivative of M f, U with respect to U, given
Ž
.
Ž
.
by the Jacobian DU M f, U . This Jacobian is a mynK =m matrix that has the form:
JU11
f
0
иии
0
Ž
.
.
.
.
JU22
f
Ž .
0
.
.
.
Ž
.
DU M f, U s
.
.
.
.
0
иии
иии JUnn
f
Ž .
Here, JUii
Ž .
f
Ž
.
Ž .
denotes the mi yK =m block of partials
Ž
.
w
Ž
.
x
Ѩ ␲ и B si␻ N␻ иU
i
ѨMis f, U
␻
f
i
␻
6
s
,
si␻ gSi␻
.
blocks since the partials vanish wherever j/i. Given the
,
is1, . . . , n,
sЈgS.
Ž
.
Ž .
ѨU sЈ
i
ѨU sЈ
i
There are zeroes outside of the JUii
linearity of payoffs in U each entry in JUii
f
Ž
Ž
.
assumes the form
f
i
Ž
␻
.
ѨMis f, U
i
Ž .
7
Ž .
s␲ и B si␻ N␻ и1sЈ
f
␻
Ž
.
ѨU sЈ
i

STOCHASTIC GAMES
1245
where si␻ gSi␻ , ␻g⍀, and 1sЈ is the m=1 Dirac vector with a 1 in the sЈ componant and 0’s
elsewhere. To be clear, the rows of JUii
action profiles sgS. Note that, due to the linearity of dynamic payoffs in the vector U, vector U
Ž .
iiŽ
f
Ž
.
vary across actions si␻ while the columns vary across
.
f is expressed as a function of f only. We first show that for each
does not appear in 7 . Hence, JU
i, JUii
Observe that
f
Ž
.
has full row rank mi yK.
Ѩ
Ž .
8
Ž
.
w
x
B
si␻ N␻ s
Af
f
Ž
.
Ѩ fi si N␻
Ѩ
Ž
.w
xy1
Pf иQ
иPf
и
s
1y␦i Iy␦i
Ž
.
Ѩ fi si N␻
Ѩ Pf
Ž
.
w
xy1
w
xy1
s 1y␦i
Iy␦i Pf иQ
и
y Iy␦i Pf иQ
ž
Ž
.
Ѩ fi si N␻
Ѩ Pf
w
xy1
Pf иQ
и Pf
и
и y␦i
иQ и Iy␦i
Ž
.
/
Ѩ fi si N␻
Ѩ Pf
Ž
.w
xy1
s 1y␦i Iy␦i Pf иQ
и
Ž
.
Ѩ fi si N␻
xy1
ˆ
w
и
Iq␦i Qи Iy␦i Pf иQ
и Pf ,
11
ˆ
Ž
.
where I is the m=m identity matrix, and Ѩ PfrѨ fi si N␻ denotes the entry by entry derivative of
Ž
.
w
xy1
Pf with respect to fi si N␻ . Note that the inverse Iy␦i Pf иQ
exists because Pf иQ is a
stochastic matrix and so Iy␦i Pf иQ is a matrix with a strictly dominant diagonal. Combining our
iiŽ
.
in 7 with equation 8 , it follows that JU f equals
knowledge of the entries of JUii
f
Ž
.
Ž .
Ž .
Ѩ Pf
w
xy1
1
P
␲
и Iy␦i f иQ
и
␻
1
1
Ž
.
1
Ѩ fi si␻ N␻
.
.
.
Ž .
9
Ž
.
1y␦i
и
и
Ѩ Pf
w
xy1
␲ Kи Iy␦i Pf иQ
и
␻
K
m
K
i
Ž
.
Ѩ fi si␻ K N␻
w
xy1
ˆ
ˆ
Iq␦i Qи Iy␦i Pf иQ
и Pf иI.
Ž .
Ž .
7
To clarify the expression 9 , the entries in
are post-multiplied by unit vectors 1s␻ . But these
Ž .
Ž .
ˆ
entries form an identity matrix I that post-multiplies expression 9 .
We first examine the last block in expression 9 . Observe:
ϱ
xy1
t Ž
␦
i
.
ˆ
ˆ
Ž
.
w
10
Iq␦i Q Iy␦i Pf иQ
и P sIq␦ Qи
Pf иQ t и Pf
Ý
f
i
t
s0
ϱ
t
t Ž
.
ˆ
sIq
␦
Qи Pf
Ý
i
t
s1
ϱ
t
t Ž
␦ Qи Pf
i
.
s
Ý
t
s0
xy1
ˆ
w
s Iy␦i Qи Pf
,
11
ˆ
The hat on I is there to distinguish it from the K=K identity matrix I.

1246
HANS HALLER AND ROGER LAGUNOFF
xy1
w
xy1
ˆ
w
where, as with Iy␦i Pf иQ , the inverse Iy␦i Qи Pf
exists because Qи Pf is a stochastic
xy1
is
ˆ
ˆ
w
matrix and so Iy␦i Qи Pf is a matrix with a strictly dominant diagonal. Since Iy␦i Qи Pf
invertible it must have full rank of m.
Ž .
Ž
.
We now turn our attention to the first block in expression 9 . The matrix Ѩ PfrѨ fi si N␻ is a
Ž
.
.
Ž
.
K=m matrix placing zeroes in all entries where fi si N␻ does not appear, and drops fi si N␻ from
Ž
wherever it appears in the joint Markov profile f sN␻ . Note that by our earlier normalization,
X
Ž
.
Ž
.
X
i
Ž
.
fi si N␻ appears in the di␻ entry since fi di␻ N␻ s1yÝs / d fi si N␻ . Letting fyi denote the
i␻
1
1
Ž
.
joint Markov profile excluding i, and fixing ␻s␻ the matrix Ѩ PfrѨ fi si N␻ has the form:
l
1
l
1
Ž
.
Ž
.
0
0
иии
иии
0
иии fyi syi N␻ иии
0
иии
иии
0
иии yfi syi N␻ иии
0
иии
иии
0
0
0
0
.
.
.
.
.
.
.
.
.
.
.
.
0
иии
0
иии
0
иии
0
Ž .
where l symbolizes variation over all profiles s with ith component si. Clearly, by 3 , there is some
1
1
Ž
.
syi for which fyi syi N␻ /0. Hence, the preceding matrix has some nonzero entries in row ␻ at
l
l
Ž
.
Ž
.
Ž
.
1
1
1
1
1
locations si␻ , syi␻ and di␻ , syi␻ and zeroes elsewhere. Let ⌳i f; si␻ denote the 1=m row
w
xy1 1.x
w
Ž Ž .
1
P
P
vector ␲ и Iy␦i f иQ
и Ѩ frѨ fi si N␻ . Indeed, let ⌳i f; si␻ denote the corresponding 1=m
␻
Ž
.
row vector for an arbitrary action si␻ . The vector ⌳i f; si␻ has nonzero entries at certain actions
Ž
.
si␻ or di␻ is the ith component of s and zero entries elsewhere. Hence the mi yK =m matrix
␻
Ž
.
⌳
f
has mi yK independent columns which means that it has full rank mi yK.
i
Summarizing, we obtain JUii
f
Ž
.
as
xy1
11
JUii
f
s 1y␦i
⌳
f
ˆ
ˆ
иI.
Ž
.
Ž
.
Ž
.
Ž
. w
и Iy␦i Qи Pf
i
We now assert that the matrix JUii
standard fact about matrix algebra is used for any two matrices A and B whose product is defined:
f
defined in equation 11 has full row rank. To see why, a
Ž
.
Ž .
Ž
.
Ž
.
Ž .
Rank AB sRank A if B is square and nonsingular. Here we have that ⌳i f has rank of mi yK
xy1
Ž .
ˆ
ˆ
w
while Iy␦i Qи Pf
иI is square and nonsingular. Applying this fact to 11 establishes that
Ž
iiŽ ..
Ž
Rank JU
f
smi yK. Because of the diagonal box form, ѨMrѨU has full rank mynKsÝi mi y
.
Ž .
as asserted. This concludes the proof of assertion ii .
K
Q.E.D.
0
0
Ž
.
Ž
.
PROOF OF LEMMA 3: By Lemma 2, DU M f, U has full rank mynK at f , U . Therefore, we
1
2
Ž
.
can find a suitable partition C , C such that
Ž
.
ѨM f, U
0
0
Ž
.
.
has full rank mynK at f , U
2
ѨUC
1
NC
2
By the Implicit Function Theorem, there exist NF , NC
,
, and ⌿ with the desired properties.
Q.E.D.
Ž
.
1
N
1
1
NF
NC
Ž
2
PROOF OF LEMMA 4: For each UC
g
, the mapping ⌿ и, UC from
to
is smooth in f.
1
C
Ž
.
.
1
Hence, by Sard’s theorem, the set of critical values of ⌿ и, UC constitutes a set Z UC of Lebesgue
Ž .
measure zero in
NC
2
. This defines the set valued mapping Z и with the asserted properties. Q.E.D.
PROOF OF LEMMA 5: The proof of measurability of Z follows a lead in the proof of Sards’
Ž
.
NF = NC
1
ªNC
. Then Zs⌽ Y where the smooth mapping
1..
2
. Let Y:NF = NC
1
theorem in Milnor 1965, p. 18 . First, recall the mapping ⌿ :
Ž
.
NF = NC
1
denote the set of f-critical points in
NF = NC
ªNC = NC is defined by ⌽ f, UC
_Y is open relative to NF = NC
Ž
.
Ž
Ž
1
1
2
1
1
⌽ :
The set
NF = NC
s UC
, ⌿ f, UC
.
Ž
.
NF = NC
1
1
and thus Y is closed relative to NF = NC .
1
1
Observe
;ޒm =ޒmyŽmyn K . sޒmqn K. Let ޑmqn K denote the set of points in ޒmqn K
with rational coordinates and let ޑqq denote the set of strictly positive rational numbers. For a
point x, r gޑmq n K =ޑqq, let Kr x denote the closed ball in ޒ
with center x and radius r.
Ž .
N
.
C
mq n K
Ž
.
Ž .
For any ys f; UC
g
N
=
N
1
, there exists x, r gޑmq n K =ޑqq with ygKr x ;
N
=
1
Ž
.
Ž
.
1
F
C
F

STOCHASTIC GAMES
1247
1
Hence the closed set Y in NF = NC can be covered by a countable family of compact subsets Tk ,
ˆ
Ž . Ž .
NF = NC
, each of the form Tk sKr x lY. For each k, Tk '⌽ Kk is a compact
1
ks1, 2, . .. , of
ˆ
Ž
.
Ž
.
Ž
.
subset of Z and Zs⌽ Y s⌽ Dk Tk sDk ⌽ Tk sDk Tk. Hence Z is a countable union of
compact sets and therefore measurable.
Ž
.
1
Z
is measurable, application
Since each of the sections Z UC has Lebesgue measure zero and
of Fubini’s theorem yields that the graph Z has Lebesgue measure zero as asserted.
To demonstrate the second assertion, recall the definitions and properties of the open sets NF ,
Ž .
Ž
.
g NC
NC
=
2
, NC
1
, the mapping ⌿ : NF = NC
1
ªNC
2
, and the correspondence Z и . Let Us UC
1
, UC
is defined in the statement
.
. Then we claim that f is an isolated point
2
1
N
2
:ޒnm. Consider further fg NF satisfying fg NF
U
Ž
.
Ž .
where NF U
C
Ž
Z, i.e. U
2
fZ UC
1
of the Lemma. Suppose also that Uf
of NF U .
Observe that by Lemma 3, fg
C
Ž
.
Ž
.
Ž
.
Ž
1. Ž
.
N
U
implies UC
2
s⌿ f, UC
1
. Because of UC
2
fZ UC
,
f, UC
1
1
F
Ž
.
Ž
.
1
is an f-regular point of ⌿ , i.e. Ѩ⌿rѨ f has full rank at f, UC . Hence the derivative D⌿ и, UC has
full rank at f. Therefore, by the Inverse Function Theorem, there exist open neighborhoods NFU of f
NF and NCU
of UC
in NC
such that ⌿ * и, UC
.
, the restriction of ⌿ и, UC
1
to NFU, is a
.
Ž
.
Ž
2
2
2
1
in
diffeomorphism from NFU onto NCU
We conclude that
2
U
is the only point in NFU l NF U . For suppose gg NF l NF U . Then
Ž
.
Ž .
f
g, fg
NU and M g, U sM f, U where UC
2
g NCU
2
. Therefore UC
2
s⌿ * g, UC
1
s⌿ * f, UC
1
. Since
Q.E.D.
Ž
.
Ž
.
Ž
.
Ž
.
F
1
NFU
onto
NCU
2
, gsf as asserted.
Ž
.
⌿ * и, UC is a diffeomorphism from
REFERENCES
Ž
.
ABREU, D., AND A. RUBINSTEIN 1988 : ‘‘The Structure of Nash Equilibrium in Repeated Games
with Finite Automata,’’ Econometrica, 56, 1259᎐1281.
Ž
.
ANDERSON, R. M., AND W. R. ZAME 1997 : ‘‘Genericity with Infinitely Many Parameters,’’ mimeo,
University of California, Berkeley.
Ž
.
AUMANN, R. J. 1981 : ‘‘Survey of Repeated Games,’’ in Essays in Game Theory and Mathematical
Economics in Honor of Oskar Morgenstern, ed. by R. J. Aumann et al. Mannheim: Bibliographis-
ches Institut, 11᎐42.
Ž
.
BALASKO, Y. 1988 : Foundations of the Theory of General Equilibrium. Boston: Academic Press, Inc.
Ž
.
BENABOU, R. 1989 : ‘‘Optimal Price Dynamics and Speculation with a Storable Good,’’ Economet-
rica, 57, 41᎐80.
Ž
.
BERGEMANN, D., AND J. VALIMAKI 1996 : ‘‘Learning and Strategic Pricing,’’ Econometrica, 64,
1125᎐1149.
Ž
.
BLUME, L. E., AND W. R. ZAME 1994 : ‘‘The Algebraic Geometry of Perfect and Sequential
Equilibrium,’’ Econometrica, 62, 783᎐794.
Ž
.
CHO, I.-K., AND H. LI 1999 : ‘‘How Complex are Networks Playing Repeated Games?’’ Economic
Theory, 13, 93᎐123.
Ž
.
DEBREU, G. 1970 : ‘‘Economies with a Finite Number of Equilibria,’’ Econometrica, 38, 387᎐392.
Ž
.
DUTTA, P. 1995 : ‘‘A Folk Theorem for Stochastic Games,’’ Journal of Economic Theory, 66, 1᎐32.
Ž
.
ᎏᎏᎏ 1996 : ‘‘Efficient Markov Perfect Equilibria,’’ mimeo, Columbia University.
Ž
.
DUTTA, P., AND R. SUNDARAM 1992 : ‘‘Markovian Equilibrium in a Class of Stochastic Games:
Existence Theorems for Discounted and Undiscounted Models,’’ Economic Theory, 2, 197᎐214.
Ž
.
FRIEDMAN, J. W. 1986 : Game Theory with Applications to Economics. New York and Oxford: Oxford
University Press.
Ž
.
FUDENBERG, D., AND E. MASKIN 1986 : ‘‘The Folk Theorem in Repeated Games with Discounting
or with Incomplete Information,’’ Econometrica, 54, 533᎐556.
Ž
.
ᎏᎏᎏ 1995 : ‘‘Learning and Markov Behavior,’’ mimeo.
Ž
.
GILLES, R. P., H. H. HALLER, AND P. H. M. RUYS 1998 : ‘‘Semi-Core Equivalence,’’ Economic
Theory, 11, 101᎐127.
Ž
.
GOVINDAN, S., AND A. MCLENNAN 1998a : ‘‘On the Generic Finiteness of Equilibrium Outcome
Distributions in Game Forms,’’ forthcoming in Econometrica.

1248
HANS HALLER AND ROGER LAGUNOFF
Ž
.
ᎏᎏᎏ 1998b : ‘‘Generic Finiteness of Equilibrium Outcome Distributions for Two person Game
Forms with Zero Sum and Common Interest Utilities,’’ mimeo.
GRANDMONT, J.-M., A. P. KIRMAN, AND W. NEUEFEIND Ž
.
1974 : ‘‘A New Approach to the Uniqueness
of Equilibrium,’’ Re¨iew of Economic Studies, 41, 289᎐291.
Ž
.
HALLER, H., AND R. LAGUNOFF 1997 : ‘‘Markov Perfect Equilibria in Repeated Asynchronous
Choice Games,’’ VPI&SU WP E-97-05, and Economics Working Paper Archive ࠻ewp-
gamer9707006, http:rreconwpa.wustl.edureprintsrgamerpapersr9707r9707006.abs.
Ž
.
HARSANYI, J. C. 1973 : ‘‘The Oddness of Equilibrium Points: A New Proof,’’ International Journal of
Game Theory, 2, 235᎐250.
Ž
.
HILDENBRAND, W. 1974 : Core and Equilibria of a Large Economy. Princeton: Princeton University
Press.
KALAI, E., AND W. STANFORD Ž
.
1988 : ‘‘Finite Rationality and Interpersonal Complexity in Repeated
Games,’’ Econometrica, 56, 397᎐410.
KALAI, E., D. SAMET, AND W. STANFORD 1988 : ‘‘A Note on Reactive Equilibria in the Repeated
Ž
.
Prisoner’s Dilemma,’’ International Journal of Game Theory, 17, 176᎐186.
Ž
.
KEIDING, H. 1997 : ‘‘On the Maximal Number of Nash Equilibria in an n=n Bimatrix Game,’’
Games and Economic Beha¨ior, 21, 148᎐160.
Ž
.
KREPS, D., AND R. WILSON 1982 : ‘‘Sequential Equilibria,’’ Econometrica, 50, 863᎐894.
LEVHARI, D., AND L. MIRMAN Ž
.
1980 : ‘‘The Great Fish War: An Example Using a Dynamic Cournot
Nash Solution,’’ Bell Journal of Economics, 11, 322᎐334.
LAGUNOFF, R., AND A. MATSUI 1997 : ‘‘Asynchronous Choice in Repeated Coordination Games,’’
Ž
.
Econometrica, 65, 1467᎐1478.
Ž
.
MAS-COLELL, A. 1985 : The Theory of General Economic Equilibrium: A Differentiable Approach.
Cambridge: Cambridge University Press.
MCKELVEY, R. D., AND A. MCLENNAN 1997 : ‘‘The Maximal Number of Regular Totally Mixed
Ž
.
Nash Equilibria,’’ Journal of Economic Theory, 72, 411᎐425.
Ž
.
MCLENNAN, A. 1997 : ‘‘The Maximal Generic Number of Pure Nash Equilibria,’’ Journal of
Economic Theory, 72, 408᎐410.
Ž
.
MCLENNAN, A., AND I.-U. PARK 1999 : ‘‘Generic 4=4 Two Person Games Have at Most 15 Nash
Equilibria,’’ Games and Economic Beha¨ior, 26, 111᎐130.
MASKIN, E., AND J. TIROLE Ž1987 : ‘‘A Theory of Dynamic Oligopoly, Part III: Cournot Competition,’’
.
European Economic Re¨iew, 31, 947᎐968.
Ž
.
ᎏᎏᎏ 1988a : ‘‘A Theory of Dynamic Oligopoly, I: Overview and Quantity Competition with Large
Fixed Costs,’’ Econometrica, 56, 549᎐570.
Ž
.
ᎏᎏᎏ 1988b : ‘‘A Theory of Dynamic Oligopoly, II: Price Competition, Kinked Demand Curves
and Fixed Costs,’’ Econometrica, 56, 571᎐600.
Ž
.
ᎏᎏᎏ 1997 : ‘‘Markov Perfect Equilibrium, I: Observable Actions,’’ mimeo.
Ž
.
MILNOR, J. W. 1965 : Topology From the Differentiable Point of View. Charlottesville: The University
Press of Virginia.
Ž
.
PARK, I.-U. 1997 : ‘‘Generic Finiteness of Equilibrium Outcome Distributions for Sender-Receiver
Cheap-Talk Games,’’ Journal of Economic Theory, 76, 431᎐448.
Ž
.
QUINT, T., AND M. SHUBIK 1997 : ‘‘A Theorem on the Number of Nash Equilibria in a Bimatrix
Game,’’ International Journal of Game Theory, 26, 353᎐359.
Ž
.
ROSENMULLER, J. 1971 : ‘‘On a Generalization of the Lemke-Howson Algorithm to Non-cooper-
¨
ative N-Person Games,’’ SIAM Journal of Applied Mathematics, 21, 73᎐79.
Ž
.
SHAPLEY, L. 1953 : ‘‘Stochastic Games,’’ Proceedings of the National Academy of Sciences, 39,
1095᎐1100.
Ž
.
WILSON, R. 1971 : ‘‘Computing Equilibria in N-Person Games,’’ SIAM Journal of Applied Mathemat-
ics, 21, 80᎐87.