%% This document created by Scientific Word (R) Version 2.5 \documentclass[12pt,thmsa,a4paper]{article} \usepackage{amsfonts} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{sw20jart} %TCIDATA{TCIstyle=article/art4.lat,jart,sw20jart} %TCIDATA{Created=Sat Dec 13 21:56:00 1997} %TCIDATA{LastRevised=Sun Nov 14 12:01:38 1999} %TCIDATA{Language=American English} \input{tcilatex} \begin{document} \title{Evolutionary Dynamics and Backward Induction\thanks{% Previous versions: September 1999; May 1999. Research partially supported by a grant of the Israel Academy of Sciences and Humanities. The starting point for this research was a discussion during the Seventh Annual Conference of the Center for Rationality. The author thanks Bob Aumann, Dani Cohen, Ilan Eshel, Michihiro Kandori, Andreu Mas-Colell, Jean-Fran\c{c}ois Mertens, Uzi Motro, Abraham Neyman, Bezalel Peleg, Motty Perry, Phil Reny, Larry Samuelson, Karl Schlag, Reinhard Selten, Avi Shmida, J\"{o}rgen Weibull, Benji Weiss, Asher Wolinsky, and Peyton Young for their useful comments.}} \author{Sergiu Hart\thanks{% Center for Rationality and Interactive Decision Theory; Department of Economics; and Department of Mathematics; The Hebrew University of Jerusalem, 91904 Jerusalem, Israel.$\quad $ \emph{E-mail}: hart@math.huji.ac.il\emph{\ }$\quad $ \emph{URL: }http://www.ma.huji.ac.il/% \symbol{126}hart}} \maketitle \begin{abstract} The backward induction (or subgame-perfect) equilibrium of a perfect information game is shown to be the unique evolutionarily stable outcome for dynamic models consisting of selection and mutation, when the mutation rate is low and the populations are large. \emph{Keywords}: games in extensive form, games of perfect information, backward induction equilibrium, subgame-perfect equilibrium, evolutionary dynamics, evolutionary stability, mutation, selection, population games. \emph{Journal of Economic Literature Classification}: C7, D7, C6. \end{abstract} %TCIMACRO{\TeXButton{setlength}{\setlength{\baselineskip}{.25in}}} %BeginExpansion \setlength{\baselineskip}{.25in}% %EndExpansion %TCIMACRO{ %\TeXButton{References Without Numbers}{ %\def\@biblabel#1{#1\hfill} %\def\thebibliography#1{\section*{References}\list %{}{ % \labelwidth 0pt % \leftmargin 1.8em % \itemindent -1.8em % \usecounter{enumi}} %\def\newblock{\hskip .11em plus .33em minus .07em} %\sloppy\clubpenalty4000\widowpenalty4000 %\sfcode`\.=1000\relax\def\baselinestretch{1}\large \normalsize} %\let\endthebibliography=\endlist}} %BeginExpansion \def\@biblabel#1{#1\hfill} \def\thebibliography#1{\section*{References}\list {}{ \labelwidth 0pt \leftmargin 1.8em \itemindent -1.8em \usecounter{enumi}} \def\newblock{\hskip .11em plus .33em minus .07em} \sloppy\clubpenalty4000\widowpenalty4000 \sfcode`\.=1000\relax\def\baselinestretch{1}\large \normalsize} \let\endthebibliography=\endlist% %EndExpansion \section{Introduction\label{s-introduction}} \subsection{Background\label{ss-background}} A fascinating meeting of ideas has occurred in the last two decades between Evolutionary Biology and Game Theory. Now this may seem strange at first. The players in game-theoretic models are usually assumed to be fully rational, whereas genes and other vehicles of evolution are assumed to behave in ways that are entirely mechanistic. Nonetheless, once a player is replaced by a population of individuals, and a mixed strategy corresponds to the proportions of the various strategies in the population, the formal structures in the two fields turn out to be very closely related. This has led to many ideas flowing back and forth. On the one hand, game-theoretic constructs---at times quite sophisticated---find their way into evolutionary arguments; on the other, the basic paradigm of natural selection is used to justify and provide foundations for many aspects of rational behavior. For a discussion of these issues, including a historical overview, the reader is referred to Hammerstein and Selten [1994] and to Aumann [1998]. The basic parallel notions in the two fields are ``strategic equilibrium'' (introduced by J. Nash in 1950) and ``evolutionarily stable strategy'' (introduced by J. Maynard Smith and G. R. Price in 1973). Roughly speaking, when a game is played by populations of individuals (with identical payoff functions), then a Nash equilibrium point essentially yields evolutionarily stable strategies. This type of relation has been established in a wide variety of setups, both static and dynamic (see the books of Hofbauer and Sigmund [1998], Weibull [1995] and Vega-Redondo [1997]). Most of these models deal with games in strategic (or normal) form. Here we consider instead \emph{games in extensive form},\emph{\ }where a most complete description of the game is given, specifying exactly the rules, the order of moves, the information of the players, and so on. Specifically, we look at the simplest such games: \emph{finite games of perfect information}. In such games, an equilibrium point can always be obtained by a so-called ``backward induction'' argument: Starting from the final nodes, each player chooses a best-reply given the (already determined) choices of all the players that move after him. This results in an equilibrium point also in each subgame (i.e., the game starting at any node of the original game), whether that subgame is reached or not. Such a point is called a \emph{% subgame-perfect equilibrium}, or a \emph{backward induction equilibrium}, a notion introduced by R. Selten in 1965, 1975. Evolutionary models are based on two main ingredients: selection and mutation. \emph{Selection} is a process whereby better strategies prevail; in contrast, \emph{mutation}, which is relatively rare, generates strategies at random, be they better or worse. It is the combination of the two that allows for natural adaptation: New mutants undergo selection, and only the better ones survive. Of course, selection includes many possible mechanisms, be they biological (the payoff determines the number of descendants, and thus the share of better strategies increases), individual (experimentation, stimulus response), social (learning, imitation), and so on. What matters is that the process is ``adaptive'' or ``improving,'' in the sense that the proportion of better strategies increases. Evolutionary models have been extensively analyzed in various classes of games in strategic form (starting with Kandori, Mailath and Rob [1993] and Young [1993]; see also the books of Young [1998] and Fudenberg and Levine [1998]). Since mutations are like small perturbations that make everything possible (i.e., every pure strategy has positive probability), and this yields in the limit (as the perturbations go to zero) the subgame-perfect equilibrium points,\footnote{% Recall that these are games of perfect information, where ``trembling-hand perfection'' is the same as ``subgame perfection.''} it is only natural to expect that evolutionary models with low mutation rates should lead to these same points. However, the literature up to now has found the above claim to be false: Evolutionary models do not necessarily pick out the backward induction equilibria. Specifically, except in special classes of games, other equilibria besides the backward induction ones also turn out to be ``evolutionarily stable'' (see N\"{o}ldeke and Samuelson [1993]; Gale, Binmore and Samuelson [1995]; Cressman and Schlag [1997]; and the books of Samuelson [1997] and Fudenberg and Levine [1998]). \subsection{Examples\label{ss-examples}} Even without specifying exactly how selection and mutation operate, one can get some intuition by considering a few examples. The first one is the $2$% -person game $\Gamma _{1}$ of Figure \ref{ex1}% %TCIMACRO{\TeXButton{BeginFigure-ex1}{\begin{figure}[tb] \centering}} %BeginExpansion \begin{figure}[tb] \centering% %EndExpansion %TCIMACRO{ %\TeXButton{ex1.pic}{ %\unitlength 1.00mm % %\begin{picture}(70.00,67.00)(5,13) %\linethickness{1.0pt} %\put(30.00,70.00){\line(1,-1){20.00}} %\put(50.00,50.00){\line(1,-1){20.00}} %\put(50.00,50.00){\line(-1,-1){20.00}} %\put(30.00,70.00){\circle*{1.50}} %\put(50.00,50.00){\circle*{1.50}} %\put(30.00,74.00){\makebox(0,0)[cc]{$1$}} %\put(52.00,53.00){\makebox(0,0)[cc]{$2$}} %\put(30.00,26.00){\makebox(0,0)[cc]{$0$}} %\put(30.00,21.00){\makebox(0,0)[cc]{$0$}} %\put(30.00,70.00){\line(-1,-1){20.00}} %\put(10.00,46.00){\makebox(0,0)[cc]{$1$}} %\put(10.00,41.00){\makebox(0,0)[cc]{$2$}} %\put(70.00,26.00){\makebox(0,0)[cc]{$2$}} %\put(70.00,21.00){\makebox(0,0)[cc]{$1$}} %\put(19.00,63.00){\makebox(0,0)[cc]{$c^1$}} %\put(42.00,63.00){\makebox(0,0)[cc]{$b^1$}} %\put(39.00,43.00){\makebox(0,0)[cc]{$c^2$}} %\put(62.00,43.00){\makebox(0,0)[cc]{$b^2$}} %\end{picture} %}} %BeginExpansion \unitlength 1.00mm \begin{picture}(70.00,67.00)(5,13) \linethickness{1.0pt} \put(30.00,70.00){\line(1,-1){20.00}} \put(50.00,50.00){\line(1,-1){20.00}} \put(50.00,50.00){\line(-1,-1){20.00}} \put(30.00,70.00){\circle*{1.50}} \put(50.00,50.00){\circle*{1.50}} \put(30.00,74.00){\makebox(0,0)[cc]{$1$}} \put(52.00,53.00){\makebox(0,0)[cc]{$2$}} \put(30.00,26.00){\makebox(0,0)[cc]{$0$}} \put(30.00,21.00){\makebox(0,0)[cc]{$0$}} \put(30.00,70.00){\line(-1,-1){20.00}} \put(10.00,46.00){\makebox(0,0)[cc]{$1$}} \put(10.00,41.00){\makebox(0,0)[cc]{$2$}} \put(70.00,26.00){\makebox(0,0)[cc]{$2$}} \put(70.00,21.00){\makebox(0,0)[cc]{$1$}} \put(19.00,63.00){\makebox(0,0)[cc]{$c^1$}} \put(42.00,63.00){\makebox(0,0)[cc]{$b^1$}} \put(39.00,43.00){\makebox(0,0)[cc]{$c^2$}} \put(62.00,43.00){\makebox(0,0)[cc]{$b^2$}} \end{picture} % %EndExpansion \caption{The game $\Gamma _1$\label{ex1}}% %TCIMACRO{\TeXButton{EndFigure}{\end{figure}}} %BeginExpansion \end{figure}% %EndExpansion . It possesses two Nash equilibria in pure strategies: $b=(b^{1},b^{2})$ and $c=(c^{1},c^{2})$; the first, $b$, is the backward induction equilibrium. Assume that at each one of the two nodes $1$ and $2$ there is a population of individuals playing the game in that role. The populations are distinct, and each individual plays a pure action at his node.\footnote{% We say, for example, that an individual at node $2$ ``plays $b^{2}$'' if he is programmed (by his ``genes'') to play $b^{2}$ whenever he is in a situation to choose between $c^{2}$ and $b^{2}$.} If everyone at node $1$ plays $b^{1}$ and everyone at node $2$ plays $b^{2}$, then any mutant in population $1$ that plays $c^{1}$ will get a payoff of $1$ instead of $2$, so selection will wipe him out; the same goes for any mutant at node $2$. Therefore the backward induction equilibrium $b$ is ``stable.'' Now assume that we are in the $c$ equilibrium: All the individuals at $1$ play $c^{1}$ and all the individuals at $2$ play $c^{2}$. Again, a mutant at $1$ loses relative to his population: He gets $0$ (since the individuals at $2$ that he will meet play $c^{2}$) instead of $1$. But now a mutant at $2$ that plays $b^{2}$ gets the same payoff as a $c^{2}$-individual, so selection has no effect at node $2$. Since node $2$ is not reached, all actions at $2$ yield the same payoff; there is no ``evolutionary pressure'' at $2$. Mutations in the population at $2$, because they are not wiped out, keep accumulating (this is called ``genetic drift''). Eventually, after a sufficiently long time,\footnote{% The assumption is that mutations have positive---though small---probability at each period.} more than half the population at $2$ will consist of $b^{2}$% -individuals. At this point the action $b^{1}$ at $1$ gets a higher expected payoff than the action $c^{1}$, and thus selection at $1$ favors $b^{1}$. So the proportion of $b^{1}$ at node $1$ becomes positive (and increases), which renders node $2$ reachable. Once $2$ is reached, evolutionary pressure there---i.e., selection---becomes effective, and it moves population $2$ towards the better strategy $b^{2}$. This only increases the advantage of $% b^{1}$ over $c^{1}$, and the whole system gets to the $b=(b^{1},b^{2})$ equilibrium. To summarize: In $\Gamma _{1}$, evolutionary dynamics lead necessarily to $b$% , the backward induction equilibrium; in other words, $b$ is the evolutionarily stable equilibrium. The next example is the $3$-player game $\Gamma _{2}$ of Figure \ref{ex2} %TCIMACRO{\TeXButton{BeginFigure-ex2}{\begin{figure}[tb] \centering}} %BeginExpansion \begin{figure}[tb] \centering% %EndExpansion %TCIMACRO{ %\TeXButton{ex2}{ %\unitlength 1.00mm % %\begin{picture}(70.00,92.00)(5,-2) %\linethickness{1.0pt} %\put(30.00,80.00){\line(1,-1){20.00}} %\put(50.00,60.00){\line(1,-1){20.00}} %\put(50.00,60.00){\line(-1,-1){20.00}} %\put(30.00,80.00){\circle*{1.50}} %\put(50.00,60.00){\circle*{1.50}} %\put(30.00,84.00){\makebox(0,0)[cc]{$1$}} %\put(52.00,63.00){\makebox(0,0)[cc]{$2$}} %\put(30.00,80.00){\line(-1,-1){20.00}} %\put(10.00,56.00){\makebox(0,0)[cc]{$0$}} %\put(10.00,51.00){\makebox(0,0)[cc]{$0$}} %\put(70.00,36.00){\makebox(0,0)[cc]{$1$}} %\put(70.00,31.00){\makebox(0,0)[cc]{$1$}} %\put(19.00,73.00){\makebox(0,0)[cc]{$c^1$}} %\put(42.00,73.00){\makebox(0,0)[cc]{$b^1$}} %\put(39.00,53.00){\makebox(0,0)[cc]{$c^2$}} %\put(62.00,53.00){\makebox(0,0)[cc]{$b^2$}} %\put(30.00,40.00){\line(1,-1){20.00}} %\put(30.00,40.00){\line(-1,-1){20.00}} %\put(30.00,40.00){\circle*{1.50}} %\put(28.00,43.00){\makebox(0,0)[cc]{$3$}} %\put(8.00,16.00){\makebox(0,0)[cc]{$-1$}} %\put(9.70,11.00){\makebox(0,0)[cc]{$5$}} %\put(48.00,16.00){\makebox(0,0)[cc]{$-1$}} %\put(48.00,11.00){\makebox(0,0)[cc]{$-1$}} %\put(19.00,33.00){\makebox(0,0)[cc]{$c^3$}} %\put(42.00,33.00){\makebox(0,0)[cc]{$b^3$}} %\put(10.00,46.00){\makebox(0,0)[cc]{$0$}} %\put(70.00,26.00){\makebox(0,0)[cc]{$1$}} %\put(8.00,6.00){\makebox(0,0)[cc]{$-1$}} %\put(49.70,6.00){\makebox(0,0)[cc]{$5$}} %\end{picture} %}} %BeginExpansion \unitlength 1.00mm \begin{picture}(70.00,92.00)(5,-2) \linethickness{1.0pt} \put(30.00,80.00){\line(1,-1){20.00}} \put(50.00,60.00){\line(1,-1){20.00}} \put(50.00,60.00){\line(-1,-1){20.00}} \put(30.00,80.00){\circle*{1.50}} \put(50.00,60.00){\circle*{1.50}} \put(30.00,84.00){\makebox(0,0)[cc]{$1$}} \put(52.00,63.00){\makebox(0,0)[cc]{$2$}} \put(30.00,80.00){\line(-1,-1){20.00}} \put(10.00,56.00){\makebox(0,0)[cc]{$0$}} \put(10.00,51.00){\makebox(0,0)[cc]{$0$}} \put(70.00,36.00){\makebox(0,0)[cc]{$1$}} \put(70.00,31.00){\makebox(0,0)[cc]{$1$}} \put(19.00,73.00){\makebox(0,0)[cc]{$c^1$}} \put(42.00,73.00){\makebox(0,0)[cc]{$b^1$}} \put(39.00,53.00){\makebox(0,0)[cc]{$c^2$}} \put(62.00,53.00){\makebox(0,0)[cc]{$b^2$}} \put(30.00,40.00){\line(1,-1){20.00}} \put(30.00,40.00){\line(-1,-1){20.00}} \put(30.00,40.00){\circle*{1.50}} \put(28.00,43.00){\makebox(0,0)[cc]{$3$}} \put(8.00,16.00){\makebox(0,0)[cc]{$-1$}} \put(9.70,11.00){\makebox(0,0)[cc]{$5$}} \put(48.00,16.00){\makebox(0,0)[cc]{$-1$}} \put(48.00,11.00){\makebox(0,0)[cc]{$-1$}} \put(19.00,33.00){\makebox(0,0)[cc]{$c^3$}} \put(42.00,33.00){\makebox(0,0)[cc]{$b^3$}} \put(10.00,46.00){\makebox(0,0)[cc]{$0$}} \put(70.00,26.00){\makebox(0,0)[cc]{$1$}} \put(8.00,6.00){\makebox(0,0)[cc]{$-1$}} \put(49.70,6.00){\makebox(0,0)[cc]{$5$}} \end{picture} % %EndExpansion \caption{The game $\Gamma _2$\label{ex2}}% %TCIMACRO{\TeXButton{EndFigure}{\end{figure}}} %BeginExpansion \end{figure}% %EndExpansion (see N\"{o}ldeke and Samuelson [1993] or Samuelson [1997, Example 8.2]). The backward induction equilibrium is $b=\left( b^{1},b^{2},b^{3}\right) $; the other pure Nash equilibrium---which is not perfect---is $% c=(c^{1},c^{2},c^{3})$. Start from a state where all individuals at each node $i$ play their backward induction action $b^{i}$. Nodes $1$ and $2$ are reached, whereas node $3$ is not. Therefore there is no selection operating at node $3$, and mutations move the population at $3$ randomly. As long as the proportion of $b^{3}$ is at least $2/3$, the system is in equilibrium. Once it goes below $2/3$, the best-reply of $2$ becomes $c^{2}$; selection then moves the population at $2$ toward $c^{2}$. But then node $3$ is no longer unreached, so selection starts affecting the population at $3$% ---towards the best-reply there, $b^{3}$. Thus, as soon as the proportion of $b^{3}$ drops below $2/3$, the evolutionary dynamic immediately pushes it back up; it is as if there is a ``reflecting barrier'' below the $2/3$ mark. All this happens fast enough that the population at $1$, which is playing $% b^{1}$, can move only a little, if at all. Therefore we have essentially shown that the equilibrium component\footnote{% Two (mixed) Nash equilibria belong to the same (\emph{equilibrium})\emph{\ component} if their equilibrium paths coincide, and they differ only at unreached nodes.} of $b$---where $b^{i}$ is played at $i=1,2$ and $b^{3}$ is played at $3$ with proportion at least $2/3$---is evolutionarily stable. Moreover, since $b$ and its component must eventually be reached from any state---by appropriate mutations---it follows that other equilibria, in particular $c$, are \emph{not} stable. This conclusion is in contrast to the result of N\"{o}ldeke and Samuelson [1993]: In their model,\footnote{% The main difference between their model and ours is that each one of their individuals, in addition to playing a pure action (as ours do), has conjectures about the composition of the populations at all nodes, whether reached or not. The dynamic then affects both actions and conjectures. In a biological world, it is hard to see how such conjectures are encoded into genes; our individuals are therefore characterized by their actions only.} the non-subgame-perfect equilibrium $c$ also belongs to the stable set. Consider now another $3$-player game: the game $\Gamma _{3}$ given in Figure \ref{ex3}% %TCIMACRO{\TeXButton{BeginFigure-ex3}{\begin{figure}[tb] \centering}} %BeginExpansion \begin{figure}[tb] \centering% %EndExpansion %TCIMACRO{ %\TeXButton{ex3}{ %\unitlength 1.00mm % %\begin{picture}(72.00,92.00)(5,-2) %\linethickness{1.0pt} %\put(50.00,80.00){\line(-1,-1){20.00}} %\put(30.00,60.00){\line(-1,-1){20.00}} %\put(30.00,60.00){\line(1,-1){20.00}} %\put(50.00,80.00){\circle*{1.50}} %\put(30.00,60.00){\circle*{1.50}} %\put(50.00,84.00){\makebox(0,0)[cc]{$1$}} %\put(28.00,63.00){\makebox(0,0)[cc]{$2$}} %\put(50.00,80.00){\line(1,-1){20.00}} %\put(70.00,56.00){\makebox(0,0)[cc]{$4$}} %\put(70.00,51.00){\makebox(0,0)[cc]{$0$}} %\put(10.00,36.00){\makebox(0,0)[cc]{$5$}} %\put(10.00,31.00){\makebox(0,0)[cc]{$9$}} %\put(62.00,73.00){\makebox(0,0)[cc]{$b^1$}} %\put(39.00,73.00){\makebox(0,0)[cc]{$c^1$}} %\put(42.00,53.00){\makebox(0,0)[cc]{$b^2$}} %\put(19.00,53.00){\makebox(0,0)[cc]{$c^2$}} %\put(50.00,40.00){\line(-1,-1){20.00}} %\put(50.00,40.00){\line(1,-1){20.00}} %\put(50.00,40.00){\circle*{1.50}} %\put(52.00,43.00){\makebox(0,0)[cc]{$3$}} %\put(70.00,16.00){\makebox(0,0)[cc]{$0$}} %\put(69.00,11.00){\makebox(0,0)[cc]{$10$}} %\put(30.00,16.00){\makebox(0,0)[cc]{$0$}} %\put(30.00,11.00){\makebox(0,0)[cc]{$0$}} %\put(62.00,33.00){\makebox(0,0)[cc]{$b^3$}} %\put(39.00,33.00){\makebox(0,0)[cc]{$c^3$}} %\put(70.00,46.00){\makebox(0,0)[cc]{$0$}} %\put(10.00,26.00){\makebox(0,0)[cc]{$0$}} %\put(70.00,6.00){\makebox(0,0)[cc]{$1$}} %\put(30.00,6.00){\makebox(0,0)[cc]{$0$}} %\end{picture} %}} %BeginExpansion \unitlength 1.00mm \begin{picture}(72.00,92.00)(5,-2) \linethickness{1.0pt} \put(50.00,80.00){\line(-1,-1){20.00}} \put(30.00,60.00){\line(-1,-1){20.00}} \put(30.00,60.00){\line(1,-1){20.00}} \put(50.00,80.00){\circle*{1.50}} \put(30.00,60.00){\circle*{1.50}} \put(50.00,84.00){\makebox(0,0)[cc]{$1$}} \put(28.00,63.00){\makebox(0,0)[cc]{$2$}} \put(50.00,80.00){\line(1,-1){20.00}} \put(70.00,56.00){\makebox(0,0)[cc]{$4$}} \put(70.00,51.00){\makebox(0,0)[cc]{$0$}} \put(10.00,36.00){\makebox(0,0)[cc]{$5$}} \put(10.00,31.00){\makebox(0,0)[cc]{$9$}} \put(62.00,73.00){\makebox(0,0)[cc]{$b^1$}} \put(39.00,73.00){\makebox(0,0)[cc]{$c^1$}} \put(42.00,53.00){\makebox(0,0)[cc]{$b^2$}} \put(19.00,53.00){\makebox(0,0)[cc]{$c^2$}} \put(50.00,40.00){\line(-1,-1){20.00}} \put(50.00,40.00){\line(1,-1){20.00}} \put(50.00,40.00){\circle*{1.50}} \put(52.00,43.00){\makebox(0,0)[cc]{$3$}} \put(70.00,16.00){\makebox(0,0)[cc]{$0$}} \put(69.00,11.00){\makebox(0,0)[cc]{$10$}} \put(30.00,16.00){\makebox(0,0)[cc]{$0$}} \put(30.00,11.00){\makebox(0,0)[cc]{$0$}} \put(62.00,33.00){\makebox(0,0)[cc]{$b^3$}} \put(39.00,33.00){\makebox(0,0)[cc]{$c^3$}} \put(70.00,46.00){\makebox(0,0)[cc]{$0$}} \put(10.00,26.00){\makebox(0,0)[cc]{$0$}} \put(70.00,6.00){\makebox(0,0)[cc]{$1$}} \put(30.00,6.00){\makebox(0,0)[cc]{$0$}} \end{picture} % %EndExpansion \caption{The game $\Gamma _3$\label{ex3}}% %TCIMACRO{\TeXButton{EndFigure}{\end{figure}}} %BeginExpansion \end{figure}% %EndExpansion . The backward induction equilibrium is $b$, at which both nodes $2$ and $3$ are unreached. The populations at $2$ and $3$ therefore move by mutations. Eventually, when the proportion of $b^{2}$ at node $2$ goes below $1/5$, selection at $1$ will move the population at $1$ from $b^{1}$ to $c^{1}$. At that point both $2$ and $3$ are reached, and which action of $2$ is the best-reply at $2$ depends on the composition of the population at $3$. If less than $9/10$ of them play $b^{3}$ (which is possible, and even quite probable,\footnote{% We take ``quite probable'' to mean that the probability of its happening is positive and bounded away from zero (as the rate of mutation goes to zero).} given that only random mutations have affected $3$ until now), then $c^{2}$ is the best-reply at $2$, and selection keeps decreasing the proportion of $% b^{2}$. Again, it is quite probable for the proportion of $b^{2}$ to get all the way down to $0$ (from $1/5$) long before the proportion of $b^{3}$ at $3$ has increased to $9/10$. What this discussion shows is that, in the game $% \Gamma _{3}$, the non-subgame-perfect equilibrium $c$ (together with its equilibrium component) cannot be ruled out; evolutionary dynamic systems may well be in such states a positive fraction of the time. However, we claim that such behavior \emph{cannot occur if the populations are large enough}. \subsection{This Paper\label{ss-this-paper}} As stated above, the games we study in this paper are finite extensive-form games with perfect information. We assume that the backward induction equilibrium is unique; this holds when the game is generic (i.e., in almost every game). At each node there is a distinct population of individuals that play the game in the role of the corresponding player. Each individual is fully characterized by his action, i.e., by the pure choice that he makes at his node (of course, this goes into effect only if his node is reached% \footnote{% This action is thus the individual's ``genotype''---the hard-wired programming by the genes; it becomes his ``phenotype''---his actual revealed behavior---when his node is reached and it is his turn to play.}). We will refer to such a population game as a ``gene-normal form'' (it parallels the ``agent-normal form''). The games are analyzed in a dynamic framework. The model is as follows: At each period, one individual is chosen at random\footnote{% Uniformly, i.e., each individual has the same probability of being chosen.} in each population. His current action, call it $a^{i}$, may then change by selection, by mutation, or it may not change at all. Selection replaces $% a^{i}$ by another action which, against the other populations currently playing the game (i.e., ``against the field''), yields a higher payoff than $% a^{i}$. Of course, this can only be if such a better action exists; if there are many, one of them is chosen at random. Mutation replaces $a^{i}$ by an arbitrary action, chosen at random. Finally, all the choices at each node are made independently. This model---to which we refer as the ``basic model''---is essentially a most elementary process that provides for both adaptive selection and mutation. It turns out that the exact probabilities of all the above choices do not matter; what is essential is that all of them be bounded away from zero (this is the ``general model''). Since such dynamics yield an ergodic system,\footnote{% Mutations make every state reachable from any other state.} the long-run behavior is well described by the corresponding (unique) invariant distribution, which, for each state, gives the (approximate) frequency of that state's occurrence during any large time interval. The mutations are rare; we are therefore interested in those states which occur with positive frequency however low the mutation rate is.\footnote{% More precisely, states whose probability, according to the invariant distribution, is bounded away from zero as the probability of mutation goes to zero.} Such states are called ``evolutionarily stable.'' Two preliminary results are that only Nash equilibria can be evolutionarily stable, and that the backward induction equilibrium is always evolutionarily stable. The examples show that other Nash equilibria may however be evolutionarily stable as well. We therefore add another factor: The populations are large. This yields: \begin{quote} \textbf{Main Result.} \emph{The backward induction equilibrium becomes in the limit the only evolutionarily stable outcome as the mutation rate decreases to zero and the populations increase to infinity.\footnote{% With an additional proviso that the population sizes be large enough, depending on the mutation rate; see the precise statement in Subsection \ref {ss-main-result}.}} \end{quote} \noindent In other words: Evolutionary dynamic systems, consisting of adaptive selection and rare mutations, lead in large populations to most of the individuals most of the time playing their backward induction strategy. Observe that this applies to reached as well as to unreached nodes; for example, in game $\Gamma _{2}$ we have most of the individuals at all nodes $% i$---\emph{including} node $3$---playing $b^{i}$. Evolutionary stability in large populations picks out not merely the equilibrium component of $b$, but $b$ itself.\footnote{% Actually, an arbitrarily small neighborhood of $b$.} The intuition for the role of the large population assumption will be provided in Subsection \ref {ss-intuition} below. Suffice it to say here that it has to do with a change of action (whether by mutation or selection) being less likely for a specific individual than for an arbitrary individual in a large population. This leads to considerations of ``sequential'' rather than ``simultaneous'' mutations. As a further consequence, unlike most of the evolutionary game-theoretic literature,\footnote{% An exception is N\"{o}ldeke and Samuelson [1995].} our result does \emph{not} rely on comparing different \emph{powers} of the infinitesimal mutation rate (which require extremely long waiting times); single mutations suffice.% \footnote{% The static notion of an ``evolutionarily stable strategy'' is also based on single mutations.} To conclude the introduction, we note that two almost diametrically opposed approaches each lead to the backward induction equilibrium. One approach (Aumann [1995]), in the realm of full rationality, assumes that all players are rational (i.e., they never play something which they know is not optimal), and moreover assumes that this fact is commonly known to them (i.e., each player knows that everyone is rational, and also knows that everyone knows that everyone is rational, and so on). The other approach (this paper), in the realm of evolutionary dynamics, is essentially machinelike and requires no conscious optimization or rationality.\footnote{% The biological mechanisms of selection are entirely automatic; other selection processes (like learning, imitation, and so on) may well use some form of rationality or ``bounded rationality.''} It is striking that such disparate models converge.\footnote{% For an interesting discussion of these matters, see Aumann [1998] (in particular pages 191--195).} The paper is organized as follows: Section \ref{s-model} presents the model: the extensive form game (in Subsection \ref{ss-game}), the associated population game (in Subsection \ref{ss-gene-normal}), and the evolutionary dynamics (in Subsection \ref{ss-dynamics}). The results are stated in Section \ref{s-results}, which also includes the proof of the preliminary result for fixed populations (in Subsection \ref{ss-preliminary-result}). The Main Result, stated in Subsection \ref{ss-main-result}, is proved in Section \ref{s-proof}. The intuition behind our result is presented in Subsection \ref{ss-intuition}, followed by an informal outline of the proof (in Subsection \ref{ss-outline}). We conclude in Section \ref{s-discussion} with a discussion of various issues, including possible extensions and generalizations of our results. \section{The Model\label{s-model}} \subsection{The Game\label{ss-game}} Let $\Gamma $ be a finite extensive-form game with perfect information. We are thus given a rooted tree; each non-terminal vertex corresponds to a \emph{move}. It may be a chance move, with fixed positive probabilities for all outgoing branches; or a move of one of the players, in which case the vertex will be called a \emph{node}. The set of nodes is denoted $N$. It is convenient to view the game in ``agent-normal form'': At each node there is a different agent, and a player consists of a number of agents with identical payoff functions. For each node $i\in N$, the agent there---called ``agent $i$''---has a set of choices $A^{i}$, which is the set of outgoing branches at $i$. We refer to $a^{i}$ in $A^{i}$ as an \emph{action }of $i$, and we put $A:=\prod_{i\in N}A^{i}$ for the set of $N$-tuples of actions. At each terminal vertex (a \emph{leaf}) there are associated payoffs to all agents; let\footnote{$\Bbb{R}$ is the real line.} $u^{i}:A\rightarrow \Bbb{R} $ be the resulting payoff function of agent $i$ (i.e., for each $a=\left( a^{j}\right) _{j\in N}\in A$: if there are no chance moves, then $u^{i}(a)$ is the payoff of $i$ at the leaf that is reached when every agent $j\in N$ chooses $a^{j}$; if there are chance moves, it is the appropriate expectation). Of course, if $i$ and $j$ are agents of the same player, then $% u^{i}\equiv u^{j}$. As usual, the payoff functions are extended multi-linearly to \emph{randomized }(or \emph{mixed}) actions; thus $% u^{i}:X\rightarrow \Bbb{R}$, where $X:=\prod_{i\in N}X^{i}$ and $% X^{i}:=\Delta (A^{i})=\left\{ x^{i}\in \Bbb{R}_{+}^{A^{i}}:\sum_{a^{i}\in A^{i}}x_{a^{i}}^{i}=1\right\} $, the unit simplex on $A^{i}$, is the set of probability distributions over $A^{i}$. For each node $i\in N$, let $N(i)$ be the set of nodes that are successors (not necessarily immediate) of $i$ in the tree, and let $\Gamma (i)$ be the subgame of $\Gamma $ starting at the node $i$. For example, if $1\in N$ is the root then $N(1)=N\backslash \{1\}$ and $\Gamma (1)=\Gamma $; in general, $j\in N(i)$ if and only if the unique path from the root to $j$ goes through $i$, and the set of nodes of $\Gamma (i)$ is $N(i)\cup \{i\}$. An $N$-tuple of randomized actions $x=\left( x^{i}\right) _{i\in N}\in X$ is a \emph{Nash equilibrium} of\emph{\ }$\Gamma $ if\footnote{% We write $x^{-i}$ for the $\left( \left| N\right| -1\right) $-tuple of actions of the other agents, i.e., $x^{-i}=\left( x^{j}\right) _{j\in N\backslash \{i\}}.$} $u^{i}(x)\geq u^{i}(y^{i},x^{-i})$ for every $i\in N$ and every $y^{i}\in X^{i}$. It is moreover a \emph{subgame-perfect }(or \emph{backward induction}) \emph{equilibrium }of $\Gamma $ if it is a Nash equilibrium in each subgame $\Gamma (i)$, for all $i\in N$. This is equivalent to each $x^{i}$ being a best-reply of $i$ in $\Gamma (i)$ when every $j\in N(i)$ plays $x^{j}$. Such an equilibrium is therefore obtained by \emph{backward induction, }starting from the final nodes (those nodes $i$ with no successors, i.e., with $N(i)=\emptyset $) and going towards the root. We will denote by $EQ$ and $BI$ the set of Nash equilibria and the set of backward induction equilibria, respectively, of the game $\Gamma $; thus $% BI\subset EQ\subset X$. At this point it is useful to point out the distinction between a best-reply of $i$ in the whole game $\Gamma $---which we call a \emph{global best-reply}% ---and a best-reply of $i$ in the subgame $\Gamma (i)$---which we call a \emph{local best-reply. }Thus a local best-reply is always a global best-reply, but the converse is not necessarily true.\footnote{% One should not get confused with the parallel notions for optima (where global implies local).} If $i$ is reached (i.e., when all agents on the path from the root to $i$ make the choice along the path with positive probability), then the two notions coincide. If $i$ is not reached, then the payoff of $i$ in $\Gamma $ is independent of his action, and thus every action in $A^{i}$ (and every mixed action in $X^{i})$ is a global best-reply of $i$ (but not necessarily a local best-reply). The difference between a Nash equilibrium and a subgame-perfect equilibrium is precisely that in the former each action of an agent that is played with positive probability is a global best-reply to the others' (mixed) actions, whereas in the latter it is additionally a local best-reply. The classical result of Kuhn [1953] states that there always exists a \emph{% pure} backward induction equilibrium; the proof constructs it by backward induction. We assume here that the game $\Gamma $ has a \emph{unique }% backward induction equilibrium, which must therefore be pure; we denote it% \emph{\ }$b=\left( b^{i}\right) _{i\in N}\in A$, and refer to $b^{i}$ as the ``backward induction action of $i$.'' This uniqueness is true generically, i.e., for almost every game. For instance, when there are no chance moves, it suffices for each player to have different payoffs at different leaves. \subsection{The Gene-Normal Form\label{ss-gene-normal}} We now consider a \emph{population game} associated to $\Gamma $: At each node $i\in N$ there is a non-empty population $M(i)$ of individuals playing the game in the role of player $i$. The populations are assumed to be distinct (i.e., $M(i)\cap M(j)=\emptyset $ for $i\neq j$). Each individual $% q\in M(i)$ plays a pure action in $A^{i}$, which we denote by $\omega _{q}^{i}\in A^{i}$; put $\omega ^{i}=\left( \omega _{q}^{i}\right) _{q\in M(i)}$ and $\omega =\left( \omega ^{i}\right) _{i\in N}$. For each $a^{i}\in A^{i}$, let\footnote{$\left| Z\right| $ denotes the number of elements of the finite set $Z.$} \begin{equation} x_{a^{i}}^{i}\equiv x_{a^{i}}^{i}\left( \omega ^{i}\right) :=\frac{\left| \left\{ q\in M(i):\omega _{q}^{i}=a^{i}\right\} \right| }{\left| M(i)\right| } \label{eq-f} \end{equation} be the proportion of population $M(i)$ that plays the action $a^{i}$; then $% x^{i}\equiv x^{i}\left( \omega ^{i}\right) :=\left( x_{a^{i}}^{i}\left( \omega ^{i}\right) \right) _{a^{i}\in A^{i}}\in X^{i}$ may be viewed as a mixed action of $i$. The payoff of an individual $q\in M(i)$ is defined as his average payoff against the other populations, i.e., $u^{i}(\omega _{q}^{i},x^{-i})$; we shall slightly abuse notation by writing this as $% u^{i}(\omega _{q}^{i},\omega ^{-i})$. We refer to the above model as the \emph{gene-normal form of }$\Gamma $\emph{% \ }(it is the counterpart, in population games, of the ``agent-normal form''). This model is clear and needs no explanation when all the players in $\Gamma $ are distinct (i.e., each player plays at most once in $\Gamma $). When however a player may play more than once (and thus has more than one agent), then the ``biological'' interpretation is as follows: Each one of the player's decisions (i.e., each one of his agents $i$) is controlled by a ``gene,'' whose various ``alleles'' correspond to the possible choices at node $i$ (i.e., the set of alleles of gene $i$ is precisely $A^{i})$. The genes of different nodes $i$ and $j$ of the same player are distinct (i.e., at different locations, or ``loci''); were it the same gene, then the player would behave identically at the two nodes---and the appropriate representation should have the two nodes $i$ and $j$ in the same information set.\footnote{% One would thus get a game of imperfect information, where information sets are not necessarily singletons. Moreover, observe that here a path may intersect an information set more than once; we are thus led naturally to ``games of imperfect recall.''}$^{,}$\footnote{% A case where, say, the decision at $i$ is controlled by the two genes in locations $1$ and $2,$ and the decision at $j$ by the two genes in locations $2$ and $3,$ is not allowed here.} For a discussion of these issues and their import, the reader is referred to Subsection \ref{ss-agents}. \subsection{The Dynamics\label{ss-dynamics}} We come now to the dynamic model. A \emph{state }$\omega $ of the system specifies the pure action of each individual in each population; i.e., $% \omega =\left( \omega ^{i}\right) _{i\in N}$, where $\omega ^{i}=\left( \omega _{q}^{i}\right) _{q\in M(i)}$ and $\omega _{q}^{i}\in A^{i}$ for each $i\in N$ and each $q\in M(i)$. Let $\Omega :=\prod_{i\in N}\left( A^{i}\right) ^{M(i)}$ be the state space. We consider discrete-time stochastic systems: Starting with an initial state\footnote{% As we shall see below, the process is ergodic; thus, in the long run, the starting state does not matter. Hence there will be no need to specify it.} $% \omega _{1}\in \Omega $, a sequence of states $\omega _{1},\omega _{2},...,\omega _{t},...$ in $\Omega $ is generated, according to certain probabilistic rules. These so-called ``transition probabilities'' specify, for each $t=1,2,...,$ the probabilities $P\left[ \omega _{t+1}=\widetilde{% \omega }\mid \omega _{1},...,\omega _{t}\right] $ that $\omega _{t+1}$ equals a state $\widetilde{\omega }\in \Omega $, given the history $\omega _{1},\omega _{2},...,\omega _{t}$. Our processes will be \emph{stationary Markov chains}: The transition probabilities depend only on $\omega _{t}$, the state in the previous period (and depend neither on the other past states $\omega _{1},...,\omega _{t-1}$, nor on the ``calendar time'' $t$). That is, there is a stochastic matrix\footnote{% I.e., $Q\left[ \widetilde{\omega }\mid \omega \right] \geq 0$ for all $% \widetilde{\omega },\omega \in \Omega $ and $\sum_{\widetilde{\omega }\in \Omega }Q\left[ \widetilde{\omega }\mid \omega \right] =1$ for every $\omega \in \Omega .$} $Q=\left( Q\left[ \widetilde{\omega }\mid \omega \right] \right) _{\widetilde{\omega },\omega \in \Omega }$ such that $P\left[ \omega _{t+1}=\widetilde{\omega }\mid \omega _{1},...,\omega _{t}\right] =Q\left[ \widetilde{\omega }\mid \omega _{t}\right] $ for every $\omega ,\widetilde{% \omega }\in \Omega $ and $t=1,2,...$. The matrix $Q$ is called \emph{the one-step transition probability matrix.} We present first a simple dynamic model, which we call the \emph{basic model}% . Assume that all populations are of equal size, say $m=\left| M(i)\right| $ for each $i\in N$. Let $\mu >0$ and $\sigma >0$ be given, such that $\mu +\sigma \leq 1$. The one-step transition probabilities $Q\left[ \widetilde{% \omega }\mid \omega \right] $ are given by the following process, performed independently for each $i\in N$: \begin{itemize} \item Choose a player $q(i)\in M(i)$ at random: All $m$ players in $M(i)$ have the same probability $1/m$ of being chosen. \item Put $\widetilde{\omega }_{q}^{i}:=\omega _{q}^{i}$ for each $q\in M(i),q\neq q(i)$; i.e., all individuals in $M(i)$ except $q(i)$ do not change their actions. \item Choose one of SE$\left( i\right) $ (``selection''), MU$\left( i\right) $ (``mutation'') and NC$\left( i\right) $ (``no change''), with probabilities $\sigma ,\mu $ and $1-\mu -\sigma $, respectively. \item If selection SE$\left( i\right) $ was chosen, then define \begin{equation} B^{i}\equiv B^{i}\left( q(i),\omega \right) :=\left\{ a^{i}\in A^{i}:u^{i}(a^{i},\omega ^{-i})>u^{i}(\omega _{q(i)}^{i},\omega ^{-i})\right\} ; \label{eq-Bi} \end{equation} this is the set of actions of player $i$ that are strictly better in $\Gamma $, against the populations at the other nodes, than the action $\omega _{q(i)}^{i}$ of the chosen player $q(i)$. If $B^{i}$ is not empty, then the new action $\widetilde{\omega }_{q(i)}^{i}$ of $q(i)$ is a randomly chosen better action: $\widetilde{\omega }_{q(i)}^{i}:=a^{i}$ with probability $% 1/\left| B^{i}\right| $ for each $a^{i}\in B^{i}$. If $B^{i}$ is empty, then there is no change in $q(i)$'s action: $\widetilde{\omega }% _{q(i)}^{i}:=\omega _{q(i)}^{i}$. \item If mutation MU$\left( i\right) $ was chosen, then $\widetilde{\omega }% _{q(i)}^{i}$ is a random action in $A^{i}$; i.e., $\widetilde{\omega }% _{q(i)}^{i}:=a^{i}$ with probability $1/\left| A^{i}\right| $ for each $% a^{i}\in A^{i}$. \item If no-change NC$\left( i\right) $ was chosen, then the action of $% q(i) $ does not change: $\widetilde{\omega }_{q(i)}^{i}:=\omega _{q(i)}^{i}$. \end{itemize} For example, in the game $\Gamma _{1}$ of Subsection \ref{ss-examples} (see Figure \ref{ex1}; here $N=\{1,2\},A^{1}=\{c^{1},b^{1}\},A^{2}=\{c^{2},b^{2}% \} $), with populations of size $m=3$, let $\omega =\left( (c^{1},c^{1},c^{1}),(b^{2},b^{2},c^{2})\right) $ and $\widetilde{\omega }% =\left( \left( b^{1},c^{1},c^{1}\right) ,\left( b^{2},b^{2},b^{2}\right) \right) $, then $Q\left[ \widetilde{\omega }\mid \omega \right] =(1/3)\cdot (\mu /2+\sigma )\cdot (1/3)\cdot \left( \mu /2\right) $. Indeed, the probability that $q(1)=1$ is $1/3$; then $c^{1}$ changes to $b^{1}$ either by mutation, with probability $\mu \cdot (1/2)$, or by selection (since $% B^{1}=\{b^{1}\}$), with probability $\sigma $; similarly, the probability that $q(2)=3$ is $1/3$, and then $c^{2}$ changes to $b^{2}$ by mutation only (since $B^{2}=\emptyset $), with probability $\mu \cdot (1/2)$. A few remarks are now in order.\medskip \textbf{Remarks.} \begin{enumerate} \item We have assumed that in each period there is at most one individual in each population that may change his action. This defines what is meant by ``one period'': It is that time interval which is small enough that the probability of more than one individual changing his action in the same period is (relatively) negligible.\footnote{% Our results do not need simultaneous mutations; they may indeed be ignored.} This is a standard construct in stochastic setups (recall, for instance, the construction of the Poisson distribution as an approximation to the binomial distribution). Our assumption may thus be viewed as essentially nothing more than a convenient rescaling of time; if one expects, say, $k$ changes each period, then time should be rescaled by a factor of $1/k$. As we shall see below (in particular in Subsection \ref{ss-intuition}), our arguments are based on \emph{comparing} occurrence times, and are thus independent of the units in which time is measured. \item The difference between mutation and selection is that mutation is ``blind''---in the sense that \emph{all} actions are possible---whereas selection is ``directional''---\emph{only better} actions are possible. We emphasize that ``better'' is understood---as it should be---with respect to the payoffs in the whole game, i.e., ``globally better.'' Of course, ``selection'' may stand for various processes of adaptation, imitation, learning, experimentation, and so on. Our model abstracts away from particular selection mechanisms, and merely assumes that better actions fare better. See also Subsection \ref{ss-extensions} for the case where the selection probability of a better action is proportional to its current proportion in the population. \item The basic dynamic is determined by two parameters,\footnote{% Once the game $\Gamma $ and the population size $m$ are given.} $\mu $ and $% \sigma $. As we shall see below, what really matters is that $\mu $ be small relative to $\sigma $; formally, $\mu \rightarrow 0$ while $\sigma >0$ is fixed: Mutations are rare relative to selection. Equivalently, we could well take $\sigma =1-\mu $, and thus have only one parameter. We have preferred to add the no-change case since it allows for more general interpretations. The no-change periods may be viewed as ``payoff accumulation'' periods, or as ``selection realization'' periods (i.e., periods during which the actual selection occurs\footnote{% This may help justify the fact that our selection mechanism is not continuous (any ``better'' action has probability bounded away from zero, whereas an ``equally good'' action has zero probability): Indeed, selection makes even a slightly better action ``win,'' given enough time. See also Subsection \ref{ss-extensions}.}). \item The one-step transition probabilities were defined to be independent over the agents; this just means that the transitions are \emph{% conditionally independent. }In general, the evolution of one population will depend substantially on that of other populations. \end{enumerate} The basic model is essentially a most simple model that captures the evolutionary paradigm of selection and mutation. It may appear however as too specific. Therefore we now present a general class of dynamic models, which will turn out to lead to the same results. The \emph{general model} is as follows: We are given a \emph{mutation rate} parameter $\mu >0$ and populations $M(i)$ at all nodes $i\in N$, which may be of different size at different nodes. The process is a stationary Markov chain, whose one-step transition probability matrix $Q=\left( Q\left[ \widetilde{\omega }\mid \omega \right] \right) _{\widetilde{\omega },\omega \in \Omega }$ satisfies: \begin{itemize} \item Conditional independence over $i\in N$, i.e.,\footnote{% For each $\omega \in \Omega ,$ we view $Q\left[ \cdot \mid \omega \right] $ as a probability distribution over $\Omega $; derived probabilites---like its marginals---will also be denoted by $Q\left[ \cdot \mid \omega \right] .$% } \begin{equation} Q\left[ \widetilde{\omega }\mid \omega \right] =\prod_{i\in N}Q\left[ \widetilde{\omega }^{i}\mid \omega \right] . \label{eq-independence} \end{equation} \item For each $i\in N$, one individual $q(i)\in M(i)$ is chosen, such that there exist constants $\gamma _{1},\gamma _{2}>0$ with \begin{equation} \frac{\gamma _{1}}{\left| M(i)\right| }\leq Q\left[ q(i)=q\mid \omega \right] \leq \frac{\gamma _{2}}{\left| M(i)\right| }\text{ for each }q\in M(i);\text{ and} \label{eq-M} \end{equation} \begin{equation} Q\left[ \widetilde{\omega }_{q}^{i}=\omega _{q}^{i}\text{ for all }q\in M(i)\backslash \{q(i)\}\mid \omega \right] =1. \label{eq-q} \end{equation} \item There exists a constant $\beta >0$ such that, for each $i\in N$, \begin{equation} Q\left[ \widetilde{\omega }_{q(i)}^{i}=a^{i}\mid \omega \right] \geq \beta \text{ for each }a^{i}\in B^{i}, \label{eq-beta} \end{equation} where $B^{i}\equiv B^{i}(q(i),\omega )$ is the set of strictly better actions, as defined in (\ref{eq-Bi}). \item There exist constants $\alpha _{1},\alpha _{2}>0$ such that, for each $i\in N$, \begin{eqnarray} Q\left[ \widetilde{\omega }_{q(i)}^{i}=a^{i}\mid \omega \right] &\geq &\alpha _{1}\mu \text{ for each }a^{i}\in A^{i};\text{ and} \label{eq-mu} \\ Q\left[ \widetilde{\omega }_{q(i)}^{i}=a^{i}\mid \omega \right] &\leq &\alpha _{2}\mu \text{ for each }a^{i}\notin B^{i},a^{i}\neq \omega _{q(i)}^{i}. \label{eq-mu2} \end{eqnarray} \end{itemize} Without loss of generality, all parameters $\alpha _{1},\alpha _{2},\beta ,\gamma _{1},\gamma _{2}$ are taken to be the same for all $i\in N$ (if needed, replace them by the appropriate maximum or minimum over $i)$. To see that the basic model is a special case of the general model, take $\gamma _{1}=\gamma _{2}=1,\beta =\sigma /\left| A^{i}\right| $ and $\alpha _{1}=\alpha _{2}=1/\left| A^{i}\right| $. The general model thus assumes that: (i) the probabilities of various individuals in the same population being chosen are comparable;\footnote{% I.e., the ratios $Q\left[ q(i)=q\mid \omega \right] /Q\left[ q(i)=q^{\prime }\mid \omega \right] $ are uniformly bounded.} (ii) the effect of selection---towards better actions---is bounded away from zero (independently of $\mu $); and (iii) the effect of mutation---with every action being possible---is of the order $\mu $. The reader is referred to Subsections \ref{ss-selection} and \ref{ss-extensions} for generalizations. \section{The Results\label{s-results}} \subsection{Preliminary Results\label{ss-preliminary-result}} A general model with a one-step transition matrix $Q$ satisfying (\ref {eq-independence})--(\ref{eq-mu2}) yields a Markov chain which is \emph{% ergodic}, since the probability of reaching any state $\omega ^{\prime }\in \Omega $ from any other state $\omega \in \Omega $ is positive (this follows from (\ref{eq-M}) and (\ref{eq-mu}), by using an appropriate sequence of mutations). Therefore there exists a unique \emph{invariant distribution} $% \pi $ on $\Omega $; i.e., a unique $\pi \in \Delta (\Omega )$ satisfying $% \pi =\pi Q$, or \[ \pi \left[ \widetilde{\omega }\right] =\sum_{\omega \in \Omega }\pi \left[ \omega \right] Q\left[ \widetilde{\omega }\mid \omega \right] \] for every $\widetilde{\omega }\in \Omega $. The long-run behavior of the process is well described by $\pi $, in the following two senses: \begin{itemize} \item The relative frequency, in any long enough period of time, of the process visiting a state $\omega $, is approximately $\pi \left[ \omega \right] $; i.e., for every $\omega \in \Omega $: \[ \lim_{T_{2}-T_{1}\rightarrow \infty }\frac{\left| \left\{ t:T_{1}0$. Recall that each state $\omega \in \Omega $ may be viewed as an $N$-tuple of mixed actions $x\left( \omega \right) =\left( x^{i}\left( \omega ^{i}\right) \right) _{i\in N}\in X$ (see (\ref{eq-f})). The invariant distribution $\pi $ on $\Omega $ therefore induces a probability distribution\footnote{$\left( x\right) ^{-1}:X\rightarrow \Omega $ denotes the inverse of the mapping $% x:\Omega \rightarrow X.$} $\widehat{\pi }:=\pi \circ \left( x\right) ^{-1}$ over $X$; i.e., $\widehat{\pi }\left[ Y\right] :=\pi \left[ \left\{ \omega \in \Omega :x(\omega )\in Y\right\} \right] $ for every (measurable) $% Y\subset X$. We therefore call an $N$-tuple of mixed actions $x\in X$ \emph{% evolutionarily stable} if there are evolutionarily stable states $\omega \in \Omega $ with $x(\omega )=x$; i.e., if $\lim \inf_{\mu \rightarrow 0}% \widehat{\pi }\left[ x\right] >0$. The following result states that only Nash equilibria can be evolutionarily stable, and that the backward induction equilibrium $b$ is always so. \begin{theorem} \label{th-mu}For each $\mu >0$, let $\pi _{\mu }$ be the unique invariant distribution of a dynamic process given by a one-step transition matrix $% Q\equiv Q_{\mu }$ satisfying (\ref{eq-independence})--(\ref{eq-mu2}). Then \begin{eqnarray*} \lim_{\mu \rightarrow 0}\widehat{\pi }_{\mu }\left[ EQ\right] &=&1,\text{ and% } \\ \stackunder{\mu \rightarrow 0}{\lim \inf }\widehat{\pi }_{\mu }\left[ b\right] &>&0\text{.} \end{eqnarray*} \end{theorem} %TCIMACRO{\TeXButton{Proof}{\proof}} %BeginExpansion \proof% %EndExpansion Assume without loss of generality that $Q_{\mu }\rightarrow Q_{0}$ and $\pi _{\mu }\rightarrow \pi _{0}$ as $\mu \rightarrow 0$ (take a convergent subsequence if needed; recall that the state space $\Omega $ is finite and fixed). The invariance property $\pi _{\mu }=\pi _{\mu }Q_{\mu }$ becomes $% \pi _{0}=\pi _{0}Q_{0}$ in the limit; thus $\pi _{0}$ is an invariant distribution of $Q_{0}$ (but $Q_{0}$ is in general not ergodic, so its invariant distribution is not unique). Now $Q_{0}$ allows no mutations (by (% \ref{eq-mu2}) and $\mu \rightarrow 0$), so only selection applies. Therefore $\omega \in \Omega $ is a Nash equilibrium state (i.e., $x(\omega )\in EQ$) if and only if $\omega $ is an absorbing state of $Q_{0}$ (i.e., $% Q_{0}\left[ \omega \mid \omega \right] =1$); denote by $\Omega _{EQ}$ the subset (of $\Omega $) of all such states. To prove that an absorbing state must always be reached---and thus $\pi _{0}\left[ \Omega _{EQ}\right] =1$% ---we shall show that $Q_{0}$ allows no cycles. Indeed, assume that $\omega _{0},\omega _{1},...,\omega _{t},...,\omega _{T}\in \Omega $ satisfy $\omega _{t}\neq \omega _{t-1}$ and $Q_{0}\left[ \omega _{t}\mid \omega _{t-1}\right] >0$ for every $t=1,...,T$, and $\omega _{T}=\omega _{0}$. At a final node $i\in N$ (i.e., with $N(i)=\emptyset $), selection can only increase the sum of the ``local'' payoffs (in $\Gamma (i)$) of the population $M(i)$, i.e.,\footnote{% We write $u_{\Gamma (i)}^{i}$ for the payoff function of $i$ in the subgame $% \Gamma (i)$.} $\sum_{q\in M(i)}u_{\Gamma (i)}^{i}\left( \omega _{q}^{i}\right) $; therefore $\omega _{T}^{i}=\omega _{0}^{i}$ implies that $% \omega _{t}^{i}=\omega _{0}^{i}$ for all $t$; thus the population at $i$ never moves. The same applies at any node $i$ for which there were no changes at all its descendant nodes $N(i)$; backward induction thus yields $% \omega _{t}^{i}=\omega _{0}^{i}$ for all $t$ and all $i\in N$, a contradiction. Next, we shall show that $\widehat{\pi }_{0}\left[ b\right] >0$. First, we claim that, given two Nash equilibrium states $\omega ,\omega ^{\prime }\in \Omega _{EQ},$ if $\pi _{0}\left[ \omega \right] >0$ and $\omega ^{\prime }$ can be reached from $\omega $ by one mutation step in one population followed by any number of selection steps, then $\pi _{0}\left[ \omega ^{\prime }\right] >0$ too. Indeed, the invariance property $\pi _{\mu }=\pi _{\mu }Q_{\mu }$ implies\footnote{$Q^{k},$ the $k$-th power of the one-step transition probability matrix $Q,$ gives precisely the $k$-steps transition probabilities.} $\pi _{\mu }=\pi _{\mu }Q_{\mu }^{k}$ for any integer $k\geq 1$, and thus \[ \pi _{\mu }\left[ \omega ^{\prime }\right] \geq \pi _{\mu }\left[ \omega ^{\prime }\right] Q_{\mu }^{k}\left[ \omega ^{\prime }\mid \omega ^{\prime }\right] +\pi _{\mu }\left[ \omega \right] Q_{\mu }\left[ \omega ^{\prime \prime }\mid \omega \right] Q_{\mu }^{k-1}\left[ \omega ^{\prime }\mid \omega ^{\prime \prime }\right] , \] where $\omega ^{\prime \prime }$ satisfies $Q_{\mu }\left[ \omega ^{\prime \prime }\mid \omega \right] \geq c_{1}\mu $ for some $c_{1}>0$ (by (\ref {eq-M}) and (\ref{eq-mu}); this is the mutation step) and $Q_{0}^{k-1}\left[ \omega ^{\prime }\mid \omega ^{\prime \prime }\right] =c_{2}>0$ (these are the selection steps; thus $Q_{0}$ rather than $Q_{\mu }$). Also, since $% \omega ^{\prime }$ is a Nash equilibrium state, it can change only by mutations, so $Q_{\mu }^{k}\left[ \omega ^{\prime }\mid \omega ^{\prime }\right] \geq 1-c_{3}\mu $ for an appropriate constant $c_{3}>0$ (by (\ref {eq-mu2})). Therefore $c_{3}\mu \pi _{\mu }\left[ \omega ^{\prime }\right] \geq c_{1}\mu \pi _{\mu }\left[ \omega \right] Q_{\mu }^{k-1}\left[ \omega ^{\prime }\mid \omega ^{\prime \prime }\right] $, which, after dividing by $% \mu $ and then letting $\mu \rightarrow 0$, yields \[ \pi _{0}\left[ \omega ^{\prime }\right] \geq \frac{c_{1}}{c_{3}}\pi _{0}\left[ \omega \right] Q_{0}^{k-1}\left[ \omega ^{\prime }\mid \omega ^{\prime \prime }\right] =\frac{c_{1}c_{2}}{c_{3}}\pi _{0}\left[ \omega \right] >0, \] and thus $\pi _{0}\left[ \omega ^{\prime }\right] >0$. Second, given a final node $i\in N$, we claim that there is a Nash equilibrium state $\omega \in \Omega _{EQ}$ with $\pi _{0}\left[ \omega \right] >0$, at which all the population at $i$ plays the backward induction action $b^{i}$. If not, let $\omega \in \Omega _{EQ}$ be such that $\pi _{0}\left[ \omega \right] >0$ and the proportion $x_{b^{i}}^{i}(\omega )$ of $b^{i}$ is maximal; thus $x_{b^{i}}^{i}(\omega )<1$. Consider a mutation of a non-$b^{i}$-individual into $b^{i}$ (and no changes at all nodes $j\neq i$% ; recall that $\omega \in \Omega _{EQ}$), followed by any number of selection periods until a state $\omega ^{\prime }\in \Omega _{EQ}$ is reached. By the claim of the previous paragraph, we have $\pi _{0}\left[ \omega ^{\prime }\right] >0$. But $x_{b^{i}}^{i}(\omega ^{\prime })>x_{b^{i}}^{i}(\omega )$, since the first mutation step increased this proportion, and the selection steps could not have decreased it; this contradicts our choice of $\omega $. Therefore there are Nash equilibrium states $\omega \in \Omega _{EQ}$ with $\pi _{0}\left[ \omega \right] >0$ and $x_{b^{i}}^{i}(\omega )=1$. The same argument applies at any node $i\in N$ for which there are Nash equilibrium states $\omega \in \Omega _{EQ}$ with $% \pi _{0}\left[ \omega \right] >0$ and $x_{b^{j}}^{j}(\omega )=1$ for all $% j\in N(i)$ (just choose among these states one with maximal $% x_{b^{i}}^{i}(\omega )$). Therefore, by backward induction, we get $\pi _{0}\left[ \omega _{b}\right] >0$ for that state $\omega _{b}\in \Omega _{EQ} $ where $x_{b^{i}}^{i}(\omega _{b})=1$ for all $i\in N$.% %TCIMACRO{\TeXButton{End Proof}{\endproof}} %BeginExpansion \endproof% %EndExpansion We note that the above proof shows that the result of Theorem \ref{th-mu} holds also in the non-generic case where the backward induction equilibrium is not unique (the second statement then applies to each $b\in BI$). \subsection{The Main Result\label{ss-main-result}} As the examples show, other equilibria besides the backward induction equilibrium $b$ (including some that are very different from $b$) may be evolutionarily stable when the populations are fixed. We now consider the case where the populations increase, i.e., $\left| M(i)\right| \rightarrow \infty $ for $i\in N$. Put $\mathbf{m=(}\left| M(i)\right| )_{i\in N}$ for the vector of population sizes; we will refer to $\mathbf{m}$ as the \emph{% population profile}. As $\mathbf{m}\rightarrow \infty $, the state space changes and becomes infinite in the limit; we need therefore\footnote{% The probability of a single point may become $0$ in the limit. For instance, if $1/m$ is much smaller than $\mu $ (i.e., if $m\mu \rightarrow \infty $), then we may well get $\widehat{\pi }[b]\rightarrow 0$ (consider even the simplest $1$-person game: The transition probability from the state $\omega _{0}$ where everyone plays $b,$ to the state $\omega _{1}$ where all but one individual play $b,$ is of the order of $\mu ,$ whereas the transition from $% \omega _{1}$ to $\omega _{0}$ has probability of the order of $1/m$).} to consider (small) neighborhoods of $BI=\{b\}$ in the set of mixed actions $X$% : For every $\varepsilon >0$, put $BI_{\varepsilon }:=\left\{ x\in X:x_{b^{i}}^{i}\geq 1-\varepsilon \text{ for all }i\in N\right\} $. That is, $x$ belongs to the $\varepsilon $-neighborhood $BI_{\varepsilon }$ of $b$ if most of the individuals, in all populations, play their backward induction action; we emphasize that this holds for \emph{all} $i\in N$---whether node $% i$ is reached or not. \begin{theorem}[Main Theorem] \label{th-main}For every mutation rate $\mu >0$ and population profile $% \mathbf{m=(}\left| M(i)\right| )_{i\in N}$ with $m:=\min_{i\in N}\left| M(i)\right| $, let $\pi _{\mu ,\mathbf{m}}$ be the unique invariant distribution of a dynamic process given by a one-step transition matrix $% Q\equiv Q_{\mu ,\mathbf{m}}$ satisfying (\ref{eq-independence})--(\ref {eq-mu2}). Then, for every $\varepsilon >0$ and $\delta >0$, \[ \lim\Sb \mu \rightarrow 0 \\ \mathbf{m}\rightarrow \infty \\ \mu m\geq \delta \endSb \widehat{\pi }_{\mu ,\mathbf{m}}\left[ BI_{\varepsilon }\right] =1. \] Moreover, there exists a constant $c$, depending on the game, on the dynamics parameters $\alpha _{1},\alpha _{2},\beta ,\gamma _{1},\gamma _{2}$% , and on $\varepsilon ,\delta ,$ such that\footnote{$E_{\mu ,\mathbf{m}}$ denotes the expectation with respect to the probability distribution $\pi _{\mu ,\mathbf{m}}.$} \begin{equation} E_{\mu ,\mathbf{m}}\left[ x_{b^{i}}^{i}(\omega )\right] \geq 1-c\mu \text{ for all }i\in N,\text{ and} \label{eq-th-e} \end{equation} \begin{equation} \pi _{\mu ,\mathbf{m}}\left[ x_{b^{i}}^{i}\left( \omega \right) \geq 1-\varepsilon \text{ for all }i\in N\right] \geq 1-c\mu , \label{eq-th-pi} \end{equation} for all $\mu >0$ and all $\mathbf{m=}\left( \left| M(i)\right| \right) _{i\in N}$ with $\left| M(i)\right| \geq \delta /\mu $ for all $i\in N$. \end{theorem} Thus, as the mutation rate is low and the populations are large enough, the proportion of each population $i$ that does not play the backward induction action is small. Hence, in the long run, the dynamic system is most of the time in states where almost every individual plays his backward induction action.\medskip \textbf{Remarks.} \begin{enumerate} \item The only assumption made on the relative rates of convergence of $\mu $ and $m$ is that $\mu m$ is bounded away from $0.$ This implies that \begin{equation} \lim\Sb \mu \rightarrow 0 \endSb \lim_{\mathbf{m}\rightarrow \infty }% \widehat{\pi }_{\mu ,\mathbf{m}}\left[ BI_{\varepsilon }\right] =1 \label{eq-lim2} \end{equation} (however this need not hold for $\lim_{\mathbf{m}\rightarrow \infty }\lim_{\mu \rightarrow 0}$). \item No assumptions are made on the relative population sizes $\left| M\left( i\right) \right| $; one population may well be much larger than another. However, the mutation rates in the different populations are assumed to be of the same order of magnitude---see (\ref{eq-mu}) and (\ref {eq-mu2}). \item The estimates we get in (\ref{eq-th-e}) and (\ref{eq-th-pi}) involve the mutation rate $\mu $ but no higher powers of $\mu $ (as is the case in much of the existing literature, in particular in evolutionary dynamics for games in strategic form). This means that the effect of \emph{simultaneous mutations }(whose probability---a power of $\mu $---is relatively small) may indeed be ignored. Thus our result does not rely on the fact that, when $\mu $ is small, $100$ simultaneous mutations are much more probable than $101$ simultaneous mutations (both of these events are extremely improbable).% \footnote{% In a sense, the comparison here is between different coefficients of $\mu $ (i.e., of $\mu $ to the power $1$), rather than between the first powers of $% \mu $ with non-zero coefficient.} Our proof therefore does not use any of the techniques based on ``counting mutations.'' \end{enumerate} \section{Proof of the Main Theorem\label{s-proof}} \subsection{An Informal Argument\label{ss-intuition}} We begin by presenting informally the main ideas of the proof of our result; in particular, we will explain the role of large populations. We do so for the simpler basic model; the same arguments apply to the general model. Clearly, if a node $i$ is reached (i.e., if at every node along the path from the root to $i$ there are individuals playing the action that corresponds to the path), then mutation MU($i$) at $i$ has probability of the order of $\mu $, which is much smaller\footnote{% We take the term ``$f$ is much smaller than $g$'' to mean that the ratio $% f/g $ goes to $0$ as $\mu \rightarrow 0$ and $m\rightarrow \infty .$} than the probability of selection SE($i$) at $i$. Therefore, at reached nodes most of the individuals play their best-reply actions. (This is essentially the argument of Theorem \ref{th-mu}.) The problem is how to get a similar conclusion at the \emph{unreached }nodes. Consider first the $3$-player game $\Gamma _{2}$ of Figure \ref{ex2} in the Introduction. Assume that the dynamic system is in a state where all individuals at nodes $1$ and $2$ play $b^{1}$ and $b^{2}$, respectively; thus node $3$ is not reached. Then selection SE($3$) does not affect the population at $3$; only mutation MU($3$) does. Mutation by itself will lead in the long run to a distribution close to $(1/2,1/2)$ (since each individual is eventually chosen, and then his action is replaced with equal probabilities by $c^{3}$ and $b^{3}$). However, there are also \emph{% mutations} \emph{at node} $2$ that yield a $c^{2}$ action, with a frequency of $\mu /2$. After such a mutation, the probability that the action of the mutant individual will revert back to $b^{2}$ is at most $\left( 1/m\right) \rho $ (since his probability of being chosen is $1/m$; here $\rho =\sigma +\mu /2$); thus, it will take on the average\footnote{% An event whose probability is $p$ every period will occur on average $pT$ times during $T$ periods, or once every $1/p$ periods. In our arguments we shall go back and forth between the two computations as needed.} $m/\rho $ periods for it to happen. Therefore, during a long stretch of time, say $T$ periods, the number of periods that there is a $c^{2}$ in population $2$ is about $\left( \mu /2\right) (m/\rho )T=\mu mT/(2\rho )$. These are periods at which $3$ is reached and thus selection SE($3$)---into $b^{3}$---is effective. At the same time, mutation MU($3$) occurs at $3$ in roughly $\mu T $ periods. Comparing the two implies that, when the population is large (i.e., as $m\rightarrow \infty $), selection has a much greater effect than mutation. Therefore, in the long run, we will get most of the population at node $3$ playing $b^{3}$---even though $3$ is unreached most of the time. Consider next the $4$-person game $\Gamma _{4}$ of Figure \ref{ex4}% %TCIMACRO{\TeXButton{BeginFigure-ex4}{\begin{figure}[tb] \centering}} %BeginExpansion \begin{figure}[tb] \centering% %EndExpansion %TCIMACRO{ %\TeXButton{ex4}{ %\unitlength 1.00mm % %\begin{picture}(90.00,117.00)(5,3) %\linethickness{1.0pt} %\put(50.00,110.00){\line(1,-1){20.00}} %\put(70.00,90.00){\line(1,-1){20.00}} %\put(70.00,90.00){\line(-1,-1){20.00}} %\put(50.00,110.00){\circle*{1.50}} %\put(70.00,90.00){\circle*{1.50}} %\put(50.00,114.00){\makebox(0,0)[cc]{$1$}} %\put(72.00,93.00){\makebox(0,0)[cc]{$2$}} %\put(50.00,110.00){\line(-1,-1){20.00}} %\put(30.00,86.00){\makebox(0,0)[cc]{$0$}} %\put(30.00,81.00){\makebox(0,0)[cc]{$0$}} %\put(90.00,66.00){\makebox(0,0)[cc]{$1$}} %\put(90.00,61.00){\makebox(0,0)[cc]{$1$}} %\put(39.00,103.00){\makebox(0,0)[cc]{$c^1$}} %\put(62.00,103.00){\makebox(0,0)[cc]{$b^1$}} %\put(59.00,83.00){\makebox(0,0)[cc]{$c^2$}} %\put(82.00,83.00){\makebox(0,0)[cc]{$b^2$}} %\put(50.00,70.00){\line(1,-1){20.00}} %\put(50.00,70.00){\line(-1,-1){20.00}} %\put(50.00,70.00){\circle*{1.50}} %\put(48.00,73.00){\makebox(0,0)[cc]{$3$}} %\put(68.30,46.00){\makebox(0,0)[cc]{$-1$}} %\put(70.00,41.00){\makebox(0,0)[cc]{$0$}} %\put(39.00,63.00){\makebox(0,0)[cc]{$c^3$}} %\put(62.00,63.00){\makebox(0,0)[cc]{$b^3$}} %\put(30.00,76.00){\makebox(0,0)[cc]{$0$}} %\put(90.00,56.00){\makebox(0,0)[cc]{$1$}} %\put(70.00,36.00){\makebox(0,0)[cc]{$0$}} %\put(30.00,50.00){\line(1,-1){20.00}} %\put(30.00,50.00){\line(-1,-1){20.00}} %\put(30.00,50.00){\circle*{1.50}} %\put(28.00,53.00){\makebox(0,0)[cc]{$4$}} %\put(8.00,26.00){\makebox(0,0)[cc]{$-1$}} %\put(9.70,21.00){\makebox(0,0)[cc]{$5$}} %\put(48.00,26.00){\makebox(0,0)[cc]{$-1$}} %\put(48.00,21.00){\makebox(0,0)[cc]{$-1$}} %\put(19.00,43.00){\makebox(0,0)[cc]{$c^4$}} %\put(42.00,43.00){\makebox(0,0)[cc]{$b^4$}} %\put(9.70,16.00){\makebox(0,0)[cc]{$5$}} %\put(48.00,16.00){\makebox(0,0)[cc]{$-1$}} %\put(30.00,71.00){\makebox(0,0)[cc]{$0$}} %\put(90.00,51.00){\makebox(0,0)[cc]{$1$}} %\put(70.00,31.00){\makebox(0,0)[cc]{$0$}} %\put(8.00,11.00){\makebox(0,0)[cc]{$-1$}} %\put(49.70,11.00){\makebox(0,0)[cc]{$5$}} %\end{picture} %}} %BeginExpansion \unitlength 1.00mm \begin{picture}(90.00,117.00)(5,3) \linethickness{1.0pt} \put(50.00,110.00){\line(1,-1){20.00}} \put(70.00,90.00){\line(1,-1){20.00}} \put(70.00,90.00){\line(-1,-1){20.00}} \put(50.00,110.00){\circle*{1.50}} \put(70.00,90.00){\circle*{1.50}} \put(50.00,114.00){\makebox(0,0)[cc]{$1$}} \put(72.00,93.00){\makebox(0,0)[cc]{$2$}} \put(50.00,110.00){\line(-1,-1){20.00}} \put(30.00,86.00){\makebox(0,0)[cc]{$0$}} \put(30.00,81.00){\makebox(0,0)[cc]{$0$}} \put(90.00,66.00){\makebox(0,0)[cc]{$1$}} \put(90.00,61.00){\makebox(0,0)[cc]{$1$}} \put(39.00,103.00){\makebox(0,0)[cc]{$c^1$}} \put(62.00,103.00){\makebox(0,0)[cc]{$b^1$}} \put(59.00,83.00){\makebox(0,0)[cc]{$c^2$}} \put(82.00,83.00){\makebox(0,0)[cc]{$b^2$}} \put(50.00,70.00){\line(1,-1){20.00}} \put(50.00,70.00){\line(-1,-1){20.00}} \put(50.00,70.00){\circle*{1.50}} \put(48.00,73.00){\makebox(0,0)[cc]{$3$}} \put(68.30,46.00){\makebox(0,0)[cc]{$-1$}} \put(70.00,41.00){\makebox(0,0)[cc]{$0$}} \put(39.00,63.00){\makebox(0,0)[cc]{$c^3$}} \put(62.00,63.00){\makebox(0,0)[cc]{$b^3$}} \put(30.00,76.00){\makebox(0,0)[cc]{$0$}} \put(90.00,56.00){\makebox(0,0)[cc]{$1$}} \put(70.00,36.00){\makebox(0,0)[cc]{$0$}} \put(30.00,50.00){\line(1,-1){20.00}} \put(30.00,50.00){\line(-1,-1){20.00}} \put(30.00,50.00){\circle*{1.50}} \put(28.00,53.00){\makebox(0,0)[cc]{$4$}} \put(8.00,26.00){\makebox(0,0)[cc]{$-1$}} \put(9.70,21.00){\makebox(0,0)[cc]{$5$}} \put(48.00,26.00){\makebox(0,0)[cc]{$-1$}} \put(48.00,21.00){\makebox(0,0)[cc]{$-1$}} \put(19.00,43.00){\makebox(0,0)[cc]{$c^4$}} \put(42.00,43.00){\makebox(0,0)[cc]{$b^4$}} \put(9.70,16.00){\makebox(0,0)[cc]{$5$}} \put(48.00,16.00){\makebox(0,0)[cc]{$-1$}} \put(30.00,71.00){\makebox(0,0)[cc]{$0$}} \put(90.00,51.00){\makebox(0,0)[cc]{$1$}} \put(70.00,31.00){\makebox(0,0)[cc]{$0$}} \put(8.00,11.00){\makebox(0,0)[cc]{$-1$}} \put(49.70,11.00){\makebox(0,0)[cc]{$5$}} \end{picture} % %EndExpansion \caption{The game $\Gamma _4$\label{ex4}}% %TCIMACRO{\TeXButton{EndFigure}{\end{figure}}} %BeginExpansion \end{figure}% %EndExpansion . Assume again that everyone plays $b^{i}$ at nodes $1$ and $2$, and thus both $3$ and $4$ are not reached. In the same way as in the previous example, we get the following: At node $4$, mutations MU($4$) occur with a frequency of $\mu $, whereas selection SE($4$) there---which requires mutations at \emph{both} nodes $2$ and $3$ in order for $4$ to be reached---occurs with a frequency of $\left( \mu /2\right) ^{2}m/\left( 2\rho \right) =\mu ^{2}m/(8\rho )$ (indeed, the probability of a mutation at $2$ into $c^{2}$ is $\mu /2$; the same goes for a mutation into $c^{3}$ at $% 3 $; and then it takes about $\left( m/\rho \right) /2=m/\left( 2\rho \right) $ periods until at least one of the mutants reverts back). But we cannot say that $\mu ^{2}m$ is much larger than $\mu $ (we only assumed that $\mu m$ is bounded away from zero), so we cannot conclude that, at node $4$, selection ``overpowers'' mutation. Without this happening at $4$, there is no reason for the populations at the higher nodes (like $3$) to choose their backward induction action either. Moreover, when a node is even further away from the equilibrium path---say, $k$ nodes away--- the previous argument will work out only if $\mu ^{k}m$ is much larger than $\mu $. A more careful analysis is thus called upon at this point. Let us consider the first time that there is a $c^{3}$ individual in population $3$; this happens (by mutation) on the average once every $2/\mu $ periods. If, at that point, there is a $c^{2}$ action in population $2$, then $4$ is reached and we are done. If not, then, as long as there is no $% c^{2}$ in population $2$, node $3$ is not reached. Therefore, the only way that the $c^{3}$ individual can revert back to $b^{3}$ is by mutation at $3$% ; the probability of that happening is $\left( 1/m\right) \left( \mu /2\right) =\mu /\left( 2m\right) $ (since that individual must be chosen out of $M(3)$, and then undergo mutation). At the same time, the probability of getting a $c^{2}$ individual in population $2$---by mutation---is $\mu /2$. Since $\mu /2$ is much larger than $\mu /\left( 2m\right) $ for large $m$, in general the latter will happen much later than the former (and therefore can be essentially ignored). Thus altogether we have to wait at most on the order of $2/\mu $ periods for the mutation at $3$, and then another $2/\mu $ periods for the mutation at node $2$; in sum, $4/\mu $ periods until node $4$ is reached (compare this to $4/\mu ^{2}$ in the previous---unsuccessful---argument). Once $4$ is reached, it takes on the order of $m/\left( 2\rho \right) $ periods for either the $c^{2}$ or the $% c^{3}$ individual to revert back, so selection SE($4$) operates at node $4$ with a frequency of approximately $\left( \mu /4\right) m/(2\rho )=\mu m/(8\rho )$. When $m\rightarrow \infty $, this is much larger than the mutation rate $\mu $; so, again, selection ``wins'' at\footnote{% This argument clearly generalizes; for a node that is at distance $k$ from the equilibrium path, the frequency of selection is of the order of $\mu m/(2k^{2}\rho ),$ which, as $m\rightarrow \infty ,$ is much larger than the mutation rate $\mu .$} $4$. Once this has been established, it follows that most of the population at node $4$ plays $b^{4}$ most of the time, and we are essentially\footnote{% See the last paragraph in this subsection.} left with a $3$-player game (like $\Gamma _{2}$); the proof is completed by (backward) induction.% \footnote{% Similar arguments apply to the $3$-player game $\Gamma _{3}$ of Figure \ref {ex3} of the Introduction. When less than $90\%$ of population $3$ plays $% b^{3},$ in order for $3$ to be reached one needs mutants at $2$ and at $1,$ and the computations are exactly as for node $4$ in $\Gamma _{4}.$ When the $% 90\%$ proportion of $b^{3}$ is exceeded, then $b^{2}$ becomes a best-reply of $2,$ so a mutant is needed only at $1$---and the estimates are as for node $3$ in $\Gamma _{2}.$} The crux of the argument is that, after a mutation in population $3$ generated a $c^{3}$, this $c^{3}$ action is ``stuck'' there for a long time% \footnote{% It is a so-called ``neutral mutation'' that does not affect the payoffs.}% ---at least until a mutation generates a $c^{2}$ in population $2$. Thus, what appeared to require \emph{simultaneous mutations} (with a frequency of the order of $\mu ^{k}$ for some $k\geq 2$), turns out instead to rely on \emph{sequential mutations} (with a frequency of the order of $\mu $).% \footnote{% This kind of argument may also explain how matching mutations occur in interacting populations; i.e., mutations that yield no advantage in their own population, unless there are fitting mutations in the other populations. The computations above show that, in large populations, the frequency of such events may well be much higher than commonly thought: of the order of $% \mu $ rather than a power of $\mu .$} It should now be clear what role the large populations play: The smaller a group of individuals is, the (relatively) less probable it is for a change of action to occur in that group. This is particularly true when comparing a \emph{specific} individual (like the $c^{3}$ mutant in the analysis of game $% \Gamma _{4}$, or the $c^{2}$ mutant in $\Gamma _{2}$), to \emph{any} individual in a whole population (population $2$ in $\Gamma _{4}$, or population $3$ in $\Gamma _{2}$). Finally, to understand the use of the condition that $\mu m\geq \delta >0,$ note that the above arguments show that the effect of selection is of the order of $\mu m$, whereas that of mutation is $\mu $. The possibility that a sizeable fraction of the population does not play the backward induction action, albeit an event of low probability for large $m$, is not negligible. A simple estimate\footnote{% Using Markov's inequality. More refined probabilistic computations may well lead to weaker conditions.} shows this probability to be of the order of at most $1/m$. When this event occurs at some descendant node, it may affect selection at the current node---away from the backward induction action. However, as long as $1/m$ is at most a constant times $\mu $---which is the case when $\mu m\geq \delta >0$---this effect (like that of random mutations) is again small relative to $\mu m$ for large $m.$ \subsection{An Outline of the Proof\label{ss-outline}} We now provide an outline that may help the reader follow the formal proof given in the next subsection. The proof proceeds by backward induction, starting from the final nodes and working back towards the root; see Proposition \ref{p-1}. The main claims that are proved for each node $i$ are as follows: \begin{enumerate} \item The probability that $b^{i}$ is not the local best-reply of $i$ is low (this happens only when a sizeable proportion of the population at some descendant node $j$ does not choose $b^{j}$, which, by induction, has low probability); in fact, this probability is of the order of $\mu $; see (\ref {p1-1}). \item When $b^{i}$ is the local best-reply of $i$, the expected proportion of population $i$ that does not play $b^{i}$ when $i$ is reached is small (this holds since selection has probability at least $\beta $, which is bounded away from $0$, while mutation has probability $\mu $); again, it is of the order of $\mu $; see (\ref{p1-2}). \item When $b^{i}$ is the local best-reply of $i$, the ratio between the expected proportion of population $i$ that does not play $b^{i}$ when $i$ is reached, and the same expected proportion when $i$ is not reached, is of the order of $\mu m$; see (\ref{eq-mu-m}). This is the central step in the proof, and its essence is the ``sequential mutations'' argument above; see Proposition \ref{p-z}. Together with the previous claim, it follows that the expected proportion of population $i$ that does not play $b^{i}$ when $i$ is not reached is of the order of $1/m$; see (\ref{p3-4}). \item Adding the above three estimates and noting that $1/m\leq \left( 1/\delta \right) \mu $ implies that the expected proportion of population $i$ that does not play $b^{i}$ is of the order of $\mu $, which yields (\ref {eq-th-e}) and (\ref{eq-th-pi}). \end{enumerate} \subsection{The Proof\label{ss-proof}} We now prove the Main Theorem. Fix $\varepsilon ,\delta >0$, the mutation rate $\mu >0$, the population profile $\mathbf{m=}\left( m^{i}\right) _{i\in N}$ (with $\mu m\geq \delta $, where $m:=\min_{i\in N}m^{i}$) and the transition probability matrix $Q$ that satisfies (\ref{eq-independence})--(% \ref{eq-mu2}). Let $\pi $ be the resulting unique invariant distribution over the state space $\Omega $. Take the state $\omega \in \Omega $ to be distributed according to $\pi $, and let $\widetilde{\omega }\in \Omega $ be the next state, given by the one-step transition probabilities $Q\left[ \widetilde{\omega }\mid \omega \right] $; then $\widetilde{\omega }$ is also distributed according to $\pi $. From now on all probability statements and expectations will be according to this distribution. Before proceeding with the proof, we introduce a number of useful notations: \begin{itemize} \item For each node $i\in N$, put $Y^{i}:=1-x_{b^{i}}^{i}(\omega )$ (the mapping $x:\Omega \rightarrow X$ is given by (\ref{eq-f})); this is the proportion of population $i$ that does \emph{not} play the backward induction action in state $\omega $. Similarly, put $\widetilde{Y}% ^{i}:=1-x_{b^{i}}^{i}\left( \widetilde{\omega }\right) $ for the same proportion in the next-period state $\widetilde{\omega }$. The random variables $Y^{i}$ and $\widetilde{Y}^{i}$ are identically distributed (their distribution is $\pi \circ \left( 1-x_{b^{i}}^{i}\right) ^{-1}$); thus in particular $E\left[ \widetilde{Y}^{i}\right] =E\left[ Y^{i}\right] $. \item Given two nodes $i,j\in N$ such that $i$ is a descendant of $j$ (i.e., $i\in N(j))$, let $R^{j,i}$ be an indicator random variable, defined to be $1$ if node $i$ is \emph{reached} from node $j$ in state $\omega $ and $0$ otherwise (i.e., $R^{j,i}=1$ if and only if for every $k\in N$ on the path from $j$ to $i$ there is at least one individual $q\in M(k)$ whose choice $\omega _{q}^{k}$ is the action that leads towards $i)$. When $j$ is the root we will write $R^{i}$ for the indicator that $i$ is reached. Again, $\widetilde{R}^{j,i}$ is defined in the same way for $\widetilde{\omega }$. \item When everyone plays the backward induction action---i.e., when $% Y^{j}=0$ for all $j\in N$---the unique local best-reply of each $i\in N$ is $% b^{i}$ (recall that $b$ is the unique backward induction equilibrium). Therefore there exists a $\lambda >0$ (appropriately small) such that $b^{i}$ is the unique local best-reply of $i$ for all $i\in N$ when $Y^{j}<\lambda $ for all $j\in N$ (i.e., when the proportion of the individuals at each node that do \emph{not} play the backward induction action is less than $\lambda $% ). This $\lambda $ depends on the game only, and will be fixed from now on. \item Let $L^{i}$ be an indicator random variable, defined to be $1$ in state $\omega $ if $Y^{j}<\lambda $ for all $j\in N(i)$ and $0$ otherwise. Thus, when $L^{i}=1$ the backward induction action $b^{i}$ is the unique \emph{local} best-reply of $i$ in state $\omega $, i.e., $u_{\Gamma (i)}^{i}(b^{i},\omega ^{N(i)})>u_{\Gamma (i)}^{i}(a^{i},\omega ^{N(i)})$ for every $a^{i}\in A^{i},a^{i}\neq b^{i}$. We denote by $\widetilde{L}^{i}$ the indicator that $\widetilde{Y}^{j}<\lambda $ for all $j\in N(i)$. When $i$ is a final node (i.e., $N(i)=\emptyset $) we have $L^{i}\equiv \widetilde{L}% ^{i}\equiv 1$. \end{itemize} We note that selection SE($i$) has an effect only when $i$ is reached, i.e., when $R^{i}=1$; if $i$ is not reached, i.e., if $R^{i}=0$, then all actions of $i$ yield the same payoff in $\Gamma $ and only mutation MU($i$) affects $% \omega ^{i}$. If $R^{i}=1$ and $L^{i}=1$ then $b^{i}$ is the global best-reply of $i$, and thus certainly a ``better action'' for a ``non-$b^{i}$% -individual'' (i.e., $b^{i}\in B^{i}(q(i),\omega )$ when $\omega _{q(i)}^{i}\neq b^{i}$). Since these arguments will be repeatedly used in the proof, for convenience we state the following implications of (\ref {eq-independence})--(\ref{eq-mu2}) here:\footnote{% We use the ``big-$O$'' notation: $f(x)=O(g(x))$ if there exists a constant $% K<\infty $ such that $\left| f(x)\right| \leq K\left| g(x)\right| $ for all $% x$ in the relevant region. Thus $f(\mu ,\mathbf{m})=O(\mu )$ means that there exists $K$ such that $\left| f(\mu ,\mathbf{m})\right| \leq K\mu $ for all $0<\mu <1$ and all vectors $\mathbf{m=}\left( m^{i}\right) _{i\in N}$ with integer coordinates $m^{i}\geq \delta /\mu $ for all $i\in N.$} \begin{equation} P\left[ \widetilde{\omega }_{q(i)}^{i}=a^{i}\mid \omega \right] \geq \alpha _{1}\mu \text{ for every }a^{i}\in A^{i}. \label{r0-1} \end{equation} \begin{equation} \text{If }R^{i}=0\text{ then }P\left[ \widetilde{\omega }_{q(i)}^{i}\neq \omega _{q(i)}^{i}\mid \omega \right] =O\left( \mu \right) . \label{r0-all} \end{equation} \begin{equation} \text{If }L^{i}R^{i}=1\text{ and }\omega _{q(i)}^{i}\neq b^{i}\text{ then }% P\left[ \widetilde{\omega }_{q(i)}^{i}=b^{i}\mid \omega \right] \geq \beta . \label{r1l1} \end{equation} The crucial argument in our proof is the following: \begin{proposition} \label{p-z}Consider the path from the root to a node $i\in N$; without loss of generality, assume that the nodes along this path are $1,2,...,i-1,i$ (in that order, with $1$ the root). Let $Z$ be a non-negative random variable. Then \begin{eqnarray*} \mu E\left[ Z\left( 1-R^{i}\right) \right] &\leq &O\left( \frac{1}{m}\right) E\left[ ZR^{i}\right] +O\left( \frac{\mu }{m}\right) \\ &&+\sum_{j=1}^{i-1}\left( E\left[ Z\left( 1-R^{j,i}\right) \right] -E\left[ Z\left( 1-\widetilde{R}^{j,i}\right) \right] \right) . \end{eqnarray*} \end{proposition} %TCIMACRO{\TeXButton{Proof}{\proof}} %BeginExpansion \proof% %EndExpansion For each $j=1,2,...,i-1$, let $c^{j}\in A^{j}$ be the choice along the given path (i.e., towards $j+1$), and put $\theta ^{j}(\omega ):=\left| \left\{ q\in M(j):\omega _{q}^{j}=c^{j}\right\} \right| $, the proportion of players at node $j$ that choose $c^{j}$; denote $V^{j}:=\theta ^{j}(\omega )$ and $% \widetilde{V}^{j}:=\theta ^{j}(\widetilde{\omega })$. We first prove three lemmata. \begin{lemma} \label{l-1} \[ E\left[ Z\left( 1-\widetilde{R}^{j,i}\right) R^{i}\right] =O\left( \frac{1}{m% }\right) E\left[ ZR^{i}\right] . \] \end{lemma} %TCIMACRO{\TeXButton{Proof}{\proof}} %BeginExpansion \proof% %EndExpansion For each $\omega $ with $R^{i}=1$, to get $\widetilde{R}^{j,i}=0$ there must be some node $k$ with $j\leq k0$ (since $R^{i}=1$), so in fact $V^{k}=1/m^{k}$ (since $\left| \widetilde{V}% ^{k}-V^{k}\right| $ is $0$ or $1/m^{k}$). Hence $P\left[ \widetilde{V}% ^{k}=0\mid \omega \right] \leq \gamma _{2}/m^{k}=O\left( 1/m\right) $ (by (% \ref{eq-M}), since the single $c^{k}$-individual must be chosen). Therefore $% P\left[ \widetilde{R}^{j,i}=0\mid \omega \right] \leq \sum_{k=j}^{i-1}P\left[ \widetilde{V}^{k}=0\mid \omega \right] =O\left( 1/m\right) $, from which it follows that \[ E\left[ Z\left( 1-\widetilde{R}^{j,i}\right) R^{i}\right] =E\left[ P\left[ \widetilde{R}^{j,i}=0\mid ZR^{i}\right] \right] =O\left( \frac{1}{m}\right) E\left[ ZR^{i}\right] . \] %TCIMACRO{\TeXButton{End Proof}{\endproof}} %BeginExpansion \endproof% %EndExpansion \begin{lemma} \label{l-2} \[ E\left[ Z\left( 1-\widetilde{R}^{j,i}\right) \left( 1-R^{j}\right) R^{j,i}\right] =O\left( \frac{\mu }{m}\right) . \] \end{lemma} %TCIMACRO{\TeXButton{Proof}{\proof}} %BeginExpansion \proof% %EndExpansion For each $\omega \in \Omega $ with $R^{j}=0$ and $R^{j,i}=1$ (i.e., $j$ is not reached, and $i$ is reached from $j$), to get $\widetilde{R}^{j,i}=0$ there must be some node $k$ with $j\leq k0$, and thus $V^{k}=1/m^{k}$. Therefore $% P\left[ \widetilde{V}^{k}=0\mid \omega \right] \leq \left( \gamma _{2}/m^{k}\right) O\left( \mu \right) =O\left( \mu /m\right) $ (by (\ref {eq-M}) and (\ref{r0-all}): the single $c^{k}$-individual must be chosen, and its action can change by mutation only, since $j$, and thus \emph{a fortiori} $k$, is not reached). Hence $P\left[ \widetilde{R}^{j,i}=0\mid \omega \right] \leq \sum_{k=j}^{i-1}P\left[ \widetilde{V}^{k}=0\mid \omega \right] =O\left( \mu /m\right) $, from which the result follows.% %TCIMACRO{\TeXButton{End Proof}{\endproof}} %BeginExpansion \endproof% %EndExpansion \begin{lemma} \label{l-3} \[ E\left[ Z\left( 1-\widetilde{R}^{j,i}\right) \left( 1-R^{j,j+1}\right) R^{j+1,i}\right] \leq \left( 1-\alpha _{1}\mu \right) E\left[ Z\left( 1-R^{j,j+1}\right) R^{j+1,i}\right] +O\left( \frac{\mu }{m}\right) . \] \end{lemma} %TCIMACRO{\TeXButton{Proof}{\proof}} %BeginExpansion \proof% %EndExpansion Take $\omega \in \Omega $ with $R^{j,j+1}=0$ (i.e., $V^{j}=0$), and $% R^{j+1,i}=1$. To get $\widetilde{R}^{j,i}=0$ there must be some node $k$ with $j\leq k0\mid \omega \right] =P\left[ \widetilde{\omega }_{q(j)}^{j}=c^{j}\mid \omega \right] \geq \alpha _{1}\mu $ (this follows from $V^{j}=0$ and (\ref {r0-1})), and $P\left[ \widetilde{V}^{k}=0\mid \omega \right] \leq \gamma _{2}/m^{k}\leq \gamma _{2}/m$ for $k=j+1,...,i-1$ (by (\ref{eq-M}), since $% R^{j+1,i}=1$ implies $V^{k}>0$). Therefore $P\left[ \widetilde{R}% ^{j,i}=1\mid \omega \right] =P\left[ \widetilde{V}^{k}>0\text{ for all }% j\leq kY^{i}\right] &=&O\left( \mu \right) ; \label{eq-p1-1} \\ E\left[ Y^{i}L^{i}R^{i}\right] &=&O\left( \mu \right) ; \label{p1-2} \\ E\left[ \widetilde{Y}^{i}\widetilde{L}^{i}R^{i}\right] &=&O\left( \mu \right) ; \label{p2-2} \\ E\left[ \left| \widetilde{Y}^{i}\widetilde{L}^{i}-Y^{i}L^{i}\right| \left( 1-R^{i}\right) \right] &=&O\left( \frac{\mu }{m}\right) ; \label{p3-1} \\ E\left[ \widetilde{Y}^{i}\widetilde{L}^{i}(1-R^{i})\right] &=&O\left( \frac{1% }{m}\right) ; \label{p3-3} \\ E\left[ Y^{i}L^{i}(1-R^{i})\right] &=&O\left( \frac{1}{m}\right) ;\text{ and} \label{p3-4} \\ E\left[ Y^{i}\right] &=&O\left( \mu \right) . \label{p-9} \end{eqnarray} \end{proposition} %TCIMACRO{\TeXButton{Proof}{\proof}} %BeginExpansion \proof% %EndExpansion The proof is by backward induction on $i$. Assume that (\ref{p1-1})--(\ref {p-9}) hold for all\footnote{% The induction starts from final nodes $i$ for which $N(i)=\emptyset $ (and thus there is no assumption).} $j\in N(i)$; then each of the claims (\ref {p1-1})--(\ref{p-9}) for $i$ will be proved in turn. \emph{Step 1: (\ref{p1-1}) holds for }$i$. Indeed,\footnote{% We thank Michihiro Kandori for pointing out an error in this proof in the first version of the paper.} $L^{i}=0$ implies that there is $j\in N(i)$ such that $Y^{j}\geq \lambda ,$ hence \[ P\left[ L^{i}=0\right] \leq \sum_{j\in N(i)}P\left[ Y^{j}\geq \lambda \right] \leq \sum_{j\in N(i)}\frac{1}{\lambda }E\left[ Y^{j}\right] =O\left( \mu \right) , \] where we have used Markov's inequality\footnote{% Markov's inequality is: $P\left[ Z\geq z\right] \leq \left( 1/z\right) E\left[ Z\right] $ for a non-negative random variable $Z$ and $z>0.$} and (% \ref{p-9}) for $j$ (by the induction hypothesis). \emph{Step 2: (\ref{eq-p1-1}) holds for }$i$. We have $E\left[ \widetilde{Y}% ^{i}\right] =E\left[ Y^{i}\right] $ (recall that $\pi $ is the invariant distribution), thus \[ 0=E\left[ \widetilde{Y}^{i}-Y^{i}\right] =\left( \frac{1}{m^{i}}\right) P\left[ \widetilde{Y}^{i}>Y^{i}\right] +\left( -\frac{1}{m^{i}}\right) P\left[ \widetilde{Y}^{i}Y^{i}\right] =P\left[ \widetilde{Y}% ^{i}Y^{i}$ we need a $b^{i}$-individual to become non-$% b^{i}$ (i.e., $\omega _{q(i)}^{i}=b^{i}$ and $\widetilde{\omega }% _{q(i)}^{i}\neq b^{i})$. This can happen either by selection---which requires $b^{i}$ not to be a best-reply of $i$ (hence $L^{i}=0$)---or by mutation---with probability equal to $O\left( \mu \right) $ (by (\ref{eq-mu2}% )). Thus \[ P\left[ \widetilde{Y}^{i}>Y^{i}\right] \leq P\left[ L^{i}=0\right] +O\left( \mu \right) =O\left( \mu \right) , \] by (\ref{p1-1}) for $i$, proving (\ref{eq-p1-1}) for $i$. \emph{Step 3: (\ref{p1-2}) holds for }$i$. The case $\widetilde{Y}^{i}Y^{i}\right] \end{eqnarray*} (since the only positive value of $\widetilde{Y}^{i}-Y^{i}$ is $1/m^{i}$). Applying (\ref{eq-p1-1}) yields the desired inequality. \emph{Step 5: (\ref{p3-1}) holds for }$i$\emph{.} We have \begin{eqnarray*} &&E\left[ \left| \widetilde{Y}^{i}\widetilde{L}^{i}-Y^{i}L^{i}\right| \left( 1-R^{i}\right) \right] \\ &\leq &E\left[ \left| \widetilde{Y}^{i}-Y^{i}\right| \widetilde{L}^{i}\left( 1-R^{i}\right) \right] +E\left[ Y^{i}\left| \widetilde{L}^{i}-L^{i}\right| \left( 1-R^{i}\right) \right] \\ &\leq &E\left[ \left| \widetilde{Y}^{i}-Y^{i}\right| \left( 1-R^{i}\right) \right] +E\left[ \left| \widetilde{L}^{i}-L^{i}\right| \left( 1-R^{i}\right) \right] \end{eqnarray*} The first term is bounded by $\left( 1/m^{i}\right) P\left[ \widetilde{Y}% ^{i}\neq Y^{i},R^{i}=0\right] =(1/m^{i})\,O\left( \mu \right) =O\left( \mu /m\right) $ (see (\ref{r0-all}): $R^{i}=0$ implies that the change from $% Y^{i}$ to $\widetilde{Y}^{i}$ is by mutation only). For the second term, note that $\widetilde{L}^{i}\neq L^{i}$ implies that there exists $j\in N(i)$ such that $Y^{j}\geq \lambda -1/m^{j}$ (otherwise $Y^{j}<\lambda -1/m^{j}$ and thus $\widetilde{Y}^{j}<\lambda $ for all $j\in N(i)$, in which case $% L^{i}=\widetilde{L}^{i}=1$). Choose $j\in N(i)$ to be a last such node; thus $Y^{l}<\lambda -1/m^{l}$ for all $l\in N(j)$, hence $L^{j}=1$. Now $% \widetilde{L}^{i}\neq L^{i}$ implies that $\widetilde{\omega }^{k}\neq \omega ^{k}$ for some $k\in N(i)\cup \left\{ i\right\} $, which, by (\ref {r0-all}), has conditional probability equal to $O\left( \mu \right) $ for every $\omega $ with $R^{i}=0$ and thus \emph{a fortiori} $R^{k}=0$. Therefore \begin{eqnarray*} E\left[ \left| \widetilde{L}^{i}-L^{i}\right| \left( 1-R^{i}\right) \right] &\leq &\sum_{j\in N(i)}P\left[ \widetilde{L}^{i}\neq L^{i},Y^{j}\geq \lambda -\frac{1}{m^{j}},L^{j}=1,R^{i}=0\right] \\ &\leq &O\left( \mu \right) \sum_{j\in N(i)}P\left[ Y^{j}\geq \lambda -\frac{1% }{m^{j}},L^{j}=1,R^{i}=0\right] \\ &\leq &O\left( \mu \right) \sum_{j\in N(i)}\frac{1}{\lambda -\frac{1}{m^{j}}}% E\left[ Y^{j}L^{j}\left( 1-R^{j}\right) \right] , \end{eqnarray*} where we have used $1-R^{i}\leq 1-R^{j}$ together with Markov's inequality. Applying (\ref{p3-4}) for each $j\in N(i)$ completes the proof of (\ref{p3-1}% ) for $i$. \emph{Step 6: (\ref{p3-3}) holds for }$i$\emph{.} Take $Z=\widetilde{Y}^{i}% \widetilde{L}^{i}$ in Proposition \ref{p-z}. We have \begin{eqnarray*} &&\left| E\left[ \widetilde{Y}^{i}\widetilde{L}^{i}\left( 1-R^{j,i}\right) \right] -E\left[ \widetilde{Y}^{i}\widetilde{L}^{i}\left( 1-\widetilde{R}% ^{j,i}\right) \right] \right| \\ &=&\left| E\left[ \widetilde{Y}^{i}\widetilde{L}^{i}\left( 1-R^{j,i}\right) \right] -E\left[ Y^{i}L^{i}\left( 1-R^{j,i}\right) \right] \right| \\ &\leq &E\left[ \left| \widetilde{Y}^{i}\widetilde{L}^{i}-Y^{i}L^{i}\right| \left( 1-R^{j,i}\right) \right] \\ &\leq &E\left[ \left| \widetilde{Y}^{i}\widetilde{L}^{i}-Y^{i}L^{i}\right| \left( 1-R^{i}\right) \right] =O\left( \frac{\mu }{m}\right) , \end{eqnarray*} where we have used the fact that $\pi $ is the invariant distribution, the inequality $1-R^{j,i}\leq 1-R^{i}$ (since $R^{j,i}=0$ implies $R^{i}=0$), and finally (\ref{p3-1}) for $i$. Thus each one of the right-most terms in the inequality obtained from Proposition \ref{p-z} is $O\left( \mu /m\right) $, and therefore \begin{equation} \mu E\left[ \widetilde{Y}^{i}\widetilde{L}^{i}\left( 1-R^{i}\right) \right] \leq O\left( \frac{1}{m}\right) E\left[ \widetilde{Y}^{i}\widetilde{L}% ^{i}R^{i}\right] +O\left( \frac{\mu }{m}\right) . \label{eq-mu-m} \end{equation} Applying (\ref{p2-2}) for $i$ completes the proof. \emph{Step 7: (\ref{p3-4}) holds for }$i$. It follows immediately from (\ref {p3-1}) and (\ref{p3-3}) for $i$. \emph{Step 8: (\ref{p-9}) holds for }$i$. Adding (\ref{p1-2}) and (\ref{p3-4}% ) for $i$ yields \[ E\left[ Y^{i}L^{i}\right] =O\left( \mu \right) +O\left( \frac{1}{m}\right) =O\left( \mu \right) , \] since\footnote{% This is the only place in the proof where $\mu m\geq \delta $ is used.} $% 1/m\leq \left( 1/\delta \right) \mu .$ Together with \[ E\left[ Y^{i}(1-L^{i})\right] \leq P\left[ L^{i}=0\right] =O\left( \mu \right) \] by (\ref{p1-1}) for $i$, the proof is completed.% %TCIMACRO{\TeXButton{End Proof}{\endproof}} %BeginExpansion \endproof% %EndExpansion \textbf{Proof of Theorem \ref{th-main} (Main Theorem). }Inequality (\ref{p-9}% ) of Proposition \ref{p-1} is precisely (\ref{eq-th-e}); applying Markov's inequality then yields (\ref{eq-th-pi}).% %TCIMACRO{\TeXButton{End Proof}{\endproof}} %BeginExpansion \endproof% %EndExpansion \section{Discussion\label{s-discussion}} \subsection{Multiple Agents\label{ss-agents}} The gene-normal form, which was defined in Subsection \ref{ss-gene-normal}, assumes that the populations at the different nodes are distinct. We shall now consider the implications of this assumption in the case where a player in the original game $\Gamma $ consists of more than one agent; that is, that player moves at more than one node. For concreteness, assume that two nodes $i$ and $j$ belong to the same player. There are three main implications: \begin{enumerate} \item The actions at $i$ and at $j$ are determined by different ``characteristics.'' This poses no problem, since different decision nodes in the tree correspond to different situations, and each one is controlled by a different ``gene.'' As we have already argued in Subsection \ref {ss-gene-normal}, if instead the same gene controls both decisions, it means that the player acts identically at both. The correct description of such an instance is then to have the two nodes belong to the same ``information set''---i.e., a game with imperfect information (and possibly imperfect recall too). \item The payoffs of all participants are computed based on independent draws from the populations; i.e., $u^{k}(\omega _{q}^{k},\omega ^{-k})=u^{k}(\omega _{q}^{k},x^{-k})$, where $x^{-k}$ is the product of $% x^{l}$ for all $l\neq k$. In particular, the proportion of a pair of actions $(a^{i},a^{j})$ is taken to be $x_{a^{i}}^{i}x_{a^{j}}^{j}$. If $i$ and $j$ were two gene loci of the same organism, this would be in general incorrect. However, an examination of our proofs suggests that a weaker assumption could be used: Namely, if both $a^{i}$ and $a^{j}$ are present (i.e., if $% x_{a^{i}}^{i}>0$ and $x_{a^{j}}^{j}>0$), then the combination $(a^{i},a^{j})$ is also present (i.e., its proportion is positive). \item At each period, the dynamic process affects the two characteristics independently. As far as mutations go, this is natural. However, selection operates at the level of the organism rather than the single gene. When the proportion of the combination $(a^{i},a^{j})$ is given by the product $% x_{a^{i}}^{i}x_{a^{j}}^{j}$, it makes no difference. But difficulties arise once this independence no longer holds. Still, note that $% x_{b^{i}}^{i}>1-\varepsilon $ and $x_{b^{j}}^{j}>1-\varepsilon $ imply that the proportion of the pair $(b^{i},b^{j})$ must be at least $1-2\varepsilon $% , regardless of the degree of interdependence between $i$ and $j$. This argument suggests that our results may well hold in this more general setup. \end{enumerate} \subsection{Other Selection Dynamics\label{ss-selection}} One straightforward generalization of our dynamics assumes that selection satisfies $Q\left[ \widetilde{\omega }_{q(i)}^{i}\in B^{i}\mid \omega \right] \geq \beta $ instead of (\ref{eq-beta}); i.e., at least one better action has positive probability of being chosen (rather than each one of them). It seems that the result will remain unchanged.\footnote{% Consider for simplicity a final node $i$; one shows first that the proportion of the worst action at $i$ must be small, after which the same is proven for the second-worst, and so on. Note that the proportion of the best-reply---which can change only by mutation---is bounded away from zero.} Another possible generalization, which also appears not to affect the result, assumes that the probability of each individual in $M(i)$ being chosen goes to zero as the population size $\left| M(i)\right| $ goes to infinity (without it necessarily being of the order of $1/\left| M(i)\right| $ as in (\ref{eq-M})).\footnote{% One then needs to work with expressions like $E\left[ p\left( Y^{i}\right) \right] $ instead of $E\left[ Y^{i}\right] $, where $p\left( Y^{i}\right) $ is the probability that a non-$b^{i}$-individual is chosen when their proportion in the population is $Y^{i}$.} Other dynamics to consider---like the ``replicator dynamics''---may have the selection take into account the actual payoff differences, rather than just their sign.\footnote{% Large populations may then decrease the effect of selection, since the difference in payoff due to one individual is small.} Further variants should also be analyzed; hopefully, a precise characterization of the class of dynamics that yield the backward induction outcome will be obtained. One modification\footnote{% Suggested by Ilan Eshel.} makes selection choose better actions with probabilities that are proportional to their current proportions in the population. Thus, for instance, if the best-reply action $c^{i}$ is currently played by $k$ individuals, then the probability that a chosen non-$% c^{i}$ individual will switch to $c^{i}$ by selection is $\sigma k/m^{i}$ (rather than $\sigma /\left| B^{i}\right| $). When $k$ is small, this probability becomes low; in particular, if $c^{i}$ is not currently present in the population, then selection cannot introduce it.\footnote{% A requirement suggested by Karl Schlag.} Such dynamics may be more appropriate in imitation-type models (where the ``visibility'' of an action depends on its prevalence in the population). Note also the property that $% x_{a^{i}}^{i}$, the proportion in the population of a better action $a^{i}$, increases by selection at a rate that is proportional to $x_{a^{i}}^{i}$. Formally, we weaken (\ref{eq-beta}) to\footnote{% Notice that (\ref{eq-beta0}) is more general than the description in the previous paragraph (since we only require $\geq $ rather than $=$).} \begin{equation} Q\left[ \widetilde{\omega }_{q(i)}^{i}=a^{i}\mid \omega \right] \geq \beta x_{a^{i}}^{i}\left( \omega \right) \text{ for each }a^{i}\in B^{i}. \label{eq-beta0} \end{equation} It turns out that our result continues to hold. \begin{theorem} \label{th-beta0}The results of the Main Theorem \ref{th-main} hold also for dynamic processes satisfying (\ref{eq-independence}), (\ref{eq-M}), (\ref {eq-q}), (\ref{eq-beta0}), (\ref{eq-mu}) and (\ref{eq-mu2}). \end{theorem} %TCIMACRO{\TeXButton{Proof}{\proof}} %BeginExpansion \proof% %EndExpansion It can easily be checked that selection---i.e., (\ref{eq-beta}) or (\ref {r1l1})---is used in the proofs of Subsection \ref{ss-proof} only in Step 3 of the Proof of Proposition \ref{p-1}. Replacing (\ref{eq-beta}) by (\ref {eq-beta0}) implies that $P\left[ \widetilde{\omega }_{q(i)}^{i}=b^{i}\mid \omega \right] \geq \beta \left( 1-Y^{i}\right) $ for every $\omega \in \Omega $ with $L^{i}R^{i}=1$ (since the proportion of $b^{i}$ in the population is $1-Y^{i}$). Therefore the argument of Step 3 yields \[ P\left[ \widetilde{Y}^{i}0$ and $c>0$ such that \[ P\left[ Y^{i}>1-\eta \right] =O\left( e^{-cm}\right) . \] \end{lemma} %TCIMACRO{\TeXButton{Proof}{\proof}} %BeginExpansion \proof% %EndExpansion We have \[ P\left[ \widetilde{Y}^{i}=\frac{k}{m^{i}}\left| Y^{i}=\frac{k+1}{m^{i}}% \right. \right] \geq \gamma _{1}\frac{k+1}{m^{i}}\alpha _{1}\mu \] by (\ref{eq-M}) and (\ref{eq-mu}). Next, \begin{eqnarray*} P\left[ \widetilde{Y}^{i}=\frac{k+1}{m^{i}}\left| Y^{i}=\frac{k}{m^{i}}% \right. \right] &\leq &\gamma _{2}\left( 1-\frac{k}{m^{i}}\right) \left( \alpha _{2}\mu +P\left[ L^{i}=0\right] \right) \\ &\leq &c_{1}\left( 1-\frac{k}{m^{i}}\right) \mu \end{eqnarray*} for an appropriate constant $c_{1}>0$, where we have used (\ref{eq-M}) and (% \ref{eq-mu2}) (selection can increase $Y^{i}$ only when $L^{i}=0$), and then $P\left[ L^{i}=0\right] =O\left( \mu \right) $ by (\ref{p1-1}) for $i$ (proved in Step 1). Using the invariant distribution property yields \[ P\left[ Y^{i}=\frac{k+1}{m^{i}}\right] \gamma _{1}\frac{k+1}{m^{i}}\alpha _{1}\mu \leq P\left[ Y^{i}=\frac{k}{m^{i}}\right] c_{1}\left( 1-\frac{k}{% m^{i}}\right) \mu , \] or \[ P\left[ Y^{i}=\frac{k+1}{m^{i}}\right] \leq c_{2}\left( \frac{m^{i}-k}{k+1}% \right) P\left[ Y^{i}=\frac{k}{m^{i}}\right] \] (where $c_{2}:=c_{1}/\left( \gamma _{1}\alpha _{1}\right) $). Let $\eta >0$ be small enough so that $c_{2}\left( m^{i}-k\right) /\left( k+1\right) \leq 1/2$ for all\footnote{$\left\lfloor x\right\rfloor $ denotes the largest integer that is $\leq x$.} $k>k_{0}:=\left\lfloor \left( 1-2\eta \right) m^{i}\right\rfloor $. Then we get \[ P\left[ Y^{i}=\frac{k}{m^{i}}\right] \leq \left( \frac{1}{2}\right) ^{k-k_{0}} \] for all $k\geq k_{0}$ and thus \[ P\left[ Y^{i}>1-\eta \right] \leq \sum_{k>\left( 1-\eta \right) m^{i}}\left( \frac{1}{2}\right) ^{k-k_{0}}\leq \left( \frac{1}{2}\right) ^{\eta m^{i}-1}, \] as claimed.% %TCIMACRO{\TeXButton{End Proof}{\endproof}} %BeginExpansion \endproof% %EndExpansion \textbf{Proof of Theorem \ref{th-beta0} (continued).} (\ref{eq-pf-step3-0}) implies \[ \eta E\left[ Y^{i}L^{i}R^{i}\mathbf{1}_{Y^{i}\leq 1-\eta }\right] =O\left( \mu \right) , \] where $\mathbf{1}_{Y^{i}\leq 1-\eta }$ is the indicator that $Y^{i}\leq 1-\eta $. Lemma \ref{l-eta} yields \[ E\left[ Y^{i}L^{i}R^{i}\mathbf{1}_{Y^{i}>1-\eta }\right] \leq P\left[ Y^{i}>1-\eta \right] =O\left( e^{-cm}\right) , \] which is at most $O\left( \mu \right) $ since $1/m\leq \left( 1/\delta \right) \mu $. Adding the two estimates gives (\ref{p1-2}) for $i$, thus completing Step 3. The rest of the Proof of Proposition \ref{p-1} is unchanged.% %TCIMACRO{\TeXButton{End Proof}{\endproof}} %BeginExpansion \endproof% %EndExpansion \subsection{Extensions\label{ss-extensions}} This work is a first attempt to analyze basic evolutionary models in extensive form games. A number of directions for further study suggest themselves: \begin{enumerate} \item \emph{Non-unique backward induction equilibrium}: Analyze the non-generic case where there is more than one subgame-perfect equilibrium; for instance, when some of the payoffs are equal. It seems that a subset of $% BI$, at times a strict subset, is obtained. \item \emph{Games with imperfect information}: Here we conjecture that all evolutionarily stable equilibria will be subgame-perfect, but the converse will no longer be true; evolutionary dynamics may well pick out certain refinements rather than others. \item \emph{Multiple agents and non-distinct populations}: This is discussed in Subsection \ref{ss-agents}, which suggests a number of relevant generalizations. \item \emph{Other selection dynamics}: These are discussed in Subsection \ref{ss-selection}. \end{enumerate} \begin{thebibliography}{99} \bibitem{} Aumann, R. J. [1995], ``Backward Induction and Common Knowledge of Rationality,'' \emph{Games and Economic Behavior} 8, 6--19. \bibitem{} Aumann, R. J. [1998], ``On the State of the Art in Game Theory,'' \emph{Games and Economic Behavior} 24, 181--210. \bibitem{} Cressman, R. and K. H. Schlag [1997], ``The Dynamic (In)Stability of Backwards Induction,'' mimeo. \bibitem{} Fudenberg, D. and D. K. Levine [1998], \emph{The Theory of Learning in Games}, MIT Press. \bibitem{} Gale, J., K. Binmore and L. Samuelson [1995], ``Learning to be Imperfect: The Ultimatum Game,'' \emph{Games and Economic Behavior} 8, 56--90. \bibitem{} Hammerstein, P. and R. Selten [1994], ``Game Theory and Evolutionary Biology,'' in \emph{Handbook of Game Theory, Vol. II}, R. J. Aumann and S. Hart (eds.), North-Holland, 929--993. \bibitem{} Hofbauer, J. and K. Sigmund [1998], \emph{Evolutionary Dynamics and Population Dynamics}, Cambridge University Press. \bibitem{} Kandori, M., G. Mailath and R. Rob [1993], ``Learning, Mutation, and Long-Run Equilibrium in Games,'' \emph{Econometrica }61, 29--56. \bibitem{} Kuhn, H. W. [1953], ``Extensive Games and the Problem of Information,'' in \emph{Contributions to the Theory of Games II},\emph{\ }H. W. Kuhn and A. W. Tucker (eds.), \emph{Annals of Mathematics Studies }28, Princeton University Press, 193--216. \bibitem{} N\"{o}ldeke, G. and L. Samuelson [1993], ``An Evolutionary Analysis of Backward and Forward Induction,'' \emph{Games and Economic Behavior} 5, 425--454. \bibitem{} Samuelson, L. [1997], \emph{Evolutionary Games and Equilibrium Selection}, MIT Press. \bibitem{} Vega-Redondo, F. [1997], \emph{Evolution, Games, and Economic Behavior}, Oxford University Press. \bibitem{} Weibull, J. W. [1995], \emph{Evolutionary Game Theory}, MIT Press. \bibitem{} Young, H. P. [1993], ``The Evolution of Conventions,'' \emph{% Econometrica} 61, 57--84. \bibitem{} Young, H. P. [1998], \emph{Individual Strategy and Social Structure}, Princeton University Press. \end{thebibliography} \end{document}