Exact Cluster Dynamics of Indirect Reciprocity in Complete Graphs
Minwoo Bae Takashi Shimada Seung Ki Baek



Department of Physics, Pukyong National University, Busan 48513, Korea

[]shimada@sys.t.u-tokyo.ac.jp
Department of Systems Innovation, Graduate School of Engineering, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan

[]seungki@pknu.ac.kr
Department of Scientific Computing, Pukyong National University, Busan 48513, Korea


Heider's balance theory emphasizes cognitive consistency in assessing others, as is expressed by “The enemy of my enemy is my friend.”
At the same time, the theory of indirect reciprocity provides us with a dynamical framework to study how to assess others based on their actions as well as how to act toward them based on the assessments. Well-known are the `leading eight' from L1 to L8, the eight norms for assessment and action to foster cooperation in social dilemmas while resisting the invasion of mutant norms prescribing alternative actions.
In this work, we begin by showing that balance is equivalent to stationarity of dynamics only for L4 and L6 (Stern Judging) among the leading eight. Stern Judging reflects an intuitive idea that good merits reward whereas evil warrants punishment.
By analyzing the dynamics of Stern Judging in complete graphs, we prove that this norm almost always segregates the graph into two mutually hostile groups as the graph size grows.
We then compare L4 with Stern Judging: The only difference of L4 is that a good player's cooperative action toward a bad one is regarded as good. This subtle difference transforms large populations governed by L4 to a “paradise” where cooperation prevails and positive assessments abound.
Our study thus helps us understand the relationship between individual norms and their emergent consequences at a population level, shedding light on the nuanced interplay between cognitive consistency and segregation dynamics.


Exact Cluster Dynamics of Indirect Reciprocity in Complete Graphs
    Seung Ki Baek
    April 29, 2024
=================================================================





§ INTRODUCTION




Heider's balance theory is a minimal model of consistency in human relations <cit.>. Because of its mathematical simplicity, the balance theory has opened up an interdisciplinary field between psychology and graph theory <cit.>. Between each given pair of individuals, the theory assumes a binary relation, which can be represented either by +1 if positive (e.g., they like each other) or by -1 if negative (e.g., they dislike each other).
The basic unit of the balance theory is a triangle as shown in Fig. <ref>, where vertices and edges represent individuals and their relations, respectively. If the triangle contains an even number of negative edges, it is balanced because everyone can clearly distinguish friend and foe: In Fig. <ref>(a), everyone is positively related to each other. In Fig. <ref>(b), the relation between i and j is positive, which is consistent with the fact that they both have negative relations with k. Mathematically speaking, the direct edge between i and j is represented by σ_ij = +1, which is exactly identical to the product of σ_ik = -1 and σ_kj = -1, where σ_xy = σ_yx for every possible pair of x and y in an undirected graph. The product σ_ikσ_kj is called the sign of this path from i to j via k. In general, for any graph with positive and negative edges, we say that it is balanced if and only if all paths joining the same pair of vertices have the same sign. By contrast, in the other two cases of Fig. <ref>(c) and (d), one feels `tension' because, e.g., one has a positive relation with his or her friend's enemy so that two paths connecting the same pair of individuals have different signs.

Of particular importance is the structure theorem <cit.>, which states that a graph is balanced if and only if the graph is separated into two clusters in such a way that every edge inside a cluster is positive whereas any edge between the clusters is negative. Let us define the size of a cluster as the number of vertices inside it. In a balanced configuration, the size of one of the clusters can be zero, in which case, all the edges are positive, and such a configuration is called paradise <cit.>.
The idea behind this structure theorem is that friends and foes are defined without ambiguity from an arbitrary individual's perspective in a balanced configuration: Those with positive relations to the focal individual constitute one cluster, and those with negative relations constitute the other.

The balance theory is static, and one could naturally ask which dynamics leads to a balanced configuration. The first attempt was a discrete-time model, in which a randomly chosen edge is flipped to achieve more balance, either locally or globally <cit.>.
One version of this discrete-time model corresponds to an Ising-spin system with the following Hamiltonian:

    H = -∑_< ijk >σ_ijσ_jkσ_ki,

where the summation runs over all triangles of the underlying graph <cit.>. By making thermal contact with a heat bath at temperature T, this Hamiltonian system undergoes stochastic time evolution, which was expected to guide the system to a balanced configuration as T → 0.
However, it has turned out that such local dynamics also generates infinitely many stable yet unbalanced configurations <cit.>. An alternative, continuous-time model with real-valued σ_ij's has thus been studied to prove that a balanced configuration is almost always reached from a random initial configuration in finite time, if a large number of vertices are connected by a complete graph <cit.>.

In this work, we study dynamics of indirect reciprocity as another way to approach structural balance. An individual's deed to another can be reciprocated indirectly from a third-party observer, and this mechanism is regarded as a powerful mechanism of establishing cooperation among individuals <cit.>.
The mechanism of indirect reciprocity typically involves three persons: An actor, also called a donor, and a recipient of the donation from the donor, and an observer watching those two persons and updating his or her own assessment of the donor. The donor may either cooperate by choosing donation or defect by doing nothing to the recipient. Note that this dynamics has directionality because σ_ij is not necessarily the same as σ_ji.
An early issue of debate in indirect reciprocity was whether a first-order assessment rule, relying only on the donor's action, is sufficient for stabilizing the paradise <cit.>, and the answer, at least in theory, is that the observer should use information of the recipient as well, in such a way that refusing to cooperate to a bad recipient does not damage the donor's image to the observer <cit.>.

Among such good higher-order assessment rules, which are now called `leading eight' and shown in Table <ref>, a particularly well-known example is what we will call L6 throughout this work (also known as `Stern Judging' or `Kandori') <cit.>. According to this simple and intuitive norm, a donor must donate only when he or she regards the recipient as good, and whether the donor's cooperation looks good to an observer heavily relies on the recipient's image to the observer.
The assessment rule of L6 can thus be algebraically expressed as <cit.>

    σ_od'=σ_orσ_dr,

where the prime means an updated value at the next time step, and the subscripts d, r, and o mean the donor, recipient, and observer, respectively.
For example, as represented by σ_or on the right-hand side, the observer's assessment of the donor at the next time step will indeed be affected by how the observer thinks about the recipient.
The squared difference between the current and next values of σ_od is

    (σ_od - σ_od' )^2 = (σ_od - σ_orσ_dr)^2 =
        2 - 2σ_odσ_orσ_dr,

where we have used (± 1)^2 = 1. Therefore, we will find σ_od' = σ_od if and only if σ_odσ_orσ_dr = 1, and this condition is certainly reminiscent of the Hamiltonian approach in Eq. (<ref>), although we will later point out its important difference from Eq. (<ref>).
L6 has its own weaknesses: Once it deviates from the paradise, L6 fails to return in the presence of noisy and private assessment <cit.>. It is rather known that L6 would divide a fully connected society into two mutually hostile clusters <cit.>, consistently with the structure theorem of the balance theory.
On the other hand, if the society uses L4, which is almost identical to L6, our numerical simulations show that it easily reaches the paradise. The only difference of L4 from L6 is that a good donor's cooperation with a bad recipient does not damage the donor's image from the observer's viewpoint. The aim of this paper is to clarify the reason of such distinct outcomes, i.e., segregation and paradise.

We investigate the mechanism of segregation by using an exact analysis of the Markov dynamics in complete graphs. The analysis reveals that segregation of L6 is actually driven by entropy, whereas L4 introduces a bias toward the paradise, which becomes stronger as the system size increases. Considering such a small difference between the two norms, we propose that L4 can be the most promising remedy for segregation induced by the intuitive rules of L6.





§ MODEL


Let us consider a directed graph with a set of vertices and a set of edges, which are denoted as V and E, respectively. Every vertex has an agent, who has an opinion about each of the neighbors that are connected to the focal vertex by edges. For any random pair of two vertices, they are connected with probability p, and the connection structure is fixed during the dynamical evolution of edges. The structure is called a complete graph when p=1, which we mainly consider in this work.
The cardinality of V is the total number of vertices, or the population size, and we denote it as N.
Opinions take discrete values, so σ_ij=+1 if i regards j as good, and -1 otherwise.
Everyone shares an assessment rule and an action rule in common.

    
  * A donor d is randomly chosen from V, and a recipient r is chosen among d's neighbors including d itself.
    
  * The donor d chooses whether to cooperate toward the recipient r according to the action rule.
    
  * All neighbors of both d and r observe d's action toward r. The set of observers includes d and r as well. Each and every observer o's opinion about d, denoted as σ_od, is updated to σ_od' as prescribed by the given assessment rule with probability 1-ϵ, and to -σ_od' with probability ϵ≪ 1, where ϵ is the probability of assessment error. We assume that actions are implemented without error.




§ RESULTS




 §.§ Balance and stationarity


We begin by checking whether the balance condition is equivalent to stationarity for each of the leading eight. This analysis is necessary because it relates the balance condition, a static property, to stationarity, which is a dynamical consequence. The conclusion of this subsection is the following: Among the leading eight (Table <ref>), the balance condition can be identified with stationarity only for L6 and L4, the former of which has been analyzed in detail by one of us previously in the context of balance and group formation <cit.>.

Regarding L6, we may rewrite its rule [Eq. (<ref>)] as

    σ_od'=σ_orσ_dr=σ_odσ_orσ_drσ_od=Φ_odrσ_od,

by using σ_od^2=1 and defining a local order parameter for triad balance,

    Φ_odr≡σ_odσ_orσ_dr.

The stationarity condition requires σ_od' = Φ_odrσ_od = σ_od
for an arbitrary triangle of o, d, and r. We thus conclude that stationarity is equivalent to the balance condition that Φ_odr=1 <cit.>.

As for L4, recall that its only difference from L6 is that a good donor's cooperation toward a bad recipient is regarded as good (Table <ref>). However, the difference will never be observed in a balanced configuration if everyone follows the L4 rule, which prescribes a good donor to defect against a bad recipient. This indicates that balance implies stationarity in L4. The proof of the converse statement on L4, as well as discussions on the other norms of the leading eight, can be found in Appendix <ref>.



 §.§ Dynamics on complete graphs


Let us imagine all the possible 2^N× N edge configurations on a complete graph, only one of which is the paradise. The question is whether the paradise will occupy 100% of the stationary probability in the limit of ϵ→ 0.
One way to answer this question is to count the order of ϵ <cit.>. That is, in the order of ϵ^0, we consider only the transitions permitted by L6 or L4, according to which the dynamics ends up with one of balanced configurations.
These sinks have no connections among themselves because balance means stationarity. Whether the probability flows will converge to the paradise is undecidable at this level of description. We then add links with probabilities of O(ϵ^1) by considering transitions mediated by a single error. If the paradise appears as a global sink at this level of description, it will occupy 100% in the limit of ϵ→ 0. Or, if there is an outgoing flow of O(ϵ) from the paradise, we conclude that it cannot occupy the whole stationary probability. If it is still undecidable, we add links of O(ϵ^2) and repeat the analysis. For our current purpose, the description of O(ϵ) is sufficient because a single error can change one balanced configuration to another as will be detailed below.



  §.§.§ Path-reversal symmetry in L6


To investigate the cluster dynamics under L6, we begin by showing the following: At a balanced configuration with two clusters, a single error can move at most a vertex from a cluster to the other cluster.
Let us start with a balanced configuration dividing V into two partitions, i.e.,

    P_balance = {{v_1, …, v_n}, {v_n+1, …, v_N}},

where 1≤ n<N. The paradise is represented by a trivial partition

    P_paradise = {V},

which we regard as a special case of P_balance with n=N by a slight abuse of notation to allow a partition to be empty.
Without loss of generality, we assume that v_n has committed an assessment error, after which all time evolution strictly follows the common social norm L6.
To be more specific, the focal individual v_n commits an error either by assessing its friend as bad or by assessing its enemy as good, so V can be divided into the following five partitions, some of which may be empty (Fig. <ref>):


    P_error = {{…}_π_1, {…}_π_2, {v_n}, {…}_π_3, {…}_π_4},

where π_1 ∪π_2 = {v_1, …, v_n-1} and π_3 ∪π_4 = {v_n+1, …, v_N}. The members of π_1 and π_2 like v_n, but v_n likes π_1 and dislikes π_2. The members of π_3 and π_4 dislike v_n, but v_n likes π_3 and dislikes π_4.
All members in each partition are the same in relation to those in another partition, so a partition can behave like a single vertex.
The dynamics can also make the elements of π_1 go over to π_2 or vice versa, and the same applies to π_3 and π_4, but v_n remains alone in its own partition because the dynamics has no more erroneous assessment.
The important point is that the five-vertex picture in Eq. (<ref>) will remain valid on the understanding that some of the partitions may be empty.
When we exhaustively trace the time evolution of the corresponding five-vertex configurations by applying L6, the final outcome is always either the original balanced configuration P_balance [Eq. (<ref>)] or a new balanced one represented by

    P'_balance = {{v_1, …, v_n-1}, {v_n, …, v_N}},

where v_n now belongs to the latter partition.
This completes the proof that an error can cause at most a single vertex to change its membership under L6.

One of our main findings is that every balanced configuration occupies equal stationary probability B^-1 in the limit of ϵ→ 0, where B = 2^N-1 is the number of balanced configurations (Appendix <ref>).
To prove this statement, we start from the rule of L6 [Eq. (<ref>)], which we write here once again for the sake of convenience:

    σ_od'=σ_orσ_dr.

Let us assume that each player's self-image has converged to +1 because σ_dd' = σ_dr^2 = +1. We may expect this convergence within O(1) Monte Carlo steps <cit.>. In addition, our analysis assumes that no error occurs in self-images.
Our proof is based on the following property of L6: For any transition sequence of configurations permitted by the above rule of L6, if we choose an arbitrary vertex and flip all its edges, except the self-loop, we will get another valid sequence of configurations permitted by L6.
It can be seen directly from the L6 rule itself: When the chosen vertex is a donor, flipping σ_od' and σ_dr makes the equality hold, while leaving σ_dd'=+1 unchanged. When the chosen vertex is a recipient, it assesses the donor with σ_rd' = σ_dr, whose equality is unaffected by flipping both the sides. Finally, when the chosen vertex is an observer, flipping σ_od' and σ_or again satisfies the above rule.

In Fig. <ref>(a), we depict an error-induced sequence from the paradise to another balanced configuration where an individual conflicts with all the rest. Now, by choosing the vertex at the lower left corner and flipping all its edges, except its self-loop, we obtain Fig. <ref>(b). The point is that the sequence in Fig. <ref>(b) shows valid transitions back to the paradise, with exactly the same probability as its counterpart in Fig. <ref>(a).
In general, for every sequence of transition from Eq. (<ref>) to Eq. (<ref>), the transformation applied to v_n generates the corresponding sequence in the opposite direction with equal probability.
In addition, as proved above, no more than a single vertex can change its cluster in this O(ϵ) description, which precludes the existence of any indirect transition paths connecting Eq. (<ref>) and Eq. (<ref>) via a third balanced configuration.
Therefore, the total transition probability must be the same in either direction, satisfying Kolmogorov's criterion. The resulting detailed-balance condition equalizes the stationary probabilities of Eq. (<ref>) and Eq. (<ref>).
In other words, the paradise has the same stationary probability as any balanced configuration of two clusters with sizes 1 and N-1, respectively, so we have

    ρ_st[ {V}] = ρ_st[ {{v}, V - {v}}],

where ρ_st means stationary probability, and v is an arbitrary element of V.
By the same token, we also see that

    ρ_st[ {{v}, V - {v}}]
    = ρ_st[ {{v, v'}, V - {v, v'}}],

where v and v' are two arbitrary distinct elements of V. Extending this argument one by one, we can conclude that every balanced configuration has the same stationary probability, which equals B^-1 in the limit of ϵ→ 0. The transitions among balanced configurations are schematically drawn in Fig. <ref>(a).



  §.§.§ Probability flows under L4




According to our exhaustive enumeration, not only P_balance and P'_balance [Eqs. (<ref>) and (<ref>)] but also P_paradise={V} becomes accessible from P_error because L4 has α_GCB = G [Eq. (<ref>)]. As a consequence, single-error transitions among balanced configurations under L4 are depicted as in Fig. <ref>(b).
The important point is the existence of the one-way transition to the paradise, when both of the clusters have more than one vertex, as represented by {{v,v'}, V-{v,v'}} or {{v,v',v”}, V-{v,v',v”}} in Fig. <ref>. Such balanced configurations should have only negligible stationary probabilities because of the one-way transition.
Still, the stationary probability of the paradise does not necessarily approach 100% even with small ϵ because the system may go back and forth between the paradise and {{v}, V-{v}}. For example, if N=4, our numerical estimate of ρ_st[ {V}] is only 61% when ϵ = 10^-4, which is consistent with the order-counting argument <cit.>.



However, the transition probability from {{v}, V-{v}} to the paradise becomes far greater than the opposite one as N grows. Figure <ref>(a) provides a zoomed-in view for the dashed box of Fig. <ref>, where the nodes denoted by 0 and N correspond to the paradise and {{v}, V-{v}}, respectively. Each node represents a set of edge configurations that are identical up to permutation of vertices.
Figure <ref>(b) shows an example of N=6 for the sake of concreteness.
The absorption probability into {{v}, V-{v}} from configuration j is denoted by q_j, which means that q_0=0 and q_N=1 by definition. The symbols attached to the arrows in Fig. <ref>(a) are transition probabilities.
For example, the configuration 1 means that a vertex v is disliked by all others whereas it still likes them. The next one denoted by 2 means that v now dislikes one of them. The transition from 1 to 2 occurs with probability P_1^+ = 1/N × (N-1)/N because v must be the recipient with probability 1/N while anyone else can be chosen as the donor with probability (N-1)/N. It is straightforward to see that P_j^+ = (1/N) × (N-j)/N. The reverse transition from 2 to 1 happens with probability P_2^- = (1/N) × (N-2)/N because the one who v dislikes (1 out of N) must donate someone who v still likes (N-2 out of N). In general, we have P_j^- = (N-j)/N × (j-1)/N. The exception is P_1^-, whose probability equals P_2^- = (N-1)/N × (1/N) because the transition happens when v donates to anyone else. General expressions for the transition probabilities μ_j, ν_j, and S_j are given in Appendix <ref>.

If an assessment error occurs at the paradise, the starting point of the transition dynamics will be the configuration denoted by 1' [see Fig. <ref>(b)]. The dynamics will end at {{v}, V-{v}} with probability q_1'. Likewise, if an error occurs at {{v}, V-{v}} by assessing an enemy as good, the starting point will be the node denoted by N-1. The dynamics ends either at the paradise or at {{v}, V-{v}}, so if we start from the one denoted by N-1, the probability of absorption into the paradise must be 1-q_N-1.
We wish to compare q_1' with 1-q_N-1 to see the asymmetry in the probability flows:
The random walk problem with two absorbing barriers as defined by Fig. <ref> can be solved by recurrence formulas, which we provide in Appendix <ref>.
The solution shows that (1-q_N-1) / q_1' is a rapidly increasing function of N, which outputs 15, 82, and 517 for N=4, 5, and 6, respectively.
It is instructive to consider the random walk only among the upper nodes without primes to get a lower bound of such asymmetry because the existence of the lower nodes, labeled with primes, should bias the net probability flow even more drastically toward the paradise.
Although q_1' does not appear in this simplified problem, one can readily see that it is proportional to q_1 from Appendix <ref>.
The absorption probability of a one-dimensional random walker with position-dependent transition probabilities is a well-known problem in evolutionary game theory <cit.>:
If we define

    γ_j ≡ P_j^- / P_j^+ =
    {[        1  for j=1;      j-1 for j>1, ].

it is straightforward to find that


    q_1    = [1+∑_i=1^N-1( ∏_j=1^i γ_j )]^-1
    
    q_k+1   = [ 1+∑_i=1^k( ∏_j=1^i γ_j ) ] q_1,


where k=1,…,N-2. One of its direct consequences is

    1-q_N-1/q_1 = ∏_j=1^N-1γ_j = (N-2)!,

which confirms that the net probability flow becomes more and more biased toward the paradise as N increases.
One could point out that we have not taken into account the existence of other paths from {{v}, V-{v}} to the paradise, e.g., through an error inside the larger cluster, but they can only contribute positively to the bias.



§ DISCUSSION




Our first main finding is that every balanced configuration occupies equal stationary probability under the rule of L6. We have explicitly verified it for small values of N by using the power method (not shown) and proved it for general N, as given above, in the limit of small ϵ. Then, the segregation phenomenon induced by L6, which has been observed numerically <cit.>, must be driven by entropy in the sense that the number of segregated balanced configurations greatly exceeds the unique possibility of the paradise as N grows. The most probable case would be such that two clusters are of roughly equal sizes as in the binomial distribution.
We can demonstrate it by using Monte Carlo simulations [Fig. <ref>(a)], according to which the size difference between two clusters, divided by N, decreases as N^-1/2.
Note the different behavior of L4, according to which the paradise is easily accessible when N ≳ O(10) [Fig. <ref>(b)].
This prediction is also partially supported by a recent analytic study <cit.>, showing that each individual is expected to receive good assessments from a half of the population, although it does not distinguish a clustered configuration from a randomly mixed one.

The uniform stationary probability among balanced configurations is contrasted with a result from the Hamiltonian in Eq. (<ref>) because the paradise is locally stable in the Hamiltonian model <cit.>. Let us make sense of this difference: To define the Hamiltonian, every pair of vertices must be in a reciprocal relation, i.e., either mutually good or mutually bad, but it is approximately true in our setting as well because the convergence of σ_ijσ_ji→ O(1) is a relatively fast process <cit.>.
We have to look at the zero-temperature Hamiltonian dynamics, derived from Eq. (<ref>) as

    σ_ij' = sgn( ∑_k σ_ikσ_kj),

where the summation runs over the common neighbors of i and j except themselves.
Referring to those common neighbors is an important ingredient to ensure the local stability of the paradise because the peer pressure can correct an assessment error. In a sense, the Hamiltonian setting introduces surface tension in such a way that the Ising model is contrasted with the voter model <cit.>.
The difference of Eq. (<ref>) from the L6 rule [Eq. (<ref>)] is evident in a large complete graph, but it vanishes if the underlying structure allows every pair of vertices to have only one common neighbor. The same applies even to the case of two common neighbors, if we interpret sgn(0) as ± 1 with equal probabilities.



From the lack of directional preference in the transition among balanced configurations, we believe that the system governed by L6 with assessment error would be in a disordered phase until reaching a balanced configuration. One possible mechanism to hinder a balanced configuration could be quenched random removal of edges, which corresponds to the case of p<1 in our model (see Sec. <ref>). When p>O(N^-1/2) and 1-p > O(N^-1), the time to reach an absorbing state increases exponentially as N grows <cit.>, and this may also be a characteristic of a disordered phase.
To support this idea, let us consider a sparse structure as depicted on the left in Fig. <ref>(a). Each edge is shared by two triangles, so we expect that it can be studied by using the Hamiltonian approach as an approximation. Considering that our σ_ij's are defined on edges, whereas spin variables are usually defined on vertices, we take the line graph of the original structure, which turns out to be the Husimi tree. The three-spin interaction Hamiltonian model on the Husimi tree is exactly solved <cit.>, and the solution tells us that it is in a disordered phase. We have summarized the solution in Appendix <ref> for the sake of completeness.
Another sparse structure that can be considered is the triangular lattice: In a Monte Carlo study, the Hamiltonian model on the triangular lattice has been reported to be disordered <cit.>. Its line graph is the kagome lattice [Fig. <ref>(b)], on which the exact solution of the three-spin Hamiltonian model again confirms that it is disordered <cit.>. All these observations indicate that a sparse structure would result in a disordered phase.



§ SUMMARY

In summary, we have analyzed cluster dynamics governed by L6 and L4, which becomes exact in the small-ϵ limit. We have explained why we focus on L6 and L4 among the leading eight by showing the equivalence between balance and stationarity. The dynamics of L6 has been studied by one of us <cit.>, and the present work concludes that the segregation induced by L6 is a purely entropy-driven phenomenon.

This work has thus demonstrated the possibility of exact knowledge on cluster dynamics in this interdisciplinary field of social psychology, graph theory, and evolutionary game theory.
It is worth pointing out that L6 is a remarkably simple and intuitive norm as indicated by its nickname `Stern Judging': It assesses cooperation (defection) toward a good person as good (bad), and cooperation (defection) toward a bad person as bad (good). It thus prescribes cooperation toward a good person and defection toward a bad person. Despite all its good properties, L6 divides a fully connected society into two mutually hostile clusters which are of roughly equal sizes.
The segregation might seem to be an ordered configuration compared to a random one, but the dominant factor behind it turns out to be entropy, and who belongs to which side is only a matter of chance.
We propose L4 as a remedy for those problems: This norm leads a sufficiently large society of N ≳ O(10) to the paradise just by changing the assessment of a good person's cooperation toward a bad person. The change is so small that L4 still prescribes a good person to defect against the bad just as L6 does, and the defection would also be assessed as good.
Furthermore, because of the clear bias toward the paradise, the system would not suffer long from disorder.

From a broader perspective, the precise understanding of segregation on fully connected graphs may give us theoretical insights into the recent trend of increasing political polarization in our hyper-connected society, as well as how to mitigate the trend with a minimal change in our judging behavior. Considering that the basic dynamics of a social norm would be preserved in more realistic acquaintance network structure <cit.>, we expect that our findings should also be relevant to real social phenomena.


We gratefully acknowledge helpful comments from Yohsuke Murase.
M.B. and S.K.B. acknowledge support by Basic Science Research Program through the
National Research Foundation of Korea (NRF) funded by the Ministry of Education
(NRF-2020R1I1A2071670).
We appreciate the APCTP for its hospitality during the completion of this work.






§ BALANCE AND STATIONARITY





 §.§ L6 and L4


We may rewrite Eq. (<ref>) as

    σ_od'=σ_orσ_dr=σ_odσ_orσ_drσ_od=Φ_odrσ_od,

by using σ_od^2=1 and defining a local order parameter for triad balance,

    Φ_odr≡σ_odσ_orσ_dr.

The stationarity condition requires σ_od' = Φ_odrσ_od = σ_od
for an arbitrary triangle of o, d, and r. We thus conclude that stationarity is equivalent to the balance condition that Φ_odr=1 <cit.>.

The same statement holds true for L4. The assessment rule of L4 can be written as follows <cit.>:

    σ_od'=1/4(-σ_or+3σ_drσ_or+σ_dr+σ_drσ_od-σ_orσ_od+1+σ_od-σ_drσ_orσ_od).

If the balance condition is met, we have Φ_odr=σ_odσ_orσ_dr=1. It automatically means
that


    σ_od   = σ_orσ_dr
    σ_or   = σ_odσ_dr
    σ_dr   = σ_odσ_or



because σ_od^2 = σ_or^2 = σ_dr^2 = 1. Plugging these relations into Eq. (<ref>), we obtain σ_od' = σ_od for an arbitrary od-pair, which means stationarity.
Now, we have to check if the converse is true. The stationarity condition requires
σ_od' = σ_od, which leads to

    σ_od = 1/4( -σ_or+3σ_drσ_or+σ_dr+σ_drσ_od-σ_orσ_od+1+σ_od-σ_drσ_orσ_od).

If we enumerate the eight possible cases of (σ_or, σ_dr, σ_od)=(± 1, ± 1, ± 1), Eq. (<ref>) is satisfied for (+1,+1,+1), (-1,-1,+1), (-1,+1,-1), (+1,-1,-1), and (-1,+1,+1), among which only the last one is unbalanced. To eliminate the last possibility, we note that stationarity is actually a stronger condition than Eq. (<ref>): For a given configuration to be stationary, it must be left invariant even if we sample the three players in different order, so that (σ_or, σ_dr, σ_od)=(+1,-1,+1) and (+1,+1,-1) must also satisfy Eq. (<ref>), while neither of them is in the list.
We thus exclude (-1,+1,+1) from consideration and conclude that the balance condition is equivalent to stationarity in L4.



 §.§ L3, L5, L7, and L8


By contrast, the balance condition is not equivalent to stationarity in L3 and L5. The assessment rule of L3 can be expressed as follows:

    σ_od'=1/2( 1+ σ_dr -σ_or +σ_orσ_dr).

Suppose that the balance condition Φ_odr=σ_odσ_orσ_dr=1 is met. By using Eq. (<ref>), we may rewrite Eq. (<ref>) as

    σ_od'=
        1/2[ 1+σ_od(1+σ_or-σ_dr) ].

If (σ_or, σ_dr, σ_od)=(-1,+1,-1), we see that stationarity is violated because σ_od' ≠σ_od.

Likewise, the assessment rule of L5 can be represented as follows:
 
    σ_od'=1/4( -σ_or+3σ_drσ_or+σ_odσ_or+1-σ_od+σ_drσ_odσ_or+σ_dr-σ_drσ_od)

Under the balance condition, together with Eq. (<ref>), we obtain

    σ_od'   =   1/4[-σ_or+3σ_drσ_or+σ_odσ_or+1-σ_od+1+σ_dr-σ_drσ_od] 
       =   1/4[-2σ_or+2σ_od+2σ_dr+2] = 1/2[1+σ_od-σ_or+σ_dr]

Again, stationarity is violated if (σ_or, σ_dr, σ_od)=(-1,+1,-1). The balance condition is not equivalent to stationarity.

For L7 and L8, it is straightforward to prove inequivalence between stationarity and the balance condition. The reason is that both assign bad reputation when a bad donor defects against a bad recipient. A triad of (σ_or, σ_dr, σ_od)=(-1,-1,-1) is thus an absorbing configuration, although it is not balanced.



 §.§ L1 and L2


For L1 and L2, a donor's action to a recipient cannot simply be identified with σ_dr from the beginning because a bad donor should cooperate to a bad recipient, i.e., β_BB=C
according to Table <ref>. For L1, a donor's action can be coded as

    β_d (σ_dd, σ_dr) = 1/2[ 1+σ_dd (σ_dr-1) + σ_dr],

and an observer's assessment rule is given as

    σ_od' = 1/4[ 1+σ_od+3β_d - σ_odβ_d + (1+σ_od)(β_d-1)σ_or].

When o=d, we obtain σ_dd'=+1 regardless of σ_dd and σ_dr, so each donor's self-evaluation quickly converges to +1. If σ_dd=+1 is plugged into Eq. (<ref>), we can identify β_d with σ_dr as in the previous cases.
Similarly, the assessment rule of L2 is

    σ_od' = 1/2β_d [ 1+σ_od (σ_or-1) + σ_or],

where β_d is given by Eq. (<ref>). By setting o=d, we once again see the convergence toward σ_dd'=+1 regardless of σ_dd and σ_dr, which allows us to identify β_d with σ_dr.

Therefore, for both L1 and L2, as soon as a donor's action is fully prescribed from σ_dr, we can apply the same argument as above to prove the inequivalence between stationarity and the balance condition: A bad donor's defection against a bad recipient is judged as bad by these norms, and this shows why (σ_or, σ_dr, σ_od)=(-1,-1,-1) is an unbalanced absorbing configuration.



§ NUMBER OF BALANCED STATES



Assume that we have a set of vertices V = {v_1, …, v_N}.
Thanks to the structure theorem, we just have to find the number of ways to divide those N elements into two clusters. If none of the clusters is empty, we can prove that the answer is

    W_N = 2^N-1-1

by using mathematical induction. First, if N=1, we have no way to divide it into two nonempty clusters, which means that W_1 = 0. Second, let us assume that

    W_k = 2^k-1-1

for some positive integer k. When a new vertex v_k+1 has appeared, we have two possibilities to divide the k+1 elements into two clusters. One is to add v_k+1 to one of the existing clusters. The other is to make a single-element cluster of v_k+1 and merge the existing clusters into one. In other words, we have

    W_k+1 = 2 W_k + 1.

Plugging Eq. (<ref>) here, we find that

    W_k+1 = 2 ( 2^k-1-1 ) +1 = 2^k-1,

which proves Eq. (<ref>) for general N. Note that W_N does not include the paradise. If we take it into account, the number of balanced states is B = 2^N-1 as mentioned in the main text.



§ RECURRENCE FORMULAS FOR L4



The absorption probabilities can be written as follows:


    q_j    = P_j^- q_j-1 + P_j^+ q_j+1 + μ_j q_(j-1)' + (1-P_j^- -P_j^+ -μ_j ) q_j
    
    q_k'   = S_k q_(k-1)' + ν_k q_k+1 + (1-S_k-ν_k) q_k',


where j=1,…,N-1 and k=1,…,N-2. By definition, we have q_0 ≡ 0 and q_N=1. It is also convenient to define q_0'≡ 0 and μ_1 ≡ 0. We may rewrite the above formulas as


    0    = P_j^- (q_j-1 - q_j) + P_j^+ (q_j+1 - q_j ) + μ_j (q_(j-1)' - q_j )
    
    q_k+1   = Γ_k ( q_k' - q_(k-1)') + q_k',


where Γ_k ≡ S_k / ν_k.
Let us define R_k ≡ q_k' - q_(k-1)'. Plugging Eq. (<ref>) into Eq. (<ref>) and rearranging the terms, we obtain

    P_j^-Γ_j-2R_j-2-[P_j^-(Γ_j-1+1)+P_j^+Γ_j-1+μ_jΓ_j-1]R_j-1
    
    +P_j^+(Γ_j +1)R_j=0.

The transition probabilities between unprimed nodes are given as follows:


    P_j^+    = (N-j/N) (1/N)
    
    P_j^-    = {[   (N-1/N) (1/N)         for j=1; (j-1/N) (N-j/N)        for j>1, ].


as explained in the main text. Recall that we are denoting by v the individual who has made an error.
The transition probability μ_j corresponds to the case of choosing  v as the donor (1 out of N) and someone else who v likes as the recipient (N-j out of N). Its counterpart ν_j is the probability of choosing v as the donor (1 out of N) and someone else who v dislikes as the recipient (j out of N). Finally, S_j is the probability of choosing someone who v dislikes as the donor (j out of N) and someone else who v likes (it can be v itself) as the recipient (N-j out of N). Therefore, their general expressions are


    μ_j    = (N-j/N) (1/N)
    ν_j   = (1/N) (j/N)
    
    S_j    = (j/N) (N-j/N),


which results in Γ_j = S_j / ν_j = N-j.

At j=1, Eq. (<ref>) reduces to

    P_1^- (-q_1) + P_1^+ ( Γ_1 q_1' + q_1' - q_1 ) = 0,

from which we obtain

    R_1 = q_1' = P_1^+ + P_1^-/P_1^+ (Γ_1+1) q_1 = 2/N q_1.

At j=2, Eq. (<ref>) takes the following form:

    P_2^- [q_1 - (Γ_1 +1 )R_1 ] + P_2^+ [ (Γ_2+1) R_2 - Γ_1 R_1] - μ_2 Γ_1 R_1 = 0,

from which we find

    R_2 = 5N-4/N(N-1)q_1.

From j=3 to N-2, we can find every R_j from the following recurrence formula:

    R_j = j-j^2+N+jN/N-j+1 R_j-1 - (j-1)(N-j+2)/N-j+1 R_j-2.

Although we have R_k's with k=1,…,N-2, the overall factor of q_1 remains unknown, and it has to be determined from Eq. (<ref>) at j=N-1:

    P_N-1^- [ Γ_N-3 R_N-3 - (1+Γ_N-2) R_N-2]
       +   P_N-1^+ [ (1-q_(N-2)')- Γ_N-2 R_N-2] - μ_N-1Γ_N-2 R_N-2 = 0,

where we have used q_N=1. By using the following identity,

    q_(N-2)' = (q_(N-2)' - q_(N-3)') +
    (q_(N-3)' - q_(N-4)') + … +
    (q_2' - q_1') +
    (q_1' - q_0')
    = ∑_k=1^N-2 R_k,

we can write Eq. (<ref>) in terms of R_j only:

    -(3N-6) R_N-3 + (3N-2) R_N-2 + ∑_k=1^N-2 R_k = 1,

from which we determine the value of q_1.



§ ISING MODEL ON THE HUSIMI TREE



Let us consider a system of Ising spins with the following Hamiltonian, defined on the Husimi tree:

    H=-J_3 ∑_⟨ i,j,k ⟩σ_i σ_j σ_k -J_2∑ _⟨ i,j ⟩σ_i σ_j - h∑_i σ_i,

where ⟨ i,j,k ⟩ denotes a triangle of i,j, and k, and ⟨ i.j ⟩ means the nearest neighbors.
Let us denote the spin at the center by σ_0, and define the following function:

    g_n(σ_0)    = ∑_{σ_1}exp[β̃(J_3∑_Δσ_0σ_1^(1)σ_1^(2) + J_2 (σ_0σ_1+ σ_0σ_2 +σ_1σ_2 ) + h ∑ _j=1,2σ_1^(j)) ]
       × [g_n-1(σ_1^(1))]^γ-1[g_n-1(σ_1^(2))]^γ-1,
 
where β̃≡ 1/(k_B T), and γ is the number of triangles at each vertex, which is two as depicted in Fig. <ref>(a). By using g_n(σ_0), we can write the partition function as follows:

    Z = ∑_σ_0exp(β̃hσ_0) [g_n(σ_0)]^γ

Now, by defining a ≡ e^2β̃h, b≡ e^2β̃J_2, and c≡ e^2β̃J_3, we obtain the following map in terms of z_n ≡ g_n(1)/g_n(-1) <cit.>:

    z_n=y(z_n-1),     y(z) = a^2b^2cz^2(γ-1)+2az^γ-1+c/a^2 z^2(γ-1) + 2acz^γ-1+b^2

The pure three-spin interaction Hamiltonian corresponds to a=b=1, in which case we have

    y(z) = cz^2+2z+c/z^2 + 2cz+1

by setting γ=2. By solving z=y(z), we obtain three fixed points, i.e., z=-1, z=1, and z=-c. However, z=1 is the only solution because z cannot be negative. In addition, by drawing the map, we can see that z=1 is a stable fixed point.
The local magnetization is expressed as <cit.>

    ⟨σ_0 ⟩ =az_n^γ -1/az_n^γ +1,

which is zero at a=z=1. However, the zero magnetization does not necessarily mean a disordered phase. To check the possibility of a phase transition, we will calculate the free energy. If it does not have a singularity at any finite temperature T, the system will always be in a disordered phase as in the high-temperature region. Let us rewrite the map by including both a and c as free parameters, while fixing b=1 and γ=2:

    y(z) = a^2cz^2+2az+c/a^2 z^2 + 2acz+1

By rearranging the terms of z=y(z), we obtain the following quadratic equation of a:

    (z^3-z^2c)a^2 + 2(z^2c-z)a +z-c=0,

which is solved by

    a = 1-cz±√(1-c^2-z^2 +c^2z^2)/z(z-c).

Noting that a≥ 1, c≥ 1, and z>0 by definition, the correct solution is given as follows:

    a(c,z) = 1-cz - √(1-c^2-z^2 +c^2z^2)/z(z-c),

where 1≤ z<c. This is a monotonically increasing function of z, and this property will be used later. The free-energy density can be written as follows <cit.>:

    β̃f = - 2/3J̃_̃3̃-h̃ - ∫^h̃_∞ [M(h̃')-1] dh̃',

where J̃_̃3̃≡β̃J_3 and h̃≡β̃h. The magnetic order parameter is denoted by M = -∂ f/ ∂ h, which we may identify with ⟨σ_0 ⟩ because of the translational symmetry of the lattice. The first two terms on the right-hand side is a constant of integration, which corresponds to the value in an ordered phase with M=1. We obtain h̃ from Eq. (<ref>) and differentiate it with respect to z for ∂h̃/∂ z. We thus calculate the free-energy density as

    β̃f = - 2/3J̃_̃3̃-h̃ - ∫^z_c [M(z')-1][∂h̃/∂ z]_z=z' dz',

which indeed has no singularity at finite temperature. The conclusion is that the system will always be in a disordered phase as in the high-temperature region.











37
fxundefined [1]
 ifx#1

fnum [1]
 #1firstoftwo
 secondoftwo
 
fx [1]
 #1firstoftwo
 secondoftwo
 





noop [0]secondoftwo

ref[1]@startlink#1@href
href[1]#1@endlink
anitize@url [0]`
12`$12`&12`#12`1̂2`_12`%12
startlink[1]
endlink[0]

rl [1]href #1












@bib@innerbibempty

[Heider(1946)]heider1946attitudes
  author author F. Heider, @noop  journal journal J.
  Psychol. volume 21, pages 107
  (year 1946)NoStop
[Harary(1953)]harary1953notion
  author author F. Harary, @noop  journal journal Mich.
  Math. J. volume 2, pages 143
  (year 1953)NoStop
[Cartwright and Harary(1956)]cartwright1956structural
  author author D. Cartwright and author F. Harary, @noop  journal journal
  Psychol. Rev. volume 63, pages 277
  (year 1956)NoStop
[Antal et al.(2005)Antal,
  Krapivsky, and Redner]antal2005dynamics
  author author T. Antal, author P. L. Krapivsky,  and author S. Redner, @noop  journal journal Phys.
  Rev. E volume 72, pages 036121
  (year 2005)NoStop
[Malarz and Hołyst(2022)]malarz2022mean
  author author K. Malarz and author J. A. Hołyst, @noop  journal journal
  Phys. Rev. E volume 106, pages
  064139 (year 2022)NoStop
[Wołoszyn and Malarz(2022)]woloszyn2022thermal
  author author M. Wołoszyn and author K. Malarz, @noop  journal journal Phys.
  Rev. E volume 105, pages 024301
  (year 2022)NoStop
[Malarz and Wołoszyn(2023)]malarz2023thermal
  author author K. Malarz and author M. Wołoszyn, @noop  journal journal
  Chaos volume 33, pages 073115
  (year 2023)NoStop
[Marvel et al.(2009)Marvel,
  Strogatz, and Kleinberg]marvel2009energy
  author author S. A. Marvel, author S. H. Strogatz,  and author J. M. Kleinberg, @noop  journal journal
  Phys. Rev. Lett. volume 103, pages
  198701 (year 2009)NoStop
[Kułakowski et al.(2005)Kułakowski, Gawroński, and Gronek]kulakowski2005heider
  author author K. Kułakowski, author P. Gawroński,  and author P. Gronek, @noop  journal journal Int.
  J. Mod. Phys. C volume 16, pages 707
  (year 2005)NoStop
[Marvel et al.(2011)Marvel,
  Kleinberg, Kleinberg, and Strogatz]marvel2011continuous
  author author S. A. Marvel, author J. Kleinberg,
  author R. D. Kleinberg,  and  author S. H. Strogatz,  @noop  journal journal Proc. Natl. Acad.
  Sci. USA volume 108, pages 1771
  (year 2011)NoStop
[Alexander(1987)]alexander1987biology
  author author R. D. Alexander, @noop  title The Biology of Moral
  Systems (publisher Aldine de Gruyter, address
  New York, year 1987)NoStop
[Nowak and Sigmund(2005)]nowak2005evolution
  author author M. A. Nowak and author K. Sigmund, @noop  journal journal
  Nature volume 437, pages 1291
  (year 2005)NoStop
[Nowak and Sigmund(1998)]nowak1998evolution
  author author M. A. Nowak and author K. Sigmund, @noop  journal journal
  Nature volume 393, pages 573
  (year 1998)NoStop
[Leimar and Hammerstein(2001)]leimar2001evolution
  author author O. Leimar and author P. Hammerstein, @noop  journal journal
  Proc. R. Soc. B volume 268, pages
  745 (year 2001)NoStop
[Sugden(1986)]sugden1986economics
  author author R. Sugden, @noop  title The Economics of Rights,
  Cooperation and Welfare (publisher Blackwell, address Oxford, year 1986)NoStop
[Ohtsuki and Iwasa(2004)]ohtsuki2004should
  author author H. Ohtsuki and author Y. Iwasa, @noop  journal journal J.
  Theor. Biol. volume 231, pages 107
  (year 2004)NoStop
[Ohtsuki and Iwasa(2006)]ohtsuki2006leading
  author author H. Ohtsuki and author Y. Iwasa, @noop  journal journal J.
  Theor. Biol. volume 239, pages 435
  (year 2006)NoStop
[Kandori(1992)]kandori1992social
  author author M. Kandori, @noop  journal journal Rev.
  Econ. Stud. volume 59, pages 63
  (year 1992)NoStop
[Pacheco et al.(2006)Pacheco, Santos, and Chalub]pacheco2006stern
  author author J. M. Pacheco, author F. C. Santos,
   and author F. A. C. Chalub,  @noop  journal journal PLoS Comput.
  Biol. volume 2, pages e178 (year 2006)NoStop
[Santos et al.(2018)Santos,
  Santos, and Pacheco]santos2018social
  author author F. P. Santos, author F. C. Santos,
   and author J. M. Pacheco,  @noop  journal journal Nature volume 555, pages 242 (year
  2018)NoStop
[Oishi et al.(2021)Oishi,
  Miyano, Kaski, and Shimada]oishi2021balanced
  author author K. Oishi, author S. Miyano,
  author K. Kaski,  and author T. Shimada, @noop 
  journal journal Phys. Rev. E volume 104, pages 024310 (year
  2021)NoStop
[Hilbe et al.(2018)Hilbe,
  Schmid, Tkadlec, Chatterjee,  and Nowak]hilbe2018indirect
  author author C. Hilbe, author L. Schmid,
  author J. Tkadlec, author K. Chatterjee,  and author M. A. Nowak, @noop 
  journal journal Proc. Natl. Acad. Sci. USA  volume 115, pages 12241 (year 2018)NoStop
[Lee et al.(2021)Lee,
  Murase, and Baek]lee2021local
  author author S. Lee, author Y. Murase,  and  author S. K. Baek, @noop
   journal journal Sci. Rep. volume 11, pages 14225 (year
  2021)NoStop
[Lee et al.(2022)Lee,
  Murase, and Baek]lee2022second
  author author S. Lee, author Y. Murase,  and  author S. K. Baek, @noop
   journal journal J. Theor. Biol. volume 548, pages 111202 (year
  2022)NoStop
[Mun and Baek(2023)]mun2023second
  author author Y. Mun and author S. K. Baek,  @noop  journal journal Eur. Phys. J.
  Spec. Top. , pages 1 (year 2023)NoStop
[Oishi et al.(2013)Oishi,
  Shimada, and Ito]oishi2013group
  author author K. Oishi, author T. Shimada,   and author N. Ito, @noop
   journal journal Phys. Rev. E volume 87, pages 030801 (year
  2013)NoStop
[Murase and Baek(2020)]murase2020five
  author author Y. Murase and author S. K. Baek, @noop  journal journal Sci.
  Rep. volume 10, pages 16904 (year 2020)NoStop
[Nowak(2006)]nowak2006evolutionary
  author author M. A. Nowak, @noop  title Evolutionary Dynamics:
  Exploring the Equations of Life (publisher Harvard
  University Press, address Cambridge, MA, year
  2006)NoStop
[Fujimoto and Ohtsuki(2022)]fujimoto2022reputation
  author author Y. Fujimoto and author H. Ohtsuki, @noop  journal journal Sci.
  Rep. volume 12, pages 10500 (year 2022)NoStop
[Dornic et al.(2001)Dornic,
  Chaté, Chave, and Hinrichsen]dornic2001critical
  author author I. Dornic, author H. Chaté,
  author J. Chave,  and author H. Hinrichsen, @noop 
  journal journal Phys. Rev. Lett. volume 87, pages 045701 (year
  2001)NoStop
[Monroe(1992)]monroe1992phase
  author author J. L. Monroe, @noop  journal journal J.
  Stat. Phys. volume 67, pages 1185
  (year 1992)NoStop
[Ananikian and Dallakian(1997)]ananikian1997multifractal
  author author N. Ananikian and author S. Dallakian, @noop  journal journal
  Phys. D volume 107, pages 75
  (year 1997)NoStop
[Malarz and Wołoszyn(2020)]malarz2020expulsion
  author author K. Malarz and author M. Wołoszyn, @noop  journal journal
  Chaos volume 30 (year
  2020)NoStop
[Wu and Wu(1989)]wu1989exact
  author author X. Wu and author F. Wu,  @noop  journal journal J. Phys. A  volume 22, pages L1031 (year
  1989)NoStop
[Barry and Muttalib(2019)]barry2019finite
  author author J. Barry and author K. Muttalib, @noop  journal journal
  Phys. A volume 527, pages 121326
  (year 2019)NoStop
[Kuroda et al.(2023)Kuroda,
  Kaski, and Shimada]kuroda2023frustrated
  author author D. Kuroda, author K. K. Kaski,   and author T. Shimada,  @noop  journal journal Front. Phys.  volume 11, pages 366 (year
  2023)NoStop
[Baxter(2007)]baxter2007exactly
  author author R. J. Baxter, @noop  title Exactly Solved Models in
  Statistical Mechanics, edition 3rd ed. (publisher Dover Publications, address Mineola, NY,  year 2007)NoStop

