|
Article Excerpt
It has been shown (Hart [2]) that the backward induction (or subgame-perfect) equilibrium of a perfect information game is the unique stable outcome for dynamic models consisting of selection and mutation, when the mutation rate is low and the populations are large, under the assumption that the expected number of mutations per generation is bounded away from zero.
Here it is shown that one can dispense with this last condition. In particular, it follows that the backward induction equilibrium is evolutionarily stable for large populations.
Key words: evolutionary dynamics; evolutionary stability; Markov chains; transition times; backward induction equilibrium; large populations
MSC2000 subject classification: Primary: 91A22; secondary: 91A18
OR/MS subject classification: Primary: games
1. Introduction. In this paper, we follow the work of Hart [2]. We study the long-run behavior of evolutionary dynamics, we introduce a few notions of stability, and finally we show the stability properties of the backward induction equilibrium (BIE).
As in Hart [2], the games we consider are generic finite games in extensive form with perfect information. In these games, there exists a unique subgame-perfect equilibrium, or backward induction equilibrium. For each such game, there is an associated population game: at each node there is a distinct population of individuals who play the game in the role of the corresponding player.
The evolutionary dynamic process is a Markov chain on the space of the mixed strategies of the game with unique invariant distribution. We are looking for stable strategies in this model. When the populations are fixed, a strategy profile is evolutionarily stable if its occurrence is positive independently of the mutation rate, i.e., if its invariant probability is bounded away from zero as the mutation rate goes to zero. (1) When the populations increase, the number of possible outcomes of the dynamics increases, and the invariant probabilities of the different strategy profiles change. Therefore, we define a strategy profile to be evolutionarily stable for large populations (ESLP) if its invariant probability is bounded away from zero as both the mutation rate goes to zero and the populations increase to infinity.
In Hart [2] it is shown that when the populations are fixed, the BIE is evolutionarily stable. The main result there is that, in the limit, the BIE becomes the only stable outcome as the mutation rate decreases to zero and the populations increase to infinity, provided that the expected number of mutations per generation is bounded away from zero. In this paper, we show that in the models we consider this additional proviso (on the expected number of mutations per generation) is not needed. Thus, the BIE is also ESLP.
Section 2 presents the model. Section 3 defines stability and presents the main theorem. Section 4 explains two major assumptions in our model, that of mutation rate and that of population size. Section 5 proves the main theorem. The appendix proves several general propositions on Markov chains, needed for the proof of the main theorem.
2. The model. The model is as in Hart [2], except for a somewhat less general class of dynamics. (2) We present a summary of the model below.
2.1. The game. Let F be a finite extensive-form game with perfect information. Each nonterminal vertex corresponds to a move, and each move of one of the players is called a node. Let N be the set of nodes, and let [??] be the set of nodes and terminal vertices (i.e., the set of all vertices that are not chance moves). For each node i [member of] N, let N(i) be the set of nodes that are successors of i in the tree. Assume that the nodes are numbered {1, ..., n}, where n = [absolute value of N], such that j [member of] N(i) implies j > i.
The game is in agent-normal form: at each node i [member of] N there is a different agent with a set of choices [A.sup.i], which is the set of outgoing branches at i. Let A := [[PI].sub.i[member of]N] [A.sup.i], and let [u.sup.i]: A [right arrow] [??] be the payoff function of agent i, which is extended multilinearly to mixed strategies; thus, [u.sup.i]: X = [[PI].sub.i[member of]N] [X.sup.i] [right arrow] [??], where [X.sup.i] := [DELTA]([A.sup.i]) is the set of probability distributions over [A.sup.i].
The classic result of Kuhn [4] states that there always exists a pure BIE. We assume here that the game [GAMMA] has a unique BIE (this is true generically) which must therefore be pure; we denote it by b = [([b.sup.i]).sub.i[member of] N] [member of] A, and refer to [b.sup.i] as the "backward induction strategy of i."
We associate a population game (3) to [GAMMA]: at each node i [member of] N there is a nonempty finite population M(i) of individuals playing the game in the role of agent i. We assume that the populations at different nodes are disjoint. For each individual q [member of] M(i), let [[omega].sup.i.sub.q] [member of] [A.sup.i] be the pure strategy of q, and let [[omega].sup.i] = [([[omega].sup.i.sub.q]).sub.q[member of]M(i)] and [omega] = [([[omega].sup.i]).sub.i[member of]N]. The proportions of the different pure strategies in population i induce a mixed strategy of agent i. We therefore have a map x of each [omega] to a vector of mixed strategies, where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]--the probability of [a.sup.i]--is the proportion of individuals in populations i that play [a.sup.i].
2.2. The dynamics. We now come to the dynamic model. We formulate the dynamics as discrete-time stationary Markov chains.
Since they are evolutionary, the dynamics are based on selection, i.e., changes toward better strategies, and on mutations, i.e., random changes. Each period of the dynamics is assumed to be small enough that the probability that more than one individual in each population will change his strategy is negligible. Thus, we assume that at each period, at most one individual may change his strategy, either due to selection or due to mutation.
For every mutation rate parameter [mu] > 0, and population size m such that (4) [absolute value of M(i)] = m for all nodes i [member of] N, the process is a stationary Markov chain on the state space [[OMEGA].sub.m] := [[PI].sub.i[member of]N] [([A.sup.i]).sup.M(i)], where a state [omega] of the system specifies the pure strategy of each individual in each population, as defined in [section] 2.1. The one-step transition probability of the process is given by a transition matrix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that satisfies (5):
* Conditional independence over i [member of] N, i.e., (6)
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2.1)
* For each i [member of] N, one individual q(i) [member of] M(i) is chosen, such that there exist constants [[gamma].sub.1], [[gamma].sub.2] > with
[[gamma].sub.1]/m [less than or equal to] Q[q(i) = q | [omega]] [less than or equal to] [[gamma].sub.2]/m for each q [member of] M(i) and (2.2)
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2.3)
* There exists a constant [sigma] > such that, for each [member of] N,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2.4)
where [B.sup.i] [equivalent to] [B.sup.i](q(i), [omega]) := {[a.sup.i] [member of] [A.sup.i]: [u.sup.i]([a.sup.i], [[omega].sup.-i]) > [u.sup.i]([[omega].sup.i.sub.q(i)], [[omega].sup.-i])} is the set of "better strategies"--those strategies at node i that are strictly better in [GAMMA], against the populations at the other nodes, than the strategy [[omega].sup.i.sub.q(i)] of the chosen individual q(i), and [S.sup.i] [equivalent to]...
|
