Learning Homophilic Incentives in Sequential Social Dilemmas
Authors: Heng Dong
Tonghan Wang
Jiayuan Liu
Chi Han
Chongjie Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: Multi-Agent Reinforcement Learning
Sequential Social Dilemma
Cooperation Emergence

Abstract: Promoting cooperation among self-interested agents is a long-standing and interdisciplinary problem, but receives less attention in multi-agent reinforcement learning (MARL). Game-theoretical studies reveal that altruistic incentives are critical to the emergence of cooperation but their analyses are limited to non-sequential social dilemmas. Recent works using deep MARL also show that learning to incentivize other agents has the potential to promote cooperation in more realistic sequential social dilemmas (SSDs). However, we find that, with these incentivizing mechanisms, the team cooperation level does not converge and regularly oscillates between cooperation and defection during learning. We show that a second-order social dilemma resulting from the incentive mechanisms is the main reason for such fragile cooperation. We analyze the dynamics of second-order social dilemmas and find that a typical tendency of humans, called homophily, provides a promising solution. We propose a novel learning framework to encourage homophilic incentives and show that it achieves stable cooperation in both SSDs of public goods and tragedy of the commons.

Under review as a conference paper at ICLR 2022
LEARNING HOMOPHILIC INCENTIVES IN SEQUENTIAL SOCIAL DILEMMAS
Anonymous authors Paper under double-blind review
ABSTRACT
Promoting cooperation among eef-iinterested agents is a long-standing and interdis- ciplinary problem, but receives less attention multi-agent reinforcement learning (MARL). Gtame-theoretical studies reveal that altruistic incentives are critical to the emergence of cooperation but their analyses are limited to non-sequential social dilemmas. Recent works using deep MARI. also show that learning to incentivize other agents has the potential to promote cooperation in more realistic sequential find that, with incentivizing mechanisms,
social dilemmas (SSDs). However, the team cooperation level does not converge and regularly oscillates between cooperation and defection during learning. We show that second-order social dilemma resulting from the incentive mechanisms is the main reason for such frag- ile cooperation. We analyze the dynamics of second-order social dilemmas and find that a typical tendency of humans, called homophily, provides promising solution. We propose a novel learning framework to encourage homophilic incentives and show that it achieves stable cooperation in both SSDs of public goods and tragedy of the commons.
INTRODUCTION
Deep multi-agent reinforcement learning (MARL) has achieved prominent progress (Sunehag et al. 2018 Rashid et al. 2018 Baker et al.) [2020] Wang et al. 2021). While much effort is devoted to fully cooperative settings, -mainng individuals many real-world situations may be self-interested. such as autonomous vehicles (Bonnefon et al. 2016), taxpayers (Rothstein) 2001 and governments dealing with climate change (Capstick 2013). unique phenomenon among self-interested agents social dilemma, in which individually rational behavior results in situation where everyone suffers in the long run. Historically, the problem of how cooperation emerges in social dilemmas has long perplexed scientists from various fields, such as evolutionary biology, animal behavioristics (Packer et al. 1991), and neuroscience (Rilling et al. 2002). and is listed as one the 125 most compelling science questions for the 21st century (Kennedy 2005 Pennisi 2005).
Cooperation emergence in non- non-sequential social dilemmas (SDs) have been extensively studied (Boyd) 1989 Rand & Nowak 2011). However, these methods only consider the problems that be cast as a matrix game (Hughes et al. 2018), and typically assume the existence of atomic actions for cooperative and defective strategies. Thus their applicability real-world, temporally extended SDs is limited, where cooperation and defection are policies that need to be learned. With the ability to learn policies in complex tasks, deep MARL shows promise to fill the gap and study how cooperation emerges in these more realistic sequential social dilemmas (SSDs) (Leibo et al. 2017).
Some previous works have studied SSDs from the perspective of MARL (Jaques et 2019 Hughes et al. 2018). Among them, Yang et al. (020) and Lupu & Precup (200) extend (altruistic) incentives to temporally extended cases. Referring to individuals paying costs to punish or reward others even though there is no immediate gain by these actions for themselves (Ostrom et al., 1992 Güth 1995]
Fehr & Gächter, 2002: Boyd et al. 2003 Mussweiler & Ockenfels 2013). altruistic incentives have been proven to be highly related to cooperation emergence in non-sequential SDs (Fowler 2005 Akçay & Roughgarden 2011 Fong Surti 2009). However, altruistic incentives have not been fully studied in SSDs. The aforementioned deep methods do not effectively scale up and are limited in very small settings. With further investigation, we find that these methods do not converge to stable cooperation, where the cooperation level regularly oscillates between cooperation and defection.

---

Under review as a conference paper at ICLR 2022
In this paper, we first analyze the underlying reasons behind the phenomenon of such unstable cooperation. We find that, although incentives make cooperation more likely to emerge, they also introduce second-order social dilemma (2nd-SDs) problem into the system if someone else would pay costs to punish or reward others, why should bother to do so (Dreber et al. (008) The consequence is that more and more second-order free-riders would exploit those agents who make an effort to incentivize others, resulting in degraded incentivizing mechanism and thus collapsed cooperation. 2nd-SDs have been well studied in non-sequential social dilemmas (Fowler) [2005] Greenwood, 2016). However, solving 2nd-SDs in sequential settings remains largely untouched in the literature and posts new challenges- the identification of cooperation and defection for incentivizing is non-trivial in SSDs and cooperation is more vulnerable to 2nd-SDs in SSDs than in SDs. Thus SSDs require a different computational approach to promote cooperation. Specifically. in SSDs, agents need to learn temporally extended strategies which are much more complex than simple cooperation and defection action in SDs and can be dynamically mixed with cooperation and defection behaviors, especially during the learning. The agents that have successfully learned cooperative incentivizing policies can be exploited by other agents with temporarily learned mixing strategies, and the exploited cooperators may abandon cooperative strategies, making it less likely for other agents to learn to cooperate. This issue does not exist in SDs but will severely hinder cooperation emergence in SSDs.
To solve this problem, first illustrate the dynamies of and formally analyze the impetus for the second-order social dilemma on a fully-featured motivating example. Based on these analyses, we propose novel learning mechanism by encouraging agents with similar environmental behaviors to have similar incentivizing behaviors. Our method is inspired by a concept called homophily, a particularly common tendency for human individuals to associate or bound with similar others, as in the proverb birds of feather flock together. In the literature, homophily has been studied in non-sequential social dilemmas, where agents interact with others of similar predefined types (Fu et al. 2012, Fletcher & Doebeli 2009 Ramazi et al. 2016). In non-sequential cases, agents can choose their partners to interact with (Rand et al. 2011 Aksoy 2015) or there is a matching system that
similar agents (Bergstrom [2033] Bilancini et al. 2016]) but it is not clear how to extend these insights to SSDs. Our work solves this problem and enables a group of self self-interested agents to cooperate stably when they are continually learning and acting in shared environment.
is worth noting that goods and the tragedy of the commons (HARDIN, 1968. Kollock 1998 Ledyard 1994 Hardin 2009). We evaluate our method on both of these sequential social dilemmas and show that the agent population learns stable cooperative behaviors with great efficiency and stability. Visualization of the evolution process of cooperation shows that homophily effectively enables stable cooperation by preventing agents that conduct altruistic incentives from being exploited by second-order free-riders.
social dilemmas are classified into two broad categories: public
PRELIMINARIES AND RELATED WORKS
Social dilemmas (SDs) are among the most important settings used to study the emergence of cooperation. In social dilemma, there exists tension between the individual and collective rationality, in which individually rational behavior results in a situation where everyone suffers in the long run. Although studies on SDs have contributed significantly to the research of cooperation emergence for decades (Axelrod & Hamilton| 1987 Peysakhovich & Lerer 2017 Anastassacos et al. 2020), they focus on fixed policies, where the cooperative and defective strategies are actions to be chosen rather than policies to be learned. To be more realistic as in real-world situations, in this paper, we consider sequential social dilemmas (SSDs, (Leibo et al. 2017 Blanco et al. 20144).
An SSD can be modelled as a partially-observale M = (T, (A,): P,O, (2t), [R.). n. 7), where 7 is finite set of n agents and 7 is a discount factor. At each time step, agent i draws partial observation E Ω. of the state s E S according to the observation function ((s, i). Based on the observation, agent selects an action a, E A,, which together form a joint action a, leading to next state s' according to the stochastic transition function P(s'|s, (s, a) and individual rewards r; = [s a) for each agent. In SSDs, instead of taking atomic cooperation or defection actions, agents must learn cooperation or defection strategies consisting of potentially long sequences of environmental actions. The goal of each agent is to maximize the local RR, Paooo 12 7 R., az) )x)(s0 8 8, ag a).
general-sum Markov game (Lttmmnn 1994)
expected return: (s a) E aoooo
2

---

Under review as a conference paper at ICLR 2022
Altruistic incentive, including altruistically rewarding and punishing others, is known one of the solutions for social dilemmas (Kollock, 1998). However, it introduces the problem of second-order social dilemma (2nd-SD), which arises from each individual's 's inclination to free ride mechanism that is designed to solve the first-order social dilemma. To solve 2nd-SDs, previous works either introduce additional mechanisms, such as extra punishing mechanisms (Fowler [2055] Greenwood 2016), reputation mechanisms (Panchanathan & Boyd, (2044) or change the game settings, such as enabling the amount of public goods to grow exponentially with the number of contributors (Ye et al. 2016), considering corruption and power asymmetries (Übeda & Duéfiez-Guzmán, 2011). These works analyze the dynamics of predefined and fixed mechanisms and focus on non-sequential games.
We propose to solve 2nd-SDs in general cases using the tendency of homophily, which states that agents tend to have similar incentivizing behaviors if their environmental behaviors are similar. In the literature, homophily, frequently termed as assortative matching (Bergstrom, 2003), is often referred to the tendency for agents to interact with others of similar types (Fu et al. 2012 & Doebeli 2009 Ramazi et al.) 2016). These works assume that a game (such as Prisoner's 's Dilemma and Public Goods Dilemma) involves only a group of several agents from a large population. Based on the way they form the group, these works can be divided into two broad categories. (1) Agents can choose their partners to interact with (Rand et al. 2011 Aksoy 2015). However, in SSDs, agents do not have such an option and their partners are determined at initialization. They have to continually learn and act in a shared environment instead of a separate environment instance for each group. (2) There is a matching system that can auto-match agents with similar predefined types to join the game (Bergstrom 2003; Bilancini et al. 2016). However, in SSDs, agents assumed to have determined partners and thus the matching process changes the game settings. Moreover, the existence of such a matching system is an unrealistic assumption because the policy types (such as cooperation and defection) in SSDs cannot be predefined since temporally extended strategies are much more complex and can be dynamically mixed with cooperation and defection, especially during learning. Therefore, previous work studying homophily can not be applied to SSDs. Moreover, |Wang et al. (2018) also find that assortative matching of environmental behaviors cannot promote cooperation in SSDs. In contrast, our work encourages homophily on the level of incentivizing behaviors, which we find outperforming other algorithms on learning cooperation in SSDs. Furthermore, we discuss how homophily relates to other possible solutions in Appendix B.9
Recent works study some other mechanisms which may encourage cooperation in SSDs. Hughes et al. (2018) study the effects of inequality aversion, which bypasses the problem of second-order social dilemmaa because the punishment does not incur costs to any agents other than the punished ones. Jaques et al. (2019) find that encouraging mutual influence among agents can promote collective behaviors. We empirically compare with these methods in Sec. 5.2
In the following sections, will first provide motivating example to show the influence of SDs, 2nd-SDs, and how homophily can solve 2nd-SDs. Based on these analyses, we introduce how to encourage homophily in temporally extended cases in Sec.
3 MOTIVATING EXAMPLE: FRAGILE COOPERATION
In this section, we provide a detailed motivating example to explain first-order social dilemmas (Ist-SDs) and second-order social dilemmas (2nd-SDs) in the context of RL, and demonstrate that homophily can promote cooperation by alleviating the 2nd-SDs. For clarity, in this section, we use one-step games to illustrate our idea, which inspires our extension to sequential settings in Sec. 4
We adopt a classic problem setting of public goods dilemma (Hauert et al, 2007 2002a Semmann al. 2003; Hauert et al. 2002b). A population of n agents has an opportunity to create public good, from which all can benefit, regardless of whether they have contributed to the good. Specifically. there are three strategies (atomic actions). Contributors (C) pay a cost e to increase the size of public good by b. Defectors (D) do not contribute. The public good is uniformly distributed among cooperators and defectors. Agents can also choose to neither contribute to nor benefit from the public good, but receive fixed reward aT, as Nonparticipants (N). For clarity, conduct analyses using an illustrative example with n=100, b=3, c=1, 0=1. We also provide a sensitivity analysis regarding parameters in Appendix B.3 to consolidate that our conclusion generally holds.
3

---

Under review as a conference paper at ICLR 2022
A: Cooperation is fragile in 1st-SDs. We first showcase the influence of 1st-SDs. The Schelling diagram (Schelling, 1973] Perolat et al., 2017) (Fig. aT)) proves the existence of SDs in this case. To visualize the learning dynamics of MARL algorithms under Ist-SDs, we learn independent policies for agents using REINFORCE [Williams] 1992). In Fig. [bb, we plot the change of the proportion of cooperative agents in the population under 3 random seeds. We observe that the cooperation level oscillates during learning. For explanation, we visualize the dynamics of population constituent in ternary plot (Fig. ()). Each point X inside the equilateral triangle represents distribution of population members (Pc- (PC-PD, PD,,),, where PC + PD + PN = 1, pc: PD. pN are represented by the distances from point X to the edges ND, C.N, and CD, respectively. Trajectories in Fig. (e) correspond to the curves with the same color in Fig. [b). We can observe that all the trajectories rotate counterclockwise in the vicinity of vertex N regardless of the starting position.
Formally, we calculate the closed-form gradients of agents" true value functions and visualize the gradient field in dd). It can be observed that cooperation is not stable solution, which can be easily taken over by defectors, and then by nonparticipants, This phenomenon is the result of Ist-SDs, where cooperation is exploited by defection, eventually leading the system to a very ineffective state. We refer readers Appendix for the detailed proof.
Completely nonparticipating population
Completely defecting population
Conneettoor Propor
0.6
Completely
couperating
populition
2000 #000 Berstion
6000
5000
10000
#Cther cooperatora (a) Schelling diagram
Oscillating cooperation
Oscillation policy spaco
(d) Gradicat field the policy space
Figure First-order social dilemmas.
B: Unexploitable altruistic incentives make cooperation possible. To introduce altruistic incen- tives into the system, we add Punishers (P) as the fourth type of strategy. The same as contributors, punisher contributes to and benefits from the public good, and importantly, it also pays cost ie to incur punishment p on defectors. This punishment is altruistic because it reduces its own immediate reward but benefits the team in the long run. To show the effect of altruistic incentives, we need to guarantee that no agent can exploit altruistic incentives by being a pure contributor that does not pay cost to punish defectors. Therefore, we first consider the setting where punishers also pay a cost ark to incur a punishment op on the pure contributors for not punishing defectors (Fowler) 2005). We denote this punishing type by PA,, which represents a kind of unexploitable altruistic incentives.
For simplicity, we illustrate our analyses with p=2, A=0.35, a=1 (sensitivity analysis is deferred to Appendix [B.3). Each horizontal plane in Fig. 2]a) shows the Schelling diagram under the
corresponding number of first-order defectors. Similar Fig. cc). we visualize the dynamics of independent learners under this situation in Fig. b) using a quaternary plot (refer to Appendix A.2 for more details). We see that although two trajectories are trapped in the C-D-N plane and similar to those in Fig. [ c), one of the three trajectories finds the stable cooperation solution PA.
We plot the closed-form gradients in Fig. a), where the green (blue) region indicates that population initialized there would converge to cooperative (non-cooperative) solution. This figure proves that introducing unexploitable altruistic incentives creates a "safe region" near PA, and the populations initialized there converge to cooperative solutions.
C: Exploitable altruistic incentives suffer from 2nd-SDs, which again lead to fragile coopera- tion. Now we restrict the punishments incurred by punishers, and they can only pay cost k to incur a punishment p on defectors. Now the punishers can be exploited by pure cooperators who do not pay for but benefit from punishments. We call this type of punishers the exploitable punishers. On each horizontal plane in Fig. c). we show the Schelling diagram with different numbers of first-order defectors, which reveals the existence of second-order social dilemmas.
Formally, assume that the probability of agent taking three actions are giC g.., B%.1 gi.P. respectively. It can be derived (Appendix E) that the gradient of agent i's value function w.r.t. the probability of second-ords -oder cooperative action gi.P minus the the gradient w.r.t the probability of second-order defective action 0i.C is kk Ejts Go.D. where k > is the punishment cost. The gradient is negative
4

---

Under review as a conference paper at ICLR 2022
for any 8i.1, which indicates that second-order cooperators would be taken over by second-orde defectors. This is the second-order social dilemma. The result is that only strategies C, D, exist, after which the system degrades due the 1st-SD as discussed before. We plot the closed- form gradients in Fig. dd), from which we observe that the "safe region" disappears, and, for any initialization, the population ends with non-cooperation.
2nd cooperating 2nd ordier defecting
order cooperaning
2nd order defecting
U order delcoor
Rostord
Yary Heward
2nd-ceder cooperators
2nd order cooperators
(a) Schelling diagram (wnesploitable pumishers)
(b) Trnjectory in the policy space
(c) Schelling diagram (erpioitable punishers)
Gradient field
(uaespioitaable punishars)
(erpionialle
Figure 2: Unexploitable and exploitable altruistic incentives.
Takeaways We conclude that only uncxploitable incentives make cooperation stable solution. becomes particularly problematic in temporally extended cases, where the incentivizing policies need to be learned. It is typical that some agents would learn altruistic incentives earlier than others. However, as analysed before, these altruistic agents will be exploited by other agents, leading degraded altruistic behaviors. Further, with collapsed altruistic incentivizing mechanisms, the population falls back to a Ist-SD, making cooperation much less likely to emerge.
D: Homophily solves second-order social dilem- mas. To show the effect of homophily, based on the settings in part C, we further encourage agents with similar acting behaviors to have similar incentiviz- ing behaviors. Since only contributors and punishers have the same acting behavior of contributing to the public good, we encourage their incentives to be the same by converting the minority of P and C to the majority with a probability of 0.2.
Nor pepertinn
D
(4) Gradient fickl (oncptlnnioble pomsherr) (b) Gindient field (/Ronophhiy)
Figure 3: Homophily solves second-order so-
We plot the closed-form gradient in Fig. 3b). We find that the "safe region" reappears. The gradient w.r.t. gi. minus the gradient w.r.t gi.C is -k Σjzs Gi.D 2Asign (Bi. )E);
cial dilemmas.
(.:C)) min P..P). which is positive when close to point P. Interestingly, the "safe region" is larger than that in Fig. a). In this way, we conclude that homophily helps solve 2nd-SDs.
By this motivating example, show that homophilic incentives encourage cooperation. However, this study focuses on one-step games and predefines the mechanism of punishers. The question is how to encourage homophily in realistic settings without depending on any predefined mechanisms.
4 METHODS
As discussed in the previous section, 2nd-SDs disturb the learning process of incentivizing actions agents who learn altruistic incentives earlier tend to be exploited by other agents. Consequently, the altruistic incentivizing behaviors are typically taken over and the population would fall back to 1st-SDs, resulting in a hopeless loop.
In this section, we discuss how to introduce homophily into sequential social dilemmas so that the loop be broken and cooperation is possible emerge and stabilize. We propose encourage homophily by encouraging agents with similar acting (environmental) behaviors to have similar incentivizing behaviors. We now describe our learning framework shown in Fig.
4.1 INCENTIVIZING AND ENVIRONMENTAL BEHAVIOR LEARNING
To enable incentivizing behaviors, we add incentivizing actions to the action space. We use 0;-- to denote the incentivizing action from to j. The action d;-z induces inter-agent reward 1/ ri
5

---

Under review as a conference paper at ICLR 2022
to agent j. Here, 17" 0 is a scaling factor. In this paper, we consider three types of incentivizing actions with positive. negative, and zero ri-+j. respectively. Since we consider altruistic incentives, the action 0:-z itself costs r/|r where 1f > 0 is also scaling factor.
Each agent learns two Q functions, for selecting envi- ronmental actions and incentivizing actions, respec- tively. At each step, agents first simultaneously select environmental actions a, according to Q6. Q which based on local and is parameterized by 0,. Then, conditioned on en- vironmental actions of other agents, a-i, each agent i decides its incentivizing actions a;-+-i according to Que ((Ti, a.:), ai-+;) parameterized by Φi.
EPfict
Fawderd
(Ti, d;), -booervtrevvti history
Qlini
@ L
2 M
O
My
One question is what rewards should be considered when training Q% Intuitively, incentivizing ac- tions are expected to positively influence the return given by the environment. Therefore, we include en- vironment rewards r;. We also consider the costs of incentivizing actions to prevent agents from exces- sively giving incentives. Moreover, we ignore the rewards received from other agents, which can effectively prevent agents from learning trivial and detrimental policies, such keeping exchanging positive incentives regardless of the observations.
(tt.ahy
(claa)
Agent
Agent
Hamophily losa for agert
Figure 4: Homophily learning framework.
Another question of learning Q2 is that it requires 3--1 outputs using conventional deep Q- network and most output heads would remain unchanged for long stretches of time. To solve this problem, agent i can learn agent j * i. However, this alternative arises considered when training Qer but they do not present an explicit decomposition over agents. To solve this problem, we propose to estimate Q iine
incentivizing Q functions Q:!!!. eaach of which corresponds
question because the environment rewards
summation:
Q inc ((Ti, a(--)) = Σ 2 ((T,, Qz-z)) jgt
Here, parameters of Que are shared to accelerate training. This formulation is similar to VDN (unne hag et al. 2018), but sum incentivizing Q's of single agent, rather than Q's of different agents.
With these formulations, we train each agent's incentivizing Q by minimizing the following TD loss:
Ci (o:) = ED[(r= - " I + + inc max Shiine 0, ((T/, a':): d( Qiiiie ((T,, a-:), a; -..-))
(2)
where nn is the discount factor, o7 is parameters of a target network that periodically copied from Φi. and the expectation is estimated by uniform samples from a replay buffer D.
Environmental Q function is trained with rewards from the environment and the incentives received from other agents, and we minimize the following TD loss for learning Qieen.
C.Th (0.) = ED (2.
Di (T, a:))
Here, the expectation is estimated with uniform samples from the replay buffer D, y r vf Σjjeeーー max.; -- (T/, a() is the target for environmental Q-learning. 0, is parameters of target network that are periodically copied from 0,.
4.2 HOMOPHILY
Directly learning incentivizing policies be difficult due to second-order social dilemmas discussed in Sec. To solve this problem and inspired by the stateless case in Sec. B Part D, we encourage agents to be homophilie, ie.., agents with similar environmental behaviors should have

---

Under review as a conference paper at ICLR 2022
Homophily (Durg) Homophily
LO
Social infuuence
Inequity Aversion
Setfish Actor Critic
actios
40
Cleanup (o=3)
Ciconup in-31
Collec Rutuum Main
Cleanup (6=
Collectuvn Renurn Men
325
Harvest (n-18)
180
100
30
13
Collectire
10
50
0.0
0.5
2.0
Figure Comparison of our method against baselines and ablations. similar incentive behaviors, which can be expressed a loss to be minimized:
Chomo (o:) ED
Σ S (i.j)s (1.5:
(4)
where ShmHh is 1 or O, indicting the environmental behaviors are similar or not. Sime measures the similarity between incentivizing behaviors of two agents.
The first question is how to define (t (i, j; Φz). The idea to measure the similarity between two agents' incentive behaviors by comparing their incentive actions to each of other agents. For each agent i, we measure its similarity to agent j as:
S (i, 0:) = E CE (Pa_ AE(
|| ((T, | ((T,,
(5)
where (-) is the softmax function, -a.-2 is categorical distribution agent j's incentive actions, with probability of I for the action that agent takes for agent & (aj-*k). The cross entropy CE[-IH-] measures the distance between these two distributions.
As for Seny if we parameterize and learn it with giee using Chome, we may get trivial solutions. For example, Senv may be a constant 1, in which case Chome is minimized given the same Sine To avoid such solutions, we propose use non-parametric Semy Details are discussed in Appendix
With these components, the loss for agent to learn environmental and incentivizing behaviors is:
(0i,, (b:) L. (0:) + xinc C. homa L. chooo (db),
where inn and X homo are scaling factors. Agents learn their policies independently.
EXPERIMENTS
Our experiments aim answer the following questions: (1) Can homophily promote the emergence of cooperation? (Sec. 5.2h (2) What the contribution of each component in the proposed learning
framework? (Sec. 5.3) (3) How does cooperation emerge and evolve under homophilic incentives?
(Sec. 5.4 (4) How does homophily affect incentive behaviors? (Sec. 5.5)
5.1
EXPERIMENTAL SETUP
We test method in SSDs. There two broad categories of multi-person social dilemmas (Kollock 1998): Public goods dilemmas and Tragedy of commons dilemmas. In this paper. we consider sequential versions of these two dilemmas, Cleanup and Harvest (Leibo al., 2017). In our learning framework, each agent has an environmental and incentivizing Q function. The Q network architecture is the same for all agents but they do not share parameters. For other details of environments and our method, we refer readers to Appendix C
5.2
PERFORMANCE
To test whether homophilic learning can promote the emergence of cooperation, we test our method on Cleanup and Harvest with different numbers of agents and compare against various baselines: LIO (Yagg et al. 2020). Inequity Aversion (Hughes et al. 2018), Social Influence (Jaques et al. be found in Appendix
2019 and Selfish Actor- Critie. The details of baselines
We test all methods with random seeds and show the mean value as well as 95% confidence intervals in Fig. 5 It can be observed that method helps agents learn cooperation with efficiency and
7

---

Under review as a conference paper at ICLR 2022
Team Retum
Behaviors
Description
Phose 1: Exploring Incentiies
++
+3
Phase 2: Second Social Diemmas
2.0M
Homophily Solves
3.3M
4+1
6
3.9M
Fhase d; Stabilized Cooperation
5.0M
4+2
+-3
Agents
Apples
Wastes
Posiive incentives
Negative Incentives
Figure 6: Evolution of cooperation in Cleanup. Left: Sum of environmental rewards received by all agents. Middle: Environmental and incentivizing behaviors at four different stages of learning. Right: Corresponding descriptions.
stability. In comparison, baseline algorithms either cannot learn any cooperation strategies or the cooperation level oscillates. Inequity aversion oscillates on Cl Cleanup (n=5), which can be proved by its large confidence intervals, and cannot learn cooperate on Harvest (n=10). Social influence proves that cooperation can be achieved by encouraging agents to influence each other, but it requires many samples (typically 100M as reported Jaques et al. (2019) to learn cooperative strategies. In contrast, method needs around 5M samples to learn stable cooperative strategies. LIO can learn cooperation on Cleanup (n=3), but less effective in dilemmas with more agents.
5.3 ABLATION STUDY
There are three contributions that characterize method. (1) First and the most important, the homophily learning objective. (2) Discrete incentive actions and factored incentive Q-functions for each agent. (3) Excluding received incentives when training incentive Q-functions. In this section, we design the following ablations to test the contribution of each of these components.
(1) Without homophily (w/ homophily). We exclude the homophily loss Chomo from our learning objective. We can see that the team performance drops significantly, especially in tasks with more agents. Moreover, without homophily loss, method performs worse than all baselines on Cleanup (n=5) and (n=10). These observations suggest that our method works mainly because of the homophily loss. (2) Continuous incentivizing actions. Ablation Cont. inc. actions shows the influence of discrete actions. We learn a continuous incentivizing rewarding function for w/o homophily. We can observe further performance decrease on Cleanup (n=3) and Harvest (n=10). We hypothesize that this is because the search space for incentivizing policies grows, making the strategy more difficult to learn. (3) Train incentivizing Q's with received incentives. We ignore incentives received by agents when training incentivizing strategies. For comparison, ablation w/ inc. shows what would happen if they are included. We can observe that w/ inc. significantly underperforms the original method on all environments. The reason is that agents learn to give each other positive incentives excessively regardless of observations. Since received incentives are also considered in Q-leaming for acting behaviors, excessive incentives would overwhelm environmental rewards and significantly hurt learning performance.
5.4 EVOLUTION COOPERATION
To clearly show the evolution of emergent cooperation, the problem of 2nd-SDs, and how homophily alleviates this problem, according to different team returns, we select four stages during learning and analyze their corresponding behaviors. The detailed stage partition be found in Fig.
8

---

Under review as a conference paper at ICLR 2022
Phase 1: Exploring incentives. During this stage, agents are learning basic dynamics of the environ- ment. For example, as shown in the first row of Fig. 6 agents have not learned to eat apples to get rewarded. Meanwhile, during exploration, agents occastonally give incentives to agents who cleaned wastes (11 + 3), which enables learning incentivizing behaviors in the following stages.
Phase2 2: Second-order social dilemmas. Some agents (the pink agent in the second row of Fig. 6 learn to give positive rewards to cleaning agents altruistically. However, other agents (e.g.. orange and blue) typically do not give positive incentives but can enjoy the benefits of others' altruistic behaviors. We can observe an oscillation of team return during this stage. This is the effect of 2nd-SDs. If there are no additional restrictions (such as homophily) to deal with this problem, the team will fall back to the state where no one wants to perform incentives, resulting in the collapse of cooperation.
Phase 3: Homophily solves 2nd-SDs. After some oscillations of cooperation, the homophily loss gradually encourages agents with similar environmental behaviors to have similar incentivizing behaviors. As shown the third row of Fig. [ although there are still some noisy incentives at this stage, agents who are close to the apple-spawning region simultaneously reward cleaning agents and punish those who are next to the wastes but do not clean them. These incentivizing behaviors indicate that the population has gotten over the 2nd-SD with the help of homophily. Correspondingly, the team return increases in this stage.
Phase 4: Stabilized cooperation. are no second-order free-riders and all incentive rewards are given by agents harvesting apples to agents in the region of wastes. Moreover, screenshots show that agents learn an efficient division of labor - three agents eat apples and get environmental rewards while two agents clean the wastes and get rewards from harvesting agents. These incentivizing and environmental behaviors are a stable solution only when homophily learning objective is included.
Taking ad advantage of the effect of homophily, during this stage, there
Based on the illustrations of the evolution of cooperation, conclude that homophily prevents altruistic incentivizing behaviors from being exploited by second-orde free riders, and thus solves the problem of 2nd-SDs and leads stable cooperation. For detailed agent behaviors at different stages, we refer readers to our online vidco!")
5.5 HOMOPИILIC INCENTIVES
In previous sections, we show that homophilic incentives can promote cooperation, but how homophily affects incentiviz- ing behaviors remains largely unclear. To make up for this, we compare our method with the ablation w/o homophily on Cleanup (n=3) by plotting their collective return and altruistic incentive (the average incentive that each Cleaner receives at
Collective Return
Homophily (Gurs)
w/l homaphily
Altruisti Incentives
0.4
each time step) in Fig.1
0.2
0.0
We observe close connection between incentives and co- operation performance. Intuitively, the more positive incentives cleaners receive, the more apples expected to spawn and be collected. However, without homophily, the received incen- tives oscillate dramatically, which is caused by second-order social dilemmas and is in line with the discussions before. In comparison, our method keeps incentivizing cleaners and thus learn cooperation with stability.
-0.2
(mill
Figure 7: Homophily eliminates in- centive oscillations.
6 CLOSING REMARKS
In this paper, we study the problem of cooperation emergence. We show that altruistic incentives make cooperation possible but cannot stabilize due to second-order social dilemmas. We then formally and empirically show that homophily, a common tendency typical of humans, may solve this problem. Combined with deep MARL, we propose implementation of homophilic learning for sequential social dilemmas. We expect that our work can encourage future works on studying the exciting topics of cooperation emergence, evolution, and stability.
https://sitent http::///iieessgggleee httpa//ggge...oooo///////eenooao 1y/

---

Under review as a conference paper at ICLR 2022
Reproducibility The source code for all the experiments along with README file with instruc- tions on how to run these experiments is attached in supplementary material. In addition, the settings and parameters for all models and algorithms mentioned in the experiment section detailed in Appendix C.
REFERENCES
Erol Akçay and Joan Roughgarden. The evolution of payoff matrices: providing incentives to cooperate. Proceedings of the Royal Society B: Biological Sciences, 278(1715)2198-222 -200, 2011.
Ozan Aksoy. Effects of heterogeneity and homophily cooperation. Social Psychology Quarterly, 78(4):324-344 344, 2015.
Nicolas Anastassacos, Stephen Hailes, and Mirco Musolesi. Partner selection for the emergence of cooperation in multi-agent systems using reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7047-7054, 2020.
Axelrod and W. D. Hamilton. The evolution of cooperation. Science, 1(1):1390-136, 1987.
Robert Axelrod and William D. Hamilton. The Evolution of Cooperation. 1984.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
Theodore C Bergstrom. The algebra of assortative encounters and the evolution of cooperation. International Game Theory Review, 5003):11-225 2003.
Ennio Bilancini, Leonardo Boncinelli, and Jiabin Wu. The interplay of cultural aversion and assortativity for the emergence of cooperation. Available at SSRN 2773097, 2016.
Mariana Blanco, Dirk Engelmann, Alexander K Koch, and Hans-Ther Normann. Preferences and beliefs in sequential social dilemma: within-subjects analysis. Games and Economic Behavior, 87:122-, 2014.
Jean-François Bonnefon, Azim Shariff, and lyad Rahwan. The social dilemma of autonomous vehicles. Science, 352(6293) 2016.
Robert Boyd. Mistakes allow evolutionary stability in the repeated prisoner's dilemma game. Journal of theoretical Biology, 136(1) (6:45567556, 1989.
Robert Boyd, Herbert Gintis, Samuel Bowles, and Peter Richerson. The evolution of altruistic punishment, Proceedings of the National Academy Sciences, 100(6)3551-3353,
2003. 2003..
Stuart Bryce Capstick. Public understanding of climate change social dilemma. Sustainability, (8):3484-3501, 2013.
Yunmei Chen and Xiaojing Ye. Projection onto a simplex, 2011.
Anna Dreber, David G Rand, Drew Fudenberg, and Martin A Nowak. Winners don't punish. Nature, 452(7185):3483511 2008
Ernst Fehr and Simon Gächter. Altruistic punishment in humans. Nature, 415 2002.
Jeffrey A Fletcher and Michael Doebeli. A simple and general explanation for the evolution of altruism. Proceedings of the Royal Society B: Biological Sciences, 13611654):13-19, 2009.
Yuk-fai Fong and Jay Surti. The optimal degree of cooperation the repeated prisoners' dilemma with side payments. Games and Economic Behavior, 67 2009.
James H Fowler. Altruistic punishment and the origin of cooperation. Proceedings of the National Academy of Sciences, 102(19):7077-704,, 2005.
Feng Fu, Martin A Nowak, Nicholas A Christakis, and James Fowler. The evolution of homophily. Scientific reports, 2(1):1-6, 2012. 2012.
10

---

Under review as a conference paper at ICLR 2022
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprint
2016.
Garrison Greenwood. Altruistic punishment can help resolve tragedy of the commons social dilemmas. In 2016 IEEE Conference on Computational Intelligence and Games (CIG), pp. 1-7. IEEE, 2016.
Werner Güth. An evolutionary approach to explaining cooperative behavior by reciprocal incentives. International Journal of Game Theory, 24(4):323 344, 1995.
HARDIN. Tragedy of the commons. new series, vol. 162, no. 3859, 1968.
Garrett Hardin. The tragedy of the commons. Journal of Natural Resources Policy Research, 1(3): 243-253, 2009.
Hauert, Christoph, Monte, Silvia, De, Hofbauer, Josef, Sigmund, and Karl. Volunteering as red queen mechanism for cooperation in public goods games. Science, 2002a.
Christoph Hauert, Silvia De Monte, Josef Hofbauer, and Karl Sigmund. Replicator dynamics for optional public good games. Journal of Theoretical Biology. 218(():187-194, 2002b.
Christoph Hauert, Arne Traulsen, Hannelore Brandt, Martin A Nowak, and Karl Sigmund. Via freedom coercion: The emergence of costly punishment. Science, (1665833):1905-1110 2007.
Morris Hirsch, Stephen Smale, and Robert Devaney. Differential equations, dynamical systems, and an introduction to chaos. Academic press, 2012.
Edward Hughes, Joel Z Leibo, Matthew Phillips, Karl Tuyls, Edgar Duemiez-Guzman, Antonio Gareía Castañeda, Jain Dunning. Tina Zhu, Kevin McKee, Raphael Koster, et al. Inequity aversion improves cooperation in intertemporal social dilemmas. In Advances in Neural Information Processing Systems, pp. 3330-3340, 2018.
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, Dj Strouse, Joel Z Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International Conference on Machine Learning, pp. 3040-3049, 2019,
Donald Kennedy. 125. Science, 309(5731):19-20, 2005.
Peter Kollock, Social dilemmas: The anatomy of cooperation. Annual Review of Sociology, 24: 183-214, 1998.
Michael Kuhlman and Alfred F Marshello. Individual differences in game motivation as moderators of preprogrammed strategy effects in prisoner's dilemma. Journal of personality and social psychology, 32(5):922, 1975.
John Ledyard. Public goods: A survey experimental research. 1994.
Joel Z Leibo, Vinicius Zambaldi, Mare Lanctot, Janusz Marecki, and Thore Graepel. Multi-agent reinforcement learning in sequential social dilemmas. In Proceedings of the 16th Conference Au- tonomous Agents and MultiAgent Systems, pp. 464-473. International Foundation for Autonomous Agents and Multiagent Systems, 2017.
Michael L. Littman. Markov games as framework for multi-agent reinforcement learning. Morgan Kauffman Publishers, Inc., 1994.
Andrei Lupu and Doina Precup. Gifting in multi-agent reinforcement learning. In Proceedings of the 19th International Conference on Autonomous Agents and MulriAgent Systems, pp. 789-797, 2020.
Thomas Mussweiler and Axel Ockenfels. Similarity increases altruistic punishment in humans. Proceedings of the National Academy of Sciences, 1 191148) 2013.
Andrei Novikov. PyClustering: Data mining library. Journal of Open Source Software, 4(36):1230 apr 2019. doi: 10.21 (.21100//0ss.00 01120.. URL /ttppps//iee...onn/0...1111///// 01230
11

---

Under review as a conference paper at ICLR 2022
Elinor Ostrom, James Walker, and Roy Gardner. Covenants with and without sword: Self- governance is possible. American political science Review, 86(2):404-417, 1992.
Craig Packer, Dennis A Gilbert, AE Pusey, and SJ O B'Brien. A molecular genetic analysis of kinship and cooperation in african lions. Nature, 35 351(6227):562-566 1991.
Karthik Panchanathan and Robert Boyd. Indirect reciprocity can stabilize cooperation without the second-order free rider problem. Nature, 432(7016)::499 2004.
Dan Pelleg, Andrew W Moore, et al. X-means: Extending k-means with efficient estimation of the number of clusters. In International Conference of Machine Learning, volume 1, pp. 727-734, 2000.
Elizabeth Pennisi. How did cooperative behavior evolve? Science. 309(5731):93-93, 2005.
Lawrence Perko. Disferential equations and dynamical systems, volume 7. Springer Science & Business Media, 2013.
Julien Perolat, Joel Z Leibo, Vinicius Zambaldi, Charles Beattie, Karl Tuyls, and Thore Graepel. A multi-agent reinforcement learning model of common-poo resource appropriation. arXiv preprint arXiv: 0660000,0600.... 2017.
Alexander Peysakhovich and Adam Lerer. Consequentialist conditional cooperation in social dilem- mas with imperfect information. arXiv preprint arXiv:1710.06975. 2017.
Pouria Ramazi, Ming Cao, and Franz J Weissing. Evolutionary dynamics of homophily and het- crophily. Scientific reports, 6(1):1-9, 2016.
David G Rand and Martin A Nowak. The evolution of antisocial punishment in optional public goods games. Nature communications, 2(1):1-7, 2011.
David Rand, Samuel Arbesman, and Nicholas A Christakis. Dynamic social networks promote cooperation in experiments with humans. Proceedings of the National Acudemy of Sciences, 108 148):19193-19198, 2011.
Ammon Rapoport, Gary Bornstein, and Ido Erev. Intergroup competition for public goods: Effects of unequal resources and relative group size. Journal of Personality and Social Psychology, 56(5): 748-756, 1989.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep aggntt reinforcement learning. In International Conference on Machine Learning, pp. 4292-4301, 2018.
James K Rilling, David A Gutman, Thorsten R Zeh, Giuseppe Pagnoni, Gregory S Berns, and Clinton D Kilts. neural basis for social cooperation. Neuron, 35(2):395 2002.
Bo Rothstein. The universal welfare state as a social dilemma. Rationality and society, 13(2): 213-233, 2001.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philiph H. S. Torr, Jakob Foerster, and Shimon Whiteson. The StarCraft Multi-Agent Challenge. CoRR, abs/ NS/11902.0044.3 2019.
Thomas C Schelling. Hockey helmets, concealed weapons, and daylight saving: A study of binary choices with externalities. Journal of Conflict resolution, 17(3)3311-428, 1973.
Dirk Semmann, Hans Juergen Krambeck, and Manfred Milinski. Volunteering leads to rock-paper- scissors dynamics in public goods game. Nature, 425(6956))330,, 2003.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki. Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Vecopsieco networks for cooperative multi-agent learning based team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2085-2087. International Foundation for Autonomous Agents and Multiagent Systems, 2018
12

---

Under review as a conference paper at ICLR 2022
Francisco Ubeda and Edgar A Duéñezz-uzzmae Power and corruption. Evolution: International Journal of Organic Evolution, 65(4):1 2011.
Eugene Vinitsky, Natasha Jaques, Joel Leibo, Antonio Castenada, and Edward Hughes. An open source implementation of sequential social dilemma games. https:/ htte:///gtthu.u.t com/
eugenevinitsky wtt.skkkyeeeeeeaaaaaaaaaaaaaaaee sacaalsssaal___ di lemma _aaaas_ammss_____ 2019. GitHub repository.
Jane X Wang, Edward Hughes, Chrisantha Fernando, Wojciech M Czarnecki, Edgar A Duéñez- Guzmán, and Joel Z Leibo. Evolving intrinsic motivations for altruistic behavior. arXiv preprint arXiv:1811.059311 2018.
Tonghan Wang. Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang. Rode: Learning roles to decompose multi-agen agent tasks. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
Weiran Wang and Miguel Á. Carreira- Carreira-Perpiñan. Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application, 2013.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-255 256, 1992.
Jiachen Yang, Ang Li, Mehrdad Farajtabar, Peter Sunehag, Edward Hughes, and Hongyuan Zha. Learning to incentivize other learning agents. arXiv preprint arXiv:2006. 0605/, 2020.
Hang Ye, Shu Chen, Jun Luo, Fei Tan, Yongmin Jia, and Yefeng Chen. Increasing returns scale: The solution to the second-order social dilemma. Scientific reports, 6(1):1-10, 2016.
A DETAILS OF MOTIVATING EXAMPLE
A.1 PROBLEM SETTINGS
From the perspective of multi-agent reinforcement learning, we provide detailed motivating example to explain both first- and second-order social dilemmas, and demonstrate that homophily can promote cooperation by alleviating second-order social dilemmas. The motivating example is based on the classic problem setting from Fowler (2005) for its modeling of the public goods dilemma.
A population of n agents has opportunity to create public good that will be equally distributed to all participants. There are several possible strategies in this population. Contributors (C) pay a cost c to increase the size of public goods by b. Defectors (D) do not contribute but benefit from the public goods. Agents can also choose to neither contribute to nor benefit from the public goods, but receive fixed reward o, Nonparticipants (N). To introduce altruistic incentives into the system, we add Punishers (P) as the fourth type of strategy. A punisher contributes to and benefits from the public goods, which is the same as contributors, and importantly, it also pays a cost & to incur a punishment defectors. To guarantee that no agent can exploit altruistic incentives by being pure contributor that does not spend energy punishing defectors, we consider unexploitable punishers (PA) who also pay cost al to incur punishment op on the pure contributors for not punishing defectors.
In Sec. 3 Part A, to showcase the influence of first-order social dilemmas, we consider Contributors (C). Defectors (D), and Nonparticipants (N). Assume that the proportion of each strategy is Pc, PD. and pv. respectively, and PC + PD + PN 1. Then the rewards each step are
I-PN
C,
Contributors (C)
bpc I-PN' 0,
Defectors (D)
Nonparticipants (N)
From Eq. 7 we can see that the rewards of defectors are always higher than those of contributors, which leads to first-order social dilemmas (Ist-SDs SDs).
In Sec. Part B, to show the effect unexploitable altruistic incentives, we consider Contributors (C), Defectors (D), Nonparticipants (N), and Unexploitable Punishers (PA). Assume that the proportion
13

---

Under review as a conference paper at ICLR 2022
of each strategy is pc- PD, PN. and PAA, respectively, and Pc + PD + PN PPA 1. Then the rewards at each step are
bpotppa) opppA>
Contributors (C)
1 PN
Mpo+pPAl PPPAi
Defectors (D)
1-P
(8)
0,
Nonparticipants (N)
bpp+tPA)) kpD akpo Unexploitable Punishers (PA)
1-PN
In Sec. 3 Part C. we restrict the punishment incurred by punishers, and they can only pay cost k to incur punishment, p on defectors. Therefore, in this part, we consider Contributors (C), Defectors (D), Nonparticipants (N), and Exploitable Punishers (P). Assume that the proportion of each strategy is pc, PD. PN, and pp, respectively, and PC + PD + PN + PP = 1. Then the rewards each step are
b(potpp)
C2
Contributors (C)
Px PpP, 1-Px
b(pc+pp)
Defectors (D)
(9)
0, b(pctpel
Nonparticipants (N)
kpD:
Exploitable Punishers (P)
1-9N
From Eq. 9 we can find that the rewards of pure contributors are always higher than those of exploitable punishers, which leads to the second-order social dilemmas (2nd-SDs).
In Sec. 3 Part D, to show the effect of homophily, based on the settings of Eq. which suffer from 2nd-SDs, we further encourage agents with similar acting behaviors to have similar incentivizing behaviors. In the considered setting, only contributors and punishers have the same acting behavior of contributing to the public goods. Therefore, we encourage their incentivizing behaviors to be the same by converting the minority of punishers and contributors the majority of them with probability 0.2. (For example, if 30% of the agents are punishers and 20% of them are contributors, then contributors become punishers with probability 0.2.)
In all our simulations, we set n = 10, b= 3, c 1, =1 p 0.35, and a = A sensitivity analysis is provided in Sec. 3 of the main text demonstrate that observation and conclusion solid for a large range of parameters, Agents use REINFORCE policy gradients (Williams) 1992) to learn independent local policies for selecting strategies (atomic actions).
A.2 VISUALIZATION AND COORDINATE TRANSFORMATION
In order to demonstrate the evolution population, we employ two visualization methods, the ternary plot (for PC.PD. PD. PN in Sec. 3 Part A) and quaternary plot (for PC; PD,,,N PPA in Sec. Part B and pc,PD; PN, pp in Sec. Part D).
Ternary plot, an equilateral triangle periphery with several tra- jectories inside, reveals the dynamics of population constituents (three different strategies), as shown in Fig. I(c) in the paper. Each point X inside the equilateral triangle represents distribu- tion of the population (pc, PD. PN).. where PC - PD + Px 1. Pc. PD. and PN represented by the distance from point X to the edge ND. CN, and CD,, respectively. This corresponds the fact that the sum of distances from any interior points of equilateral triangle three sides is fixed value. Naturally, we can then depict the evolution of the percentage of three strategies curve inside the triangle.
Figure 8: Population policy space in the 3-dimensional rectangular co- ordinate system.
However, ternary plot can only visualize the evolutionary trajectories of three strategies. When the fourth strategy is introduced, we resort to the quaternary plot in 3-dimensional space. For any interior point X of a regular tetrahedron CDN (Fig. g). the sum of distances from X to four faces NCD, PCN, DPN, and PCD is constant. Therefore,
still interior point X to
14

---

Under review as a conference paper at ICLR 2022
represent population distribution and represent Pc-PD. P..P.. by the distances from X to different faces.
Point-to-face distances have to be transformed into rectangular coordinates before trajectories can be plotted. We now describe the details of coordinate transformation.
We first plot regular tetrahedron in the three-dimensional rectangular coordinate system, with 4: 4: 0), ( x2 _ve 0) as in Fig. 8 To simplify 4:
four vertices P(O, 0, 1), N O, 0), C(- C2-v2,
notations, denote the distance from an interior point X to faces DNP. CNP. CDP, and CDN by Pc. PD. PN. and pp, respectively.
It can be calculated that the equation for plane PNC' is
/2x + Voy + 2
and the equation for plane iN
V2r V6y + 2
Next, using formula in analytical geometry for calculating the distance from a point to a given plane, can derive
pn v2 Voy PC = 3/v2x VBy + = 1/,
(10)
Pp
Finally, we solve the above system equations and get
222 (2-3pp 3pc 2pp),
4
(pD -P)-
(11)
PP,
With Eq. [T] we can calculate the corresponding coordinate in the three-dimensional rectangular coordinate system of any population distribution. Connecting all points into curve gives the 3D) quaternary plot.
B
MORE RESULTS AND ANALYSES
B.1 MOTIVATING EXAMPLE: LIMIT CYCLE
In Fig. (d) of the paper, visualize the gradient field within the population policy space when exploitable punishers are considered. There, conclude that independent REINFORCE learners can never converge to cooperative solutions in this setting, As special case, show that population may rotate infinitely in the non-cooperative region of the policy space.
P
In Fig.
present limit cycle in the population policy space. A limit cycle is a closed trajectory, and any population initialized on the cycle would keep looping over it and never converge to stable solution. It is worth noting that although homophilic incentives make cooperation possible (Fig. 3(b) in the main text), they cannot eliminate limit cycles in the non- cooperative (blue) region.
Figure 9: Limit Cycle.
B.2 MOTIVATING EXAMPLE: DEGREE OF НOМОPIILLY
In Sec. 3 Part D, encourage agents with similar acting behaviors to have similar incentivizing behaviors by converting the minority of punishers and contributors to the majority of them with probability À (A=0.2 in the paper). We call À the degree of homophily.
To further show the influence of X, in Fig. I0 we plot how the cooperation proportion changes with respect the degree of homophily. Cooperation proportion is the ratio of the volume of the
15

---

Under review as a conference paper at ICLR 2022
Cooperation
Proportion
0.40
0.05
0.30
0.25
0.20
0.10
0.05
0.00
0.20
Degree of homophily
Noo-cooperative
Copperative
Gradient Field
Figure 10: The more homophilic a population is, the more possible cooperation would emerge. The cooperation proportion and gradient field in the population policy space under different degrees of homophily are shown. The increasing volume of the "safe region" and the cooperation proportion increases with the degree of homophily.
PA
Non-ocoperativee
Cooperative
N
D
(a) Gradient field (unexploitablle punisher) (b) Gradient field (Homophily)
(c) Gradient field (Inequity Aversion)
Figure 12: Gradient fields of our method against baselines
cooperative (green) region to the volume of the regular tetrahedron. We observe that the cooperation proportion increases with the degree of homophily, and gradually converges constant value 0.4. We further present the gradient field under several degrees of homophily. expected, the volume of the "safe region" increases with the degree of homophily. These results demonstrate that the more homophilic population is, the more possible cooperation would emerge.
B.3 MOTIVATING EXAMPLE: SENSITIVITY ANALYSIS
We one-at-a-time method and show the result with Tornado Diagram in Fig. [T When homophily introduced, with 20% perturbation of default
Homophiy
Hamophily
parameters, 2nd-SDs persist and the "cooperative vol- ume" (green region Fig. d)) always 0 (Fig. [I left). In contrast, when homophily is introduced, the cooperative volume (green region in Fig. bb)) fluc- tuates within reasonable range and is always larger than 0. (Fig. rrihtt, which allows cooperation emergence. These results consolidate the robustness of our observations and method across wide range of conditions.
be 20%
by 20%
by 20%
0.330-42
"ccoperation
Figure 11: Sensitivity analysis.
B.4 MOTIVATING EXAMPLE: GRADIENT FIELD OF INEQUITY AVERSION
In Sec. 3 we use the gradient field plot to show the effect of social dilemmas and homophily. Here to demonstrate the mechanism behind other baselines, we plot the gradient field of Inequity
16

---

Under review as a conference paper at ICLR 2022
Homophily
Homophly range
Cellecive Wean
Colective Return Mown
10
100
200
Calective
20
6.0
1.0 100l
2.0
T Imill
(mi)
Figure 13: Performance of our method when the incentive range is restricted
Aversion (uuhes et al. 2018). We adopt the inequity aversion model used in its original paper as in Equ.
33 N
inequity aversion
Σ max(r, rr.
Σ jti
max (r: rg.
(12)
where a = 5 and B = 0.05 in their default settings.
We compare the gradient field of our method and other baselines in Fig. 12 The cooperative area volume of inequity aversion is smaller than our method (about 60%). Moreover, unlike our method, there no cooperative area around the vertex N. Once the population of agents trapped in the plane C-D-N, they never escape from it.
B.5 SSDs: RESTRICTED INCENTIVE RANGE
In Sec. 4 we allow the agents to incentivize any other agents even if they are not in the view range. Here consider restricting the incentive range to the view size. We compare this restricted variant with the original unrestricted version in Fig. 13 There is only slightly performance decrease in the restricted version, which shows the robustness of our method.
B.6 SSDS: FAIRNESS IN CLEANUP
In Sec. 5.4 we have observed the division of labor between agents in Cleanup (n=5). real life. fairness is very important indicator of how good the division of labor is. Here we statistically measure the fairness of the system, and find that the agents carrying out different tasks are roughly fair in Cleanup (n=5), when we take the incentivizing rewards into consideration. We use the Equality metric (Hughes al. 2018) to measure the fairness:
R
R 1=1
i=
(13)
2n
Σi=1
where r, is agent i's reward and n is the number of agents.
The value of equlity metric is between 0 and 1. The closer the value to 1, the fairer the system is. We measure the fairness models learned with 5 random seeds and calculate the mean value as well 95% confidence intervals. The mean values and confidence intervals of equality when we only consider environmental rewards and when we consider both environmental and incentivizing rewards 0.6693(0. 1252) and 0. (.8900(0.0773) respectively. We conjecture that the fairness in this system comes from the fact that apple-harvesters and waste-cleaners should have roughly equal total rewards, otherwise no agents would choose clean wastes.
B.7 RESULTS OF DIFFERENT INCENTIVE COEFFICIENTS
For single-stage social dilemmas, have conducted sensitivity analysis in Sec. 3 which shows our method are quite robust to these hyperparameters. For SSDs, we also observe similar results. However, when extreme values of these hyperparameters used, the performance severely
17

---

Under review as a conference paper at ICLR 2022
degrade. Here show the results when we change the incentive effect factor ry", and incentive cost factor of in the following table.
Table 1: Results of Different Incentive Coefficients.
Incentivizing Action Frequency
Incentives for Cleaning Waste
Configs (nf.77
Team Return
(L.0, 0.1r(Ours)
46.80(2.85)
0.1165(0.0002
0.800(0.020) -0.00100.013) 0.440(0.200)
(1.0, 1.0)
3.46
0.0334(0.0004) 0.4741(0.0009)
(1.0, 0.0) (0.0, 0.0)
8.56(6.72)
2.80(1.34)
Each item in the above table is formatted with mean(std). When the incentive cost 17 is equal to incentive effect 17,, agents tend to not use incentivizing actions, which makes it difficult to achieve cooperation. On the contrary, when the incentive cost 17" is zero, agents use incentivizing actions too frequently, which interferes with the learning of environmental policies.
B.8 INTUITION OF HOMOPIILLY
We have provided intuition for introducing homophily by our motivating example in Sec. Here provide more explanations of why homophily is effective heuristic by (1) using real-world example and (2) giving more explanations about the impact of homophily in SSDs the experiment section.
(1) In a real-world situation where there are multiple social infrastructure builders and taxpayers, the taxpayers' benefits depend on the builders' contribution and the builders' profits depend on gathered taxes. In this case, taxpayers should have similar tax payment strategies. Otherwise, more and more taxpayers will choose be free-riders and refuse to pay the tax, then the cooperation will collapse.
(2) In the evolution of cooperation of Cleanup in Sec. 5.4| apple- hepeetsssesssers under the constraint of homophily tend associate with other apple-harvesters, and tend not be second-order free-rider, ie., refusing to give positive rewards to waste-cleaners. Then the altruistic apple-harvester will not be exploited by second-order free-riders and the waste-cleaners will keep receiving rewards while cleaning. Thus the emergent cooperation becomes stable.
B.9 DISCUSSION
Is homophily the only possible solution for 2nd-SDs? No, is not, but homophily has several advantages over other possible solutions. There are three types of solutions for (1st-) SDs (Kollock 1998). (1) Motivational solutions assume that agents take their partners' rewards into account when making decision (Kuhlman & Marshello, 1975), which build in strong bias towards cooperation. (2) Strategic solutions, such as tit-for-tat (Axeirod Hamilton] 1984) and partner selection (Anastassacos al. 2020), typically require identifying cooperative and defective behaviors. Such approaches face major challenges temporally extended cases the co-learning of cooperation/deeectioo detection and incentivizing mechanism is fragile and suffers from extremely postponed learning signals from each other. (3) Structural solutions modify the game settings (Rapoport et al.) 1989) and thus may violate the assumption of the study of cooperation emergence. The advantage homophily is that avoids higher-orde order SDs (e.g., 3rd-SDs) while not requiring identifying cooperatioon/deeection.
C DETAILS OF EXPERIMENTS
Our method built on the open-sourced codebase PyMARL (Samvelyan et al. 2019) and Sequential Social Dilemma Games (SSDG) (Vinitsky et al., 2019). We now discuss the specific environmental settings and implementation details.
C.1 SEQUENTIAL SOCIAL DILEMMAS
18

---

Under review as a conference paper at ICLR 2022
In Cleanup game (Fig. 14)a), the apple regrowth rate de- creases linearly with the density of waste and would reduce to
apple
zero as the amount of waste exceeds saturation threshold. At
agant
the start of each episode, the environment resets with waste just beyond the saturation threshold. To enable apple reproduction, agents can fire cleaning beam to clear waste within the beam range, but this action induces no immediate reward. Addition- ally, waste is produced with certain probability during the episode, so agents need keep cleaning waste maintain the provision of apples. We have dilemma in this game. There distance between the waste field and the apple field. personally more rewarding to stay in the apple field to wait for the spawned apples, but some agents have to sacrifice, leave the apple field, and contribute to the public goods by cleaning waste.
(8)
waste
cleaning
boam
agens
(b)
Applo
Figure 14: (a) Cleanup and (b)
Harvest Game
In Harvest game (Fig. 14 b)), the apple reproduction rate grows with the density of uncollected apples around it. If all apples in a local area are harvested then no apple will re-spawn until the next episode. There dilemma in the game. For individual short-ferm interests, agents tend to harvest as rapidly as possible, which will deplete local resources and harm long-term collective interests. However, agents who abstain from personal benefits for the good of the group are casily exploited by defecting and over- werrhhavesting agents.
C.2 ENVIRONMENTS
To focus on the problem of social dilemmas, for all experiments, including baselines and ablations, we remove agent rotation actions in SSDG and set the orientation of all agents to face "up", like in previous works studying social dilemmas YYagg et 2020). For our method, we disable the "fining" action and use incentive actions as the way to incentivize other agents. In both Cl and Harvest game, eating an apple will provide local reward +1, and there are no other environmental rewards.
In Cleanup, agents are equipped with cleaning beam, which allows them to remove waste. We test our method on three Cleanup maps with different numbers of agents. In Table we show the details of each map.
Table Environmental settings for Cleanup with different numbers of agents.
Parameter
n=3
n=5
n=10
Map Size
10x 10
25 x 18
48x 18
View Size
7
Max Steps
50
100
100
Apple Respawn Probability
0.3
0.05
0.05
Depletion Threshold
0.4
0.99
0.99
Restoration Threshold
0.0
0.0
0.0
Waste Spawn Probability
0.5
0.05
0.05
In Harvest, the apple spawning rate at each point is related to the current number of apples within an l disitttace 2, and the spawn probability is 0, 0.05, 0.08, and 0.1 when there are 1, 2, and 23 apples within the distance, respectively.
C.3 IMPLEMENTATION
Network architecture There are two main components in our methods: environmental Q-functions and incentivizing Q-functions. In the study of social dilemmas, agents learn independently, do not share parameters among different agents, except for the RGB preprocessing network, which has the following architecture: 1 convolutional layer (6 filters. 3x 3 kernel with stride 1), flatten layer, and dense layer (32 neurons) with LeakyReLU activation. The environmental Q-functions and incentivizing Q-functions take the output of the RGB preprocessing network input.
19

---

Under review as a conference paper at ICLR 2022
The environmental Q-function consists of three layers: fully-comm conneetddde layer with LeakyReLU as activation, followed by a 64 bit GRU, and followed by another fully tully-connected layer that outputs an estimated utility for each action. The incentivizing Q-function has the same architecture as the acting Q-function, except that the last layer additionally takes the target agent's environmental action as input.
Optimization For all experiments, we set the loss scaling factor Aine = 1, X homo = 0.01, discount factor 7 = 0.95, T 0.995, incentive effect factor 7f 1.0, and incentive cost factor 1f 0.1. The optimization is conducted using Adam with a learning rate of 0.0001. For exploration, we use e-greedy with annealed linearly from 1.0 0.05 over 50K time steps and kept constant for the rest of the training. We run one environment each time to collect samples. Batches of 16 episodes are sampled from the replay buffer (whose size 5000); and the whole framework is trained end-to-end on fully unrolled episodes.
Experiments are carried out on NVIDIA GTX 2080 Ti GPU. For 10-agent environment (like Cleanup (n=10)), our method requires approximately 60G of RAM and 0.9G of video memory, and takes about 115 hours to finish 5M timesteps of training.
C.4 SIMILARITY OF ENVIRONMENTAL BEHAVIORS
In Sec. 4.2 of the paper, we discuss how to encourage homophily in temporally extended cases. challenge to measure the similarity of environmental behaviors. In this paper, we use the X-means (Pelleg et al. 2000) implementation provided by PyClustering (Novikov] (019) to identify similar behaviors. The behavioral features include the changes made to common information like the amount of harvesting, the amount of cleanup, etc., in the last 10 timesteps. When clustering, the minimum and maximum number of clusters are set to 2 and 4, respectively.
D DETAILS OF BASELINES AND ABLATIONS
We compare our method against various baselines and ablations. For LIO Yang al., 2020). Incquity Aversion (Hughes et al.) 2018), and Social Influence (Jaques et al. 2019) we use the codes provided by the authors and the hyper-parameter that have been fine-tuned on the Sequential Social Dilemma Games (SSDG) (Vinitsky al., 2019). For Selfish Actor-Critic, we use the default implementation in SSDG.
The ablation Cont. inc. actions, which learns continuous incentives, uses the same implementation and hyperparameter settings as LIO, but with the only difference that the incentive cost changed from the default value of LIO to 0.1, which is the same in our method. Ablation w/o homophily and w/ inc use the identical network structure and syper--arameter settings as our method. The differences are that w/o homophily does factor X home to O, and w/ inc additionally uses received incentives to train incentive Q-functions. For all the experiments, keep the game settings be the same for fair comparisons.
the homophily loss by setting homophily loss scaling
E FORMAL ANALYSIS
In this section, we formally calculate the closed-form gradients in the policy space for the motivating example problem, which are visualized as ternary plots or quaternary plots Sec. of the paper.
E.I NOTATIONS
Suppose team of n agents joins the public goods game introduced in Sec. 3, where the reward functions can be found in Appendix A The action set A is identical for all agents and depends on the specific settings in the following subsections. Agent chooses actions according to its own policy T; which is parameterized by |A| parameters, and ΣxEA Ty (1 = X) = In addition, we assume agents choose actions independently, that T(a,. ... .n) = 1 T,,a))
We first define two frequently used equations. Let T (a; = N) = Bx,N, where N represents the action of non-participanting 0R . E [0, 1), and 1,2,
20

---

Under review as a conference paper at ICLR 2022
First we define
E_ Ex
kez kiti Max = N)
where Enei Max = N) is the number of agents taking the non-participating action N. We use the notation d_; (d1. ... 1.-1,.,+..... .d,), where d3 = I(ax = NN) {0, 1 is the indicator
variable, i.e., dę if ag and otherwise d2 We have
E_, Σ
II O2,N)² d- 0g kii
(14)
= n Exes de
Note that 8 E_ 0. Similarly, we define J0,,
E-ig = Em
Exe(ist M(a = N)
and use the notation d- = (d1, ." ,,,,,,,,, dit1. ,d-- d=t1,"" ... ddn) where d, = I(ax
N) {0, 1}. We have
E-ij
E
II (1 Ok.N)
(15)
Exe(ie) da kE(())
d_E//0,11=-2
Note that
09.NN
④ E
ij
= O.
E.2
SEC. PARTA
To showcace the influence of first-order social dilemmas, in Sec. 3 Part A consider three atomic actions, C, C. Assume that agent chooses actions from {C, N} with probabilities 0cc, 0z,D, di,N. The reward function is defined in Eq. 7 Appendix A.1 We can calculate the value function of agent i:
V." = Eg [r:(e1, ... a,,)
-d)
Ex
Il(:: =C)
b E I1a; = N)
Σ
((a; 0) 0) -
+ I(a, D)b n -ofe Maj = N)
Σ
Ilay =0)
+ I(a, = N)o
=8,0
E Eo,.E--0 E-i jtti
Ab.bb D., +
where E-; and E-ij are defined as in Eq. 14 and Eq. derivatives of the value function w.r.t each parameter:
15 respectively. Then we can calculate the
OV
=b
D + -c,
(16)
00,0
21

---

Under review as a conference paper at ICLR 2022
OV. -b Σ
(17)
D0 jti
OV.
=0.
(18)
00,,N
The above equations are used to plot Fig. (d) of the paper.
E.3
SEC. PART B
To introduce altruistic incentives into the system, we add the fourth type of atomic action, PA. We consider unexploitable punishments here, and exploitable punishments in the next subsection. Agent i chooses actions from A = {C, D. N, PA] with probabilities 0g,c, Oz 02,N 0,,PA The reward function in this case defined Eq. in Appendix A.1 We can calculate the value function of agent i
V," EE, [ri(a...... "., ,an]]
-E,r
I(a; = C)
b (n Eipi I(aj = N)
Σ
I(a, = -C. -
op
Σ
I(a; PA))
n1
jti
+ +(a;= = D)
b/ n- Ejzi En-Ett = =N)
-00
-P Σ
1
I(a (a)=
3#
+ +[(a; = N)o
+ +I(a; = PA)
Σ
I(a ΣI(a= I CAA)++1 C( -c
- Effii I(ay =N)
ak
1
Σ
I(a, = =C) - Σ
I(a; D1)
7
iti
1
-0.0 6
Σ (0,c (A.++0/AA)E-pp + E-i
a-p
Σ
0j.PA
jt1
+ OLD
b ( +gpA)
p= Σ
1
0j.PA
J#Y
j+1
+ 0N
+ 03.PA
b
(0, + E + E_s -c ak Σ jt
0 - k n
Σ 0g.0 i
where II(a; CA) equals one if and only if aj Cr = PA, and E_, and E- are defined Eq. [4] and Eq. [5] respectively. Then we can calculate the derivatives of the value function w.r.t each parameter,
OV 00,c
=b
+0,,c++0/AA)--.. EE
c ap Σ 0y.PA jØ1
(19)
22

---

Under review as a conference paper at ICLR 2022
1 OV. -b -(0ho+0;pA) +O,PAA)-115 - p- OgPA.
Σ
(20)
00, j71
n 571
OV.
=0,
(21)
N0,
OV.
(10,.+00.ra).-... + E-i
- ak
Σ
03
-k-
Σ
jj.D.
(22)
71
j&
The above equations are used to plot Fig. 3(a) the paper.
E.4
SEC. PART
Now consider exploitable punishments. Agent chooses actions from A DC P) with probabilities 8, p. ,,,N, p..p. The reward function is defined in Eq. 9 in Appendix A.1 calculate the value function of agent
We can
V. =E, [r,(a1," ".. : .an)]]
T(a = C, C) +1 -/ -c)
=E, I(a; = =C)
b
Σ
2ize I(a, = N)
jz
+ +1(a, D)
Σ
I(a, = C.P)
- -p- Σ
I(a, P) 171
Ejqi 1(a;= = N)
jfi
+ +1(a; N)o
+ I(a: =P)
P)
b (n-E Ejjt Maj -N)
I1(a; I(aj C,P)+1
1/
Maj D) ]
k: n
Σ
1#i
-c)
-8,
[(,,c + (..r)) + Eass -c)
+ 0.D
[0,.c 00. p- Σ
0,p
j7
jtz
+ 02
(0
-(0ho+0;))
-c- -- Σ 50DD ni j
+ 0,
E_i
jti
where I(a, P) equals one if and only if a, = or and F_, and E_ir are defined in
Eq. 14 and Eq. 15 respectively. Then can calculate the derivatives of the value function w.r. each parameter,
OV.T 00.c
=b
Σ
00p)) + E-i
(23)
1$1
OVE
1
=b Σ
(03.c (g.r)
p
Σ 0gp
(24)
00,D
23

---

Under review as a conference paper at ICLR 2022
TV. =0,
(25)
N0,,
OV
=b
(0,,c+0,p))-.
+
c k- Σ
O.DD
(26)
n
jti
jti
The above equations used to plot Fig. 2(d) of the paper. It worth noting that
ov - d0,cc
Σ 00 S..
(27)
8
n j
The gradient is non-positive for any Dj.D, which indicates that second-order cooperators would be taken over by second-ores -oder defectors.
E.5 SEC. 3 PART D
Based on the settings specified in Appendix E.4 we consider homophily here. Agent chooses actions from A {C, D, N, P) with probabilities 0g,c, 0i, 0i,N, 0i.p. The reward function is
defined in Eq. 9 We can calculate the value function agent
V, Er, [ri(ai.... "", (un]]
I1(as 1(a -.P)) -c)
-E, I(a; =c)
b n2
Σ
n Eライ "n-E/t H(a, N)
jz
+ +I(a; D)
b jzz I(a; = N)
Σ Iay= = =C,))
-P Σ
I(aj =P)
+ T(a N)a
+ I(a; P)(1) b -ifi Ma,
Σ
I(aa C, C, +1
= -N)
Iaa = D) ]
k
1
Σ
n jti
-0..
Σ
(0 + (j,r) + E_i -0)
+ 00,D
(10c (g.c+
p- Σ Og.
JØL
ftz
+ 0,,No
+ f3.
(000++0rr))..p + F.,; jti
-c- k
Σ 01D n jfi
where I(a, C, P) equals one if and only a, = C Co and E_, and E-ig are defined in Eq. 14 and Eq. 15 respectively. Then can calculate the derivatives of the value function w.r.t each parameter. Besides, to show the effect of homophily, we encourage agents with similar environmental behaviors to have similar incentivizing behaviors. Since only contributors and punishers have the same environmental behavior of contributing to the public goods, we encourage their incentivizing behaviors to be the same converting the minority of P and C the majority with probability of
24

---

Under review as a conference paper at ICLR 2022
= 0.2. For each agent, the converting direction depends all the other agents. Specifically, if other agents choose action P more often (sign ( (0 ,,,c)) > 0), agent i will increase the probability of choosing action P' by À -min(0,,cr P), and vice versa. Formally, taken homophily into consideration, the gradients of each parameter of agent are:
a =b +0,r))) + E-
(28)
1#1
+ A sign
E0sc - 0s,p))
min min(0s,c,,,p) 0sPP)
(29)
jzi
0. = Σ 00 + 0g,p)
P Σ
1
p3.p.
(30)
11 jzi
1
0N -0,
(31)
00. =b
(03.c + Og.p)E-ij + E_i -c k-
Σ 05.0
(32)
8+1
x- ssign
E 05,0) (s,(
(33)
The above equations are used to plot Fig. 3(b) of the paper. And it is worth noting that
0DD E 0.p- - =-k n 1#1
2A sign Σ 103r 03.c) min(0.c;0c.P)
(34)
which is positive when the population is close to point P. in which situation the population chooses action P more often than C and D (sign(). yys (0j, 0g,c)) > and Ejjs 0g.D small), and thus the agents will not deviate second-order free-riding.
E.6 PROJECT ONTO THE PROBABILITY SIMPLEX
After we have obtained the gradients of each action of agent i, we can calculate the new policy as follows:
0x = 0x,x + 3 OV
VX E A.
(35)
00, x
where / is the learning rate. Now T< = X) 0% x However, this new policy may not be in the
valid probability space, i.e. ExEA 7< = X) = 1 may not hold anymore. To address this issue,
we project it onto the probability simplex (Chen & Yc 2011 Wang & Carreira- 2013) after
each update. Let IT AI Al A [Al denotes the projection to the valid space:
M [x] = arg min || - =||-
(36)
where || ||| denotes the regular Euclidean norm and A/4| the canonical simplex defined by
LA
A |||
z (21, ".AA)) E ER!!
:0 5 1, 1,... and
=
1
:=1
25

---

Under review as a conference paper at ICLR 2022
Using this projection, the valid new policy of agent i is
- II A mT]
(37)
where कं = x)xx is the parameter vector of agent i. With enough updates and this projection
rule, we can determine the location of the "safe region" in Fig. 2(d), Fig. 3(a) and Fig. 3(b) of the paper.
F LIMITATIONS
F.1 LIMITATIONS OF FORMAL ANALYSIS
In this work, we study the problem of cooperation emergence in both single-stage and sequential social dilemmas. For single-stage social dilemmas, we provide formal analyses and numerical results for the effect of free-riders and homophily in Sec. 3 and Appendix E. However, in the main text, for sequential social dilemmas, we only provide empirical results in Sec. 5.
Our aim is to formally analyze the evolutionary dynamics of environmental behaviors and incen- tivizing behaviors on SSDs. However, the environmental policies and incentivizing policies are interdependent, and it is difficult to accurately account for the effect of incentivizing behaviors when considering environmental policy updates.
To better explain this challenge, we first give some notations. There are n agents participating in the public goods game introduced Sec. The first-order cooperation contributes to the public goods and benefits from it, while the first-order defection does not contribute but benefits from the public goods. The second-order cooperation will pay a cost to punish those who choose first-order defection, while the second-orde -odder defection will not punish such defections. Each agent chooses actions according to its own policy Ty, which includes environmental policy π. (a!) parameterized by 0₂,1 and incentivizing policy (a{)) parameterized by 0,,2. We assume that the two policies
independent, i.e., (a a n. (a )x; (a.). Agent chooses first-order cooperation (or defection) with probability .! (a: = C) 0z,1 (or T/ (a D) = 0;,1) and chooses second-order
cooperation (or defection) with probability T² = C* 0,2 (or 7 (o D) 02.2). We also
assume different agents choose actions independently: (aa of a a I[; Ty (a) a5).
We calculate the value function of agent i,
V =E, (riat am, ... a,, a]]]
E
T(a) = C) -II C) p- I(a = D) Σ
T(a T(af= C
LLT(a C) Σ T(a) D)
n
1
00.1 c0,,1 - -p-(1 02,1) Σ 022
00 Σ - 03.1) n
j=1 n
n
$$1
$41
b
c),,, Σ
b 0 p-1 (1 00,
k 0 - 0311)
n
jf1
The learning process of agent i's incentivizing policy can be framed a bi-level optimization problem,
max V
* EAA
26

---

Under review as a conference paper at ICLR 2022
subject to n'
1I ]
jj 1.
1,
arg max V .j = 1, , EA
where A' A is the valid space for environmental and incentivizing policies, respectively. The environmental policies of all the agents are first updated under the influence of incentivizing policies, and then the incentivizing policy of agent is optimized under the new environmental policies. It is challenging to get closed-form solution for this optimization problem when other agents' incentivizing policies also optimize this bi-level optimization problem. But we can still provide insights into this problem. We first calculate the gradient of the value function V w.r.t 03.1:
OV
c
P T2
0k.
(38)
00
With learning rate 3, the updated
1 becomes:
0V
b
001 - +
03
+
c
+
p
On.2
(39)
00
11
71
Now the new value function for agent is
V
b -))0 n + Σ A&L
(
P- 0,
k n - 02,1)
(40)
To calculate updated incentivizing policies, we derive the gradient of V w.r.t. 02.. Note that agent i's incentivizing policy does not directly influence its environmental behaviors, have
06 J,1
j=i,
00,
8p n:
j i.
With this derivative in hand, can obtain the gradient of VF¹ W.r.t 0:
ov 00.2
= =Σ
3p k (1 f3 - Bpk 01,2
n²
iti
(n- _ (p+ kc) ph n
n
Σ (1 0,,) + 3 n =ー n2 #
2) Σ , + n0 (n (n-2)
We find that the learning rate 3 has decisive influence on the positivity and negativity of the above equation, and the direction of the gradient w.r.t 0g2 cannot determined at each step. alternative to consider multiple gradient steps, calculate optimal V given incentivizing policies, and then derive the change direction of 0g,2 based on convergent V. However, it is challenging to formally calculate the global optimal V,5.
In addition, another problem arises when we consider the homophily constraint as a loss function. Using the definition of Eq. 4 and Eq. 5 in the paper, the homophily loss of agent i under the updated environmental policies
(1 (1-1,))) + (1 (1-00 0111((1 - -02z)) (0 log 0:2 + (1 03:2) log(1 - 0,,2)) JAIKE
Σ
(41)
27

---

Under review as a conference paper at ICLR 2022
With further calculation, find that the derivative of LT" w.r. 8,,2 has nonlinear dependency on others' policies, which makes the dynamics of the system hard to capture, not to mention obtaining the closed-form solution (Perko 2013).
So far, we have presented the challenges of obtaining theoretical supports in temporally extended cases. These challenges have perplexed the researchers for long time (Gould et al. [016]] Hiischh et al. 2012 Hughes et al. 2018). and we believe that the solution for these questions is an important and promising direction for future work.
F.2 LIMITATIONS OF EMPIRICAL IMPLEMENTATIONS
In this work, we encourage homophily on the level of incentivizing behaviors and outperform other works in SSDs. However, computing the homophily loss in Sec. requires observing other agents' environmental actions, well as their incentivizing actions towards all other agents. It might be a promising future work to restrict the agents' observaton and only allow the agent to incentivize nearby agents. Opponent modeling and communication might be critical techniques to achieve these goals.
In addition, incentivizing actions expected to positively influence the return given by the envi- romment through incentivizing other agents. However, incentivizing actions mainly influence the policy update of other agents, the effects of incentivizing actions could be delayed, which may result in slow learning. Yang et al. (2020) have studied this issue on the framework of actor-critic, but how to effectively solve this problem the framework of Q-learning is still open question. Fortunately, one advantage of homophily is that its influence is immediate. If homophily can help cooperation emergence (and fortunately can, as shown by our results), this timely feedback can bypass the problem of delayed reward influence. In the meantime, we are aware that addressing the problem of delayed reward influence may further improve learning performance. We will study this more in de-tepth in future work.
28


Reviews:
[{"review_id": "mx3nkqMnKu", "reviewer": "Reviewer_bDVR", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nI think the extension of what has been studied purely in the PD to more complex games is an interesting idea. The experiments are well done.\n\nHowever, I’m not sure there is enough in this paper to warrant publication at ICLR. \n\nAs the authors point out, the evolution of second order cooperation (i.e. punishing of non-punishers) is heavily studied in the standard evolution of cooperation literature. \n\nAs the authors point out, there is already work in the standard PD space that shows that preferential matching (which is quite similar to what the authors call homophilic matching) can stabilize cooperation in the PD. Note that the authors cite a few of the main papers in this literature but there are many more, as this topic has been done pretty extensively. I would actually remove section 3 from the paper and just state the headers as a sentence as these things have hundreds (thousands?) of pages already written about them.\n\nGiven that this is so well understood in the PD, it seems like the main novelty in this paper is just the extension of the PD to the SSD and the use of RL instead of e.g. Moran processes. I am not sure that’s a sufficient contribution.\n\nPossible Extensions\nI do not want to sound too negative, I think this is an interesting start, so I now discuss some potential extensions to increase the meat in the paper.\n\nI would recommend the addition of theoretical guarantees (fine if they’re just in tabular RL). A paper of just experiments begs the question of how cherry picked the environments are and what the boundary conditions are. This would be a real extension since most of the existing literature only has theoretical results for the PD, which, as the authors point out, is very simple and unclear how much generalizes.\n\nThe homophily loss in the paper is basically just biasing the learning towards strategies which do well when paired with themselves. This actually smells a bit like the concept of evolutionary stability, so I wonder if that is a base for a potential theorem.", "summary_of_the_paper": "Summary\nThe paper studies the evolution of cooperation in SSDs which are essentially more complex versions of the (repeated) Prisoner’s Dilemma. Whether cooperation in a population evolves (or not) depends on whether there exist individuals who punish non-cooperators. This evolution is now doubly fragile because there is an incentive to free-ride on punishment – that is, not to punish the punishers. The authors introduce a mechanism where agents also try to seek out those who have similar strategies as them, which reduces second order free riding.\n", "summary_of_the_review": " I’m not sure there is enough new stuff in this paper to warrant publication at ICLR. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "efGmExFsFUQ", "reviewer": "Reviewer_neVn", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The writing is generally well-organized and of good quality. The detail introduction, related work and motivating example section served nicely to establish the current proposal’s novelty.\n2. This paper, as far as I know, is the first to try to address second-order social dilemmas in MARL, which should be the main reason for the existing baselines requiring 100M to learn cooperative strategies.\n3 This paper makes an adequate comparison with various baselines.\nWeaknesses\n1.\tThe selection of colors in figs 1-3 makes a lot of confusing, sometimes bule means the 2-nd order defecting, sometimes it means one trajectory.  \n2.\tIt is not clear how the authors introducing homophily into the motivating example. What do you mean by “we encourage their incentives to be the same by converting the minority of P and C to the majority with a probability of 0.2.”\n3.\tCould you show more in the motivating example? I mean you can show that the mechanism behind the other baselines, such as Inequity Aversion (Hughes et al., 2018), Social Influence (Jaques et al., 2019) cannot solve 2nd-SDs. It is incredible that the baselines typically need hundreds of millions of steps to learn cooperation, but your methods only needs 2-5 million steps!!! Is the proposed method just a trick, which does not allow the agents to adopt 2-nd order defecting. What if some agents use your method, while some use other baselines? \n4.\tThe equation for S^env (i,j) should be given in the main paper, because this is the main idea of this paper.", "summary_of_the_paper": "How cooperative behavior emergeing among self-interested agents was a question of longstanding interest. In recent years, this problem has been investigated in multi-agent RL situations. This paper considers the instability of the cooperation in MARL. \nThe paper first illustrates the phenomenon of oscillation-producing second-order social dilemmas within an EGT case study, and shows how a homophily mechanism can resolve them and produce convergence to a socially efficient set of roles. Then they propose a loss function called “homophily loss” that can resolve these second-order dilemmas in MARL. They experiment with this in two SSD's, Harvest and Cleanup, and show that their method outperforms the baselines they investigate.", "summary_of_the_review": "The paper is generally well written, and with some novelty. But the provided results cannot convince me that the proposed method is not just a trick. I will rasie my points if the authors can provide more results to convince me.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ZK2jwAkpuJ", "reviewer": "Reviewer_TQpe", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On the positive side, I found the paper to be well-written, and it gives a fairly satisfying and complete first investigation of using the tendency of homophily in sequential social dilemmas. The idea behind homophily is intuitive, i.e. associate human individuals with similar others, and seems to be quite useful according to the simulation results in both single-stage and sequential social dilemmas. \n\nOn the other hand, a major concern in my view is that the computation of S^{env} and S^{inc} in equation (4) assumes the agent knows all the other agents’ incentivizing and environmental information. This doesn’t seem to be super realistic in practice given that all the agents are self-interested. In addition, the proposed method requires much more information about other agents, so it’s not very surprising that the proposed method can achieve better cooperation between agents compared to other baseline methods, which uses much less information about other agents.  The sharing of this environmental and incentivizing information between all the agents can already be seen as a kind of “cooperation” imposed by the proposed method. Therefore, it is not truly clear to me that the better performance of the proposed method is due to more demanding requests of the agent, or due to a better learning algorithm. This is a major reason for my rating of weak rejection. \n\nIn addition, how to specifically implement the homophily, e.g. to what extent (especially this paper is using a binary instead of a continuous variable to determine the similarity in the sequential social dilemmas setting) can we regard two individuals as similar? In Section 3.D, the authors introduced a concept - degree of homophily, and show the “safer region” increases with the degree of homophily. How is this degree estimated, does this degree exist in practice, and if so what’s a normal value for this? Also, what’s the relationship between the degree and the S^{env} (environment similarity variable) in the sequential social dilemmas setting? There seems not a good guidance for these questions. \n\nAdditionally, the title of the paper emphasizes “sequential social dilemmas”. However, I am not sure if this matches the main concern of the paper. As far as I understand, the main contribution of the paper is using homophily to solve the second-order social dilemmas resulting from the incentive mechanisms other than temporally extended mechanisms. What’s more, the formal analysis of how homophily solves second-order social dilemmas is only proved for single-stage social dilemmas, only simulation results were provided for this paper’s main goal - sequential social dilemmas. Therefore, I think the results from this paper don't solve the problem as completely as proposed.\n\nAbout the simulation results, I like the trajectory figure and gradient field figure plotted by the authors. However, the results there need more explanation. Why does oscillating cooperation mean the distribution of population members converges to Nonparticipants (N)? I think when the distribution of population members converges to Defecting agents, this can also be thought as noncooperation. Similarly, why does the convergence of the distribution to Punishers (P) means stable cooperation?\n\nSome notation issues: \nSection 3 Paragraph 1: no definition about 1st-SDs, is it just the SDs? Or if there are others that the authors have in mind; \nSection 2 Paragraph 1: SDs is defined as the abbreviation of Social dilemmas which is contradicting with the definition of Non-sequential\nSocial Dilemmas from Section 1 Paragraph 2.\n", "summary_of_the_paper": "This paper studies the problem of promoting cooperation among self-interested agents. Inspired by the work which studied homophily in non-sequential social dilemmas, the authors proposed to use homophily, which encourages agents with similar environment behaviors to have similar incentivizing behaviors, to achieve stable cooperation in sequential social dilemmas. Simulation evidence from sequential social dilemmas of public goods and tragedy of the commons was also presented in the paper to support the effectiveness of the proposed method.", "summary_of_the_review": " Overall, I do think that, unless there is something I am missing, the limitations I described somewhat limit what we can take away for realistic settings, and so doesn’t quite settle the questions claimed so completely as suggested. I would recommend weak\nrejection. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper propose a novel framework to increase cooperation in second-order social dilemmas. This is based on encouraging homophilic incentives. Reviewers agree that the paper does not meet the standards of publication yet. In particular, they worry that the assumptions made are so restrictive as to make model inapplicable to interesting problems. There is also a concern that the work is simply not novel enough.
Decision: Reject