# Normative Disagreement as a Challenge for Cooperative AI

Julian Stastny
University of Tuebingen
<EMAIL_ADDRESS>
&Maxime Riché
Center on Long-Term Risk
<EMAIL_ADDRESS>
&Alexander Lyzhov
Center on Long-Term Risk
<EMAIL_ADDRESS>
&Johannes Treutlein
Vector Institute
University of Toronto
<EMAIL_ADDRESS>
&Allan Dafoe
DeepMind
<EMAIL_ADDRESS>
&Jesse Clifton
Center on Long-Term Risk
<EMAIL_ADDRESS>
Now at New York University

###### Abstract

Cooperation in settings where agents have both common and conflicting
interests (mixed-motive environments) has recently received considerable
attention in multi-agent learning. However, the mixed-motive environments
typically studied have a single cooperative outcome on which all agents can
agree. Many real-world multi-agent environments are instead bargaining
problems (BPs): they have several Pareto-optimal payoff profiles over which
agents have conflicting preferences. We argue that typical cooperation-
inducing learning algorithms fail to cooperate in BPs when there is room for
normative disagreement resulting in the existence of multiple competing
cooperative equilibria, and illustrate this problem empirically. To remedy the
issue, we introduce the notion of norm-adaptive policies. Norm-adaptive
policies are capable of behaving according to different norms in different
circumstances, creating opportunities for resolving normative disagreement. We
develop a class of norm-adaptive policies and show in experiments that these
significantly increase cooperation. However, norm-adaptiveness cannot address
residual bargaining failure arising from a fundamental tradeoff between
exploitability and cooperative robustness.

##  1 Introduction

Multi-agent contexts often exhibit opportunities for cooperation: situations
where joint action can lead to mutual benefits (Dafoe et al., 2020).
Individuals can engage in mutually beneficial trade; nation-states can enter
into treaties instead of going to war; disputants can settle out of court
rather than engaging in costly litigation. But a hurdle common to each of
these examples is that the agents will disagree about their ideal agreement.
Even if agreements benefit all parties relative to the status quo, different
agreements will benefit different parties to different degrees. These
circumstances can be called bargaining problems (Schelling, 1956).

As AI systems are deployed to act on behalf of humans in more real-world
circumstances, they will need to be able to act effectively in bargaining
problems — from commercial negotiations in the nearer-term (e.g., Chakraborty
et al. (2020)) to high-stakes strategic decision-making in the longer-term
(Geist and Lohn, 2018). Moreover, agents may be trained independently and
offline before interacting with one another in the world. This raises concerns
about future AI systems following incompatible norms for arriving at solutions
to bargaining problems, analogously to disagreements about fairness which
create hurdles to international cooperation on critical issues such as climate
policy (Albin, 2001; Ringius et al., 2002).

Our contributions are as follows. We introduce a taxonomy of cooperation
games, including bargaining problems (Section 3). We relate their difficulty
to the degree of normative disagreement, i.e., differences over principles for
selecting among mutually beneficial outcomes, which we formalize in terms of
welfare functions. Normative disagreement does not arise in purely cooperative
games or simple sequential social dilemmas (Leibo et al., 2017), but is an
important obstacle for cooperation in what we call asymmetric bargaining
problems. Following this, we introduce the notion of norm-adaptive policies –
policies which can play according to different norms depending on the
circumstances. In several multi-agent learning environments we highlight the
difficulty of bargaining between norm-unadaptive policies (Section 4). We then
contrast this with a class of norm-adaptive policies (Section 5) based on
Lerer and Peysakhovich (2017)’s approximate Markov tit-for-tat algorithm. We
show that this improves performance in bargaining problems. However, there
remain limitations, most fundamentally a tradeoff between exploitability and
the robustness of cooperation.

##  2 Related work

BargainingAsymmetric BargainingMixed- motiveCoordinationSSDs Figure 1: Venn
diagram of cooperation problems.

The field of multi-agent learning (MAL) has recently paid considerable
attention to problems of cooperation in mixed-motive games, in which agents
have conflicting preferences. Much of this work has been focused on sequential
social dilemmas (SSDs) (e.g., Peysakhovich and Lerer 2017; Lerer and
Peysakhovich 2017; Eccles et al. 2019). The classic example of a social
dilemma is the Prisoner’s Dilemma, and the SSDs studied in this literature are
similar to the Prisoner’s Dilemma in that there is a single salient notion of
“cooperation”. This means that it is relatively easy for actors to coordinate
in their selection of policies to deploy in these settings.
Cao et al. (2018) look at negotiation between deep reinforcement learners, but
not between independently trained agents. Several authors have recently
investigated the board game Diplomacy (Paquette et al., 2019; Anthony et al.,
2020; Gray et al., 2021) which contains implicit bargaining problems amongst
players. Bargaining problems are also investigated in older MAL literature
(e.g., Crandall and Goodrich 2011) as well as literature on automated
negotiation (e.g., Kraus and Arkin 2001; Baarslag et al. 2013), but also not
between independently trained agents. Considerable work has gone into
understanding the emergence of norms in both human (Bendor and Swistak, 2001;
Boyd and Richerson, 2009) and artificial societies (Walker and Wooldridge,
1995; Shoham and Tennenholtz, 1997; Sen and Airiau, 2007). Especially relevant
are empirical studies of bargaining across cultural contexts (Henrich et al.,
2001). There is also recent multi-agent reinforcement learning work on norms
(Hadfield-Menell et al., 2019; Lerer and Peysakhovich, 2019; Köster et al.,
2020) is also relevant here as bargaining problems can be understood as
settings in which there are multiple efficient but incompatible norms.
However, much less attention has been paid in these literatures to how agents
with different norms are or aren’t able to overcome normative disagreement.

There are large game-theoretic literatures on bargaining (for a review see
Muthoo (2001)). This includes a long tradition of work on cooperative
bargaining solutions, which tries to establish normative principles for
deciding among mutually beneficial agreements (Thomson, 1994). We will draw on
this work in our discussion of normative (dis)agreement below.

Lastly, the class of norm-adaptive policies we develop in Section 5 —
$\texttt{amTFT}(\mathcal{W})$ — can be seen as a more general variant of an
approach proposed by Boutilier (1999) for coordinating in pure coordination
games. As it implicitly searches for overlap in the agents’ sets of allowed
welfare functions, it is also similar to Rosenschein and Genesereth (1988)’s
approach to reaching agreement in general-sum games via sets of proposals by
each agent.

##  3 Coordination, bargaining and normative disagreement

We are interested in a setting in which multiple actors (“principals”) train
machine learning systems offline, and then deploy them into an environment in
which they interact. For instance, two different companies might separately
train systems to negotiate on their behalf and deploy them without explicit
coordination on deployment. In this section, we develop a taxonomy of
environments that these agents might face, and relate these different types of
environments to the difficulty of bargaining.

###  3.1 Preliminaries

We formalize multi-agent environments as partially observable stochastic games
(POSGs). For simplicity we assume two players, $i=1,2$. We will index player
$i$’s counterpart by $-i$. Each player has an action space
${\mathcal{A}}_{i}$. There is a space $\mathcal{S}$ of states $S^{t}$ which
evolve according to a Markovian transition function $P(S^{t+1}\mid
S^{t},A_{1}^{t},A_{2}^{t})$. At each time step, each player sees an
observation $O_{i}^{t}$ which depends on $S^{t}$. Thus each player has an
accumulating history of observations
$\mathcal{H}_{i}^{t}=\\{O_{1}^{v},A_{1}^{v}\\}_{v=1}^{t}$. We refer to the set
of all histories for player $i$ as
$\mathcal{H}_{i}=\cup_{t=1}^{\infty}\mathcal{H}^{t}_{i}$ and assume for
simplicity that the initial observation history is fixed and common knowledge:
$h^{0}_{1}=h^{0}_{2}\equiv h^{0}$. Finally, principals choose among policies
$\pi_{i}:\mathcal{H}_{i}\rightarrow\Delta({\mathcal{A}}_{i})$, which we
imagine as artificial agents deployed by the principals. We will refer to
policy profiles generically as $\pi\in\Pi:=\Pi_{1}\times\Pi_{2}$.

Each player has a reward function $r_{i}$, such that
$r_{i}(S^{t},A_{1}^{t},A_{2}^{t})$ is their reward at time $t$. We define the
value to player $i$ of policy profile $\pi$ starting at history $h_{i}^{t}$ as
$V_{i}(h_{i}^{t},\pi)=\mathbb{E}_{\pi}\left[\sum_{v=t}^{\infty}\gamma^{v-t}r_{i}(S^{v},A_{1}^{v},A_{2}^{v})\mid
H_{i}^{t}=h_{i}^{t}\right]$, where $\gamma\in[0,1)$ is a discount factor, and
the value of a policy profile to player $i$ as $V_{i}(\pi)=V_{i}(h^{0},\pi)$.
A payoff profile is then a tuple $(V_{1}(\pi),V_{2}(\pi))$. We say that $\pi$
is a (Nash) equilibrium of a POSG if
$\pi_{i}\in\operatorname*{arg\,max}_{\pi_{i}^{\prime}\in\Pi_{i}}V_{i}(h^{0},\pi_{i}^{\prime},\pi_{-i})$
for $i=1,2$. We say that $\pi$ is Pareto-optimal if for $i=1,2$ and
$\pi^{\prime}\in\Pi$ we have that $V_{i}(\pi^{\prime})>V_{i}(\pi)$ implies
$V_{-i}(\pi^{\prime})<V_{-i}(\pi).$

###  3.2 Coordination problems

We define a coordination problem as a game involving multiple Pareto-optimal
equilibria (cf. Zhang and Hofbauer 2015), which require some coordinated
action to achieve. That is, if the players disagree about which equilibrium
they are playing, they will not reach a Pareto-optimal outcome. A pure
coordination problem is a game in which there are multiple Pareto-optimal
equilibria over which agents have identical interests. Although agents may
still experience difficulties in pure coordination games, for instance due to
a noisy communication channel, they are made easier by the fact that
principals are indifferent between the Pareto-optimal equilibria.

###  3.3 Bargaining problems and normative disagreement

We define a bargaining problem (BP) to be a game in which there are multiple
Pareto-optimal equilibria over which the principals have conflicting
preferences. These equilibria represent more than one way to collaborate for
mutual benefit, or put in another way, for sharing a surplus. Thus a
bargaining problem is a mixed-motive coordination problem, in which there is
conflicting interest between Pareto-optimal equilibria and common interest in
reaching a Pareto-optimal equilibrium.

We can distinguish between BPs which are symmetric and asymmetric games. A
2-player game is symmetric if for any attainable payoff profile $(a,b)$ there
exists a profile $(b,a)$. The reason this distinction is important is that all
(finite) symmetric games have a symmetric Nash equilibrium (Nash, 1990); thus
symmetric games have a natural set of focal points (Schelling, 1958) for
aiding coordination in mixed-motive contexts, while asymmetric BPs may not.
Similarly, given a chance to play a correlated equilibrium (Aumann, 1974),
agents in a symmetric BP could play according to a correlated equilibrium
which randomizes using a symmetric distribution over Pareto-optimal payoff
profiles.

Figure 3.3 displays the payoff matrices of three coordination games: Pure
Coordination, and two variants of Bach or Stravinsky (BoS), one of which is a
symmetric BP and one of which is an asymmetric BP. Pure Coordination is not a
BP because it is not a mixed-motive game as the players only care about
playing the same action. On the other hand, in the case of symmetric BoS the
players do have conflicting interest, however, there is a correlated
equilibrium – tossing a commonly observed fair coin – that is intuitively the
most reasonable way of coordinating: It both maximizes the total payoff and
offers each player the same expected reward.

& B  S
---
| B |  $1,1$ |  $0,0$
| S |  $0,0$ |  $1,1$

(a)

& B  S
---
| B |  $3,2$ |  $0,0$
| S |  $0,0$ |  $2,3$

& B  S
---
| B |  $4,1$ |  $0,0$
| S |  $0,0$ |  $2,2$

(a) Payoff matrices for Pure Coordination (left), BoS (middle), Asymmetric BoS
(right).

To develop a better intuition for the sense in which equilibria can be more or
less reasonable, consider a BoS with an extreme asymmetry, with equilibrium
payoffs (15, 10) and (1, 11). Even though each of these equilibria is Pareto-
optimal, the latter seems unreasonable or uncooperative: it yields a lower
total payoff, more inequality, and lowers the reward of the worst-off player
in the equilibrium. To formalize this intuition, we characterize the
reasonableness of a Pareto-optimal payoff profile in terms of the extent to
which it optimizes welfare functions: we can say that (1, 11) is unreasonable
because there is no (impartial, see below) welfare function that would prefer
it. Different welfare functions with different properties have been introduced
in the literature (see Appendix A for an overview), but two uncontroversial
properties of a welfare function are _Pareto-optimality_ (i.e., its optimizer
should be Pareto-optimal) and _impartiality_ 111The requirement of
impartiality is also called symmetry in the welfare economics literature, or
anonymity in the social choice literature (Campbell and Fishburn, 1980).
(i.e., the welfare of a policy profile should be invariant to permutations of
player indices). From the latter property we can observe that the intuitively
reasonable choice of playing the correlated equilibrium with a fair
correlation device in the case of symmetric games is also the choice which all
impartial welfare functions recommend, provided that it is possible for the
agents to play a correlated equilibrium.

By contrast, in the asymmetric BoS from Figure 3.3 we see that playing BB
maximizes utilitarian welfare $w^{\mathrm{Util}}(\pi)=V_{1}(\pi)+V_{2}(\pi)$,
whereas playing SS maximizes the egalitarian welfare
$w^{\mathrm{Egal}}(\pi)=\min\\{V_{1}(\pi),V_{2}(\pi)\\}$ subject to $\pi$
Pareto-optimal. Throwing a correlated fair coin to choose between the two
would lead to an expected payoff that is optimal with respect to the Nash
welfare $w^{\mathrm{Nash}}(\pi)=V_{1}(\pi)\cdot V_{2}(\pi)$. Each of these
different equilibria has a normative principle to motivate it.

In the best case, all principals agree on the same welfare function as a
common ground for coordination in asymmetric BPs. However, the principals may
have reasonable differences with respect to which welfare function they
perceive as fair, and so they may train their systems to optimize different
welfare functions, leading to coordination failure when the systems interact
after deployment. In cases where agents were independently-trained according
to inconsistent welfare functions, we will say that there is normative
disagreement. There may be different degrees of normative disagreement. For
instance, the difference
$|\max_{\pi}w^{\mathrm{Util}}(\pi)-\max_{\pi}w^{\mathrm{Egal}}(\pi)|$ differs
across games.

To summarize, we relate the difficulty of coordination problems to the concept
of welfare functions: In pure coordination problems, they are not needed. In
symmmetric bargaining problems, they all point to the same equilibria. And in
asymmetric bargaining problems, they can serve to filter out intuitively
unreasonable equilbria, but leave the possibility of normative disagreement
between reasonable ones. This makes normative disagreement a critical
challenge for bargaining. In the remainder of the paper, we will focus on
asymmetric bargaining problems for this reason.

###  3.4 Norm-adaptive policies

When there is potential for normative disagreement, it can be helpful for
agents to have some flexibility as to the norms they play according to.

A number of definitions of norms have been proposed in the social scientific
literature (e.g., Gibbs (1965)), but they tend to agree that a norm is a rule
specifying acceptable and unacceptable behaviors in a group of people, along
with sanctions for violations of that rule. Game-theoretic work sometimes
identifies norms with equilibrium selection devices (e.g., Binmore and
Samuelson 1994; Young 1996). Given that complex games generally exhibit many
equilibria, some rule (such as maximizing a particular welfare function) is
needed to select among them.

Normative disagreement arises (among other reasons) from the
underdetermination of good behavior in complex multi-agent settings. This is
exemplified by the problem of conflicting equilibrium selection criteria in
asymmetric bargaining problems, but there are other possible cases of
undeterdetermination. One example is undetermination of the beliefs that a
reasonable agent should act according to in games of incomplete information
(cf. the common prior assumption in Bayesian games (Morris, 1995)). Thus our
definition of norm will be more general than an equilibrium selection device,
though in the remainder of the paper we will focus on the use of welfare
functions to choose among equilibria.

######  Definition 3.1 (Norms).

Given a 2-player POSG, a norm $N$ is a tuple
$N=(\Pi_{1}^{N},\Pi_{2}^{N},p_{1},p_{2},\Pi_{1}^{p},\Pi_{2}^{p})$, where
$\Pi_{i}^{N}$ are normative policies (i.e., those which comply with the norm);
$\Pi_{i}^{p}$ are “punishment” policies, which are enacted when deviations
from a normative policy are detected; and $p_{i}$ are rules for judging
whether a deviation has happened and how to respond, i.e.,
$p_{i}:\mathcal{H}_{i}\rightarrow\\{\texttt{True},\texttt{False}\\}$. A policy
$\pi_{i}$ is compatible with norm $N$ if, for all $H_{i}\in\mathcal{H}_{i}$,

$\pi_{i}(h)=\begin{cases}\pi_{i}^{N}(h),\pi^{N}_{i}\in\Pi_{i}^{N},\text{ if
}p_{i}(h)=\texttt{False};\\\ \pi_{i}^{p}(h),\pi^{p}_{i}\in\Pi_{i}^{p},\text{
if }p_{i}(h)=\texttt{True}.\end{cases}$

For example, in the iterated Asymmetric BoS, one norm is for both players to
always play $B$ (this is the normative policy), and for a player to respond to
deviations by continuing to play $B$. A similar norm is given by both players
always playing $S$ instead. More generally, following the folk theorems
(Mailath et al., 2006), an equilibrium in a repeated game corresponds to a
norm, in which a profile of normative policies corresponds to play on the
equilibrium path; the functions $p_{i}$ indicate whether there is deviation
from equilibrium play; and punishment policies $\pi_{i}^{p}$ are chosen such
that players are made worse off by deviating than by continuing to play
according to the normative policy profile.

Now we formally define norm-adaptive policies.

######  Definition 3.2 (Norm-adaptive policies.).

Take a 2-player POSG and a non-singleton set of norms $\mathcal{N}$ for that
game. Let $N_{i}:\mathcal{H}_{i}\rightarrow\mathcal{N}$ be a surjective
function that maps histories of observations to norms (i.e., for each norm in
$\mathcal{N}$, there are histories for which $N_{i}$ chooses that norm.) Then,
a policy $\pi_{i}^{\prime}$ is norm-adaptive if, for all $h$, there is a
policy $\pi_{i}$ such that $\pi_{i}$ is compatible with $N_{i}(h)$ and
$\pi^{\prime}_{i}(h)=\pi_{i}(h)$.

That is, norm-adaptive policies are able to play according to different norms
depending on the circumstances. As we will see below, the benefit of making
agents explicitly norm-adaptive is that this can help to prevent or resolve
normative disagreement. Lastly, note that we can define higher-order norms and
higher-order norm-adaptiveness: a higher-order norm is a norm $N$ such that
policies $\Pi_{i}^{N}$ are themselves norm-adaptive with respect to some set
of norms. This framework allows us for discussing differing (higher-order)
norms for resolving normative disagreement.

##  4 Multi-agent learning and cooperation failures in BPs

In this section, we illustrate how cooperation-inducing, but norm-unadaptive,
multi-agent learning algorithms fail to cooperate in asymmetric BPs. In
Section 5 we will then show how norm-adaptiveness improves cooperation. The
environments and algorithms considered are summarized in Table 1.

###  4.1 Setup: Learning algorithms and environments

In order to both include algorithms which use an explicitly specified welfare
function and ones which do not, we use the Learning with Opponent-Learning
Awareness (LOLA) algorithm (Foerster et al., 2018) in its policy gradient and
exact value function optimization versions as an example for the latter, and
Generalized Approximate Markov Tit-for-tat ($\texttt{amTFT}(w)$) for the
former.

We introduce $\texttt{amTFT}(w)$ as a variant of Lerer and Peysakhovich
(2017)’s Approximate Markov Tit-for-tat. The original algorithm trains a
cooperative policy profile on the utilitarian welfare, as well as a punishment
policy, and switches from the cooperative policy to the punishment policy when
it detects that the other player is defecting from the cooperative policy. The
algorithm has the appeal that it “cooperates with itself, is robust against
defectors, and incentivizes cooperation from its partner” (Lerer and
Peysakhovich, 2017). We consider the more general class of algorithms that we
call $\texttt{amTFT}(w)$ in which a cooperative policy is constructed by
optimizing an arbitrary welfare function $w$. Note that although
$\texttt{amTFT}(w)$ takes a welfare function as an argument, the resulting
policies are not norm-adaptive.

To cover a range of environments representing both symmetric and asymmetric
games, we use some existing multi-agent reinforcement learning environments
(IPD, Coin Game [CG; Lerer and Peysakhovich 2017]) and introduce two new ones
(IAsymBoS, ABCG).

Iterated asymmetric Bach or Stravinsky (IAsymBoS) is an asymmetric version of
the iterated Bach or Stravinsky matrix game. At each time step, the game
defined on the right in Figure 3.3 is played. We focus on the asymmetric
variant due to the argument in Section 3.3 that players could resolve the
symmetric version by playing a symmetric equilibrium; however, applying LOLA
without modification would also lead to coordination failure in the symmetric
variant. It should also be noted that IAsymBoS is not an SSD because it does
not incentivize defection: agents cannot gain from miscoordinating. Thus we
consider IAsymBos to be a minimal example for an environment that can produce
bargaining failures out of normative disagreement.

For a more involved example we also introduce an asymmetric version of the
stochastic gridworld Coin Game (Lerer and Peysakhovich, 2017) – asymmetric
bargaining Coin Game (ABCG) – which is both an SSD and an asymmetric BP. In
ABCG, a red and a blue agent navigate a grid with coins. Two coins
simultaneously appear on this grid: a Cooperation coin and a Disagreement
coin, each colored red or blue. Cooperation coins can only be consumed by both
players moving onto them at the same time, whereas the Disagreement coin can
only be consumed by the player of the same color as the coin. The game is
designed such that $w^{\mathrm{Util}}$ is maximized by both players always
consuming the Cooperation coin, however, this will make one player benefit
more than the other. Due to the sequential nature of the game, this means that
welfare functions which also care about (in)equity will favor an equilibrium
in which the player who benefits less from the Cooperation coin is allowed to
consume the Disagreement coin from time to time without retaliation.

Players move simultaneously in all games. Note that we assume each player to
have full knowledge of the other player’s rewards as this is required by LOLA-
exact during training and by $\texttt{amTFT}(w)$ both at training and
deployment. We use simple tabular and neural network policy parameterizations,
which are described in Appendix C along with learning algorithms.

Table 1: Summary of the environments and learning algorithms that we use to study sequential social dilemmas (SSDs) and asymmetric bargaining problems in this section.  Environment | Asymmetric BP | SSD | Learning algorithms
---|---|---|---
Iterated Prisoner’s Dilemma (IPD) | ✗ | ✓ |  LOLA-Exact, $\texttt{amTFT}(w)$
Iterated Asymmetric BoS (IAsymBoS) | ✓ | ✗ |  LOLA-Exact, $\texttt{amTFT}(w)$
Coin Game (CG) | ✗ | ✓ |  LOLA-PG, $\texttt{amTFT}(w)$
Asymmetric bargaining Coin Game (ABCG) | ✓ | ✓ |  LOLA-PG, $\texttt{amTFT}(w)$

###  4.2 Evaluating cooperative success

Figure 3: Comparison of cooperative success, measured by NormalizedScore,
between SSDs (left) and asymmetric BPs (right). Small black bars are standard
errors. For LOLA in asymmetric BPs, payoff profiles are collected into sets
corresponding to the welfare functions they implicitly optimize, in order to
obtain cross-play between identical and between different welfare functions.
Figure 4: Values of policy profiles trained in IPD and in IAsymBoS with LOLA
in self-play and cross-play. In the IPD, all policy profiles cooperate in
cross-play. But in IAsymBoS, LOLA converges to different Pareto-optimal
outcomes in self-play, leading to failures in cross-play. The purple areas
describe sets of attainable payoffs. Jitter is added for improved visibility.

We train policies in environments listed in Table 1 with the corresponding
MARL algorithms. After the training, we evaluate cooperative success in self-
play and cross-play. Self-play refers to average performance between jointly-
trained policies. Cross-play refers to average performance between
independently-trained policies. We distinguish between two kinds of cross-
play: that between agents trained using the same notion of collective
optimality (such as a welfare function or an inequity aversion term in the
value function), and between agents trained using different ones. For
$\texttt{amTFT}(w)$ we use two welfare functions, $w^{\mathrm{Util}}$ and an
inequity-averse welfare-function $w^{\mathrm{IA}}$ (see Appendix C).

Comparing cooperative success across environments is not straightforward:
environments have different sets of feasible payoffs, and we should not
evaluate cooperative success with a single welfare function, because our
concerns about normative disagreement stem from the fact that it is not
obvious what single welfare function to use. Thus we compute cooperative
success as follows. First, we take $\mathcal{W}$ to be the set of welfare
functions which we use in our experiments in the environment in question. For
instance, for IAsymBoS and $\texttt{amTFT}(w)$ this is
$\mathcal{W}=\\{w^{\mathrm{Util}},w^{\mathrm{IA}}\\}$. Second, we define
disagreement payoff profiles $\pi^{d}$ corresponding to cooperation failure;
in IAsymBoS the disagreement policy profile would be the one which has payoff
profile $(0,0)$. Then, for a policy profile $\pi$, we compute its normalized
score as
$\mathrm{NormalizedScore}(\pi)\triangleq\max_{w\in\mathcal{W}}\frac{w(\pi)-w(\pi^{d})}{\max_{\pi^{\prime}}w(\pi^{\prime})-w(\pi^{d})}$.
Under this scoring method, players do maximally well when they play a policy
profile which is optimal according to some welfare function in $\mathcal{W}$.

Figure 3 illustrates the difference between cooperation in SSDs and bargaining
problems. When there is a single "cooperative" equilibrium, as in the case of
IPD and CG, cooperation-inducing learning algorithms typically achieve
cooperation in cross-play. In contrast, in IAsymBoS and ABCG we observe mild
performance degradation in cross-play where agents optimize the same welfare
functions, and strong degradation when agents optimize different welfare
functions.

##  5 Benefits and limitations of norm-adaptiveness

The cooperation-inducing properties of the algorithms in Section 4 are simple
and are not designed to help agents resolve potential normative disagreement
to avoid Pareto-dominated outcomes. The two main problems are (1) that the
algorithms are ill-equipped for reacting to normative disagreement, and (2)
that they may confuse normative disagreement with defection.

The former problem is already evident in IAsymBoS. There, playing according to
incompatible welfare functions is not interpreted as defection by amTFT. This
is not necessarily bad – we claim that normative disagreement should be
treated differently to defection – but it does mean that amTFT lacks the
policy space to react to normative disagreement. For the latter problem, we
observe that in the ABCG the $\texttt{amTFT}(w)$-agent does classify some of
the opponent’s actions as defection, even though they are aimed to optimize an
impartial welfare function, and punishes accordingly.

###  5.1 $\texttt{amTFT}(\mathcal{W})$

Figure 5: Average cross-play payoff profiles with standard errors for profiles
of policies
$\left(\texttt{amTFT}(\mathcal{W}_{1}),\texttt{amTFT}(\mathcal{W}_{2})\right)$.
The legend shows various combinations of sets $\mathcal{W}_{1}$ and
$\mathcal{W}_{2}$. Coordination failure only occurs when
$\mathcal{W}_{1}\cap\mathcal{W}_{2}=\emptyset$.

To overcome both of these problems, we propose a norm-adaptive modification to
$\texttt{amTFT}(w)$. As we only aim to illustrate the benefit of norm-adaptive
policies, we keep the implementation simple: Instead of a welfare function $w$
the algorithm now takes a welfare-function set $\mathcal{W}$:
$\texttt{amTFT}(\mathcal{W})$. The agent starts out playing according to some
$w\in\mathcal{W}$. The initial choice can be made at random or according to a
preference ordering between the $w\in\mathcal{W}$.

$\texttt{amTFT}(\mathcal{W})$ then follows a two-stage decision process.
First, if the agent detects that their opponent is merely playing according to
a different welfare function than itself, $w$ gets re-sampled. Second, if the
agent detects defection by the opponent, it will punish, just as in the
original algorithm. However, by first checking for normative disagreement, we
make sure that punishment does not happen as a result of a normative
disagreement.

In Figure 5 we illustrate how, assuming uniform re-sampling from
$\mathcal{W}$, $\texttt{amTFT}(\mathcal{W})$ can overcome normative
disagreement and perform close to the Pareto frontier. Agents need not sample
uniformly, though. For instance when the number of possible welfare functions
is large, it would be beneficial to put higher probability on welfare
functions which one’s counterpart is more likely to be optimizing. Furthermore
an agent might want to put higher probability on welfare functions that it
prefers.

Notice that, when $w\in\mathcal{W}$, one player using
$\texttt{amTFT}(\mathcal{W})$ rather than $\texttt{amTFT}(w)$ leads to a
(weak) Pareto improvement. Beyond that, in anticipation of bargaining failure
due to not having a way to resolve normative disagreement, players are
incentivized to include more than just their preferred welfare function into
$\mathcal{W}$. In both IAsymBoS (see Figure 5) and ABCG (see Table 5, Appendix
D) we can observe significant improvement for cross-play when at least one
player is norm-adaptive.

###  5.2 The exploitability-robustness tradeoff

As our experiments with $\texttt{amTFT}(\mathcal{W})$ show, agents who are
more flexible are less prone to bargaining failure due to normative
disagreement. However, they are prone to having that flexibility exploited by
their counterparts. For instance, an agent which is open to optimizing either
$w^{\mathrm{Util}}$ or $w^{\mathrm{IA}}$ will end up optimizing
$w^{\mathrm{IA}}$ if playing against an agent for whom
$\mathcal{W}=\\{w^{\mathrm{IA}}\\}$. More generally, an agent who puts higher
probability on a welfare function it has a preference for, when re-sampling
$w$, will be less robust against counterparts who disprefer that welfare
function and put a lower probability on it. An agent who tries to guess the
counterpart’s welfare function and tries to accommodate to this is exploitable
to agents who do not.

##  6 Discussion

We formally introduce a class of hard cooperation problems – asymmetric
bargaining problems – and situate them within a wider game taxonomy. We argue
that they are hard because there can arise normative disagreement between
multiple "reasonable" cooperative equilibria, characterized by divergence in
the preferred outcomes according to different welfare functions. This presents
a problem for those deploying AI systems without coordinating on the norms
those systems follow. We have introduced the notion of norm-adaptive policies,
which are policies that allow agents to change the norms according to which
they play, giving rise to opportunities for resolving normative disagreement.
As an example of a class of norm-adaptive policies, we introduced
$\texttt{amTFT}(\mathcal{W})$, and showed in experiments that this tends to
improve robustness to normative disagreement. On the other hand, we have
demonstrated a robustness-exploitability tradeoff, under which methods that
learn more normatively flexible strategies are also more vulnerable to
exploitation.

There are a number of limitations to this work. We have throughout assumed
that the agents have a common and correctly-specified model of their
environment, including their counterpart’s reward function. In real-world
situations, however, principals may not have identical simulators with which
to train their systems, and there are well-known obstacles to the honest
disclosure of preferences (Hurwicz, 1972), meaning that common knowledge of
rewards may be unrealistic. Similarly, we assumed a certain degree of
reasonableness on part of the principals, see by the willingness to play the
symmetric correlated equilibrium in symmetric BoS (Section 3), for instance.
However, we believe this to be a minimal assumption as the deployers of such
agents are aware of the risk of coordination failure as a result of insisting
on equilibria that no impartial welfare function would recommend.

Future work should consider more sophisticated and learning-driven approaches
to designing norm-adaptive policies, as $\texttt{amTFT}(\mathcal{W})$ relies
on a finite set of user-specified welfare functions and a hard-coded procedure
for switching between policies. One possibility is to train agents who are
themselves capable of jointly deliberating about the principles they should
use to select an equilibrium, e.g., deciding among the axioms which
characterize different bargaining solutions (see Appendix A) in the hopes that
they will be able to resolve initial disagreements. Another direction is
resolving disagreements that cannot be expressed as disagreements over the
welfare functions according to which agents play; for instance, disagreements
over the beliefs or world-models which should inform agents’ behavior.

## Acknowledgments and Disclosure of Funding

We’d like to thank Yoram Bachrach, Lewis Hammond, Vojta Kovařík, Alex Cloud,
as well as our anonymous reviewers for their valuable feedback; Daniel
Rüthemann for designing Figures 6 and 7; Chi Nguyen for crucial support just
before a deadline; Toby Ord and Jakob Foerster for helpful comments.

Julian Stastny performed part of the research for this paper while interning
at the Center on Long-Term Risk. Johannes Treutlein was supported by the
Center on Long-Term Risk, the Berkeley Existential Risk Initiative, and Open
Philantropy. Allan Dafoe received funding from Open Philantropy and the Centre
for the Governance of AI.

## References

  * Albin [2001] Cecilia Albin.  _Justice and fairness in international negotiation_.  Number 74. Cambridge University Press, 2001.
  * Anthony et al. [2020] Thomas Anthony, Tom Eccles, Andrea Tacchetti, János Kramár, Ian Gemp, Thomas Hudson, Nicolas Porcel, Marc Lanctot, Julien Perolat, Richard Everett, Satinder Singh, Thore Graepel, and Yoram Bachrach.  Learning to play no-press diplomacy with best response policy iteration.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 17987–18003. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/d1419302db9c022ab1d48681b13d5f8b-Paper.pdf.
  * Aumann [1974] Robert J Aumann.  Subjectivity and correlation in randomized strategies.  _Journal of mathematical Economics_ , 1(1):67–96, 1974.
  * Baarslag et al. [2013] Tim Baarslag, Katsuhide Fujita, Enrico H Gerding, Koen Hindriks, Takayuki Ito, Nicholas R Jennings, Catholijn Jonker, Sarit Kraus, Raz Lin, Valentin Robu, et al.  Evaluating practical negotiating agents: Results and analysis of the 2011 international competition.  _Artificial Intelligence_ , 198:73–103, 2013.
  * Bendor and Swistak [2001] Jonathan Bendor and Piotr Swistak.  The evolution of norms.  _American Journal of Sociology_ , 106(6):1493–1545, 2001.
  * Binmore and Samuelson [1994] Ken Binmore and Larry Samuelson.  An economist’s perspective on the evolution of norms.  _Journal of Institutional and Theoretical Economics (JITE)/Zeitschrift für die gesamte Staatswissenschaft_ , pages 45–63, 1994\.
  * Boutilier [1999] Craig Boutilier.  Sequential optimality and coordination in multiagent systems.  In _IJCAI_ , volume 99, pages 478–485, 1999.
  * Boyd and Richerson [2009] Robert Boyd and Peter J Richerson.  Culture and the evolution of human cooperation.  _Philosophical Transactions of the Royal Society B: Biological Sciences_ , 364(1533):3281–3288, 2009.
  * Campbell and Fishburn [1980] Donald E Campbell and Peter C Fishburn.  Anonymity conditions in social choice theory.  _Theory and Decision_ , 12(1):21, 1980.
  * Cao et al. [2018] Kris Cao, Angeliki Lazaridou, Marc Lanctot, Joel Z Leibo, Karl Tuyls, and Stephen Clark.  Emergent communication through negotiation.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=Hk6WhagRW.
  * Chakraborty et al. [2020] Shantanu Chakraborty, Tim Baarslag, and Michael Kaisers.  Automated peer-to-peer negotiation for energy contract settlements in residential cooperatives.  _Applied Energy_ , 259:114173, 2020.
  * Crandall and Goodrich [2011] Jacob W Crandall and Michael A Goodrich.  Learning to compete, coordinate, and cooperate in repeated games using reinforcement learning.  _Machine Learning_ , 82(3):281–314, 2011.
  * Dafoe et al. [2020] Allan Dafoe, Edward Hughes, Yoram Bachrach, Tantum Collins, Kevin R McKee, Joel Z Leibo, Kate Larson, and Thore Graepel.  Open problems in cooperative ai.  _arXiv preprint arXiv:2012.08630_ , 2020.
  * Eccles et al. [2019] Tom Eccles, Edward Hughes, János Kramár, Steven Wheelwright, and Joel Z Leibo.  Learning reciprocity in complex sequential social dilemmas.  _arXiv preprint arXiv:1903.08082_ , 2019.
  * Foerster et al. [2018] Jakob Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch.  Learning with opponent-learning awareness.  In _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems_ , pages 122–130. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
  * Geist and Lohn [2018] Edward Geist and Andrew J Lohn.  _How might artificial intelligence affect the risk of nuclear war?_ Rand Corporation, 2018.
  * Gibbs [1965] Jack P Gibbs.  Norms: The problem of definition and classification.  _American Journal of Sociology_ , 70(5):586–594, 1965.
  * Gray et al. [2021] Jonathan Gray, Adam Lerer, Anton Bakhtin, and Noam Brown.  Human-level performance in no-press diplomacy via equilibrium search.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=0-uUGPbIjD.
  * Hadfield-Menell et al. [2019] Dylan Hadfield-Menell, McKane Andrus, and Gillian Hadfield.  Legible normativity for ai alignment: The value of silly rules.  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 115–121, 2019.
  * Harsanyi [1955] John C Harsanyi.  Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility.  _Journal of political economy_ , 63(4):309–321, 1955.
  * Henrich et al. [2001] Joseph Henrich, Robert Boyd, Samuel Bowles, Colin Camerer, Ernst Fehr, Herbert Gintis, and Richard McElreath.  In search of homo economicus: behavioral experiments in 15 small-scale societies.  _American Economic Review_ , 91(2):73–78, 2001\.
  * Hurwicz [1972] Leonid Hurwicz.  On informationally decentralized systems.  _Decision and organization: A volume in Honor of J. Marschak_ , 1972\.
  * Kalai [1977] Ehud Kalai.  Proportional solutions to bargaining situations: interpersonal utility comparisons.  _Econometrica: Journal of the Econometric Society_ , pages 1623–1630, 1977.
  * Kalai and Smorodinsky [1975] Ehud Kalai and Smorodinsky.  Other solutions to nash’s bargaining problem.  _Econometrica_ , 43(3):513–518, 1975.
  * Köster et al. [2020] Raphael Köster, Kevin R McKee, Richard Everett, Laura Weidinger, William S Isaac, Edward Hughes, Edgar A Duéñez-Guzmán, Thore Graepel, Matthew Botvinick, and Joel Z Leibo.  Model-free conventions in multi-agent reinforcement learning with heterogeneous preferences.  _arXiv preprint arXiv:2010.09054_ , 2020.
  * Kraus and Arkin [2001] Sarit Kraus and Ronald C Arkin.  _Strategic negotiation in multiagent environments_.  MIT press, 2001.
  * Leibo et al. [2017] Joel Z Leibo, Vinicius Zambaldi, Marc Lanctot, Janusz Marecki, and Thore Graepel.  Multi-agent reinforcement learning in sequential social dilemmas.  In _Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems_ , pages 464–473. International Foundation for Autonomous Agents and Multiagent Systems, 2017.
  * Lerer and Peysakhovich [2017] Adam Lerer and Alexander Peysakhovich.  Maintaining cooperation in complex social dilemmas using deep reinforcement learning.  _arXiv preprint arXiv:1707.01068_ , 2017.
  * Lerer and Peysakhovich [2019] Adam Lerer and Alexander Peysakhovich.  Learning existing social conventions via observationally augmented self-play.  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 107–114, 2019.
  * Liang et al. [2018] Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael Jordan, and Ion Stoica.  RLlib: Abstractions for distributed reinforcement learning.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 3053–3062. PMLR, 10–15 Jul 2018.  URL http://proceedings.mlr.press/v80/liang18b.html.
  * Mailath et al. [2006] George J Mailath, J George, Larry Samuelson, et al.  _Repeated games and reputations: long-run relationships_.  Oxford university press, 2006.
  * Morris [1995] Stephen Morris.  The common prior assumption in economic theory.  _Economics & Philosophy_, 11(2):227–253, 1995\.
  * Muthoo [2001] Abhinay Muthoo.  _The economics of bargaining_.  EOLSS, 2001.
  * Nash [1950] John F Nash.  The bargaining problem.  _Econometrica: Journal of the Econometric Society_ , pages 155–162, 1950.
  * Nash [1990] John Forbes Nash.  Non-cooperative games.  _Annals of Mathematics_ , 5(4):2, 1990.
  * Paquette et al. [2019] Philip Paquette, Yuchen Lu, SETON STEVEN BOCCO, Max Smith, Satya O.-G., Jonathan K. Kummerfeld, Joelle Pineau, Satinder Singh, and Aaron C Courville.  No-press diplomacy: Modeling multi-agent gameplay.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/84b20b1f5a0d103f5710bb67a043cd78-Paper.pdf.
  * Peysakhovich and Lerer [2017] Alexander Peysakhovich and Adam Lerer.  Consequentialist conditional cooperation in social dilemmas with imperfect information.  _arXiv preprint arXiv:1710.06975_ , 2017.
  * Ringius et al. [2002] Lasse Ringius, Asbjørn Torvanger, and Arild Underdal.  Burden sharing and fairness principles in international climate policy.  _International Environmental Agreements_ , 2(1):1–22, 2002.
  * Rosenschein and Genesereth [1988] Jeffrey S Rosenschein and Michael R Genesereth.  Deals among rational agents.  In _Readings in Distributed Artificial Intelligence_ , pages 227–234. Elsevier, 1988.
  * Schelling [1956] Thomas C Schelling.  An essay on bargaining.  _The American Economic Review_ , 46(3):281–306, 1956.
  * Schelling [1958] Thomas C Schelling.  The strategy of conflict. prospectus for a reorientation of game theory.  _Journal of Conflict Resolution_ , 2(3):203–264, 1958.
  * Sen and Airiau [2007] Sandip Sen and Stephane Airiau.  Emergence of norms through social learning.  In _IJCAI_ , volume 1507, page 1512, 2007.
  * Shoham and Tennenholtz [1997] Yoav Shoham and Moshe Tennenholtz.  On the emergence of social conventions: modeling, analysis, and simulations.  _Artificial Intelligence_ , 94(1-2):139–166, 1997\.
  * Thomson [1994] William Thomson.  Cooperative models of bargaining.  _Handbook of game theory with economic applications_ , 2:1237–1284, 1994.
  * Walker and Wooldridge [1995] Adam Walker and Michael J Wooldridge.  Understanding the emergence of conventions in multi-agent systems.  In _ICMAS_ , volume 95, pages 384–389, 1995.
  * Young [1996] H Peyton Young.  The economics of convention.  _Journal of economic perspectives_ , 10(2):105–122, 1996.
  * Zhang and Hofbauer [2015] Boyu Zhang and Josef Hofbauer.  Equilibrium selection via replicator dynamics in $2\times 2$ coordination games.  _International Journal of Game Theory_ , 44(2):433–448, 2015.
  * Zhou [1997] Lin Zhou.  The nash bargaining theory with non-convex problems.  _Econometrica: Journal of the Econometric Society_ , pages 681–685, 1997.

##  Appendix A Welfare functions

Different welfare functions have been introduced in the literature. Table 2
gives an overview over commonly discussed welfare functions. Their properties
are noted in Table 3.

Table 2:  Welfare functions, adapted to the multi-agent RL setting where two agents with value functions $V_{1},V_{2}$ are bargaining over the policy profile $\pi$ to deploy. $d_{i}$, the disagreement value, is the value which player i gets when bargaining fails.  Name of welfare function $w$ |  Form of $w(\pi)$
---|---
Nash [Nash, 1950] | $\left[V_{1}(\pi)-d_{1}\right]\cdot\left[V_{2}(\pi)-d_{2}\right]$
Kalai-Smorodinsky [Kalai and Smorodinsky, 1975] |  $\Big{\lvert}\frac{V_{1}(\pi)-d_{1}}{V_{2}(\pi)-d_{2}}-\frac{\sup_{\pi}V_{1}(\pi)-d_{1}}{\sup_{\pi}V_{2}(\pi)-d_{2}}\Big{\rvert}$ s.t. Pareto-optimal
Egalitarian [Kalai, 1977] |  $\min\left\\{V_{1}(\pi)-d_{1},V_{2}(\pi)-d_{2}\right\\}$ s.t. Pareto-optimal
Utilitarian [Harsanyi, 1955] | $V_{1}(\pi)+V_{2}(\pi)$

Pareto-optimality refers to the property that the welfare function’s optimizer
should be Pareto-optimal. Impartiality, often called symmetry, implies that
the welfare of a policy profile should be invariant to permutations of player
indices. These are treated as relatively uncontroversial properties in the
literature. Invariance to affine transformations of the payoff matrix is
usually motivated by the assumption that interpersonal comparison of utility
is impossible. In contrast, the utilitarian welfare function assumes that such
comparisons are possible. Independence of irrelevant alternatives refers to
the principle that a preference for an equilibrium A over equilibrium B should
only depend on properties of A and B. That is, a third equilibrium C should
not change the preference ordering between A and B. Rescource monotonicity
refers to the principle that if the payoff for any policy profile increases,
this should not make any agent worse off.

Table 3: Properties of welfare functions. For properties of Nash welfare here the set of feasible payoffs is assumed to be convex (Zhou [1997] describes properties in the non-convex case). | Nash | Kalai-Smorodinsky | Egalitarian | Utilitarian
---|---|---|---|---
Pareto optimality | ✓ | ✓ | ✓ | ✓
Impartiality | ✓ | ✓ | ✓ | ✓
Invariance to affine transformations | ✓ | ✓ | ✗ | ✗
Independence of irrelevant alternatives | ✓ | ✗ | ✓ | ✓
Resource monotonicity | ✗ | ✓ | ✓ | ✗

##  Appendix B Environments

###  B.1 Additional descriptions of environments

#### Coin Game

Figure 6: A pictorial description of agents’ rewards in the Coin Game
environment [Lerer and Peysakhovich, 2017]. A Red player and a Blue player
navigate a grid and pick up randomly-generated coins. Each player gets a
reward of $1$ for picking up a coin of any color. But, a player gets a reward
of $-2$ if the other player picks up their coin. This creates a social dilemma
in which the socially optimal behavior is to only get one’s own coin, but
there is incentive to defect and try to get the other player’s coin as well.

#### Asymmetric bargaining Coin Game

Figure 7: Illustration of the Asymmetric bargaining Coin Game described in
Section 4. CC stands for Cooperative Coin and DC stands for Disagreement Coin.

###  B.2 Disagreement profiles for each environment

For computing the normalized scores in Figure 3, we use the following
disagreement profiles, corresponding to cooperation failure. In IPD, the
cooperation failures are only the joint defections (D,D) producing a reward
profile of (-3, -3). In IAsymBoS, they are the profiles (B, S) and (S, B),
both associated with the reward profile (0, 0). In Coin Game, the cooperation
failures are when both players pick all coins at maximum speed selfishly and
this produce a reward profile of (0, 0). In Asymmetric bargaining Coin Game
(ABCG), when the players fails to cooperates, they can punish the opponent by
preventing any coin to be picked by waiting instead of picking their own
defection coin (e.g. with amTFT). In these cooperation failures, the reward
profile with perfect punishment is (0, 0).

##  Appendix C Experimental details

###  C.1 Learning algorithms

We use the discount factor $\gamma=0.96$ for all the algorithms and
environments unless specified otherwise in Table 4.

#### Approximate Markov tit-for-tat (amTFT)

We follow the amTFT algorithm from [Lerer and Peysakhovich, 2017] with two
changes: 1) Instead of using a selfish policy to punish the opponent, we use a
policy that minimizes the reward of the opponent. 2) We use the amTFT version
that uses rollouts to compute the debit and the punishment length. We observed
that using long rollouts to compute the debit increases significantly the
variance on the debit and this leads to false positive detection of defection.
To reduce this variance, we thus compute the debit without rollouts. We use
the direct difference between the rewards given by the actual action and given
by the simulated cooperative action. The rollout length used to compute the
punishment length is 20.

We note that in asymmetric BoS, training runs using the utilitarian welfare
function sometimes learn to produce, in self-play, the egalitarian outcome
instead of the utilitarian outcome. In these cases the policy gets discarded.

The inequity-averse welfare $w^{\mathrm{IA}}$ is defined as follows:

$\displaystyle
w^{\mathrm{IA}}(\pi)=V_{1}(\pi)+V_{2}(\pi)-\beta\cdot\mathbb{E}\left[\lvert
e^{t}_{1}(h^{t}_{1},h^{t}_{2})-e^{t}_{2}(h^{t}_{1},h^{t}_{2})\rvert\right]$

where $e_{i}^{t}(h^{t}_{1},h^{t}_{2})=\gamma\lambda
e^{t-1}_{i}(h^{t-1}_{1},h^{t-1}_{2})+r_{i}(S^{t},A_{1}^{t},A_{2}^{t})$ are
smoothed cumulative rewards with a discount factor $\gamma$ and a parameter
$\beta$ which controls how much unequal outcomes are penalized.

#### Learning with Opponent-Learning Awareness (LOLA)

Write $V_{i}(\theta_{1},\theta_{2})$ as the value to player $i$ under a
profile of policies with parameters $\theta_{1},\theta_{2}$. Then, the LOLA
update [Foerster et al., 2018] for player 1 at time $t$ with parameters
$\delta,\eta>0$ is

$\theta^{t}_{1}=\theta^{t-1}_{1}+\delta\nabla_{\theta_{1}}V_{i}(\theta_{1},\theta_{2})+\delta\eta\left[\nabla_{\theta_{2}}V_{1}(\theta_{1},\theta_{2})\right]^{{}^{\sf
T}}\nabla_{\theta_{1}}\nabla_{\theta_{2}}V_{2}(\theta_{1},\theta_{2}).$

###  C.2 Policies

We used RLlib [Liang et al., 2018] for almost all the experiments. It is under
Apache License 2.0. All activation functions are ReLU if not specified
otherwise.

#### Matrix games (IPD and IBoS) with LOLA-Exact

We used the official implementation of LOLA-Exact from
https://github.com/alshedivat/lola. We slightly modified it to increase the
stability and remove a few confusing behaviors. Following Foerster et al.
[2018]’s parameterization of policies in the iterated Prisoner’s Dilemma, we
use policies which condition on the previous pair of actions played, with the
difference that instead of using one parameter for every possible previous
action profile, we use $N$ parameters for every one of the previous action
profile to always to play in larger action space ($N$ actions possible).

#### Matrix games (IPD and IBoS) with amTFT

We use a Double Dueling DQN architecture + LSTM for both simple and complex
environments when using amTFT. This architecture is non-exhaustively composed
of a shared fully connected layer (hidden layer size 64), an LSTM (cell size
16), a value branch and an action-value branch both composed of a fully
connected network (hidden layer size 64).

#### Coin games (CG and ABCG) with LOLA-PG

We used the official implementation from https://github.com/alshedivat/lola,
which is under MIT license. We slightly modified it to increase the stability
and remove a few confusing behaviors. Especially, we removed the critic
branch, which had no effect in practice. We use a PG+LSTM architecture
composed of two convolution layers (kernel size 3x3 and feature size 20), an
LSTM (cell size 64) and a final fully connected layer.

ABCG + LOLA-PG mainly generates policies that are associated with an
egalitarian welfare function. Within this set of policies, some are a bit
closer to the utilitarian outcome than others, which we used as a basis to
classify them as "utilitarian" for the purpose of comparison in Figures 3 and
8. However, because the difference is small, we do not observe a lot of
additional cross-play failure compared to cross-play between the "same"
welfare function. It should also be noted that we chose to discard the runs in
which none of the agents becomes competent at picking any of the coins.

#### Coin games (CG and ABCG) with amTFT

We use a Double Dueling DQN architecture + LSTM for both simple and complex
environments when using amTFT. The architecture used is non-exhaustively
composed of two convolution layers (kernel size 3x3 and feature size 64), an
LSTM (cell size 16), a value branch and an action-value branch both composed
of a fully connected network (hidden layer size 32).

###  C.3 Code assets

The code that we provide allows to run all of the experiments and to generate
the figures with our results. All instructions on how to install and run the
experiments are given in the ‘README.md‘ file. The code to run the experiments
from Section 4 is in the folder "base_game_experiments". The code to run the
experiments from Section 5, is in the folder ‘base_game_experiments‘. The code
to generate the figures is in the folder ‘plots‘.

An anonymized version of the code is available at
https://github.com/68545324/anonymous.

###  C.4 Hyperparameters

Table 4: Main hyperparameters for each cross-play experiment.

Env. (Algo.) | LR | Episodes | Episode length | Gamma | LSTM
---|---|---|---|---|---
Matrix games (LOLA-Exact) | 1.0 | N/A | N/A | 0.96 | N/A
Matrix games (amTFT) | 0.03 | 800 | 20 | 0.96 | ✓
CG (LOLA-PG) | 0.05 | 2048000 | 40 | 0.90 | ✓
ABCG (LOLA-PG) | 0.1 | 2048000 | 40 | 0.90 | ✓
CG and ABCG (amTFT) | 0.1 | 4000 | 100 | 0.96 | ✓

All hyperparameters can be found in the code provided as the supplementary
material. They are stored in the "params.json" files associated with each
replicate of each experiment. The experiments are stored in the "results"
folders.

The hyperparameters selected are those producing the most welfare-optimal
results when evaluating in self-play (the closest to the optimal profiles
associated with each welfare function). Both manual hyperparameter tuning and
grid searches were performed.

##  Appendix D Additional experimental results

Table 5: Cross-play normalized score of $\texttt{amTFT}(\mathcal{W})$ in ABCG. |  | $\\{w^{\mathrm{Util}}\\}$ | $\\{w^{\mathrm{IA}}\\}$ | $\\{w^{\mathrm{Util}},w^{\mathrm{IA}}\\}$
---|---|---|---|---
| $\\{w^{\mathrm{Util}}\\}$ | 0.82 | 0.12 | 0.69
$\\{w^{\mathrm{IA}}\\}$ | 0.92 | 0.95 | 0.95
$\\{w^{\mathrm{Util}},w^{\mathrm{IA}}\\}$ | 0.85 | 0.91 | 0.91

Figure 8: Mean reward of policy profiles for environments and learning
algorithms given in Table 1 The purple areas describe sets of attainable
payoffs. In matrix games, a small amount of jitter is added to the points for
improved visibility. The plots on top compare self-play with cross-play,
whereas the plots below compare cross-play between policies optimizing same
and different welfare functions.

##  Appendix E Exploitability-robustness tradeoff

In this section, we provide some theory on the tradeoff between exploitability
and robustness. Consider some asymmetric BP, with welfare functions
$w,w^{\prime}$ optimized in equilibrium, such that for any two policy profiles
$\pi^{w},\pi^{w^{\prime}}$, the cross-play policy profile
$(\pi^{w}_{1},\pi^{w^{\prime}}_{2})$ is Pareto-dominated. Note that the
definition implies that the welfare functions must be distinct.

We can derive an upper bound for how well players can do under the cross-play
policy profile. It follows from the fact that both $\pi^{w}$ and
$\pi^{w^{\prime}}$ are in equilibrium that for $i=1,2$, it is

$V_{i}(\pi^{w}_{1},\pi^{w^{\prime}}_{2})\leq\min\\{V_{i}(\pi^{w}),V_{i}(\pi^{w^{\prime}})\\}.$
(1)

This is because, otherwise, at least one of the two profiles cannot be in
equilibrium, since a player would have an incentive to switch to another
policy to increase their value.

From the above, it also follows that the cross-play policy must be strictly
dominated. To see this, assume it was not dominated. This would imply that one
player has equal values under both profiles. So that player would be
indifferent, while one of the profiles would leave the other player worse off.
Thus, that profile would be weakly Pareto dominated, which is excluded by the
definition of a welfare function.

It is a desirable quality for a policy profile maximizing a welfare function
in equilibrium to have values that are close to this upper bound in cross-play
against other policies. For instance, if some coordination mechanism exists
for agreeing on a common policy to employ, it may be feasible to realize this
bound against any opponent willing to do the same.

Moreover, the bound implies that whenever we try to be even more robust
against players employing policies corresponding to other welfare functions
(e.g., a policy which reaches Pareto optimal outcomes against a range of
different policies), our policy will cease to be in equilibrium. In that
sense, such a policy will be exploitable, while unexploitable policies can
only be robust against different opponents up to the above bound. Note that
this holds even in idealized settings, where coordination, e.g., via some
grounded messages, is possible.

Lastly, note that if no coordination is possible, or if no special care is
being taken in making policies robust, then equilibrium profiles that maximize
a welfare function can perform much worse in cross-play than the above upper
bound.

We show this formally in a special case in which our POSG is an iterated game,
i.e., it only has one state. Moreover, we assume that it is an asymmetric BP,
and that for both welfare functions $w,w^{\prime}$ in question, an optimal
policy $\pi^{w},\pi^{w^{\prime}}$ exists that is deterministic. Denote
$V_{i}(t,\pi)\triangleq V_{i}(H_{t},\pi)$ (where $H_{t}$ denotes the joint
observation history up to step $t$) as the return from time step $t$ onwards,
under the policy $\pi$. We also assume that for any player $i$, the minimax
value $\min_{a_{-i}}\max_{a_{i}}\frac{1}{1-\gamma}r_{i}(a)$ is strictly worse
than the values of their preferred welfare function maximizing profile. Then
we can show that policies maximizing the welfare functions exist such that
after some time step, their returns will be upper bounded by their minimax
return.

######  Proposition 1.

In the situation outlined above, there exist policices
$\tilde{\pi}^{w},\tilde{\pi}^{w^{\prime}}$ optimizing the respective welfare
functions and a time step $t$ such that

$V_{i}(t,\tilde{\pi}_{1}^{w},\tilde{\pi}_{2}^{w^{\prime}})\leq\min_{a_{-i}}\max_{a_{i}}\frac{1}{1-\gamma}r_{i}(a)$

for $i=1,2$.

###### Proof.

Define $\tilde{\pi}^{w}$ as the policy profile in which player $i$ follows
$\pi_{i}^{w}$, unless the other player’s actions differ from $\pi_{-i}^{w}$ at
least once, after which they switch to the action
$a_{i}\triangleq\operatorname*{arg\,min}_{a_{i}}\max_{a_{-i}}r_{-i}(a)$.
Define $\tilde{\pi}^{w^{\prime}}$ analogously. Note that both profiles are
still optimal for the corresponding welfare functions.

As argued above, the cross-play profile $(\pi_{1}^{w},\pi_{2}^{w^{\prime}})$
must be strictly worse than their preferred profile, for both players. So
there is a time $t^{\prime}$ after which an action of a player $i$ must differ
from $-i$’s prefered profile and thus $-i$ switches to the minimax action
$a_{-i}$. We have
$V_{i}(t^{\prime},\pi_{i}^{w},a_{-i})\leq\min_{a^{\prime}_{-i}}\max_{a^{\prime}_{i}}\frac{1}{1-\gamma}r_{i}(a^{\prime})$,
i.e., the value $i$ gets after step $t^{\prime}$ must be smaller than their
minimax value, and by assumption, the minimax value is worse for $i$ than the
value of their preferred welfare-maximizing profile. Hence, there must be a
time step $t-1\geq t^{\prime}$ after which $i$ also switches to their minimax
action.

From $t$ onwards, both players play $a$, so

$V_{i}(t,\tilde{\pi})=\frac{1}{1-\gamma}r_{i}(a)\leq\max_{a^{\prime}_{i}}\frac{1}{1-\gamma}r_{i}(a_{-i},a^{\prime}_{i})=\min_{a^{\prime}_{-i}}\max_{a^{\prime}_{i}}\frac{1}{1-\gamma}r(a^{\prime}).$

∎


# Dynamic Vulnerability Detection on Smart Contracts Using Machine Learning

Author 11 co-author(s)1 1Organization<EMAIL_ADDRESS>
###### Abstract

In this work we propose Dynamit, a monitoring framework to detect a reentrancy
vulnerability in an Ethereum smart contract. The novelty of our framework is
that it relies only on transaction metadata and balance data from the
blockchain system; our approach requires no domain knowledge, code
instrumentation, or special execution environment. Dynamit extracts features
from transaction data and uses a machine learning model to classify
transactions as benign or harmful. Therefore, not only we can find the
contracts that are vulnerable to reentrancy attacks, but we also get an
execution trace that reproduces the attack. All the required metadata of the
transactions is readily available in Ethereum blockchain and requires no
modification of the deployed smart contracts. Using a random forest
classifier, our model achieves 95 % accuracy on 105 transactions, showing the
potential of our technique.

##  1 Introduction

Smart contracts are collection of code and the associated data deployed on top
of a blockchain (e.g. Ethereum ethereumhome) that enable decentralised and
automated transfer of assets between accounts on the same blockchain system. A
smart contract depending on the programming language used can encode any set
of rules to handle the transfer of assets. The mentioned transfers happen
within transactions that are stored on blockchain, and are persistent.
Therefore, smart contracts can implement a wide range of use-cases including
financial and governance applications b7. For instance, a contract could act
like an autonomous agreement between multiple parties to transfer specific
amounts of assets to desired accounts when particular conditions are met.

One of the most popular blockchain platforms that supports smart contracts is
Ethereum. As of January 2021, the market capitalization of Ethereum is 138
bilion dollars b8. Smart contracts on Ethereum are a type of account that both
users and other contracts can interact with by doing read-only calls to
functions inside contracts or via state-changing transactions through their
functions. The smart contracts in Ethereum are themselves written in Solidity
which is a language influenced by JavaScript, C++, and python. To perform the
operations of a smart contract an execution fee is needed that is called Gas.
Gas fees are paid in Ethereum’s native currency, Ether (ETH) b9.

Despite the fact that management of assets in this decentralised system with
no central authority should be done with more care, smart contracts often have
a rapid development process which makes them more susceptible to bugs or
vulnerabilities that may be exploited by other accounts in Ethereum network.
In fact, there has been a number of attacks on the Ethereum main network that
caused loss of millions of ETH. The most famous attack so far on Ethereum has
been the attack on Decentralized Autonomous Organisation (DAO) which was
conducted by exploiting the reentrancy vulnerability. As a result of this
attack 3.5 million ETH was stolen (~50M USD at the time) b10.

\+ how does reentrancy work in a nutshell? (about two sentences)

\+ what is our contribution?

\+ why is our contribution useful? (no code instr., high accuracy)

\+ trace as explanation

##  2 Background

###  2.1 Ethereum

\+ block chain and VM

\+ smart contracts in bitcode(?)

\+ typically Solidity as source language

\+ VM executes contracts one insn at a time

\+ each insn has a cost (”gas”)

###  2.2 Reentrancy Vulnerability

Contracts in Ethereum can send Ether to each other. Whenever a contract
receives message without data that has Ether and does not specify a function,
a default unnamed function is executed. This function is called fallback
function. The fallback function has to be marked payable in solidity,
otherwise, the transaction of plain Ether to this contract would not be
successful, and will be reverted by Ethereum. When there is a transfer of
funds from contract A to contract B the control will be handed over to
contract B b11. In the mean time that B has the control, it can call back into
any public function in contract A again even the same function that issued the
call to B. This situation is called reentrancy. A very simplified example of
reentrancy is illustrated in Fig. 1 and Fig. 2 where the contract Attacker in
its startAttack function issues a call to the donate function of contract
Vulnerable. After this call, Vulnerable transfers plain Ether to Attacker. At
this point, the control is passed to the fallback function of Attacker, and it
tries to call the donate function again.

In order to prevent reentrancy, one could use function modifiers in solidity
b9. In case of our Vulnerable contract, even a simple check before sending the
Ether could prevent the attacker to steal Ether. The safe version of
Vulernable contract is available in Fig. 3 where we put a check, and we change
the state of NotVulnerable contract before sending Ether to the interacting
contract.

[language=Solidity] contract Vulnerable function donate(address to_) public
payable require(to_.call.value(1 ether)());

Figure 1: A sample contract vulnerable to attacks on reentrancy

[language=Solidity] contract Attacker Vulnerable public vul_contract; function
startAttack(address _addr) public vul_contract = Vulnerable(_addr);
vul_contract.donate(address(this)); function() public payable
vul_contract.donate(address(this));

Figure 2: A sample contract that abuses a contract that is vulnerable to
reentrancy

[language=Solidity] contract NotVulnerable mapping (address =¿ bool) public
donated; function donate(address to_) public payable if (donated[to_] != true)
donated[to_] = true; require(to_.call.value(1 ether)());

Figure 3: A sample contract that has the vulnerability to reentrancy fixed.

###  2.3 Related Work

\+ key literature from VR proposal [Cyrille]

In the area of malware detection, a metadata-focused approach has also been
used successfully afzal2020using; in that work, Afzal et al. look at the
frequency and size of packets sent over encrypted connections to classify the
behavior of the application as benign or malicious.

##  3 Method

Dynamit framework is built to explore the possibility of detecting a certain
class of vulnerabilities (re-entrancy) in smart contracts without looking at
the source code, and by only looking at the dynamic behavior of the smart
contract that is extracted from transactional metadata to and from the
contracts. We could gain insight into the dynamic behavior of the smart
contracts using only the metadata that is automatically generated in the
blockchain environment. We also put focus on monitoring techniques that
require the least amount of instrumentation to the blockchain system to gather
data.

To detect the vulnerable transactions part of the system has to observe the
blockchain, and other part has to make decisions based on the observations of
the former. Therefore, our verification system consists of two parts:

  1. 1.

The Monitor

  2. 2.

The Detector

The diagram of the system is depicted in Fig. 4.

Figure 4: Dynamit framework system diagram

###  3.1 Monitor

The monitor connects to the Ethereum blockchain client to gather information
about desired transactions. It uses the latest version of Web3js b2 which is
the official Ethereum Javascript API to connect to and probe the system.
In order to get data using the API’s exposed by Web3js, the monitor uses the
following techniques:

  * •

Subscribing to the events emitted by Ethereum client. There are specific
events in the Ethereum client possible to be subscribed to by Web3 client.
Mainly, these are useful to get information about when a transaction related
to an account has been issued. A list of all subscribable events is available
here b4. For the current work, we used pendingTransactions to get any new
transactions related to our accounts under observation.

  * •

Probing the blockchain at specific intervals until the desired information is
retrieved. This is more suitable for getting information about an already
mined transaction or getting the state of a contract after an event.

###  3.2 Detector

The detector is the part of the system that identifies the harmful
transactions from the benign ones. This part in our system consists of a part
that processes and cleans that data received by the monitor and a machine
learning model that is trained as the monitor feeds in the data.

###  3.3 Extracted Features

The extracted features along with the approach that monitor uses to get them
are available in Table 1.

Table 1: Features gathered by monitor and used by our ML model in detector Feature | Monitoring Mechanism
---|---
Gas usage of transaction | Event subscription
Contract 1 balance difference | Probing
Contract 2 balance difference | Probing
Average call stack depth | Probing

The contract balance difference feature is the difference of the balance of a
contract before and after the transaction has taken place. Keeping in mind
that the balance of a contract that would abuse the re-entrancy vulnerability
(and the victim) may or may not change. In those cases using only balance
difference would not suffice, and we may need to look at a book-keeping
variable. Since we try not to have any code instrumentations in our approach,
we will assume that the mentioned situation will not happen. In fact, the
feature contract balance difference may easily be replaced by any other asset
that is being transferred by the contracts to match the specific use-case.
The average call stack depth is the only feature being directly retrieved from
the transaction trace. Calling a regular function in a contract will not
increase this average call stack depth. However, recursive external calls will
drastically change this value which is usually the case for re-entrancy
vulnerability where a particular function in victim is recursively called
until the attacker contract stops. Since there is high correlation between
average stack depth and the transaction being harmful, presence of this
feature in data set makes will increase the performance of machine learning
model in detector. Therefore, we decided to put effort to superficially
increase the average call stack even for benign transactions to make it harder
for the detector to distinguish between benign and harmful transactions.
As mentioned earlier, when a contract executes on the blockchain it will spend
Gas. Therefore, the Gas usage depends on the specific operations that a
contract is performing within the specific transaction. Since performing
successful attacks on a vulnerable contract by another contract may have a
specific pattern of sequence of operations, we decided to use this gas usage
as a feature for detection.

###  3.4 Classifier

##  4 Experiments

For the experiment we monitored a total of 105 transactions with almost equal
number of harmful and benign transactions. All of the transactions have been
labelled manually before starting the experiment, therefore, they could be
used for training and testing a supervised model. Each transaction is the
result of the interaction between two contracts specific pair of contracts.
Thus, it is safe to say that for 105 transactions (data points that will be
fed to the machine learning model) we need 210 deployed smart contracts. We
chose have a distinct pair of contracts for each transaction to make the
experiment more reliable by limiting the effect of transactions on each other.
Out of these 105 transactions, 25 are generated using 25 freely available
smart contracts source codes. We wrote 25 contracts for the aforementioned
contract to interact with them. This interaction is either benign or harmful.
In other words, these are the possibilities we assumed:

  * •

The peer contract tries to exploit the re-entrancy vulnerability, and it is
successful due to the victim contract being written poorly: harmful
transaction

  * •

The peer contract tries to exploit to re-entrancy, but, it is unsuccessful
(the first contract is not vulnerable to re-entrancy): benign transaction

  * •

The peer contract does not try to exploit the re-entrancy at all: benign
transaction

Each of the 25 transactions represents one of the above possibilities.
The rest 80 transactions are generated using two sets of contract source codes
(4 contracts) that are meant to generate both harmful and benign transactions
randomly. These transactions are generated in a way to prevent overfit for
model by having random greediness in the attack or the way that the benign
transactions are performed. The source code of the Vulnerable smart contract
that is used for generating random harmful transactions (as a victim of re-
entracy vulnerability) is avaialbe in Fig. 5. Besides these two sets of
contracts will be used to generate the transactions, they will generate
transactions that emphasize particular operations that may manipulate the
monitored variables. This will result in some form of randomization in
gathered data that prevents the data points being similar.

[language=Solidity] contract Vulnerable uint public noReasonCounter = 0; uint
public c = 0; uint public d_binary = 0; uint public amount; function
random_binary() private view returns (uint8) return
uint8(uint256(keccak256(block.timestamp, block.difficulty)) function
random(uint num) private view returns (uint8) return
uint8(uint256(keccak256(block.timestamp, block.difficulty)) constructor()
public payable function donate(address to_) public payable d_binary =
random_binary(); c = random(10); if (d_binary == 1) for (uint i = 0; i ¡ c;
i++) noReasonCounter++; amount = random(10) * 500000000000000000;
require(to_.call.value(amount)());

Figure 5: Source code for the smart contract used to generate random harmful
transactions for the experiment

##  5 Results

The highest achievable accuracy get is 95 percent in detecting the vulnerable
transactions with a Random Forest classifier that has 100 decision trees. Due
to small dataset we had to employ 5-fold cross-validation.
Besides the Random Forest, we used four other models for detector: Naive Bayes
(NB), Logistic Regression, K-Nearest Neighbours, and Support Vector Machine
(SVM) with a linear kernel.
Although in terms of accuracy none of the models could outperform the Random
Forest model, there are a few interesting observations about their
performance. As it is obvious in Fig. 3, the False Positive Rate (FPR) and
False Negative Rate (FNR) are more close in Random Forest model, but in other
cases the FNR is much higher than FPR. Therefore, most of the inaccuracy of
these models should be attributed to high FNR. In other words, the detector is
labeling a considerable number of harmful transactions as benign. This is also
understandable from Fig. 4 as the recall of all the models except Random
Forest is relatively low. This further proves that these models were unable to
catch a considerable number of harmful transactions. For instance, in Fig. 3
the highest FNR belongs to the Logistic Regression model. At the same time we
observe that the least recall (0.66) belongs to the same model as it is shown
in Fig. 4. Furthermore, the f1 score for this model is only 0.77.
Conversely, the Random Forest model has a more consistent behavior making more
balanced number of mistakes for detecting benign transactions as harmful or
vice versa. This is also notable in 4 as all three metrics are around the same
0.91 number.

Figure 6: Average False Positive Rate and False Negative Rate for detecting
the vulnerable transactions based on different classification models.

Figure 7: Average Accuracy, F1 Score, and Recall when detecting the vulnerable
transactions based on different classification models.

As mentioned earlier, the contract sets we used for random transaction
generation may try to imitate the behavior of the class they do not belong to
randomly. We took this measure in an effort to generate transactions that are
harder to classify for the detector. However, calculating the correlation of
the average call stack depth reveals that the extent of this imitation on both
sides made the this correlation so small (0.02) that we decided to build the
model without using the average call stack depth feature. The performance
measurements of this version of the model is shown in Fig. 5 and Fig. 6. The
overall behavior of all model is consistent with the previous models. However,
the performance of Random Forest model increased to 95 percent.

Figure 8: Average False Positive Rate and False Negative Rate for detecting
the vulnerable transactions based on different classification models for the
case that we omit average call stack depth feature.

Figure 9: Average Accuracy, F1 Score, and Recall when detecting the vulnerable
transactions based on different classification models for the case that we
omit average call stack depth feature.

##  6 Threats to Validity

\+ small number of contracts, relatively small number of transaction

\+ bias in random transaction generator?

\+ contracts written by ourselves but modeled after real contracts

##  7 Conclusion and Future Work

In this work we present Dynamit, a dynamic vulerability detection for Ethereum
smart contracts. Our work sheds light on finding vulnerable smart contracts by
detecting harmful transactions in blockchain using transactional metadata and
machine learning. We used a dataset of 105 transactions which is large enough
to build a proof of feasibility for this approach. However, to further
develope a framework for our monitor and detector we need investigate the
automatic test-case generation tools such as Vultron b5. Therefore, the next
potential step is to use fuzzing tools to generate labeled transactions which
will help us build a more robust monitoring and detection framework. Another
direction for future work would be to find more features to make the detection
more accurate. An example would be to observe book-keeping variables inside
the contracts, and the way they change in order to collect data.

+++++++++++++++++ delete everything below(?)

###  7.1 Word Processing Software

As detailed below, IJCAI has prepared and made available a set of LaTeX macros
and a Microsoft Word template for use in formatting your paper. If you are
using some other word processing software, please follow the format
instructions given below and ensure that your final paper looks as much like
this sample as possible.

##  8 Style and Format

LaTeX and Word style files that implement these instructions can be retrieved
electronically. (See Appendix A for instructions on how to obtain these
files.)

###  8.1 Layout

Print manuscripts two columns to a page, in the manner in which these
instructions are printed. The exact dimensions for pages are:

  * •

left and right margins: .75′′

  * •

column width: 3.375′′

  * •

gap between columns: .25′′

  * •

top margin—first page: 1.375′′

  * •

top margin—other pages: .75′′

  * •

bottom margin: 1.25′′

  * •

column height—first page: 6.625′′

  * •

column height—other pages: 9′′

All measurements assume an 8-1/2′′ $\times$ 11′′ page size. For A4-size paper,
use the given top and left margins, column width, height, and gap, and modify
the bottom and right margins as necessary.

###  8.2 Format of Electronic Manuscript

For the production of the electronic manuscript, you must use Adobe’s Portable
Document Format (PDF). A PDF file can be generated, for instance, on Unix
systems using ps2pdf or on Windows systems using Adobe’s Distiller. There is
also a website with free software and conversion services:
http://www.ps2pdf.com. For reasons of uniformity, use of Adobe’s Times Roman
font is strongly suggested. In LaTeX2e this is accomplished by writing

> $\backslash$usepackage{times}

in the preamble.111You may want also to use the package latexsym, which
defines all symbols known from the old LaTeX version.

Additionally, it is of utmost importance to specify the letter format
(corresponding to 8-1/2′′ $\times$ 11′′) when formatting the paper. When
working with dvips, for instance, one should specify -t letter.

###  8.3 Title and Author Information

Center the title on the entire width of the page in a 14-point bold font. The
title must be capitalized using Title Case. Below it, center author name(s) in
12-point bold font. On the following line(s) place the affiliations, each
affiliation on its own line using 12-point regular font. Matching between
authors and affiliations can be done using numeric superindices. Optionally, a
comma-separated list of email addresses follows the affiliation(s) line(s),
using 12-point regular font.

####  8.3.1 Blind Review

In order to make blind reviewing possible, authors must omit their names and
affiliations when submitting the paper for review. In place of names and
affiliations, provide a list of content areas. When referring to one’s own
work, use the third person rather than the first person. For example, say,
“Previously, Gottlob gottlob:nonmon has shown that…”, rather than, “In our
previous work gottlob:nonmon, we have shown that…” Try to avoid including any
information in the body of the paper or references that would identify the
authors or their institutions. Such information can be added to the final
camera-ready version for publication.

###  8.4 Abstract

Place the abstract at the beginning of the first column 3′′ from the top of
the page, unless that does not leave enough room for the title and author
information. Use a slightly smaller width than in the body of the paper. Head
the abstract with “Abstract” centered above the body of the abstract in a
12-point bold font. The body of the abstract should be in the same font as the
body of the paper.

The abstract should be a concise, one-paragraph summary describing the general
thesis and conclusion of your paper. A reader should be able to learn the
purpose of the paper and the reason for its importance from the abstract. The
abstract should be no more than 200 words long.

###  8.5 Text

The main body of the text immediately follows the abstract. Use 10-point type
in a clear, readable font with 1-point leading (10 on 11).

Indent when starting a new paragraph, except after major headings.

###  8.6 Headings and Sections

When necessary, headings should be used to separate major sections of your
paper. (These instructions use many headings to demonstrate their appearance;
your paper should have fewer headings.). All headings should be capitalized
using Title Case.

####  8.6.1 Section Headings

Print section headings in 12-point bold type in the style shown in these
instructions. Leave a blank space of approximately 10 points above and 4
points below section headings. Number sections with arabic numerals.

####  8.6.2 Subsection Headings

Print subsection headings in 11-point bold type. Leave a blank space of
approximately 8 points above and 3 points below subsection headings. Number
subsections with the section number and the subsection number (in arabic
numerals) separated by a period.

####  8.6.3 Subsubsection Headings

Print subsubsection headings in 10-point bold type. Leave a blank space of
approximately 6 points above subsubsection headings. Do not number
subsubsections.

##### Titled paragraphs.

You should use titled paragraphs if and only if the title covers exactly one
paragraph. Such paragraphs should be separated from the preceding content by
at least 3pt, and no more than 6pt. The title should be in 10pt bold font and
ended with a period. After that, a 1em horizontal space should follow the
title before the paragraph’s text.

In LaTeX titled paragraphs should be typeset using

> \paragraph{Title.} text .

####  8.6.4 Acknowledgements

You may include an unnumbered acknowledgments section, including
acknowledgments of help from colleagues, financial support, and permission to
publish. If present, acknowledgements must be in a dedicated, unnumbered
section appearing after all regular sections but before any appendices or
references.

Use

> \section*{Acknowledgements})

to typeset the acknowledgements section in LaTeX.

####  8.6.5 Appendices

Any appendices directly follow the text and look like sections, except that
they are numbered with capital letters instead of arabic numerals. See this
document for an example.

####  8.6.6 References

The references section is headed “References”, printed in the same style as a
section heading but without a number. A sample list of references is given at
the end of these instructions. Use a consistent format for references. The
reference list should not include publicly unavailable work.

###  8.7 Citations

Citations within the text should include the author’s last name and the year
of publication, for example gottlob:nonmon. Append lowercase letters to the
year in cases of ambiguity. Treat multiple authors as in the following
examples: abelson-et-al:scheme or bgf:Lixto (for more than two authors) and
brachman-schmolze:kl-one (for two authors). If the author portion of a
citation is obvious, omit it, e.g., Nebel nebel:jair-2000. Collapse multiple
citations as follows: gls:hypertrees; levesque:functional-foundations.

###  8.8 Footnotes

Place footnotes at the bottom of the page in a 9-point font. Refer to them
with superscript numbers.222This is how your footnotes should appear. Separate
them from the text by a short line.333Note the line separating these footnotes
from the text. Avoid footnotes as much as possible; they interrupt the flow of
the text.

##  9 Illustrations

Place all illustrations (figures, drawings, tables, and photographs)
throughout the paper at the places where they are first discussed, rather than
at the end of the paper.

They should be floated to the top (preferred) or bottom of the page, unless
they are an integral part of your narrative flow. When placed at the bottom or
top of a page, illustrations may run across both columns, but not when they
appear inline.

Illustrations must be rendered electronically or scanned and placed directly
in your document. They should be cropped outside latex, otherwise portions of
the image could reappear during the post-processing of your paper. All
illustrations should be understandable when printed in black and white, albeit
you can use colors to enhance them. Line weights should be 1/2-point or
thicker. Avoid screens and superimposing type on patterns, as these effects
may not reproduce well.

Number illustrations sequentially. Use references of the following form:
Figure 1, Table 2, etc. Place illustration numbers and captions under
illustrations. Leave a margin of 1/4-inch around the area covered by the
illustration and caption. Use 9-point type for captions, labels, and other
text in illustrations. Captions should always appear below the illustration.

##  10 Tables

Tables are considered illustrations containing data. Therefore, they should
also appear floated to the top (preferably) or bottom of the page, and with
the captions below them.

Scenario | $\delta$ | Runtime
---|---|---
Paris | 0.1s | 13.65ms
Paris | 0.2s | 0.01ms
New York | 0.1s | 92.50ms
Singapore | 0.1s | 33.33ms
Singapore | 0.2s | 23.01ms
Table 2: Latex default table Scenario |  $\delta$ (s) | Runtime (ms)
---|---|---
Paris | 0.1 | 13.65
| 0.2 | 0.01
New York | 0.1 | 92.50
Singapore | 0.1 | 33.33
| 0.2 | 23.01
Table 3: Booktabs table

If you are using LaTeX, you should use the booktabs package, because it
produces better tables than the standard ones. Compare Tables 2 and 3. The
latter is clearly more readable for three reasons:

  1. 1.

The styling is better thanks to using the booktabs rulers instead of the
default ones.

  2. 2.

Numeric columns are right-aligned, making it easier to compare the numbers.
Make sure to also right-align the corresponding headers, and to use the same
precision for all numbers.

  3. 3.

We avoid unnecessary repetition, both between lines (no need to repeat the
scenario name in this case) as well as in the content (units can be shown in
the column header).

##  11 Formulas

IJCAI’s two-column format makes it difficult to typeset long formulas. A usual
temptation is to reduce the size of the formula by using the small or tiny
sizes. This doesn’t work correctly with the current LaTeX versions, breaking
the line spacing of the preceding paragraphs and title, as well as the
equation number sizes. The following equation demonstrates the effects (notice
that this entire paragraph looks badly formatted):

$x=\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}+\prod_{i=1}^{n}\sum_{j=1}^{n}i_{j}+\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}+\prod_{i=1}^{n}\sum_{j=1}^{n}i_{j}+\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}$
(1)

Reducing formula sizes this way is strictly forbidden. We strongly recommend
authors to split formulas in multiple lines when they don’t fit in a single
line. This is the easiest approach to typeset those formulas and provides the
most readable output

$\displaystyle x=$
$\displaystyle\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}+\prod_{i=1}^{n}\sum_{j=1}^{n}i_{j}+\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}+\prod_{i=1}^{n}\sum_{j=1}^{n}i_{j}+$
$\displaystyle+$ $\displaystyle\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}$ (2)

If a line is just slightly longer than the column width, you may use the
resizebox environment on that equation. The result looks better and doesn’t
interfere with the paragraph’s line spacing:

$\displaystyle
x=\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}+\prod_{i=1}^{n}\sum_{j=1}^{n}i_{j}+\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}+\prod_{i=1}^{n}\sum_{j=1}^{n}i_{j}+\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}$

(3)

This last solution may have to be adapted if you use different equation
environments, but it can generally be made to work. Please notice that in any
case:

  * •

Equation numbers must be in the same font and size than the main text (10pt).

  * •

Your formula’s main symbols should not be smaller than small text (9pt).

For instance, the formula

$\displaystyle
x=\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}+\prod_{i=1}^{n}\sum_{j=1}^{n}i_{j}+\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}+\prod_{i=1}^{n}\sum_{j=1}^{n}i_{j}+\prod_{i=1}^{n}\sum_{j=1}^{n}j_{i}+\prod_{i=1}^{n}\sum_{j=1}^{n}i_{j}$

(4)

would not be acceptable because the text is too small.

##  12 Examples, Definitions, Theorems and Similar

Examples, definitions, theorems, corollaries and similar must be written in
their own paragraph. The paragraph must be separated by at least 2pt and no
more than 5pt from the preceding and succeeding paragraphs. They must begin
with the kind of item written in 10pt bold font followed by their number
(e.g.: Theorem 1), optionally followed by a title/summary between parentheses
in non-bold font and ended with a period. After that the main body of the item
follows, written in 10 pt italics font (see below for examples).

In LaTeX We strongly recommend you to define environments for your examples,
definitions, propositions, lemmas, corollaries and similar. This can be done
in your LaTeX preamble using \newtheorem – see the source of this document for
examples. Numbering for these items must be global, not per-section (e.g.:
Theorem 1 instead of Theorem 6.1).

######  Example 1 (How to write an example).

Examples should be written using the example environment defined in this
template.

######  Theorem 1.

This is an example of an untitled theorem.

You may also include a title or description using these environments as shown
in the following theorem.

######  Theorem 2 (A titled theorem).

This is an example of a titled theorem.

##  13 Proofs

Proofs must be written in their own paragraph separated by at least 2pt and no
more than 5pt from the preceding and succeeding paragraphs. Proof paragraphs
should start with the keyword “Proof.” in 10pt italics font. After that the
proof follows in regular 10pt font. At the end of the proof, an unfilled
square symbol (qed) marks the end of the proof.

In LaTeX proofs should be typeset using the \proof environment.

###### Proof.

This paragraph is an example of how a proof looks like using the \proof
environment. ∎

##  14 Algorithms and Listings

Algorithms and listings are a special kind of figures. Like all illustrations,
they should appear floated to the top (preferably) or bottom of the page.
However, their caption should appear in the header, left-justified and
enclosed between horizontal lines, as shown in Algorithm 1. The algorithm body
should be terminated with another horizontal line. It is up to the authors to
decide whether to show line numbers or not, how to format comments, etc.

In LaTeX algorithms may be typeset using the algorithm and algorithmic
packages, but you can also use one of the many other packages for the task.

Algorithm 1 Example algorithm

Input: Your algorithm’s input
Parameter: Optional list of parameters
Output: Your algorithm’s output

1: Let $t=0$.

2: while condition do

3: Do some action.

4: if conditional then

5: Perform task A.

6: else

7: Perform task B.

8: end if

9: end while

10: return solution

## Acknowledgments

The preparation of these instructions and the LaTeX and BibTeX files that
implement them was supported by Schlumberger Palo Alto Research, AT&T Bell
Laboratories, and Morgan Kaufmann Publishers. Preparation of the Microsoft
Word file was supported by IJCAI. An early version of this document was
created by Shirley Jowell and Peter F. Patel-Schneider. It was subsequently
modified by Jennifer Ballentine and Thomas Dean, Bernhard Nebel, Daniel
Pagenstecher, Kurt Steinkraus, Toby Walsh and Carles Sierra. The current
version has been prepared by Marc Pujol-Gonzalez and Francisco Cruz-Mencia.

##  Appendix A LaTeX and Word Style Files

The LaTeX and Word style files are available on the IJCAI–21 website,
https://www.ijcai21.org/. These style files implement the formatting
instructions in this document.

The LaTeX files are ijcai21.sty and ijcai21.tex, and the BibTeX files are
named.bst and ijcai21.bib. The LaTeX style file is for version 2e of LaTeX,
and the BibTeX style file is for version 0.99c of BibTeX (not version 0.98i).
The ijcai21.sty style differs from the ijcai20.sty file used for
IJCAI–PRICAI–20.

The Microsoft Word style file consists of a single file, ijcai21.doc. This
template differs from the one used for IJCAI–PRICAI–20.

These Microsoft Word and LaTeX files contain the source of the present
document and may serve as a formatting sample.

Further information on using these styles for the preparation of papers for
IJCAI–21 can be obtained by contacting<EMAIL_ADDRESS>