ARTICLE IN PRESS

Journal of Theoretical Biology 239 (2006) 435–444
www.elsevier.com/locate/yjtbi

The leading eight: Social norms that can maintain cooperation byindirect reciprocity
Hisashi Ohtsuki, Yoh Iwasa
Department of Biology, Faculty of Sciences, Kyushu University, Fukuoka 812-8581, Japan
Received 31 May 2005; received in revised form 7 August 2005; accepted 9 August 2005
Available online 19 September 2005

Abstract
The theory of indirect reciprocation explains the evolution of cooperation among unrelated individuals, engaging in one-shot
interaction. Using reputation, a player acquires information on who are worth cooperating and who are not. In a previous paper, weformalized the reputation dynamics, a rule to assign a binary reputation (good or bad) to each player when his action, his current
reputation, and the opponent’s reputation are given. We then examined all the possible reputation dynamics, and found that there
exist only eight reputation dynamics named ‘‘leading eight’’ that can maintain the ESS with a high level of cooperation, even if
errors are included in executing intended cooperation and in reporting the observation to the public. In this paper, we study thenature of these successful social norms. First, we characterize the role of each pivot of the reputation dynamics common to all of theleading eight. We conclude that keys to the success in indirect reciprocity are to be nice (maintenance of cooperation among
themselves), retaliatory (detection of defectors, punishment, and justiﬁcation of punishment), apologetic, and forgiving. Second, we
prove the two basic properties of the leading eight, which give a quantitative evaluation of the ESS condition and the level ofcooperation maintained at the ESS.
r 2005 Elsevier Ltd. All rights reserved.
Keywords: Cooperation; Reputation; Standing; Justiﬁed defection; Leading eight; Social norm

1. Introduction
The evolution of cooperation between unrelated
individuals has been a research focus of evolutionary
biology. In a classical paper, Trivers (1971) proposed
reciprocal altruism (or direct reciprocity) that promotes
cooperation between a dyad of players interacting
repeatedly. This idea was later formalized mathematically as the repeated prisoner’s dilemma game by
Axelrod and Hamilton (1981) in which a cooperative,
retaliatory and forgiving strategy, Tit For Tat, won in
the round robin tournament. In contrast, the theory ofCorresponding author. Tel.: +81 92 642 2641;
fax: +81 92 642 2645.
E-mail address: ohtsuki@bio-math10.biology.kyushu-u.ac.jp(H. Ohtsuki).

0022-5193/$ - see front matter r 2005 Elsevier Ltd. All rights reserved.
doi:10.1016/j.jtbi.2005.08.008

indirect reciprocation explains cooperation even in a
one-shot interaction. Using reputation, a player acquires
information on who are worth cooperating and who are
not, even if he has no experiences of direct interaction
with them. If cheaters were effectively excluded by thismechanism, cooperation could be maintained in the
population.
Nowak and Sigmund (1998a, b) examined this scenario mathematically for the ﬁrst time by introducing theconcept of image score. In Nowak and Sigmund (1998a),
image score is a binary representation of a player’s social
reputation and is either good or bad. When a player gives
help to others, his image score becomes good. On theother hand, refusal of giving yields bad image score to
the actor. Under this updating rule, Nowak andSigmund found that the discriminator strategy, who
gives help only to good individuals, performed well.

ARTICLE IN PRESS
436

H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 239 (2006) 435–444

However, many subsequent studies have cast doubt
on the image-score strategy, especially about the
incentive to maintain the discriminator strategy. Discriminators refuse help against a bad recipient. Paradoxically this refusal brings about bad reputation to theactor. In other words, refusal of help against a bad
opponent is not justiﬁed in the population dominated bydiscriminators themselves. Therefore it is beneﬁcial forthe actor to cooperate even with bad opponents in orderto keep his good reputation. The population composedof discriminators is invaded and replaced by AllC, whichis then followed by the invasion by AllD players. Indeed,
Ohtsuki (2004) and Panchanathan and Boyd (2003)
have shown the failure of discriminators who use theimage-score criterion.
This suggests to us the need of a more sophisticatedmechanism than assumed in the image score to judge
whether a player is good or bad. Sugden (1986) had
proposed a different rule of assessment, called standing
criterion, in which refusal against a bad recipient does
not undermine the donor’s reputation. Leimar andHammerstein (2001), Panchanathan and Boyd (2003),
and Ohtsuki and Iwasa (2004) have shown that thestanding strategy, based on the standing criterion,
overcomes the issue of unjustiﬁed defection and maintains cooperation.
Ohtsuki and Iwasa (2004) examined all the possible
ways to assign reputation to a player, once his action,
his current reputation, and the opponent’s reputation
are given. They asked whether cooperative strategies canevolve based on indirect reciprocation even when there
is some error included in executing the intended
cooperation and in reporting the action of others to
the public. Brandt and Sigmund (2004) developed asimilar model independently with a small difference in
how errors occur, and studied the evolution ofcooperation by an individual based model. As a resultof exhaustive search, Ohtsuki and Iwasa (2004) foundthat there are eight reputation dynamics which canmaintain a non-trivial ESS with a high level ofcooperation. They also showed that these ‘‘leadingeight’’ are the only reputation dynamics allowing nontrivial ESS when the beneﬁt exceeds the cost only
slightly, and that the level of cooperation maintained at
the ESS are close to the theoretical maximum (see below
for more accurate statement).
In the present paper, we characterize the nature of
successful social norms, the leading eight. After explaining the formalism of indirect reciprocity game adopted
by Ohtsuki and Iwasa (2004) and Brandt and Sigmund(2004), we discuss the role of the elements that arecommon to all social norms of the leading eight toillustrate the mechanisms by which the leading eightachieves the high performance. Then we give a formal
proof for two deﬁning properties of the social norms of
the leading eight.

2. Indirect reciprocity game and the leading eight
2.1. Indirect reciprocity game
Here we explain the formalism of indirect reciprocity
game studied by Ohtsuki and Iwasa (2004). We consider
a large population of individuals who engage in a gameamong them. In each generation they play the game formultiple rounds, each with a different player. In eachround, players are paired randomly, and play one-shotprisoner’s dilemma game. A player who cooperates pays
ﬁtness cost c, but the one who defects (i.e. refusescooperation) pays no cost. A player receives beneﬁt b, if
the opponent cooperates. The beneﬁt is larger than thecost (b4c). In choosing whether to cooperate or todefect, players can use reputation.
Fig. 1 illustrates events in the model. First, the focal
player (player 1) meets player 2 who has been chosenrandomly from the population. They both happen tohave a good reputation, as indicated by G in the ﬁgure.
Each player has his own ‘‘behavioral strategy’’, anddecides whether to cooperate or to defect based on the
reputation of the self and the opponent. In Fig. 1, player
1 defects and player 2 cooperates. Based on theseactions, each player receives payoff. Here players 1 and
2 receive +b and c, respectively. Then they will change
the partner and will never meet again. In Fig. 1, in thenext round, player 1 engages in the game with player 3,
who has a good reputation, indicated by G. Player 1 hada good reputation in the ﬁrst round, but he now has abad reputation in the second round, because he played
defection against a good player in the previous round.
The rule describing how reputation of a player changes
over time is called ‘‘reputation dynamics’’. It assigns‘‘good’’ (abbreviated as G) or ‘‘bad’’ (B) as his new
reputation to the focal player in the next round,according to the action, the previous reputation of theactor, and the reputation of the opponent. Since no two

Fig. 1. Scheme of the indirect reciprocity game. See the text for details.

ARTICLE IN PRESS
H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 239 (2006) 435–444

players meet again, a player’s past action affects his
beneﬁt in the future only through modiﬁcation of his
own reputation. Ohtsuki and Iwasa (2004) asked
whether there is any reputation dynamics that encourages the evolution of the cooperative behavioral
strategy, rather than AllD, and, if there are some, what
those successful reputation dynamics are.
Each player has a binary reputation, either good orbad, which is known publicly. Whether a player
cooperates or defects may in general depend on the
reputation of the opponent and that of himself. To
express this, we consider behavioral strategy, denoted byp. p(i, j) indicates action (either C or D, indicating
cooperation and defection, respectively) when his
reputation is i and the opponent’s reputation is j (i, j
are G or B, indicating good and bad, respectively).
There are four different situations concerning the
reputation of the self and opponent: both are good
(GG), the actor is good whereas the opponent is bad(GB), the actor is bad whereas the opponent is good(BG), and both are bad (BB). For each case, abehavioral strategy prescribes whether to cooperate(C) or not (D). Hence there are 24 ¼ 16 possible
behavioral strategies in total. Two simplest examples
are AllD which defects (D) for all four cases, and AllC
which always cooperates (C). But the other 14 behavioral strategies take different actions depending on the
reputation of the self and the opponent.
In addition, the population has a ‘‘social norm’’,
which assigns reputation (G or B) to each player. We
call this a ‘‘reputation dynamics’’, and denote it by d
(Ohtsuki and Iwasa, 2004). d(i, j, X) is either good (G) or
bad (B), and indicates the reputation of a player who
takes an action X (either C or D), when his own
reputation is i and the opponent’s reputation is j (i,j ¼ G, B). There are four possible situations (ij ¼ GG,
GB, BG, and BB) and for each situation there are two
possible actions (X ¼ C and D). A reputation dynamic
speciﬁes whether the given action in the given situationis good or bad for each of 4  2 ¼ 8 cases. Hence there
are 28 ¼ 256 different reputation dynamics in total. For
example, the image-score criterion (Nowak and Sigmund, 1998a) is to regard players who cooperate as
good and those who defect as bad, hence d (*,*, C) ¼ G
and d(*,*, D) ¼ B, in which asterisk (*) is a wild card
(i.e. these equations hold if * replaced by G or B).
Another famous reputation dynamics is standing(Sugden, 1986), which differs from the image score only
in one element: d(GB, D) ¼ G (Ohtsuki and Iwasa,
2004).
Here we also consider a factor not included in
Ohtsuki and Iwasa (2004). We assume that the numberof rounds experienced by a player in a generation
follows a geometric distribution. The expected probability that another round of game is played is given byo (0ooo1). The beneﬁt to be obtained in the following

437

round should be discounted by factor o. When o islarge and close to one, as assumed in Ohtsuki and Iwasa(2004), each player engages in the game over a numberof rounds per generation, but in each round with adifferent opponent randomly chosen from the population. If o is small, the reciprocation in the futureinteraction is less likely, and having a good reputation
gives a smaller indirect beneﬁt than the case with alarge o.
2.2. The leading eight
Ohtsuki and Iwasa (2004) studied the reputation
dynamics that has the following properties: ﬁrst, in the
population dominated by (d, p) players, the behavioral
strategy p has a higher ﬁtness than a rare mutant of anyof the 15 behavioral strategies p0 , including AllD. In
such a case, (d, p) is called an ESS pair. Second, in the
population composed of (d, p) players only, the level of
average ﬁtness gain obtained per interaction is high.
They studied the model when errors at low frequency
occur both in executing the cooperation and in reporting
the observed behavior to the public.
As a result of exhaustive examination of all 4096
possible pairs (d, p), only eight pairs are found to show
very high performance in both properties (Ohtsuki andIwasa, 2004). The population dominated by the type (d,p) refuses the invasion of 15 other behavioral strategies
including AllD and AllC. The level of cooperation at the
ESS is very high, and the average payoff per game isclose to the maximum, bc. These properties are shared
only for these eight pairs, and we named them ‘‘leadingeight’’ (Ohtsuki and Iwasa, 2004). Later we will statethese two properties more precisely and prove them.
The leading eight pairs of reputation dynamics andbehavioral strategy (d, p) have some elements incommon but differ in others (Fig. 2). For example, all
the eight reputation dynamics havedðn ; G; CÞ ¼ G and dðn ; G; DÞ ¼ B(1)

where the asterisk (*) indicates a wild card. Eq. (1)implies that a player who cooperates with anotherplayer with a good reputation is assigned good in thenext round, irrespective of the current reputation.
Similarly, the second of Eq. (1) implies that a player
who defects against a good opponent becomes to have a
bad reputation in the subsequent round. In addition
there is one more element common to all the leadingeight, as follows:d ðG; B; DÞ ¼ G(2)This implies that a good player who refuses cooperation
to a bad opponent can remain good in the next round.
Since each asterisk in Eq. (1) corresponds to two
possibilities, Eqs. (1) and (2) combined specify 5 out of
8 elements of the reputation dynamics. However, theARTICLE IN PRESS
H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 239 (2006) 435–444

438

d:

GG

GB

BG

BB

3. Characterization of the leading eight

C

G

*

G

*

3.1. Intuition behind the leading eight

D

B

G

B

*

p:

C

D

C

**

Fig. 2. The leading eight (Ohtsuki and Iwasa, 2004). Top table: thereputation dynamics d, which speciﬁes the reputation in the next
round. Four columns correspond to the different pairs of reputationsof the actor and the opponent. G and B indicate good and bad,respectively, and GG, GB, BG and BB are four combinations of
reputations of the actor (the ﬁrst symbol) and the recipient (the second
symbol). Left of the table indicates the action of the actor (C and D
implies cooperation and defection, respectively). Symbols in the table
are the reputation common to all social norms in the leading eight.
Asterisk (*) is a wild card, implying that both G and B are included in
the element. Bottom table: the behavioral strategy p, which speciﬁes
the action of the player. Three elements ﬁlled as C and D indicates thatthose are common to all social norms in the leading eight. The one withdouble asterisks (**) is either C or D, which is determined according to
the social norm that is adopted. It is C if and only if d(BB, C) ¼ G andd(BB, D) ¼ B; and it is D otherwise. See the main text for details.

following three elements are not speciﬁed: d(G, B, C),d(B, B, C), and d(B, B, D). Since each of these three canbe either G or B, there are 23 ¼ 8 combinations, and allof these can achieve the ESS with a very high level ofcooperation if a suitable behavioral strategy is chosen.
Concerning the behavioral strategy, the following
three elements out of four are common to all the leadingeight (see Fig. 2):
pðG; GÞ ¼ C; pðG; BÞ ¼ D; and pðB; GÞ ¼ C:

(3)

But the fourth element p(B, B) can either be G or B.
However, this cannot be freely chosen. Once we specify
the reputation dynamics, then p(B, B) is speciﬁed to be
G or B for (d, p) to be the ESS pair (see below).
These leading eight are discovered by an exhaustive
search in Ohtsuki and Iwasa (2004). Subsequently,
we showed that the condition for these eight pairs of dand p to constitute a non-trivial ESS pair undersmall errors and the level of cooperation at the ESS,
indicating that they are desirable social norms. However, they are not the ones deduced from the argumentof what the desirable social norms should be. We havenot examined the meaning of each element of theleading eight reputation dynamics. In the next section,
we attempt to explore the mechanisms by which theseleading eight can succeed in maintaining the high level ofcooperation.

Here we ﬁrst explain the characteristics common to allof these leading eight social norms and discuss the roleof each element in shaping a cooperative society. Laterwe give a formal proof of two deﬁning properties of theleading eight reputation dynamics.
(1) Maintenance of cooperation: First, in the population dominated by a successful pair (d, p), most players
should maintain a high reputation (i.e. they are good),
and most players cooperate with each other, except for asmall fraction caused by unavoidable errors at a low
frequency. We request the following two relations:pðGGÞ ¼ C and d ðGG; CÞ ¼ G:

(4)The ﬁrst formula implies that a player with a good
reputation should cooperate if the opponent is good.
The second equation indicates that the outcome of suchan encounter keeps the actor in a good reputation.
(2) Identification of defectors: The second requirement
is the efﬁciency of spotting rare defectors using
reputation. Suppose that one AllD invades the population dominated by (d, p), in which most players have agood reputation. The AllD player should be immediately labeled as ‘‘bad’’, and in the next round he should
be refused cooperation by another (d, p) player. We
hence request the following two:d ðGG; DÞ ¼ B and d ðBG; DÞ ¼ B:

(5)These two equations indicate that a player who defects
against a good opponent should be regarded as bad in
the next round, irrespective of the current reputation.
Using an asterisk (*) for a wild card, these can be
combined as d(*G,D) ¼ B.
(3) Punishment and justification of punishment: When adefector is detected and identiﬁed, then other good
players should refuse cooperation to him in the next
round. Hence a good player who meets with an
opponent labeled as ‘‘bad’’ should refuse cooperation.
pðGBÞ ¼ D:

(6)In addition, a good player who refuses cooperation to abad opponent should be able to maintain good
reputation in the next round. Hence we haved ðGB; DÞ ¼ G;

(7)which implies the justiﬁcation of punishment.
(4) Apology and forgiveness: There are errors at a low
frequency, either in the execution process or in the way a
player’s revised reputation is reported. As a result, aplayer may be given a bad reputation and be refusedcooperation once. However after this, the player musthave a way to go back to the normal state with a good
reputation and to start to cooperate again with othermembers. If the social norm does not allow such an

ARTICLE IN PRESS
H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 239 (2006) 435–444

immediate forgiveness, one error may result in many
events of punishment and refusal of cooperation, which
reduces the average level of cooperation in the society.
We hence consider the following condition:pðBGÞ ¼ C;

(8)which implies that a player who recognized that he has
been labeled as ‘‘bad’’, should apologize by playing
cooperation. Then after this behavior, his reputation cango back to ‘‘good’’, as expressed byd ðBG; CÞ ¼ G;

(9)which can be called ‘‘forgiveness’’.
Requirements given by Eqs. (4), (5), (7) and (9) specify
ﬁve elements of reputation dynamics common to all theleading eight. There are three elements, d(GB, C), d(BB,C), and d(BB, D), which remain unspeciﬁed. Since thesethree can be chosen either G or B, there are in total eightways of ﬁlling them — hence the leading eight.
3.2. Rationality of behavioral strategy
For the pair (d, p) to be an ESS, the behavioral
strategy p achieves a higher payoff on average than any
other 15 behavioral strategies, given that the population
is dominated by the players with (d, p). Cooperation (C)is accompanied by a cost, as the actor can save the costby adopting an alternative option (defection, D).
Playing cooperation, hence, must be accompanied by a
beneﬁt that is going to be given in future, wheninteracting with other players. We consider the difference in the expected payoff in the future between two
players differing only in the reputation. This beneﬁt of
having a higher reputation must exceed the immediate
cost of help in a population in which a high level ofcooperation is maintained stably.
½Benefit of having a higher reputation4½Cost of help.
(10)
If this inequality is reversed, then the optimal choice of
behavioral strategy is to play defection in any situations(p(GG) ¼ p(GB) ¼ p(BG) ¼ p(BB) ¼ D), resulting in the
population without cooperation. Hence in the population
with the cooperation level higher than the one achievedby AllD, Eq. (10) must be satisﬁed. The cost ofcooperation is c. But the beneﬁt of having a higher
reputation depends on many things such as the composition of the population, the strategy, or the expected
number of times each player interacts per generation.
This can be calculated in the population dominated by aparticular (d, p), as shown in Appendix A.
Assume Eq. (10) holds, then we can conclude thefollowing:pðij Þ ¼ C; only if ‘‘dði; j; CÞ ¼ G and dði; j; DÞ ¼ B’’,
(11a)pðij Þ ¼ D; otherwise:

439

(11b)

Eq. (11a) indicates that cooperation is worth playing only when the beneﬁt of having a better reputation
exceeds the immediate cost of c, which occurs only
when the cooperation brings in good reputation
while defection bad reputation. If this is not thecase, the optimal choice is to defect, as indicatedby Eq. (11b). Once the reputation dynamics isknown, the behavioral strategy is fully speciﬁed by
Eq. (11).
As explained before, there are eight possible ways to
ﬁll three unspeciﬁed elements of reputation dynamics,
but the behavioral strategy corresponding to each ofthese is speciﬁed. Only when cooperation produces agood reputation do players give help.
3.3. General proof of two properties of the leading eight
In deriving the leading eight, Ohtsuki and Iwasa(2004) considered errors in two forms: a player intended
to cooperate fails to do so (execution error) and an
observer reports the revised reputation of a player
incorrectly (assessment error), both of which occur at asmall probability of the same order of magnitude as
small parameter e. Deﬁnition of the leading eight isstated in the following form:
Property 1. In the population dominated by (d, p)
players, the behavioral strategy p has a higher ﬁtness
than a rare mutant with any of the 15 behavioral
strategies p’ different from p. This result holds if an
inequality ob  c40 is satisﬁed, in which the ob  cmust be greater than 0 by the difference greater thanO(e), a small term of the same order of magnitude as theerror rates.
Property 2. In the population composed of (d, p)
players only, the average ﬁtness gain obtained perinteraction is close to the possible maximum, bc. To be
precise, the mean ﬁtness gain per interaction is bcminus a small term of O(e). Note that this is equivalent
to that the mean ﬁtness gain per generation is ðb cÞ=ð1  oÞ minus O(e).
Ohtsuki and Iwasa (2004) discovered the leadingeight by exhaustive examination and stated thatthese properties can be shown for the leadingeight strategies, but did not give the proof in generalcases. In Appendix A, we give a proof that the
reputation dynamics of the leading eight have both ofthese properties, and conversely, that the reputation
dynamics with these properties must be one of theleading eight.
Now we have succeeded in clarifying why thesocial norms must be one of the leading eight,
and why a social norm that is not included in theleading eight fails to maintain cooperation at a highlevel.

ARTICLE IN PRESS440

H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 239 (2006) 435–444

4. Discussion
Indirect reciprocity is one of the major driving forcesof the evolution of cooperation in humans (Fehr andFischbacher, 2003). Several experiments have shownthat reciprocation through reputation formation plays
an important role in generalized exchange (Bolton et al.,2005; Wedekind and Braithwaite, 2002; Wedekind andMilinski, 2000). In theory, evolutionary biologists aswell as social scientists have studied about how indirect
reciprocity emerges and works among selﬁsh individuals(Brandt and Sigmund, 2004, 2005; Leimar and Hammerstein, 2001; Nowak and Sigmund, 1998a, b; Ohtsuki
and Iwasa, 2004; Panchanathan and Boyd, 2003, 2004;
Takagi, 1996).
In a previous paper, we examined exhaustively theways of assigning reputation to a player in the next
round based on the current reputation of the player, thatof the opponent, and the action (Ohtsuki and Iwasa,
2004). We found that only eight reputation dynamics
can achieve a very high level of cooperation at theequilibrium, but we did not discuss why only these eight
reputation dynamics work and not others. In the present
paper, we have attempted to identify the mechanisms bywhich the ‘‘leading eight’’ can maintain a high level ofcooperation. We have ﬁrst characterized these eight
reputation dynamics. They have the following common
aspects: (1) Cooperation is maintained in the population
composed of that type only. (2) When cheaters invade,they should be detected and labeled immediately. (3)Those who are labeled as ‘‘bad’’ are refused cooperation
by other members of the population, while those who
refused help to them are regarded as good. (4) The
player who got a bad reputation by occasionalunavoidable errors should apologize, and he will be
forgiven and can return to the good reputation again.
Those four characteristics give us a clear and intuitive
reason why the leading eight are so successful, which we
could not ﬁnd in the previous paper. Second, we havefound how evolutionarily stable behavioral strategy is
deduced from each reputation dynamics of the leadingeight. We have shown that the successful strategy is theone that prescribes cooperation only when giving yields
better reputation to the actor. Third, we gave a formal
analysis and conﬁrmed the ESS condition for theleading eight and the equilibrium cooperation level inthe ESS under small errors. As far as we know, this is
the ﬁrst study that has analytically derived the beneﬁt of
having a higher reputation (see Appendix A for its
detail). We believe that the method used here is directly
applicable to a wide variety of game models on animal
behavior, especially in calculating the value of information.
Most theoretical studies on indirect reciprocity focus
on the evolutionary stability of a cooperative strategy.
One of the characteristics of Ohtsuki and Iwasa (2004) isan explicit consideration of the mean level of cooperation achieved in the ESS. Using this criterion, we candiscuss the effect of errors that propagate the populationand thereby reduce the fraction of cooperative players at
equilibrium. For example in Appendix A, we show thatthe social norms in the leading eight can achieve theequilibrium population with almost all the members
having good reputation even if the small rate of errors
are unavoidable in execution and observation processes;
whilst other reputation dynamics have the equilibrium
including far more members with bad reputation. Thiscan be shown by mathematically examining the dynamical stability near the equilibrium (see Appendix A). If
a social norm can maintain a higher level of cooperation
than an alternative norm, we can deduce that the former
social norm is more likely to be adopted in societies.
Hence, we may expect that social norms we face in theworld are likely to be those that are able to maintain ahigh level of cooperation against errors and recurrent
invasion of alternative strategies.
In the following, we discuss the relation of our workto other studies.
4.1. Kandori’s classical work
In a classical paper of game theory on social norms,
Kandori (1992) investigated social norm which cansustain a cooperative and individually rational strategy,
through local information processing such as reputation, rumor, or gossip. In Kandori’s (1992) formalism,
rules of updating reputation may in general depend on(1) the current reputation of the self, (2) the current
reputation of the opponent, (3) the action of the self,and (4) the action of the opponent, and hence can becalled, following Brandt and Sigmund (2005), ‘‘fourthorder assessment’’. In contrast, Ohtsuki and Iwasa(2004) and Brandt and Sigmund (2004) assume the
new reputation to depend on (1), (2), and (3) only, whichis ‘‘third-order assessment’’. Takahashi and Mashima(2003) focused on the case with (2) and (3) only, andhence their formalism can be called ‘‘second-orderassessment’’, and a discriminator in Nowak andSigmund (1998a, b) using (2) only is ﬁrst-orderassessment. We may translate the general results
obtained by Kandori (1992) into the context of indirect
reciprocity game. Kandori has proved that the rule ofassigning reputation, ‘‘donation to good recipients andrefusal against bad ones, are good behavior’’, is able tosustain cooperation as a sequential equilibrium, which isstricter than Nash equilibrium. Using the formalism
discussed in the present paper, Kandori discussed thereputation dynamics given by d(*G-C) ¼ d(*B-D) ¼ G
and d(*G-D) ¼ d(*B-C) ¼ B, combined with the behavioral strategy: p(*G) ¼ C and p(*B) ¼ D, This rulestudied by Kandori (1992) is one of the leading eight in
Ohstuki and Iwasa (2004).

ARTICLE IN PRESS
H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 239 (2006) 435–444

Also notable is that Kandori (1992) proved that,
under a weak condition, this type of reputation
dynamics makes any kind of outcomes an equilibriumin any kind of games, though generally it takes morethan one round to impose effective punishment and so
there should be more than two reputation. It isinteresting that with the suitable reputation dynamics
having the concept of punishment and justiﬁed defection, everything becomes an equilibrium. This result issimilar to the conclusion of Boyd and Richerson (1992),
who showed that with the option of punishment
everything is possible in a repeated interaction.
4.2. Takahashi and Mashima’s reputation dynamics
Based on the second-order assessment, Takahashi and
Mashima (2003) studied reputation dynamics which give
good reputation only when a donor cooperates with agood recipient. This reputation dynamics assigns bad
reputation to any players who happened to meet a bad
player. With this dynamics, bad reputation bearers keepincreasing over time. By computer simulation Takahashi
and Mashima found that it is robust against invasion byother strategies and that the average cooperation rate isfairly high, about 80%. However, this high giving rate is
originated from a short generation time they assumed intheir simulation. Takahashi and Mashima (2003)
assumed that all the players have good reputation at
the beginning of every generation. If the generation timeis short, each generation ends before bad reputation
spreads in the population, as they observed. However if
there were more interactions per generation, Takahashi
and Mashima’s reputation dynamics would not produce
a society with a high level of cooperation. That is why
this reputation dynamics is not included in the leadingeight.
4.3. Private opinion versus social reputation
Brandt and Sigmund (2004) considered a similar
scheme of the indirectly reciprocity game as Ohtsuki andIwasa (2004) (Fig. 1). In the individual-based directcomputer simulation, Brandt and Sigmund often founda mixture of multiple strategies instead of pure ESS, as aresult of the evolution. One difference between these twostudies was a ﬁnite number of rounds per generation in
Brandt and Sigmund (2004), whilst a very large numberof rounds per generation was assumed in Ohtsuki andIwasa (2004). In the present paper, we relaxed thisassumption of Ohtsuki and Iwasa (2004), and showedthat qualitatively the same result is obtained for the casethe number of rounds each player experiences in a
generation is ﬁnite. The condition for the leading eight
to be ESS is ob4c, in which the beneﬁt of cooperation
by indirect reciprocity is discounted by factor o, theprobability of having a next round.

441

Another difference, probably more important, wasthat in Brandt and Sigmund (2004) the evaluation on aplayer should be done purely based on the evaluator’s
personal observation of the past action of the player.
Therefore players never exchange the information or theviews on other members of the community, and hence
the reputation (they called score) on the same player
may differ between players in the population. In
contrast, Ohtsuki and Iwasa (2004) assumed that the
information on a player’s reputation is exchanged
among other members of the population and is shared
among the members. Reputation in this model is trulysocial information, though it may be incorrect due to theerror in the observation and reporting processes.
One of the criticism to the latter ‘‘social reputation
assumption’’ is that, due to the manipulation of players
in favor of himself, the social reputation is not reliable
and hence unlikely to be the basis of the cooperation in
the society (Brandt and Sigmund, 2004, 2005). Study on
the effect of lies and deliberate spread of incorrect or
distorted information is a very important and interesting
theme (see, for example, Nakamaru and Kawata, 2004).
In fact, it is probable that through language the social
reputation becomes more and more trustless thus
reputation dynamics depending on second or higher
order assessment rules become less effective. However, it
is also possible that language facilitates the formation ofsocial reputation that is free from lies, because weusually carry out careful evaluation of how trustworthy
each piece of information is. If we think of how muchinformation on the action and personality of aparticular member of the community are based on the
direct observation by ourselves, in contrast to theinformation obtained from other members of thesociety, it is clear that the acquisition of the informationof others via constantly exchanging views, gossip or
rumor plays a very important role in evaluating andjudging the character and past behavior of other players
in the same society. Thus language may have two
mutually opposite effects on the social reputation.
In our analysis we assumed that the population shares
the same reputation dynamics, which resulted in the
population having social reputation as a consensus. If,
however, reputation dynamics, namely moral criteria,
are different among players, private opinion might play
more important role than social reputation. It is an open
question to be examined further in future.
In human society it is often the case that good
reputation, once lost, is hard to recover (Herbig et al.,
1994; Nicholas and Fournier, 1999). To consider thisslow recovery of the reputation, we may introduce thechance of recovery from bad reputation to good
reputation, denoted by r, is less than unity. When aplayer had a bad reputation and took the action that is
worth good reputation in reputation dynamics, he canactually recover good reputation only with probability r.

ARTICLE IN PRESS
442

H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 239 (2006) 435–444

With probability 1r his reputation remains bad,though he tried to gain good reputation. When it is thecase, it takes bad reputation bearers on average 1 þ ð1 
rÞ þ ð1  rÞ2 þ . . . ¼ 1=r interactions before recovering
good reputation even if he always tries. Therefore, under
the leading eight the beneﬁt of good reputation isenhanced by a factor of 1/r, making players more likely
to keep their good reputation.
Recently Brandt and Sigmund (2005) showed that
discriminators and AllCs can coexist stably if age
structure is considered.
Axelrod (1984) summarized his study of direct
reciprocity by that a good strategy in direct reciprocity
should be nice, retaliatory, and forgiving. Based on ourstudy of indirect reciprocity, we have found that thekeys to the success in indirect reciprocity are to be nice(shown by maintenance of cooperation pivots), retaliatory (detection of defectors, punishment, and justiﬁcation of punishment pivots), apologetic and forgiving.

Acknowledgment
We thank Hannelore Brandt, Michihiro Kandori,Martin Nowak, Karl Sigmund, and Nobuyuki Takahashi for their fruitful comments. H.O. acknowledges the
support from JSPS.

Appendix A. Proof of two properties of the leading eight
In the following we give a sketch of the proof that theleading eight reputation dynamics have Properties 1 and2 stated in the main text, and that they are the only
reputation dynamics that satisfy both of them. We start
our argument with Property 1.
(1) Behavioral strategy is the one maximizing the fitnessof the playerThis is the same as rational choice condition in the
text. We require that p(i, j) should take either C or D,
the one that gives a higher payoff to the player. Hence
we must compare the beneﬁt of having a higher
reputation that makes return a greater reward in the
future with the cost. We require that the beneﬁt of
having a higher reputation v has to be greater than theimmediate cost c: v4c. This is necessary for any nontrivial ESSs to exist (see text). Under the assumption ofv4c, we request Eq. (11) in the main text. Thiscondition speciﬁes the behavioral strategy p(i, j) once
we know the reputation dynamics d(i, j, X).
Then the remaining problem is to show that thisbeneﬁt of having a good reputation exceeds c. To do so,
we ﬁrst start with a few premises that are to be satisﬁedby successful social rules, including those requested by
Property 2.

(2) All the players should become to cooperate in themonomorphic population in the absence of errors
In the population composed only of (d, p), startingfrom any initial condition, all players cooperate
and all have a high reputation, except for unavoidable
errors at a low frequency. From this, we immediately
conclude p(GG) ¼ C, implying a good player meeting
another good player must cooperate. From this,combined with the rational-choice condition (Eq. (11)),
we haved ðGG; CÞ ¼ G and dðGG; DÞ ¼ B.

(A.1)

Now we consider time change in the fraction of playerswith good reputation. Let h be a frequency of playerswith good reputation in the population. In the absenceof errors, h should converge to 1 from any initialcondition 0oh0 p1. Let d ij ¼ dði; j; pðijÞÞ be the reputation that a p-strategist is assigned after an interaction insituation ij ¼ GG,GB,BG,BB. Then we havedh  2¼ h  dðd GG Þ þ hð1  hÞðdðd GB Þ þ dðd BG ÞÞdtþ ð1  hÞ2  dðd BB Þ  h,ðA:2Þ

where dðGÞ ¼ 1 and dðBÞ ¼ 0. Deﬁne f(h) as the r.h.s. of
Eq. (A.2). The stability of the equilibrium h ¼ 1 leads tof ð1Þ ¼ 0 and f 0 ð1Þp0, which give dðd GG Þ ¼ 1 anddðd GB Þ þ dðd BG ÞX1. When dðd GB Þ þ dðd BG Þ ¼ 2, theglobal stability holds irrespective of the value ofdðd BB Þ. In contrast, when dðd GB Þ þ dðd BG Þ ¼ 1, we havef ðhÞ ¼ ð1  hÞ2  dðd BB Þ, and hence dðd BB Þ ¼ 1 is necessary for global stability of h ¼ 1. We come to thefollowing conclusions:(i) d ðGG; pðGGÞÞ ¼ G, which was already given by
Eq. (A.1).
(ii) At least two of the three equations: d ðGB; pðGBÞÞ ¼
G, d ðBG; pðBGÞÞ ¼ G, and d ðBB; pðBBÞÞ ¼ G musthold.
(3) Errors of small magnitude reduce the cooperationlevel only by a small amountOhtsuki and Iwasa (2004) considered errors in two
forms: a player intended to cooperate fails to do so(execution error) and an observer reports the revised
reputation of a player incorrectly (assessment error),both of which occur at a low rate. These can be
expressed as an additional term of small magnitude (sayof e order). The system’s behavior when perturbed by asmall additional error differs between the following twocases:(i) When both d(GB, p(GB)) ¼ G and d(BG,
p(BG)) ¼ G hold:
The eigenvalue at h ¼ 1 is 1. Since time constant is
1, after more than several rounds, h converges to theequilibrium, hn . Hence small errors of order O(e ) cause
the shift in the equilibrium by O(e ): the fraction of goodpeople decreases by 1  hn ¼ OðÞ.

ARTICLE IN PRESS
H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 239 (2006) 435–444(ii) When d(BB, p(BB)) ¼ G holds but either d(GB,p(GB)) ¼ G or d(BG, p(BG)) ¼ G does not hold:
The eigenvalue of the linearized dynamics at h ¼ 1 iszero, and h ¼ 1 is stable only by the second-order terms:
dð1  hÞ=dt ¼ ð1  hÞ2 , hence convergence to theequilibrium is rather slow. Additional error p
terms
of
ﬃﬃ
magnitude of e cause the shift by 1  hn ¼ Oð Þ. The
decline of the fractionof ‘‘good’’ players is of order ofpﬃﬃ
magnitude of , which is much greater than e if e issmall. This can be demonstrated in a detailed calculationfor each special case of different ways of introducing
errors (calculation not shown here).
By comparison between (i) and (ii), the rules satisfying(i) give a higher fraction of ‘‘good’’ people and hence resultin a higher cooperation level. Therefore, we conclude thata desirable strategy must satisfy the following:d ðGB; pðGBÞÞ ¼ G and d ðBG; pðBGÞÞ ¼ G:

(A.3)(4) Detecting cheaters and punishment
Next, we show p(GB) ¼ D. Assume to the contrary
that p(GB) ¼ C holds. Then every player, who is
supposed to have a good reputation at h ¼ 1 equilibrium, gives help even to opponents having a bad
reputation. This means that it does not matter at allwhether a player has a good reputation or a bad one at
this equilibrium, which contradicts v4c condition.
Therefore, p(GB) ¼ D must hold, which is the condition
for punishment pivot in the text.
From p(GB) ¼ D together with d(GB, p(GB)) ¼ G
which was derived in Eq. (A.3), we conclude
dðGB; DÞ ¼ G(A.4)

which implies that the punishment to a bad player(refusal of cooperation against bad players) is justiﬁed
and the actor in such a situation can maintain a highreputation in the next round.
(5) Benefit of good reputation:
Next we examine d(BG,C) and d(BG, D). From d(BG,
p(BG)) ¼ G obtained in Eq. (A.3), we have thefollowing two possibilities: Case 1, d(BG, C) ¼ G andp(BG) ¼ C, and Case 2, d(BG, D) ¼ G and p(BG) ¼ D.
We examine the possibility of v4c in these cases
separately:
Case 1: When d(BG, C) ¼ G and p(BG) ¼ C.
Consider two players Agood and Abad, whose behavioral strategies are p, and suppose that the reputationof Agood is good whereas that of Abad is bad. In the next
interaction (which exists with probability o), Agoodcooperates (p(GG) ¼ C) with his opponent and his
opponent also cooperates (p(GG) ¼ C) with him,
resulting in his good reputation in the next round(d(GG,C) ¼ G). The expected payoff is oðb  c þ ovÞ.
In contrast, Abad cooperates with his good opponent(p(BG) ¼ C) but his opponent defects (p(GB) ¼ D)
against him, resulting in his good reputation in the next
round (d(BG,C) ¼ G). Abad’s gain is calculated as443

o  ðc þ ovÞ. The difference in gains between these
two gives the beneﬁt of having a higher reputation v, and
it is v ¼ oðb  c þ ovÞ  oðc þ ovÞ ¼ ob. From this,the relation v4c holds when ob4c.
Case 2: When d(BG, D) ¼ G and p(BG) ¼ D:
Consider two players Agood and Abad, whose behavioral strategies are p, and suppose that the reputationof Agood is good whereas that of Abad is bad. In the next
interaction (which exists with probability o), Agoodcooperates (p(GG) ¼ C) with his good opponent andhis opponent also cooperates (p(GG) ¼ C) with him,
resulting in his new good reputation (d(GG,C) ¼ G).
Through this interaction his gain is oðb  c þ ovÞ. In
contrast, Abad defects (p(BG) ¼ D) against his good
opponent and his opponent also defects (p(GB) ¼ D)
against him, resulting in his new good reputation (d(BG,D) ¼ G). Therefore his total gain is calculated asoð0 þ ovÞ. The difference in gains between these twocases is equal to the beneﬁt of having a good reputation,
which is v ¼ oðb  c þ ovÞ  oð0 þ ovÞ ¼ oðb  cÞ.
Hence v4c condition holds if and only if ob4ð1 þ oÞc.
The condition for v4c is satisﬁed when ob4c for therules in Case 1, but only when ob4ð1 þ oÞc for therules in Case 2. The latter is more difﬁcult to satisfy, andhence we request the former condition to be satisﬁed in a
desirable reputation dynamics. Thus we conclude d(BG,C) ¼ G and p(BG) ¼ C. From the rationality of
behavioral strategy (Eq. (11)), we also have d(BG,D) ¼ B.
If the number of interactions within a generation isvery large (o is close to 1), the condition for v4c can besatisﬁed when bc is only slightly larger than zero, asshown in Ohtsuki and Iwasa (2004).
(6) The leading eight:
The argument above speciﬁes the following ﬁve pivots
in the reputation dynamics:d ðGG; CÞ ¼ d ðBG; CÞ ¼ d ðGB; DÞ ¼ G
andd ðGG; DÞ ¼ d ðBG; DÞ ¼ B;
and the following three pivots of the behavioral strategy:pðGGÞ ¼ pðBGÞ ¼ C and pðGBÞ ¼ D:
Now, we have three more pivots in reputation dynamics:d(GB,C), d(BB,C), and d(BB,D). These three can bechosen freely, and hence there are 23 ¼ 8 possibilities,
which are the leading eight social norms (Ohtsuki andIwasa, 2004). One pivot of behavioral strategy p(BB)remains unspeciﬁed, but this is determined by Eq. (11)once both d(BB,C) and d(BB,D) are given.
From these arguments, we can tell that the leadingeight satisﬁes the two properties we requested fordesirable reputation dynamics, and that none of thereputation dynamics other than the leading eight cansatisfy the conditions we request.

ARTICLE IN PRESS
444

H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 239 (2006) 435–444

References
Axelrod, R., 1984. The evolution of cooperation. Basic Books, New
York, USA.
Axelrod, R., Hamilton, W.D., 1981. The evolution of cooperation.
Science 211, 1390–1396.
Bolton, G.E., Katok, E., Ockenfels, A., 2005. Cooperation among
strangers with limited information about reputation. J. Public
Econ. 89, 1457–1468.
Boyd, R., Richerson, P.J., 1992. Punishment allows the evolution ofcooperation (or anything else) in sizable groups. Ethol. Sociobiol.
13, 171–195.
Brandt, B., Sigmund, K., 2004. The logic of reprobation: assessment
and action rules for indirect reciprocation. J. Theor. Biol. 231,
475–486.
Brandt, B., Sigmund, K., 2005. Indirect reciprocity, image scoring, andmoral hazard. Proc. Natl. Acad. Sci. USA 102, 2666–2670.
Fehr, E., Fischbacher, U., 2003. The nature of altruism. Nature 425,
785–791.
Herbig, P., Milewicz, J., Golden, J., 1994. A model of reputationbuilding and destruction. J. Business Res. 31, 23–31.
Kandori, M., 1992. Social norms and community enforcement. Rev.
Econ. Stud. 59, 63–80.
Leimar, O., Hammerstein, P., 2001. Evolution of cooperation
through indirect reciprocity. Proc. R. Soc. London B 268,
745–753.
Nakamaru, M., Kawata, M., 2004. Evolution of rumors that
discriminate lying defectors. Evol. Ecol. Res. 6, 261–283.
Nicholas, M.W., Fournier, G.M., 1999. Recovering from a bad
reputation: changing beliefs about the quality of US autos. Int. J.
Ind. Org. 17, 299–318.

Nowak, M., Sigmund, K., 1998a. The dynamics of indirect reciprocity.
J. Theor. Biol. 194, 561–574.
Nowak, M., Sigmund, K., 1998b. Evolution of indirect reciprocity by
image scoring. Nature 393, 573–577.
Ohtsuki, H., 2004. Reactive strategies in indirect reciprocity. J. Theor.
Biol. 227, 299–314.
Ohtsuki, H., Iwasa, Y., 2004. How should we deﬁne goodness?
reputation dynamics in indirect reciprocity. J. Theor. Biol. 231,
107–120.
Panchanathan, K., Boyd, R., 2003. A tale of two defectors: theimportance of standing for evolution of indirect reciprocity. J.
Theor. Biol. 224, 115–126.
Panchanathan, K., Boyd, R., 2004. Indirect reciprocity can stabilize
cooperation without the second-order free rider problem. Nature
432, 499–502.
Sugden, R., 1986. The Economics of Rights, Co-operation andWelfare. Blackwell, Oxford, UK.
Takagi, E., 1996. The generalized exchange perspective of theevolution of altruism. In: Liebrand, W.B.G., Messick, D.M.
(Eds.), Frontiers in Social Dilemmas Research. Springer, Berlin,
pp. 311–336.
Takahashi, N., Mashima, R., 2003. The Emergence of Indirect
Reciprocity: Is the Standing Strategy the Answer? Center for the
study of cultural and ecological foundations of the mind,
Hokkaido University, Japan, Working Paper Series No. 29.
Trivers, R., 1971. The evolution of reciprocal altruism. Q. Rev. Biol.
46, 35–57.
Wedekind, C., Braithwaite, V.A., 2002. The long-term beneﬁts ofhuman generosity in indirect reciprocity. Curr. Biol. 12, 1012–1015.
Wedekind, C., Milinski, M., 2000. Cooperation through image scoringin humans. Science 288, 850–852.