% This is the first line of the Latex file.
% Erase anything that comes before.
\documentstyle[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{LastRevised=Mon Jun 07 21:09:33 1999}
%TCIDATA{}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=article.cst}
\pagestyle{plain}
\renewcommand{\baselinestretch}{1.5}
\footnotesep.25in
\topmargin-0.5in
\textheight9in
\oddsidemargin0.1in
\evensidemargin0.1in
\textwidth6.2in
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{theorem}{Theorem}
\newtheorem{remark}{Remark}
\newtheorem{subclaim}{Subclaim}
\newcommand{\up}[1]{\overline{#1}}
\newcommand{\dn}[1]{\underline{#1}}
\newcommand{\F}{\mbox{\boldmath $F$}}
\newcommand{\bm}[1]{\mbox{\boldmath $#1$}}
\newcommand{\pder}[2]{\mbox{$\partial #1 \over \partial #2$}}
\newcommand{\pdermath}[2]{{\partial #1 \over \partial #2}}
\newcommand{\ep}{\epsilon}
\input{tcilatex}
\begin{document}
\begin{abstract}
We study a coordination game with randomly changing payoffs and small
frictions in changing actions. Using only backwards induction, we find that
players must coordinate on the risk dominant equilibrium. More precisely, a
continuum of fully rational players are randomly matched to play a symmetric
$2\times 2$ game. The payoff matrix changes according to a random walk.
Players observe these payoffs and the population distribution of actions as
they evolve. The game has frictions: opportunities to change strategies
arrive from independent random processes, so that the players are locked
into their actions for some time. As the frictions disappear, each player
ignores what the others are doing and switches at her first opportunity to
the risk dominant equilibrium. History dependence emerges in some cases when
frictions remain positive.
\vspace{.5in} \noindent {\bf J.E.L. No.:} C73. {\bf Field:} Game Theory.
\end{abstract}
\bigskip \setcounter{part}{0} \setcounter{section}{0} \setcounter{table}{0}
\begin{titlepage}
\mbox{} \\
\vspace{.5in}
\begin{center}
{\huge \bf Fast Equilibrium Selection} \\
\vspace{.15in}
{\huge \bf by Rational Players} \\
\vspace{.15in}
{\huge \bf Living in a Changing World} \\
\vspace{.8in}
{\large Krzysztof Burdzy,} \\
\vspace{.07in}
{\large David M. Frankel,} \\
\vspace{.07in}
{\large and Ady Pauzner}\footnote{Burdzy: Department of
Mathematics, University of Washington, Seattle, WA 98195, USA
(e-mail: burdzy@math.washington.edu). Frankel and Pauzner: Eitan
Berglas School of Economics, Tel Aviv University, Ramat Aviv, Tel
Aviv 69978, Israel (e-mail: dfrankel@econ.tau.ac.il,
ady@econ.tau.ac.il.). We are grateful for the helpful comments of
Elchanan Ben-Porath, Eddie Dekel, Drew Fudenberg, Philip Reny,
Ariel Rubenstein, 3 anonymous referees, and seminar participants at
Berkeley, Brown, Cornell, Harvard, Hebrew U., LSE, Northwestern,
Penn, Pittsburgh, Princeton, Stanford, Tel Aviv, the Technion, University
College London, UCSD, and
U.\ Washington. Burdzy was supported in part by NSF grant
9322689.} \\
\vspace{.5in}
{\large First version: July 1996.} \\
\vspace{.1in}
{\large This version: \today} \\
\end{center}
\end{titlepage}
\setcounter{page}{1}
\section{Introduction}
Games with multiple strict Nash equilibria present a major challenge for
game theory. \ Most equilibrium refinements do not select a unique
equilibrium in such games, and those that do are not unanimous in their
predictions. \ These difficulties have motivated an interest in explicitly
modelling dynamic processes by which play might evolve. \ By tracing a
gradual process in which players adjust their actions in response to past
play, one could hope to identify conditions that govern whether players will
eventually coordinate on an equilibrium and, if so, on which one.
Most dynamic models have focused on the evolution of play in a fixed world.
\ We assume instead that the world changes over time. \ In many of the
concrete examples of multiple equilibria, such as the choice between
technological standards or the economy's coordination on high or low
activity, the assumption that the world is changing is more realistic. The
state of technological knowledge, oil prices, and weather conditions are
only a few of many factors that change over time and affect the relative
payoffs from different choices.
The model has a continuum of fully rational players who are randomly matched
in pairs to play a symmetric 2x2 game with strategic complementarities. \
There are frictions: \ in each period, each player has only a small
probability of being able to change her action. \ The payoff matrix of the
game change every period, according to a random walk. \ We assume that, in
the (perhaps very distant) future, the cumulative changes in payoffs have
the potential to make either action strictly dominant.
We focus on the limit case in which the frictions become small, so that\
players' chances to change actions come more and more often.\footnote{%
In taking this limit as frictions become small, we also shrink the time
between periods, in order to retain the property that each player has only a
small chance to change actions in a given period.} \ The model becomes
dominance-solvable. \ {\em The equilibrium that is risk-dominant at any
given time must be played}. \ Moreover, convergence to that equilibrium
occurs as fast as the frictions allow.
This contrasts with the predictions of most dynamic random matching models
with players who are not fully rational (such as Kandori, Mailath and Rob
\cite{Kandori} and Foster and Young \cite{FosterYoung}). \ In such models,
when there is selection (e.g., as mutations go to zero), it takes a
relatively weak form: \ the selected equilibrium is played almost all of the
time in the ultra-long run. \ Our result also contrasts with selection in
other matching models with rational players, where equilibrium refinements
have typically been needed (e.g., Matsui and Matsuyama \cite{MatsuiMatsuyama}%
).
The result is driven by a contagion argument. \ Because of strategic
complementarities in the static game, players have an incentive to pick the
same action that their opponents are likely to choose. \ Hence, if a player
picks her action when the game's parameters are near a region where an
action (call it {\em a}) is strictly dominant, she has an incentive to pick
that action as well. \ This is because while she is locked into her action,
random payoff changes are likely to move the game into the region of strict
dominance, leading some of the player's opponents to pick {\em a}. \ So {\em %
a} must be played when sufficiently close to the dominance region. \ But
then {\em a} must be played when sufficiently close to this {\em adjacent}
region, and so on.
In the limit as frictions become small, this iterative process covers the
entire parameter space, giving unique predictions of what players will do in
any situation. \ This result depends crucially on the assumption that only a
small proportion of players change actions in each period, so that two
players matched at random will nearly always have chosen their actions
seeing different payoffs. \ Without this, there might be multiple equilibria
for some parameters, since a player's optimal action could depend on what
others plan to do at the same payoffs.
We also consider the case in which frictions remain large but payoff shocks
shrink to zero. \ If players are completely patient, the same result
obtains: \ the risk-dominant equilibrium is selected. \ With impatience,
players' strategies are still uniquely determined, but they now take into
account the distribution of actions in the population. \ In particular,
there can be {\em history dependence}: \ for a range of payoffs, if enough
players are initially playing a given action, the rest of the population
must follow.
This paper is related to papers by Carlsson and van Damme \cite{Carlsson}
and Matsui and Matsuyama \cite{MatsuiMatsuyama}. \ The former analyzes a
static game in which two players each receive a slightly noisy signal of the
game's payoffs. \ Iterative strict dominance leads to the selection of the
risk-dominant equilibrium through a contagion argument. \ Matsui and
Matsuyama study a dynamic model in which a large population of players are
randomly matched to play a static game. \ There are multiple rational
expectations equilibria; however, only the stationary state in which the
risk-dominant equilibrium is played possesses certain stability properties.
Our model is like that of Matsui and Matsuyama, but the payoffs in the
static game change randomly over time. \ This gives rise to a unique
outcome. \ Like Carlsson and van Damme, we prove this using a contagion
argument. \ However, our contagion mechanism is fundamentally different
since our model is dynamic and, as such, has state variables that have the
potential to generate history dependence. \ The key to our argument is
showing that the effect of the state variables is offset by players' future
behavior. \ The relations among these three papers are discussed in detail
in section \ref{sec:lit}.
Another related paper is Frankel and Pauzner \cite{FP}. \ They apply some of
the techniques of this paper to a continuous-time macroeconomic model in
which workers choose between two sectors, one of which has external
increasing returns and is subject to productivity shocks. \ The paper also
studies extensions to cases not analyzed in this paper. \ In particular, it
identifies conditions under which there is a unique equilibrium of the
dynamic game with nonvanishing frictions and shocks.
The rest of this paper is organized as follows. The model is presented in
section \ref{sec:themodel}. \ Section \ref{sec:solvingmodel} presents the
results and their intuitions, with proofs deferred to the appendix. \ In
section \ref{sec:lit} we review related literature. Section \ref
{sec:conclusion} concludes with a discussion of how the results depend on
the various features of the model.\medskip \bigskip
\section{The Model}
\label{sec:themodel}
\subsection{The Static Game}
We consider a symmetric static game with two actions, R and L. Payoffs
depend on a random parameter $B_{t}$ that changes over time: if a player
playing $a$ meets a player playing $a^{\prime }$ at time $t$, her payoff in
the static game is $u(a,a^{\prime },B_{t})$. Higher values of $B_{t}$ raise
the relative payoff to playing R while lower values make L more desirable.
More precisely, the {\em relative payoff to playing R} against the action $a$%
, $\Delta (a,B_{t})=u(R,a,B_{t})-u(L,a,B_{t})$, is strictly increasing and
continuously differentiable in $B_{t}.$
The game has strategic complementarities. That is, the relative payoff to
playing R is higher when one's opponent is playing R: $\Delta(R,B_t) >
\Delta(L,B_t)$.\footnote{%
This assumption also ensures that only $(R,R)$ and $(L,L)$ can ever be pure
Nash equilibria.} The following table gives an example of the time-$t$
payoff matrix.
\smallskip \vspace{0.1in}
\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|}
\hline
& {\bf R} & {\bf L} \\ \hline
{\bf R} & $3+B _t,3+B _t$ & $2+B _t,0$ \\ \hline
{\bf L} & $0,2+B _t$ & $4,4$ \\ \hline
\end{tabular}
\end{table}
An action is $p${\em -dominant} (Morris, Rob and Shin \cite{Morris}) if it
is a best response whenever the opponent is expected to play that action
with probability at least $p$. We say that an action is {\em exactly }$p$%
{\em -dominant} if a player is {\em indifferent} when her opponent puts a
weight of exactly $p$ on that action.\footnote{%
For the purpose of the definition, we allow $p$ to take values also outside
the interval $[0,1]$. For example, if R is exactly $-0.2$-dominant, it is
strictly dominant.} (Equivalently, $p$ is the smallest number for which the
action is $p${\em -dominant}.) \ Clearly, R is exactly $p$-dominant if and
only if L is exactly $(1-p)$-dominant.
This terminology permits a convenient rescaling. We denote by $B^{p}$ the
value of $B_{t}$ at which R is exactly $p$-dominant in the static game:
\begin{equation}
pu(R,R,B^{p})+(1-p)u(R,L,B^{p})\;\;=\;\;pu(L,R,B^{p})+(1-p)u(L,L,B^{p})
\label{eq:pdom}
\end{equation}
\noindent In the above game, for instance, when $B_{t}=0$, R is exactly $0.4$%
-dominant, so $0=B^{0.4}$. Note that $B^{p}$ is decreasing in $p$: if a
player's opponent plays R with higher probability, the player will be
willing to play R at {\em lower} values of $B_{t}$. An action is {\em %
risk-dominant} (Harsanyi and Selten \cite{HarsanyiSelten}) if it is a best
response when one's opponent is expected to play both actions with equal
probabilities. In our terminology, R is risk-dominant whenever $B_{t}\geq
B^{1/2}$ and L is whenever $B_{t}\leq B^{1/2}$.
\subsection{The Dynamic Context}
The game takes place in a sequence of periods at times $t=\tau ,2\tau ,3\tau
,\ldots $. There is a continuum of players of measure 1. In each period, a
subset of the players is randomly selected to revise their actions. Each
player has an independent chance $k\tau $ of receiving an action revision
opportunity.\footnote{%
The assumption that the action revision rate is independent of a player's
current action is for expositional simplicity only; see the discussion in
section \ref{sec:extensions}.} We assume no aggregate uncertainty;\footnote{%
Judd \cite{Judd} discusses some technical problems that arise with a
continuum of i.i.d.\ variables. Boylan \cite{Boylan} and Gilboa and Matsui
\cite{GilboaMatsui} offer possible solutions in the context of random
matching.} hence, in each period a measure $k\tau $ of players can change
actions. When $k$ is large, we say that frictions are small since a player's
expected lock-in time $1/k$ is short.
After actions are revised, the payoff parameter changes randomly (from $%
B_{t-\tau }$ to $B_{t}$). We assume that it follows a random walk: it jumps
by either $\mu \tau +\sigma \sqrt{\tau }$ or $\mu \tau -\sigma \sqrt{\tau }$%
, with equal probabilities. \ We use this formulation so that the real-time
mean and variance do not depend on the parameter $\tau $: \ for any times $%
t>t^{\prime }$ that are both integer multiples of $\tau $, the random
variable $B_{t}-B_{t^{\prime }}$ has mean $\mu (t-\hat{t})$ and variance $%
\sigma ^{2}(t-\hat{t})$. \ We refer to $\mu $ as the trend of $B$ and to $%
\sigma ^{2}$ as the variance.
Following the change in the payoff parameter, another subset of the players
is selected and randomly matched in pairs. Each pair collects the static
game payoffs corresponding to the actions they are currently locked into and
to the new value of the random parameter. Each player has an independent
chance $m\tau $ of being matched; the measure of matched players is thus $%
m\tau $.
Let $X_{t}$ be the proportion of players locked into R after actions are
revised in period $t$. We refer to $X_{t}$ as the ``state of play,'' $B_{t}$
as the ``state of the world,'' and the pair $(B_{t},X_{t})$ as the ``state
of the environment.'' The {\em public history} at time $t$ is the evolution
of the environment until period $t-\tau $, $(B_{v},X_{v})_{v=0,\tau ,\ldots
,t-\tau }$. \ (The initial values $(B_{0},X_{0})$ are given.) \ A player's
{\em private history} at time $t$ consists of her actions and the details of
her matches through period $t-\tau $. A player's information set at time $%
t=\tau ,2\tau ,\ldots $ is given by the public history, together with her
private history. {\em Strategies} are functions from the set of all
information sets to the set of mixtures over $\{R,L\}$ that indicate what a
player will do should she have an action revision opportunity.\footnote{%
A given strategy profile gives rise to a particular dynamical system. \ Let $%
h_{t}$ denote the vector of private histories at time $t$. \ Let $R(h_{t})$
denote the probability that a randomly selected player chooses R after the
history $h_{t}$. \ (If players use only pure strategies, $R(h_{t})$ is just
the proportion who choose R.) \ Then $X_{t}=X_{t-\tau }(1-k\tau )+k\tau
R(h_{t})$, while\ $B_{t}=B_{t-\tau }+\mu \tau \pm \sigma \sqrt{\tau }$ with
equal probabilities.}
When a player has a revision opportunity, she chooses the best action given
the probability distribution over paths $(B_{v})_{v=t,t+\tau ,\ldots }$ and
her beliefs about the path of play $(X_{v})_{v=t,t+\tau ,\ldots }$ that will
result from any given realization of $(B_{v})_{v=t,t+\tau ,\ldots }$. In any
period $v$, a player is matched with probability $m\tau $ to an opponent who
plays R with probability $X_{v}$ and L with probability $1-X_{v}$. If she is
locked into action $a\in \{R,L\}$, her expected payoff in the period is thus
$m\tau (X_{v}u(a,R,B_{v})+(1-X_{v})u(a,L,B_{v}))$. \ This payoff is relevant
to her time $t$ decision only if she has no revision opportunities between
times $t$ and $v$. \ This event has the probability $(1-k\tau )^{\frac{v-t}{%
\tau }}$. \ Hence, her relative payoff to choosing R in period $t$ is:%
\footnote{%
This holds because the player's action choice can have no influence over
which path $(X_{v})_{v=t,t+\tau ,\ldots }$ will occur, since\ any player's
action will be observed by only a countable number of other players.}
\begin{equation}
E\left[ \sum_{v=t,t+\tau ,\ldots }m\tau (1-k\tau )^{\frac{v-t}{\tau }%
}e^{-r(v-t)}\left( X_{v}\Delta (R,B_{v})+(1-X_{v})\Delta (L,B_{v})\right) %
\right] \label{eq:relpay}
\end{equation}
\noindent where $r\geq 0$ is the common discount rate. \ A player chooses R
if this relative payoff is positive and L if it is negative. Note that the
relative weight on period $v$, $(1-k\tau )^{\frac{v-t}{\tau }}e^{-r(v-t)}$,
depends on $k$. When revision opportunities are frequent ($k$ large),
players put most of the weight on payoffs that they receive very soon.
Nevertheless, we will see that more distant events remain important because
of backwards induction.
Finally, to give our iterative dominance argument a place to start, we
assume the existence of dominance regions. \ For $B_{t-\tau }$ large enough,
\begin{equation}
E\left[ \sum_{v=t,t+\tau ,\ldots }m\tau (1-k\tau )^{\frac{v-t}{\tau }%
}e^{-r(v-t)}\Delta (L,B_{v})dv\;\;|\;\;B_{t-\tau }\right] >0
\label{eq:domregn}
\end{equation}
\noindent which implies that R is strictly dominant. \ For $B_{t-\tau }$
small enough,
\begin{equation}
E\left[ \sum_{v=t,t+\tau ,\ldots }m\tau (1-k\tau )^{\frac{v-t}{\tau }%
}e^{-r(v-t)}\Delta (R,B_{v})dv\;\;|\;\;B_{t-\tau }\right] <0
\end{equation}
\noindent so that L is strictly dominant.
\section{Solving the Model}
\label{sec:solvingmodel}
Rather than looking for equilibria, we analyze the game using a more
primitive solution concept: the {\em iterative elimination of conditionally
dominated strategies} (see Fudenberg \& Tirole \cite[pp.\ 128 ff.]
{FudenbergTirole}). This is essentially the extension of backwards induction
to infinite horizon games. \ It is important to note that, in our model,
iterative conditional dominance is not a refinement of Nash equilibrium: \
every Nash equilibrium outcome of the dynamic game survives the iterative
process.\footnote{%
This is because players are small and anonymous, so that no unilateral
deviation can alter the probability distribution of reached information
sets. Therefore, given a Nash equilibrium, one can alter the strategies in
any way at unreached information sets and the resulting strategy profile
will remain a Nash equilibrium. In particular, one can adjust the strategies
at unreached information sets so that the overall equilibrium is subgame
perfect and thus survives iterated conditional dominance. \ To make this
argument precise, let $s$ be a Nash equilibrium strategy profile, and let $%
s(b,x)$ denote the play prescribed by $s$ if the initial state is $%
(B_{0},X_{0})=(b,x)$. We construct a subgame perfect equilibrium $\hat{s}$
that has the same distribution of equilibrium paths as $s$ as follows. If
the public history at time $t$ is consistent with $s$, players continue to
play according to $s$. \ (In particular, they ignore deviations by
individual opponents.) \ Otherwise, let $v\leq t$ be the earliest period
such that the public history at time $t$ is consistent with all players
having `reset their clocks to zero' at time $v$ and having played according
to $s(B_{v},X_{v})$ thereafter. Under the new profile $\hat{s}$, players
continue to conform to $s(B_{v},X_{v})$ after seeing the history $h_{t}$. \
Clearly, $\hat{s}$ induces the same equilibrium play as $s$ and is subgame
perfect. \ (We thank Philip Reny for suggesting this argument.)}
When carrying out the iterative procedure, we use a simple method to keep
track of the strategies that survive each successive round of elimination.
We consider the space $\Re \times \lbrack 0,1]$ of all conceivable values of
the current state $(B_{t},X_{t})$. When we discover that R must be played in
all surviving strategies after any public history $h_{t}$ that ends in the
state $(B_{t},X_{t})$, we tag the state with `R'.\footnote{%
Since the random walk is a discrete process, $\Re \times \lbrack 0,1]$ may
include some states that cannot be reached from a given $(B_{0},X_{0})$.
This does not present a problem; by tagging unreachable states, we do not
alter the set of surviving strategies.} \ We do the same for L.
Suppose a player receives an action revision opportunity at time $t$. If $%
B_{t}$ is large enough, R is strictly dominant, so the player will choose R
regardless of her beliefs over which strategies are used by the other
players. \label{pg:fn}Let $f^{0}$ be the boundary of the region where R is
strictly dominant (i.e., where (\ref{eq:domregn}) holds). This is depicted
in Figure \ref{pic:f0}. To the right of $f^{0}$, we know that the player
must choose R; on or to the left of $f^{0}$ we cannot yet say what the
player does. We tag the region to the right of $f^{0}$ with `R'. This
corresponds to eliminating all the strategies in which any player ever
chooses L in states $(B_{t},X_{t})$ that are to the right of $f^{0}$.
\begin{figure}[h]
\centering
\begin{picture}(400,85)
\put(10,0){\makebox(390,90)[br]{$B_t$}}
\put(40,15){\line(1,0){340}}
\put(40,65){\line(1,0){340}}
\put(0,10){\makebox(360,58)[tl]{$X_t=1$}}
\put(0,10){\makebox(360,58)[bl]{$X_t=0$}}
\put(60,35){\large L}
\put(101,65){\line(2,-5){20}}
\put(120,25){$g^0$}
\put(140,25){\ldots}
\thicklines
\put(162,65){\line(2,-5){20}}
\thinlines
\put(181,25){$G$}
\put(30,0){\makebox(190,65)[br]{$B^{1/2}$}}
\put(206,35){\large ?}
\thicklines
\put(224,65){\line(2,-5){20}}
\thinlines
\put(243,25){$F$}
\put(264,25){\ldots}
\put(275,65){\line(2,-5){20}}
\put(294,25){$f^1$}
\put(295,65){\line(2,-5){20}}
\put(314,25){$f^0$}
\put(350,35){\large R}
\end{picture}
\parbox{5in}{\caption{The iterative elimination procedure.
\label{pic:f0}}}
\end{figure}
In the second step we assume that a player believes that other players will
always choose R when they are strictly to the right of $f^{0}$. With this
belief, there is a new boundary, $f^{1}$, such that a player must choose R
when she is strictly to the right of $f^{1}$. $f^{1}$ must lie weakly to the
left of $f^{0}$, since knowing that other players will sometimes choose R
can only make R a more appealing action. In the next step we find $f^{2}$
and so on. Let $F$ be the limit of the sequence $f^{0},$ $f^{1},\ldots $.
Whenever $(B_{t},X_{t})$ is strictly to the right of $F$, any player who is
called to act must choose R. In a similar way, starting an iterative process
from the left side of the environment space where the action L is dominant,
we construct a sequence $g^{0},g^{1},...$, with limit $G$.
In all strategies that survive the iterative procedure, R is played to the
right of $F$ and L is played to the left of $G$. We cannot preclude the
possibility of a region (denoted by `?' in Figure \ref{pic:f0}) between the
two curves. Because it is not tagged with `R' or `L', we cannot say how
players will act in this region (if it exists). Different strategies might
partition this region into R and L in different ways, and their
prescriptions might even depend on aspects of the history that are not
reflected in the time-$t$ environment space.
\subsection{Results}
We have results for two limiting cases: \ small frictions and small noise. \
In both cases, we take the period length $\tau $ to zero first. \ This
ensures that the impact of the $\tau k$ players who revise actions
simultaneously in each period is negligible relative to the effects of the
random changes in $B$, which are of order $\sigma \sqrt{\tau }$.\footnote{%
The fact that the random changes in B are proportional to the square root of
the time interval is not a special feature of a random walk; it must hold
for any stochastic process with independent increments. \ See section \ref
{sec:freqjumps}.}
Theorem \ref{thm:kinfty} pertains to the case of small frictions: when $k$
tends to infinity. \ In the limit, $F$ and $G$ coincide with the vertical
line at $B^{1/2}$. This is depicted in Figure \ref{fig:kinfty}. Apart from a
vanishing range of values of $B_{t}$ around $B^{1/2}$, a player's choice
between L and R is uniquely determined by the state of the world $B_{t}$.
The player simply plays the action that would be a best response in the
static game against an opponent who puts equal weight on R and L.
\begin{figure}[h]
\centering
\begin{picture}(400,80)
\put(10,0){\makebox(390,90)[br]{$B_t$}}
\put(50,15){\line(1,0){330}}
\put(50,65){\line(1,0){330}}
\put(0,10){\makebox(360,58)[tl]{$X_t=1$}}
\put(0,10){\makebox(360,58)[bl]{$X_t=0$}}
\put(30,-5){\makebox(180,65)[br]{$B^{1/2}$}}
\put(193,65){\line(0,-1){55}}
\put(80,35){\large L}
\put(300,35){\large R}
\put(199,35){$F=G$}
\end{picture}
\parbox{5in}{\caption{Case of vanishing frictions ($k \rightarrow
\infty$). \label{fig:kinfty}}}
\end{figure}
\vspace{-0.2in}
\begin{theorem}
\label{thm:kinfty}Holding $\sigma $, $\mu $, and $r$ fixed, $%
\lim_{k\rightarrow \infty }\lim_{\tau \rightarrow 0}F=\lim_{k\rightarrow
\infty }\lim_{\tau \rightarrow 0}G=B^{1/2}$. \
\noindent Equivalently, for any $\varepsilon >0$, there is a $\underline{k}$
and a function $\underline{\tau }(\cdot )>0$ such that if $k>\underline{k}$
and $\tau <\underline{\tau }(k)$, then R must be played whenever $%
B_{t}>B^{1/2}+\varepsilon $ and L whenever $B_{t}0$, there is a $\overline{%
\sigma }>0$, $\overline{\mu }>0$, and a function $\underline{\tau }(\cdot
)>0 $, such that if $\sigma <\overline{\sigma }$, $\left| \mu \right| <%
\overline{\mu }$, and $\tau <\underline{\tau }(\sigma )$, then R must be
played whenever $B_{t}>B^{h(X_{t})}+\varepsilon $ and L whenever $%
B_{t}0$ that is less than the smaller
of the distances from $X_{t}$ to 0 and 1.\footnote{%
I.e., $\delta <\min \{X_{t},1-X_{t}\}$.} \ If $(B_{t},X_{t})$ is close to $Q$%
, the (random) {\em time of a }$\delta ${\em -bifurcation} is the last time $%
v\geq t$ at which the state is close to $Q$ before $X$ reaches a $\delta $%
-neighborhood of either zero or one.\footnote{%
If $X_{t}$ equals 0 or 1, $\delta $ can be any small positive number. \ The
bifurcation time is then the last time at which the state is close to $Q$
before $X$ comes within $\delta $ of 1 or 0, respectively.} \ We say that
the bifurcation is {\em upward} if, following the bifurcation, the state
remains to the right of $Q$ (so that $X$ grows towards 1). \ Otherwise it is
a {\em downward} bifurcation.
\begin{lemma}
\label{lem:1}Fix $\sigma $, $\mu $, and $\delta $. \ Let $Q:[0,1]\rightarrow
\Re $ be any strictly decreasing, continuously differentiable function. \
Consider the dynamical system depicted in Figure \ref{pic:dynamics}.%
\footnote{%
In this system, $B_{v}-B_{v-\tau }$ equals $\mu \tau \pm \sigma \sqrt{\tau }$
with equal probabilities. \ $X_{v}-X_{v-\tau }$ equals $-k\tau X_{v-\tau }$
if $B_{v-\tau }Q(X_{v-\tau })$. \ If $B_{v-\tau }=Q(X_{v-\tau })$, $X_{v}-X_{v-\tau }$
can take any value in $[-k\tau X_{v-\tau },k\tau (1-X_{v-\tau })]$.} \ For
any $\varepsilon >0$, there is a $\underline{k}$ and a function $\underline{%
\tau }(\cdot )>0$ such that if $k>\underline{k}$ and $\tau <\underline{\tau }%
(k)$, and if $(B_{t},X_{t})$ is `close to $Q$', then\vspace{-0.15in}
\begin{enumerate}
\item with probability at least $1-\varepsilon $, a $\delta $-bifurcation
will happen within time $\varepsilon /k$;\vspace{-0.15in}
\item the probability that the bifurcation will be upward is within $%
\varepsilon $ of $1-X_{t}$.\smallskip
\end{enumerate}
\end{lemma}
\begin{lemma}
\label{lem:2}Fix $k$. \ Let $Q:[0,1]\rightarrow \Re $ be any strictly
decreasing, continuously differentiable function. \ Consider the dynamical
system depicted in Figure \ref{pic:dynamics}. \ For any $\varepsilon >0$,
there are $\underline{\sigma }>0$, $\underline{\mu }>0$ and a function $%
\underline{\tau }(\cdot )>0$ such that if $\sigma <\underline{\sigma }$, $%
\left| \mu \right| <\underline{\mu }$, and $\tau <\underline{\tau }(\sigma )$%
, and if $(B_{t},X_{t})$ is `close to $Q$', then \vspace{-0.15in}
\begin{enumerate}
\item with probability at least $1-\varepsilon $, a $\delta $-bifurcation
will happen within time $\varepsilon /k$;\vspace{-0.15in}
\item the probability that the bifurcation will be upward is within $%
\varepsilon $ of $1-X_{t}$.
\end{enumerate}
\end{lemma}
\subsection{{\bf Intuitions for Lemmas 1 and }2}
We begin with the intuition for Lemma 2. \ Lemma \ref{lem:1} will follow by
a change of variables. \ It is convenient to linearize the dynamical system:
\ let $D_{t}=B_{t}-Q(X_{t})$, so that $\left| D_{t}\right| $ is the
horizontal distance between the state and $Q$. \ We can think of the process
$D$ as the sum of a random component (mean zero jumps of $\pm \sigma \sqrt{%
\tau }$) and two deterministic trends: \ positive jumps of approximately $%
\lambda _{R}\tau =k(1-X)|Q^{\prime }(X)|\tau $ when $D$ is positive and
negative jumps of about $-\lambda _{L}\tau =-kX|Q^{\prime }(X)|\tau $ when $D
$ is negative. \ (We can ignore the $\mu \tau $ term since $\mu $ goes to
zero while $k$ is fixed.) \ The trends $\lambda _{R}$ and $\lambda _{L}$ are
depicted in Figure \ref{fig:twotrends}.
\begin{figure}[h]
\centering
\begin{picture}(360,60)
\put(30,15){\line(1,0){310}}
\put(30,0){\makebox(320,60)[br]{$D_v$}}
\put(180,20){\line(0,-1){10}}
\put(10,0){\makebox(173,60)[br]{$0$}}
\put(130,27){$\lambda_L$}
\put(215,27){$\lambda_R$}
\put(170,30){\vector(-1,0){20}}
\put(190,30){\vector(1,0){20}}
\end{picture}
\parbox{5in}{\caption{Deterministic component of D.\label{fig:twotrends}}}
\end{figure}
An upward (downward) bifurcation of $(B,X)$ corresponds to a positive
(negative) bifurcation of $D$: \ a time after which $D$ remains positive
(negative) for some long period. \ The smaller is the $\delta $-neighborhood
that X must reach, the longer $D$ must remain positive (or negative) for a
bifurcation to occur. \ The reasoning behind Theorems 1 and 2 is that by
taking $\delta $ to be very small, we can ignore what happens in the distant
future after X reaches a $\delta $-neighborhood of zero or one. \ We will
approximate this case of small $\delta $ by considering the probabilities
that $D$ will stay positive or negative {\em forever}.
We first need to explain why the bifurcation occurs almost instantly. \
Intuitively, after spending any time on one side of 0 the deterministic
trend will take $D$ a positive distance from 0. \ But as the random jumps
shrink, so does the chance that a reverse movement in $D$ will take us back
to 0. This means that a increasingly short stay on one side of 0 suffices to
make bifurcation very likely. \ Hence, the bifurcation must happen quickly.
To compute the odds of a positive vs. a negative bifurcation, we use several
approximations. \ First, since $X$ changes little before the bifurcation,
the trends $\lambda _{R}$ and $\lambda _{L}$ can be treated as a fixed
constant ($k|Q^{\prime }(X_{t})|$) times the constants $1-X_{t}$ and $X_{t}$%
, respectively. \ Moreover, since $\tau $ is taken to zero before the other
limits, we can treat $D$ as moving in a continuous way. \ With this last
approximation, $D$ can be said to bifurcate at time $v$ if $D_{v}=0$ and $%
D_{s}\neq 0$ for all $s>v$.
Suppose that $D_{t}=0$. Let $P^{\uparrow }$ be the probability of a positive
bifurcation of $D$ occurring at any time after $t$. Let $P^{\downarrow }$ be
the probability of a negative bifurcation. For any constant $\gamma >0$, let
$P_{\gamma }^{\uparrow }$ and $P_{\gamma }^{\downarrow }$, respectively, be
the probabilities of a positive and negative bifurcation occurring at some
time $v\in \lbrack t,t+\gamma ]$. \ We claim that, the ratio $P^{\uparrow
}/P^{\downarrow }$ of bifurcation probabilities equals the ratio $P_{\gamma
}^{\uparrow }/P_{\gamma }^{\downarrow }$. Why? Let $P_{\gamma }=P_{\gamma
}^{\uparrow }+P_{\gamma }^{\downarrow }$. If there is no bifurcation in the
interval $[t,t+\gamma ]$, then $D$ must equal $0$ at some time $v>t+\gamma $%
. As of time $v$, the probability of an upwards bifurcation is once again $%
P^{\uparrow }$. Thus, $P^{\uparrow }=P_{\gamma }^{\uparrow }+(1-P_{\gamma
})P^{\uparrow }$. This shows that $P^{\uparrow }=P_{\gamma }^{\uparrow
}/P_{\gamma }$. Likewise, $P^{\downarrow }=P_{\gamma }^{\downarrow
}/P_{\gamma }$. Therefore, $P^{\uparrow }/P^{\downarrow }=P_{\gamma
}^{\uparrow }/P_{\gamma }^{\downarrow }$.
Since this equality holds for all $\gamma $, it also holds as $\gamma $ goes
to zero. This limit turns out to be easy to compute. For an upwards
bifurcation to occur in $[t,t+\gamma ]$, two things must happen. First, $D$
must be positive at time $t+\gamma $. Second, $D$ must remain positive
forever after. Where is $D$ at $t+\gamma $? Since $D_{t}=0$, the value of $D$
at time $t+\gamma $ is dominated by the noise in $B$. This is because the
standard deviation of $B_{t+\gamma }-B_{t}$ is proportional to $\sqrt{\gamma
}$, while the linear trends $\lambda _{R}$ and $\lambda _{L}$ (coming from
changes in $X$) produce a change of order only $\gamma $. For small $\gamma $%
, $\sqrt{\gamma }/\gamma $ is arbitrarily large. So for small $\gamma $ we
can treat the distribution $\Psi _{\gamma }$ of $D_{t+\gamma }$ as
approximately symmetric around zero. (In particular, it is approximately
normal with mean $0$ and standard deviation $\sigma \sqrt{\gamma }$).%
\footnote{%
This property of Brownian motions, that the noise swamps any linear trend
over short intervals, is an implication of independent increments. See note
\ref{fn:noiseswampstrend} in section \ref{sec:freqjumps}.}
Given that $D$ is positive at $t+\gamma $, what is the probability that it
remains so forever after? If $D_{t+\gamma }=z$ and $z$ is small, this
probability is approximately proportional to the distance $z$ times the
trend $\lambda _{R}$. This relies only on the fact that a random walk has
i.i.d. increments. \ To see why, let $p$ be this probability, and consider
what happens if $D_{t+\gamma }$ starts twice as far away, at $2z$. What is
the probability that $D$ never hits zero? \ It is the probability $p$ that $%
D $ never hits $z$, plus the probability $1-p$ that $D$ hits $z$ times the
probability $p$ that, from $z$, $D$ never reaches zero. This is $p+(1-p)p$,
which is approximately $2p$ since, for small $z$, $1-p$ is close to one.
This shows that the probability that $D$ never hits zero if it starts at $z$
is approximately proportional to $z$ for small $z$.
Why is this probability also approximately proportional to $\lambda _{R}$? \
Let us multiply the time scale by 4 and the space scale by 2, giving a new
process $\widehat{D}_{v}=2D_{v/4}$. \ As long as $D$ and $\widehat{D}$
remain positive, both have constant trends, so they have the same variance:
\[
\mbox{Var}(\widehat{D}_{w}-\widehat{D}_{v})=\mbox{Var}(2D_{w/4}-2D_{v/4})=4%
\sigma ^{2}\left( w/4-v/4\right) =\sigma ^{2}(w-v)=\mbox{Var}(D_{w}-D_{v})
\]
\noindent The new process $\widehat{D}$ begins at $2z$. Since the time scale
is stretched by twice the space scale, the trend of $\widehat{D}$ is $%
\lambda _{R}/2$, half the trend of $D$. But a change in the scaling cannot
affect the probability of never hitting zero, which must still be $p$ after
doubling the initial distance $z$ and halving the trend $\lambda _{R}$.
Since the probability that $D$ never hits zero is linear in $z$, it must
also be linear in $\lambda _{R}$.
Hence, if $D_{t+\gamma }=z$ and $z$ is small, the probability that $D_{v}$
remains positive for all $v>t+\gamma $ is proportional to $z\lambda _{R}$.
Since most of the weight of the c.d.f. $\Psi _{\gamma }$ of $z$ is close to
zero, the probability $P_{\gamma }^{\uparrow }$ is approximately
proportional to
\[
\int_{z=0}^{\infty }z\lambda _{R}d\Psi _{\gamma }(z)\;=\;\lambda
_{R}\int_{z=0}^{\infty }zd\Psi _{\gamma }(z)
\]
\noindent The probability $P_{\gamma }^{\downarrow }$ that $D$ has a
negative bifurcation in $[t,t+\gamma ]$ is approximately proportional to
\[
\int_{z=-\infty }^{0}|z|\lambda _{L}d\Psi _{\gamma }(z)\;\approx
\;\int_{z=0}^{\infty }z\lambda _{L}d\Psi _{\gamma }(z)\;=\;\lambda
_{L}\int_{z=0}^{\infty }zd\Psi _{\gamma }(z)
\]
\noindent because $\Psi _{\gamma }$ is approximately symmetric. Therefore,
the ratio $P_{\gamma }^{\uparrow }/P_{\gamma }^{\downarrow }$ equals $%
\lambda _{R}/\lambda _{L}$ as $\gamma $ goes to zero. \ This ratio is
approximately $(1-X_{t})/X_{t}$. This explains why the relative probability
of bifurcating up vs.\ down converges to $(1-X_{t})/X_{t}$ as $\tau $ and
then $\sigma $ and $\mu $ shrink to zero.
Lemma 1 follows from Lemma 2 by a change of variables. \ We stretch the time
scale by replacing $B_{t}$ with $\hat{B}_{t}=B_{t/k}$ and $X_{t}$ with $\hat{%
X}_{t}=X_{t/k}$. \ In the new time coordinates, the rate of change of $\hat{X%
}$ is fixed while the variance $\sigma /k$ and trend $\mu /k$ of $\hat{B}$
shrink to zero, so Lemma 2 can be applied.
\section{Relation to the Literature}
\label{sec:lit}This paper is related to two research programs. The first
studies how connections among ``nearby'' games can determine how rational
players will behave in a given game. \ The second is the literature on
dynamic population models.\smallskip
\noindent {\bf Connections Among Nearby Games}
Our framework is closely related to that of Carlsson and van Damme \cite
{Carlsson} (henceforth, CvD).\footnote{%
See also Morris, Rob and Shin \cite{Morris}.} That paper studies a one-shot $%
2\times 2$ game whose payoffs are not common knowledge. Rather, each player
receives a slightly noisy signal of the true payoffs. The space of possible
payoffs includes regions where each action is strictly dominant. \ Iterative
strict dominance gives rise to a contagion effect that starts from these
regions and determines how players will play throughout the space of
possible payoffs. For small enough noise in the signals, the players must
play the risk-dominant equilibrium of the true game.
There is an analogy between CvD's game and our own. \ Since CvD's game has
incomplete information, a player must consider what opponents of different
types will do. \ (In CvD, a player's type is her signal.) \ The correlation
between the two players' signals leads players to focus on opponents whose
types are close to their own. \ This (together with the dominance regions)
is what causes the contagion effect. \ In our model, payoffs change
randomly. \ Thus, a player who wishes to predict what players will choose
after her must consider a distribution of possible ``types'', each seeing
different payoffs. \ The persistence of the random walk plays a role similar
to that of correlation in CvD: \ most of these players will choose actions
at states that are close to that at which the given player chooses her
action.
However, there is a fundamental difference. \ In our model, when a player
chooses her action, half of her future opponents have already chosen theirs.
\ Any reasoning she does about what different types of players must do can
relate only to the half who {\em haven't} chosen their actions yet. \ This
contrasts with CvD, where a player's conclusions from tracing other players'
decision problems apply to {\em all} of her potential opponents.
Indeed, trying to apply CvD's technique directly to our model (i.e., doing
iterative dominance on the payoff parameter alone) establishes only a weaker
result: \ that an action must be played if it is better than $1/4$-dominant.
No prediction can be reached if $B_{t}$ is greater than $B^{3/4}$ but less
than $B^{1/4}$. \ Formally, doing iterative dominance on $B_{t}$ alone is
equivalent to iterating with vertical lines. \ Suppose that such an
iterative process starting from the region where R is strictly dominant ends
at $B_{t}=b$. \ Consider a player who picks actions at $X_{t}=0$ with $B_{t}$
slightly greater than $b$. \ We know that she is willing to play R. \ With
small frictions, she cares only about the very near future, when the random
walk is equally likely to be above or below $b$. Therefore, she expects that
half of the new players will play R and half L. \ Since all old players are
playing L, she expects just quarter of her opponents to play R. \ Hence, $%
B_{t}$ must be $B^{1/4}$. \ Similarly, iterating from the left also stops
short of $B^{1/2}$, at $B^{3/4}$.
The key to our stronger result is observing that the new and old players
offset each other. \ The reason is that once the population starts shifting
towards a given action, the speed at which this occurs is proportional to
the size of the population currently playing the {\em other} action. \ On
the curve $F$, these speeds govern the bifurcation probabilities.\footnote{%
This follows from our assumption that payoffs change frequently (i.e., that $%
\tau $ tends to zero faster than anything else). \ This point is discussed
further in section \ref{sec:freqjumps}.} \ Hence, when the proportion $X_{t}$
of old players playing R is low, the chance $1-X_{t}$ that the new players
will play R is high. \ When the payoff weight on the two groups is equal
(i.e., when frictions are small or players are patient), this leads to a
strong selection result: \ $X_{t}$ plays no role at all in a player's
decision. \ When old players receive more weight (i.e., when frictions are
large and players are impatient), there is history dependence since the new
players only partially offset the old.
To see more clearly the difference between our model and a static model of
incomplete information game, it is instructive to look at the model of
Matsui \cite{Matsui}. \ His also has a payoff parameter that changes
randomly in each period. \ There is a sequence of players, each of whom
chooses one action. \ Unlike in our model, each player's payoff comes only
from her interaction with the player who chooses {\em after} her. \ Matsui
shows that his model is isomorphic to a static incomplete information game
like that of CvD. \ Such an isomorphism cannot be found with our model,
since the actions of past players (captured by the state variable $X_{t}$)
are payoff-relevant. \ The lack of such an isomorphism is most obvious in
the case of small noise and large frictions, where we find history
dependence.\smallskip
\noindent {\bf Dynamic Population Models}
There is an extensive literature that studies models in which players in a
large population are randomly matched, from time to time, to play some
normal-form game. \ With less than fully rational players and mutations,
these models can yield equilibrium selection in the form of a long-run
ergodic distribution with most of its weight on a given equilibrium.%
\footnote{%
Examples include Foster and Young \cite{FosterYoung}, Fudenberg and Harris
\cite{FudenbergHarris}, Kandori, Mailath and Rob \cite{Kandori}, and Young
\cite{Young}. \ Models of bounded rationality with {\em local interaction}
yield faster convergence; see, for example, Ellison \cite{Ellison} and Blume
\cite{Blume93}.}
Our model, which assumes fully rational players, is most related to that of
Matsui and Matsuyama \cite{MatsuiMatsuyama} (henceforth, MM). \ The
essential difference between the two models is that payoffs in MM are fixed.
\ In our model this corresponds to taking $B_{t}$ as a constant parameter. \
Figure \ref{pic:MM} illustrates what happens with constant $B_{t}$, in the
case of small frictions (which is the case on which MM focus).\bigskip
\begin{figure}[h]
\centering
\begin{picture}(320,90)
\put(8,2){\makebox(306,144)[br]{$B_t$}}
\put(32,14){\line(1,0){262}}
\put(32,94){\line(1,0){262}}
\put(-5,16){\makebox(288,83)[tl]{$X_t=1$}}
\put(-5,10){\makebox(288,83)[bl]{$X_t=0$}}
\put(168,14){\dashbox{2}(0,80)}
\thicklines
\put(120,50){\large $\ell _1$}
\put(104,94){\line(4,-5){64}}
\put(212,50){\large $\ell _2$}
\put(168,94){\line(4,-5){64}}
\thinlines
\put(24,2){\makebox(86,104)[br]{$B^1$}}
\put(24,2){\makebox(214,104)[br]{$B^0$}}
\put(24,2){\makebox(152,104)[br]{$B^{1/2}$}}
\put(72,66){\vector(0,-1){24}}
\put(164,54){\vector(0,1){12}}
\put(164,54){\vector(0,-1){12}}
\put(256,42){\vector(0,1){24}}
\end{picture}
\parbox{5in}{\caption{Case of constant $B_t$, corresponding to
MM.\label{pic:MM}}}
\end{figure}
\noindent To the left of $\ell _{1}$, only L can be selected in any rational
expectations equilibrium. \ R must be chosen to the right of $\ell _{2}$.%
\footnote{%
These curves correspond roughly to $g^{0}$ and $f^{0}$ in Figure \ref{pic:f0}%
. \ In the limit as frictions vanish, this correspondence is exact.} \
Between the curves, there are multiple equilibria, including one in which
players always select R and another in which they always choose L. \
However, MM find support for the prediction that the risk-dominant
equilibrium of the static game is more likely to be played, since it is
`globally accessible' and `uniquely absorbing.' Suppose, e.g., that $%
B_{0}>B^{1/2}$. \ Since the initial state must be to the right of $\ell _{1}$%
, it is an equilibrium for all players to choose R for any initial value $%
X_{0}$: \ R is `globally accessible.' \ Moreover, if $X_{0}$ is large
enough, the initial state lies above $\ell _{2}$, so all players {\em must}
choose R. \ Hence, R is also `uniquely absorbing.'
Our model shows that with stochastic payoff changes, the area between $\ell
_{1}$ and $\ell _{2}$ splits into two regions. \ The part to the left of $%
B^{1/2}$ joins the area where players must choose L, while the part to the
right of $B^{1/2}$ joins the area where they must choose R. \ Moreover, the
changes in payoffs make the model dominance-solvable.
\section{Concluding Remarks}
\label{sec:conclusion}
\subsection{The Assumption of Frequent Jumps in the Random Walk}
\label{sec:freqjumps}For all of our results we take the time $\tau $ between
jumps of the random walk to be small given the other key parameters of the
model, $k$ and $\sigma $. \ Without this, there could be regions with
multiple equilibria. \ To see why, consider the group of players who choose
actions simultaneously in a given period. \ This group constitutes a
proportion $k\tau $ of the players. \ If they all choose the action $a$,
their relative payoff to playing $a$ is increased, and this might justify
their choice.
The group's choice affects their relative payoff in two ways. \ First,
members of the group may play each other. \ To make this effect negligible,
we take $\tau $ small given $k$, so that $k\tau $ is small. \ An analogous
issue emerges in the static incomplete information game of CvD \cite
{Carlsson}. \ There, multiple equilibria might arise if the probability that
the two players see the same signal of the true payoff\ parameter is large.
\ CvD make this probability zero by assuming a continuous signal
distribution.
A second consideration, which has no analogue in CvD's model, comes from the
dynamic structure of our model: \ if the $k\tau $ others pick R, $X$ will
rise, possibly moving the state into a region where yet more players will
pick R. \ Taking $\tau $ small given $k$ and $\sigma $ eliminates this
possibility by ensuring that the effect of the players' simultaneous action
choices, which is of order $k\tau $, is swamped by the random jumps in $B$,
which are of size $\sigma \sqrt{\tau }$.\footnote{\label{fn:noiseswampstrend}%
The property that the noise $\sigma \sqrt{\tau }$ is proportional to the
square root of the time $\tau $ between jumps is a consequence of the random
walk having independent increments. \ The change in $B$ over a given
interval of length, say, 1, is the sum of $1/\tau $ independent jumps. The
only way this sum can retain a nontrivial variance as $\tau $ shrinks is if
the size of each jump is of order $\sqrt{\tau }$.}
\subsection{Extensions}
\label{sec:extensions}
\noindent {\bf The Stochastic Process}
We assume that payoffs change according to a random walk. \ However, our
results remain valid if payoffs follow any discrete process with
independent, stationary increments.\footnote{%
Stationarity means that the distribution of increments over a given time
interval can depend only on its length.}\ For example, the jump in each
period might be normally distributed. \ Or the waiting times between jumps
might themselves be random. \ As $\tau $ shrinks, all such processes behave
in essentially the same way and share the properties of a random walk that
we use. \ Our results also hold when $\tau $ {\em equals} zero, so that $B$
is a Brownian motion and time is continuous (see Burdzy, Frankel, and
Pauzner \cite{BFP2}). \ Hence, there is continuity at the limit.
The assumption of independent, stationary increments can also be weakened. $%
B $ may be any strictly increasing, continuously differentiable function of
a random walk, as long as it can reach values at which either action is
strictly dominant.\footnote{%
This is because any such transformation of $B$ is equivalent to a change in
the utility function: instead of $u(a,a^{\prime },\tilde{B}_{t})$ where $%
\tilde{B}_{t}=g(B_{t})$, we use the utility function $\tilde{u}(a,a^{\prime
},B_{t})=u(a,a^{\prime },g(B_{t}))$.} \ This lets $B$ represent bounded
processes such as prices or temperatures. \ Our results also hold if the
trend parameter, rather than being constant, is any bounded Lipschitz
function of $t$ and $B_{t}$. \ For instance, the trend may have a seasonal
component or be mean-reverting. \ Our results may be of greater interest
with mean-reverting processes. \ This is because a random walk tends to
wander away from $B^{1/2}$ to regions where one action is strictly dominant;
a mean reverting process with mean close to $B^{1/2}$ spends a positive
fraction of its time in the area where the static game has multiple
equilibria.
In the case we study (small $\tau $), the stochastic process changes almost
continuously over time. \ For some applications, it may be more natural to
assume that in addition to its small frequent jumps, $B$ also has large
infrequent jumps at random times. Theorem 1 holds for any such process,
since during a player's shrinking lock-in period the chance of a large jump
becomes very small. \ For Theorem 2, the noise can become small in two ways:
\ the large jumps may become less and less frequent, or they may retain
their frequency but become smaller and smaller. Theorem 2 holds in both
cases. The reason is that the bifurcation occurs earlier and earlier, so
that the probability that a random jump will precede the bifurcation goes to
zero; hence, infrequent jumps have almost no effect on the dynamics of $X$%
.\smallskip
\noindent {\bf Dominance Regions and Monotonicity}
We assume that extreme values of $B_{t}$ make either action strictly
dominant and that the relative payoff to R against either action is strictly
increasing in $B_{t}$.\ \ The first assumption gives the contagion argument
a place to start. \ The second guarantees that the iterations starting from
the two dominance regions will meet.
If these assumptions do not hold, the following weaker version of Theorem
\ref{thm:kinfty} can still be proved. Assume only that the game has
strategic complementarities ($\Delta (R,B_{t})>\Delta (L,B_{t})$) and that $%
\Delta (a,B_{t})$ is continuously differentiable in $B_{t}$. Let $b$ be any
value of $B_{t}$ at which R is strictly dominant. Let $(\underline{b},%
\overline{b})$ be the largest (potentially infinite) interval that includes $%
b$, such that R is risk-dominant (and L is not) throughout the interval. In
the limit as $\tau \rightarrow 0$ and then $k\rightarrow \infty $, R must be
played at all points in this interval. An analogous result can be proved for
L.\smallskip
\noindent {\bf Different Revision Rates}
Our model assumes that a player's rate of action revision opportunities is
independent of the action she is currently playing. \ With differing
revision rates, players still choose the risk-dominant action in the case of
small frictions (Theorem \ref{thm:kinfty}). \ To see why, let $k_{a}$ be the
revision rate of a player currently locked into action $a$. We compute the
relative payoff of player `A' (p. \pageref{pg:A}) to playing R vs.\ L by
first conditioning on bifurcations in each direction. \ If A knew that the
bifurcation would be upward, she would play R from now on. \ By picking L
rather than R, she loses utility only until her next revision opportunity,
when she will switch to R. \ These opportunities arrive at rate $k_{L}$,
which equals the rate at which other players change actions (since only L
players switch). \ Hence, her expected numbers of new and old opponents
while she is locked into L are still equal.\footnote{%
More precisely, since R players never change their actions in an upward
bifurcation, their revision rate is irrelevant. \ So for the purposes of
computation, we can assume that the R players also have the revision rate $%
k_{L}$ and hence that the expected numbers of new and old opponents are
equal.} $\ X_{t}$ of the old players and {\em all} of the new players play
R, so the expected number of R players is approximately $1/2+\ X_{t}/2$. \
The expected lock-in time is $1/k_{L}$. \ Hence, her relative payoff from
playing R is $\frac{1}{k_{L}}\left[ \frac{1+X_{t}}{2}\Delta (R,B_{t})+\frac{%
1-X_{t}}{2}\Delta (L,B_{t})\right] $. \ Similarly, conditional on a downward
bifurcation, the relative payoff from R is $\frac{1}{k_{R}}\left[ \frac{X_{t}%
}{2}\Delta (R,B_{t})+\left( \frac{2-X_{t}}{2}\right) \Delta (L,B_{t})\right]
$. \ The probabilities of upward and downward bifurcations are proportional
to the speeds at which $X$ moves up and down, $k_{L}(1-X_{t})$ and $%
k_{R}X_{t}$. \ Therefore, the (unconditional) relative payoff to choosing R
is proportional to
\begin{eqnarray*}
&&k_{L}(1-X_{t})\frac{1}{k_{L}}\left[ \frac{1+X_{t}}{2}\Delta (R,B_{t})+%
\frac{1-X_{t}}{2}\Delta (L,B_{t})\right] \\
&&+k_{R}X_{t}\frac{1}{k_{R}}\left[ \frac{X_{t}}{2}\Delta (R,B_{t})+\left(
\frac{2-X_{t}}{2}\right) \Delta (L,B_{t})\right] \\
&=&\frac{1}{2}\left[ \Delta (R,B_{t})+\Delta (L,B_{t})\right]
\end{eqnarray*}
\vspace{-0.1in}\noindent Thus, the division line is again vertical at $%
B^{1/2}$.
In the case of small noise, the weight on old players depends on the
revision rate corresponding to each direction of bifurcation. \ Hence, the
revision rates do not cancel out in the computation. \ The result is
qualitatively the same as in Theorem \ref{thm:sigmazero}, but the division
line now depends on the two revision rates, $k_{R}$ and $k_{L}$.\smallskip
\noindent {\bf Homogeneity of Players}
We assume all players have the same payoff function. \ Suppose instead that
the payoff of player $i\in \lbrack 0,1]$ is $u(a,a^{\prime },B_{t}+\theta
_{i})$. Assume that most of the players have taste parameters $\theta _{i}$
in the range $[\theta ,\theta ^{\prime }]$: no more than $\varepsilon $ are
below $\theta $, while no more than $\varepsilon ^{\prime }$ are above $%
\theta ^{\prime }$. A modification of our argument shows that as frictions
vanish, at least $1-\varepsilon $ of the players choose R when $%
B_{t}>B^{1/2-\varepsilon /2}-\theta $ and at least $1-\varepsilon ^{\prime }$
choose L when $B_{t}B^{1/2}+\varepsilon $; the proof
that L must be played for $B_{t}q_{n}(X_{t})$%
), R is a strict best response if all other players are expected to choose R
whenever the state is to the right of $q_{n-1}$ and L otherwise. \ Since R
is strictly dominant for large enough $B_{t}$, $q_{n}(x)$ must be finite for
all $n\geq 0$. \ By strategic complementarities, $q_{n}(x)\leq q_{n-1}(x)$.
\ Moreover, by the existence of a dominance region for L, the sequence $%
(q_{n}(x))_{n\geq -1}$ is bounded below. $\ $Hence $Q(x)=\lim_{n\rightarrow
\infty }q_{n}(x)$ exists and is finite.
All players must choose R when the state is to the right of $Q$. \ Since the
iterative process stops at $Q$, there must also be states arbitrarily close
to (or on) $Q$ at which a player is willing to choose L if she thinks that
all others will choose R when to the right of $Q$ and L otherwise. \ Let `A'
denote a player with these beliefs who observes such a state $(b,x)$ and
then chooses an action at time $t$. \ (Note that $b$, $x$, and $Q$ are all
functions of $k$ and $\tau $.) \ We can assume that $(b,x)$ is within one
horizontal jump of $Q$. \ Let $\underline{\tau }()$ be small enough that
this implies $b-Q(x)<\varepsilon /3$.\footnote{%
Since $b-Q(x)<\sigma \sqrt{\tau }+\left| \mu \right| \tau $, we must have $%
b-Q(x)<\varepsilon /3$ if $\tau <\min \left\{ \varepsilon /3\sigma ,\left[
\varepsilon /3\sigma \right] ^{2}\right\} $, which we can guarantee by
choosing $\underline{\tau }(\sigma )$ to be smaller than $\min \left\{
\varepsilon /3\sigma ,\left[ \varepsilon /3\sigma \right] ^{2}\right\} $.} \
By (\ref{eq:relpay}),
\[
0\geq E\left[ \sum_{v=t,t+\tau ,\ldots }m\tau (1-k\tau )^{\frac{v-t}{\tau }%
}e^{-r(v-t)}[X_{v}\Delta (R,B_{v})+(1-X_{v})\Delta (L,B_{v})]\right]
\]
\noindent Taking $\tau $ to zero for any given $k$, the right hand side
converges to
\[
E\left[ \int_{v=t}^{\infty }me^{-(k+r)(v-t)}\left[ X_{v}\Delta
(R,B_{v})+(1-X_{v})\Delta (L,B_{v})\right] dv\right]
\]
\noindent since $\lim_{\tau \rightarrow 0}(1-k\tau )^{\frac{v-t}{\tau }%
}=e^{-k(v-t)}$. \ Since $\Delta $ is a continuous function, as $k\rightarrow
\infty $ this converges to
\begin{equation}
\int_{v=t}^{\infty }me^{-(k+r)(v-t)}\left[ E(X_{v})\Delta
(R,b)+(1-E(X_{v}))\Delta (L,b)\right] dv \label{eq:payoffkinf}
\end{equation}
By Lemma \ref{lem:1}, for any $\delta \in (0,\min (x,1-x))$, in the limit as
first $\tau \rightarrow 0$ and then $k\rightarrow \infty $ player A expects
a $\delta $-bifurcation to happen almost instantaneously relative to her
expected lock-in time, $1/k$. \ The probability that the $\delta $%
-bifurcation will be upwards is $1-x$. \ Since $\delta $ can be arbitrarily
small, $E(X_{v})$ converges to $(1-x)(1-(1-x)e^{-{k}v})+x(xe^{-{k}%
v})=1-x+(2x-1)e^{-{k}v}$. \ Therefore, the (nonpositive) relative payoff
from choosing R converges to
\[
\int_{v=t}^{\infty }me^{-(k+r)(v-t)}\left( (1-x+(2x-1)e^{-{k}v})\Delta
(R,b)+(x-(2x-1)e^{-{k}v})\Delta (L,b)\right) dv
\]
\[
=\frac{m}{k+r}\left[ \frac{rx+k}{2k+r}\Delta (R,b)+\left( 1-\frac{rx+k}{2k+r}%
\right) \Delta (L,b)\right]
\]
\noindent As $k\rightarrow \infty $ the expression in square brackets
converges to $\frac{1}{2}\Delta (R,b)+\frac{1}{2}\Delta (L,b)$. \ But $\frac{%
1}{2}\Delta (R,B^{1/2})+\frac{1}{2}\Delta (L,B^{1/2})=0$. \ So for any $%
\varepsilon >0$, if $k$ is sufficiently large and $\tau $ is small enough
given $k$, then $b$ must be less than $B^{1/2}+\varepsilon /3$. \ Since $%
dQ(x)/dx=-\varepsilon /3$, $\left| b-Q(x)\right| <\varepsilon /3$, and R
must be played to the right of $Q$, it follows that R must be played
whenever $B_{t}>B^{1/2}+\varepsilon $. \ Q.E.D.\bigskip
\noindent {\bf Proof of Theorem 2\smallskip }
The proof follows the lines of the proof of Theorem \ref{thm:kinfty}, so we
simply sketch the differences. \ Instead of doing the iterations with lines
of a fixed slope, we use translations of $B^{h(x)}$, where $h(x)=\frac{rx+k}{%
2k+r}$. \ (It is straightforward to check that $B^{h(x)}$ is strictly
decreasing and continuously differentiable in $x$.) \ Suppose player A is
willing to choose L at a state $(b,x)$ satisfying $\left| b-Q(x)\right|
<\varepsilon /2$ on the belief that others will play according to $Q$. \ By
Lemma \ref{lem:2}, in the limit as $\tau \rightarrow 0$ and then $\sigma
,\mu \rightarrow 0$, player A expects an instantaneous bifurcation, with the
probability $1-x$ that it will be upwards. \ As in the proof of Theorem \ref
{thm:kinfty}, her (nonpositive) relative payoff from choosing R is
proportional to
\[
\frac{rx+k}{2k+r}\Delta (R,b)+\left( 1-\frac{rx+k}{2k+r}\right) \Delta (L,b)
\]
\noindent in the limit. \ This expression is zero precisely when $b=B^{h(x)}$%
. \ Hence, we can choose $\sigma $ and $\mu $ sufficiently small, and $\tau $
small enough given $\sigma $ and $\mu $, so that $b\leq B^{h(x)}+\varepsilon
/2$. \ Since $\left| b-Q(x)\right| <\varepsilon /2$, $Q$ must be within $%
\varepsilon $ of $B^{h()}$. \ But R must be played to the right of $Q$. \
The proof that L must be played whenever $B_{t}0$, and $%
\underline{\tau }_{0}(\cdot )>0$ such that for any $\sigma $, if $\left| \mu
\right| <\underline{\mu }$ and $\tau <\underline{\tau }_{0}(\sigma )$ then
once $\left| D\right| $ exceeds $c\sigma ^{2}$, the probability exceeds $%
1-\varepsilon /2$ that $X$ will reach a $\delta $-neighborhood of 0 or 1
without the state $(B,X)$ ever again being `close to $Q$'.\footnote{%
For brevity, Claim \ref{clm:2.1} only addresses the case in which $X_{t}$ is
not 0 or 1. \ Otherwise, the same proof guarantees a bifurcation only if $D$
reaches $+\underline{d}$ (in the case $X_{t}=0$) or $-\underline{d}$ (in the
case $X_{t}=1$). \ This is not a problem since in Part 2 we will show that
the probability of reaching the `correct' $\underline{d}$ is nearly 1 in the
limit.}{\bf \vspace{-0.1in}}
\end{claim}
\noindent {\bf Proof}\quad Let $\overline{Q}^{\prime }$\ and $\underline{Q}%
^{\prime }$ be (strictly positive and finite) upper and lower bounds on $%
\left| Q^{\prime }(x)\right| $. \ These bounds exist because $Q^{\prime }$
is strictly negative and continuous over the compact interval $[0,1]$. \
When on one side of $Q$, the mean of $\left| D_{t}\right| $ changes at a
rate no less than $\lambda =k\underline{Q}^{\prime }\delta -\left| \mu
\right| $, since $\min (1-X_{t},X_{t})>\delta $. \ Let $\underline{\mu }=k%
\underline{Q}^{\prime }\delta /2$, so that $\lambda $ is strictly positive
if $\left| \mu \right| <\underline{\mu }$. \ Then if $\left| D_{t}\right|
=c\sigma ^{2}$, the chance of hitting $Q$ before $X$ reaches a $\delta $%
-neighborhood of 0 or 1 is less than $e^{-2c\lambda }$ in the limit as $\tau
\rightarrow 0$ (see Karlin and Taylor \cite[p. 362]{Karlin}).\footnote{%
This uses the fact, from Billingsley \cite{Billingsley}, that as $\tau
\rightarrow 0$, $B$ converges to a Brownian motion with variance $\sigma
^{2} $ and drift $\mu $.} \ So letting $c=\ln (2/\varepsilon )/(k\underline{Q%
}^{\prime }\delta )$, once $\left| D_{t}\right| $ equals $c\sigma ^{2}$, the
probability exceeds $1-\varepsilon /2$ that the state will reach a $\delta $%
-neighborhood of 0 or 1 without ever again being `close to $Q$'. \ Q.E.D.$_{(%
\text{Claim \ref{clm:2.1}})}$
We now show that for small $\sigma ^{2}$, $\left| D\right| $ reaches $%
c\sigma ^{2}$ quickly with high probability. \ Claim \ref{clm:2.2.1}\ shows
that independently of the state at time $t$, by time $t+\sigma ^{2}$ the
noise in $B$ takes us on the order of $\sigma ^{2}$ away from $Q$ with
positive probability:{\bf \vspace{-0.1in}}
\begin{claim}
\label{clm:2.2.1} There are constants $p_{1}>0$ and $c_{1}>0$, and a
function $\underline{\tau }_{1}(\cdot )>0$, such that for any $\sigma ^{2}$,
$\mu $, $B_{t}$ and $X_{t}$, if $\tau <\underline{\tau }_{1}(\sigma )$ then
the probability that $\left| B_{t+\sigma ^{2}}-Q(X_{t+\sigma ^{2}})\right|
>c_{1}\sigma ^{2}$ is greater than $p_{1}$.{\bf \vspace{-0.1in}}
\end{claim}
\noindent {\bf Proof\vspace{-0.1in} \ }
\begin{eqnarray*}
\Pr \left( |B_{t+\sigma ^{2}}-Q(X_{t+\sigma ^{2}})|>c_{1}\sigma ^{2}\right)
&\geq &\Pr \left( |B_{t+\sigma ^{2}}-Q(X_{t})|-|Q(X_{t+\sigma
^{2}})-Q(X_{t})|>c_{1}\sigma ^{2}\right) \\
&\geq &\Pr \left( |B_{t+\sigma ^{2}}-Q(X_{t})|>(c_{1}+k\overline{Q}^{\prime
})\sigma ^{2}\right)
\end{eqnarray*}
\vspace{-0.1in}\noindent since $|Q(X_{t+\sigma ^{2}})-Q(X_{t})|\leq k%
\overline{Q}^{\prime }\sigma ^{2}$. \ But the probability that the
difference between a random variable $B_{t+\sigma ^{2}}$ and a given number $%
Q(X_{t})$ exceeds some number $(c_{1}+k\overline{Q}^{\prime })\sigma ^{2}$
is at least the probability that the difference between the random variable
and its {\em mean} exceeds this number. \ Thus,\vspace{-0.1in}
\[
\Pr \left( |B_{t+\sigma ^{2}}-Q(X_{t})|>(c_{1}+k\overline{Q}^{\prime
})\sigma ^{2}\right) \geq \Pr \left( |B_{t+\sigma ^{2}}-E(B_{t+\sigma
^{2}}|B_{t})|>(c_{1}+k\overline{Q}^{\prime })\sigma ^{2}\right)
\]
\vspace{-0.1in}\noindent As $\tau $ shrinks the increment $B_{t+\sigma
^{2}}-E(B_{t+\sigma ^{2}}|B_{t})$ becomes normal with standard deviation $%
\sqrt{\sigma ^{2}\cdot \sigma ^{2}}=\sigma ^{2}$\ (by the central limit
theorem). \ Hence, the last term exceeds some fixed probability $p_{1}$ if $%
\tau $ is sufficiently small. \ Q.E.D.$_{(\text{Claim }\ref{clm:2.2.1})}$
Once the state is a distance of order $\sigma ^{2}$ from $Q$, there is some
chance that it will reach $c\sigma ^{2}$ in time of order $\sigma ^{2}$, at
which point a bifurcation is almost guaranteed by Claim \ref{clm:2.1}. \
Claim \ref{clm:2.2.2} shows that this probability is independent of $\sigma
^{2}$.{\bf \vspace{-0.1in}}
\begin{claim}
\label{clm:2.2.2} For any $c>0$, there are positive constants $p_{2}$ and $%
c_{2}$, independent of $\sigma $, and a function $\underline{\tau }%
_{2}(\cdot )>0$, such that if $|D_{v}|=c_{1}\sigma ^{2}$ and $\tau <%
\underline{\tau }_{2}(\sigma )$, then the probability that $%
|D_{v+c_{2}\sigma ^{2}}|>c\sigma ^{2}$ exceeds $p_{2}$.{\bf \vspace{-0.1in}}
\end{claim}
\noindent {\bf Proof}\quad The given probability exceeds the probability
that $|D_{v+c_{2}\sigma ^{2}}|>c\sigma ^{2}$ {\em and} that $D$ is never
close to zero between the times $v$ and $v+c_{2}\sigma ^{2}$. \ While $D$
remains on one side of zero, $|D|$ is a random walk with a strictly positive
trend. \ Let $\widetilde{D}$ be a random walk with the same variance as $D$
but with zero trend, and assume $\widetilde{D}_{v}=c_{1}\sigma ^{2}$. \ The
probability that $|D_{v+c_{2}\sigma ^{2}}|>c\sigma ^{2}$ exceeds the
probability that $\widetilde{D}$ exceeds $c\sigma ^{2}$ at time $%
v+c_{2}\sigma ^{2}$ and is never close to zero between the two times. \ This
probability is approximately $\Pr \left( \widetilde{D}_{v+c_{2}\sigma
^{4}}>c\sigma ^{2}\right) -\Pr \left( \widetilde{D}_{v+c_{2}\sigma
^{4}}<-c\sigma ^{2}\right) $, since for small $\tau $ the reflection
principle can be used. \ But $\widetilde{D}_{v+c_{2}\sigma ^{4}}$ is
approximately normal for small $\tau $, so this probability is close to $\Pr
\left( N(c_{1}\sigma ^{2},c_{2}\sigma ^{4})>c\sigma ^{2}\right) -\Pr \left(
N(c_{1}\sigma ^{2},c_{2}\sigma ^{4})<-c\sigma ^{2}\right) $, which equals $%
\Pr \left( \frac{c-c_{1}}{\sqrt{c_{2}}}0$ and any large enough $c$,%
\footnote{%
By the proof of claim \ref{clm:2.1}, $c$ is `large enough' if it exceeds $%
\ln (2/\varepsilon )/(k\underline{Q}^{\prime }\delta )$.} there are $%
\underline{\sigma }>0$, $\underline{\tau }(\cdot )>0$, and $\underline{\mu }%
>0$ such that if $\sigma <\underline{\sigma }$, $\tau <\underline{\tau }%
(\sigma )$, and $\left| \mu \right| <\underline{\mu }$, then $\left|
D\right| $ reaches a distance $c\sigma ^{2}$ with probability $1-\varepsilon
/2$ within time $\varepsilon $, and once it reaches this distance, a $\delta
$-bifurcation has occurred with probability at least $1-\varepsilon /2$. \
This proves part 1.\bigskip
\noindent {\bf Direction of Bifurcation}
Since for $c$ large enough, a bifurcation occurs with probability $%
1-\varepsilon /2$ once a distance $c\sigma ^{2}$ from $Q$ is reached, it
suffices to compute the ratio of probabilities of reaching $+c\sigma ^{2}$
first vs.\ reaching $-c\sigma ^{2}$ first. \ For any $\varepsilon ^{\prime
}>0$ we can choose $\sigma $, $\mu $, and $\tau $ small enough that the
distance $c\sigma ^{2}$ is reached with probability $1-\varepsilon ^{\prime
}/2$ within time $\varepsilon ^{\prime }$. \ During this time, $X$ can
change by no more than $k\varepsilon ^{\prime }$ (taking $\tau $ to be
small). Hence, the absolute value of the trend in $D_{t}$ is bounded between
two constants $\underline{\lambda }_{R}<\overline{\lambda }_{R}\,$when $%
D_{t} $ is positive and two other constants $\underline{\lambda }_{L}<%
\overline{\lambda }_{L}$ when it is negative, where these bounds converge to
$\lambda _{R}=k(1-X_{t})|Q^{\prime }(X_{t})|+\mu \,$ and $\lambda
_{L}=kX_{t}|Q^{\prime }(X_{t})|-\mu $, respectively, as $\varepsilon
^{\prime }$ shrinks. \ The ratio of bifurcation probabilities lies between
the ratio corresponding to constant trends $\underline{\lambda }_{R}$ and $%
\overline{\lambda }_{L}$ and the ratio that comes from $\overline{\lambda }%
_{R}$ and $\underline{\lambda }_{L}$. \ This is because more positive trends
make $D$ higher for any given realization of the random component of $B$
(i.e., given any sequence of signs of $B$'s jumps). \ Hence, $\varepsilon
^{\prime }$ shrinks, the ratio of bifurcation probabilities converges to
that computed using the constant absolute trends $\lambda _{R}\,$ and $%
\lambda _{L}$. \ For the remainder of the proof we will assume constant
trends and show that for large enough $c$, the ratio of the probabilities is
approximately $\lambda _{R}/\lambda _{L}$, which converges to $%
(1-X_{t})/X_{t}$ as $\mu $ shrinks.
Claim \ref{clm:2.3} shows that for small $\tau $, the relative probability
of reaching $+c\sigma ^{2}$ first vs.\ reaching $-c\sigma ^{2}$ first
depends little on the precise value of $D_{t}$ as long as it is `close to
0'. \ Let $P^{\uparrow }$ and $P^{\downarrow }$, respectively, be the
probabilities of reaching $+c\sigma ^{2}$ first and $-c\sigma ^{2}$ first on
the assumption that $D_{t}$ {\em equals} 0.{\bf \vspace{-0.1in}}
\begin{claim}
\label{clm:2.3} For any $\varepsilon ^{\prime }>0$ there is a $\underline{%
\tau }>0$ such that if $\tau <\underline{\tau }$ then whenever $D_{t}\in
\lbrack -\sigma \sqrt{\tau }+\mu \tau ,+\sigma \sqrt{\tau }+\mu \tau ]$, the
probability of reaching $+c\sigma ^{2}$ ($-c\sigma ^{2}$) first is within $%
\varepsilon ^{\prime }$ of $P^{\uparrow }$ ($P^{\downarrow }$).{\bf \vspace{%
-0.1in}}
\end{claim}
\noindent {\bf Proof}\quad For any $D_{t}$ in the given range and for any
small $\nu >0$, the c.d.f. $\Gamma $ of $D_{t+\nu }$ is between two bounds.
\ The lower bound is the time $t+\nu $ c.d.f. $\underline{\Gamma }$\ of a
random walk that starts at $-\sigma \sqrt{\tau }-\left| \mu \right| \tau $
and has the constant trend $-\lambda _{L}$. \ The upper bound is the time $%
t+\nu $ c.d.f. $\overline{\Gamma }$ of a random walk that starts at $\sigma
\sqrt{\tau }+\left| \mu \right| \tau $ and has the trend $\lambda _{R}$. \
When $\tau $ is small, these two bounds are approximately normal with means $%
-\sigma \sqrt{\tau }-\left| \mu \right| \tau -\lambda _{L}\nu $ and $\sigma
\sqrt{\tau }+\left| \mu \right| \tau +\lambda _{R}\nu $, respectively, and
common standard deviation $\sigma \sqrt{\nu }$.\ \ For small $\nu $, $\sqrt{%
\nu }/\nu $ is arbitrarily large, so the two bounds converge to each other
(as $\nu $ and $\tau $ shrink, with $\tau $ sufficiently small given $\nu $%
). \ Let $P^{\uparrow }(z)$ be the probability of an upwards bifurcation
when $D_{t+\nu }=z$. \ Then the probability of an upward bifurcation is
between $\int_{z=-\infty }^{\infty }P^{\uparrow }(z)d\underline{\Gamma }(z)$
and $\int_{z=-\infty }^{\infty }P^{\uparrow }(z)d\overline{\Gamma }(z)$. \
Since $P^{\uparrow }(z)$ is always between 0 and 1, the two integrals
converge to each other (see Royden \cite[p. 232]{Royden}). \ Q.E.D.$_{(\text{%
Claim }\ref{clm:2.3})}$
The next claim shows that to compute the probability ratio $P^{\uparrow
}/P^{\downarrow }$ we can focus on what happens in an arbitrarily short time
interval after time $t$. \ Given any $\eta >0$, let $P_{\eta }^{\uparrow }$
and $P_{\eta }^{\downarrow }$, respectively, be the probabilities of an
upward and downward $c\sigma ^{2}$-bifurcation occurring at some time $v\in
\lbrack t,t+\eta )$, on the assumption that $D_{t}$ equals 0. \ (A `$c\sigma
^{2}$-bifurcation' occurs at the last time at which $D$ is close to zero
before reaching $\pm c\sigma ^{2}$.){\bf \vspace{-0.1in}}
\begin{claim}
\label{clm:2.4} For any $\eta >0$ and $\varepsilon ^{\prime }>0$, there is a
$\underline{\tau }>0$ such that if $\tau <\underline{\tau }$, then $%
P^{\uparrow }/P^{\downarrow }$ is within $\varepsilon ^{\prime }$ of $%
P_{\eta }^{\uparrow }/P_{\eta }^{\downarrow }$.{\bf \vspace{-0.1in}}
\end{claim}
\noindent {\bf Proof}\quad Let $P_{\eta }=P_{\eta }^{\uparrow }+P_{\eta
}^{\downarrow }$. If there is no $c\sigma ^{2}${\em -}bifurcation in the
interval $[t,t+\eta )$, then we must have $D_{s}$ close to 0 for some $s\geq
t+\eta $. \ By Claim \ref{clm:2.3}, for any $\varepsilon >0$, if $\tau $ is
small enough the probability of an upward $c\sigma ^{2}${\em -}bifurcation
following time $s$ is in the range $[P^{\uparrow }-\varepsilon ,P^{\uparrow
}+\varepsilon ]$. \ Thus, $P^{\uparrow }$ is between $P_{\eta }^{\uparrow
}+(1-P_{\eta })(P^{\uparrow }-\varepsilon )$ and $P_{\eta }^{\uparrow
}+(1-P_{\eta })(P^{\uparrow }+\varepsilon )$. \ This shows that $P^{\uparrow
}$ is between $\frac{P_{\eta }^{\uparrow }+\varepsilon (1-P_{\eta })}{%
P_{\eta }}$ and $\frac{P_{\eta }^{\uparrow }-\varepsilon (1-P_{\eta })}{%
P_{\eta }}$. Likewise, $P^{\downarrow }$ is between $\frac{P_{\eta
}^{\downarrow }+\varepsilon (1-P_{\eta })}{P_{\eta }}$ and $\frac{P_{\eta
}^{\downarrow }-\varepsilon (1-P_{\eta })}{P_{\eta }}$. Therefore, $%
P^{\uparrow }/P^{\downarrow }$ is between $\frac{P_{\eta }^{\uparrow
}-\varepsilon (1-P_{\eta })}{P_{\eta }^{\downarrow }+\varepsilon (1-P_{\eta
})}$ and $\frac{P_{\eta }^{\uparrow }+\varepsilon (1-P_{\eta })}{P_{\eta
}^{\downarrow }-\varepsilon (1-P_{\eta })}$. \ But given $\eta $, we can
take $\tau $ small enough that $\varepsilon $ is negligible relative to the
sum $P_{\eta }=P_{\eta }^{\uparrow }+P_{\eta }^{\downarrow }$. \ Q.E.D.$_{(%
\text{Claim }\ref{clm:2.4})}$
By Claim \ref{clm:2.4}, $\lim_{\tau \rightarrow 0}P^{\uparrow
}/P^{\downarrow }=\lim_{\tau \rightarrow 0}P_{\eta }^{\uparrow }/P_{\eta
}^{\downarrow }$ for any $\eta >0$. \ Thus, $\lim_{\tau \rightarrow
0}P^{\uparrow }/P^{\downarrow }$ equals $\lim_{\eta \rightarrow 0}\lim_{\tau
\rightarrow 0}P_{\eta }^{\uparrow }/P_{\eta }^{\downarrow }$, which we now
compute. \ For a $c\sigma ^{2}${\em -}bifurcation to occur in $[t,t+\eta )$,
two things must happen. First, $D$ must not be `close to zero' at time $%
t+\eta $. \ Second, $D$ subsequently must reach a distance $c\sigma ^{2}$
while remaining not `close to zero.' \ Let $\Phi _{M,S}$ denote the c.d.f.
of a normally distributed random variable with mean $M$ and standard
deviation $S$. \ By the law of large numbers,
\begin{equation}
\lim_{\tau \rightarrow 0}\Pr (D_{t+\eta }0$ such that for any $a>0$, $%
\lim_{c\rightarrow \infty }\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow 0}%
\frac{P(a\sqrt{\eta })}{c_{3}a\sqrt{\eta }\lambda _{R}}=1$ and $%
\lim_{c\rightarrow \infty }\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow 0}%
\frac{P(-a\sqrt{\eta })}{c_{3}a\sqrt{\eta }\lambda _{L}}=1$.{\bf \vspace{%
-0.1in}}
\end{claim}
\noindent {\bf Proof}\quad We will show the first equality; the second
follows analogously. \ In the given limit, $a\sqrt{\eta }$ becomes
arbitrarily large relative to the jumps in $D$ and arbitrarily small
relative to $c\sigma ^{2}$.\ \ Suppose $D_{t+\eta }=a\sqrt{\eta }$ and let $%
a^{\prime }\in (0,a)$. \ To reach zero, $D$ must first reach $a^{\prime }%
\sqrt{\eta }$. \ Since $D$ has stationary increments as long as it remains
positive, $\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow 0}\frac{P(a\sqrt{%
\eta })}{P([a-a^{\prime }]\sqrt{\eta })+(1-P([a-a^{\prime }]\sqrt{\eta }%
))P(a^{\prime }\sqrt{\eta })}=1$. \ But $\lim_{\eta \rightarrow 0}\lim_{\tau
\rightarrow 0}P(a^{\prime }\sqrt{\eta })=$
\noindent $\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow 0}P([a-a^{\prime
}]\sqrt{\eta })=0$, so $\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow 0}%
\frac{P(a\sqrt{\eta })}{P([a-a^{\prime }]\sqrt{\eta })+P(a^{\prime }\sqrt{%
\eta })}=1$. \ Since this holds for any $a^{\prime }\in (0,a)$, $P(a\sqrt{%
\eta })$ must become proportional to $a\sqrt{\eta }$. \ As for $\lambda _{R}$%
, as long as $D$ remains positive, it is simply a random walk with constant
trend $\lambda _{R}$. \ For any $\ell >1$, consider the process $\hat{D}_{v}=%
\frac{1}{\ell }D_{\ell ^{2}v}$. \ In the limit as $\tau \rightarrow 0$,
\[
\mbox{Var}(\hat{D}_{w}-\hat{D}_{v})=\mbox{Var}(\frac{1}{\ell }D_{\ell ^{2}w}-%
\frac{1}{\ell }D_{\ell ^{2}v})=\frac{1}{\ell ^{2}}\sigma ^{2}\left( \ell
^{2}w-\ell ^{2}v\right) =\sigma ^{2}(w-v)=\mbox{Var}(D_{w}-D_{v})
\]
\noindent By the change of variables, $P(a\sqrt{\eta })$ equals the
probability that, given that $\hat{D}_{\ell ^{2}(t+\eta )}=a\sqrt{\eta }%
/\ell $, $\hat{D}$ subsequently reaches $c\sigma ^{2}/\ell $ before zero. \
The trend of $\hat{D}$ is $\ell \lambda $. \ But
\begin{eqnarray*}
\lim_{c\rightarrow \infty }\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow
0}\Pr (\hat{D}\text{ reaches }c\sigma ^{2}\text{ before }0\,|\,\hat{D}\text{
starts at }c\sigma ^{2}/\ell ) &=& \\
\lim_{c\rightarrow \infty }\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow
0}\Pr (D\text{ reaches }\ell c\sigma ^{2}\text{ before }0\,|\,D\text{ starts
at }c\sigma ^{2}) &=&1
\end{eqnarray*}
since the probability in the second line is greater than the probability
that $D$ will {\em never} return to zero if it starts at $c\sigma ^{2}$,
which converges to $1-e^{-2c\lambda _{R}}$ as $\tau \rightarrow 0$ (see
Karlin and Taylor \cite{Karlin}). \ So
\[
\lim_{c\rightarrow \infty }\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow 0}%
\frac{\Pr (\widehat{D}\text{ reaches }c\sigma ^{2}\text{ before 0 }|\text{ }%
\hat{D}_{\ell ^{2}(t+\eta )}=a\sqrt{\eta }/\ell )}{P(a\sqrt{\eta })}=1
\]
But by prior arguments,
\[
\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow 0}\frac{\Pr (\widehat{D}%
\text{ reaches }c\sigma ^{2}\text{ before 0 }|\text{ }\hat{D}_{\ell
^{2}(t+\eta )}=a\sqrt{\eta }/\ell )}{\frac{1}{\ell }\cdot \Pr (\widehat{D}%
\text{ reaches }c\sigma ^{2}\text{ before 0 }|\text{ }\hat{D}_{\ell
^{2}(t+\eta )}=a\sqrt{\eta })}=1
\]
\noindent so that
\[
\lim_{c\rightarrow \infty }\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow 0}%
\frac{\ell \cdot P(a\sqrt{\eta })}{\Pr (\widehat{D}\text{ reaches }c\sigma
^{2}\text{ before 0 }|\text{ }\hat{D}_{\ell ^{2}(t+\eta )}=a\sqrt{\eta })}=1
\]
\noindent Since $\widehat{D}$ has the variance of $D$ but trend $\ell
\lambda _{R}$, $P(a\sqrt{\eta })$ must become proportional to the trend as
well. \ Q.E.D.$_{(\text{Claim }\ref{clm:2.5})}\medskip $
By Claim \ref{clm:2.5},
\[
\lim_{c\rightarrow \infty }\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow 0}%
\frac{P_{\eta }^{\uparrow }}{P_{\eta }^{\downarrow }}=\lim_{c\rightarrow
\infty }\lim_{\eta \rightarrow 0}\lim_{\tau \rightarrow 0}\frac{%
\int_{a=0}^{\infty }P(a\sqrt{\eta })d\Psi _{\eta }(a\sqrt{\eta })}{%
\int_{a=0}^{\infty }P(-a\sqrt{\eta })d\Psi _{\eta }(-a\sqrt{\eta })}
\]
\noindent where $\Psi _{\eta }$ is the c.d.f. of $D_{t+\eta }$. \ Since $%
\lim_{\eta \rightarrow 0}\sqrt{\eta }/\eta =\infty $ and by (\ref{eq:cdfofD}%
), $\Psi _{\eta }$ converges to a c.d.f. of a normally distributed variable
with mean 0 and standard deviation $\sigma \sqrt{\eta }$. \ Hence, by Claim
\ref{clm:2.5}, $\lim_{c\rightarrow \infty }\lim_{\eta \rightarrow
0}\lim_{\tau \rightarrow 0}P_{\eta }^{\uparrow }/P_{\eta }^{\downarrow
}=\lambda _{R}/\lambda _{L}$, so $\lim_{c\rightarrow \infty }\lim_{\tau
\rightarrow 0}P^{\uparrow }/P^{\downarrow }=\lambda _{R}/\lambda _{L}$. \
This shows that for $c$ large enough, the relative probability of reaching $%
+c\sigma ^{2}$ vs. $-c\sigma ^{2}$ first with constant trends $\lambda _{R}$
and $\lambda _{L}$ is approximately $\lambda _{R}/\lambda _{L}$ for small $%
\tau $. Q.E.D.$_{(\text{Lemma }\ref{lem:2})}$\bigskip
\noindent {\bf Proof of Lemma \ref{lem:1}}
We replace $B_{t}$ with $\hat{B}_{t}=B_{t/k}$ and $X_{t}$ with $\hat{X}%
_{t}=X_{t/k}$. \ The variance of $\hat{B}$ is $\sigma ^{2}/k$ and the trend
is $\mu /k$. \ Since these go to zero as $k$ grows, the odds of an upward
vs.\ a downward bifurcation are as in Lemma \ref{lem:2}. \ A bifurcation
happens with probability $1-\varepsilon $ before time $\varepsilon $ in the
new time units; in the original time units, it happens with probability $%
1-\varepsilon $ before time $\varepsilon /k$. \ The time between periods is $%
\tau k$ in the new time units. \ To apply the prior argument we require $%
\tau k<\underline{\tau }^{\text{Lem }\ref{lem:2}}(\sigma )$ (where $%
\underline{\tau }^{\text{Lem }\ref{lem:2}}$ denotes the $\underline{\tau }$
of Lemma \ref{lem:2}), so we can let $\underline{\tau }(k)=\underline{\tau }%
^{\text{Lem }\ref{lem:2}}(\sigma )/k$. \ Since $\sigma $ is fixed in Lemma
\ref{lem:2}, $\underline{\tau }(k)$ is a function of $k$ alone.
\pagebreak
\begin{thebibliography}{99}
\bibitem{Billingsley} Billingsley, P. \ {\sl Convergence of Probability
Measures.} New York: \ Wiley, 1968.
\bibitem{Blume93} Blume, L. 1993. ``The Statistical Mechanics of Strategic
Interaction.'' {\sl Games and Economic Behavior} 5:387-424.
\bibitem{Boylan} Boylan, R.T. 1992. ``Laws of Large Numbers for Dynamical
Systems with Randomly Matched Individuals.'' {\sl Journal of Economics Theory%
} 57:473-504.
\bibitem{BFP2} Burdzy, K., D.M. Frankel, and A. Pauzner. 1997. ``Fast
Equilibrium Selection by Rational Players Living in a Changing World.'' \
Foerder Institute w.p. 7-97.
\bibitem{BFPmath} Burdzy, Krzysztof, David M. Frankel, and Ady Pauzner. \
1998. \ ``On the Time and Direction of Stochastic Bifurcation.'' \ In B.
Szyszkowicz, ed. {\sl Asymptotic Methods in Probability and Statistics: A
Volume in Honour of Miklos Csorgo.} Holland: Elsevier.
\bibitem{Carlsson} Carlsson, H., and E. van Damme. 1993. ``Global Games and
Equilibrium Selection.'' {\sl Econometrica} 61:989-1018.
\bibitem{Ellison} Ellison, G. 1993. ``Learning, Local Interaction, and
Coordination.'' {\sl Econometrica} 61:1047-1071.
\bibitem{FosterYoung} Foster, D., and P.H. Young. 1990. ``Stochastic
Evolutionary Game Dynamics.'' {\sl Theoretical Population Biology}
38:219-232.
\bibitem{FP} Frankel, David M., and Ady Pauzner. 1999. ``Resolving
Indeterminacy in Dynamic Settings: \ the Role of Shocks.'' \ Forthcoming,
{\sl Quarterly Journal of Economics}. \ Available at http://econ.tau.ac.il/%
\symbol{126}ady/papers.html
\bibitem{FudenbergTirole} Fudenberg, D., and J. Tirole. 1991. {\sl Game
Theory}. Cambridge: MIT Press.
\bibitem{FudenbergHarris} Fudenberg, D., and C. Harris. 1992.
``Evolutionary Dynamics with Aggregate Shocks.'' {\sl Journal of Economic
Theory} 57:420-441.
\bibitem{GilboaMatsui} Gilboa, I., and A. Matsui. 1992. ``A Model of Random
Matching.'' {\sl Journal of Mathematical Economics} 21:185-197.
\bibitem{HarsanyiSelten} Harsanyi, J., and R. Selten. 1988. {\sl A General
Theory of Equilibrium Selection in Games.} Cambridge: MIT Press.
\bibitem{Judd} Judd, K.L. 1985. ``The Law of Large Numbers with a Continuum
of IID Random Variables.'' {\sl Journal of Economic Theory} 35:19-25.
\bibitem{Kandori} Kandori, M., G.J. Mailath, and R. Rob. 1993. ``Learning,
Mutation, and Long Run Equilibria in Games.'' {\sl Econometrica} 61:29-56.
\bibitem{Karlin} Karlin, S., and H.M. Taylor. {\sl A First Course in
Stochastic Processes, 2nd ed.} New York: Academic Press, 1975.
\bibitem{Matsui} Matsui, A.. \ 1998. \ ``Multiple Lenders and Credit
Squeeze.'' \ Mimeo, U. Tokyo.
\bibitem{MatsuiMatsuyama} Matsui, A., and K. Matsuyama. 1995. ``An Approach
to Equilibrium Selection.'' {\sl Journal of Economic Theory} 65:415-434.
\bibitem{Morris} Morris, S., R. Rob, and H.S. Shin. 1995. ``p-Dominance and
Belief Potential.'' {\sl Econometrica} 63:145-157.
\bibitem{Royden} Royden, H. L. \ 1968. \ {\sl Real Analysis (2nd ed.)} \
Toronto: \ MacMillan.
\bibitem{Young} Young, P. 1993. ``The Evolution of Conventions.'' {\sl %
Econometrica} 61:57-84.
\end{thebibliography}
\end{document}