JOURNAL

OF ECONOMIC

THEORY57, 278-305(1992)

Evolutionary
Stability in Repeated
Played by Finite Automata*
KENNETHG.

Games

BINMORE

Departmentof Economics,
University
College of London,
Departmentof Economics,
University
qf Michigan,

London,WCIE 6BT,
Ann Arbor, Michigan

England,48109

Madison,

53706

and

AND

LARRY SAMUELSON
Departmentof Economics.
Received

University

Decemberof Wisconsin.

5, 1990; revised

November

Wisconsin
20, 1991

We consider a game in which “meta-players”
choose finite automata
to play arepeated stage game. Meta-players’
utilities are lexicographic,
first increasing in the(limit-of-the-means)payoffs of the repeatedgame and second decreasingin thenumber of states in their automaton.
We examine the outcomes in this game which
satisfy a version of evolutionary
stability that has been modified to permit existence.
We find that such automata
must be efficient, in that they must maximize
the sumof the (limit-of-the-means)payoffs from the repeated game. Journal of Economic
Literature
Classification
Numbers:
C70, C72.
‘0 1992 Academic Press, Inc

1. PREVIEW

Although the results in this paper are applicable in general, attention willoften be focused on the Prisoners’ Dilemma in the form given on the leftof Fig. 1. The shaded region in the diagram on the right of Fig. 1 is the setof payoff pairs that the “Folk Theorem” (Aumann [3]) shows to beachievable by equilibrium
play in the infinitely repeated version of the
Prisoners’ Dilemma
with “limit-of-the-means”
payoffs (which we call
“profits” in this paper).
Abreu and Rubinstein[l] study a model in which each of two“metaplayers” choose a finite automaton to play the infinitely repeatedPrisoners’ Dilemma on their behalf. In one specification of this model, themetaplayers have lexicographic preferences. They seek to maximize their* Financial
supportfrom the NW0 (Netherlands
846-276)is gratefully
acknowledged,is the hospitality
and supportof the CentER
for Economic
Research at Tilburg
University.

278
0022-053

l/92 $5.00

Copyright
rS, 1992 by Academic Press, Inc.
All rights of reproductmn
m any form reserved.

asEVOLUTIONARY279

STABILITY

Fa
2

2

3

-1

-I

3

0

0

FIG.

I.

The Prisoner’s

Dilemma

profit; but if two automata achieve the same profit, a metaplayer prefers
whichever is less complex. Nash equilibrium outcomes in this automaton
selection game are the rational points lying on the cross shown on the rightof Fig. 1.
Abreu and Rubinstein interpret their result in terms of decision-makers
of unbounded rationality who must delegate authority to subordinates who
can only reliably execute simple decision rules. The interpretation to be
explored in this paper is that the metaplayers are a metaphor for an
evolutionary process. That is to say, the automata represent rules-of-thumbthat have evolved during past plays of the (infinitely repeated) game. If
metaplayers are to be seen as a metaphor for an evolutionary process, thenit is natural to replace the notion of a Nash equilibrium by an appropriate
version of the idea of an evolutionarily stable strategy. This paper examines
the evolutionary viability of strategies in automaton selection games of the
Abreu-Rubinsteinvariety.
With the notion of evolutionary viability that we employ, only (2,2) inthe diagram on the right of Fig. 1 survives as a possible equilibrium outcome of the infinitely repeated Prisoners’ Dilemma. The same argument,
applied to a general two-player, normal-form
game’ shows that only
utilitarian outcomes are substainable as evolutionary
viable equilibria.
However, we are anxious that the paper not be seen as a stylized defenseof utilitarianism
valid for all societies without qualification. Some of ourassumptions need to be treated with great reserve for the reasons explainedin Section 4.
’ The extensions

to n-player

games are straightforward,

but we do not discuss them.

280

BINMOREAND

SAMUELSON

CD

CD

DEFECT
nasty

COOPERATE
nice
CD

D

C

M
D

C

D

C
TIT-FOR-TAT
nice

GRIM
nice
C

C

C

D
D
m

TAT-FOR-TIT
nasty

c

D
TWEEDLEDUM

-

nice

C

d-d

C,D

D

D

C

TWEETYPIETWEEDLEDEE
nice
FIG.

2.

Some automata

The idea behind our argument is of ancient vintage. Recent papers that
use the idea include Binmore [S], Fudenberg and Maskin [13] andRobson [23]. An initiallynonutilitarian
population
is vulnerable toinvasion by mutants who recognize each other by means of what Robson[23] calls a “secret handshake.” This private signal allows the mutants toform an insider group who cooperate among themselves but treat outsiders
as outsiders treat each other. As a result, insiders earn a higher average
payoff than outsiders, and so the latter are displaced. Only utilitarianmachines can be immune to such invasions and so they are the only
possible candidates for evolutionary viability.
Axelrod and Hamilton[6] are perhaps the most notable of the contributors to what is now a large literature on the “evolution of cooperation.” Their evolutionary defense of TIT-FOR-TAT
as a strategy for theinfinitely repeated Prisoners’ Dilemma is much cited.
Figure 2 shows a representationof TIT-FOR-TAT
as a finite
automaton’
along with a number of other strategies for the infinitely
2The particular
type of automaton
we use is called
Ullman [14]).
Appendix
B discusses some of the formal
without
penetratingthese mysteries.

a Mooremachine(Hopcraftandissues, but the paper can be read

EVOLUTIONARYSTABILITY

281

repeated Prisoners’ Dilemma. 3 Each circle in a diagram of Fig. 2 indicatesa possible state of the machine. The letter written inside the circle shows
the action the machine will take in the Prisoners’ Dilemma when in thatstate. The arrows indicate how machines make transitions from one state toanother. For example, after TIT-FOR-TAT
has just defected (D), it willremain in its D state if the opponent just played D, but will shift to its C
state if the opponent just cooperated (C). The initial state of a machine isshown by an arrow with no source.
When only profits are considered, all the strategies represented by theautomata of Fig. 2 are Nash equilibria against themselves except for
COOPERATE
and TWEETYPIE.4
In particular, as emphasized by
Axelrod and Hamilton [6], TIT-FOR-TAT
is a Nash equilibrium against
itself. However, two TIT-FOR-TAT
machines do not constitute a Nashequilibrium
for the automaton selection game of Abreu and Rubinsteinbased on the Prisoners’ Dilemma. COOPERATE
is a better reply to
TIT-FOR-TAT
than TIT-FOR-TAT
is to itself, because COOPERATE
gets the same profit in the repeated Prisoners’ Dilemma when playing
TIT-FOR-TAT,
but COOPERATE
has the additional advantage of being
less complex than TIT-FOR-TAT.
In our evolutionary model, this implies
that a population consisting entirely of TIT-FOR-TAT
machines can beinvaded by COOPERATE
mutants.
In Axelrod’s [S] terminology, a nice machine is one that is never the firstto defect. TIT-FOR-TAT
is therefore a “nice” machine. Axelrod [S]emphasizes the success of nice machines in his setting. However, in ourmodel the same reasons that destabilize TIT-FOR-TAT
also apply to any
population consisting entirely of nice machines.5 A population therefore
cannot be evolutionarily
viable in our model unless it contains at least
some machines that are nasty (i.e. not nice). To this extent, our work is atvariance with Axelrod’s.
The machine TAT-FOR-TIT
of Fig. 2 is a nasty machine. It begins bydefecting and treats a corresponding defection by the opponent as a secrethandshake signaling a switch to its C state. In contrast to the case of two
TIT-FOR-TAT
machines, two TAT-FOR-TIT
machines constitute aNash equilibriumin the Abreu-Rubinstein
automaton selection game.
Moreover, two TAT-FOR-TIT
machines achieve the utilitarianoutcome (2,2) and so do no worse than two TIT-FOR-TAT
machines.
3 Appendix
A contains a listing of all one and two state machines capable of playing theinfinitely
repeated Prisoners’
Dilemma.
4 Appendix
A contains
a payoff table for all pairs of one and two state machines.
‘Anypopulationof nice machines
is vulnerable
to invasion
by COOPERATE
mutants
except a populationconsisting
entirely of COOPERATE
machines. But such a populationisvulnerable
to invasion by DEFECT
mutants.

282

BINMORE AND SAMUELSON

The fact that two TAT-FOR-TIT
machines are a Nash equilibrium does
not guarantee that a populationof TAT-FOR-TITS
is evolutionarily
stable in the Abreu-Rubinstein
automaton selection game. In fact, thegame has no strategies that are evolutionarily
stable according to thestandard definition. This is not a problem that is special to Abreu andRubinstein’s model. Existence problem for evolutionarily
stable strategies
have been well-documented in a number of other variants of the infinitely
repeated Prisoners’ Dilemma (Boyd and Lorberbaum [9], Farrell andWare [ 111, and Kim [ 163). The nonexistence problem arises because thestandard definition requires that any mutant bridgehead will be entirely
eliminated. However, a mutant player whose behavior would differ fromthat of an existing strategy only off the equilibrium path will necessarily be
indistinguishable
from existing strategies on the equilibrium
path, andhence cannot be driven out.
Using a modified definition of evolutionary stability that takes accountof this difficulty, we show that a population consisting entirely of TATFOR-TIT
machines is evolutionarily
viable. However, the new definition
makes it impossible to ignore the case of polymorphous
populations
in which different machines may co-exist in a symbiotic relationship.
Extending our analysis to include such populations, we show in generalthat only utilitarian outcomes are evolutionarily viable.
The paper is organized in the following way. Sections 2 and 3 provide a
discussion of the issues that motivate our work. Section 4 considers someof the modeling problems that our approach entails and explains how wedeal with some of these problems and evade others. Sections 5 and 6 introduce the necessary formalities, and introduce our modified definition of anevolutionary
stable strategy. Section 7 establishes that a populationconsisting of only one type of machine must be utilitarian if it is to be
evolutionarily
stable according to our modified definition. Section 8 seeks
to explain why such a result needs to be generalized to the case ofof machines. Section 9 provides such a
polymorphous
populations
generalization.
2. EQUILIBRIUM

SELECTION

When more than one equilibrium
exists, the problem of selecting one
from among them is not easy. But progress on this front is necessary ifgame theory is to break out of the beachhead it has established in thesocial sciences.
In seeking insight into the equilibrium selection problem, it is sensible tofirst look at simple examples. In such simple examples, the “right”
equilibrium often seems glaringly obvious, and it may be easy to give lists

EVOLUTIONARYSTABILITY

283

of plausible ad hoc reasons why the right equilibrium should be selected.
However, such principles are notoriously
unreliable when applied ingeneral. The purpose of the enterprise is not to pluck a selection criterion
from the air that happens to be intuitively satisfying in particular cases. It
is to find selection criteria that are defensible from first principles. Our
selection criteria, for example, choose the utilitarian outcome. One could
give a hundred reasons drawn from political philosophy why the utilitarianoutcome should be desirable, but none of these reasons are relevant to ourconcerns.6
Our approach to the equilibrium selection problem is based on studying“trembles,” as is the widely advertised “refinements of Nash equilibrium”
literature. Indeed, this seems inevitable. In traditional analyses, players use
their equilibrium strategies because of what would happen if they did not.
It is therefore necessary to contemplate counterfactual hypotheses of thetype: suppose a player who is sure to play his equilibrium strategy, doesn’t.
Philosophers (e.g., D. Lewis [ 183) discuss the meaning of such counterfactuals in terms of “possible worlds.” It is true that no player will deviate
from his equilibrium strategy in this world, but there are possible worlds inwhich he would. Our task is to find the closest possible world to our own
in which the deviation occurs. A tremble can then be thought of as being
the change in our own world necessary to bring about the closest possible
world in which the deviation occurs. Equilibrium
selection proceeds byretaining only those equilibria that remain equilibria in the analyst’sfavored closest possible world.
But the word “closest” has no a priori definition in this context. An equilibrium selection theory that employs this methodology must assign theword a meaning by choosing the nature of the trembles it takes as being
relevant. It is natural that economists should be reluctant to abandon
the paradigm of an economic agent as a “perfectly rational” optimizer.
Traditionally,
trembles are therefore imposed only on the rules of thegame, the preference of the players, or the beliefs that the players hold.
A strong bias exists in favor of the first of these. This is explicit in Selten’s[25] “trembling-handperfect” equilibrium,
which is obtained by adding
appropriate chance moves to the original game. A similar attitude pervades
the refinements literature, being implicit, for example, in the definitions ofsequential or subgame-perfect equilibrium.7
60~raims are the same as the even more easily misunderstoodwork of Aumann
andSorin [4] or Anderhni[2] who are concernedwith equilibrium
selection in games of pure
coordinationin which one equilibrium
Pareto-dominates
the others. Nothing
could be easieror less relevant
than to solve the problem
they set for themselves
by inventing“collective
rationality”
principles
like: reject any equilibrium
Pareto-dominatedby another.
’ Even the successive deletion of weakly dominatedstrategies requires a similar treatmentof counterfactuals.

284

BINMORE AND SAMUELSON

Unlike the refinements literature and the otherwise closely related workof Fudenberg and Maskin [13], we see the traditional types of tremble
only as epiphenomena. Such trembles will indeed be significant in manycases, especially in evolutionary animal biology, but they are seen here as
secondary in games played by humans. For this reason, we do not consider
environmental trembles in this paper.’
The trembles this paper takes as primary are those in the thinking processes of the players. The idea is that, if an opponent plays irrationally, theexplanation of first resort should be that he or she reasoned irrationally(and therefore may perhaps reason irrationally in the future). The trembles
we wish to study are therefore internal to the players rather than external,
as in traditional
treatments.’ Such an approach requires modeling thethinking processes of the players explicitly.
How are the thinking processes of a player to be modeled? The avenueof investigation that we regard as most promising abandons the theory thatpeople think deeply about their behavior when interacting with others
in game-like situations. Instead, they are seen as hosts for “memes.”
Dawkins [lo] uses the term meme to include rules-of-thumb, social norms,
conventions, or other more complex idea systems that a human being may
use in translating a stimulus into a response. Evolution is seen as being
responsible for a selection being made from the pool of possible memes.
After evolution has operated, non-selected memes play a role in interpreting counterfactuals much like that played by trembles in traditional
refinement theory. In brief, the non-selected memes serve as “explanations”
for what would happen if selected memes were to deviate from equilibrium
play.

3. BOUNDED RATIONALITY
The previous section explains why we seek to model the thinking processes of the players in a game explicitly. The device used for this purposeis the idea of a finite automaton as outlined in Section 1 and, more formally, in Appendix B. The exposition is often less clumsy if players are
identified with the finite automaton that represents the strategy they areusing. However, a more generally applicable paradigm sees the finite
automaton as something like a virus that controls the strategy of a player’ The common
criticism of Axelrod’s
work, that a pair of TIT-FOR-TAT
strategies is not
subgame-perfect,is therefore
not relevant
to our concerns. Nor is Kalai and Neme’s [IS]similar criticism of the results of Abreu and Rubinstein[ 1).
9 With the notable exceptionof the “gang of four” paper [17] and related work.

EVOLUTIONARYSTABILITY

285

who gets infected with it. The virus then spreads at a rate determined by
how well the strategy performs relative to other strategies currently in use.
One virtue of working with finite automata is that they focus attention
on the complexity of strategies and the possible cost of complexity. It isnot, however, obvious how such costs are to be incorporated into a formal
model. It is often taken for granted in the literature on “bounded
rationality”
that one should work with a fixed, exogenously determined
upper bound on the complexity of the automata to be studied. We would
prefer to characterize work in which this assumption is made, notably thatof Neyman [22], as being concerned with uniformly bounded rationality.
With such an assumption, it is easy to see that a pair of GRIM machines(Fig. 2) is a Nash equilibrium for an automaton selection game based on
a 100 times repeated Prisoners’ Dilemma provided that machines with morethan 99 states are excluded. This cooperation is achieved because amachine that plays better against GRIM than GRIM itself will necessarily
cooperate in every round but the last, when it will defect. Such a machinemust be able to count to 100 in order to know when the last round has
arrived, but a machine with only 99 states can count only to 99.”
The difficulty with models incorporating
an exogenously determined
upper bound on the complexity of a machine is that cases can arise inwhich a highly complex machine may achieve only a relatively small payoffin equilibrium,
although a much higher payoff might be achieved if themachine were replaced by another machine with just one additional state.
Because of this difficulty, we follow Abreu and Rubinstein [l] in studying
models in which the bound on complexity is endogenously determined. l1
Such an assumption always permits a machine to be displaced by anothermachine of slightly greater complexity if the resulting improvement in game
payoffs is sufficiently large. (One may always “think a little harder” if theprospective benefits make it seem worthwhile.)
In measuring complexity, we simply count states. The complexity Ial ofa machine a is therefore how many states it has. All the machines of
Figure 2 have complexity 2 except for DEFECT and COOPERATE
which
have complexity 1. .4 discussion of this complexity measure, which isarbitrary to a considerable degree, is postponed until the next section.

‘” Neyman[22] shows that a clever constructionof the implicit messages that the machines
send each other throughtheir behavior
in the early stages of the game allows equilibrium
payoffs very close to the utilitarianoutcome to be achieved in a 100 times repeated Prisoners’
Dilemma,even when the uniform
bound on the complexityof a machine is very much higher
than 99.
‘I It is sometimes
arguedthat such models
are not properly
models of “bounded
rationality”.
If this argument
is thought
persuasive,then one can refer to “imperfectrationality”
or “costly rationality”
to describe our approach.

286

BINMOREAND

SAMUELSON

4. MODELINGISSUESIn evolutionary
game theory, a game G is seen as being played
repeatedly. Each time it is played, Nature chooses its players from a
population whose composition changes over time. The players do not think
about how to play G. They are endowed with strategies by a process ofmutation and selection that tends to eliminate strategies that are relatively
less successful. In the literature, G is usually a normal-form game, but inour paper it is itself the repeated game G”.
Ideally, one would evaluate the players’ income streams in G” using a
discount factor p that represents the probability that the game will cointinue beyond any stage reached in G”. Thus, although G’^ would bemodeled as an infinite game, it would end in finite time with probability
one, so that no difficulty arises in constructing an evolutionary model inwhich the “infinitely repeated” game G z is repeatedly played. Within thiscontext, we are interested in cases in which p is relatively large, so thatthe future is relatively important. In order to construct a mathematicallysimple model, however, we first assign payoffs to income streams using
the limit-of-the-means
criterion rather than discounting. This can be viewed
as focusing on the case in which p approaches unity while glossing overthe problems that arise in going to the limit. Appendix C examines theselimiting problems in the course of extending the results to the case of
discounting. Whether discounting or limit-of-the-means
payoffs are used, it
is essential to our analysis that players be patient. This ensures that the
mutants we construct can deliver their secret handshakes without suffering
undue payoff losses.
The strategies that players use in G” are modeled as finite automata.
Our basic intuition is that interesting evolutionary processes will tend toselect against complex machines unless their complexity generates real
gains compared with less complex machines. We model this by introducing
costs of complexity into players’ utility functions.
The crudeness of such an approach is compounded by our measuring
complexity by simply counting states. It is important to our analysis thatstates be costly, as this ensures that existing machines will not containstates that are not used in equilibrium
but could be used to inflict harshpunishments on machines which offer secret handshakes. As Banks andSundaram [7] have shown, however, other measures of complexity may
lead to different conclusions. Moreover, we look at the extreme case inwhich costs of complexity are ranked lexicographically behind profits. We
should stress that this allows us much freedom in constructing possible
mutants when testing the stability of populations. Successful mutants may
be vastly more complex than the population they invade provided onlythat they succeed in achieving a slightly higher profit.

EVOLUTIONARY287

STABILITY

We follow the standard practice of evading a study of the dynamics ofthe evolutionary process by appealing to the idea of an evolutionarily
stable strategy. Our modification of this definition to suit our special circumstances, though essential to our results by allowing us to avoid the difficulties arising out of the nonexistence of an evolutionarily stable strategy,
will probably not be controversial. However, it is important to stress thatevolutionarily stable strategies are desgined for use in a biological context.
Mutations are then rare, so that after each mutant invasion, the system hastime to attain a new equilibrium before the next mutant invasions. Is sucha model appropriate in our context? We think that socioeconomic evolution would be better modeled by supposing that mutations are sufficiently
frequent that the systems do not have time to adjust to the last mutation
before the next appears. In particular, we plan a future paper in which
there is a steady stream of mutations consisting of simplified versions of
those machines that are currently present in the population.”
In pointing out this last possible inadequacy in our model, we areagreeing with Fudenberg’s [12] criticism that our model is overly
restrictive in the type of trembles that equilibrium strategies must confront.
Note, however, that our remedy does not lie in appealing to Selten’s
trembling hand but in expanding the set of mutations to be considered.

5. FORMALITIES

Only two-player games are considered. The underlying game G is
specified by a quadruple (S, , S,, 7c,, x2) in which S, and S, are strategy
sets and the payoff functions are 7ti: S, x S, + R (i= 1,2). The Prisoners’
Dilemma on the left of Fig. 1 will be the principal example.
A repeated game G” = (R,, R,, P,, P2) with the underlying game G as
its stage-game, is constructed in the usual way. The payoff functions P, andP2 are defined as limits of the means.13 (Discounting
is discussed inAppendix C.) ThusP,(rl, r2) = !FE$'f' ~i(rl(hr),t=0r2(h,)),“We
believe that such a model may lead to markedly
different
conclusions,
Linster [ 193providessome support
for such a conjecture
while pursuing
Nachbar’s[21] criticismsofAxelrod’s“Olympiad”
simulations.
He Ends that GRIM
does exceedingly
well, much better
than TIT-FOR-TAT,in simulationsof evolutionary
competition
between one and two statemachines provided
that the inflow of mutants is sufficiently
rich and varied.
I3 Since only strategies
implementableby finite automata
are considered,P,(r,, r2) will
always be defined.

288

BINMORE AND SAMUELSON

where h, denotes the history of the game up to and including time t, andrj(h,) is the action in Sj taken by player i at time t + 1. The number
Pj(r, , r2) will be called a profit.
An automaton
selection game G# is defined as in Abreu andRubinstein [ 11. The strategy space Ai consists of a set of finite automata(Moore machines) described formally in Appendix B. An automaton a inthe set Ai is capable of occupying the role of player i in the repeated game
G”. No confusion will result from using a to denote the strategy implemented by the automaton a in G” as well as the automaton a itself.
The automaton selection game G# = (A,, A,, U, , U2 ) is played by two
metaplayers. The payoff functions Uj reflect the fact that the metaplayers
are assumed to care, not only about profits in G’“, but also about the complexity (al of the machine to which they delegate the duty of playing G”‘.
The precise assumption to be made attributes lexicographic preferences tothe metaplayers. More precisely
U,(a, c) > U,(b, cl-with a similar requirementin the machine u.)r4{P,(a, cl> P,(b, cl)or{P,(a, c) = P,(b, cl

and I4 < I4 1,

for U,. (Recall that Ial is the number of states

6. EVOLUTIONARYSTABILITY

In Abreu and Rubinstein [ 1 ] a metaplayer’s choice of an automaton isinterpreted as an act of delegating responsibility for the play of G” to asimple-minded
underling. In this section, the choices attributed to themetaplayers are assumed to emerge from an evolutionary process.
The case when G is symmetric will be studied first. Then G# is also symmetric and we may write A = A, = A2 and Ul(u, b) = U(u, b) = U,(b, a).
For the moment, forget that U represents lexicographic preferences. If,
instead, U measures fitness, then the standard criteria (Maynard
Smith [20]) for a to be an euolutionurily stable strategy (ESS) are
(I)
(II)

U(a, a) > u(b, a), orU(u, a) = U(b, a) and U(u, 6) > U(b, b),

for all possible mutants b. These conditions imply that a is a best response
to itself, and hence (a, a) is a symmetric Nash equilibrium for G#. In addiI4 We choose to represent the lexicographic
preferences
here with a utility function
exists because the set of finite automata
is countable)
in order to ease comparison
modifieddefinitionof evolutionary
stability with the standard
definition.

(whichof ourEVOLUTIONARY289

STABILITY

tion, the ESS conditions incorporate a stability requirement. For any alternative best response b to a, a must be a better response to b than b is itself.
The ESS requirements are intended to capture the idea that a populationof replicas of a should be invulnerable to invasion by sufficiently small
groups of mutant b’s.
With lexicographic preferences, (I) and (II) need to be modified. The
modified requirements for a to be an ESS are
(i)
(ii)
(iii)

P(a, a) > P(b, a), orP(a, a) = P(b, a) and P(a, b) > P(b, b), orZ’(a, a) = P(b, a) and P(a, b) = P(b, b) and Ial < jbl,

for all possible mutants b. The principle is that profits are always counted
before complexity.
Various authors have commented on the existence problem for an evolutionarily stable strategy in the repeated Prisoners’ Dilemma, including
Boyd and Lorberbaum [9], Kim [16], and Robson [23]. Existence is also
a problem for the modified definition of an ESS given above. Since it iseasy to see that COOPERATE
and DEFECT can both be invaded, thefollowing result shows that no automaton satisfies this definition of an ESS
when G is the Prisoners’ Dilemma.
LEMMA 6.1. For any G, an automaton a that satisfies (i), (ii) or (iii) for
all automata b has only one state.

Proof
This is obvious if G has only one action. If G has two actions,consider an automaton a with more than one state that satisfies (i), (ii) and(iii). Suppose that a uses action x in its initial state. Now construct amutant b that is identical to a except that, if its opponent plays somethingother than x when b is in its initial state, then b switches to a different statefrom that to which a would switch. Then la1 = lb1 and P(u, a) =P(b, a) = P(u, b) = P(b, b). The reason for the latter set of equations is thata and b always use x in their initial state, and a and b are indistinguishable
in play provided that their opponent uses x in its initial state. Thus the
hypothesis that a has more than one state leads to the conclusion that noneof (i), (ii), or (iii) hold. 1
Existence problems of this type seem to us to be an artificial constructarising from a definition of an ESS that is not entirely appropriate to thesituation. l5 The standard definition of an ESS demands that any sufficiently
small invading group of mutants be eventually eradicated. One certainly
I5 The existence problem
does not arise because automata
always yield a host of out-of-equilibrium
paths in a repeatedbe constructedby altering behavior
on these paths.

64?‘57:?-3

are used. Any pure strategy
game, and invading
mutants

will
can

290

BINMOREAND

SAMUELSON

would wish to use a definition that precludes mutant invasions in which theoriginal small mutant bridgehead expands at the expense of the original
normal population. But what of mutant invasions after which the original
bridgehead neither expands nor contracts? The original normal populationand the mutant invaders will then survive together in a state of peacefulco-existence. In particular, the observed behavior of both natives andinvaders may be precisely the same, their differing strategies leading todifferent behavior only under unrealized contingencies. As regards putative
applications to human societies, who cares if different people would behaveslightly differently under certain unrealized contingencies if, in fact, they all
cooperate in sustaining a utilitarian outcome?
To accommodate this issue we introduce a further modification
into
the evolutionary viability requirement to be studied. A machine a will becalled a modzj2ed evolutionary stable strategy (MESS) if, for all possible
mutants b,
(1)

(2)
(3)

P(a, a) > Ptb, a), orP(a, a)=P(b,a) and P(a, b)>P(b,b), orP(a, a) = P(b, a) and P(a, b) = P(b, b) and Ial < Jbl.

As will become clear, one cannot dispense with the definition of a MESS
simply by considering a mixed ESS or a polymorphous extension of the
ESS idea.16 On the other hand, polymorphous MESSES will be important
for the reasons given in Section 7. However, in this and the following
section, the polymorphy issue is put to one side in an attempt to ease theexposition.
Complexity is important in the requirements for a MESS because its
inclusion means that a MESS a can have no states that are not used whena plays G ” against itself. i’ If an unused state existed, an automaton b
could be constructed that is similar to a but which dispenses with theunused state so that 161< Ial. The automaton b plays G” exactly as a plays
G” provided that its opponent has always played G” exactly as a plays
G” in the past. It follows that P(a, a) = P(b, a) = P(u, b) = P(b, b), andhence Condition (3) for a MESS is violated. This is one of the easierarguments of Abreu and Rubinstein [l]adapted to our purpose.
Appendix B (Lemma B. 1) provides the formal details.
Note that it follows from the fact that all states must be used in equiI6 A mixed ESS occurs when no suhiciently
small group of mutants can invade a population
whose members all play the same mixed strategy. A polymorphy
occurs when no member ofthe population
randomizes,
but the effect is the same for an invading
mutant because different
members of the original populationuse different
pure strategies.
” Rubinstein’s[24] original work on automata
used a criterion
that called for all states tobe used infinitely
ofren. We see no grounds for imposing such a constraint
here.

EVOLUTIONARY

291

STABILITY

librium that neither TIT-FOR-TAT
nor GRIM can be a MESS (although
this does not preclude their being constituents of a polymorphous MESS).
So far, only the case of a symmetric underlying game G has been considered. This section concludes by describing how asymmetric games may
be addressed. In the symmetric case, automata do not “know” whether
they are player 1 or player 2. Even if the payoff matrix for G is symmetric,
this lack of information may be a handicap. For example, if the 3s in theversion of the Prisoners’ Dilemma of Figure 1 are replaced by 6s it ceases
to be true that the sum of the payoffs is maximized at (C, C), The sum ismaximized instead at (C, D) or (D, C) (or some mixture of these).
If this problem arises or the payoff matrix of G is asymmetric, we will
follow the standard practice in evolutionary game theory of introducing asymmetrized version of G# to be denoted by G# #. The first event in G” #consists of the automata receiving a signal indicating whether they are to
be player 1 or player 2, where each signal is received with probability l/2.
An automaton a can then be seen as a pair (a,, a,) of simpler automata inwhich a, is used when a acts as player 1, and a2 is used when a acts asplayer 2.
The profit for player 1 in the symmetrized game G# # is given by

The complexity of the machine a = (a,, az) in the symmetrized game istaken to be la\ = la, 1+ la, I. These definitions allow a utility function V tobe defined lexicographically by writing
V(a, c) > V(b, c)o{P(a, c) > P(b, c)}or{p(a, c) = Y(b, c)

and Ial < Ib( >.

One may then take G # # to be the quadruple

in which V, and V, are defined by V,(a, 6) = V(a, 6) = V,(b, a).

7. UTILITARIAN

AUTOMATAWhen a plays itself in G ’ # , the largest value its profit can be is

292

BINMORE AND SAMUELSONAn automaton a* that achieves this maximum will be called a utilitarian
automaton for G## because it acts to maximimize the sum of payoffs in theunderlying game G. ‘*
A utilitarian automaton a* in G# is defined to be one that satisfies (I),but with the maximization subject to the additional constraint that s, =s2.
This constraint reflects the fact that no mechanism is provided in G” forbreaking the symmetry of G. Of course, when G is the Prisoners’ Dilemmaof Fig. 1, the utilitarian profits for G” and G## are the same. Unless thisis the case, the definition of a utilitarian automaton for G# is of no greatinterest.
THEOREM

7.1. An automaton a can be a MESS in G## only if a isurilitarian.
Proof: Let a* be a utilitarian automaton and, for the purposes of contradiction, let a be an automaton which is a MESS but is not utilitarian.
It will be shown that a population consisting entirely of replicas of a canbe displaced by a mutant b. The mutant b will be more complex than a,but complexity counts after profit in the lexicographic preferences describedby U.
The mutant b is constructed to have the following properties:

Initially,l6, outputs a strategy for G that differs from ai’s initial

output.
If the initial output of the opposing machine differs from a-$‘s
initial output, then bi “knows” that it is playing a replica of itself. It therefore continues by mimicking the utilitarian automaton a,*
If the initial output of the opposing machine is the same as a pi’s
initial output, then 6, “knows” that it is playing a. It therefore emits an output in the next period that “convinces” a that its opponent is a replica ofitself, and then continues by mimicking ai, and so achieves a profit ofP(a, a).
ll

If such a machine b can be constructed, then it follows from the third
property that P(b, a) = P(a, a) = P(a, b). But P(b, b) = P(a*, a*) > P(a, a).
Thus none of the criteria (1) (2), or (3) for a MESS are satisfied and thetheorem follows.
It remains to be confirmed that the third property for the mutant b can
be satisfied, and so P(b, a) = P(a, a) = P(a, 6). This is not entirely obvious.
For example, if a were the GRIM strategy of Fig. 2 and G were thePrisoners’ Dilemma of Fig. 1, then b’s playing differently from a at the first
I* But one must recall that P is a “limit of means.” Thus a* need not maximize the sum of
payoffs in every stage game.

EVOLUTIONARYSTABILITY

293

stage of G” would push a into its punishment phase for ever. Thus
P(b, a) = 0 < 2 = P(a, a). Note, however, that the GRIM strategy is not a
MESS because it has a state that is unused in equilibrium. This observationis the key in establishing that P(b, a) = P(a, a) = Z’(a, b).
Suppose that b,‘s initial action switches uei from its initial state q,, toanother state q. Since all of C,‘S states are used in equilibrium, uei would
eventually reach state q when playing a,. At that time, let a, be in state q*
generating output r. The automaton h should therefore be constructed sothat, if the opponent’s initial output is the same as a- ;‘s, then b switches
to a state which we will label q* and emits the output r. After that, b can
mimic ui without difficulty. Appendix B (Lemma B.2) provides the details.
A machine designed in this way satisfies the third of the three properties
attributed to b. In particular, P(b, a) = P(u, a) = P(u, b). 1
Theorem 7.1 provides a necessary condition for an automaton to be a
MESS in G##. The same necessary condition, of course, holds for G#.
Sufficient conditions for the existence of a MESS are easily obtainedusing Folk Theorem arguments. We again quote only the result for G##.
THEOREM 7.2. Let ti denote the pure strategy minimux point of theunderlying game G. Let u be its utilitarian outcome. Then a sufficient condition for the existence of a MESS in G’ # is that u 2 rii.

Note that the sufficient condition of Theorem 7.2 need not be satisfied.
Its failure will sometimes be a consequence of the exclusion of mixed
strategies from the analysis. Our results can be extended to machines that
output mixed strategies for G rather than just pure strategies.lg One canthen replace ti in Theorem 7.2 by its mixed strategy equivalent V< ti.
However, there remains no guarantee that u > 6. If this inequality fails, a
MESS fails to exist.
8. POLYMORPHOUS

POPULATIONS

The definition of an evolutionarily stable strategy is designed for the casewhen mutations come at sufficiently infrequent intervals that the system
can fully recover from the effects of repelling one mutation before the next
appears. The definition of a MESS is inconsistent with such a story because
it allows for the possibility that certain mutations may not be repelled atall. After an invasion by such a mutant, the system will therefore not revert
to its original state. This section illustrates the significance of this featureof the definition.
I9 An alternative
would
to insist on pure outputs.

be to allow the machines access to random inputs,
This approachcreates difficulties
for our analysis,

but to continue

294

BINMOREAND

SAMUELSON

Appendix A summarizes the relevant properties of all one and two statemachines that are capable of playing the infinitely repeated Prisoners’
Dilemma. Observe that a population consisting entirely of TIT-FOR-TAT
machines will be displaced by an invasion of mutant COOPERATE
machines. After the invasion, all machines will be getting the utilitarian
profit, but COOPERATE
has an advantage in that it is less complex. With
the exception of a populationconsisting only of copies of the
COOPERATE
machine, the same goes for any populationof nicemachines.
This argument shows that no nice machine can be a MESS.” A machine
can be an optimal reply to itself in our framework only if it exhibits somenasty behavior in equilibrium. The simplest such machine is DEFECT, but
DEFECT is not a MESS because an invasion by TIT-FOR-TAT
will
expand from its initial bridgehead.
The simplest machine that is a MESS is TAT-FOR-TIT(Fig. 2). But
the fact that no invading mutant can expand at the expense of TAT-FORTIT does not imply that TAT-FOR-TIT
cannot be invaded. In the notation of Appendix A, TAT-FOR-TIT
can be invaded by “cc”, “cd”, “AA”,“AC”, or “CA”. (Small letters indicate machines that begin by cooperating;large letters indicate machines that begin by defecting.) A tiny invadinggroup of one of these machines will not expand, but neither will it bedriven to extinction.
The inability of a MESS to repel all invaders implies that the purity ofa MESS in which the whole populations consists of copies of a single
machine will eventually be sullied. This makes it necessary to study
polymorphous
populations.
The next section offers a definition of apolymorphous
MESS, and proves an appropriate
generalization
ofTheorem 7.1. This section continues with a simple example that is intended
to indicate some of the complexities that this analysis evades.
In a populationconsisting of positive fractions of TAT-FOR-TIT,
TWEEDLEDUM(cc), and TWEEDLEDEE(cd) all machines will always
earn the utilitarian profit. The population cannnot be invaded by any one
or two state machine except TWEETYPIE(CA). Nor can any machine ofcomplexity greater than two invade. However, after an attempted invasion
has been repelled, the proportions of the three types of machine may bealtered. For example, an attempted invasion by “AC” will increase therelative numbers of TWEEDLEDUM
and an attempted invasion by “AA”
will reduce the relative numbers of TWEEDLEDEE.
In the long run, theproportions of the different types in the population will therefore be subject
to drift in the face of mutations.
*‘This argument
also shows that, with the definitionof a polymorphous
MESS given in thenext section, no populationconsisting
entirely of “nice” machines can be a MESS.

EVOLUTIONARYSTABILITY

295

Not only this, none of the three machines are equipped to repel
TWEETYPIE.
TWEETYPIE
can therefore invade the population. Afterthe invasion, all machines will still always earn the utilitarian
profit.
However, once TWEETYPIE
gets established, its toothlessness allows
suitable machines (of complexity greater than two) to gain a temporary
foothold. Such machines will get more than the utilitarian payoff whenplaying TWEETYPIE
who will consequently get less than the utilitarian
payoff. Eventually, the invading machines will lose their edge when their
exploitation of TWEETYPIE
results in its being eliminated. They will then,in turn, be eliminated themselves because their greater complexity nolonger generates any extra advantage. This restores a populationof
TAT-FOR-TIT,
TWEEDLEDUM,
and TWEEDLEDEE
in which allmachines earn the utilitarian payoff.
A populationconsisting of suitable fractions of TAT-FOR-TIT,
TWEEDLEDUM,TWEEDLEDEE,
andtransient
numbersof
TWEETYPIE
can therefore co-exist in a relationship whose stability issomewhat precarious. The proportions in which they are present will drift
depending on the shocks the system receives as different mutants appear.
Although the symbiotic relationship may persist for long periods of time,
it will be stressed to the point of collapse if a sufficiently adverse sequenceof mutations is encountered.
Perhaps more satisfactory stability situations exist at higher complexity
levels. At the two state level, little more can be said without information
about how mutations arise.

9. POLYMORPHOUS

MESSESIt remains to confirm that the conclusion of Theorem 7.1 is valid in thepresence of polymorphy. To this end, let F denote a population in which
the automaton u” occurs with frequency fn > 0 (n = 1, 2...N). DefineP(a, F)=i f,P(a, a”).
n=l

A population F will be said to be a polymorphous MESS if, for all possible
mutants b and all u” in F,(1)

P(u”, F) > P(b, F), or

(2)
(3)

P(un, F) = P(b, F) and P(un, b) > P(b, b), orP(u”, F) = P(b, F) and P(a”, b) = P(b, b) and \a”( d Jbl.

The conditions for a polymorphous MESS ensure that each machine in
the population does at least as well as any potential invader, provided the296

BINMORE AND SAMUELSON

latter appears in sufliciently small numbers. Some examples for the casewhen the underlying game G is the Prisoners’ Dilemma of Fig. 1 may help
to clarify the definition. We have seen that a population consisting entirely
of TIT-FOR-TAT
is not a MESS. However, a population consisting
entirely of TAT-FOR-TIT
is a MESS. So is any population consisting ofspecimens of TAT-FOR-TIT,
TWEEDLEDUM,
and TWEEDLEDEE.
But the addition of small numbers of TWEETYPIE
generates a populationthat is not a MESS.
Since any member of the population can itself appear as a mutant 6, apolymorphous MESS must have the property that P(u”‘, F) = P(a”, F) for
all am and an in F. It follows from part (2) of the definition of apolymorphous MESS that, for all am and an in F,
P(um, a”) 2 P(a”, a”).

(2)z = min P(a”, a”) E P(ak, ak).

(3)

We definen

It follows from parts (2) and (3) of the definition
that, for all 8’ and an in F,

of a polymorphousP( am,a”) 2 z.

MESS
(4)

A population F will be said to be utilitarian if, for all am and un in F,
P(um, a”) B P(a*, a*) = u, where a* is a utilitarian automaton.21
THEOREM 9.1. If the underlying game G is symmetric, then a population
F can be a polymorphous MESS for G# only if F is utilitarian.

Proof: Let F be a populationthat is a polymorphoustheorem will follow from (4) if it can be shown that z > u.
The first step is to prove that, for any am in F,
P(am, ak) >, u

or

MESS.

(P(ak, a*), P(am, a”)) = (z, z),

The

(5)

where ak satisfies (3).
Suppose that (5) fails. Then there exists ui in F for whichP(aj, ak) < uand(P(ak, a’), P(a’, a”)) # (z, z).

(6)*I If the automaton
selection game is Gx#, then it is also true that P(a”, a”) < P(a*, a*) for
all a”’ and u” in E This also holds when G is symmetricand the automaton
selection gameis G* provided
that, as in the Prisoners’
Dilemmaof Figure 1, the utilitarian
profit in G*
coincideswith that of G**.
If this proviso
does not hold, the definitionof a utilitarian
population
is not very interestingfor Gr.

EVOLUTIONARY

291

STABILITY

It will be shown that (6) allows the construction
better than aj. The mutant plays as follows:of a mutantb that does

Initially, b mimics ak, and continues to do so unless a cycle isestablished that generates a profit pair of (z, z). (Because each automaton
in F is finite, b can be programmed to detect the occurrence of one of thefinitely many cycles generated by the automata in F which yields the profit
pair (z, 2)).
If such a cycle is established, b sends an identifying signal. If thisis reciprocated, b “knows” it is playing itself and thereafter mimics a*.
If the signal is not reciprocated, b experiments until it learns theidentity of the automaton a’ in F that it is playing.
This will leave a” in some state q. For familiar reasons, a” mustuse q in playing against at least one automaton am in F. Thus b may now
mimic a”’ thereafter, and hence, by (4), secure a profit of at least z.
l

l

l

l

To see that the mutant b so constructed does better than a’, first observe
that, for all a” in F,22P( b, a”) 2 P( ak, a”).

(7)

It follows that P(b, F) > P(ak, F) = P(aj, F). The first of the conditions fora polymorphous
MESS is therefore not satisfied. The second and third
conditions are not satisfied either because P(b, 6) = P(a*, a*) = U, andP(aj, 6) = P(a’, ak) < U, by (6). Thus, P(aj, b) < P(b, b). It follows that (5)must hold if F is a MESS. It remains to complete the proof by showingthat z 2 u follows from (5) and the fact that F is a MESS. A mutant b isconstructed exactly as in the first part of the proof, but we now examine
how this mutant performs in comparison to ak rather than aj. As before,
the mutant satisfies (7) for all an in F.
When playing ak, the mutant b eventually behaves like some machine amin F. Suppose that P(b, ak)= P(am, uk) 3~. If u> z= P(uk, uk), then (7)holds with strict inequality when n = k. It follows that P(b, F) > P(uk, F).
This contradicts the assumption that F is a MESS. Thus, either z > u as weare trying to prove, or else P(um, a”) < u.
We therefore consider the case when P(um, ak) < U. Then (5) implies that
P(ak, b) = P(ak, am) = z. Since P(b, F) 2 P(ak, I;), the second and third
conditions for a polymorphous MESS yield that P(ak, b) 2 P(b, b) = u. On
combining these results, we therefore obtain again that z >, U. [22T~ establish(7),

noticeif urn is the automatonthat b mimics against a” in the lastP(b, a’) = P(a”, a”) 2 P(ak, a”), since otherwiseP(&, 0”) >precluding
the ability of b and a” to yield a cycle of profits (z, Z)

thatpart of the description of b, thenP(a”, a”) 3 z (from (2)-(3)),
and yielding a contradiction.

298

BINMOREANDSAMUELSON

THEOREM 9.2. A population F can he a polymorphous MESS for G# #only if F is utilitarian.

Proof We note only that, in adapting the proof of Theorem 9.1, one
need not construct a mutant that signals its identity under certain contingencies both when in the role of player 1 and in the role of player 2. It
is enough to do better than a machine in the current population in one of
the two roles. 1

10. CONCLUSION
We have examined circumstances under which the only evolutionarily
viable outcome in an infinitely repeated game is utilitarian. The argument
depends on the players being boundedly rational, but no uniform bound is
imposed on the complexity of their thinking processes.
Our notion of evolutionary
viability,
captured by the modified
euolutionarily stable strategy (MESS) permits players operating different
strategies to co-exist in a symbiotic relationship that sustains the utilitarianoutcome against any single potential disrupting mutant invasion. However,questions remain about the viability of such populations in the presence ofrepeated invasion attempts. We feel that the examination of more stringent
stability requirements than those studied in this paper is an important areafor further research. In particular, it is not clear that one should follow thebiologists in supposing that the interval between successive invasion
attempts is sufliciently large that a nonviable mutant will be entirely
eliminated before the appearance of a new mutant. Overlapping invasions
would seem more suited to a social context.

APPENDIXA

This appendix contains a listing of all 26 one and two state Moore
machines capable of playing the infinitely repeated Prisoners’ Dilemma.
The entry in row r and column c in the Figs. 3 and 4 give the profit (thelimit-of-the-means
payoff) that machine r gets when it plays machine c.
Machines that cooperate in their initial state are labeled with lower caseletters. Machines that defect in their initial state are labeled with upper caseletters.
APPENDIX

B

This appendix discusses some formal issues in the theory of finite
automata that are neglected in the text. For more details, see Hopcraft andEVOLUTIONARY299

STABILITY&-‘:cyf$jD--&gc +&&
‘ba’

‘bb’

‘bc’

+&y:&~D-&gc-&~
‘ca’

‘cb’
TIT-FOR-TAT

I

‘CC’

TWEEDLEDUM‘cd’

TWEEDLEDEE
C.D
-

c
t?
‘dd‘

COOPERATE&jc’“&-y($JD-&gc+ff&.&
‘BA’

‘BB’

‘CA’

‘CB’

‘BC’

+&(fJ&~D+&~c*&&‘CC’
TAT-FOR-TIT

TWEETYPIE

C.D
-

D
d
‘DD’
DEFECT

FIG.

3.

All

one and two state machines

g
0

FIG.

4.

Payoff

DD

DD

AA

AB

AC

for all one and two state machines

cc

CB

CB

CD

CA

CA

CD

BD

BD

cc

BB
BC

BC

BA

BA

BB

AC
AD

AD

AB

AC

AA

AB

dd

dd

AA

cc
cd

cc

cd

CL
cb

ca

cb

bc
bd

bc

bd

ba

ad

ad

bb

ac

ac

bb

ab

ab

ba

aa

aa

AD

BA

BB

BC

BD

CA

CB

CC

CD

DD

EVOLUTIONARYSTABILITY

301

Ullman [14]. We work with a particular type of finite automaton called a
Moore machine. A Moore machine capable of serving as player i in therepeated game G” has the set Si of player i’s actions in the underlying
game G as its output (or response) set. The set SPi of actions jointly
available to the other players in G is its input (or stimulus) set.
Formally, a Moore machine with these input and output sets is aquadruple (Q, qO, t, u). The set Q is finite. An element q E Q is interpreted
as a state of the machine. The output function t: Q -+ Sj describes the actiont(q) used by the automaton when it is in state q. The first time that themachine plays G, it is in its initial state qO. The transition function
u: Q x Sei + Q describes how other states are reached. If the machine is instate q, it will play t(q) in the current repetition of G. The other players will
use some joint action s _ ;. This shifts the automaton to state u(q, s-,),where it will remain until after the next repetition of G.
For simplicity, the following results are confined to the case when G issymmetric.
LEMMA B.l.
If an automaton a is a MESS for G#, then every state oj
a is used when a plays G# against itself.

Proof. Suppose that a = ((2, qO,t, u) has a state q* that is not reachedwhen it plays itself. A machine b = (Q’, qb, t’, u’) is then constructed asfollows. Take Q’=Q\{q*)and qb=qO (#q*). Define u’:Q’xS-~-Q’SO
that u’(q, smi)=u(q, s-;), unless u(q, s_,)=q*. In the latter case, takeu’(q, spi) = q. The game G” will then be played the same whether theplayers are two a machines, two b machines, or an a machine and a b
machine. Thus, P(a, a) = P(b, a) = P(a, b) = P(b, b). All the conditions for ato be a MESS then fail because lb1< la(. mLEMMA B.2. If an automaton a is a MESS for G# and u is the utilitarian
payoff, then there exists a machine b such that P(b, b) = u andP(b, a) = P(a, a).

Proof: Suppose that a = (Q, qO, t, u ). Let t(q,,) = x. The lemma isimmediate unless G admits a second action y. Let u(q,, y) = q*, Take
Q=Qu{r,s}, and define b=(e , r, 1, 6) so that I(r) = y and i(s) =z,
where z is the utilitarian action in G. Define 2(q) = t(q), for all q E Q. Defineii(r, y) = s and E(r, w) = q* for all w # y. Define z?(s,w) = z for all w. Defineii(q, w) = u(q, w) for all w and all q E Q.
Then P(b, b) = u because, after observing the opponent play y, theautomaton b switches from state r to state s, where it remains thereafterusing action z. Why is P(b, a) = P(a, a)? After b plays y and a plays x intheir respective initial states, both automata then switch to state q* and302

BINMOREANDSAMUELSON

play like a thereafter. Since all of a’s states are used when a plays itself (byLemma B.l), it follows that P(b, a) = P(a, a). 1
The formalities for the corresponding results for polymorphous MESSes
and for asymmetric underlying games G are similar but have longer proofs.

APPENDIXC

The main body of the paper looks only at limit-of-the-means
profits in
the repeated game G”‘. This appendix indicates some extensions to the discounting case. Only pure populations and a symmetric underlying game G
will be considered.
If an automaton a plays G” with a second automaton b, denote thestage-game payoff to the former at time t by ~‘(a, b). Denote the “continuation payoff’ at the Tth stage of G” by
P&b)=(l-6)

fsz-~rcr(u,b),r=T

where 6 is a discount factor satisfying 0 < 6 < 1. The function
P,(u, b) = Pi(u, b) then replaces the profit function of the text. Complexity
considerations remain unchanged.
More liberties will be taken with the definition of evolutionary stability.
If 0 < 6 < 1 and E> 0, a population will be said to be (6, &)-viable if amutant bridgehead consisting of a fraction E of the population cannot
expand when the discount factor is 6. An automaton a will be said to be
a GUESS if, whenever E= U( 1 - 6) as 6 + 1, a population consisting
entirely of specimens of a is (6, &)-viable for all 6 sufficiently close to 1.
The following theorem is a limiting result. Away from the limit, one can
not guarantee that machines are utilitarian. One can only ask that they beapproximately utilitarian.
THEOREMCl.

Zfu is a GUESS,

then

P,(u, a) + u us s --) 1,
where u is the utilitarian payoff:
Proof If a is a GUESS, then it has no unused states for familiar
reasons. Let t = T be the first stage at which Pi(u, a) achieves its minimum.
Assume for the moment that T>O. Construct a mutant b with thefollowing properties:
l

Until

time T- 1, the mutant b mimics a.

EVOLUTIONARY303

STABILITY

At time T- 1, the mutant b outputs something different from a.
If the signal is reciprocated, b continues by mimicking
theutilitarian machine from period T onwards.
If the signal is not reciprocated, b returns to mimicking a fromT onward, but starting from the state to which a was switched by b’s
deviation at time T - 1.
lll

The expected continuation profit from time T- 1 to the a automaton
after an invasion by a fraction E of b mutants is(1 -S){(l-&)nr-‘(a,a)+~n~~‘(a,b)}+6((1-~)PgT(u,u)+&P,T(u,b)}.
The expected continuation
the invasion is(8)

profit from time T- 1 to the b automaton

after(l-6){(1-~)+‘(b,u)+~n~-‘(b,b)}+6{(1 -E) P,‘(b, u)+cP;(b,

b)}.

(9)

Both a and b get the same profit flow up to time T - 1, and so a will get
displaced if (9) exceeds (8). If m and M are the minimum and maximum
values in the payoff matrix for G, we obtain the following sufficient condition for (9) to exceed (8) and hence for a to be displaced by b:(1 -E) P,‘(u, a) + &‘;(a,b) - (1 -E) P;(b, a)< EP,T(b, b) -A simpler sufficient condition
thatis obtained by noting that P,‘(b, b) = U, andP,‘( u, b) = P,‘( b, a) >, P,T(u, a).

The latter observation follows from the fact that b mimics u from time T
onward, and hence Pf(a, 6) = P,T(b, a) 2 Pi(a, a) 2 P,‘(u, a), for some t. On
substituting, we obtain our final sufficient condition that b be able todisplace a. The sufficient condition isEP;(U, U) < EU -Suppose that it is false that P,(u, a) + u as 6 + 1. Then there exists an
YI> 0 and a sequence ~5~+ 1 such that P,,(a, a) < u - r]. It follows that,P~(d”(u,u)~P,,(u,u)$u-?<u-

(

2

I I >

(M-m),(11)

304

BINMOREAND

SAMUELSON

provided thatl-6.
*
( I 1 >(M-m)<v.
To obtain a contradiction,

it remains to select2 (1-S;)

E-Z--.
’ rlhiThen si = 0( 1 - S,), but (11) and hence (10) hold. Therefore b can displace
a for each value of i. Thus a is not a GUESS.
This proves the theorem provided that it is never true that T=O. If
T= 0, b is constructed to screen at time 0. Then Pj(b, a) = Pi(u, b) 3
Z-$(Q, a), and (10) must be replaced by(1-E)P;(a,a)-(1-2&)P~(a,a)<EUSince Pj(a, a)= Pf(u, a)+ O(1 -6),
extra algebra.

(
the result

7

still

>

(M-m).

follows

after

a little

REFERENCES
1. D. ABREU AND A. RUBINSTEIN, The structureof Nash equilibrium
in repeated games withfinite automata,Econometrica
56 (1988), 1259-1282.
2. L. ANDERLINI, ‘Communication,
Computability
and Common
Interest Games,”
Working
paper, St. John’s College, Cambridge,
1990.
3. R. AUMANN,
Survey of repeated games, in “Essays in Game Theory and MathematicalWissenschaftsverlag,
Bibliographisches
Economics
in Honorof OskarMorgenstern,”
Institut,
Mannheim/Wein/Zurich,
1981.
4. R. AUMANN AND S. SORIN, Cooperation
and bounded recall, Games Econ. Behav. 1 (1989)
5-39.
5. R. AXELROD, “The Evolutionof Cooperation,”
Basic Books, New York, 1984.
6. R. AXELROD
AND W. HAMILTON,The evolutionof cooperation,
Science 211 (1981)
1390-1396.
7. J. BANKS AND R. SUNDARAM,
Repeated games, finite automata
and complexity,
Games
Econ. Behav. 2 (1990), 97-117.
8. K. G. BINMORE, Social contract
III: Evolution
and utilitarianism,
Consfiturional
Polir.
Econ. 1 (1990), l-26.
9. R. BOYD AND J. LOBERBAUM,
No pure strategy
is evolutionarily
stable in the repeatedPrisoners’ Dilemma
game, Nature 327 (1987). 58-59.
10. R. DAWKINS, “The Selfish Gene,” Oxford
Univ. Press, Oxford,
1976.
11. J. FARRELL AND R. WARE, Evolutionary
stability
in the repeatedPrisoner’s
Dilemmagame, Theorer. Popularion
Biol. 36 (1988), 161-166.
Game Explanationsof Commitment
and Cooperation,”in
12. D. FUDENBERG, “Repeated‘*Advancesin Economic
Theory:Sixth World
Congressof the EconometricSociety”(J.-J. Laffont.
Ed.), Cambridge
Univ. Press, Cambridge,
1991.

EVOLUTIONARYSTABILITY

305

13. D. FUDENBERG ANU E. MASKIN,
Evolutionand cooperationin noisy repeatedgames,
Amer. Econ. Rev. 80 (1990), 214-219.
14. J. HOPCRAFT
AND J. ULLMAN,“Introduction
to Automata
Theory,Languages
andComputation,”
Addison-Wesley,
Reading,
MA, 1979.
15. E. KALAI AND A. NEME, “The Strengthof a Little
Perfection,”
Discussion
paper 858,
Northwestern
University,
1989.
16. Y. KIM. “Evolutionary
Stable Strategies
in the RepeatedPrisoner’s
Dilemma,”
Working
paper, Universityof Iowa, 1989.
17. D. KREPS, P. MILGROM,
J. ROBERTS, AND R. WILSON, Rational cooperationin the finitely
repeated prisoners’ dilemma,
J. Econ. Theory 27 (1982), 245-252.
18. D. LEWIS. “Counterfactuals,”
Basil Blackwell,
Oxford,1976.
19. B. LINSTER, “Essays
on Cooperation
and Competition,”
Ph.D. Thesis. UniversityofMichigan,
1990.
20. J. MAYNARD
SMITH, “Evolution
and the Theoryof Games,”
Cambridge
Univ. Press,
Cambridge,
1982.
21. J. NACHBAR, “The Evolutionof Cooperation
Revisited.”
Working
paper, Washington
University,
St. Louis, 1989.
22. A. NEYMAN, Bounded
complexity
justifies cooperationin the finitely repeated prisoners’
dilemma,
Econ. Left. 19 (1986), 227-229.
23. A. ROBSON, Efficiency
in evolutionary
games: Darwin,
Nash, and the secret handshake,
J. Theoret. Biol. 144 (1990), 379-396.
24. A. RUBINSTEIN, Finite automata
play the repeated prisoners’ dilemma. J. Econ. Theory 39(1986). 83-96.
25. R. SELTEN, Reexaminationof the perfectness concept for equilibrium
points in extensivegames, Int. J. Game Theory 4 (1975), 25-55.