# Aligning Individual and Collective Objectives in Multi-Agent Cooperation

Yang Li  Wenhao Zhang  Jianhong Wang  Shao Zhang  Yali Du  Ying Wen  Wei Pan

###### Abstract

In the field of multi-agent learning, the challenge of mixed-motive
cooperation is pronounced, given the inherent contradictions between
individual and collective goals. Current research in this domain primarily
focuses on incorporating domain knowledge into rewards or introducing
additional mechanisms to foster cooperation. However, many of these methods
suffer from the drawbacks of manual design costs and the lack of a theoretical
grounding convergence procedure to the solution. To address this gap, we
approach the mixed-motive game by modeling it as a differentiable game to
study learning dynamics. We introduce a novel optimization method named
Altruistic Gradient Adjustment (AgA) that employs gradient adjustments to
novelly align individual and collective objectives. Furthermore, we provide
theoretical proof that the selection of an appropriate alignment weight in AgA
can accelerate convergence towards the desired solutions while effectively
avoiding the undesired ones. The visualization of learning dynamics
effectively demonstrates that AgA successfully achieves alignment between
individual and collective objectives. Additionally, through evaluations
conducted on established mixed-motive benchmarks such as the public good game,
Cleanup, Harvest, and our modified mixed-motive SMAC environment, we validate
AgA’s capability to facilitate altruistic and fair collaboration.

Machine Learning, ICML

##  1 Introduction

Multi-agent cooperation primarily focuses on learning how to promote
collaborative behavior in shared environments. Typically, research divides
multi-agent cooperation into two prominent areas, pure-motive cooperation and
mixed-motive cooperation (Du et al., 2023; McKee et al., 2020a). Recent
progress in cooperative Multi-Agent Reinforcement Learning (MARL) has
primarily focused on addressing pure-motive cooperation, which also known as a
common-payoff game, represents situations where individual goals fully align
with collective objectives (Yu et al., 2022; Wang et al., 2020; Zhong et al.,
2023; Li et al., 2024). Despite pure-motive cooperation, mixed-motive
cooperation, which is typically defined by the imperfect alignment between
individual and collective rationalities, is more common in real-world
scenarios (Rapoport, 1974; McKee et al., 2020a).

Recent mixed-motive cooperative studies in MARL have largely employed hand-
crafted designs to promote collaboration. Incorporating additional mechanisms
to align objectives appears to be a popular avenue, including aspects such as
reputation (Anastassacos et al., 2021), norms (Vinitsky et al., 2023), and
contracts (Hughes et al., 2020). Another prevalent method draws on intrinsic
motivation to align individual and collective objectives, augmenting
altruistic collaboration by integrating heuristic knowledge into the incentive
function. Conventionally, some works accumulate individual rewards with the
group to cultivate altruistic conduct (Hostallero et al., 2020; Peysakhovich &
Lerer, 2018; Apt & Schäfer, 2014). Furthermore, some studies derive more
sophisticated preference signals from the rewards of other agents (Hughes et
al., 2018; McKee et al., 2020a). Additionally, several approaches aim to learn
the potential influences of an agent’s actions on others (Yang et al., 2020;
Jaques et al., 2019; Lu et al., 2022). Most of these algorithms are highly
dependent on carefully crafted designs, necessitating significant human
expertise and detailed domain knowledge. However, they lack in-depth
theoretical analysis concerning alignment and convergence.

In this work, we first present the differentiable mixed-motive game (DMG),
premised on the assumption that the players’ loss functions are at least twice
differentiable. The proposed formulation offers an efficient tool for
analyzing the dynamics of gradient-based methods when optimizing mixed-motive
objectives. Furthermore, we explore the optimization trajectories of
simultaneous optimization methods and gradient adjustment methods ( consensus
optimization (Mescheder et al., 2017) and symplectic gradient adjustment
(Letcher et al., 2019)) in the context of a two-player DMG, as shown in Fig.
1. First, we observe that gradient adjustment methods are ineffective in
addressing mixed-motive problems. These methods tend to prioritize stability
at the expense of mitigating individual loss, which conflicts with the
interests of individual participants (Chen et al., 2023). While simultaneous
optimization with collective loss successfully enhances collective interests,
it seems to neglect individual interests.

To address the issue, we propose an Altruistic Gradient Adjustment (AgA)
optimization algorithm, designed to align individual and collective objectives
from a gradient perspective. We provide a theoretical proof to suggest that
appropriately choosing the sign of the alignment weight of the gradient terms
could speed up the convergence of the AgA optimization strategy towards stable
fixed point of collective objective while effectively bypassing unstable ones.
The trajectory visualizations in Fig. 1, along with the sign selection
ablation study trajectories presented in Fig. 3, serve to demonstrate
successful alignment of objectives.

To further assess the effectiveness of our proposed AgA approach, we perform
an assortment of experiments on a two-player public goods game and two
sequential social dilemma games (Cleanup and Harvest) (Leibo et al., 2017).
Given the relatively simple nature of these standard test scenarios used in
mixed-motive cooperation contexts, we chose to modify the widely used SMAC
environment (Samvelyan et al., 2019) to create a more complex mixed-motive
cooperative setting. Evaluation based on various performance metrics including
social welfare, equality, and win rate, suggests that the AgA approach
surpasses the performance of baseline methods.

The contribution of the paper can be summarized as follows: (1) We introduce
the differentiable mixed-motive game (DMG) and propose Altruistic Gradient
Adjustment (AgA) algorithm to align individual and collective objectives from
a gradient perspective. (2) We theoretically prove that careful selection of
the alignment weight’s sign can expedite convergence in AgA and effectively
avoid unstable fixed points. (3) Visualizations based on a two-player DMG show
that our method efficiently aligns individual and collective objectives.
Further experiments conducted on mixed-motive testbeds and modified SMAC
environments underscore the superior performance of our AgA method in several
measurement metrics compared to baselines.

##  2 Related Work

Mixed-motive cooperation. Mixed-motive cooperation refers to scenarios where
the group’s objectives are sometimes aligned and at other times conflicted
(Philip S. Gallo & McClintock, 1965). Recently, there has been a surge in
academic interest in the Sequential Social Dilemma (SSD) (Leibo et al., 2017),
which expands the concept from its roots in matrix games (Macy & Flache, 2002)
to Markov games. Prosocial (Peysakhovich & Lerer, 2018) improves collective
performance by blending individual rewards to redraft the agent’s overall
utility. While PED-DQN enables agents to incrementally adjust their reward
functions for enhanced collaborative action through inter-agent evaluative
signal exchanges (Hostallero et al., 2020), Gifting directly reward other
agents as part of action space (Lupu & Precup, 2020). Inequity aversion
further integrates the concept into Markov games by adding envy
(disadvantageous inequality) and guilt (advantageous inequality) rewards to
the original individual rewards (Hughes et al., 2018). Simultaneously, Social
Value Orientation (SVO) strategy introduces a unique shared rewards-based
compensation approach, encouraging behavior modifications in line with
interdependence theory (McKee et al., 2020b). The LIO strategy bypasses the
need to modify extrinsic rewards by empowering an agent to directly influence
its partner’s actions (Yang et al., 2020). Meanwhile, other studies introduce
new cooperative mechanisms such as incorporating a reputation model as an
intrinsic reward (McKee et al., 2023). The CNM strategy delineates acceptable
and unacceptable behaviors using classifiers as social norms, aiding agents to
learn advantageous norms for improved returns per agent (Vinitsky et al.,
2023). Despite these advances, many current studies lack both cost-efficiency
in design and theoretical analysis of alignment and convergence. To address
this, our study applies a gradient perspective to align goals and further
investigates the learning dynamics of our proposed method.

Gradient-based Methods.  Our proposed AgA is fundamentally a gradient
adjustment methodology, making gradient-based optimization methods highly
relevant to the context of this paper. Methods based on gradient have been
developed to find stationary points, such as the Nash equilibrium or stable
fixed points. Optimistic Mirror Descent leverages historical data to
extrapolate subsequent gradients (Daskalakis et al., 2018), while Gidel et al.
(2020) extends this concept by advocating averaging methodologies and variants
of extrapolation techniques. Consensus gradient adjustment, or consensus
optimization, is a technique that embeds a consensus agreement term within the
gradient to ensure its convergence (Mescheder et al., 2017). Learning with
Opponent-Learning Awareness (LOLA) utilizes information from other players to
compute one player’s anticipated learning steps (Foerster et al., 2018).
Subsequently, Stable Opponent Shaping (SOS) (Letcher et al., 2021) and
Consistent Opponent-Learning Awareness (COLA) (Willi et al., 2022) methods
have enhanced the LOLA algorithm, targeting convergence assurance and
inconsistency elimination, respectively. Symplectic Gradient Adjustment (SGA)
alters the update direction towards the stable fixed points based on a novel
decomposition of game dynamics (Balduzzi et al., 2018; Letcher et al., 2019).
Recently, Learning to Play Games (L2PG) ensures convergence towards a stable
fixed point by predicting updates to players’ parameters derived from
historical trajectories (Chen et al., 2023). However, these methods, while
focusing on zero-sum or general sum games, could potentially act counter to
their individual interests, as they may prioritize stability over minimizing
personal loss. Our research specifically targets the mixed-motive setting with
the aim of reconciling individual and collective objectives.

(a) Collective Reward Landscape

(b) Reward Contour of Player 1

(c) Reward Contour of Player 2

Figure 1: Trajectories of optimization in a two-player DMG (as delineated in
Example 4.1). Fig. 1(a) displays the trajectories over the collective reward
landscape - deeper orange equates to higher rewards. Remarkably, only Simul-Co
and AgA make successful strides towards the social optimum. Fig. 1(b) and Fig.
1(c) delineate trajectories on the individual reward contour, underscoring
Simul-Co’s neglect for Player 1’s interests even though it achieves higher
rewards with fewer steps (65 steps versus 100 steps of AgA). Conversely, our
AgA optimizes along the summit of Player 1’s reward while also maximizing the
collective reward, demonstrating a successful alignment.

##  3 Preliminaries

Differential Game.  The theory of differential games was initially proposed by
Isaacs (1965), aiming to expand the scope of sequential game theory to
encompass continuous-time scenarios. Through the lens of machine learning, we
formalize the differential game, as shown in Definition 3.1.

######  Definition 3.1 (Differential Game (Balduzzi et al., 2018; Letcher et
al., 2019)).

A differential game could be defined as a tuple
$\\{{\mathcal{N}},{\bm{w}},{\bm{\ell}}\\}$, where
${\mathcal{N}}=\\{1,\dots,n\\}$ delineates the assembly of players. The
parameter set ${\bm{w}}=[{\bm{w}}_{i}]^{n}\in\mathbb{R}^{d}$ is defined, each
with ${\bm{w}}_{i}\in\mathbb{R}^{d_{i}}$ and $d=\sum_{i=1}^{n}d_{i}$. Here,
${\bm{\ell}}=\\{\ell_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}\\}_{i=1}^{n}$
represents the corresponding losses. These losses are assumed to be at least
twice differential. Each player $i\in{\mathcal{N}}$ is equipped with a policy,
parameterized by ${\bm{w}}_{i}$, aiming to minimize its individual loss
$\ell_{i}$.

We rewrite the simultaneous gradient ${\bm{\xi}}({\bm{w}})$ of a differential
game as
${\bm{\xi}}({\bm{w}})=(\nabla_{{\bm{w}}_{1}}\ell_{1},\dots,\nabla_{{\bm{w}}_{n}}\ell_{n})\in\mathbb{R}^{d},$
which is the gradient of the losses with respect to the parameters of the
respective players. Furthermore, Hessian matrix ${\bm{H}}$ mentioned in a
differential game is the Jacobian matrix of the simultaneous gradient.

The learning dynamics of differential game often refers to the process of
sequential updates over ${\bm{w}}$. The learning rule for each player is
defined as the operator, ${\bm{w}}\leftarrow{\bm{w}}-\gamma{\bm{\xi}},$ where
${\bm{\xi}}$ is a feasible direction, and $\gamma$ is a step size (learning
rate) to determine the distance to move for each update.

Gradient Adjustment Optimization.  The stable fixed point, a criterion
initiated from stability theory, corresponds to the nature of local Nash
equilibria (Balduzzi et al., 2018), as defined within the field of game
theory. More specifically, a stable fixed point, exhibiting its stability
(robustness) to minor perturbations from environments, making it applicable to
many real-world scenarios. The concept of stable fixed point prevailing in
general-sum and zero-sum games, is defined as follows.

######  Definition 3.2.

A point ${\bm{w}}^{\star}$ is a fixed point if
${\bm{\xi}}({\bm{w}}^{\star})=0$. If ${\bm{H}}({\bm{w}}^{\star})\succeq 0$ and
${\bm{H}}({\bm{w}}^{\star})$ is invertible, the fixed point ${\bm{w}}^{\star}$
is called stable fixed point. If ${\bm{H}}({\bm{w}}^{\star})\prec 0$, the
point is called unstable.

A naive idea to steer the dynamic towards convergence at stable fixed points
involves minimizing $\frac{1}{2}\|{\bm{\xi}}({\bm{w}})\|^{2}$. Assuming the
Hessian ${\bm{H}}({\bm{w}})$ is invertible, then
$\nabla(\frac{1}{2}\|{\bm{\xi}}({\bm{w}})\|^{2})={\bm{H}}^{T}{\bm{\xi}}=0$
holds true if and only if ${\bm{\xi}}=0$. However, it could fail to converge
to stable fixed point (Mescheder et al., 2017). Hence, the consensus
optimization method has been proposed, incorporating gradient adjustment
(Mescheder et al., 2017), shown as follows:

$\tilde{{\bm{\xi}}}={\bm{\xi}}+\lambda\cdot\nabla\frac{1}{2}\|{\bm{\xi}}({\bm{w}})\|^{2}={\bm{\xi}}+\lambda\cdot{\bm{H}}^{T}{\bm{\xi}}.$
(1)

For simplicity, we will refer to the consensus gradient adjustment as CGA.
While CGA proves effective in certain specific scenarios, such as two-player
zero-sum games, it unfortunately falls short in general games (Balduzzi et
al., 2018). To address this shortage, symplectic gradient adjustment (SGA)
(Balduzzi et al., 2018; Letcher et al., 2019) is introduced to find the stable
fixed point in general sum games, such that
$\tilde{{\bm{\xi}}}={\bm{\xi}}+\lambda\cdot{\bm{A}}^{T}{\bm{\xi}}.$ Herein,
${\bm{A}}$ represents the antisymmetric component of the generalized Helmholtz
decomposition of ${\bm{H}}$,
${\bm{H}}({\bm{w}})={\bm{S}}({\bm{w}})+{\bm{A}}({\bm{w}})$, where
${\bm{S}}({\bm{w}})$ denotes the symmetric component. The hyperparameter
$\lambda$ is determined by the following formula:
$\lambda=\operatorname{sign}\left(\frac{1}{d}\langle\bm{\xi},{\bm{H}}^{T}{\bm{\xi}}\rangle\langle\mathbf{A}^{\top}\bm{\xi},{\bm{H}}^{T}{\bm{\xi}}\rangle+\epsilon\right),$
where $\epsilon$ is a small positive number.

##  4 Method

###  4.1 Differentiable Mixed-motive Game

We first formulate the mixed-motive game as a differentiable game.
Specifically, the differentiable mixed-motive game (DMG) is defined as a tuple
$({\mathcal{N}},{\bm{w}},{\bm{\ell}})$, where $\ell_{i}\in{\bm{\ell}}$ is at
least twice the differentiable loss function for the agent $i$. Differentiable
losses exhibit the mixed motivation property: minimization of individual
losses can result in a conflict between individuals or between individual and
collective objectives (e.g., maximizing social welfare or beating opponents in
basketball matches). The primary objective of DMG is to optimize the
collective objective by minimizing collective loss, denoted as $\ell_{c}$,
while simultaneously taking into account the need to minimize individual
objectives, represented by ${\bm{\ell}}$. Before delving into our interest
alignment methods, let us first introduce some notations. We use
${\bm{\xi}}_{c}({\bm{w}})$ to refer the gradient of collective loss:
${\bm{\xi}}_{c}({\bm{w}})=\left(\nabla_{\mathbf{w}_{1}}\ell_{c},\ldots,\nabla_{\mathbf{w}_{n}}\ell_{c}\right).$

Nonetheless, direct optimization of individual or collective losses can lead
to convergence issues and a mismatch between individual and collective
interests. It is improbable that by minimizing only the individual loss of
each agent, a collective minimum will be achieved (Leibo et al., 2017; McKee
et al., 2020b). On the other hand, optimizing collective loss might produce
improved collective outcomes, but at the risk of overlooking individual
interests. This phenomenon is also demonstrated in Example 4.1. Furthermore,
the local convergence of the gradient descent on singular collective functions
is not always guaranteed (Balduzzi et al., 2018). This also typifies the
problem of credit assignment in MARL.

Alignment Dilemma in DMG.  Here, we provide an example of a two-player
differentiable mixed-motive game and the optimization results of the
aforementioned methods.

######  Example 4.1.

Consider a two-player DMG with
$\ell_{1}(a_{1},a_{2})=-sin(a_{1}a_{2}+a_{2}^{2})$ and
$\ell_{2}(a_{1},a_{2})=-[cos(1+a_{1}-(1+a_{2})^{2})+a_{1}a_{2}^{2}]$. The
rewards for the two players are the negation of their respective losses.

We provide a visual representation of optimization trajectories using a series
of methods to investigate the learning dynamics involved in resolving the toy
two-player differentiable mixed-motive game. In particular, we first implement
simultaneous optimization of individual losses (Simul-Ind) with respect to
each parameter, defined by the learning rule
${\bm{w}}_{i}={\bm{w}}_{i}-\gamma{\bm{\xi}}_{i}$, for $i\in\\{1,2\\}$, where
${\bm{\xi}}_{i}=\nabla_{{\bm{w}}_{i}}\ell_{i}$. Simultaneous optimization of
collective loss (Simul-Co) replaces the individual gradient with the
collective gradient ${\bm{\xi}}_{c}$ of collective loss
$\ell_{c}=\ell_{1}+\ell_{2}$. Furthermore, in order to investigate the
learning dynamics of prevalent gradient modification optimization approaches
such as SGA and CGA for the two-player differentiable mixed-motive game, we
modify the learning rule by integrating the respective adjusted gradient as
delineated in Section 3.1.

Fig. 1(a) shows the optimization paths on the collective reward landscapes,
with every path starting from the front-bottom of the landscape. The
collective reward is defined as social welfare, i.e., the sum of individual
rewards. As shown in the figure, Simul-Ind, CGA , and SGA converge to unstable
points or local maxima. Simul-Co effectively navigates towards the apex of the
collective reward landscape as depicted in Fig. 1(a). However, Simul-Co is
ineffective in aligning individual and collective objectives, leading to the
neglect of individual interests. As depicted in Fig. 1(b), the update
trajectory navigates through the crests and troughs of Player 1’s reward
contour. The trajectory suggests a disregard for Player 1’s preferences,
signifying that the updates are predominantly driven by the overarching
collective goal.

###  4.2 Altruistic Gradient Adjustment

In this section, we propose the alignment of individual and collective
interests towards achieving stable fixed points of collective objectives
within the context of mixed-motive cooperation. Revisit that the learning
dynamics of simultaneous optimization on collective loss is given by
${\bm{w}}={\bm{w}}-\gamma{\bm{\xi}}_{c},$ where ${\bm{\xi}}_{c}$ represents
the gradients of collective loss $\ell_{c}$ respectively, with respect to the
parameters of each player ${\bm{w}}_{i}\in{\bm{w}}$. Although Simul-Co
efficiently enhances collective performance, its shortcomings lie in not
guaranteeing stable fixed points (Balduzzi et al., 2018) and overlooking
individual interests as discussed in Example 4.1.

To tackle this challenge, we introduce the Altruistic Gradient Adjustment
(AgA) method with the goal of aligning individual and collective objectives
while seeking stable fixed points. Unlike existing gradient adjustment methods
(Mescheder et al., 2017; Balduzzi et al., 2018; Letcher et al., 2019; Chen et
al., 2023) that primarily focus on identifying the stable fixed points of
individual losses, our proposed AgA method integrates the individual gradient
into the collective gradient and ensures convergence to stable fixed points of
the collective loss. Specifically, AgA is defined as follows.

######  Proposition 4.2 (Altruistic Gradient Adjustment).

Altruistic gradient adjustment (AgA) extends the gradient term in the learning
dynamic as

$\displaystyle\tilde{{\bm{\xi}}}:={\bm{\xi}}_{c}+\lambda{\bm{\xi}}_{adj}={\bm{\xi}}_{c}+\lambda\left({\bm{\xi}}+{\bm{H}}_{c}^{T}{\bm{\xi}}_{c}\right),$
(2)

where $\lambda\in\mathbb{R}$ is alignment parameter, $\lambda{\bm{\xi}}_{adj}$
is called adjustment term. In ${\bm{\xi}}_{adj}$, ${\bm{\xi}}_{c}$ and
${\bm{H}}_{c}$ is the gradient vector and Hessian matrix of the game about
collective loss.

Figure 2: Illustration of Corollary 4.3. In case 1, within an unstable fixed
point’s neighborhoods, an appropriate selection of the $\lambda$ sign push AgA
to evade the unstable fixed point and pull towards a stable fixed point in its
neighborhoods as shown in case 2.

Note that the Hessian matrix ${\bm{H}}_{c}$ is a symmetric matrix. To simplify
the notation, we use $\nabla{\mathcal{H}}_{c}$ to denote the term
$\nabla_{\bm{w}}\left(\frac{1}{2}\|{\bm{\xi}}_{c}\|^{2}\right)$, i.e.,
${\bm{H}}_{c}^{T}{\bm{\xi}}_{c}$.

Intuitively, AgA is designed to involve both collective and individual
objectives, in order to harmonize the interests of individuals and the team.
The alignment parameter $\lambda$ adjusts the balance between the individual
and the collective objective. Furthermore, we minimize
${\mathcal{H}}_{c}=\frac{1}{2}\|{\bm{\xi}}_{c}\|^{2}$ to converge to a fixed
point. This objective is reflected in the gradient term
${\bm{H}}_{c}^{T}{\bm{\xi}}_{c}$ in $\tilde{{\bm{\xi}}}$. Assuming that
${\bm{H}}_{c}$ is invertible, we can deduce that
$\nabla{\mathcal{H}}_{c}={\bm{H}}_{c}^{T}{\bm{\xi}}_{c}=0$, if and only if
${\bm{\xi}}_{c}=0$. Therefore, minimizing ${\mathcal{H}}_{c}$ will guarantee
the convergence to a fixed point (Letcher et al., 2019).

Impact of the Sign of $\lambda$. While the modified AgA gradient introduces
additional complexity, we theoretically demonstrate that an appropriate choice
of the sign of $\lambda$ ensures that the AgA gradient $\tilde{{\bm{\xi}}}$ is
attracted towards a stable fixed point. In contrast, when dealing with an
unstable fixed point, AgA is pushed away the point.

Before we delve into the corollary of the sign selection for $\lambda$, we
first establish some foundational definitions. The inner product of vectors
${\bm{a}}$ and ${\bm{b}}$ are denoted by $\langle{\bm{a}},{\bm{b}}\rangle$. If
the Hessian matrix ${\bm{H}}$ is non-negative-definite,
$\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}\rangle\geq 0$ for a non-zero
${\bm{\xi}}_{c}$. Analogously, if ${\bm{H}}$ is negative-definite,
$\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}\rangle<0$ for a non-zero
${\bm{\xi}}_{c}$. Lastly, the angle between the two vectors ${\bm{a}}$ and
${\bm{b}}$ is denoted by $\theta({\bm{a}},{\bm{b}})$.

The following corollary states that AgA with a suitable sign of $\lambda$ will
bring the adjusted gradient $\tilde{{\bm{\xi}}}$ point closer to a stable
fixed point and escape from unstable fixed points.

######  Corollary 4.3.

If we let the sign of $\lambda$ satisfy
$\lambda\cdot\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle(\langle{\bm{\xi}},\nabla{\mathcal{H}}_{c}\rangle+\|\nabla{\mathcal{H}}_{c}\|^{2})\geq
0$, the optimization process using the AgA method exhibit following
attributes. Primarily, in neighborhood of fixed point of collective objective,
if the point is stable (${\bm{H}}_{c}\succeq 0$), the AgA gradient will be
pulled toward this point, which means that
$\theta(\tilde{{\bm{\xi}}},\nabla{\mathcal{H}}_{c})\leq\theta({\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c})$.
On the other hand, if the point represents unstable equilibria where
${\bm{H}}_{c}\prec 0$, the AgA gradient will be pushed out of the point,
indicating that
$\theta(\tilde{{\bm{\xi}}},\nabla{\mathcal{H}}_{c})\geq\theta({\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c})$.

The proof is provided in Appendix A. Fig. 2 presents a illustrative
visualization of Corollary 4.3. The figure depicts two scenarios: the
neighborhoods of stable and unstable fixed point (denoted by a star),
respectively. In the neighborhood of an unstable fixed point of the collective
objective, as depicted in Case 1, our AaA gradient $\tilde{{\bm{\xi}}}$ is
pushed out of the region, resulting in a faster escape compared to the
original collective gradient ${\bm{\xi}}_{c}$. This behavior is exemplified by
the green arrow. Conversely, Case 2 illustrates the scenario of a stable fixed
point, wherein our AaA gradient $\tilde{{\bm{\xi}}}$ is pulled towards the
stable equilibrium, exemplified by the red arrow.

Algorithm 1 Altruistic Gradient Adjustment (AgA)

1: Input: individual losses $\bm{\ell}=[\ell_{1},\cdots,\ell_{n}]$, collective
loss $\ell_{c}$, parameters ${\bm{w}}=[{\bm{w}}_{1},\cdots,{\bm{w}}_{n}]$,
magnitude of alignment parameter $\lambda$

2: ${\bm{\xi}}\leftarrow[grad(\ell_{i},{\bm{w}}_{i})\ for\
(\ell_{i},{\bm{w}}_{i})\in(\bm{\ell},{\bm{w}})]$

3: ${\bm{\xi}}_{c}\leftarrow[grad(\ell_{c},{\bm{w}}_{i})\ for\
{\bm{w}}_{i}\in{\bm{w}}]$

4:
$\nabla{\mathcal{H}}_{c}\leftarrow[grad(\frac{1}{2}\|{\bm{\xi}}_{c}\|^{2},{\bm{w}}_{i})\
for\ {\bm{w}}_{i}\in{\bm{w}}]$

5: $\lambda\leftarrow\lambda\times
sign\left(\frac{1}{d}\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle\left(\langle{\bm{\xi}},\nabla{\mathcal{H}}_{c}\rangle+\|\nabla{\mathcal{H}}_{c}\|^{2}\right)\right)$

6: Output:
$\tilde{{\bm{\xi}}}={\bm{\xi}}_{c}+\lambda({\bm{\xi}}+\nabla{\mathcal{H}}_{c})$
{Plug into any gradient descent optimizer}

Implementation of MARL Algorithms with AgA. The concrete implementation of
altruistic gradient adjustment is elaborated in Algorithm 1. AgA can be easily
incorporated into any centralized training decentralized execution (CTDE)
framework of MARL. In a typical CTDE framework, each agent, denoted as $i$,
strives to learn a policy that employs local observations to prompt a
distribution over personal actions. The unique characteristic during the
centralized learning phase is that agents gain supplementary information from
their peers that is inaccessible during the execution stage. Furthermore, a
centralized critic often operates in tandem in CTDE settings, leveraging
shared information and evaluating individual agent policies’ potency. To
incorporate our proposed AgA algorithm into CTDE frameworks, supplementary
reward exchanges between agents are required, offering the essential inputs
for Algorithm 1. The individual losses are calculated from individual rewards
conforming to established MARL algorithm framework, such as IPPO (de Witt et
al., 2020) or MAPPO (Yu et al., 2022). Here, the collective loss $\ell_{c}$ is
calculated according to individual rewards; for example, it could be a sum of
individual rewards or an elementary transformation thereof. Furthermore, the
AgA algorithm requires a magnitude value of the alignment parameter $\lambda$,
which should be a positive entity. The sign of $\lambda$ is then calculated in
line 5 of Algorithm 1 and is based on each gradient component calculated in
lines 2-4. Subsequently, the algorithm produces the adjusted gradient
$\tilde{{\bm{\xi}}}$. $\tilde{{\bm{\xi}}}$ is then distributed across each
corresponding parameter, and optimization is carried out using a suitable
optimizer such as Adam optimizer (Kingma & Ba, 2015).

(a) Reward Contour of Player 1

(b) Reward Contour of Player 2

Figure 3: The comparison between AgA (shown in red) and AgA without sign
alignment (AgA w/o Sign, in purple) trajectories spans 40 steps, marked at
every tenth step. Norm gradients are represented with blue arrows. Starting
from the 14th step, sign alignment pull the update direction. Consequently,
AgA is about 6 steps ahead of AgA w/o Sign at the trajectory’s end.

###  4.3 Alignment Efficiency of AgA: A Toy Experiment

To address the two-player DMG as outlined in Example 4.1, we incorporate the
AgA method into the fundamental gradient descent algorithm. The findings
reveal that the AgA method is effective in facilitating the alignment of
objectives. The optimization trajectories in both the collective reward
landscape and the individual player reward contour are represented in Fig.
1(a), Fig. 1(b), and Fig. 1(c), with brighter colors reflecting higher
collective rewards. In contrast to the objective misalignment exhibited by
Simul-Co, AgA successfully aligns the agents’ interests, as evidenced in Fig.
1(b) and Fig 1(c). Fig. 1(b) depicts the trajectory of AgA meticulously
carving its course along the summit of the individual reward contour.
Furthermore, AgA is also shown to improve the reward of Player 2 (as shown in
Fig. 1(c)), despite a convergence rate slower than that of Simul-Co.
Evidently, the trajectory of AgA (as depicted in Fig. 1(b)) takes 100 steps,
whereas Simul-Co takes 65 steps.

In addition, Fig. 3 presents a critical comparison between the trajectories of
AgA (in red) and AgA without sign alignment (AgA w/o Sign, depicted in
purple), as outlined in Corollary 4.3. This side-by-side comparison covers 40
steps and features highlighted points every tenth step. It provides a visual
illustration of the efficiency introduced by sign alignment starting from the
14th step in the trajectories of AgA and AgA without sign alignment.
Remarkably, norm gradients are represented by blue arrows, indicating the
direction of the fastest updates. As depicted in the figure, AgA with sign
selection is aligned towards the fastest update direction, resulting in AgA
progressing approximately 6 steps ahead of AgA without Sign at the end of the
trajectory.

##  5 Experiments

In this section, we conduct a series of experiments to verify the AgA
algorithm. First, we provide an overview of the experimental settings and
clarify the evaluation metrics employed.

Baselines and Evaluation Metrics. A comparison of experiments involves
specific baselines such as simultaneous optimization with individual and
collective losses (abbreviated as Simul-Ind and Siml-Co), CGA (Mescheder et
al., 2017), SGA (Balduzzi et al., 2018) and SVO (McKee et al., 2020a). In the
two-player public goods game experiment, these techniques are simply
integrated into the basic gradient ascent algorithm, whereas, for more
intricate settings like Cleanup, Harvest (Leibo et al., 2017), and SMAC
(Samvelyan et al., 2019), these baselines are infused within various RL
algorithms. Detailed operations for implementing these RL algorithms are
further elucidated in their respective sections.

We assess collaborative performance in mixed-motive games using a three-tier
approach. Primarily, we employ social welfare to gauge overall team
performance. Next, an equality metric is introduced to scrutinize fairness in
environments such as Cleanup and Harvest. Lastly, the probability of victory
against opposition in an SMAC framework determines the probability of the
team’s success. Social Welfare is a commonly accepted metric for evaluating
the performance of mixed motivation cooperation, representing the total
episodic rewards earned by all agents as $SW=\sum_{i=1}^{n}r_{i}$. Social
welfare lacks the ability to analyze teamwork in mixed cooperative-competitive
contexts. Here, we use the average Win Rate against the built-in computer AI
bot in SMAC to assess algorithmic performance. We also involve the Equality
due to the measures like social welfare and win rate are limited to a general
performance evaluation, ignoring individual interest. Therefore, the Gini
coefficient, originally intended as an income equality measure (David, 1968),
has been modified to assess reward equality in cooperative AI settings. This
study utilizes an expedited Gini coefficient calculation method, with an
associated equality metric $E$, formulated as $E:=1-G$. Each individual’s
rewards are arranged in ascending order to create a new payoff vector
${\bm{p}}$, and the Gini coefficient is computed as
$G=\frac{2}{n^{2}\bar{{\bm{p}}}}\sum_{i=1}^{n}i\left(p_{i}-\bar{{\bm{p}}}\right)$,
followed by $E=1-G$. Here, $\bar{{\bm{p}}}$ denotes the mean of the ranked
payoff vector ${\bm{p}}$ and $n$ signifies the total number of players. A
larger $E$ value implies greater equality.

(a) Cleanup: AgA with different $\lambda$ and AgA/Sign

(b) Cleanup: comparison between AgA and baselines

(c) Harvest: AgA with different $\lambda$ and AgA/Sign

(d) Cleanup: comparison between AgA and baselines

Figure 4: Comparison of Episodic Social Welfare: our proposed AgA methods
along with baselines on Cleanup (figure a and b) and Harvest (figure c and d)
tasks. Figure (a) and (c) provide an illustration of varying alignment
parameter $\lambda$ values in AgA, as well as AgA sans sign selection
(AgA/Sign), as applied to Cleanup and Harvest tasks respectively. Subfigures
(b) and (d) exhibit the social welfare obtained by AgA utilizing the optimal
$\lambda$ value, in comparison to those secured by Simul-Ind, Simal-Co, CGA,
SGA and SVO. Bold lines represent the average of the social welfare across
three seeds, with the encompassing shaded areas denoting the standard
deviation.

Metrics | Algorithms |
---|---|---
Simul-Ind | CGA | SGA | SVO | Simul-Co | AgA
${r_{1}}$ | 1.13 | 1.16 | 1.18 | 1.10 | 1.43 | 1.46
${r_{2}}$ | 1.18 | 1.15 | 1.14 | 1.06 | 1.38 | 1.45
${SW}$ | 2.32 | 2.31 | 2.31 | 2.16 | 2.81 | 2.90
${E}$ | 0.92 | 0.93 | 0.92 | 0.93 | 0.94 | 0.96

Table 1: The comparison of the average individual rewards (denoted as
$r_{1},r_{2}$), social welfare (denoted as $SW$) and equality metric (denoted
as $E$). Each value is the mean of 50 random runs.

###  5.1 Two-Player Public Goods Game

A two-player Public Goods matrix game ${\mathcal{G}}$ is widely utilized to
study cooperation in social dilemmas. The game involves players $\\{1,2\\}$
with parameters $\\{{\bm{w}}_{1},{\bm{w}}_{2}\\}$ and payoffs
$\\{p_{1},p_{2}\\}$. The social welfare, denoted as $SW=p_{1}+p_{2}$. Each
player, i.e., $i\in\\{1,2\\}$, contributes an amount $a_{i}$ within a budgeted
range $[0,b]$, and the host evenly distributes these contributions as
$\frac{c}{2}(a_{1}+a_{2})$, where $1<c\leq 2$. Consequently, each player’s
payoff $p_{i}(a_{1},a_{2})$ is estimated as
$b-a_{i}+\frac{c}{2}(a_{1}+a_{2})$. In our experiments, we set the budget $b$
to $1$ and weight $c$ to $1.5$, with the Nash equilibrium of game at $(0,0)$.

Results.  Table 1 compares averindividual rewards, social welfare, and the
equality metric sourced from 50 random runs, each capped at 100 steps. The
rows $r_{1},r_{2}$ and $SW$ represent the rewards accrued by each individual
player and the collective group respectively. Row $E$ denotes the equality
metric. The table reveals that AgA surpasses benchmark methods in individual
rewards and social welfare, and equality metric. The social optimum of the
game is at coordinates $(1,1)$, which corresponds to a maximum achievable
social welfare of $3$. Among all the algorithms, AgA achieves the closest
social welfare score to this optimum, with a value of 2.90. In addition, AgA
demonstrates the highest level of equality, with a score of 0.96, when
compared to the baseline algorithms. Additionally, Fig. 6 in Appendix B
visualizes the action distributions of these methods, demonstrating
convergence points, further supporting that AgA converges more efficiently
towards the social optimum.

###  5.2 Sequential Social Dilemma: Cleanup and Harvest

We conduct experiments in sequential social dilemma environments with a group
size of five namely, Harvest and Cleanup (Hughes et al., 2018). In Cleanup,
the agents primarily derive rewards from harvesting apples in a nearby
orchard, which is contingent upon river pollution levels. If negligence
towards the escalating pollution levels surpasses a threshold, apple growth
ceases, hence leading to a conflict of interest between obtaining individual
rewards and safeguarding joint welfare. Harvest’s premise, on the other hand,
involves agents receiving rewards by gathering apples, whereby optimal apple
regrowth is dependent on the presence of adjacent apples. A collective dilemma
appears when rampant harvesting reduces the apple regeneration rate, thus
decrementing overall team rewards. Simul-Ind, Simul-Co, CGA, and SVO are
benchmarked against our AgA methodology in our experiments. The implementation
of the Simul-Ind algorithm is based on the IPPO algorithm (de Witt et al.,
2020), with all other strategies leveraging the shared parameters of the IPPO
algorithm as well. The joint reward formula used for the calculation of
collective loss for Simul-Co, CGA, and AgAs is designed to promote both
improved collective performance and equitable behavior among agents, i.e,
$\sum_{i}\left(r_{i}-\alpha(1-actan\left(\frac{sum_{j,j\neq
i}r_{j}}{r_{i}}\right)\right)$ with constant $\alpha$. More detailed
information on these environments and algorithm execution can be found in
Appendix C.1.

Envs | Metrics | Algorithms
---|---|---
Simul-Ind | Simul-Co | SVO | CGA | AgA
Cleanup | $SW$ | 24.86 | 72.02 | 27.30 | 44.23 | 83.90
$E$ | 0.97 | 0.88 | 0.85 | 0.91 | 0.95
Harvest | $SW$ | 623.13 | 625.80 | 638.95 | 667.37 | 683.42
$E$ | 0.97 | 0.96 | 0.97 | 0.98 | 0.98

Table 2: The highest social welfare achieved throughout training along with
the corresponding equality metric. The foremost row for each environment
reflects the best social welfare, while the second row indicates the
associated equality metric.

Results. Fig. 4(a) and Fig. 4(c) present the average episodic social welfare
comparison of the AgA algorithm and AgA/Sign, excluding the sign selection
(Corollary 4.3). These figures also highlight the effect of varying the
alignment parameter $\lambda$. The prescribed $\lambda$ values for AgA/Sign is
100 for Cleanup and 0.1 for Harvest, resulting in the best performance for
each. Failing to select signs in AgA/Sign leads to poorer collective results.
Fig. 4(b) and Fig. 4(d) compare the social welfare achieved by AgA, with the
optimal $\lambda$ value, with baseline methods. Here, AgA $(\lambda=100)$ in
Cleanup and AgA $(\lambda=0.1)$ in Harvest surpass the benchmark methods for
the majority of the training process. Table 2 presents the peak social welfare
achieved during training alongside the equality metric. For simplicity, the
AgA column denotes the respective optimal $\lambda$ for each scenario. In
Cleanup, AgA surpasses the second-best method, Simul-Co, by over 10 points.
However, although Simul-Ind shows superior equality performance, it delivers
the lowest social welfare. Contrarily, AgA achieves a satisfactory balance
between equity and team performance. Analogous conclusions apply to the
Harvest, where AgA outperforms baselines in social welfare and equality.

(a) MMM2: AgA with various $\lambda$ and AgA/Sign

(b) MMM2: comparison between AgA and baselines

Figure 5: The comparison of win rates on the mixed-motive MMM2 map of SMAC.
The left figure shows results of varying alignment parameter $\lambda$ values
in AgA, as well as AgA sans sign selection (AgA/Sign), The right figure
compare the win rate of AgA $(\lambda=100)$ with baselines. The bold lines
illustrate the mean of the win rate over 3 seeds, while the encompassing
shaded regions depict the standard deviation.

###  5.3 Mixed-motive SMAC

Despite their widespread use in the study of mixed-motive games, sequential
social dilemma games can be relatively simplistic compared to other testbeds
in the field of MARL, particularly when considering real-world scenarios.
Cooperative Multi-Agent Reinforcement Learning often adopts more intricate
environments such as SMAC (Samvelyan et al., 2019). In this game environment,
agents must collaborate to defeat their opponents. We modify the MMM2 map from
SMAC as a mixed-motive testbed. Here, agents command various game entities
confronting opposing forces. Unlike the original StarCraft II game’s team-
oriented architecture, we instill individual interests in each agent to
enhance mixed-motive characteristics. Reward mechanisms have been modified
such that an agent’s individual reward aligns with the damage it inflicts on
the enemy, replacing the standard practice of distributing total damage across
all agents. Penalties for agent removal also reinforce self-preservation,
accentuating inherent agent selfishness. The experimental implementation
utilizes the IPPO algorithm (de Witt et al., 2020) for Simul-Ind, while
employing the MAPPO framework (Yu et al., 2022) for Simul-Co, SVO, CGA, and
AgA. More details can be found in Appendix C.2.

Results. Fig. 5(a) compares average win rates for various $\lambda$ parameters
in AgA, also encompassing AgA without sign selection, as stated in Corollary
4.3. The results suggest comparable performance for $\lambda=1$ and $100$,
with a lower value of $0.1$ trailing noticeably. Notably, AgA with
$\lambda=0.1$ underperforms, even when contrasted with AgA’s ablation study.
Fig. 5(b) benchmarks the win rate for AgA $(\lambda=100)$ against Simul-Ind,
Simul-Co, CGA, and SVO. Within this context, Simul-Ind, implemented via IPPO,
struggles with the mixed-motive MMM2 task. Impressively, our AgA
$(\lambda=100)$ method achieves a win rate peak of $0.85$ (standard deviation
of $0.09$), significantly outperforming the SVO method that only nets $44.55$.

##  6 Conclusion

In this paper, we propose AgA, an gradient adjustment method, specifically
designed to align individual and collective objectives within mixed-motive
cooperation scenarios. To materialize this, we first model the mixed-motive
game as a differentiable game, thereby facilitating the analysis of learning
dynamics. Thereafter, we analyze the optimization paths in a toy
differentiable mixed-motive game. We reveal that optimization techniques that
heavily rely on collective loss suffer from inherent limitations. These
approaches often overlook individual preferences, and existing gradient
adjustment methods are inadequate for addressing mixed-motive cooperation
challenges. Our AgA strategy efficiently bridges the gap between individual
and collective objectives. The optimization paths further support our
theoretical claims by demonstrating that careful selection of the sign of the
alignment weight enables convergence towards stable fixed points while
escaping unstable ones. Comprehensive experiments conducted on mixed-motive
testbeds and modified SMAC environments provide further evidence of the
superior performance of AgA. It consistently outperforms existing baselines
across multiple evaluation metrics.

Limitations and Future Work. The experiments conducted in this study were
confined to a single map of the SMAC environment. Our future objectives
include investigating the mixed-motive cooperative mechanism in real-world
scenarios and developing a more complex mixed-motive testbed. In this paper,
while we strive to align the objectives of both individuals and the
collective, our primary objective is to converge towards a stable equilibrium
of the collective objective. For future research, we intend to broaden our
comprehension of how individual objectives interact in mixed-motive games,
placing a greater emphasis on understanding their dynamics in mixed-motive
cooperation.

## Impact Statements

This paper presents a novel approach in the field of multi-agent learning,
aimed at advancing collaborations with mixed motivations. The proposed
framework addresses a fundamental challenge in machine learning, wherein
agents with diverse objectives are required to cooperate to achieve collective
goals. The work described in this paper holds significant potential for
various societal applications. By enabling effective cooperation among agents
with different motivations, our approach can be leveraged in domains such as
games, autonomous systems, smart cities, and decentralized resource
allocation. Such advancements have numerous societal consequences, including
improved efficiency in transportation systems, optimized resource allocation
in energy grids, and enhanced decision-making in complex multi-agent
environments. Furthermore, our findings contribute to the broader field of
machine learning by offering insights into managing mixed-motivation
scenarios. Consequently, our work paves the way for future research and
innovation, driving progress in multi-agent learning and its applications
across various domains.

## References

  * Anastassacos et al. (2021) Anastassacos, N., García, J., Hailes, S., and Musolesi, M.  Cooperation and reputation dynamics with reinforcement learning.  In Dignum, F., Lomuscio, A., Endriss, U., and Nowé, A. (eds.), _AAMAS ’21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021_ , pp. 115–123. ACM, 2021.  doi: 10.5555/3463952.3463972.  URL https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p115.pdf.
  * Apt & Schäfer (2014) Apt, K. R. and Schäfer, G.  Selfishness level of strategic games.  _J. Artif. Int. Res._ , 49(1):207–240, jan 2014.  ISSN 1076-9757.
  * Balduzzi et al. (2018) Balduzzi, D., Racaniere, S., Martens, J., Foerster, J., Tuyls, K., and Graepel, T.  The mechanics of n-player differentiable games.  In _International Conference on Machine Learning_ , pp. 354–363. PMLR, 2018.
  * Chen et al. (2023) Chen, X., Vadori, N., Chen, T., and Wang, Z.  Learning to optimize differentiable games.  In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pp. 5036–5051. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/chen23ab.html.
  * Daskalakis et al. (2018) Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H.  Training gans with optimism, 2018.
  * David (1968) David, H. A.  Gini’s mean difference rediscovered.  _Biometrika_ , 55(3):573–575, 1968.  ISSN 00063444.  URL http://www.jstor.org/stable/2334264.
  * de Witt et al. (2020) de Witt, C. S., Gupta, T., Makoviichuk, D., Makoviychuk, V., Torr, P. H. S., Sun, M., and Whiteson, S.  Is independent learning all you need in the starcraft multi-agent challenge?  _CoRR_ , abs/2011.09533, 2020.  URL https://arxiv.org/abs/2011.09533.
  * Du et al. (2023) Du, Y., Leibo, J. Z., Islam, U., Willis, R., and Sunehag, P.  A review of cooperation in multi-agent learning, 2023.
  * Foerster et al. (2018) Foerster, J. N., Chen, R. Y., Al-Shedivat, M., Whiteson, S., Abbeel, P., and Mordatch, I.  Learning with opponent-learning awareness, 2018.
  * Gidel et al. (2020) Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste-Julien, S.  A variational inequality perspective on generative adversarial networks, 2020.
  * Hostallero et al. (2020) Hostallero, D. E., Kim, D., Moon, S., Son, K., Kang, W. J., and Yi, Y.  Inducing cooperation through reward reshaping based on peer evaluations in deep multi-agent reinforcement learning.  In Seghrouchni, A. E. F., Sukthankar, G., An, B., and Yorke-Smith, N. (eds.), _Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, Auckland, New Zealand, May 9-13, 2020_ , pp. 520–528. International Foundation for Autonomous Agents and Multiagent Systems, 2020.  doi: 10.5555/3398761.3398825.  URL https://dl.acm.org/doi/10.5555/3398761.3398825.
  * Hughes et al. (2018) Hughes, E., Leibo, J. Z., Phillips, M., Tuyls, K., Duéñez-Guzmán, E. A., Castañeda, A. G., Dunning, I., Zhu, T., McKee, K. R., Koster, R., Roff, H., and Graepel, T.  Inequity aversion improves cooperation in intertemporal social dilemmas.  In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , pp. 3330–3340, 2018.  URL https://proceedings.neurips.cc/paper/2018/hash/7fea637fd6d02b8f0adf6f7dc36aed93-Abstract.html.
  * Hughes et al. (2020) Hughes, E., Anthony, T. W., Eccles, T., Leibo, J. Z., Balduzzi, D., and Bachrach, Y.  Learning to resolve alliance dilemmas in many-player zero-sum games.  _CoRR_ , abs/2003.00799, 2020.  URL https://arxiv.org/abs/2003.00799.
  * Isaacs (1965) Isaacs, R.  _Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization_.  Dover books on mathematics. Wiley, 1965.  ISBN 9780471428602.  URL https://books.google.co.uk/books?id=gtlQAAAAMAAJ.
  * Jaques et al. (2019) Jaques, N., Lazaridou, A., Hughes, E., Gulcehre, C., Ortega, P., Strouse, D., Leibo, J. Z., and De Freitas, N.  Social influence as intrinsic motivation for multi-agent deep reinforcement learning.  In _International conference on machine learning_ , pp. 3040–3049. PMLR, 2019.
  * Kingma & Ba (2015) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  In Bengio, Y. and LeCun, Y. (eds.), _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.  URL http://arxiv.org/abs/1412.6980.
  * Leibo et al. (2017) Leibo, J. Z., Zambaldi, V. F., Lanctot, M., Marecki, J., and Graepel, T.  Multi-agent reinforcement learning in sequential social dilemmas.  _CoRR_ , abs/1702.03037, 2017.  URL http://arxiv.org/abs/1702.03037.
  * Letcher et al. (2019) Letcher, A., Balduzzi, D., Racanière, S., Martens, J., Foerster, J., Tuyls, K., and Graepel, T.  Differentiable game mechanics.  _Journal of Machine Learning Research_ , 20(84):1–40, 2019.  URL http://jmlr.org/papers/v20/19-008.html.
  * Letcher et al. (2021) Letcher, A., Foerster, J., Balduzzi, D., Rocktäschel, T., and Whiteson, S.  Stable opponent shaping in differentiable games, 2021.
  * Li et al. (2024) Li, Y., Zhang, S., Sun, J., Zhang, W., Du, Y., Wen, Y., Wang, X., and Pan, W.  Tackling cooperative incompatibility for zero-shot human-ai coordination, 2024.
  * Lu et al. (2022) Lu, C., Willi, T., de Witt, C. A. S., and Foerster, J. N.  Model-free opponent shaping.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., and Sabato, S. (eds.), _International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 14398–14411. PMLR, 2022.  URL https://proceedings.mlr.press/v162/lu22d.html.
  * Lupu & Precup (2020) Lupu, A. and Precup, D.  Gifting in multi-agent reinforcement learning.  In _Proceedings of the 19th International Conference on autonomous agents and multiagent systems_ , pp. 789–797, 2020.
  * Macy & Flache (2002) Macy, D. and Flache, A.  Learning dynamics in social dilemmas.  _Proceedings of the National Academy of Sciences of the United States of America_ , 99 Suppl 3:7229–36, 06 2002.  doi: 10.1073/pnas.092080099.
  * McKee et al. (2020a) McKee, K. R., Gemp, I., McWilliams, B., Duéñez-Guzmán, E. A., Hughes, E., and Leibo, J. Z.  Social diversity and social preferences in mixed-motive reinforcement learning.  In Seghrouchni, A. E. F., Sukthankar, G., An, B., and Yorke-Smith, N. (eds.), _Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, Auckland, New Zealand, May 9-13, 2020_ , pp. 869–877. International Foundation for Autonomous Agents and Multiagent Systems, 2020a.  doi: 10.5555/3398761.3398863.  URL https://dl.acm.org/doi/10.5555/3398761.3398863.
  * McKee et al. (2020b) McKee, K. R., Gemp, I., McWilliams, B., Duéñez-Guzmán, E. A., Hughes, E., and Leibo, J. Z.  Social diversity and social preferences in mixed-motive reinforcement learning, 2020b.
  * McKee et al. (2023) McKee, K. R., Hughes, E., Zhu, T. O., Chadwick, M. J., Koster, R., Castaneda, A. G., Beattie, C., Graepel, T., Botvinick, M., and Leibo, J. Z.  A multi-agent reinforcement learning model of reputation and cooperation in human groups, 2023.
  * Mescheder et al. (2017) Mescheder, L. M., Nowozin, S., and Geiger, A.  The numerics of gans.  In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pp. 1825–1835, 2017.  URL https://proceedings.neurips.cc/paper/2017/hash/4588e674d3f0faf985047d4c3f13ed0d-Abstract.html.
  * Peysakhovich & Lerer (2018) Peysakhovich, A. and Lerer, A.  Prosocial learning agents solve generalized stag hunts better than selfish ones.  In André, E., Koenig, S., Dastani, M., and Sukthankar, G. (eds.), _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018_ , pp. 2043–2044. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM, 2018.  URL http://dl.acm.org/citation.cfm?id=3238065.
  * Philip S. Gallo & McClintock (1965) Philip S. Gallo, J. and McClintock, C. G.  Cooperative and competitive behavior in mixed-motive games.  _Journal of Conflict Resolution_ , 9(1):68–78, 1965.  doi: 10.1177/002200276500900106.  URL https://doi.org/10.1177/002200276500900106.
  * Raffin et al. (2021) Raffin, A., Hill, A., Gleave, A., Kanervisto, A., Ernestus, M., and Dormann, N.  Stable-baselines3: Reliable reinforcement learning implementations.  _Journal of Machine Learning Research_ , 22(268):1–8, 2021.  URL http://jmlr.org/papers/v22/20-1364.html.
  * Rapoport (1974) Rapoport, A.  Prisoner’s dilemma—recollections and observations.  In _Game Theory as a Theory of a Conflict Resolution_ , pp. 17–34. Springer, 1974.
  * Samvelyan et al. (2019) Samvelyan, M., Rashid, T., de Witt, C. S., Farquhar, G., Nardelli, N., Rudner, T. G. J., Hung, C., Torr, P. H. S., Foerster, J. N., and Whiteson, S.  The starcraft multi-agent challenge.  In Elkind, E., Veloso, M., Agmon, N., and Taylor, M. E. (eds.), _Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019_ , pp. 2186–2188. International Foundation for Autonomous Agents and Multiagent Systems, 2019.  URL http://dl.acm.org/citation.cfm?id=3332052.
  * Vinitsky et al. (2019) Vinitsky, E., Jaques, N., Leibo, J., Castenada, A., and Hughes, E.  An open source implementation of sequential social dilemma games.  https://github.com/eugenevinitsky/sequential_social_dilemma_games/issues/182, 2019.  GitHub repository.
  * Vinitsky et al. (2023) Vinitsky, E., Köster, R., Agapiou, J. P., Duéñez-Guzmán, E. A., Vezhnevets, A. S., and Leibo, J. Z.  Eugene2023collectiveized multi-agent settings.  _Collective Intelligence_ , 2(2):26339137231162025, 2023.  doi: 10.1177/26339137231162025.  URL https://doi.org/10.1177/26339137231162025.
  * Wang et al. (2020) Wang, J., Zhang, Y., Kim, T., and Gu, Y.  Shapley q-value: A local reward approach to solve global reward games.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pp. 7285–7292. AAAI Press, 2020.  doi: 10.1609/AAAI.V34I05.6220.  URL https://doi.org/10.1609/aaai.v34i05.6220.
  * Willi et al. (2022) Willi, T., Letcher, A. H., Treutlein, J., and Foerster, J.  COLA: Consistent learning with opponent-learning awareness.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 23804–23831. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/willi22a.html.
  * Yang et al. (2020) Yang, J., Li, A., Farajtabar, M., Sunehag, P., Hughes, E., and Zha, H.  Learning to incentivize other learning agents.  _Advances in Neural Information Processing Systems_ , 33:15208–15219, 2020.
  * Yu et al. (2022) Yu, C., Velu, A., Vinitsky, E., Gao, J., Wang, Y., Bayen, A. M., and Wu, Y.  The surprising effectiveness of PPO in cooperative multi-agent games.  In _NeurIPS_ , 2022.
  * Zhong et al. (2023) Zhong, Y., Kuba, J. G., Hu, S., Ji, J., and Yang, Y.  Heterogeneous-agent reinforcement learning, 2023.

##  Appendix A Proof of Corollary 4.3

See 4.3

###### Proof.

Prior to embarking on the elucidation of the corollary’s proof, it is
essential to first introduce relevant notations and the foundational concepts.
Take note of the notation $\theta({\bm{a}},{\bm{b}})$, which symbolizes the
angular measure between two vectors. Furthermore, we write
$\theta_{\lambda}(\tilde{{\bm{\xi}}},{\bm{w}})$ to represent the angular
measure between AgA gradient $\tilde{{\bm{\xi}}}$ and a reference update
direction ${\bm{w}}$. For simplicity, we use
$\tilde{{\bm{\xi}}}={\bm{u}}+\lambda{\bm{v}}$ to denote the AgA gradient
$\tilde{{\bm{\xi}}}={\bm{\xi}}_{c}+\lambda\left({\bm{\xi}}+{\bm{H}}_{c}^{T}{\bm{\xi}}_{c}\right),$as
defined in Eq. 2. Specifically, ${\bm{u}}$ denotes collective gradient
${\bm{\xi}}_{c}$ and ${\bm{v}}$ denotes
$\left({\bm{\xi}}+{\bm{H}}_{c}^{T}{\bm{\xi}}_{c}\right)$.

We then extend the definition of infinitesimal alignment (Balduzzi et al.,
2018) to our proposed AgA gradient. Given a third reference vector ${\bm{w}}$,
the infinitesimal alignment for AgA gradient $\tilde{{\bm{\xi}}}$ with
${\bm{w}}$ is defined as

$align(\tilde{{\bm{\xi}}},{\bm{w}}):=\frac{d}{d\lambda}\\{cos^{2}\theta_{\lambda}\\}_{|\lambda=0}.$
(3)

Intuitively, we may presume that vectors ${\bm{u}}$ and ${\bm{w}}$ are
directionally aligned, given that ${\bm{u}}^{T}{\bm{w}}>0$. In this scenario,
$align>0$ implies that vector ${\bm{v}}$ is drawing ${\bm{u}}$ closer towards
the reference vector ${\bm{w}}$. Conversely, vector ${\bm{v}}$ is propelling
${\bm{u}}$ away from ${\bm{w}}$. Similar arguments hold for $align<0$:
${\bm{v}}$ pushes ${\bm{u}}$ away from the reference vector ${\bm{w}}$ when
${\bm{u}}$ and ${\bm{w}}$ share the same directional orientation. Conversely,
${\bm{v}}$ pulls ${\bm{u}}$ towards the reference vector ${\bm{w}}$ when the
vectors ${\bm{u}}$ and ${\bm{w}}$ are not oriented in the same direction.

The ensuing lemma provides a simplified method for determining the sign of
$align$, circumventing the need for generating an exact solution.

######  Lemma A.1 (Sign of $align$.).

Given AgA gradient $\tilde{{\bm{\xi}}}$ and reference vector
$\nabla{\mathcal{H}}_{c}$, the sign of infinitesimal alignment $align$ could
be calculated by

$sign\left(align(\tilde{{\bm{\xi}}},\nabla{\mathcal{H}}_{c})\right)=sign\left(\langle{\bm{\xi}},\nabla{\mathcal{H}}_{c}\rangle(\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle+\|\nabla{\mathcal{H}}_{c}\|^{2})\right).$

###### Proof.

By the definition of $\theta_{\lambda}$, we could directly get:

$\displaystyle cos^{2}\theta_{\lambda}$ (4a) $\displaystyle=$
$\displaystyle\left(\frac{\langle\tilde{{\bm{\xi}}},\nabla{\mathcal{H}}_{c}\rangle}{\|\tilde{{\bm{\xi}}}\|^{2}\cdot\|\nabla{\mathcal{H}}_{c}\|^{2}}\right)^{2}$
(4b) $\displaystyle=$
$\displaystyle\left(\frac{\langle{\bm{\xi}}_{c}+\lambda({\bm{\xi}}+\nabla{\mathcal{H}}_{c}),\nabla{\mathcal{H}}_{c}\rangle}{\|\tilde{{\bm{\xi}}}\|^{2}\cdot\|\nabla{\mathcal{H}}_{c}\|^{2}}\right)^{2}$
(4c) $\displaystyle=$
$\displaystyle\frac{\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle^{2}+2\lambda\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle\langle{\bm{\xi}}+\nabla{\mathcal{H}}_{c},\nabla{\mathcal{H}}_{c}\rangle+{\mathcal{O}}(\lambda^{2})}{\left(\|\tilde{{\bm{\xi}}}\|^{2}\cdot\|\nabla{\mathcal{H}}_{c}\|^{2}\right)^{2}}$
(4d) $\displaystyle=$
$\displaystyle\frac{\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle^{2}+2\lambda\langle{\bm{\xi}},\nabla{\mathcal{H}}_{c}\rangle\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle+2\lambda\|\nabla{\mathcal{H}}_{c}\|^{2}\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle+{\mathcal{O}}(\lambda^{2})}{\left(\|\tilde{{\bm{\xi}}}\|^{2}\cdot\|\nabla{\mathcal{H}}_{c}\|^{2}\right)^{2}}$
(4e) $\displaystyle=$
$\displaystyle\frac{\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle^{2}+2\lambda\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle(\|\nabla{\mathcal{H}}_{c}\|^{2}+\langle{\bm{\xi}},\nabla{\mathcal{H}}_{c}\rangle)+{\mathcal{O}}(\lambda^{2})}{\left(\|\tilde{{\bm{\xi}}}\|^{2}\cdot\|\nabla{\mathcal{H}}_{c}\|^{2}\right)^{2}}.$
(4f)

In accordance with the established definition of infinitesimal alignment, it
becomes feasible to further compute the sign of $align$ by taking the
derivative of $\lambda$ with respect to $cos^{2}\theta_{\lambda}$:

$\displaystyle
sign\left(align(\tilde{{\bm{\xi}}},\nabla{\mathcal{H}}_{c})\right)$ (5a)
$\displaystyle=$ $\displaystyle
sign\left(\frac{d}{d\lambda}cos^{2}\theta_{\lambda}\right)$ (5b)
$\displaystyle=$ $\displaystyle
sign\left(\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle\left(\langle{\bm{\xi}},\nabla{\mathcal{H}}_{c}\rangle+\|\nabla{\mathcal{H}}_{c}\|^{2}\right)\right).$
(5c)

∎

Lemma A.1 empowers us to calculate the sign of infinitesimal alignment relying
on components that are readily computable.

Let us observe
$\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle={\bm{\xi}}_{c}^{T}{\bm{H}}_{c}{\bm{\xi}}_{c}$
for symmetric Hessian matrix ${\bm{H}}_{c}$. Under the assumption of
${\bm{\xi}}_{c}\neq 0$, we could derive:

$\left\\{\begin{aligned} &if\ {\bm{H}}_{c}\succeq 0,then\
\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle\geq 0;\\\ &if\
{\bm{H}}_{c}\prec 0,then\
\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle<0.\end{aligned}\right.$
(6)

As demonstrated by Eq. 6, when situated in the neighborhood of a stable fixed
point (that is to say, ${\bm{H}}_{c}\succeq 0$), we observe
$\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle\geq 0$. In converse
circumstances, $\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle<0$
occurs. Following this, we shall proceed to delve into two specific scenarios:
stability and instability of the fixed point.

1) Case 1: In a neighborhood of a stable fixed point. If we are in a
neighborhood of a stable fixed point then
$\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle\geq 0$. This indicates
that both vectors ${\bm{\xi}}_{c}$ and $\nabla{\mathcal{H}}_{c}$ point in the
same direction, i.e.,
$\theta({\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c})\leq\pi/2$. Referring to Lemma
A.1, the sign of $align(\tilde{{\bm{\xi}}},\nabla{\mathcal{H}}_{c})$ is the
same as the sign of
$\langle{\bm{\xi}},\nabla{\mathcal{H}}_{c}\rangle+\|\nabla{\mathcal{H}}_{c}\|^{2}$
if $\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle\geq 0$. Consequently,
we have
$sign(\lambda)=sign(\langle{\bm{\xi}},\nabla{\mathcal{H}}_{c}\rangle+\|\nabla{\mathcal{H}}_{c}\|^{2})=sign(align)$
matching the claim of our corollary.

Let us now conjecture the scenarios of $sign(align)$, namely, $sign(align)\geq
0$ or $sign(align)<0$. When $sign(align)\geq 0$, it follows that
$sign(\lambda)\geq 0$. Consequently, vector ${\bm{v}}$ will draw ${\bm{u}}$
towards ${\bm{w}}$. Subsequently, when $sign(align)<0$, we observe that
$sign(\lambda)<0$. A negative $\lambda$ reverses the mechanism such that
${\bm{v}}$ pushes ${\bm{u}}$ away from ${\bm{w}}$, aligning with the
discussion following Eq. 3 that assumes a positive $\lambda$. Thus, regardless
of the sign of $align$, if we set
$sign(\lambda)=sign(\langle{\bm{\xi}},\nabla{\mathcal{H}}_{c}\rangle+\|\nabla{\mathcal{H}}_{c}\|^{2})$,
vector ${\bm{v}}$ ensures ${\bm{u}}$ is drawn towards ${\bm{w}}$.

From now, we prove that in the neighborhood of a stable fixed point, if we let
$sign(\lambda)$ satisfy
$\lambda\cdot\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle(\langle{\bm{\xi}},\nabla{\mathcal{H}}_{c}\rangle+\|\nabla{\mathcal{H}}_{c}\|^{2})\geq
0$, the AgA gradient $\tilde{{\bm{\xi}}}$ will be pulled more closer to
$\nabla{\mathcal{H}}_{c}$ than ${\bm{\xi}}_{c}$.

2) Case 2: In a neighborhood of a unstable fixed point. The proofing approach
for the unstable case exhibits similarity to Case 1.

Therefore, we prove that if we let the sign of $\lambda$ follows the condition
$\lambda\cdot\langle{\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c}\rangle(\langle{\bm{\xi}},\nabla{\mathcal{H}}_{c}\rangle+\|\nabla{\mathcal{H}}_{c}\|^{2})\geq
0$, the optimization process using the AgA method exhibit following
attributes. In areas close to fixed points, 1) if the point is stable, the AgA
gradient will be pulled toward this point, which means that
$\theta(\tilde{{\bm{\xi}}},\nabla{\mathcal{H}}_{c})\leq\theta({\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c})$;
2) if the point represents unstable equilibria, the AgA gradient will be
pushed out of the point, indicating that
$\theta(\tilde{{\bm{\xi}}},\nabla{\mathcal{H}}_{c})\geq\theta({\bm{\xi}}_{c},\nabla{\mathcal{H}}_{c})$.
An illustrative example of the corollary is provided in Fig. 2.

∎

##  Appendix B Additional Experiment Results

Figure 6:  The scatter of actions in a two-player public goods game achieved
through different optimization methods. Each circle represents the position
attained within a maximum of 100 steps, with the color indicating the
corresponding method. The ’X’ mark represents the mean actions of 50 random
runs. With the exception of Simul-Co, the baseline methods converge towards
the Nash equilibrium (0,0). Notably, while both AgA and Simul-Co display
altruistic behavior, the actions of AgA are more tightly clustered around the
(1,1) point compared to Simul-Co.

###  B.1 Result Visualization of Two-player Public Goods Game

Fig. 6 depicts the actions produced by various methods in a two-player public
game. The action generated by each method is represented by a circle, which is
color-coded according to the corresponding method. To ensure fairness, each
method’s updates are constrained to a maximum of 100 steps. These methods
include the individual loss-driven simultaneous optimization (Simul-Ind), two
variants of gradient adjustment methods termed as CGA and SGA, and the
simultaneous optimization leveraging collective loss (Simul-Co) alongside our
proposed AgA, where $\lambda=1$. Each of these methods is fundamentally
underpinned by the gradient ascent algorithm. The illustration consolidates
data from 50 randomized runs initialized from diverse starting points. The ‘X’
demarcated circles indicate the average actions mapped to each method. From
the figure, it’s apparent that Simul-Ind, CGA, SGA, SVO tend to converge
towards scenarios where at least one player abstains from contributing, an
occurrence often tagged as ‘free-riding’. In contrast, Simul-Co (represented
by a yellow circle) and our AgA method (illustrated as a red circle) tend to
converge towards scenarios characterized by enhanced contributions or
’altruism’. The observed results underline that players employing the AgA
method exhibit heightened altruistic tendencies relative to those operating
under Simul-Co. Further, AgA exhibits a superior alignment towards socially
optimal outcome point $(1,1)$.

##  Appendix C Experiment Details

###  C.1 Social Dilemma Games: Cleanup and Harvest

SSD games (Vinitsky et al., 2019) implements the Harvest and Cleanup as grid
world games.The agents use partially observed graphics observation, which
contains a grid of $15\times 15$ centered on themselves. Compared to the
original Cleanup and Harvest games, SSD games add a fire beam mechanic, where
agents can fire on the grid to hit other partners. An agent will gain 1 reward
if harvesting an apple and -1 reward if firing a beam. Besides, being hit by a
beam will result in a 50 individual reward loss. Under this mechanic, selfish
agents can easily use fire to prevent others from harvesting apples to gain
more individual rewards but harm social welfare.

We utilized PPO algorithm in stable-baselines3 (Raffin et al., 2021) to
implement the baselines and our methods, with all the agents using separated
policy parameters for Simul-Ind and sharing same policy parameters for other
experiments. For SVO, we modify the individual reward to be
$r_{i}-\alpha(1-actan\left(\frac{sum_{j,j\neq i}r_{j}}{r_{i}}\right)$. To
employ CGA and AgAs to PPO training process, we compute both individual and
collective PPO-Clip policy losses and subsequently utilize them to calculate
the adjusted gradient through automatic differentiation. We don’t make changes
to the critic loss nor the critic net optimization process.

The hyper-parameters for PPO training are as follows.

  * •

The learning rate is 1e-4

  * •

The PPO clipping factor is 0.2.

  * •

The value loss coefficient is 1.

  * •

The entropy coefficient is 0.001.

  * •

The $\gamma$ is 0.99.

  * •

The total environment step is 1e7 for Harvest and 2e7 for Cleanup.

  * •

The environment episode length is 1000.

  * •

The grad clip is 40.

###  C.2 Mixed-motive StarCraft II

SMAC, often employed as a testbed within the sphere of cooperative MARL, is
characterized by the shared reward system among players. Within this paper, we
present the MMM2 map transformed as a versatile testbed designed for mixed-
motive cooperation. Specifically, MMM2 map encompasses 10 agents and 12
adversaries as enumerated below:

  * •

Controlled Agents: Comprised of 1 Medivac, 2 Marauders, and 7 Marines.

  * •

Adversaries: Incorporates 1 Medivac, 3 Marauders, and 8 Marines.

Moreover, this setting embodies both heterogeneity and asymmetry, where agents
within the same team exhibit diverse gaming skills. Additionally, the team
compositions, for instance, variation in agent number and type, differ in both
opposing factions. Consequently, the intricate gaming mechanism, the presence
of heterogeneous players, and the discernible asymmetry conspire to establish
an exemplary milieu conducive for the exploration of mixed-motive issues.

In order to create a mixed-motive testbed, we adjusted the reward system
hailing from the original SMAC environment. With this, we proposed a revamped
reward function that features two distinct components: a reward for imposing
damage and a penalty associated specifically with agent fatalities. In a move
to potentially intensify internal conflicts amongst agents, the reward for
imposing damage is solely allocated to the agent responsible for executing the
attack on the enemy. Additionally, the death of an agent results in the
imposition of an extra penalty. Consequently, this mechanism fosters an
environment where agents are predisposed towards individual protection and
separate reward acquisition, as opposed to collective cooperation.

Formally, the agent $i$’s reward at step $t$ is defined as follows:

$\text{delta-enemy}_{i}=\sum_{j\in\text{Enemy}\atop i\text{ hit }j\text{ at
}t}[(\text{previous-health}-\text{current-health})+(\text{previous-
shield}-\text{current-shield})]$

The individual reward for Player $i$ is determined as follows: If the player
dies, then $r_{i}=\text{delta-enemy}_{i}-\beta\times\text{penalty}$;
otherwise, if the player survives, then $r_{i}=\text{delta-enemy}_{i}$.

Experiment settings.  Simul-Ind leverages IPPO with recurrent policies and
distinct policy networks. Conversely, Simul-Co employs MAPPO with recurrent
policies and consolidated policy networks. The implementation of the IPPO and
MAPPO algorithms presented in this paper is founded on the methodology
detailed in (Yu et al., 2022). We utilize gradient adjustment optimization
methods, such as CGA and AgAs, derived from MAPPO, implementing gradient
adjustments as outlined in Algorithm 1.

The hyper-parameters for PPO-based training are as follows.

  * •

The learning rate is 5e-4

  * •

The PPO clipping factor is 0.2.

  * •

The value loss coefficient is 1.

  * •

The entropy coefficient is 0.01.

  * •

The $\gamma$ is 0.99.

  * •

The total environment step is 1e7.

  * •

The factor $\beta$ in reward function is 1.

  * •

The environment episode length is 400.