ARTICLE IN PRESS

Journal of Theoretical Biology 244 (2007) 518–531
www.elsevier.com/locate/yjtbi

Global analyses of evolutionary dynamics and exhaustive search forsocial norms that maintain cooperation by reputation
Hisashi Ohtsuki!, Yoh Iwasa
Faculty of Sciences, Department of Biology, Kyushu University, 6-10-1 Hakozaki, Fukuoka 812-8581, Japan
Received 11 April 2006; received in revised form 22 July 2006; accepted 25 August 2006
Available online 1 September 2006

Abstract
Reputation formation is a key to understanding indirect reciprocity. In particular, the way to assign reputation to each individual,
namely a norm that describes who is good and who is bad, greatly affects the possibility of sustained cooperation in the population.
Previously, we have exhaustively studied reputation dynamics that are able to maintain a high level of cooperation at the ESS. However,this analysis examined the stability of monomorphic population and did not investigate polymorphic population where several strategies
coexist. Here, we study the evolutionary dynamics of multiple behavioral strategies by replicator dynamics. We exhaustively study all 16
possible norms under which the reputation of a player in the next round is determined by the action of the self and the reputation of the
opponent. For each norm, we explore evolutionary dynamics of three strategies: unconditional cooperators, unconditional defectors, andconditional cooperators. We find that only three norms, simple-standing, Kandori, and shunning, can make conditional cooperation
evolutionarily stable, hence, realize sustained cooperation. The other 13 norms, including scoring, ultimately lead to the invasion by
defectors. Also, we study the model in which private reputation errors exist to a small extent. In this case, we find the stable coexistence ofunconditional and conditional cooperators under the three norms.
r 2006 Elsevier Ltd. All rights reserved.
Keywords: Indirect reciprocity; Reputation; Norms; Discriminator; Exhaustive search; Replicator dynamics

1. Introduction
Richard Alexander (1987) said that indirect reciprocity is ‘‘a consequence of direct reciprocity occurring in the presenceof interested audiences’’. The audiences repeatedly evaluate members in a society and judge who deserves help. Those who
gain a good reputation receive donation from others while those who gain a bad reputation miss help. Cooperative act ispassed from person to person via reputation. Hence, having good reputation or status is of great importance in indirect
reciprocation (Fehr, 2004). Recently, much empirical work has been done to reveal the nature of indirect reciprocity andreputation formation in humans (e.g. Bolton et al., 2005; Milinski et al., 2001, 2006; Wedekind and Milinski, 2000;
Wedekind and Braithwaite, 2002). For a recent review on indirect reciprocity, we refer to Nowak and Sigmund (2005).
In theory, Nowak and Sigmund (1998a, b) investigated how indirect reciprocity works among individuals. Nowak andSigmund (1998b) introduced binary reputation, either good or bad, to represent the social status of players. Individuals
repeatedly play a Prisoner’s Dilemma game with others, each time recruiting a different opponent from the society. There
are two strategic choices in this game, cooperation or defection. Those who cooperate pay cost c for their opponent toreceive benefit b. Those who choose defection pay nothing. Players do not interact with the same person more than once.
According to the result of the game, observers assign a new reputation to players. The way to attach reputation is asfollows. Those who cooperated in the previous interaction receive a good reputation. In contrast, those who refused to help
others in the previous round gain a bad reputation. This rule of assigning reputation, or namely the ‘‘norm’’, is called!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 2006 Elsevier Ltd. All rights reserved.
doi:10.1016/j.jtbi.2006.08.018

ARTICLE IN PRESS
H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531

519‘‘scoring’’ (Brandt and Sigmund, 2004; Ohtsuki and Iwasa, 2004). Nowak and Sigmund (1998b) showed that under scoring
conditional cooperators who help only good individuals are resistant to defectors, because they selectively give help only tocooperative members. Reputation works as media for community enforcement (Kandori, 1992).
The simplest as it is, scoring has a critical shortcoming in it. It cannot distinguish sanction from selfish defection. Scoring
assigns a bad reputation to conditional cooperators who refused to help a bad person as punishment. Therefore, noconditional cooperators are motivated to give cheaters a penalty, which obviously leads to a triumph of defectors. Previous
theoretical works confirmed that scoring is not able to sustain cooperation under errors (Panchanathan and Boyd, 2003,
Ohtsuki, 2004, Ohtsuki and Iwasa, 2004) without an additional mechanism, such as growing social networks (Brandt andSigmund, 2005).
Following this result, Ohtsuki and Iwasa (2004, 2006) searched for combinations of a norm and a behavioral strategy
that can maintain cooperation, among a huge number of possibilities. According to their formulation, a norm judges
whether an observed action is good or bad taking the following three components into account: (i) the action of the focal
player (cooperation or defection), (ii) the reputation of the opponent (good or bad), and (iii) the reputation of the focal
player (good or bad). This type of norm is called third-order assessment (Brandt and Sigmund, 2005). Also, a player’s
behavioral strategy that prescribes the action (to cooperate or to defect) toward an opponent is conditional on (a) the
reputation of the opponent (good or bad), and (b) the reputation of the focal player (good or bad). In this framework,
Ohtsuki and Iwasa (2004) asked under which norm which behavioral strategy becomes an evolutionarily stable strategy(ESS) that realizes cooperation at a high level even under a small amount of errors. As a result, they found eightcombinations of a norm and a behavioral strategy, called the ‘‘leading eight’’, which were characterized in the subsequent
paper (Ohtsuki and Iwasa, 2006).
While exhaustive ESS analyses have been completed by Ohtsuki and Iwasa (2004, 2006), their analysis is restricted to theinvasibility of the equilibrium dominated by a single strategy. No works have conducted a global analysis of evolutionary
dynamics of strategies over all possible norms. One of the aims of the present paper is to obtain a complete classification ofevolutionary dynamics over all possible norms. Here, we focus on the norms that are based on second-order assessment
instead of third-order assessment (Brandt and Sigmund, 2005). That is, a norm in this category specifies whether a player isgood or bad based on (i) the action of the focal player (cooperation or defection), and (ii) the reputation of the opponent(good or bad), but without using the previous reputation of the focal player. Similarly, we consider behavioral strategies
that are conditional only on the reputation of the opponent (good or bad), but not on the reputation of the self. By such asimplification, we can reduce the total number of norms from 256 to 16 and the total number of behavioral strategies from
16 to 4, making the exhaustive examination of global behavior feasible. Out of all 16 conceivable norms we find that threenorms, called ‘‘simple-standing’’, ‘‘Kandori’’, and ‘‘shunning’’, realize sustained cooperation.
We also study the effect of private reputation errors in evaluating others in indirect reciprocation. If players individuallyand independently commit errors they result in having different opinions on the same person. Hence, reputation is not
public information but can be a private opinion (that is, we must consider not only who is good but also who thinks who isgood). Here, we study the effect of private reputation errors under a very simple assumption. The reputation of all themembers in the population is determined publicly, but there is a small chance that each player makes a mistake ininterpreting the reputation of others. We show that the existence of such private reputation errors induces the stablecoexistence of unconditional and conditional cooperators under the three norms mentioned above.
2. Model2.1. Prisoner’s dilemma game
Consider an infinitely large population. For each integer round t ¼ 1; 2; . . . , each player randomly finds an opponent
and engages in a one-shot Prisoner’s Dilemma game. There are two behavioral choices, either to give help ( ¼ C;
cooperation) or to refuse help ( ¼ D; defection). Cooperation costs c to the donor and yields the benefit b to the recipient.
In contrast, defection yields nothing to either. Two players in a pair decide their actions simultaneously and gain payoffs.
After the game they leave the pair, and each of them seeks an opponent in the next round. The number of rounds played ina generation by each player follows a geometric distribution. Parameter o represents the probability that the next round
exists ð0poo1Þ. Hence, the mean payoff is calculated as the summed payoffs in which future gains are discounted by thefactor o per round.
2.2. Behavioral strategies
Since players change their opponents every round, they always meet a stranger whom they have never met before. For
strategic choice, a player relies on the reputation of the opponent (except two unconditional strategies, ALLC and ALLD).
Here, we assume the simplest kind of social reputation, binary reputation, as in Nowak and Sigmund (1998b). Each player

ARTICLE IN PRESS520

H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531

Table 1
Sixteen conceivable reputation dynamics that are second-order assessment
C to good

C to badD to good

D to bad

G
G
G
G
G
G
G
G
B
B
B
B
B
B
B
B

G
G
G
G
B
B
B
B
G
G
G
G
B
B
B
B

G
G
B
B
G
G
B
B
G
G
B
B
G
G
B
B

G
B
G
B
G
B
G
B
G
B
G
B
G
B
G
B

Name

Simple-standing
Scoring

KandoriShunning

has either a good or bad reputation. According to the reputation of the opponents, a player determines their action.
Throughout this paper, we assume that individuals know the reputation of the opponent (either correctly or incorrectly; we
exclude the possibility that one does not know the reputation of others). There are four possible behavioral strategies,
ALLC, ALLD, DISC, and pDISC. An ALLC player always helps the opponent. An ALLD player never gives help. A
DISC player helps the good but not the bad (note that ‘‘DISC’’ means a ‘‘discriminator’’). In contrast, a pDISC(paradoxical-discriminator) helps the bad but not the good. In the present paper, we study three of the four strategies,
ALLC, ALLD and DISC, but do not study pDISC strategy because it is odd and not feasible for studying the emergence ofcooperation. We assume that players fail to cooperate against their will with small probability ee, due to, for example, alack of resources (Fishman, 2003). We call this ‘‘execution error’’. We do not consider an execution error of the opposite
side; players never misimplement intended defection because it is quite unlikely that one accidentally helps others though
he intended to do nothing. Later, we see that execution errors play a critical role in our analysis, as in previous studies(Lotem et al., 1999; Panchanathan and Boyd, 2003, 2004).
2.3. Reputation dynamics of second-order assessment
Regarding how to judge what action is good and what is bad, we assume that all members in a society share the same
norm for moral judgment. Following Ohtsuki and Iwasa (2004), we call this norm ‘‘reputation dynamics’’ in the
population. It is denoted by d. In this paper we consider reputation dynamics that are second-order assessment (Brandt andSigmund, 2005). In order to attach a reputation to a player, an observer must know what action the focal player took to
whom. There are four possible outcomes: (1) the focal player cooperated with a good opponent, (2) he cooperated with abad opponent, (3) he defected against a good opponent, and (4) he defected against a bad opponent. To each of the four
scenarios, the reputation dynamics assigns a reputation, either good or bad. Hence, we have 24 ¼ 16 different reputation
dynamics in total, see Table 1.
A player’s reputation is updated as follows. Initially ðt ¼ 0Þ everyone is supposed to have a good reputation. At round t a
focal player randomly finds an opponent and plays a one-shot Prisoner’s Dilemma game with him. Based on the focal
player’s action in the game and the opponent’s reputation, a new reputation at round t þ 1 is assigned to the focal player by
reputation dynamics d.
3. Method
We investigate 16 different reputation dynamics one by one. Let us consider one of the reputation dynamics, d. Under
this norm, we study evolutionary dynamics of three behavioral strategies, ALLC, ALLD and DISC. In the following, we
identify each of these strategies by an integer i: 1 ¼ ALLC, 2 ¼ ALLD, and 3 ¼ DISC. Let xi be the relative abundance ofstrategy i, and let Wi be the total payoff of i.
We adopt the following imitation update rule for strategies. A player is sometimes given an opportunity to change his
strategy. He randomly samples a player and calculates the difference in payoffs of the two. If a sampled player has a greater
payoff then the sampling player imitates the sampled player’s strategy with probability proportional to the difference inpayoffs. Otherwise a sampling player remains the same strategy. This microscopic updating yields the evolutionary

ARTICLE IN PRESS
H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531

521

dynamics of the frequencies of strategies, which are called replicator dynamics (Taylor and Jonker, 1978, Hofbauer and
Sigmund, 1998), given as follows:
x_ i ¼ xi ðW i % W̄ Þ,(1)where W̄ is the average payoff in the entire population, defined as W̄ ¼ x1 W 1 þ x2 W 2 þ x3 W 3 . This differential equation
is defined on the simplex S3 ¼ fðx1 ; x2 ; x3 Þjx1 þ x2 þ x3 ¼ 1; xi X0g. Each corner of the simplex is an equilibrium of the
dynamics corresponding to a monomorphic population. Note that in this dynamics only the relative size of payoff matters:
additive shifts in payoffs do not alter the dynamics at all.
Throughout our analysis, we assume that the execution error rate ee is very small.
4. Results under public reputation
In this section, we assume that each individual knows the correct reputation of others. In this sense the reputation is
public information. That is, all individuals have the same opinion on the focal player.
4.1. When oboc holds
When oboc holds, we can prove that ALLD always gains the largest payoff among the three strategies under any
conceivable norms. This is plausible because the cost of cooperation c exceeds the maximum return in the next round ob.
In this case, cooperation can never be advantageous. Therefore, in the following we consider the case in which ob is larger
than c unless otherwise specified.
4.2. Scoring
Consider the reputation dynamics called scoring (given as ‘‘GGBB’’ in Table 1) (Brandt and Sigmund, 2004, Ohtsuki andIwasa, 2004). Under this norm, cooperation is always good and defection is always bad, irrespective of the reputation of
the opponent.
~ i be the total
By adding the same constant we can make W2 equal to zero without loss of generality (see Section 3). Let W~
payoff of strategy i after this normalization. Exact calculation in Appendices A.1 and B.1 shows W 2 ¼ 0 and~ 1 ¼ ð1 % !e Þ ð1 % !e Þobx3 % c ;W
1%o~ 3 ¼ 1 % o þ ð1 % !e Þox1 W~ 1.
W
1 % ð1 % !e Þox3

(2)

The phase portrait of the dynamics is described in Fig. 1a. In the absence of defectors ðx2 ¼ 0Þ we obtain~ 1 ¼ %ð1 % !e Þ!e o~ 3%WWð1 % !e Þobx3 % c.
ð1 % oÞf1 % ð1 % !e Þox3 g(3)Therefore, there is an equilibrium P on the ALLC–DISC edge, which is stable along this edge. Note, however, that it is
not asymptotically stable. On the ALLD–DISC edge, there is an unstable equilibrium Q. There is a line of equilibria
located in the center of the simplex, at x3 ¼ c=ð1 % !e Þob. This line always connects the two equilibria, P and Q, irrespectiveof error rates ee, so along this line neutral drift can drive the population away from P.
A small segment on the P–Q line in the vicinity of P (in gray in Fig. 1a) is transversally stable so that any perturbations
away from this segment are counterattacked by the dynamics (Brandt and Sigmund, 2006). Therefore, each point on thesegment including P is Lyapunov stable. However, the length of this segment is small and of order ee. Therefore, thestability of P is quite vulnerable especially when the error rate is small. The other part of the P–Q line (in white in Fig. 1a; it
can be quite large when is ee is small) is transversally unstable. Any perturbations to increase DISC players are amplified,ultimately leading back to the equilibrium P (see Fig. 1a). On the other hand, any perturbations to decrease DISC players
lead to the fixation of ALLD players (see Fig. 1a). Taking neutral drift and small errors into account, we conclude that
ALLD is the unique end point of the dynamics after a long run.
4.3. Simple standing
Next, we study the norm given by GGBG in Table 1. This is similar to the ‘‘standing’’ (Sugden, 1986, Leimar andHammerstein, 2001) for the third-order assessment problem, but is not exactly the same. Hence, we call this ‘‘simplestanding’’. This reputation dynamics differs from scoring in that those who refused to help the bad are regarded as good.
This norm has the concept of justified defection (Nowak and Sigmund, 2005).

ARTICLE IN PRESS
522

H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531
DISC

DISC

Q

P

ALLC

ALLD

(a)

Q

ALLC

DISC

DISC

Q

ALLC

(c)

ALLD

(b)

ALLD

Q

ALLC

(d)

ALLD

Fig. 1. The phase portrait of evolutionary dynamics of three behavioral strategies, ALLC, ALLD, and DISC when execution errors exist. A triangle
represents the phase space, simplex S3. Each corner of the simplex corresponds to a monomorphic population. Solid circles, circles in gray, and open
circles represent asymptotically stable equilibria, Lyapunov stable but not asymptotically stable equilibria, and asymptotically unstable equilibria,
respectively. We used b ¼ 10, c ¼ 1, w ¼ 0:4 and !e ¼ 0:01. (a) Under scoring: There is a line that consists of equilibria, which connects two equilbria on
the edges, P and Q. A small segment on this line in the very vicinity of P (in gray) is transversally stable, but the other part (in white) is transversally
unstable. With our parameters the former occupies 0.7% and the latter occupies 99.3% of the P–Q line. P is Lyapunov stable but not asymptoticallystable. Along the ALLC–DISC edge, the population eventually reaches the equilibrium P. From P a neutral drift can replace some ALLC players with
ALLD players so that the population reaches a transversally unstable part of the P–Q line (in white), where any deviations to decrease DISC players leadto the fixation of ALLD. ALLD is the unique asymptotically stable equilibrium. (b) Under simple-standing: On the ALLC–DISC edge DISC always earns
larger payoff than ALLC, so DISC eventually becomes dominant. The corners of DISC and ALLD are both stable equilibria, suggesting that both
strategies are evolutionarily stable. The DISC–ALLD edge exhibits bistability and has an unstable equilibrium Q. Its stable manifold is theseparatrix dividing the phase space into two basins of attraction of DISC or ALLD. Note that the separatrix is very close to the ALLC–DISC edge
near the ALLC corner. Under (c) Kandori and (d) shunning: The phase portrait is qualitatively similar to that of simple standing. DISC is evolutionarily
stable.

~ 2 ¼ 0, we obtain
After the normalization of W
~ 1 ¼ ð1 % !e Þ ð1 % !e Þobx3 % ½1 þ of1 % ð1 % !e Þðx1 þ x3 Þg'c ,W
ð1 % oÞ½1 þ of1 % ð1 % !e Þðx1 þ x3 Þg'~ 3 ¼ ð1 % !e ÞW

ð1 % !e Þobx3 % c
ð1 % oÞ½1 þ of1 % ð1 % !e Þðx1 þ x3 Þg'(4)(see Appendix B.2). The phase portrait of this dynamics is given in Fig. 1b. In contrast to scoring, DISC is always favoredon the ALLC–DISC edge, because in the absence of defectors,~ 3%W~ 1 ¼ o!e c þ Oð!2 Þ
W
e
1%o

(5)

is always positive. The ALLD–DISC edge shows bistability and has an unstable equilibrium Q. The corners of DISC and
ALLD are both asymptotically stable equilibria of the dynamics, suggesting they are ESSs. The path that converges to Q
(i.e. the stable manifold of Q) runs horizontally and divides the phase space into two regions, and it is a separatrix of theevolutionary dynamics. Above the separatrix is the basin of attraction of DISC. Below that is that of ALLD. Hence,
depending on the initial condition, cooperation can be stably maintained by DISC strategy under simple-standing. Whenthe separatrix comes close to the ALLC–DISC edge, it runs downward in the neighborhood of ALLC–DISC edge, andfinally converges to ALLC-corner.

ARTICLE IN PRESS
H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531

523

4.4. Kandori (GBBG)
We consider the norm represented as GBBG in Table 1. This is the same norm that was proved to be able to maintain thecooperative equilibrium under a much wider condition by Kandori’s (1992) classical work. After this, we call thisreputation dynamics ‘‘Kandori’’. This norm has the concept of justified defection. In addition helping a bad player is a bad
action. Too much generosity is regarded bad (Takagi, 1996) under this norm.
The phase portrait of the evolutionary dynamics under this norm is given in Fig. 1c (see Appendix B.3 for calculation of
payoffs). It is qualitatively the same as that in simple-standing. Again DISC is always favored against ALLC on the
ALLC–DISC edge. Both DISC and ALLD are ESSs. The path that converges to the unstable Q on the ALLD–DISC edge
is the separatrix of the dynamics. It lies between two basins of attraction of ALLD or DISC. We conclude that the norm
Kandori can also foster sustained cooperation.
4.5. Shunning (GBBB)
We consider the reputation dynamics given as GBBB in Table 1, called shunning (Nowak and Sigmund, 2005). Shunning
is a strict norm in such a sense that those who interacted with bad players are immediately labeled as bad, irrespective of
their action (C or D). Under this norm, a player gains a good reputation only by cooperating with a good player.
The phase portrait of the evolutionary dynamics of strategies under this norm is given in Fig. 1d (see Appendix B.4 forcalculation of payoffs). It is qualitatively the same as simple-standing and Kandori. Shunning enables sustainedcooperation, too.
4.6. Other reputation dynamics
We have studied four reputation dynamics out of the 16 in Table 1. Under each of the other 12 reputation dynamics, we
can prove that ALLD is the unique global attractor. The proof is in Appendix B.5. Hence, they cannot foster cooperation.
5. With private reputation errors
So far we have studied evolutionary dynamics of strategies under the assumption of public information. In this section,
we slightly loosen this assumption and study the effect of small amount of private reputation errors. Suppose that at eachround t, a player has an incorrect opinion on a focal player with small probability ep due to some reasons. We consider
errors of both directions: a player may mistakenly regard a good player as bad or he may mistakenly regard a bad one as
good. For example, when player X’s correct reputation is good, a vast majority regards X as a good person but a small
amount of individuals who have committed this error think that X is a bad person. The question is how the reputation ofplayer Y, who is the opponent of X in the next round, is determined, because it is dependent on X’s reputation but somethink X good and others think X bad. Here, we assume that reputation is determined publicly in every round: that is, Y’s
new reputation is first determined by the majority rule in the society and everyone shares this new information. After thispublic consensus is reached, each individual may again independently deviate from this due to private reputation errors in
the next round. As a result, private reputation errors committed in a round in evaluating other members are not carriedover to the following round. We discuss the appropriateness of this assumption later.
Thus, we will consider two different sorts of errors, execution errors (with the rate ee) and private reputation errors (ep).
We assume that ee and ep are very small. Notice that the following results are derived for ob4c.
5.1. Scoring
Consider scoring (see Table 1). Introduction of private reputation errors does not change the structure of evolutionary
dynamics qualitatively. See Fig. 2a. We have an equilibrium P on the ALLC–DISC edge. It is stable along this edge but is
not asymptotically stable. On the ALLD–DISC edge there is an unstable equilibrium Q. The straight line connecting P and
Q consist of equilibria (see Appendix B.1). A small segment on this line in the very vicinity of P (in gray in Fig. 2a) is
qffiffiffiffiffiffiffiffiffiffiffiffiffi
transversally stable, which length is of order !2e þ !2p . The other part (in white in Fig. 2a) is transversally unstable.

Even if the initial population has plenty of DISC players, the equilibrium P with a mixture of DISC and ALLC iseventually reached. A neutral drift can replace ALLC players with ALLD players along the line of equilibria. Once thenumber of ALLD players exceeds a certain amount and the population reaches the unstable part of the segment (in whitein Fig. 2a), a small deviation to decrease DISC players leads to the fixation of unconditional defectors. Hence, scoring is
unlikely to be able to maintain stable cooperation. See Appendix B.1 for detailed calculations.

ARTICLE IN PRESS
524

H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531
DISC

DISC

R
P

Q

Q

ALLC

ALLD

(a)

ALLC

ALLD

(b)
DISC

DISC

R

R
Q

ALLC

ALLD

(c)

Q

ALLC

ALLD

(d)

Fig. 2. The phase portrait of evolutionary dynamics of three strategies, ALLC, ALLD, and DISC, when both execution and private reputation errors
exist. The meanings of symbols used are the same as in Fig. 1. We used b ¼ 10, c ¼ 1, w ¼ 0:4, !e ¼ 0:01 and !p ¼ 0:04. (a) Under scoring: The phase
portrait is qualitatively unchanged from Fig. 1a. There is a line of equilibria in the center of the simplex. About 6% of the line in the vicinity of P istransversally stable (in gray) in our parameters while the rest 94% (in white) is transversally unstable. P is Lyapunov stable but not asymptotically stable.
After some neutral drifts along the P–Q line, a small deviation to decrease DISC players leads to the fixation of ALLD. (b) Under simple-standing: Unlike
Fig. 1b, the ALLC–DISC edge exhibits bistability. There is a coexistence equilibrium R between ALLC and DISC that is stable along the ALLC–DISC
edge. The separatrix, the path converging to unstable equilibrium Q, divides the phase space into two regions. Note that the separatrix is very close to the
ALLC–DISC edge around the ALLC corner. The equilibrium R lies in the upper region, so it is asymptotically stable. Hence, stable coexistence ofunconditional and conditional cooperators is realized. Under (c) Kandori and (d) shunning: The phase portrait is similar to that of simple standing. The
coexistence equilibrium R is asymptotically stable, hence an attractor of the dynamics.

5.2. Simple-standing, Kandori, amd shunning
Under simple-standing, Kandori, or shunning, DISC strategy is evolutionarily stable in the absence of private reputation
errors. However, the dynamics of behavioral strategies can change if small private reputation errors are included inaddition to small execution errors.
As an example, consider simple-standing (see Table 1). Fig. 2b shows the evolutionary dynamics of three strategies undersimple-standing (for detailed calculations of payoffs see Appendix B.2). We see that the introduction of private reputation
errors alters the dynamics on the ALLC–DISC edge. In fact Eq. (5) changes to~ 3%W~ 1 ¼ %obx3 !p þ fo!e þ ð1 þ ox3 Þ!p gc þ Oð!2 Þ,
W
1%o

(6)

b 1
1
4 þ
,
c o !p =ð!e þ !p Þ

(7)

where O(e2) represents small terms of magnitude of ee2 and ep2. If

holds (the inequality (7) is satisfied often when ep is large in comparison to ee), then we have a stable equilibrium R along
the ALLC–DISC edge. We stress that DISC is no more evolutionarily stable. On the ALLD–DISC edge, there is an
unstable equilibrium Q. The path that converges to Q is the separatrix of the dynamics, dividing the phase space into two
regions. The lower region is the basin of attraction of ALLD. Remarkably, all the internal points of the ALLC–DISC edge
including R belong to the upper region (Fig. 2b). Therefore, R is an attractor of the dynamics: from any initial states in theregion above the separatrix, the population converges to R. R is a polymorphic equilibrium in which unconditional andconditional cooperators coexist, and it is stable against the invasion of ALLD. R is located away from the separatrix.
If private reputation errors are not frequent, Eq. (7) is not satisfied, and DISC is favored against ALLC on the
ALLC–DISC edge. DISC remains evolutionarily stable as in Fig. 1a (see Appendix B.2 for further details), as long as
ob4c holds. In contrast, if private reputation errors are sufficiently frequent compared with execution errors, DISC is

ARTICLE IN PRESS
H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531

525

susceptible to those errors while ALLC is not, because ALLC strategists do not use the reputation of others at all. This
brings an advantage to unconditional cooperators, leading to the coexistence.
Qualitatively similar results hold for Kandori and shunning. See Figs. 2c–d. For both norms we have a stable coexistence
equilibrium R on the ALLC–DISC edge if private reputation errors occur. In Appendices B.3–4 we show the conditions
under which the coexistence equilibrium appears.
5.3. Other reputation dynamics
None of the other 12 reputation dynamics (see Table 1) can realize sustained cooperation in the absence of private
reputation errors, and this conclusion remains the same when there are private reputation errors. See Appendix B.5 for the
proof.
6. Selection pressure to reduce private reputation errors
In the last section, we assumed that reputation was determined publicly but each member has a chance to incorrectly
memorize the reputation of a focal person. Those who committed a private reputation error and had an incorrect opinion
toward a focal person can modify his error through communicating with other members of the population. In this section,
we will show that there is a selective pressure at work for each player to reduce his own private reputation error rate ep.
Consider a mutant of DISC players, called DISC’ player, who also uses DISC as behavioral strategy and cooperates withgood opponents only. A DISC’ player communicates with others concerning the reputation of the opponent and attempts
to adjust his opinion to sympathize with the majority if his private opinion on the opponent differs from that of the
majority. Let e0 p be the probability that he has an incorrect opinion on a focal player. From the nature of DISC’ strategy
we expect e0 poep, because communication enables a DISC’ player to modify his incorrect opinion if any. Suppose that the
population consists of the fraction of x(3 of DISC players and that of 1 % x(3 of ALLC players. Let W4 be the total payoff ofrare DISC’ players in that population. Under simple standing, Kandori, or shunning, we obtainobx(3 % c.
(8)1%o
We can prove that Eq. (8) is always positive at the coexistence equilibrium of ALLC and DISC (represented as R in
Figs. 2b–d). This implies that selection favors DISC’ mutants more than wild-type DISC players. In other words, theability to correct private reputation errors is favored by natural selection. In order to perform well in a society where theindirect reciprocity operates, players should care not about ‘‘how I think’’ but about ‘‘how others think’’. Throughcommunication, players correct private reputation errors they committed and side with the majority. We expect that, as aresult of this selection, ep is kept small if communication among members is not very costly.
W 4 % W 3 ) ð!p % !0p Þ

7. Discussion
We have studied evolutionary dynamics of three strategies, ALLC, ALLD, and DISC, under 16 possible reputation
dynamics that are based on second-order assessment (Brandt and Sigmund, 2005). This is the first study that has
systematically explored global evolutionary dynamics for all conceivable norms. As a result, we found that only the threenorms out of 16, simple-standing, Kandori, and shunning (see Table 1) could realize sustained cooperation while the other13, including scoring, could not. First, we considered the effect of execution errors only. Under the three norms, the cornerof DISC strategy was asymptotically stable equilibrium of the dynamics; hence, DISC strategy was evolutionarily stable.
Second, we incorporated private reputation errors of evaluating others. We obtained the stable coexistence ofunconditional and conditional cooperators. Finally, we discussed natural selection favoring players with smaller private
reputation errors, who communicate with others and sympathize with the majority in opinion.
As the benefit-to-cost ratio of cooperation b=c changes, the evolutionary dynamics change in the following manner if
simple standing, Kandori, or shunning is adopted. When small private reputation errors exist and the benefit-cost ratio ofcooperation b=c is large, we obtain the stable coexistence of unconditional and conditional cooperators (equilibrium R in
Figs. 2b–d). As b=c ratio becomes smaller, conditional cooperators become more abundant at the equilibrium: in the phasespace in Figs. 2b–d the coexistence equilibrium R approaches the DISC-corner, until finally unconditional cooperators
disappear and a monomorphic population of conditional cooperators realizes sustained cooperation as an ESS, as inFigs. 1b–d. As b=c decreases further, the unstable equilibrium Q and the separatrix in Figs. 1b–d move upward and thebasin of attraction of ALLD expands. When b=c becomes less than 1=o, the basin of attraction of DISC vanishes and
ALLD prevails from any initial conditions.
Hence, b=c41=o is the condition for the evolution of cooperation by indirect reciprocity. If this is satisfied, then there
are two situations with respect to the composition of the population. For example under simple-standing norm,

ARTICLE IN PRESS
526

H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531

cooperation is sustained by the mixture of unconditional and conditional cooperators if b=c41=o þ ½!p =ð!e þ !e Þ'%1
holds; but cooperation is sustained by a monomorphic population of conditional cooperators if instead
1=oob=co1=o½!p =ð!e þ !p Þ'%1 holds. In the absence of private reputation errors, we always obtain the latter because
the term ½!p =ð!e þ !p Þ'%1 is infinitely large.
7.1. Leading two and shunning
Ohtsuki and Iwasa (2004) studied 256 reputation dynamics that are third-order assessment. A norm that is third-orderassessment judges an observed action by (i) the action of the focal player, (ii) the reputation of the opponent, and (iii) the
reputation of the focal player. As a result of ESS analysis, Ohtsuki and Iwasa found eight combinations of a reputation
dynamics and a behavioral strategy, called the leading eight. The reputation dynamics of two of the leading eight do notuse (iii), and they are essentially based on second-order assessment. Those two norms are simple-standing and Kandori,and may be called the ‘‘leading two’’ in the indirect reciprocity of second-order assessment. We note that the leading two
has the concept of justified defection; defection against a bad person is regarded as a good behavior (see Table 1). This isquite effective in expelling cheaters when they are rare. However, it is also true that defectors can gain a good reputation
without giving if they are abundant in the population, which potentially weakens the cooperative strategies.
It is noteworthy that shunning can make DISC-strategy evolutionarily stable, although it does not belong to the leadingeight, hence nor to the leading two. This difference comes from different assumptions on the initial condition. In this paper,
we assumed that everyone has a good reputation at the start of each generation. In contrast, in Ohtsuki and Iwasa (2004,
2006), the initial fraction of good persons can be an intermediate value, and the fraction of good persons in the leadingeight automatically increases and becomes close to unity after multiple rounds of the game. For the population adopting
shunning, the fraction of good players at the ESS monotonically declines with time, but the rate of decline is slow ifeveryone is good in the initial population and if error rate is very small. When this is the case, the repeated game terminates
far earlier before many players become bad in the population, and cooperation is sustained under shunning, which is inagreement with that of Takahashi and Mashima (2003).
7.2. Kinds of errors and the evolutionary outcome
When private reputation errors occur relatively more frequently than execution errors, the stable coexistence ofunconditional and cooperators is likely to be achieved. This indicates that different types of errors have different impacts
on the evolutionary dynamics, even though they occur rarely. Since the difference in payoffs between ALLC and DISC
strategies results from nothing but errors, the dynamics are highly sensitive to the manner in which errors are introduced
into models. The presence of people who are labeled bad favors DISC because ALLC misses an opportunity to defectwithout being punished. Hence, a large execution error ee favors DISC over ALLC. In contrast, larger private reputation
errors of evaluation of others ep would jeopardize DISC. If the reputation is incorrect, a DISC player defects against a‘‘bad’’ opponent, and may find out being punished by others, because the opponent was in fact considered as ‘‘good’’ byother members.
To explore this further, we introduce the third error, called ‘‘reporting error’’, into our model and examine its effect(Ohtsuki and Iwasa, 2004). The action of a focal player is observed by a few others, who report it to the rest of the
population, and then a collective decision on the reputation in the next round is made (this is called ‘‘indirect observation
model’’ by Ohtsuki and Iwasa (2004)). A reporting error occurs in this process: a reporter may mistakenly report the wrong
information about the action of the focal player to all the others (note that we do not study intentional lying; for studies onlying see Nakamaru and Kawata, 2004). Therefore, the reporting errors influence all members in the population.
As an example consider simple-standing. We consider three errors; execution errors, reporting errors, and private
reputation errors, with rates ee, er and ep, respectively. Note that the former two affect all players but the latter one
influences the error-committer only. Private reputation errors ep disfavor conditional cooperation by indirect reciprocity. If
players have different opinions on the same person, errors undermine cooperation (Takahashi and Mashima, 2003; Brandt
and Sigmund, 2005). In contrast, reporting errors would not harm conditional cooperators because those errors cause
incorrect evaluation on a member by all the players in the population. On the contrary, reporting errors er increase thefraction of player labeled ‘‘bad’’ by public, and hence favor DISC over ALLC, in the same way as execution errors ee.
Preliminary calculation shows that reporting errors only changes ee in Eq. (7) to !e þ !r .
7.3. Advantage of adopting evaluation of the majority
We have shown that players gain larger payoff by tuning their private (incorrect) opinion to that of the public if theydiffer. In order to receive help from others, it is very important to be regarded as good by others. What really matters inindirect reciprocation is not ‘‘how I think of me’’ but ‘‘how others think of me’’, because it is from others that a player

ARTICLE IN PRESS
H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531

527

receives help. Therefore, each player corrects private reputation errors through communication with others. We believethat in this process language capability of humans must play an important role (Fehr and Fischbacher, 2003). When theeffect of private reputation errors is kept small such elaborated norms as simple-standing, Kandori, or shunning, are able
to contribute much to sustained cooperation. Based on the analysis of the present paper, we conjecture that the evolutionof language have caused a rapid evolution of indirect reciprocity. Linguistic communication enables humans to constructpublic information that all members sympathize with. As a result, reputation realizes community enforcement forcooperation.
Acknowledgments
This work was done in support of Grant-in-Aids from Japan Society for the Promotion of Science to H.O and to Y.I.
Appendix A. Calculation of total payoff Wi
Let Wi be the discounted total payoff of strategy i (1 ¼ ALLC, 2 ¼ ALLD, and 3 ¼ DISC). Let Pi(t) (t ¼ 1, 2, y) be theaverage payoff of strategy i at round t. Then Wi is written as
Wi ¼

1
X
t¼1

ot%1 Pi ðtÞ,(A.1)

where o is a discount factor ð0poo1Þ. Let Gi(t) (t ¼ 0, 1, 2, y) be the fraction of individuals among i strategists
whose (correct) reputation is good at the end of round t. The fraction of bad individuals among i strategists isgiven by Bi ðtÞ ¼ 1 % G i ðtÞ. At round t, a player receives cooperation (i) if he meets an ALLC player or (ii) if he meets a
DISC player by whom he is thought to be a good player. Regarding when one pays cost, an ALLC player always
cooperates with others while a DISC player cooperates only when he meets a good person. Taking those into
consideration, we obtain
P1 ðtÞ ¼ ð1 % !e Þ½fx1 þ fð1 % !p ÞG 1 ðt % 1Þ þ !p B1 ðt % 1Þgx3 gb % c',

P2 ðtÞ ¼ ð1 % !e Þ½fx1 þ fð1 % !p ÞG 2 ðt % 1Þ þ !p B2 ðt % 1Þgx3 gb',P3 ðtÞ ¼ ð1 % !e Þ½fx1 þ fð1 % !p ÞG 3 ðt % 1Þ þ !p B3 ðt % 1Þgx3 gb % fð1 % !p ÞGðt % 1Þ þ !p Bðt % 1Þgc'.

ðA:2Þ

Here, GðtÞ * x1 G 1 ðtÞ þ x2 G 2 ðtÞ þ x3 G 3 ðtÞ and BðtÞ * x1 B1 ðtÞ þ x2 B2 ðtÞ þ x3 B3 ðtÞ. ee and ep are error rates of execution
error and private reputation error respectively. From Eqs. (A.1) and (A.2) we need to know Gi(t) (t ¼ 0, 1, 2, y) in order toderive Wi.
From our assumption, we have G 1 ð0Þ ¼ G2 ð0Þ ¼ G 3 ð0Þ ¼ 1 as an initial condition. Let us derive a recursion on Gi(t).
Whether a player is assigned a good or bad reputation depends on what action he takes to whom. Consider the interaction
at round t.
(1) An ALLC player cooperates with a good player with probability m11 ¼ ð1 % !e ÞGðt % 1Þ, cooperates with a bad player
with probability m12 ¼ ð1 % !e ÞBðt % 1Þ, defects against a good player with probability m13 ¼ !e Gðt % 1Þ, and defects
against a bad player with probability m14 ¼ !e Bðt % 1Þ.
(2) An ALLD player cooperates with a good player with probability m21 ¼ 0, cooperates with a bad player withprobability m22 ¼ 0, defects against a good player with probability m23 ¼ Gðt % 1Þ, and defects against a bad player
with probability m24 ¼ Bðt % 1Þ.
(3) A DISC player cooperates with a good player with probability m31 ¼ ð1 % !e Þð1 % !p ÞGðt % 1Þ, cooperates with abad player with probability m32 ¼ ð1 % !e Þ!p Bðt % 1Þ, defects against a good player with probability m33 ¼
f1 % ð1 % !e Þð1 % !p ÞgGðt % 1Þ, and defects against a bad player with probability m34 ¼ f1 % ð1 % !e Þ!p gBðt % 1Þ.
Now define a 3 + 4 matrix M as
01
m11 m12 m13 m14
BC
M ¼ @ m21 m22 m23 m24 A.

(A.3)

DBD ÞT .

(A.4)

m31

m32

m33

m34

The components mij are linear functions of Gðt % 1Þ, so we should write M as M½Gðt % 1Þ'. Also define a 4 + 1‘‘reputation dynamics’’ matrix (or a column vector) D as
D ¼ ð DGC

DBC

DGD

ARTICLE IN PRESS
528

H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531

Here each of DGC, DBC, DGD, DBD corresponds to ‘‘C to good’’, ‘‘C to bad’’, ‘‘D to good’’, ‘‘D to bad’’. If the focal
reputation dynamics d assigns a good reputation in this situation then the corresponding D-value is 1, otherwise it is 0. For
example, scoring is (C to good, C to bad, D to good, D to bad) ¼ (G, G, B, B) so it yields D ¼ ð 1 1 0 0 ÞT . Using thosenotations above we obtain the following recursion on Gi(t)’s:ð G1 ðtÞ

G3 ðtÞ ÞT ¼ M½Gðt % 1Þ'D.

G2 ðtÞ

(A.5)

Since GðtÞ * x1 G1 ðtÞ þ x2 G 2 ðtÞ þ x3 G3 ðtÞ, we have GðtÞ ¼ ð x1 x2 x3 Þ , M½Gðt % 1Þ'D. This is a linear recursion on
G(t), so we are able to solve that. Then we can solve Eq. (A.5), so we obtain Wi from Eqs. (A.1) and (A.2).
Appendix B. Results for each of 16 norms
In the following, we use notation like ‘‘GGBB’’ to represent a norm out of 16. For example, GGBB means (C to good, C
to bad, D to good, D to bad) ¼ (G, G, B, B), so it represents scoring (see also Table 1). Let Wi be the discounted total payoffof strategy i, calculated in the previous section. By subtracting W2 from each Wi we can normalize payoff such thatqffiffiffiffiffiffiffiffiffiffiffiffiffi~ 1 ¼ W 1 % W 2, W
~ 2 ¼ W 2 % W 2 ¼ 0, and W~ 3 ¼ W 3 % W 2 . We assume that the magnitude of errors ! * !2 þ !2 is soWep

small.

B.1. GGBB (scoring)
From Appendix A we obtain~ 1 ¼ ð1 % !e Þ ð1 % !e Þð1 % 2!p Þobx3 % c ,W
1%o~ 3 ¼ ð1 % !e Þ ð1 % !e Þð1 % 2!p Þobx3 % c 1 % o % ð1 % 2oÞ!p þ ð1 % !e Þð1 % 2!p Þox1W
1%o
1 % ð1 % !e Þð1 % 2!p Þox3
1
%
o
%
ð1
%
2oÞ!
þ
ð1
%
!
Þð1
%
2!
Þox
p
e
p
1
~1
¼W
.
1 % ð1 % !e Þð1 % 2!p Þox3

ðB:1ÞWhen x2 ¼ 0,

~ 1 ¼ %ð1 % !e Þ f!p þ !e ð1 % 2!p Þogfð1 % !e Þð1 % 2!p Þobx3 % cg .
~ 3%WW
ð1 % oÞf1 % ð1 % !e Þð1 % 2!p Þox3 g(B.2)

From these, two equilibria, P and Q, and the line of equilibria are at x3 ¼ c=ð1 % !e Þð1 % 2!p Þob.
B.2. GGBG (simple-standing)
From Appendix A, we obtain~ 1 ¼ ð1 % !e Þ ð1 % !e Þð1 % 2!p Þobx3 % ½1 þ of1 % ð1 % !e Þðx1 þ ð1 % !p Þx3 Þg'c ,W
ð1 % oÞ½1 þ of1 % ð1 % !e Þðx1 þ ð1 % !p Þx3 Þg'~ 3 ¼ ð1 % !e Þ ð1 % !e Þð1 % !p Þð1 % 2!p Þobx3 % ½1 % !p f1 % oð1 % ð1 % !e Þðx1 þ ð1 % !p Þx3 ÞÞg'c ,W
ð1 % oÞ½1 þ of1 % ð1 % !e Þðx1 þ ð1 % !p Þx3 Þg'(B.3)

When x2 ¼ 0,

~ 1 ¼ %obx3 !p þ fo!e þ ð1 þ ox3 Þ!p gc þ Oð!2 Þ.
~ 3%W
(B.4)
W
1%o
First, in the absence of defectors we have
~ 3%W
~ 1 ¼ o!e c þ Oð!2 Þ,
W
(B.5)
e
1%o
which is always positive. Therefore, DISC is always favored against ALLC on the ALLC–DISC edge. Second consider
when private reputation errors exist. If
b 1 1
4 þ ;
c o a

"

#
a * !p =ð!e þ !p Þ ,(B.6)

ARTICLE IN PRESS
529

H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531

is satisfied then the coexistence equilibrium R emerges on the ALLC–DISC edge as in Fig. 2b. If not, DISC isevolutionarily stable as in Fig. 1a as long as ob4c.
B.3. GBBG (Kandori)
From Appendix A we obtain~ 1 ¼ ð1 % !e ÞW
ð1 % !e Þð1 % 2!p Þobx3 ½1 þ of%1 þ ð1 % !e Þð1 % 2!p Þx3 g' % ½1 þ of1 % ð2x1 þ x3 Þð1 % !e Þg'c+,
ð1 % oÞ½1 þ of!e % ð1 % !e Þðx1 % x2 Þg'~ 3 ¼ ð1 % !e ÞW+

ð1 % !e Þð1 % 2!p Þobx3 f1 % oð1 % !e Þð1 % 2!p Þx1 % ð1 þ oÞ!p g % ½ð1 % !p Þfð1 % oÞ % 2oð1 % !e Þ!p x3 g þ of1 % ð1 % !e Þx1 g'c
ð1 % oÞ½1 þ of!e % ð1 % !e Þðx1 % x2 Þg'ðB:7Þ

When x2 ¼ 0,

~ 3%W
~ 1 ¼ %obx3 f%o!e þ ð1 % oÞ!p g þ fo!e þ ð1 % o þ 2ox3 Þ!p gc þ Oð!2 Þ.
Wð1 % oÞð1 % ox1 Þ

(B.8)

~ 3%W
~ 1 ¼ oðobx3 þ cÞ!e þ Oð!2 Þ.
Weð1 % oÞð1 % ox1 Þ(B.9)

Without private reputation errors, Eq. (B.8) is rewritten as

This is always positive, hence DISC is favored on the ALLC–DISC edge. Next, consider when private reputation errors
exist. In this case the coexistence equilibrium R exists on the ALLC–DISC edge as in Fig. 2c if
$
%
b
1 1
1
4
þ
and a4o ða * !p =ð!e þ !p ÞÞ,(B.10)co a 1 % o=a

is satisfied. If not DISC is evolutionarily stable as in Fig. 1c as long as ob4c.
B.4. GBBB (shunning)
From Appendix A we obtain~ 1 ¼ ð1 % !e Þ ð1 % !e Þð1 % 2!p Þð1 % oÞobx3 % ½1 % oð1 % !e Þfx1 þ ð1 % !p Þx3 g'c ,W
ð1 % oÞ½1 % oð1 % !e Þfx1 þ ð1 % !p Þx3 g'~ 3 ¼ ð1 % !e Þ ð1 % !e Þð1 % !p Þð1 % 2!p Þð1 % oÞobx3 % ½1 % o % !p f1 % oð2 % ð1 % !e Þðx1 þ ð1 % !p Þx3 ÞÞg'c .
W
ð1 % oÞ½1 % oð1 % !e Þfx1 þ ð1 % !p Þx3 g'

ðB:11Þ

When x2 ¼ 0,

~ 3%W
~ 1 ¼ %!p ð1 % oÞobx3 þ fo!e þ ð1 % o þ ox3 Þ!p gc þ Oð!2 Þ.
Wð1 % oÞ2

Without private reputation errors Eq. (B.12) is rewritten as~ 3%W~ 1 ¼ o!e c þ Oð!2 Þ.
Weð1 % oÞ2(B.12)(B.13)

This is always positive, hence DISC is always favored on the ALLC–DISC edge. With private reputation errors, if
b 1
1
4 þ
;
c o að1 % oÞða * !p =ð!e þ !p ÞÞ,(B.14)

is satisfied then the coexistence equilibrium R emerges on the ALLC–DISC edge as in Fig. 2d. If not, DISC isevolutionarily stable as in Fig. 1d as long as ob4c.
B.5. Other 12 norms
From Appendix A, we can calculate payoffs of three strategies under each of other 12 norms, see Table 2. In Table 2, we~ 1 Þ and DISC ðW~ 3 Þ in the absence of any errors. We note that when errors do notshow normalized payoffs of ALLC ðWARTICLE IN PRESS530

H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531

Table 2
~ 3 for 12 norms other than four norms explained in the text
~ 1 and W
Normalized payoffs W
Norm

~1
W

~3
W

(1) GGGG(2) GGGB(3) GBGG(4) GBGB(5) BGGG(6) BGGB(7) BGBG(8) BGBB(9) BBGG(10) BBGB(11) BBBG(12) BBBB%c=ð1 % oÞ
%c=ð1 % oÞ
%c=ð1 % oÞ
%c=ð1 % oÞ%ððobx3 þ cÞ þ ocðx1 þ x3 ÞÞ=ð1 % oÞf1 þ oðx1 þ x3 Þg
ð%ðobx3 þ cÞf1 % oð1 % x1 Þg+oðobx3 % cÞð1 % x2 ÞÞ/ð1 % oÞf1 þ oðx1 % x2 Þg%c=ð1 % oÞ
ð%cf1 % oð1 % x1 Þg þ oðobx3 % cÞÞ/ðð1 % oÞð1 þ ox1 ÞÞ%ðobx3 þ cÞ=ð1 % oÞ%ððobx3 þ cÞ=ð1 % ox2 ÞÞ-ðocð1 % x2 ÞÞ=ðð1 % oÞð1 % ox2 ÞÞ%ðcð1 % ox1 Þ þ oðobx3 þ cÞÞ/ð1 % oÞf1 þ oðx2 þ x3 Þg%c=ð1 % oÞ

%c=ð1 % oÞ
%c=ð1 % oÞ
%c=ð1 % oÞ
%c=ð1 % oÞ%ðobx3 þ cÞ=ð1 % oÞf1 þ oðx1 þ x3 Þg%ððobx3 þ cÞf1 % oð1 % x1 ÞgÞ/ð1 % oÞf1 þ oðx1 % x2 Þg%c=ð1 % o2 Þ
%cf1 % oð1 % x1 Þg=ð1 % oÞð1 þ ox1 Þ%ðobx3 þ cÞ=ð1 % ox1 Þ=ð1 % oÞð1 þ ox3 Þ%ðobx3 þ cÞ=ð1 % ox2 Þ%ðcð1 % ox1 ÞÞ=ð1 % oÞf1 þ oðx2 þ x3 Þg%c

For the notation of norms, see Table 1 and Appendix B.

exist, evolutionary dynamics of three strategies are structurally stable for each norm. This means that the introduction ofsmall amount of errors do not change the dynamics qualitatively. Hence, it is enough to analyse the error-free case.
We will prove below that ALLD is a unique global attractor for norms (1)–(12) in Table 2. For norms (1)–(5), (7) and(9)–(12), it is easy to see that W 2 is always the largest among Wi (i ¼ 1, 2, 3), so ALLD is a unique global attractor of the
dynamics. For norms (6) and (8), if x3 Xc=ob then W3 is the smallest of the three, so x3 decreases such that it becomes
below c=ob. This suggests that the region defined as {ðx1 ; x2 ; x3 Þjx1 þ x2 þ x3 ¼ 1, x3 oc=ob, xi X0} is positively invariant
under the replicator dynamics. In this region, W2 is always largest of the three, so ALLD is a unique global attractor of the
dynamics. This ends the proof.

Appendix C. Payoff of DISC’ players
Consider DISC’ players. They adopt DISC strategy as normal DISC players do. They also communicate with others andtry to correct their opinion if it is different from the majority. Let !0p be the probability that a DISC’ player has an incorrect
opinion on a focal player.
We introduce a considerably small amount of DISC’ players into the population and calculate the difference in payofffrom normal DISC players. Since DISC’ players are rare in the population they do not affect the payoff of the otherstrategies.
We need to conduct almost the same calculation as in Appendix A. Let W4 be DISC’ players’
total payoff over rounds.
P
t%1
As in Appendix A, it is given by the weighted sum of payoff at the tth round P4(t) as W 4 ¼ 1
P4 ðtÞ. Similarly to Eq.
t¼1 o(A.2), P4(t) is given as
P4 ðtÞ ¼ ð1 % !e Þ½fx1 þ fð1 % !p ÞG4 ðt % 1Þ þ !p B4 ðt % 1Þgx3 gb % fð1 % !0p ÞGðt % 1Þ þ !0p Bðt % 1Þgc'.

(C.1)

Here G4(t) and B4(t) represent the fraction of good or bad players among DISC’ strategists at the end of round t. As in
Eq. (A.5) the recursion on G4(t) is given byð G1 ðtÞ

G2 ðtÞ

G3 ðtÞ

G4 ðtÞ ÞT ¼ M½Gðt % 1Þ'D.

(C.2)

Here M½Gðt % 1Þ' ¼ ðmij Þ is the 4 + 4 matrix. mij’s (i ¼ 1, 2, 3) are defined as in Appendix A. m4j is the same as m3j exceptthat ep is substituted by e0 p. The 4 + 1 matrix D is given by Eq. (A.4).
From these calculations, we obtain the following results. For simple-standing (GGBG, see Table 1), we have
W 4 % W 3 ) ð!p % !0p Þ

obx3 % cð1 % ox2 Þ.
ð1 % oÞð1 þ ox2 Þ(C.3)

For Kandori (GBBG, see Table 1) we have&
' obx f1 % oðx % x Þg % cf1 % oðx þ x Þg
3
1
2
1
2
W 4 % W 3 ) !p % !0p.
ð1 % oÞf1 % oðx1 % x2 Þg(C.4)

ARTICLE IN PRESS
H. Ohtsuki, Y. Iwasa / Journal of Theoretical Biology 244 (2007) 518–531

531

For shunning (GBBB, see Table 1) we have
W 4 % W 3 ) ð!p % !0p Þ

obx3 ð1 % oÞ % cf1 % oð1 þ x2 Þg,
ð1 % oÞf1 % oð1 % x2 Þg(C.5)

By substituting ðx1 ; x2 ; x3 Þ ¼ ð1 % x(3 ; 0; x(3 Þ in Eqs. (C.3)–(C.5) we obtain Eq. (8) in the main text.
References
Alexander, R.D., 1987. The Biology of Moral Systems. Aldine de Gruyter, New York.
Bolton, G., Katok, E., Ockenfels, A., 2005. A cooperation among strangers with limited information about reputation. J. Public. Econ. 89, 1457–1468.
Brandt, H., Sigmund, K., 2004. The logic of reprobation: assessment and action rules for indirect reciprocity. J. Theor. Biol. 231, 475–486.
Brandt, H., Sigmund, K., 2005. Indirect reciprocity, image scoring, and moral hazard. Proc. Natl Acad. Sci. USA 102, 2666–2670.
Brandt, H., Sigmund, K., 2006. The good, the bad and the discriminator—errors in direct and indirect reciprocity. J. Theor. Biol. 239, 183–194.
Fehr, E., 2004. Don’t lose your reputation. Nature 432, 449–450.
Fehr, E., Fischbacher, U., 2003. The nature of human altruism. Nature 425, 785–791.
Fishman, M.A., 2003. Indirect reciprocity among imperfect individuals. J. Theor. Biol. 225, 285–292.
Hofbauer, J., Sigmund, K., 1998. Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge.
Kandori, M., 1992. Social norms and community enforcement. Rev. Econ. Stud. 59, 63–80.
Leimar, O., Hammerstein, P., 2001. Evolution of cooperation through indirect reciprocation. Proc. R. Soc. London B 268, 745–753.
Lotem, A., Fishman, M.A., Stone, L., 1999. Evolution of cooperation between individuals. Nature 400, 226–227.
Milinski, M., Semmann, D., Bakker, T.C.M., Krambeck, H.J., 2001. Cooperation through indirect reciprocity: image scoring or standing strategy? Proc.
R. Soc. London B 268, 2495–2501.
Milinski, M., Semmann, D., Krambeck, H.J., Marotzke, J., 2006. Stabilizing the Earth’s climate is not a losing game: supporting evidence from public
goods experiments. Proc. Natl Acad. Sci. USA 103, 3994–3998.
Nakamaru, M., Kawata, M., 2004. Evolution of rumors that discriminate lying defectors. Evol. Ecol. Res. 6, 261–283.
Nowak, M.A., Sigmund, K., 1998a. Evolution of indirect reciprocity by image scoring. Nature 393, 573–577.
Nowak, M.A., Sigmund, K., 1998b. The dynamics of indirect reciprocity. J. Theor. Biol. 194, 561–574.
Nowak, M.A., Sigmund, K., 2005. Evolution of indirect reciprocity. Nature 437, 1291–1298.
Ohtsuki, H., 2004. Reactive strategies in indirect reciprocity. J. Theor. Biol. 227, 299–314.
Ohtsuki, H., Iwasa, Y., 2004. How should we define goodness? Reputation dynamics in indirect reciprocity. J. Theor. Biol. 231, 107–120.
Ohtsuki, H., Iwasa, Y., 2006. The leading eight: social norms that can maintain cooperation by indirect reciprocity. J. Theor. Biol. 239, 435–444.
Panchanathan, K., Boyd, R., 2003. A tale of two defectors: the importance 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, 449–450.
Sugden, R., 1986. The Economics of Rights, Cooperation and Welfare. Blackwell, Oxford.
Takagi, E., 1996. The generalized exchange perspective of the evolution 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 andecological foundations of the mind, Hokkaido University, Japan, Working Paper Series No. 29.
Taylor, P.D., Jonker, L.B., 1978. Evolutionary stable strategies and game dynamics. Math. Biosci. 40, 145–156.
Wedekind, C., Braithwaite, V.A., 2002. The long-term benefits of human generosity in indirect reciprocity. Curr. Biol. 12, 1012–1015.
Wedekind, C., Milinski, M., 2000. Cooperation through image scoring in humans. Science 288, 850–852.