Paper deep dive
Symmetric solution of the Bellman optimality equation for repeated harmony game
Hisato Komatsu
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In social dilemma games, additional rewards or punishments have been studied as means of promoting cooperation. Therefore, it is important to investigate the ideal situation, in which such an additional payoff would change the game. In this study, we investigated the symmetric solution of the Bellman optimality equation for a repeated harmony game. The calculations showed that three types of symmetric solutions exist. One of them corresponds to the trivial All-C strategy, and another to the Win-stay Lose-shift strategy of the prisoners dilemma game. The nontrivial behavior of the strategy corresponding to the last solution is also discussed in detail. In addition, we numerically investigated which strategy the agents actually learn by the reinforcement learning algorithm.
Tags
Links
- Source: https://arxiv.org/abs/2609.16289v1
- Canonical: https://arxiv.org/abs/2609.16289v1
Trouble viewing inline? Open PDF directly →
Full Text
65,645 characters extracted from source content.
Expand or collapse full text
Symmetric solution of the Bellman optimality equation for repeated harmony game Hisato Komatsu Email: komatsu@phys.kindai.ac.jp Affiliation: Department of Physics, Kindai University, 577-8502, Higashi-Osaka, Osaka, Japan Affiliation: Data Science and AI Innovation Research Promotion Center, Shiga University, 522-8522, Hikone, Shiga, Japan Abstract In social dilemma games, additional rewards or punishments have been studied as means of promoting cooperation. Therefore, it is important to investigate the ideal situation, in which such an additional payoff would change the game. In this study, we investigated the symmetric solution of the Bellman optimality equation for a repeated harmony game. The calculations showed that three types of symmetric solutions exist. One of them corresponds to the trivial All-C strategy, and another to the Win-stay Lose-shift strategy of the prisoners dilemma game. The nontrivial behavior of the strategy corresponding to the last solution is also discussed in detail. In addition, we numerically investigated which strategy the agents actually learn by the reinforcement learning algorithm. 1 Introduction The methods for promoting cooperation in social dilemma games are important in game theory. One such method is the introduction of additional rewards or punishments by participants [1, 2] or third parties [3, 4]. Along with recent advances in machine learning, multi-agent reinforcement learning methods incorporating such additional rewards have been proposed [5]. Moreover, the learning dynamics of agents in the presence of additional rewards have also been studied [6]. Various studies have been conducted on reinforcement learning applied to repeated games [7, 8, 9]. Usui and Ueda investigated the symmetric solution, i.e., the solution in which the two agents have the same strategy, of the Bellman optimality equation for the repeated prisoner’s dilemma [10]. They showed that the All-D strategy creates an equilibrium regardless of the conditions, and the Win-stay Lose-shift (WSLS) [11] and Grim strategies create it when specific conditions are fulfilled. The Bellman optimality equation was also employed by Meylahn and Janssen to investigate the best response to an opponent with a fixed strategy [12, 13]. The harmony game is a 2×22× 2 game in which cooperation yields a higher payoff for an agent regardless of the opponent’s strategy. This game is often excluded from theoretical considerations because cooperation is the dominant strategy, at least in one-shot games. However, several previous studies have reported that, even in this game, cooperation can collapse under certain evolutionary [14] or learning dynamics [15], or the spatial structure [16], indicating that the emergence and maintenance of cooperation is not always trivial in practice. Moreover, in repeated games, the folk theorem ensures the existence of strategies that achieve a wide range of average payoffs [17]. Therefore, before considering situations in which additional payoffs are introduced to promote cooperation, we first examine the ideal case in which such additional payoffs completely transform the game into a harmony game. This study investigated the Bellman optimality equation of the harmony game with an approach similar to that in Ref. [10] and lists possible strategies corresponding to symmetric solutions. In addition, we performed numerical experiments using reinforcement learning (Q-learning [20, 21]) to examine which strategies the agents learn under several initial conditions. The remainder of this paper introduces this model in Sec. 2 and then derives the symmetric solutions of the Bellman optimality equation in Sec. 3. We compare these solutions with the numerical simulations in Sec. 4, and summarize the study in Sec. 5. For reproducibility, details of the simulations in Sec. 4 are provided in A. We also discuss the optimal strategy when the opponent’s strategy is fixed, in B. 2 Model We consider the repeated harmony game, in which two agents (A and B) choose an action, either C (cooperation) or D (defection), at each time step. The reward for each agent, rAr_A or rBr_B, depends on their joint action, (a,b) (a,b ), according to rA(C,C) r_A ( .C,C . ) =rB(C,C)=R, =r_B ( .C,C . )=R, (1) rA(C,D) r_A ( .C,D . ) =rB(D,C)=S, =r_B ( .D,C . )=S, rA(D,C) r_A ( .D,C . ) =rB(C,D)=T, =r_B ( .C,D . )=T, rA(D,D) r_A ( .D,D . ) =rB(D,D)=P, =r_B ( .D,D . )=P, with R>T>PR>T>P and R>S>PR>S>P. Strictly speaking, the definition of the harmony game varies slightly across references. Our definition is identical to that used in Ref. [16], for example. Throughout this paper, we use the term “reward” instead of “payoff” to align with the terminology of reinforcement learning. In the one-shot game, the unique Nash equilibrium is (C,C) (C,C ), and C is the dominant strategy of both agents. Moreover, unlike the prisoner’s dilemma, the one-shot game lacks a social dilemma. However, in a repeated game, the folk theorem ensures the existence of Nash equilibrium strategies other than the trivial All-C strategy [17]. Therefore, theoretical and numerical investigations should be carefully conducted to avoid overlooking such nontrivial strategies. For simplicity, we focus on memory-1 strategies, in which agents forget any actions taken two steps ago or earlier and choose their current action based solely on their previous action. In this case, the observation of the agent was the previous joint action. 3 Bellman optimality equation and its symmetric solution By ignoring exploration noise such as ϵε in ϵε-greedy method, the Bellman optimality equation is expressed as follows: QA∗((a0,b0),a1) Q_A ( (a_0,b_0 ),a_1 ) = = rA(a1,b~1)+γmaxa2QA∗((a1,b~1),a2), r_A ( .a_1, b_1 . )+γ _a_2Q_A ( (a_1, b_1 ),a_2 ), (2) QB∗((a0,b0),b1) Q_B ( (a_0,b_0 ),b_1 ) = = rB(a~1,b1)+γmaxb2QB∗((a~1,b1),b2), r_B ( . a_1,b_1 . )+γ _b_2Q_B ( ( a_1,b_1 ),b_2 ), (3) wherea~1=argmaxa1QA∗((a0,b0),a1),b~1=argmaxb1QB∗((a0,b0),b1).where\ \ a_1= *argmax_a_1Q_A ( (a_0,b_0 ),a_1 ),\ b_1= *argmax_b_1Q_B ( (a_0,b_0 ),b_1 ). (4) To derive Eq. (4), we assume that agents employ the greedy method. Assuming symmetry of the Q-function between the two agents, QA∗((a0,b0),a)=QB∗((b0,a0),a),Q_A ( (a_0,b_0 ),a )=Q_B ( (b_0,a_0 ),a ), (5) Eq. (3) can be reduced to Eq. (2). Therefore, we consider Eq. (2) under the following conditions: b~1=argmaxb1QA∗((b0,a0),b1). b_1= *argmax_b_1Q_A ( (b_0,a_0 ),b_1 ). (6) In the following discussions, we ignore the case in which the Q-functions for the two actions accidentally coincide: QA∗((a,b),C)=QA∗((a,b),D)Q_A ( (a,b ),C )=Q_A ( (a,b ),D ), considering that such cases rarely occur. 3.1 Limitation on the symmetric solution In this section, we prove two lemmas that characterize the allowed pairwise ordering of the Q-function. Lemma 1. QA∗((D,D),C)>QA∗((D,D),D)Q_A ( (D,D ),C )>Q_A ( (D,D ),D ) Proof 1. If we assume QA∗((D,D),C)<QA∗((D,D),D)Q_A ( (D,D ),C )<Q_A ( (D,D ),D ), then Bellman equation for QA∗((D,D),a1)Q_A ( (D,D ),a_1 ) is expressed as: QA∗((D,D),C)=S+γmaxa2QA∗((C,D),a2),Q_A ( (D,D ),C )=S+γ _a_2Q_A ( (C,D ),a_2 ), (7) QA∗((D,D),D)=P+γmaxa2QA∗((D,D),a2)=P+γQA∗((D,D),D).Q_A ( (D,D ),D )=P+γ _a_2Q_A ( (D,D ),a_2 )=P+γ Q_A ( (D,D ),D ). (8) Solving Eq. (8), we obtain QA∗((D,D),D)=P1−γ.Q_A ( (D,D ),D )= P1-γ. (9) Considering that the reward at each step has a minimum value, P, the following inequality is derived from the original definition of the Q-function: QA∗((a0,b0),a1) Q_A ( (a_0,b_0 ),a_1 ) = = E[∑t=0∞γtrA(at+1,bt+1)|(a0,b0),a1] E [ _t=0^∞γ^tr_A ( .a_t+1,b_t+1 . ) | (a_0,b_0 ),a_1 ] (10) ≥ ≥ ∑t=0∞γtP=P1−γ _t=0^∞γ^tP= P1-γ Substituting this into Eqs. (7) and (9), we obtain the following inequality: QA∗((D,D),C)−QA∗((D,D),D)≥S+γP1−γ−P1−γ=S−P>0.Q_A ( (D,D ),C )-Q_A ( (D,D ),D )≥ S+ γ P1-γ- P1-γ=S-P>0. (11) However, this contradicts the first assumption, QA∗((D,D),C)<QA∗((D,D),D)Q_A ( (D,D ),C )<Q_A ( (D,D ),D ). Thus, QA∗((D,D),C)>QA∗((D,D),D)Q_A ( (D,D ),C )>Q_A ( (D,D ),D ). ∎ Using Lemma 1, the Bellman optimality equation for QA∗((D,D),a)Q_A ( (D,D ),a ) can be expressed as QA∗((D,D),C)=R+γmaxa2QA∗((C,C),a2),Q_A ( (D,D ),C )=R+γ _a_2Q_A ( (C,C ),a_2 ), (12) QA∗((D,D),D)=T+γmaxa2QA∗((D,C),a2),Q_A ( (D,D ),D )=T+γ _a_2Q_A ( (D,C ),a_2 ), (13) Lemma 2. Only the following two order-relation patterns are permitted: QA∗((D,C),C)>QA∗((D,C),D)andQA∗((C,D),C)>QA∗((C,D),D)Q_A ( (D,C ),C )>Q_A ( (D,C ),D )\ and\ Q_A ( (C,D ),C )>Q_A ( (C,D ),D ) (14) QA∗((D,C),C)<QA∗((D,C),D)andQA∗((C,D),C)<QA∗((C,D),D)Q_A ( (D,C ),C )<Q_A ( (D,C ),D )\ and\ Q_A ( (C,D ),C )<Q_A ( (C,D ),D ) (15) Proof 2. Assuming QA∗((D,C),C)<QA∗((D,C),D)Q_A ( (D,C ),C )<Q_A ( (D,C ),D ) and QA∗((C,D),C)>QA∗((C,D),D)Q_A ( (C,D ),C )>Q_A ( (C,D ),D ), we obtain the following equations: QA∗((D,C),C)=R+γmaxa2QA∗((C,C),a2)=QA∗((D,D),C),Q_A ( (D,C ),C )=R+γ _a_2Q_A ( (C,C ),a_2 )=Q_A ( (D,D ),C ), (16) QA∗((D,C),D)=T+γmaxa2QA∗((D,C),a2)=QA∗((D,D),D),Q_A ( (D,C ),D )=T+γ _a_2Q_A ( (D,C ),a_2 )=Q_A ( (D,D ),D ), (17) Here, Eqs. (12) and (13) were used to derive these equations. Considering Eqs. (16) and (17), and Lemma 1, the following inequality holds: QA∗((D,C),C)=QA∗((D,D),C)>QA∗((D,D),D)=QA∗((D,C),D).Q_A ( (D,C ),C )=Q_A ( (D,D ),C )>Q_A ( (D,D ),D )=Q_A ( (D,C ),D ). (18) However, this result contradicts the assumption QA∗((D,C),C)<QA∗((D,C),D)Q_A ( (D,C ),C )<Q_A ( (D,C ),D ). Similarly, QA∗((D,C),C)>QA∗((D,C),D)Q_A ( (D,C ),C )>Q_A ( (D,C ),D ) and QA∗((C,D),C)<QA∗((C,D),D)Q_A ( (C,D ),C )<Q_A ( (C,D ),D ) produces the contradiction. Therefore, Eqs. (14) and (15) are the only permitted order-relation patterns. ∎ 3.2 Explicit solutions Next, we derive explicit solutions for the four cases allowed by the lemmas in Sec. 3.1. Each solution has the same form as in Ref. [10] because the structure of the Bellman equation does not depend directly on the relationship among R,T,SR,T,S, and P, but on the assumed pairwise ordering of the Q-function. In this discussion, we use the following expression: x1 x_1 ≡R+γmaxa2QA∗((C,C),a2), ≡ R+γ _a_2Q_A ( (C,C ),a_2 ), (19) x2 x_2 ≡T+γmaxa2QA∗((D,C),a2), ≡ T+γ _a_2Q_A ( (D,C ),a_2 ), x3 x_3 ≡S+γmaxa2QA∗((C,D),a2), ≡ S+γ _a_2Q_A ( (C,D ),a_2 ), x4 x_4 ≡P+γmaxa2QA∗((D,D),a2), ≡ P+γ _a_2Q_A ( (D,D ),a_2 ), for later convenience. This expression is primarily used in B 3.2.1 The case QA∗((C,C),C)>QA∗((C,C),D)Q_A ( (C,C ),C )>Q_A ( (C,C ),D ), QA∗((C,D),C)>QA∗((C,D),D)Q_A ( (C,D ),C )>Q_A ( (C,D ),D ), QA∗((D,C),C)>QA∗((D,C),D)Q_A ( (D,C ),C )>Q_A ( (D,C ),D ), and QA∗((D,D),C)>QA∗((D,D),D)Q_A ( (D,D ),C )>Q_A ( (D,D ),D ) This corresponds to an All-C strategy. The solution is given as x1 x_1 =QA∗((C,C),C)=QA∗((C,D),C)=QA∗((D,C),C)=QA∗((D,D),C)=11−γR =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )=Q_A ( (D,C ),C )=Q_A ( (D,D ),C )= 11-γR (20) x2 x_2 =QA∗((C,C),D)=QA∗((C,D),D)=QA∗((D,C),D)=QA∗((D,D),D)=T+γ1−γR =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=Q_A ( (D,D ),D )=T+ γ1-γR This is always consistent with the condition of the harmony game. 3.2.2 The case QA∗((C,C),C)>QA∗((C,C),D)Q_A ( (C,C ),C )>Q_A ( (C,C ),D ), QA∗((C,D),C)<QA∗((C,D),D)Q_A ( (C,D ),C )<Q_A ( (C,D ),D ), QA∗((D,C),C)<QA∗((D,C),D)Q_A ( (D,C ),C )<Q_A ( (D,C ),D ), and QA∗((D,D),C)>QA∗((D,D),D)Q_A ( (D,D ),C )>Q_A ( (D,D ),D ) This corresponds to the WSLS strategy in the prisoner’s dilemma [11]. In this study, we use the term “WSLS” for convenience, although the notions of “win” and “lose” in the harmony game differ from those in the prisoner’s dilemma. The solution is given as x1 x_1 =QA∗((C,C),C)=QA∗((D,D),C)=11−γR =Q_A ( (C,C ),C )=Q_A ( (D,D ),C )= 11-γR (21) x2 x_2 =QA∗((C,C),D)=QA∗((D,D),D)=T+γP+γ21−γR, =Q_A ( (C,C ),D )=Q_A ( (D,D ),D )=T+γ P+ γ^21-γR, x3 x_3 =QA∗((C,D),C)=QA∗((D,C),C)=S+γP+γ21−γR, =Q_A ( (C,D ),C )=Q_A ( (D,C ),C )=S+γ P+ γ^21-γR, x4 x_4 =QA∗((C,D),D)=QA∗((D,C),D)=P+γ1−γR, =Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=P+ γ1-γR, This solution is consistent with the condition of the game when γ>S−PR−Pγ> S-PR-P. 3.2.3 The case QA∗((C,C),C)<QA∗((C,C),D)Q_A ( (C,C ),C )<Q_A ( (C,C ),D ), QA∗((C,D),C)>QA∗((C,D),D)Q_A ( (C,D ),C )>Q_A ( (C,D ),D ), QA∗((D,C),C)>QA∗((D,C),D)Q_A ( (D,C ),C )>Q_A ( (D,C ),D ), and QA∗((D,D),C)>QA∗((D,D),D)Q_A ( (D,D ),C )>Q_A ( (D,D ),D ) In this case, the solution is given as x1 x_1 =QA∗((C,D),C)=QA∗((D,C),C)=QA∗((D,D),C)=11−γ2(R+γP), =Q_A ( (C,D ),C )=Q_A ( (D,C ),C )=Q_A ( (D,D ),C )= 11-γ^2(R+γ P), (22) x2 x_2 =QA∗((C,D),D)=QA∗((D,C),D)=QA∗((D,D),D)=T+γ1−γ2(R+γP), =Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=Q_A ( (D,D ),D )=T+ γ1-γ^2(R+γ P), x3 x_3 =QA∗((C,C),C)=S+γ1−γ2(R+γP), =Q_A ( (C,C ),C )=S+ γ1-γ^2(R+γ P), x4 x_4 =QA∗((C,C),D)=11−γ2(P+γR) =Q_A ( (C,C ),D )= 11-γ^2(P+γ R) However, this solution contradicts the condition S>PS>P. 3.2.4 The case QA∗((C,C),C)<QA∗((C,C),D)Q_A ( (C,C ),C )<Q_A ( (C,C ),D ), QA∗((C,D),C)<QA∗((C,D),D)Q_A ( (C,D ),C )<Q_A ( (C,D ),D ), QA∗((D,C),C)<QA∗((D,C),D)Q_A ( (D,C ),C )<Q_A ( (D,C ),D ), and QA∗((D,D),C)>QA∗((D,D),D)Q_A ( (D,D ),C )>Q_A ( (D,D ),D ) In this case, the solution is given as x1 x_1 =QA∗((D,D),C)=11−γ2(R+γP), =Q_A ( (D,D ),C )= 11-γ^2(R+γ P), (23) x2 x_2 =QA∗((D,D),D)=T+γ1−γ2(P+γR), =Q_A ( (D,D ),D )=T+ γ1-γ^2(P+γ R), x3 x_3 =QA∗((C,C),C)=QA∗((C,D),C)=QA∗((D,C),C)=S+γ1−γ2(P+γR), =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )=Q_A ( (D,C ),C )=S+ γ1-γ^2(P+γ R), x4 x_4 =QA∗((C,C),D)=QA∗((C,D),D)=QA∗((D,C),D)=11−γ2(P+γR). =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=Q_A ( (D,C ),D )= 11-γ^2(P+γ R). This solution is consistent with the condition of the game when γ>S−PR−Sγ> S-PR-S. In this strategy, an agent chooses C if and only if both agents chose D in the previous step. In the repeated prisoner’s dilemma, the “handshake mechanisms”, in which agents use particular initial action patterns as the signal for cooperation, have been proposed [18, 19]. Compared to these mechanisms, this strategy seems to require frequent “D” handshakes from the opponent at an appropriate time as a condition of cooperation. Hence, in the following, we call this strategy the “Frequent Handshake (FH) strategy”. Note that this strategy is termed the “anti-Grim trigger” in some studies [13], however, the definition of the term “anti-Grim trigger” is confusing because its definition varies across the literature. The FH strategy may seem odd because it deliberately destroys cooperation even though defection yields a lower reward. Therefore, to illustrate the actual dynamics, we examine several cases in which agent A uses specific strategies while agent B’s strategy is fixed as an FH strategy. First, if agent A adopts the FH strategy, the sequence converges to the following limit cycle: (C,C)→(D,D)→(C,C)→….(C,C)→(D,D)→(C,C)→.... (24) In this case, the long-term average of agent A’s reward is R+P2 R+P2. For agent A using the WSLS strategy, the sequence converges to the following limit cycle: (C,C)→(C,D)→(D,D)→(C,C)→…,(C,C)→(C,D)→(D,D)→(C,C)→..., (25) and the long-term average of agent A’s reward is R+S+P3 R+S+P3. If agent A emoplys the All-C strategy, the sequence converges to a fixed point, (C,D),(C,D), (26) and the long-term average of agent A’s reward is S. Among the three strategies, the FH strategy achieves the highest long-term average when R+P2>S. R+P2>S. (27) The condition that the FH strategy appears, γ>S−PR−Sγ> S-PR-S, converges to Eq. (27) when γ→1γ→ 1. In addition, considering the following: S=minbmaxarA(a,b),S= _b _ar_A ( .a,b . ), (28) Eq. (27) has the same form as the condition under which the folk theorem holds (for γ sufficiently close to 1) [17]. The best response of agent A under the fixed strategy of agent B is investigated in detail in B. 4 Numerical experiments In this section, we numerically investigate the strategies adopted by actual reinforcement learning agents. Here, Q-learning [20, 21] was employed as the learning algorithm, and the two agents independently updated their Q-functions QAQ_A and QBQ_B. In other words, these functions were updated after the reward was calculated at each step using the following equation: QA((at−1,bt−1),at)← Q_A ( (a_t-1,b_t-1 ),a_t )← QA((at−1,bt−1),at) Q_A ( (a_t-1,b_t-1 ),a_t ) (29) +α[rA(at,bt)+γmaxa′QA((at,bt),a′)−QA((at−1,bt−1),at)], +α [r_A (a_t,b_t )+γ _a Q_A ( (a_t,b_t ),a )-Q_A ( (a_t-1,b_t-1 ),a_t ) ], QB((at−1,bt−1),at)← Q_B ( (a_t-1,b_t-1 ),a_t )← QB((at−1,bt−1),at) Q_B ( (a_t-1,b_t-1 ),a_t ) +α[rB(at,bt)+γmaxb′QB((at,bt),b′)−QB((at−1,bt−1),bt)], +α [r_B (a_t,b_t )+γ _b Q_B ( (a_t,b_t ),b )-Q_B ( (a_t-1,b_t-1 ),b_t ) ], where α denotes the learning rate. The rewards for each joint action were set as R=3R=3, T=2T=2, S=1S=1, and P=0P=0. One episode is truncated when the time step reaches Tep=100T_ep=100, but the truncation is not treated as an episode termination when updating the Q-functions according to Eq. (29). In the actual implementation, we realized this by recording the global time step t and resetting the environment when t was a multiple of Tep=100T_ep=100; that is, when t%Tep=t%100=0t \%T_ep=t \%100=0. At the beginning of each episode, the observation of agents, (a,b) (a,b ), is uniformly randomly chosen from (C,C) (C,C ), (C,D) (C,D ), (D,C) (D,C ), and (D,D) (D,D ). In other words, the previous actions observed by the agents in the initial state are selected uniformly at random. At each step, the agents choose their actions according to the ϵε-greedy method. For each agent, i=A,Bi=A,B, the initial value of ϵi _i is set to ϵinit _init, and ϵi _i is subsequently decreased using the following equation: ϵi←max[ϵmin,(1−δϵ)ϵi], _i← [ _min,(1- _ε) _i ], (30) We considered two values of ϵinit _init: ϵinit=1 _init=1 and ϵinit=0.02 _init=0.02, whereas the other hyperparameters were fixed, as given in Table 2 of A. The detailed pseudocode is provided by Algorithm 1 in this appendix. Several initial Q-functions were also considered: Qinit=QzeroQ_init=Q_zero, QWSLSQ_WSLS, and QFHQ_FH, where Qzero((a,b),a′)=0foranya,b,a′,Q_zero ( (a,b ),a )=0\ \ for\ any\ a,b,a , (31) QWSLS((C,C),C) Q_WSLS ( (C,C ),C ) =QWSLS((C,D),D)=QWSLS((D,C),D)=QWSLS((D,D),C)=1, =Q_WSLS ( (C,D ),D )=Q_WSLS ( (D,C ),D )=Q_WSLS ( (D,D ),C )=1, (32) QWSLS((C,C),D) Q_WSLS ( (C,C ),D ) =QWSLS((C,D),C)=QWSLS((D,C),C)=QWSLS((D,D),D)=0, =Q_WSLS ( (C,D ),C )=Q_WSLS ( (D,C ),C )=Q_WSLS ( (D,D ),D )=0, and QFH((C,C),D) Q_FH ( (C,C ),D ) =QFH((C,D),D)=QFH((D,C),D)=QFH((D,D),C)=1, =Q_FH ( (C,D ),D )=Q_FH ( (D,C ),D )=Q_FH ( (D,D ),C )=1, (33) QFH((C,C),C) Q_FH ( (C,C ),C ) =QFH((C,D),C)=QFH((D,C),C)=QFH((D,D),D)=0, =Q_FH ( (C,D ),C )=Q_FH ( (D,C ),C )=Q_FH ( (D,D ),D )=0, with QA((a,b),a′)|t=0=QB((b,a),a′)|t=0=Qinit((a,b),a′). .Q_A ( (a,b ),a ) |_t=0= .Q_B ( (b,a ),a ) |_t=0=Q_init ( (a,b ),a ). (34) As seen later, when Qinit=QzeroQ_init=Q_zero, the agents adopt the All-C strategy with high probability. Therefore, we also investigated two other initial Q-functions, QWSLSQ_WSLS and QFHQ_FH, under which agents tend to employ WSLS and FH strategies. When tuning hyperparameters, we conducted 20 or 100 trials using a random seed different from that used when collecting the reported data. Fig. 1 shows the time evolution of the Q-function in each case. In this figure, the solid curves and shaded areas show the median and interquartile intervals (both computed using the numpy.quantile()) over 1000 independent trials. The graphs of the cases with Qinit=QWSLSQ_init=Q_WSLS or QFHQ_FH and ϵinit=1 _init=1 are omitted because their shapes are almost identical to the corresponding graph for Qinit=QzeroQ_init=Q_zero and ϵinit=1 _init=1. Table 1 lists the number of trials (out of 1000) in which both agents selected each strategy. In this table, the learned strategy is identified by the ordering of the Q-functions at the end of the simulation, and the cases in which the two agents learned different strategies are excluded. According to the table, agents almost always learn the All-C strategy when ϵinit=1 _init=1, whereas the learned strategy depends on QinitQ_init when ϵinit=0.02 _init=0.02. Specifically, agents learned the WSLS strategy when Qinit=QWSLSQ_init=Q_WSLS and the FH strategy when Qinit=QFHQ_init=Q_FH in most trials. Under Qinit=QzeroQ_init=Q_zero and ϵinit=0.02 _init=0.02, the All-C strategy was learned most frequently. However, the WSLS and FH strategies were sometimes learned. Comparing the results for Qinit=QzeroQ_init=Q_zero with different values of ϵinit _init, the frequency with which both agents learned the All-C strategy is higher when ϵinit=1 _init=1 than when ϵinit=0.02 _init=0.02. A possible explanation is that when the opponent behaves randomly, independent of the previous action, the appropriate strategy is always to choose C as in the one-shot game. To compare the simulation results with the theoretical values discussed in 3.2, we plot the symmetric solutions of the Bellman optimality equation as dotted lines in Fig. 1. These lines correspond to the All-C strategy (Eq. (20)) in graphs (a) and (b), the WSLS strategy (Eq. (21)) in (c), and the FH strategy (Eq. (23)) in (d). Fig. 1 indicates that the medians of the Q-functions converge to a symmetric solution corresponding to the strategies most frequently learned in the simulations. Note that in this simulation, strategies learned with low frequency behaved as outliers, which caused the average over the trials to deviate from the theoretical values. Therefore, we have plotted the median and interquartile intervals in Fig. 1. Figure 1: Time evolution of the Q-function (of agent A) with (a) Qinit=QzeroQ_init=Q_zero and ϵinit=1 _init=1, (b) Qinit=QzeroQ_init=Q_zero and ϵinit=0.02 _init=0.02, (c) Qinit=QWSLSQ_init=Q_WSLS and ϵinit=0.02 _init=0.02, and (d) Qinit=QFHQ_init=Q_FH and ϵinit=0.02 _init=0.02. The solid curves and shaded areas of each color represent the median and interquartile intervals of each component QA((a,b),a′)Q_A ( (a,b ),a ). The dotted lines are the corresponding components of the symmetric solution of the Bellman optimality equation, yielding (a), (b) the All-C strategy (Eq. (20)); (c) the WSLS strategy (Eq. (21)); and (d) the FH strategy (Eq. (23)). initial condition All-C WSLS FH Qinit=QzeroQ_init=Q_zero, ϵinit=1 _init=1 1000 0 0 Qinit=QWSLSQ_init=Q_WSLS, ϵinit=1 _init=1 1000 0 0 Qinit=QFHQ_init=Q_FH, ϵinit=1 _init=1 1000 0 0 Qinit=QzeroQ_init=Q_zero, ϵinit=0.02 _init=0.02 823 64 13 Qinit=QWSLSQ_init=Q_WSLS, ϵinit=0.02 _init=0.02 1 999 0 Qinit=QFHQ_init=Q_FH, ϵinit=0.02 _init=0.02 0 7 993 Table 1: Number of trials (out of 1000) in which both agents learned each strategy. 5 Summary In this study, we analyzed the Bellman optimality equation for a repeated harmony game and identified three symmetric solutions: All-C, WSLS, and a third strategy, which we referred to as the Frequent Handshake (FH). In the FH strategy, the agent chooses C (cooperation) only when both it and the opponent have chosen D (defection) in the previous step. If both agents employ this strategy, they repeat (C,C) (C,C ) and (D,D) (D,D ) alternately and punish deviations from this pattern by choosing D. Numerical experiments using Q-learning showed that agents frequently learn WSLS or FH strategies if the exploration noise is sufficiently weak and the initial Q-function is biased toward these strategies. Our original motivation was to promote cooperation in the social dilemma game by introducing additional rewards, and the harmony game was considered as an ideal case in which these additional rewards completely resolve the dilemma at least in the one-shot game. The fact that such nontrivial strategies exist even in the harmony game makes the design of the additional reward complex. In particular, the FH strategy frequently chooses D and consequently receives less reward than the All-C and WSLS strategies. If frequent defections were observed in more complex environments or under more sophisticated reinforcement learning algorithms, it would be difficult to determine whether they reflected a non-trivial strategy learned by the agents or were merely due to insufficient relaxation or algorithmic issues. The source code for this work is uploaded to https://github.com/Hisato-Komatsu/Repeated_Harmony. Acknowledgements We would like to thank Editage (w.editage.jp) for English language editing. Declaration of generative AI and AI-assisted technologies in the manuscript preparation process During the preparation of this work, the author used DeepL, Google Translate, Microsoft Copilot, and ChatGPT for English language editing, translation, research-related queries, and source code review and improvement suggestions. After using these tools, the author reviewed and edited the content as needed and takes full responsibility for the content of the publication. Appendix A Details of the numerical experiment This section describes the pseudocode (Algorithm 1), and lists the hyperparameters (Table 2) for reproducibility. Algorithm 1 Algorithm used for the calculation 1: Initialize QAQ_A and QBQ_B using Eq. (34) 2: ϵA,ϵB←ϵinit _A, _B← _init 3: Set the initial observation (a0,b0) (a_0,b_0 ) randomly 4: for t←1,…,Tmaxt← 1,...,T_max do 5: Choose agents’ action ata_t and btb_t using ϵε-greedy method with ϵ=ϵAε= _A and ϵ=ϵBε= _B, respectively 6: Calculate the rewards rAr_A and rBr_B 7: Update QAQ_A and QBQ_B using Eq. (29) 8: ϵA←max[ϵmin,(1−δϵ)ϵA] _A← [ _min,(1- _ε) _A ] 9: ϵB←max[ϵmin,(1−δϵ)ϵB] _B← [ _min,(1- _ε) _B ] 10: if t%Tep=0t \%T_ep=0 then 11: truncate the episode and reset the environment by randomly reselecting (at,bt) (a_t,b_t ) 12: end if 13: end for character meaning value γ discount factor 0.95 δϵ _ε decaying rate of ϵε per one step 1×10−61× 10^-6 ϵmin _min minimum value of ϵε 0.002 α learning rate 0.1 TepT_ep episode length 100 TmaxT_max whole time steps 10710^7 R – 3 T – 2 S – 1 P – 0 Table 2: Hyperparameters of this study. Appendix B Optimal strategy against fixed strategy To gain insights into the stability of a strategy, it is common practice to consider an agent’s learning dynamics while the opponent’s strategy is fixed [12, 13]. Therefore, we briefly discuss agent A’s learning when agent B’s strategy is fixed. Assuming that agent B follows a deterministic policy πB _B, the Bellman optimality equation for agent A is given by Eq. (2) with b~1=πB(a0,b0), b_1= _B ( .a_0,b_0 . ), (35) where πB(a,b) _B ( .a,b . ) denotes agent B’s action when the previous action pair (a,b) (a,b ) is given. To represent agent B’s strategy, we use the following vector: (πB(C,C),πB(C,D),πB(D,C),πB(D,D)). ( _B ( .C,C . ), _B ( .C,D . ), _B ( .D,C . ), _B ( .D,D . ) ). (36) For example, the WSLS strategy is expressed as (C,D,D,C)(C,D,D,C). First, we discuss the case in which agent B takes the strategies that genetate the symmetric solutions discussed in Sec. 3.2, WSLS, FH, and All-C. B.1 Optimal strategy against the WSLS strategy (The case (C,D,D,C)(C,D,D,C)) When agent B’s strategy is fixed as the WSLS strategy, the Bellman optimality equation is expressed as follows: QA∗((C,C),C) Q_A ( (C,C ),C ) =QA∗((D,D),C)=R+γmaxa2QA∗((C,C),a2), =Q_A ( (D,D ),C )=R+γ _a_2Q_A ( (C,C ),a_2 ), (37) QA∗((C,C),D) Q_A ( (C,C ),D ) =QA∗((D,D),D)=T+γmaxa2QA∗((D,C),a2), =Q_A ( (D,D ),D )=T+γ _a_2Q_A ( (D,C ),a_2 ), QA∗((C,D),C) Q_A ( (C,D ),C ) =QA∗((D,C),C)=S+γmaxa2QA∗((C,D),a2), =Q_A ( (D,C ),C )=S+γ _a_2Q_A ( (C,D ),a_2 ), QA∗((C,D),D) Q_A ( (C,D ),D ) =QA∗((D,C),D)=P+γmaxa2QA∗((D,D),a2). =Q_A ( (D,C ),D )=P+γ _a_2Q_A ( (D,D ),a_2 ). Using Eq. (19), Eq. (37) is transformed into x1 x_1 =R+γmax(x1,x2), =R+γ (x_1,x_2 ), (38) x2 x_2 =T+γmax(x3,x4), =T+γ (x_3,x_4 ), x3 x_3 =S+γmax(x3,x4), =S+γ (x_3,x_4 ), x4 x_4 =P+γmax(x1,x2). =P+γ (x_1,x_2 ). By solving these equations, we obtain the same form as Eq. (21) with x1>x2x_1>x_2 and x3<x4x_3<x_4 when γ>S−PR−Pγ> S-PR-P, and x1 x_1 =QA∗((C,C),C)=QA∗((D,D),C)=11−γR, =Q_A ( (C,C ),C )=Q_A ( (D,D ),C )= 11-γR, (39) x2 x_2 =QA∗((C,C),D)=QA∗((D,D),D)=T+γ1−γS, =Q_A ( (C,C ),D )=Q_A ( (D,D ),D )=T+ γ1-γS, x3 x_3 =QA∗((C,D),C)=QA∗((D,C),C)=11−γS, =Q_A ( (C,D ),C )=Q_A ( (D,C ),C )= 11-γS, x4 x_4 =QA∗((C,D),D)=QA∗((D,C),D)=P+γ1−γR. =Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=P+ γ1-γR. with x1>x2x_1>x_2 and x3>x4x_3>x_4 when γ<S−PR−Pγ< S-PR-P. Seeing the ordering of the Q-function values, the former and latter solutions correspond to the WSLS and All-C strategies, respectively. B.2 Optimal strategy against the FH strategy (The case (D,D,D,C)(D,D,D,C)) In this case, the Bellman optimality equation is expressed as QA∗((D,D),C) Q_A ( (D,D ),C ) =R+γmaxa2QA∗((C,C),a2), =R+γ _a_2Q_A ( (C,C ),a_2 ), (40) QA∗((D,D),D) Q_A ( (D,D ),D ) =T+γmaxa2QA∗((D,C),a2), =T+γ _a_2Q_A ( (D,C ),a_2 ), QA∗((C,C),C) Q_A ( (C,C ),C ) =QA∗((C,D),C)=QA∗((D,C),C)=S+γmaxa2QA∗((C,D),a2), =Q_A ( (C,D ),C )=Q_A ( (D,C ),C )=S+γ _a_2Q_A ( (C,D ),a_2 ), QA∗((C,C),D) Q_A ( (C,C ),D ) =QA∗((C,D),D)=QA∗((D,C),D)=P+γmaxa2QA∗((D,D),a2). =Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=P+γ _a_2Q_A ( (D,D ),a_2 ). By solving these equations, we obtain the same form as Eq. (23) with x1>x2x_1>x_2 and x3<x4x_3<x_4 when γ>S−PR−Sγ> S-PR-S and x1 x_1 =QA∗((D,D),C)=R+γ1−γS, =Q_A ( (D,D ),C )=R+ γ1-γS, (41) x2 x_2 =QA∗((D,D),D)=T+γ1−γS, =Q_A ( (D,D ),D )=T+ γ1-γS, x3 x_3 =QA∗((C,C),C)=QA∗((C,D),C)=QA∗((D,C),C)=11−γS, =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )=Q_A ( (D,C ),C )= 11-γS, x4 x_4 =QA∗((C,C),D)=QA∗((C,D),D)=QA∗((D,C),D)=P+γR+γ21−γS, =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=P+γ R+ γ^21-γS, with x1>x2x_1>x_2 and x3>x4x_3>x_4 when γ<S−PR−Sγ< S-PR-S. The former and latter solutions correspond to the FH and All-C strategies, respectively. B.3 Optimal strategy against the All-C strategy (The case (C,C,C,C)(C,C,C,C)) In this case, by solving the Bellman optimality equation, as in the two cases above, we obtain the same form as Eq. (20), with x1>x2x_1>x_2. This solution corresponds to the All-C strategy. In other words, when agent B adopts the All-C strategy, the optimal strategy for agent A is also the All-C one. Note that, for All-C, WSLS, and FH, the condition under which the optimal strategy against each strategy coincides with the respective strategy is the same as that under which the symmetric solution discussed in Sec. 3.2 emerges. This implies that the strategy providing the symmetric solution represents a Nash equilibrium, in which neither of the two agents can unilaterally change their strategy to increase their cumulative reward, when the strategy set is restricted to memory-1 strategies. B.4 Optimal strategies against other fixed strategies We also consider the case in which the strategy of agent B is fixed as one of 13 (deterministic) strategies that do not correspond to symmetric solutions. B.4.1 The case (C,C,C,D)(C,C,C,D) In this case, we obtain x1 x_1 =QA∗((C,C),C)=QA∗((C,D),C)=QA∗((D,C),C)=11−γR, =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )=Q_A ( (D,C ),C )= 11-γR, (42) x2 x_2 =QA∗((C,C),D)=QA∗((C,D),D)=QA∗((D,C),D)=T+γ1−γR, =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=T+ γ1-γR, x3 x_3 =QA∗((D,D),C)=S+γ1−γR, =Q_A ( (D,D ),C )=S+ γ1-γR, x4 x_4 =QA∗((D,D),D)=P+γS+γ21−γR, =Q_A ( (D,D ),D )=P+γ S+ γ^21-γR, with x1>x2x_1>x_2 and x3>x4x_3>x_4. This solution corresponds to the All-C strategy. B.4.2 The case (C,C,D,C)(C,C,D,C) In this case, we obtain x1 x_1 =QA∗((C,C),C)=QA∗((C,D),C)=QA∗((D,D),C)=11−γR, =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )=Q_A ( (D,D ),C )= 11-γR, (43) x2 x_2 =QA∗((C,C),D)=QA∗((C,D),D)=QA∗((D,D),D)=T+γS+γ21−γR, =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=Q_A ( (D,D ),D )=T+γ S+ γ^21-γR, x3 x_3 =QA∗((D,C),C)=S+γ1−γR, =Q_A ( (D,C ),C )=S+ γ1-γR, x4 x_4 =QA∗((D,C),D)=P+γ1−γR, =Q_A ( (D,C ),D )=P+ γ1-γR, with x1>x2x_1>x_2 and x3>x4x_3>x_4. This solution corresponds to the All-C strategy. B.4.3 The case (C,D,C,C)(C,D,C,C) In this case, we obtain x1 x_1 =QA∗((C,C),C)=QA∗((D,C),C)=QA∗((D,D),C)=11−γR, =Q_A ( (C,C ),C )=Q_A ( (D,C ),C )=Q_A ( (D,D ),C )= 11-γR, (44) x2 x_2 =QA∗((C,C),D)=QA∗((D,C),D)=QA∗((D,D),D)=T+γ1−γR, =Q_A ( (C,C ),D )=Q_A ( (D,C ),D )=Q_A ( (D,D ),D )=T+ γ1-γR, x3 x_3 =QA∗((C,D),C)=11−γS, =Q_A ( (C,D ),C )= 11-γS, x4 x_4 =QA∗((C,D),D)=P+γ1−γR, =Q_A ( (C,D ),D )=P+ γ1-γR, with x1>x2x_1>x_2 and x3>x4x_3>x_4, when γ<S−PR−Pγ< S-PR-P, and x1 x_1 =QA∗((C,C),C)=QA∗((D,C),C)=QA∗((D,D),C)=11−γR, =Q_A ( (C,C ),C )=Q_A ( (D,C ),C )=Q_A ( (D,D ),C )= 11-γR, (45) x2 x_2 =QA∗((C,C),D)=QA∗((D,C),D)=QA∗((D,D),D)=T+γ1−γR, =Q_A ( (C,C ),D )=Q_A ( (D,C ),D )=Q_A ( (D,D ),D )=T+ γ1-γR, x3 x_3 =QA∗((C,D),C)=S+γP+γ21−γR, =Q_A ( (C,D ),C )=S+γ P+ γ^21-γR, x4 x_4 =QA∗((C,D),D)=P+γ1−γR, =Q_A ( (C,D ),D )=P+ γ1-γR, with x1>x2x_1>x_2 and x3<x4x_3<x_4, when γ>S−PR−Pγ> S-PR-P. The former and latter solutions correspond to the All-C and (C,C,D,C)(C,C,D,C) strategies. B.4.4 The case (D,C,C,C)(D,C,C,C) In this case, we obtain x1 x_1 =QA∗((C,D),C)=QA∗((D,C),C)=QA∗((D,D),C)=11−γ2(R+γS), =Q_A ( (C,D ),C )=Q_A ( (D,C ),C )=Q_A ( (D,D ),C )= 11-γ^2(R+γ S), (46) x2 x_2 =QA∗((C,D),D)=QA∗((D,C),D)=QA∗((D,D),D)=T+γ1−γ2(R+γS), =Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=Q_A ( (D,D ),D )=T+ γ1-γ^2(R+γ S), x3 x_3 =QA∗((C,C),C)=11−γ2(S+γR), =Q_A ( (C,C ),C )= 11-γ^2(S+γ R), x4 x_4 =QA∗((C,C),D)=P+γ1−γ2(R+γS), =Q_A ( (C,C ),D )=P+ γ1-γ^2(R+γ S), with x1>x2x_1>x_2 and x3>x4x_3>x_4, when γ(T−S)<R−Tγ(T-S)<R-T, and x1 x_1 =QA∗((C,D),C)=QA∗((D,C),C)=QA∗((D,D),C)=R+γS+γ21−γT, =Q_A ( (C,D ),C )=Q_A ( (D,C ),C )=Q_A ( (D,D ),C )=R+γ S+ γ^21-γT, (47) x2 x_2 =QA∗((C,D),D)=QA∗((D,C),D)=QA∗((D,D),D)=11−γT, =Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=Q_A ( (D,D ),D )= 11-γT, x3 x_3 =QA∗((C,C),C)=S+γ1−γT, =Q_A ( (C,C ),C )=S+ γ1-γT, x4 x_4 =QA∗((C,C),D)=P+γ1−γT, =Q_A ( (C,C ),D )=P+ γ1-γT, with x1<x2x_1<x_2 and x3>x4x_3>x_4, when γ(T−S)>R−Tγ(T-S)>R-T. The former and latter solutions correspond to the All-C and Grim strategies, respectively. Here, following Refs. [10, 12, 13], we use the term “Grim strategy” to refer to the 1-memory strategy that chooses C if and only if the previous joint action is (C,C) (C,C ), i.e., the (C,D,D,D)(C,D,D,D) strategy. This terminology differs from the conventional Grim Trigger strategy in which a deviation triggers permanent punishment [22, 23]. B.4.5 The case (C,C,D,D)(C,C,D,D) In this case, agent B responds with the Tit-for-Tat (TFT) strategy [24]. By solving the Bellman optimality equation, we obtain x1 x_1 =QA∗((C,C),C)=QA∗((C,D),C)=11−γR, =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )= 11-γR, (48) x2 x_2 =QA∗((C,C),D)=QA∗((C,D),D)=T+γS+γ21−γR, =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=T+γ S+ γ^21-γR, x3 x_3 =QA∗((D,C),C)=QA∗((D,D),C)=S+γ1−γR, =Q_A ( (D,C ),C )=Q_A ( (D,D ),C )=S+ γ1-γR, x4 x_4 =QA∗((D,C),D)=QA∗((D,D),D)=P+γS+γ21−γR, =Q_A ( (D,C ),D )=Q_A ( (D,D ),D )=P+γ S+ γ^21-γR, with x1>x2x_1>x_2 and x3>x4x_3>x_4. This solution corresponds to the All-C strategy. B.4.6 The case (C,D,C,D)(C,D,C,D) In this case, we obtain x1 x_1 =QA∗((C,C),C)=QA∗((D,C),C)=11−γR, =Q_A ( (C,C ),C )=Q_A ( (D,C ),C )= 11-γR, (49) x2 x_2 =QA∗((C,C),D)=QA∗((D,C),D)=T+γ1−γR, =Q_A ( (C,C ),D )=Q_A ( (D,C ),D )=T+ γ1-γR, x3 x_3 =QA∗((C,D),C)=QA∗((D,D),C)=11−γS, =Q_A ( (C,D ),C )=Q_A ( (D,D ),C )= 11-γS, x4 x_4 =QA∗((C,D),D)=QA∗((D,D),D)=P+γ1−γS, =Q_A ( (C,D ),D )=Q_A ( (D,D ),D )=P+ γ1-γS, with x1>x2x_1>x_2 and x3>x4x_3>x_4. This solution corresponds to the All-C strategy. B.4.7 The case (D,C,C,D)(D,C,C,D) In this case, we obtain x1 x_1 =QA∗((C,D),C)=QA∗((D,C),C)=11−γ2(R+γS), =Q_A ( (C,D ),C )=Q_A ( (D,C ),C )= 11-γ^2(R+γ S), (50) x2 x_2 =QA∗((C,D),D)=QA∗((D,C),D)=T+γ1−γ2(R+γS), =Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=T+ γ1-γ^2(R+γ S), x3 x_3 =QA∗((C,C),C)=QA∗((D,D),C)=11−γ2(S+γR), =Q_A ( (C,C ),C )=Q_A ( (D,D ),C )= 11-γ^2(S+γ R), x4 x_4 =QA∗((C,C),D)=QA∗((D,D),D)=P+γ1−γ2(S+γR), =Q_A ( (C,C ),D )=Q_A ( (D,D ),D )=P+ γ1-γ^2(S+γ R), with x1>x2x_1>x_2 and x3>x4x_3>x_4, when R−T>γ(T−S)R-T>γ(T-S), and x1 x_1 =QA∗((C,D),C)=QA∗((D,C),C)=R+γS+γ21−γT, =Q_A ( (C,D ),C )=Q_A ( (D,C ),C )=R+γ S+ γ^21-γT, (51) x2 x_2 =QA∗((C,D),D)=QA∗((D,C),D)=11−γT, =Q_A ( (C,D ),D )=Q_A ( (D,C ),D )= 11-γT, x3 x_3 =QA∗((C,C),C)=QA∗((D,D),C)=S+γ1−γT, =Q_A ( (C,C ),C )=Q_A ( (D,D ),C )=S+ γ1-γT, x4 x_4 =QA∗((C,C),D)=QA∗((D,D),D)=P+γS+γ21−γT, =Q_A ( (C,C ),D )=Q_A ( (D,D ),D )=P+γ S+ γ^21-γT, with x1<x2x_1<x_2 and x3>x4x_3>x_4, when R−T<γ(T−S)R-T<γ(T-S). The former and latter solutions correspond to the All-C and WSLS strategies. B.4.8 The case (D,C,D,C)(D,C,D,C) In this case, we obtain x1 x_1 =QA∗((C,D),C)=QA∗((D,D),C)=11−γ2(R+γS), =Q_A ( (C,D ),C )=Q_A ( (D,D ),C )= 11-γ^2(R+γ S), (52) x2 x_2 =QA∗((C,D),D)=QA∗((D,D),D)=T+γ1−γ2(S+γR), =Q_A ( (C,D ),D )=Q_A ( (D,D ),D )=T+ γ1-γ^2(S+γ R), x3 x_3 =QA∗((C,C),C)=QA∗((D,C),C)=11−γ2(S+γR), =Q_A ( (C,C ),C )=Q_A ( (D,C ),C )= 11-γ^2(S+γ R), x4 x_4 =QA∗((C,C),D)=QA∗((D,C),D)=P+γ1−γ2(R+γS), =Q_A ( (C,C ),D )=Q_A ( (D,C ),D )=P+ γ1-γ^2(R+γ S), with x1>x2x_1>x_2 and x3>x4x_3>x_4. This solution corresponds to the All-C strategy. B.4.9 The case (D,D,C,C)(D,D,C,C) In this case, we obtain x1 x_1 =QA∗((D,C),C)=QA∗((D,D),C)=R+γ1−γS, =Q_A ( (D,C ),C )=Q_A ( (D,D ),C )=R+ γ1-γS, (53) x2 x_2 =QA∗((D,C),D)=QA∗((D,D),D)=T+γR+γ21−γS, =Q_A ( (D,C ),D )=Q_A ( (D,D ),D )=T+γ R+ γ^21-γS, x3 x_3 =QA∗((C,C),C)=QA∗((C,D),C)=11−γS, =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )= 11-γS, x4 x_4 =QA∗((C,C),D)=QA∗((C,D),D)=P+γR+γ21−γS, =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=P+γ R+ γ^21-γS, with x1>x2x_1>x_2 and x3>x4x_3>x_4, when T−γS<(1−γ)RT-γ S<(1-γ)R and S>P+γR1+γS> P+γ R1+γ, x1 x_1 =QA∗((D,C),C)=QA∗((D,D),C)=11−γ2(R+γP), =Q_A ( (D,C ),C )=Q_A ( (D,D ),C )= 11-γ^2(R+γ P), (54) x2 x_2 =QA∗((D,C),D)=QA∗((D,D),D)=T+γ1−γ2(R+γP), =Q_A ( (D,C ),D )=Q_A ( (D,D ),D )=T+ γ1-γ^2(R+γ P), x3 x_3 =QA∗((C,C),C)=QA∗((C,D),C)=S+γ1−γ2(P+γR), =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )=S+ γ1-γ^2(P+γ R), x4 x_4 =QA∗((C,C),D)=QA∗((C,D),D)=11−γ2(P+γR), =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )= 11-γ^2(P+γ R), with x1>x2x_1>x_2 and x3<x4x_3<x_4, when T<R+γP1+γT< R+γ P1+γ and S<P+γR1+γS< P+γ R1+γ, x1 x_1 =QA∗((D,C),C)=QA∗((D,D),C)=R+γ1−γS, =Q_A ( (D,C ),C )=Q_A ( (D,D ),C )=R+ γ1-γS, (55) x2 x_2 =QA∗((D,C),D)=QA∗((D,D),D)=11−γT, =Q_A ( (D,C ),D )=Q_A ( (D,D ),D )= 11-γT, x3 x_3 =QA∗((C,C),C)=QA∗((C,D),C)=11−γS, =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )= 11-γS, x4 x_4 =QA∗((C,C),D)=QA∗((C,D),D)=P+γ1−γT, =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=P+ γ1-γT, with x1<x2x_1<x_2 and x3>x4x_3>x_4, when T−γS>(1−γ)RT-γ S>(1-γ)R and S−γT>(1−γ)PS-γ T>(1-γ)P, and x1 x_1 =QA∗((D,C),C)=QA∗((D,D),C)=R+γP+γ21−γT, =Q_A ( (D,C ),C )=Q_A ( (D,D ),C )=R+γ P+ γ^21-γT, (56) x2 x_2 =QA∗((D,C),D)=QA∗((D,D),D)=11−γT, =Q_A ( (D,C ),D )=Q_A ( (D,D ),D )= 11-γT, x3 x_3 =QA∗((C,C),C)=QA∗((C,D),C)=S+γP+γ21−γT, =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )=S+γ P+ γ^21-γT, x4 x_4 =QA∗((C,C),D)=QA∗((C,D),D)=P+γ1−γT, =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=P+ γ1-γT, with x1<x2x_1<x_2 and x3<x4x_3<x_4, when T>R+γP1+γT> R+γ P1+γ and S−γT<(1−γ)PS-γ T<(1-γ)P. These solutions correspond to the All-C, (D,C,D,C)(D,C,D,C), (C,D,C,D)(C,D,C,D), and All-D strategies. B.4.10 The case (C,D,D,D)(C,D,D,D) In this case, agent B’s stragtegy corresponds to the Grim one. Solving the Bellman optimality equation, we obtain x1 x_1 =QA∗((C,C),C)=11−γR, =Q_A ( (C,C ),C )= 11-γR, (57) x2 x_2 =QA∗((C,C),D)=T+γ1−γS, =Q_A ( (C,C ),D )=T+ γ1-γS, x3 x_3 =QA∗((C,D),C)=QA∗((D,C),C)=QA∗((D,D),C)=11−γS, =Q_A ( (C,D ),C )=Q_A ( (D,C ),C )=Q_A ( (D,D ),C )= 11-γS, x4 x_4 =QA∗((C,D),D)=QA∗((D,C),D)=QA∗((D,D),D)=P+γ1−γS, =Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=Q_A ( (D,D ),D )=P+ γ1-γS, with x1>x2x_1>x_2 and x3>x4x_3>x_4. This solution corresponds to the All-C strategy. B.4.11 The case (D,C,D,D)(D,C,D,D) In this case, we obtain x1 x_1 =QA∗((C,D),C)=11−γ2(R+γS), =Q_A ( (C,D ),C )= 11-γ^2(R+γ S), (58) x2 x_2 =QA∗((C,D),D)=T+γ1−γ2(S+γR), =Q_A ( (C,D ),D )=T+ γ1-γ^2(S+γ R), x3 x_3 =QA∗((C,C),C)=QA∗((D,C),C)=QA∗((D,D),C)=11−γ2(S+γR), =Q_A ( (C,C ),C )=Q_A ( (D,C ),C )=Q_A ( (D,D ),C )= 11-γ^2(S+γ R), x4 x_4 =QA∗((C,C),D)=QA∗((D,C),D)=QA∗((D,D),D)=P+γ1−γ2(S+γR), =Q_A ( (C,C ),D )=Q_A ( (D,C ),D )=Q_A ( (D,D ),D )=P+ γ1-γ^2(S+γ R), with x1>x2x_1>x_2 and x3>x4x_3>x_4. This solution corresponds to the All-C strategy. B.4.12 The case (D,D,C,D)(D,D,C,D) In this case, we obtain x1 x_1 =QA∗((D,C),C)=R+γ1−γS, =Q_A ( (D,C ),C )=R+ γ1-γS, (59) x2 x_2 =QA∗((D,C),D)=T+γR+γ21−γS, =Q_A ( (D,C ),D )=T+γ R+ γ^21-γS, x3 x_3 =QA∗((C,C),C)=QA∗((C,D),C)=QA∗((D,D),C)=11−γS, =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )=Q_A ( (D,D ),C )= 11-γS, x4 x_4 =QA∗((C,C),D)=QA∗((C,D),D)=QA∗((D,D),D)=P+γ1−γS, =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=Q_A ( (D,D ),D )=P+ γ1-γS, with x1>x2x_1>x_2 and x3>x4x_3>x_4, when γ<R−TR−Sγ< R-TR-S, and x1 x_1 =QA∗((D,C),C)=R+γ1−γS, =Q_A ( (D,C ),C )=R+ γ1-γS, (60) x2 x_2 =QA∗((D,C),D)=11−γT, =Q_A ( (D,C ),D )= 11-γT, x3 x_3 =QA∗((C,C),C)=QA∗((C,D),C)=QA∗((D,D),C)=11−γS, =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )=Q_A ( (D,D ),C )= 11-γS, x4 x_4 =QA∗((C,C),D)=QA∗((C,D),D)=QA∗((D,D),D)=P+γ1−γS, =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=Q_A ( (D,D ),D )=P+ γ1-γS, with x1<x2x_1<x_2 and x3>x4x_3>x_4, when γ>R−TR−Sγ> R-TR-S. The former and latter solutions correspond to the All-C and (C,D,C,C)(C,D,C,C) strategies. B.4.13 The case (D,D,D,D)(D,D,D,D) (the All-D strategy) In this case, we obtain x3 x_3 =QA∗((C,C),C)=QA∗((C,D),C)=QA∗((D,C),C)=QA∗((D,D),C)=11−γS, =Q_A ( (C,C ),C )=Q_A ( (C,D ),C )=Q_A ( (D,C ),C )=Q_A ( (D,D ),C )= 11-γS, (61) x4 x_4 =QA∗((C,C),D)=QA∗((C,D),D)=QA∗((D,C),D)=QA∗((D,D),D)=P+γ1−γS, =Q_A ( (C,C ),D )=Q_A ( (C,D ),D )=Q_A ( (D,C ),D )=Q_A ( (D,D ),D )=P+ γ1-γS, with x3>x4x_3>x_4. This solution corresponds to the All-C strategy. In light of the above discussion, we can draw a directed graph in which the edges go from each strategy to its optimal response, as shown in Fig. 2. This graph is referred to as the best-response network in Ref. [12]. Fig. 2 shows that the graph contains three absorbing states corresponding to the symmetric solution of Sec. 3.2, that is, the All-C, WSLS, and FH strategies. Therefore, if the agents update their strategies by taking the best response to the present opponent, as in Ref. [12], their strategies converge to one of these three or to the cycle among them. Figure 2: The best-response network of the Harmony game when the agents’ strategies are deterministic. References [1] E. Fehr, S. Gächter, Cooperation and punishment in public goods experiments, Am. Econ. Rev. 90(4) (2000) 980–994. https://doi.org/10.1257/aer.90.4.980 [2] R. Boyd, H. Gintis, S. Bowles, P. J. Richerson, The evolution of altruistic punishment, Proc. Natl. Acad. Sci. U.S.A. 100(6) (2003) 3531-3535. https://doi.org/10.1073/pnas.0630443100 [3] E. Fehr, U. Fischbacher, Third-party punishment and social norms, Evol. Hum. Behav. 25(2) (2004) 63-87. https://doi.org/10.1016/S1090-5138(04)00005-4 [4] E. W. de Kwaadsteniet, S. A. M. Rijkhoff, E. van Dijk, Equality as a benchmark for third-party punishment and reward: The moderating role of uncertainty in social dilemmas, Organ. Behav. Hum. Decis. Proc. 120(2) (2013) 251-259. https://doi.org/10.1016/j.obhdp.2012.06.007 [5] J. Yang, A. Li, M. Farajtabar, P. Sunehag, E. Hughes, H. Zha, Learning to Incentivize Other Learning Agents, In Advances in Neural Information Processing Systems 33 (NeurIPS 2020) (2020) [6] C. Zhao, G. Zheng, C. Zhang, J. Zhang, L. Chen, Emergence of cooperation under punishment: A reinforcement learning perspective, Chaos 34 (2024) 073123. https://doi.org/10.1063/5.0215702 [7] T. W. Sandholm, R. H. Crites, Multiagent reinforcement learning in the Iterated Prisoner’s Dilemma, Biosystems 37 (1996) 147-166. https://doi.org/10.1016/0303-2647(95)01551-5 [8] J. Foerster, R. Chen, M. Al-Shedivat, S. Whiteson, P. Abbeel, I. Mordatch, Learning with opponent-learning awareness, In Proceedings of the 17th international conference on autonomous agents and multiagent systems, (2018) 122 - 130. https://dl.acm.org/doi/abs/10.5555/3237383.3237408 [9] Y. Hu, C. Han, H. Li, T. Guo, Modeling opponent learning in multiagent repeated games, Appl. Intell. 53(13) (2023) 17194–17210. https://doi.org/10.1007/s10489-022-04249-x. [10] Y. Usui, M. Ueda, Symmetric equilibrium of multi-agent reinforcement learning in repeated prisoner’s dilemma, Appl. Math. Comput. 409 (2021) 126370. https://doi.org/10.1016/j.amc.2021.126370 [11] M. Nowak, K. Sigmund A strategy of win-stay, lose-shift that outperforms tit-for-tat in the Prisoner’s Dilemma game, Nature 364 (1993) 56–58. https://doi.org/10.1038/364056a0 [12] J. M. Meylahn, L. Janssen, Limiting dynamics for Q-learning with memory one in symmetric two-player, two-action Games, Complexity 2022(1) (2022) 4830491. https://doi.org/10.1155/2022/4830491 [13] J. M. Meylahn, Quantifying the likelihood of learning collusive strategy equilibria, Chaos 35 (2025) 083106. https://doi.org/10.1063/5.0281443 [14] C. P. Roca, J. A. Cuesta, and A. Sánchez Time Scales in Evolutionary Dynamics, Phys. Rev. Lett. 97 (2006) 158701. https://doi.org/10.1103/PhysRevLett.97.158701 [15] M. C. Couto, F. P. Santos, and C. Hilbe, Evolution of noisy learning in games, Proc. Natl. Acad. Sci. U.S.A. 123(20) (2026) e2529959123. https://doi.org/10.1073/pnas.2529959123 [16] J. T. Matamalas, J. Poncela-Casasnovas, S. Gómez, and A. Arenas, Strategical incoherence regulates cooperation in social dilemmas on multiplex networks, Sci. Rep. 5 (2015) 9519. https://doi.org/10.1038/srep09519 [17] D. Fudenberg, and E. Maskin The folk theorem in repeated games with discounting or with incomplete information, Econometrica 54(3) (1986) 533-554. https://doi.org/10.2307/1911307 [18] J. Li, P. Hingston, and G. Kendall, Engineering design of strategies for winning iterated prisoner’s dilemma competitions, IEEE Trans. Comput. Intell. AI Games 3(4) (2011) 348-360. https://doi.org/10.1109/TCIAIG.2011.2166268 [19] V. Knight, M. Harper, N. E. Glynatsi, and O. Campbell, Evolution reinforces cooperation with the emergence of self-recognition mechanisms: An empirical study of strategies in the Moran process for the iterated prisoner’s dilemma, PLoS One. 13(10) (2018) e0204981. https://doi.org/10.1371/journal.pone.0204981 [20] C. J. C. H. Watkins and P. Dayan, Q-learning, Mach. Learn. 8(3) (1992) 279–292. https://doi.org/10.1007/BF00992698 [21] R. S. Sutton, A. G. Barto, Reinforcement Learning: An Introduction, second edition, MIT press, (2018). [22] J. E. Harrington, Jr. The Determination of Price and Output Quotas in a Heterogeneous Cartel, Int. Econ. Rev. 32(4) (1991) 767-792. https://doi.org/10.2307/2527033 [23] F. McGillivray and A. Smith. Trust and cooperation through agent-specific punishments, Int. Organ. 54(4) (2000) 809-824. https://doi.org/10.1162/002081800551370 [24] R. Axelrod, and W. D. Hamilton, The evolution of cooperation, Science 211(4489) (1981) 1390-1396. https://doi.org/10.1126/science.7466396