ifaamas doi [AAMAS’18]Proc. of the 17th International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2018), M. Dastani, G. Sukthankar, E.
Andre, S. Koenig (eds.)July 2018Stockholm, Sweden 2018 2018

0000-0002-0561-9641 Collective Learning Group, The MIT Media Lab Massachusetts
Institute of Technology, 22 Ames Street, Cambridge Massachusetts 02139

INESC-ID and Instituto Superior Técnico,
Universidade de Lisboa 2744-016 Porto Salvo, Portugal

# Local Wealth Redistribution Promotes Cooperation in Multiagent Systems

Flávio L. Pinheiro<EMAIL_ADDRESS>and  Fernando P. Santos
<EMAIL_ADDRESS>
###### Abstract.

Designing mechanisms that leverage cooperation between agents has been a long-
lasting goal in Multiagent Systems. The task is especially challenging when
agents are selfish, lack common goals and face social dilemmas, i.e.,
situations in which individual interest conflicts with social welfare. Past
works explored mechanisms that explain cooperation in biological and social
systems, providing important clues for the aim of designing cooperative
artificial societies. In particular, several works show that cooperation is
able to emerge when specific network structures underlie agents’ interactions.
Notwithstanding, social dilemmas in which defection is highly tempting still
pose challenges concerning the effective sustainability of cooperation. Here
we propose a new redistribution mechanism that can be applied in structured
populations of agents. Importantly, we show that, when implemented locally
(i.e., agents share a fraction of their wealth surplus with their nearest
neighbors), redistribution excels in promoting cooperation under regimes
where, before, only defection prevailed.

###### Key words and phrases:

Emergent behaviour; Social networks; Social simulation; Simulation of complex
systems; Cooperation

¡ccs2012¿ ¡concept¿
¡concept_id¿10010147.10010178.10010219.10010220¡/concept_id¿
¡concept_desc¿Computing methodologies Multi-agent systems¡/concept_desc¿
¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿
¡concept_id¿10010147.10010178.10010219.10010223¡/concept_id¿
¡concept_desc¿Computing methodologies Cooperation and
coordination¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿
¡/concept¿ ¡/ccs2012¿

[500]Computing methodologies Multi-agent systems [500]Computing methodologies
Cooperation and coordination

##  1\. Introduction

Explaining cooperation among selfish and unrelated individuals has been a
central topic in evolutionary biology and social sciences Nowak (2012).
Simultaneously, the challenge of designing cooperative Multiagent Systems
(MAS) has been a long standing goal of researchers in artificial intelligence
(AI) Genesereth et al. (1986); Jennings et al. (1998). More than thirty years
ago it was already clear that ”Intelligent agents will inevitably need to
interact flexibly with other entities. The existence of conflicting goals will
need to be handled by these automated agents, just as it is routinely handled
by humans.“ Genesereth et al. (1986).

In Cooperative multiagent interactions, agents need to collaborate towards
common goals, which introduces challenges associated with coordination,
communication and teamwork modeling Panait and Luke (2005); Jennings et al.
(1998). Self-interested interactions, in contrast, require the design of
indirect incentive schemes that motivate selfish agents to cooperate in a
sustainable way Ephrati and Rosenschein (1996); Jennings et al. (1998).
Cooperation is often framed as an altruistic act that requires an agent to pay
a cost ($c$) in order to generate a benefit ($b$) to another. Refusing to
incur in such a cost is associated with an act of defection and results in no
benefits generated. Whenever the benefit exceeds the cost ($b>c$) and plays
occur simultaneously, agents face the Prisoner’s Dilemma, a decision-making
challenge that embodies a fundamental social dilemma within MAS Macy and
Flache (2002): rational agents pursuing their self-interests are expected to
defect, while the optimal collective outcome requires cooperation. If
defection is the likely decision of rational agents, however, how can we
justify the ubiquity of cooperation in the real world? Evolutionary biology
has pursued this fundamental question by searching for additional evolutionary
mechanisms that might help to explain the emergence of cooperative behavior
Nowak (2012, 2006). Some of these mechanisms allowed to develop solutions that
found applications in computer science, such as informing about ways of
incentivizing cooperation in p2p networks Golle et al. (2001); Feldman and
Chuang (2005), wireless sensor networks Akyildiz et al. (2002), robotics
Waibel et al. (2011) or resource allocation and distributed work systems
Seuken et al. (2010) – to name a few.

Network reciprocity is one of the most popular mechanisms to explain the
evolution of cooperation in social and biological systems Nowak and May
(1992); Santos and Pacheco (2005); Ohtsuki et al. (2006); Pinheiro et al.
(2012, 2016); Pinheiro and Hartmann (2017). In this context, populations are
structured and interactions among agents are constrained. These constraints
are often modelled by means of a complex network of interactions. Applications
of this mechanism have been explored in the design of MAS that reach high
levels of cooperation Hofmann et al. (2011); Peleteiro et al. (2014); Ranjbar-
Sahraei et al. (2014); Airiau et al. (2014). Despite these advances,
cooperation on structured populations is still hard to achieve when
considering social dilemmas with high levels of temptation to defect.
Additional complementary mechanisms are required.

Here we consider that agents contribute a percentage of their surplus (defined
below), which is later divided among a Beneficiary Set of other agents. In
this context, we aim at answering the following questions:

  * •

Does redistribution of wealth promote the evolution of cooperation?

  * •

How should Beneficiary Sets be selected?

  * •

What are the potential disadvantages of such a mechanism?

Using methods from Evolutionary Game Theory (EGT) Sigmund (2010) and resorting
to computer simulations, we explore how wealth redistribution impacts the
evolution of cooperation on a population of agents without memory (i.e. unable
to recall past interactions) and rationally bounded (i.e. lacking full
information on payoff structure of the game they are engaging). We assume that
agents resort to social learning through peer imitation, which proves to be a
predominant adaptation scheme employed by humans Rendell et al. (2010). Also,
we consider that strategies are binary – Cooperate and Defect – opting to
focus our attention on the complexity provided by 1) heterogeneous
populations, 2) the redistribution mechanism and 3) the self-organizing
process of agents when adapting over time. The role of larger strategy spaces
(such as in Peleteiro et al. (2014); Ranjbar-Sahraei et al. (2014); Santos et
al. (2017)) lies outside the scope of the present work.

With redistribution, we show that cooperation emerges in a parameter region
where previously it was absent. Moreover, we show that the optimal choice of
redistributing groups consists in picking the nearest neighbors (local
redistribution). This result fits with a local and polycentric view of
incentive mechanisms Ostrom (2015); Vasconcelos et al. (2015) in MAS, which
may not only be easier to implement but, as we show, establish an optimal
scale of interaction in terms of eliciting cooperation.

##  2\. Related Work

The problem of Cooperation is a broad and intrinsically multidisciplinary
topic, which has been part of the MAS research agenda for a long time Jennings
et al. (1998); Genesereth et al. (1986). In the realm of evolutionary biology,
several mechanisms were proposed to explain the evolution of cooperation Nowak
(2006). Kin selection Hamilton (1964), direct reciprocity Trivers (1971),
indirect reciprocity Nowak and Sigmund (2005); Santos et al. (2018) and
network reciprocity Santos and Pacheco (2005); Ohtsuki et al. (2006)
constitute some of the most important mechanisms proposed. Remarkably, these
mechanisms have been applied in AI in order to design MAS in which cooperation
emerges. For example, Waibel et al. associated kin selection with evolutionary
robotics Waibel et al. (2011); Griffiths employed indirect reciprocity to
promote cooperation in p2p networks while Ho et al. investigated the social
norms that, through a system of reputations and indirect reciprocity, promote
cooperation in crowdsourcing markets Griffiths (2008); Ho et al. (2012).
Similarly, Peleteiro et al. combined indirect reciprocity with complex
networks to design a MAS where, again, cooperation is able to emerge Peleteiro
et al. (2014). On top of that, Han applied EGT – as performed in our study –
in order to investigate the role of punishment and commitments in multiagent
cooperation, both in pairwise Han (2016) and group interactions Han et al.
(2017). Regarding alternative agent-oriented approaches to sustain cooperation
in MAS, we shall underline the role of electronic institutions Esteva et al.
(2004); Arcos et al. (2005) whereby agents’ actions are explicitly constrained
so that desirable collective behaviors can be engineered.

The role of population structure and network reciprocity is, in this context,
a prolific area of research. In Pinheiro et al. (2012) it was shown that
complex networks are able to fundamentally change the dilemma at stake,
depending on the particular topology considered Pinheiro et al. (2012);
Ichinose et al. (2017); Ranjbar-Sahraei et al. applied tools from control
theory in order to study the role of complex networks on the evolution of
cooperation Ranjbar-Sahraei et al. (2014). Importantly, the role of dynamic
networks – i.e., agents are able to rewire their links – was also shown to
significantly improve the levels of cooperation, especially in networks with a
high average degree of connectivity Santos et al. (2006); Pinheiro et al.
(2016). A survey on the topic of complex networks and the emergence of
cooperation in MAS can be accessed in Hofmann et al. (2011).

Previous works found that cooperation in structured population substantially
decreases when the temptation to defect increases (see Model for a proper
definition of Temptation). Thereby, here we contribute with an additional
mechanism of cooperation on structured populations. We consider a mechanism of
redistribution, inspired in the wealth redistribution mechanisms that prevail
in modern economic/political systems, mainly through taxation. We are
particularly interested in understanding how to sample redistribution groups
in an effective way. In this context, we shall underline the works of Salazar
et al. and Burguillo-Rial, in which a system of taxes and coalitions was shown
to promote cooperation on complex networks Salazar et al. (2011) and regular
grids Burguillo-Rial (2009). While Salazar et al. (2011) and Burguillo-Rial
(2009) do an excellent job showing how coalitions – leaded by a single agent –
emerge, here we consider a simpler/decentralized model (e.g. no leaders are
considered and taxes are redistributed rather than centralized in a single
entity) and focus our analysis on showing that local redistribution sets are
optimal. Our approach does not require additional means of reciprocity,
memory, leadership, punishment or knowledge about features of the network. We
cover a wide range of dilemma strengths and explicitly show when the local
redistribution promotes cooperation by itself. Notwithstanding, the analysis
performed in Salazar et al. (2011) and Burguillo-Rial (2009) surely provides
important insights to address in future works, on how to explicitly model the
adherence to beneficiary sets and guarantee their stability. Also, while here
we assume an egalitarian redistribution over each individual in the
Beneficiary Set, we shall note that different redistribution heuristics may
imply different levels of allocation fairness Pitt et al. (2012). In this
context, a recent work introduces the concept of Distributed Distributed
Justice Kurka and Pitt (2016) and shows that local interactions may provide a
reliable basis to build trust and reputation between agents, which can be used
to regulate, in a decentralized way, the levels of justice in agents’ actions.
This way, it is rewarding to note that local interactions not only constitute
an optimal scale to form cooperative Beneficiary Sets (as we show, see below),
but also provide the convenient interaction environment to allow justice in
contributions to be sustained.

##  3\. Model

###  3.1. Three Stage Redistribution Game

Here we propose a sequential game dynamics made of three stages. Focusing on
an arbitrary agent $i$, these stages can be described as follows:

  1. (1)

Agent $i$ participates in a one-shot game (here a Prisoner’s Dilemma) with all
his/her neighbors $j$. From each interaction $j$, he/she obtains a payoff
$\pi_{i,j}$. After all interactions, agent $i$ accumulates a total payoff
$\Pi_{i}=\sum_{j}\pi_{i,j}$;

  2. (2)

Next, agent $i$ contributes a fraction $\alpha$ of his/her payoff surplus
($\Pi_{i}-\theta$) to be redistributed. The group that benefits from agent $i$
contribution is called Beneficiary Set $i$ ($B_{i}$).

  3. (3)

Finally, agent $i$ receives his/her share from each Beneficiary Set that
he/she is part of.

We refer to $\alpha$ as the level of taxation, as it defines the fraction of
the surplus that agents contribute, while $\theta$ is the threshold level of
payoff that defines the surplus. By definition, agents with negative payoff
cannot contribute (i.e., $\theta>0$); they might, however, receive benefits
from the Beneficiary Sets. Each agent $i$ contributes only to one Beneficiary
Set $B_{i}$ from which they cannot be part of, that is, agents do not receive
from the Beneficiary Set they contribute to. A central question of this work
is how to select $B_{i}$ for each $i$. As we show, this decision has a
profound and non-trivial impact on the overall cooperation levels in the
system.

###  3.2. The Prisoner’s Dilemma Game

Figure 1. Solutions for the two-person game with wealth redistribution. Each
curve indicates the critical taxation levels ($\alpha^{\ast}$) above which the
nature of the social dilemma changes, for different payoff thresholds
($\theta$) and as a function of the Temptation parameter ($T$).

In general, all the possible outcomes of a two-strategy two-player game, in
which two agents engage in a one-shot interaction that requires them to decide
– independently and simultaneously – whether they wish to Cooperate (C) or to
Defect (D), can be summarized in a payoff matrix, such as

| C | D
---|---|---
C | $R$ | $S$
D | $T$ | $P$

which reads as the payoff obtained by playing the row strategy when facing an
opponent with the column strategy. Here, $R$ represents the Reward payoff for
mutual cooperation and $P$ the Punishment for mutual defection. When one of
the individuals Defects and the other Cooperates, the first receives the
Temptation payoff ($T$) while the second obtains the Sucker’s payoff ($S$). In
this manuscript we consider that agents interact according to the Prisoner’s
Dilemma (PD). Agents are said to face a PD whenever the relationship between
the payoffs is such that $T>R>P>S$ Sigmund (2010). In such a scenario,
rational agents seeking to optimize their self-returns are expected to always
Defect. However, since the best aggregated outcome would have both players
cooperating ($2R>2P$), agents are said to face a social dilemma: optimizing
self-returns clashes with optimizing the social outcome. In this sense, mutual
cooperation is Pareto Optimal and contributes to increase both average payoff
(over mutual defection) and egalitarian social welfare (over unilateral
cooperation) Endriss and Maudet (2003). It is noteworthy to mention that other
situations – with different optimal rational responses – arise when the
parameters take a different relationship Macy and Flache (2002): the Stag Hunt
game when $R>T>P>S$; the Snowdrift Game when $T>R>S>P$; the Harmony Game when
$R>T>S>P$; or the Deadlock Game when $T>P>R>S$, to name a few.
Notwithstanding, the PD is by far the most popular metaphor of social dilemmas
Sigmund (2010) and the one that presents the biggest challenge for cooperation
to emerge. For these reasons, PD shall be the main focus of study in this
manuscript. We further simplify the parameter space by considering that $R=1$,
$P=0$, $S=1-T$ and $1<T\leq 2$ with the game being fully determined by the
Temptation value (T). In that sense, higher temptation creates more stringent
conditions for the emergence of cooperation.

###  3.3. Prisoner’s Dilemma with Wealth Redistribution

Figure 2. Graphical depiction of the specific structures used in this work. a)
Homogeneous Networks correspond to a structure in which all nodes have the
same degree. b) Heterogeneous Networks are characterized by a high variance
among the degree of nodes. The color of each node indicates its degree: blue
tones represent lower degree and red tones higher degree. Panel c) and d)
show, respectively, the degree distributions of the Homogeneous and
Heterogeneous networks under analysis. In particular, we use scale-free
networks as representatives of heterogeneous structures; these have a degree
distribution that decays as a power law.

As an introductory example, let us start by analyzing the particular case of
two interacting agents ($i$ and $j$) in a one-shot event. In this case, the
Beneficiary Sets of each agent ($B_{i}$ and $B_{j}$) are composed only by the
opponent. Wealth/payoff redistribution can thus be analyzed by considering a
slightly modified payoff matrix, that takes into account the second and third
stages. The resulting payoff matrix becomes

| C | D
---|---|---
C | $1$ | $1-T+\alpha(T-\theta)$
D | $T-\alpha(T-\theta)$ | $0$

where $\theta$ is the payoff threshold and $\alpha$ is the level of taxation.
The rationale to arrive at this payoff structure is the following: whenever
both players choose to act the same way the payoff remains the same as their
contributions (from taxes) and benefits (from receiving the contributions of
their opponent) cancel out. A Defector playing against a Cooperator sees his
payoff of $T$ subtracted by an amount $\alpha(T-\theta)$ while not receiving
any benefit, since the Cooperator has negative payoff and does not contribute.
Likewise, the Cooperator is exempt from contributing but receives an
additional contribution of $\alpha(T-\theta)$, which represents the amount
taxed to the Defector.

Figure 3.  Level of Cooperation on Homogeneous Random Networks (a) and
Heterogeneous (Scale-free) Networks (b). Each plot shows the level of
cooperation under a different combination of taxation level, $\alpha$, and
Temptation, $T$. In all cases the fitness threshold is fixed at
$\theta=R=1.0$. Blue indicates regions where Cooperation dominates, Red
delimits regions dominated by Defectors. Top bars above each panel indicate
the level of cooperation in the absence of wealth redistribution, as a
function of the Temptation payoff parameter. The level of cooperation is
computed by estimating the expected fraction of cooperators when the
population reaches a stationary state. To that end we run $10^{4}$ independent
simulations that start with $50\%$ cooperators and $50\%$ defectors.
Population size of $Z=10^{3}$ and intensity of selection $\beta=1.0$.

To inspect whether wealth redistribution changes the nature of the social
dilemma (_i.e._ from a Prisoner’s Dilemma to another type of game) we have to
inspect whether there is a difference in the relationship between the payoffs
$R$ and $T$ or $P$ and $S$. This sums up to solving a single inequality,

$T-\alpha(T-\theta)<1$ (1)

which results in the critical values of $\alpha$,

$\alpha^{\ast}>\frac{T-1}{(T-\theta)}$ (2)

Hence, depending on the choice of $\theta$ and for a given $T$,
$\alpha^{\ast}$ is the minimum level of taxation required to observe a change
in the nature of the game faced by agents. It is straightforward to notice
that the nature of the game changes from a Prisoner’s Dilemma to an Harmony
Game as the relationship moves from $T>R>P>S$ to $R>T>S>P$. Figure 1 shows
$\alpha^{\ast}$ for different values of $T$ and $\theta$. Clearly, in well-
mixed populations and under the simple scenario of a MAS composed by two
agents, the redistribution mechanism has the simple effect of reshaping the
payoff matrix, trivially changing the nature of the dilemma. Such a trivial
conclusion cannot be drawn with large populations playing on networks, where
we will show that different ways of assigning the Beneficiary Sets have a
profound impact on the ensuing levels of cooperation.

Figure 4. Level of cooperation on Heterogeneous (a) and Homogeneous (b)
populations for different values of the payoff threshold ($\theta$) as a
function of the Temptation payoff parameter ($T$). Gray Dashed line shows the
results obtained in the absence of a wealth redistribution scheme. Population
size of $Z=10^{3}$ and intensity of selection $\beta=1.0$.

###  3.4. Structured Populations

Let us consider a population of $Z$ agents in which agents correspond to the
nodes/vertices of a complex network, while links dictate who interacts with
whom. The structure reflects the existence of constraints that limit
interactions between agents. These constraints can arise from spatial or
communication limitations.

The number of interactions that each agent $i$ participates in defines his/her
degree $z_{i}$. The distribution of degrees, $D(z)$, describes the fraction of
agents that has degree $z$. In this work we consider two structures:
Homogeneous Random Graphs Santos et al. (2005, 2017) and Scale-Free Barabási
Networks Albert and Barabási (2002).

Homogeneous Random Graphs are generated by successively randomizing the ends
of pairs of links from an initially regular graph (e.g. Lattice or Ring). The
resulting structure has a random interaction structure but all nodes in the
network have the same degree. Figure 2a) depicts graphically an example of
such structures and Figure 2c) the corresponding Degree distribution.

Scale-free networks are generated by an algorithm of growth and preferential
attachment Albert and Barabási (2002). This algorithm is as follows: 1) start
from three fully connected nodes; 2) add, sequentially, each of the $Z-m$
remaining nodes; 3) each time a new node is added, it connects to $m$ pre-
existing nodes, selecting preferentially nodes with higher degree. Here we
have used $m=3$ The resulting network is characterized by a heterogeneous
degree distribution (one which decays as a power law), in which the majority
of the nodes have few connections while a few have many. Figure 2b) shows a
graphical example of such structure and Figure 2d) the degree distribution.

In the following we explore the case of networks with $Z=10^{3}$ nodes and
average degree of $\langle z\rangle=\sum_{z}zD(z)=4$. During the simulations
we make use of $20$ independently generated networks of each type.

###  3.5. Games on Networks

We study the expected level of cooperation attained by the population. We
estimate this quantity through computer simulations. The level of cooperation
corresponds to the expected fraction of cooperators in a population that
evolved after $2.5\times 10^{6}$ iterations. We estimate this quantity by
averaging the observed fraction of cooperators at the final of each
simulation, over $10^{4}$ independent simulations.

Each simulation starts from a population with an equal composition of
Cooperators and Defectors, which are randomly placed along the nodes of the
network. In between each update round, each agent $i$ plays once with all
his/her $z_{i}$ nearest neighbors (i.e., agents they are directly connected
with). The accumulated payoff over all interactions an agent $i$ participates
can be computed as

$\Pi_{i}=n^{C}_{i}T-\sigma_{i}(1-T)(n^{D}_{i}+n^{C}_{i})$ (3)

where $n_{i}^{D}$ ($n_{i}^{C}$) is the number of neighbors of $i$ that Defect
(Cooperate) and $\sigma_{i}$ is equal to 1 if $i$ is a Cooperator and 0
otherwise. From the accumulated payoff, agents contribute to a pool a fraction
$\alpha$ of the surplus $\Pi-\theta$. The fitness $f_{i}$ of an agent $i$
results from subtracting from his/her accumulated payoff his/her contributions
plus the share he/she obtains from each of the Beneficiary Sets $j$ he/she
participates in. We shall underline that, while $T$ is the same for all agents
(that is, the dilemma is the same for everyone in the population),
heterogeneous populations introduce an additional complexity layer by implying
that different agents may vary in the maximum values of accumulated payoff
that they are able to earn. This can be formalized as

$f_{i}=(1-\alpha)(\Pi_{i}-\theta)+\sum_{j}^{Z}\delta_{i,j}\frac{\alpha(\Pi_{j}-\theta)}{|B_{j}|}$
(4)

where $\delta_{i,j}$ is equal to one if $i$ is part of the Beneficiary Set
towards which $j$ contributes and zero otherwise, while $|B_{j}|$ denotes the
size of set $B_{j}$.

Figure 5. Comparison between the effects of assigning the nearest neighbors of
an agent $i$ to the corresponding Beneficiary Set $B_{i}$ (dark blue line) and
when agents are assigned at random to $B_{i}$ (light blue), on the level of
cooperation in the domain of the Temptation payoff parameter, T. Panel a)
shows the results on Heterogeneous populations and panel b) the impact on
Homogeneous populations. Population size of $Z=10^{3}$ and intensity of
selection $\beta=1.0$.

Evolution in the frequency of strategies adopted in the population happens
through a process of imitation or social learning. At each iteration a random
agent, say $i$, compares his fitness with the fitness of a neighbor, say $j$.
Depending on the fitness difference, $i$ adopts the strategy of $j$ with
probability

$p=\frac{1}{1+Exp(-\beta(f_{j}-f_{i}))}$ (5)

The meaning of this sigmoid function can be understood as follows: if $j$ is
performing much better than $i$, then $i$ updates his/her strategy, adopting
the strategy of $j$. Conversely, if $j$ is performing much worse, $i$ does not
update the strategy. The parameter $\beta$, often called the intensity of
selection and akin to a learning rate, dictates how sharp is the transition
between these two regimes, as $f_{j}-f_{i}$ approaches zero. Large $\beta$
means that individuals act in a more deterministic way, updating strategies at
the minimum difference; small $\beta$ means that individuals are prone to make
imitation mistakes.

##  4\. Results

###  4.1. Wealth Redistribution and the Level of Cooperation in Structured
Populations

In this section we start by analyzing the scenario in which the Beneficiary
Set of each agent $i$ corresponds to his/her nearest neighbors. Hence, the
size of the Beneficiary set of $i$ is $|B_{i}|=z_{i}$. These are also the
agents from whom he/she interacts with and obtains a payoff from. Figure 3
shows the achieved levels of cooperation when the payoff threshold is set to
$\theta=R=1.0$, as a function of the Temptation payoff ($T$) and the level of
taxation ($\alpha$). Figure 3a shows the results on Homogeneous networks, and
Figure 3b on Heterogeneous. We find that, for a fixed payoff threshold
($\theta$), increasing the level of taxation results in an increase in the
levels of cooperation. This effect diminishes with an increase in the
Temptation ($T$). That is, when increasing $T$ the minimum value of $\alpha$
necessary to promote cooperation increases as well. The same behavior is
observed in both structures. However, there is a larger degree of cooperation
on Heterogeneous networks, where there is always a level of taxation for a
given Temptation that guarantees a 100$\%$ level of cooperation. Hence, in
order for cooperation to be evolutionary viable on homogeneous networks, more
stringent conditions are necessary, e.g. higher tax levels.

Figure 4 shows how the level of cooperation depends on variations of the
fitness threshold ($0\leq\theta\leq 2.0$, in intervals of $0.4$) while keeping
a fixed level of taxation ($\alpha=0.5$) under different levels of the
Temptation payoff ($T$). Figure 4a shows the results obtained for
Heterogeneous networks and panel b) the results on Homogeneous structures. For
a constant level of taxation, $\alpha$, decreasing the payoff threshold,
$\theta$, increases the range of Temptation, $T$, under which cooperation can
possibly evolve. This is the case in both types of structures. However, once
again, the effect is more limited in homogeneous populations.

Both Figure 3 and 4 highlight the positive impact of a local wealth
redistribution mechanism in the enhancement of cooperation. It also puts in
evidence that the success of such mechanism depends on the volume of payoff
that is redistributed. Ultimately, this can be done by either increasing the
level of taxation, $\alpha$ or decreasing the payoff threshold, $\theta$, that
defines the taxable payoff.

Figure 6. Panel a) compares how extending beneficiary sets, from the nearest
neighbors ($d=1$) to nodes at a distance up to $d=4$ links away, impacts the
level of cooperation on Heterogeneous networks. Panel b) shows how extended
beneficiary sets impact the level of cooperation on Homogeneous networks. In
both cases extending the set of beneficiaries has a negative a negative impact
in the levels of cooperation. Population size of $Z=10^{3}$ and intensity of
selection $\beta=1.0$.

###  4.2. Randomized Beneficiary Set

Next we explore to which extent the results obtained depend on the way agents
are being assigned to each Beneficiary Set. To that end, we compare two cases:
i) nearest set assignment – the Beneficiary Set of each agent corresponds to
her/his nearest neighbors, as above; and ii) random set assignment – agents
are assigned at random to each Beneficiary Set. The number of agents assigned
to each set is equal to the degree of the contributing agent, in both cases,
which guarantees that the collected payoffs from each agent are distributed
among the same number of individuals in both i) and ii).

Figure 5a and b show the results obtained, respectively, on Heterogeneous and
Homogeneous networks. We consider $\theta=0.5$, $\alpha=0.9$ and explore the
domain $1.0\leq T\leq 2$. Dark blue curves show the results obtained under the
nearest set assignment and light blue curves the results obtained under a
random set assignment. The results show that the ability of a wealth
redistribution mechanism lies in the redistribution of the taxed payoff among
the agents that are spatially related. A random assignment of agents
drastically decreases the levels of cooperation obtained in both networks. But
to which extent do the Beneficiary Sets need to be constrained spatially?

Figure 7. Panel a) shows the fixation times (in generations) on homogeneous
networks. Panel b) shows the fixation times (in generations) in heterogeneous
networks. A generation corresponds to $Z$ iteration steps and the fixation
times indicate the expected time that the population takes to arrive to a
state dominated by Cooperators or Defectors when starting from a state with
equal abundance of both strategies. Population size of $Z=10^{3}$ and
intensity of selection $\beta=1.0$.

###  4.3. Extended Beneficiary Set

To answer the previous question, we explore the case in which all nodes (up to
a distance of $d$ links) are assigned to the Beneficiary Set of a focal agent
$i$; when $d=1$ the previous results are thereby obtained.

Figure 6a and b show the results up to $d=4$ on Heterogeneous and Homogeneous
networks respectively. In both cases, we see that an expansion in the size of
the Beneficiary Set leads to a decrease in the levels of cooperation. This
result further reinforces the conclusion that wealth redistribution is only
efficient when agents return, in form of taxes, a share of the accumulated
payoffs to the agents they have engaged with. We shall underline that here
both distance and size of $B_{i}$ play a role on the obtained results, while
in the previous section the size of $B_{i}$ was kept constant for each $i$
across the different treatments, thus disambiguating the effect of $B_{i}$
size and distance on the resulting cooperation levels.

###  4.4. What is the cost of wealth redistribution?

Figure 7a and b shows the fixation times of populations when $\theta=1.0$
along the domain bounded by $0.0\leq\alpha\leq 1.0$ and $1.0\leq T\leq 2.0$.
The fixation times correspond to the expected number of generations (i.e.,
sets of $Z$ potential imitation steps) for the population to reach a state in
which only one strategy is present in the population. These plots map directly
into Figure 3a and b, allowing to compare the relative fixation times of
regions with high/low levels of cooperation.

We observe that the evolution of cooperation is associated with an increase in
the fixation times. This increase can be in some situations an order of
magnitude higher. The regions that exhibit larger fixation times lie in the
critical boundary that divides areas of defectors and cooperators dominance
(Figure 3). Hence, promoting cooperation by redistributing wealth also
requires a longer waiting time for the population to reach a state of full
cooperation. However, setting higher taxation values than the bare minimum
necessary for the emergence of cooperation allows populations to reach
fixation quicker.

###  4.5. Multiple Contribution Brackets

In the real world, taxes are unlikely to be defined by a single threshold
($\theta$) that separates agents who contribute from those that do not. In
reality taxes are progressive, in the sense that taxation levels ($\alpha$)
increase with increasing level of income (in this case accumulated payoff). In
this section we implement a similar approach and inspect the impact of
increasing the number of taxation brackets.

Let us consider that, instead of a single threshold we now have $B$ taxation
brackets divided by $B-1$ threshold levels. For each bracket we define
$\alpha_{b}$ as the effective tax and $\theta_{b}$ as the bottom threshold of
bracket $b$, where $b\in\\{0,1,2,...,B-1,B\\}$.

By definition $B=0$ corresponds to the case in which no taxes are collected,
and the redistribution of wealth is absent. Moreover, $B=1$, implies the
existence of a single bracket were all individuals would contribute, a case
that we do not explore in this manuscript. $B=2$, corresponds to the case in
which there are two brackets, which is the scenario that we have explored
until now.

We consider the case in which taxation increases linearly with increasing
brackets. Let us define $\theta_{b}=b\theta/B$. Individuals in bracket $b$
have their payoff surplus taxed by $\alpha_{b}=(b-1)\alpha/B$ when their
accumulated payoff falls into $\theta_{b}<\Pi\leq\theta_{b+1}$ for $b<B-1$.
For $b=B$ the tax level is $\alpha_{b}=\alpha$ and affects all individuals
with $\Pi>\theta$.

As an example, for $B=3$ each bracket would be characterized by the following
tax levels

  * $b=0$)

$\alpha_{b}=0$ for all individuals with $\Pi\leq\theta/3$;

  * $b=1$)

$\alpha_{b}=\alpha/3$ for all individuals with $\theta/3<\Pi\leq 2\theta/3$;

  * $b=2$)

$\alpha_{b}=2\alpha/3$ for all individuals with $2\theta/3<\Pi\leq\theta$;

  * $b=3$)

$\alpha_{b}=\alpha$ for all individuals with $\Pi>\theta$.

In this way we use $\theta$ and $\alpha$ as the upper level bound and only
parameters in this condition.

We find that variations in the number of taxation brackets ($B$=3,4,5) have
only a marginal impact in the overall levels of cooperation observed when
compared with the scenarios studied so far ($B$=2).

###  4.6. Wealth Inequality

Figure 8. Relative wealth inequality after the redistribution step, in a
heterogeneous population dominated by cooperators and for different
combinations of taxation level ($\alpha$) and threshold ($\theta$). We
quantify the relative wealth inequality after the redistribution step as the
ratio between the variance of the fitness distribution ($Var_{f}$, i.e.
variance in gains across the population after redistribution) and the variance
of the accumulated payoff distribution ($Var_{p}$, i.e. variance in gains
before redistribution). Population size of $Z=10^{3}$ and intensity of
selection $\beta=1.0$.

Finally, we discuss the effect of wealth redistribution on fitness inequality.
First, it is important to highlight that the observed levels of inequality
depend, by default, on the distribution of strategies and network degree. In
homogeneous structures, if every agent adopts the same strategy – either
Defectors or Cooperators – everyone obtains the same fitness. In heterogeneous
structures, a Cooperation dominance scenario bounds the feasible equality
levels, given the degree distribution of the population. In fact, some agents
engage in more interactions than others and Beneficiary Sets have different
sizes, depending on the particular connectivity of agents. We shall focus on
this scenario.

We compare the variance of fitness (i.e. gains after the redistribution step)
and the variance of accumulated payoff (i.e. gains before the redistribution
step) in order to quantify the relative inequality after we apply the proposed
redistribution mechanism. In particular, we use the ratio between the variance
of fitness and the variance of accumulated payoff as a metric of resulting
wealth inequality.

Figure 8 shows how higher levels of $\theta$ and $\alpha$ reduce the resulting
inequality. In fact, while increasing payoff threshold limits taxation to the
richer agents, increasing level of taxation increases the flow of fitness from
rich agents to their Beneficiary Sets. In the most strict case – high $\theta$
and $\alpha$ – the variance of the fitness distribution is reduced to as low
as $7\%$ of the accumulated payoff distribution.

##  5\. Conclusion

To sum up, we show that wealth redistribution embodies an effective mechanism
that significantly helps cooperation to evolve. It works by fundamentally
changing the nature of the dilemma at stake: by appropriately choosing the
level of taxation ($\alpha$) and payoff threshold ($\theta$) it is possible to
shift from a Defector dominance to a Cooperator dominance dynamics. Moreover,
we find that in Heterogeneous populations allow us to ease the redistribution
mechanism – that is, imposing lower taxation rates and/or lower taxable
surplus values when compared with Homogeneously structured populations.

Additionally, we show, for the first time, that different assignments of
Beneficiary Sets significantly impact the ensuing levels of cooperation. Local
Beneficiary Sets, where agents receive the contributions from their direct
neighbors, constitute a judicious choice when compared with Beneficiary Sets
that are formed by 1) agents randomly picked from the population or 2) by
including agents at higher distances. Naturally, a Local wealth redistribution
scheme may not only prove optimal in terms of achieved cooperation levels, but
also reveal much simpler to implement, by exempting the need of central
redistribution entities and by minimizing the number of peers that agents need
to interact with. We shall highlight, however, that promoting cooperation
through a wealth redistribution mechanism bears longer fixation times, in
terms of the number of iterations required to achieve overall cooperation.

Here we assume that the redistribution mechanism is externally imposed. Agents
are not able to opt out from the taxation scheme. Given that this mechanism
increases the overall cooperation and average payoff in the system, an
argument for its acceptance - by rational agents - can be formulated based on
the infamous veil of ignorance proposed by John Rawls Rawls (2009): Agents
should decide the kind of society they would like to live in without knowing
their social position. Agents would, this way, prefer a cooperative society
where redistribution exists, provided that here average payoff is maximized.
Notwithstanding, future research shall analyze the role of more complex
strategies that give opportunity of agents to voluntarily engage (or not) in
the proposed redistribution scheme. Alongside, effective mechanisms that
discourage the second order free riding problem (i.e., free riding by not
contributing to the redistribution pot, while expecting others to do so) shall
be examined. Future works shall also evaluate whether alternative taxation
schemes are prone to be more efficient than the one proposed here. In all
these cases, an evolutionary game theoretic framework – such as the one here
developed – constitutes a promising toolkit to employ.

##  6\. Acknowledgments

The authors acknowledge the useful discussions with Francisco C. Santos, Jorge
M. Pacheco and Aamena Alshamsi. F.L.P. is thankful to the Media Lab Consortium
for financial support. F.P.S. acknowledges the financial support of Fundação
para a Ciência e Tecnologia (FCT) through PhD scholarship SFRH/BD/94736/2013,
multi-annual funding of INESC-ID (UID/CEC/50021/2013) and grants PTDC/EEI-
SII/5081/2014, PTDC/MAT/STA/3358/2014.

## References

  * (1)
  * Airiau et al. (2014) Stéphane Airiau, Sandip Sen, and Daniel Villatoro. 2014\.  Emergence of conventions through social learning.  _Autonomous Agents and Multi-Agent Systems_ 28, 5 (2014), 779–804.
  * Akyildiz et al. (2002) Ian F Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci. 2002.  Wireless sensor networks: a survey.  _Computer Networks_ 38, 4 (2002), 393–422.
  * Albert and Barabási (2002) Réka Albert and Albert-László Barabási. 2002\.  Statistical mechanics of complex networks.  _Reviews of Modern Physics_ 74, 1 (2002), 47\.
  * Arcos et al. (2005) Josep Ll Arcos, Marc Esteva, Pablo Noriega, Juan A Rodríguez-Aguilar, and Carles Sierra. 2005\.  Engineering open environments with electronic institutions.  _Engineering Applications of Artificial Intelligence_ 18, 2 (2005), 191–204.
  * Burguillo-Rial (2009) Juan C Burguillo-Rial. 2009\.  A memetic framework for describing and simulating spatial prisoner’s dilemma with coalition formation. In _Proceedings of AAAI’09_. AAAI Press, 441–448.
  * Endriss and Maudet (2003) Ulle Endriss and Nicolas Maudet. 2003.  Welfare engineering in multiagent systems. In _International Workshop on Engineering Societies in the Agents World_. Springer, 93–106.
  * Ephrati and Rosenschein (1996) Eithan Ephrati and Jeffrey S Rosenschein. 1996.  Deriving consensus in multiagent systems.  _Artificial Intelligence_ 87, 1-2 (1996), 21–74.
  * Esteva et al. (2004) Marc Esteva, Bruno Rosell, Juan A Rodriguez-Aguilar, and Josep Ll Arcos. 2004.  AMELI: An agent-based middleware for electronic institutions. In _Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems_. IEEE Computer Society, 236–243.
  * Feldman and Chuang (2005) Michal Feldman and John Chuang. 2005.  Overcoming free-riding behavior in peer-to-peer systems.  _ACM SIGecom Exchanges_ 5, 4 (2005), 41–50.
  * Genesereth et al. (1986) Michael R Genesereth, Matthew L Ginsberg, and Jeffrey S Rosenschein. 1986.  Cooperation without communication. In _Proceedings of AAAI’86_. AAAI Press.
  * Golle et al. (2001) Philippe Golle, Kevin Leyton-Brown, Ilya Mironov, and Mark Lillibridge. 2001.  Incentives for sharing in peer-to-peer networks.  In _Electronic Commerce_. Springer, 75–87.
  * Griffiths (2008) Nathan Griffiths. 2008\.  Tags and image scoring for robust cooperation. In _Proceedings of the 2008 International Conference on Autonomous Agents and Multi-agent Systems_. International Foundation for Autonomous Agents and Multiagent Systems, 575–582.
  * Hamilton (1964) William D Hamilton. 1964\.  The genetical evolution of social behaviour.  _Journal of Theoretical Biology_ 7, 1 (1964), 17–52.
  * Han (2016) TA Han. 2016.  Emergence of Social Punishment and Cooperation through Prior Commitments. In _Proceedings of AAAI’16_. AAAI Press, 2494–2500.
  * Han et al. (2017) TA Han, Luís Moniz Pereira, Luis A Martinez-Vaquero, and Tom Lenaerts. 2017.  Centralized vs. Personalized Commitments and their influence on Cooperation in Group Interactions. In _Proceedings of AAAI’17_. AAAI Press.
  * Ho et al. (2012) Chien-Ju Ho, Yu Zhang, Jennifer Vaughan, and Mihaela Van Der Schaar. 2012.  Towards social norm design for crowdsourcing markets. In _AAAI’12 Technical Report WS-12-08_. AAAI Press.
  * Hofmann et al. (2011) Lisa-Maria Hofmann, Nilanjan Chakraborty, and Katia Sycara. 2011.  The evolution of cooperation in self-interested agent societies: a critical study. In _Proceedings of the 2011 International Conference on Autonomous Agents and Multi-agent Systems_. International Foundation for Autonomous Agents and Multiagent Systems, 685–692.
  * Ichinose et al. (2017) Genki Ichinose, Yoshiki Satotani, and Hiroki Sayama. 2017\.  How mutation alters fitness of cooperation in networked evolutionary games.  _arXiv preprint arXiv:1706.03013_ (2017).
  * Jennings et al. (1998) Nicholas R Jennings, Katia Sycara, and Michael Wooldridge. 1998\.  A roadmap of agent research and development.  _Autonomous Agents and Multi-agent Systems_ 1, 1 (1998), 7–38.
  * Kurka and Pitt (2016) David Burth Kurka and Jeremy Pitt. 2016.  Distributed distributive justice. In _Self-Adaptive and Self-Organizing Systems (SASO), 2016 IEEE 10th International Conference on_. IEEE, 80–89.
  * Macy and Flache (2002) Michael W Macy and Andreas Flache. 2002.  Learning dynamics in social dilemmas.  _Proceedings of the National Academy of Sciences_ 99 (2002), 7229–7236.
  * Nowak (2006) Martin A Nowak. 2006\.  Five rules for the evolution of cooperation.  _Science_ 314, 5805 (2006), 1560–1563.
  * Nowak (2012) Martin A Nowak. 2012\.  Evolving cooperation.  _Journal of Theoretical Biology_ 299 (2012), 1–8.
  * Nowak and May (1992) Martin A Nowak and Robert M May. 1992.  Evolutionary games and spatial chaos.  _Nature_ 359, 6398 (1992), 826–829.
  * Nowak and Sigmund (2005) Martin A Nowak and Karl Sigmund. 2005.  Evolution of indirect reciprocity.  _Nature_ (2005).
  * Ohtsuki et al. (2006) Hisashi Ohtsuki, Christoph Hauert, Erez Lieberman, and Martin A Nowak. 2006.  A simple rule for the evolution of cooperation on graphs.  _Nature_ 441, 7092 (2006), 502.
  * Ostrom (2015) Elinor Ostrom. 2015\.  _Governing the commons_.  Cambridge University Press.
  * Panait and Luke (2005) Liviu Panait and Sean Luke. 2005.  Cooperative multi-agent learning: The state of the art.  _Autonomous Agents and Multi-agent Systems_ 11, 3 (2005), 387–434.
  * Peleteiro et al. (2014) Ana Peleteiro, Juan C Burguillo, and Siang Yew Chong. 2014\.  Exploring indirect reciprocity in complex networks using coalitions and rewiring. In _Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems_. International Foundation for Autonomous Agents and Multiagent Systems, 669–676.
  * Pinheiro and Hartmann (2017) Flávio L. Pinheiro and Dominik Hartmann. 2017.  Intermediate Levels of Network Heterogeneity Provide the Best Evolutionary Outcomes.  _Scientific Reports_ 7, 1 (2017), 15242.
  * Pinheiro et al. (2012) Flavio L Pinheiro, Jorge M Pacheco, and Francisco C Santos. 2012\.  From local to global dilemmas in social networks.  _PloS ONE_ 7, 2 (2012), e32114.
  * Pinheiro et al. (2016) Flávio L Pinheiro, Francisco C Santos, and Jorge M Pacheco. 2016.  Linking individual and collective behavior in adaptive social networks.  _Physical Review Letters_ 116, 12 (2016), 128702\.
  * Pitt et al. (2012) Jeremy Pitt, Julia Schaumeier, Didac Busquets, and Sam Macbeth. 2012.  Self-organising common-pool resource allocation and canons of distributive justice. In _Self-Adaptive and Self-Organizing Systems (SASO), 2012 IEEE Sixth International Conference on_. IEEE, 119–128.
  * Ranjbar-Sahraei et al. (2014) Bijan Ranjbar-Sahraei, Haitham Bou Ammar, Daan Bloembergen, Karl Tuyls, and Gerhard Weiss. 2014\.  Theory of cooperation in complex social networks. In _Proceedings of AAAI’14_. AAAI Press.
  * Rawls (2009) John Rawls. 2009\.  _A theory of justice_.  Harvard University Press.
  * Rendell et al. (2010) Luke Rendell, Robert Boyd, Daniel Cownden, Marquist Enquist, Kimmo Eriksson, Marc W Feldman, Laurel Fogarty, Stefano Ghirlanda, Timothy Lillicrap, and Kevin N Laland. 2010\.  Why copy others? Insights from the social learning strategies tournament.  _Science_ 328, 5975 (2010), 208–213.
  * Salazar et al. (2011) Norman Salazar, Juan A Rodriguez-Aguilar, Josep Ll Arcos, Ana Peleteiro, and Juan C Burguillo-Rial. 2011\.  Emerging cooperation on complex networks. In _Proceedings of the 2011 International Conference on Autonomous Agents and Multi-agent Systems_. International Foundation for Autonomous Agents and Multiagent Systems, 669–676.
  * Santos and Pacheco (2005) Francisco C Santos and Jorge M Pacheco. 2005.  Scale-free networks provide a unifying framework for the emergence of cooperation.  _Physical Review Letters_ 95, 9 (2005), 098104\.
  * Santos et al. (2006) Francisco C Santos, Jorge M Pacheco, and Tom Lenaerts. 2006\.  Cooperation prevails when individuals adjust their social ties.  _PLoS Computational Biology_ 2, 10 (2006), e140.
  * Santos et al. (2005) Francisco C Santos, JF Rodrigues, and Jorge M Pacheco. 2005\.  Epidemic spreading and cooperation dynamics on homogeneous small-world networks.  _Physical Review E_ 72, 5 (2005), 056128.
  * Santos et al. (2017) Fernando P Santos, Jorge M Pacheco, Ana Paiva, and Francisco C Santos. 2017.  Structural power and the evolution of collective fairness in social networks.  _PloS ONE_ 12, 4 (2017), e0175687.
  * Santos et al. (2018) Fernando P. Santos, Jorge M. Pacheco, and Francisco C. Santos. 2018.  Social norms of cooperation with costly reputation building. In _AAAI’18_. AAAI Press.
  * Seuken et al. (2010) Sven Seuken, Jie Tang, and David C Parkes. 2010.  Accounting Mechanisms for Distributed Work Systems. In _AAAI’10_. AAAI Press.
  * Sigmund (2010) Karl Sigmund. 2010\.  _The calculus of selfishness_.  Princeton University Press.
  * Trivers (1971) Robert L Trivers. 1971\.  The evolution of reciprocal altruism.  _The Quarterly Review of Biology_ 46, 1 (1971), 35–57.
  * Vasconcelos et al. (2015) Vítor V Vasconcelos, Francisco C Santos, and Jorge M Pacheco. 2015.  Cooperation dynamics of polycentric climate governance.  _Mathematical Models and Methods in Applied Sciences_ 25, 13 (2015), 2503–2517.
  * Waibel et al. (2011) Markus Waibel, Dario Floreano, and Laurent Keller. 2011\.  A quantitative test of Hamilton’s rule for the evolution of altruism.  _PLoS Biology_ 9, 5 (2011), e1000615.


# AVAC: A Machine Learning based Adaptive RRAM Variability-Aware Controller
for Edge Devices

Shikhar Tuli1 and Shreshth Tuli2  1Department of Electrical Engineering,
Indian Institute of Technology Delhi  2Department of Computer Science and
Engineering, Indian Institute of Technology Delhi  Email: {shikhartuli98,
<EMAIL_ADDRESS>
###### Abstract

Recently, the Edge Computing paradigm has gained significant popularity both
in industry and academia. Researchers now increasingly target to improve
performance and reduce energy consumption of such devices. Some recent efforts
focus on using emerging RRAM technologies for improving energy efficiency,
thanks to their no leakage property and high integration density. As the
complexity and dynamism of applications supported by such devices escalate, it
has become difficult to maintain ideal performance by static RRAM controllers.
Machine Learning provides a promising solution for this, and hence, this work
focuses on extending such controllers to allow dynamic parameter updates. In
this work we propose an Adaptive RRAM Variability-Aware Controller, AVAC,
which periodically updates Wait Buffer and batch sizes using on-the-fly
learning models and gradient ascent. AVAC allows Edge devices to adapt to
different applications and their stages, to improve computation performance
and reduce energy consumption. Simulations demonstrate that the proposed model
can provide up to 29% increase in performance and 19% decrease in energy,
compared to static controllers, using traces of real-life healthcare
applications on a Raspberry-Pi based Edge deployment.

##  I Introduction

With the rapid technology burst in the Internet of Things (IoT) domain, the
demands from Edge and Fog devices have been continuously increasing [1]. Edge
devices are becoming more complex, expected to do more-and-more computations
in order to reduce the data to be sent through the transceiver; thus reducing
the bandwidth requirement, latency and energy consumption. With the eventual
goal of a completely independent Edge node [2], designers are constantly
making energy specifications stricter for Edge devices [1]. Further, with CMOS
technology scaling to the deep sub-micron domain, the leakage power has become
comparable to the logic power consumption [3]. To alleviate this problem, it
is lucrative to enhance the performance of such devices and then expect them
to quickly switch to the idle deep-sleep mode [4].

In that context, emerging Resistive Random Access Memory (RRAM) technologies
serve as a good candidate as opposed to the traditional eFlash technologies,
thanks to their non-volatile operation, zero leakage, easy co-integration with
CMOS process, low programming voltage and fast switching [5, 6]. RRAMs find
applications in novel system designs with non-volatile cache and universal
memories [7, 8]. These new architectures can allow sufficient gains in
performance and energy, much needed for upcoming Edge/Fog devices.

One such architecture is the Static RRAM Variability-Aware Controller (RRAM-
VAC) proposed by S. Tuli et al. in [9]. To tackle the problem of high device-
to-device and cycle-to-cycle temporal variability in RRAMs (which can be up to
several decades [10]), the Static RRAM-VAC utilizes the recently proposed
Write Termination (WT) circuits [11]. Thanks to their capability of
dynamically detecting and stopping the programming operation once the device
has switched, the Static RRAM-VAC can coalesce multiple write operations
before triggering the write request. Thus, it can average out the temporal
write-time variability and effectively run the system at the memory
programming time distribution mean rather than the worst case tail. However,
with a fixed and rigid architecture, the Static RRAM-VAC is not robust and
adaptive enough to accommodate widely varied and unpredictable memory trace
patterns in developing complex Edge/Fog devices.

Hence, in this work we propose a Machine Learning (ML) based approach to
dynamically tune operation parameters so as to maximize performance and limit
energy requirement at all times of operation. For this, we characterize
different Wireless Body Sensor Node (WBSN) applications, a typical candidate
for large amount of critical data which needs to be processed timely, securely
and efficiently. We exploit a polynomial regression technique to model the
operation parameters, namely the Wait Buffer and batch sizes with the
performance and energy gains. We then apply gradient ascent method to maximize
the gains dynamically, thus providing up to 94% performance gains (up to 29%
more than the Static RRAM-VAC) and up to 99% energy gains (up to 19% more than
the Static RRAM-VAC) on traces of real-life healthcare applications, including
the HealthFog [12, 13] framework.

The rest of the paper is organized as follows. Section II presents the Static
RRAM-VAC operation and the Machine Learning technique used. Section III shows
the proposed AVAC architecture. Section IV describes the RRAM technology
assumptions and experimental setup used for simulations. Section V compares
the gains of the Adaptive over the Static RRAM-VAC. Finally, Section VI
concludes the paper.

##  II Background

###  II-A The Static RRAM-VAC

The Static RRAM Variability-Aware Controller (RRAM-VAC) proposed in [9] stores
the write requests and locks them to form a batch. This batch is then written
to an RRAM using the “Write Coalescing” method - as part of a single
operation, writing the next bit as-soon-as the previous one is finished [9].
This allows it to effectively interact with a synchronous processor and write
to the RRAM asynchronously, further enabling the system to run at the mean of
the switching-time distribution rather than at the worst-case tail.

Functionally, the Static RRAM-VAC uses a Wait Buffer and a Read Buffer. The
Wait Buffer is implemented as a Binary Content Addressable Memory (BCAM) [14]
of a fixed size. The locked batch is a part of the Wait Buffer and cannot
catch read requests. On the other hand, the rest of the Wait Buffer can still
catch both read and write requests. Read requests are first sent to the Wait
Buffer. If the corresponding address is not present in the Wait Buffer, the
request is issued to the RRAM. If a locked batch is in process, the read
request is stored in the Read Buffer where it waits until the RRAM is
available.

However, the given system has a fixed size of the Wait Buffer and batch,
optimally dependent on application patterns [9]. With the increasing
complexity of Edge/Fog workloads, there is a need to dynamically tune the Wait
Buffer and batch sizes in order to enhance energy and performance. Moreover,
these workloads correspond to real-life applications and continuously engage
with unpredictable service demands and tasks. This makes prediction of optimum
buffer and batch sizes difficult. Thus, in this work, we propose an on-the-fly
ML based approach of dynamically tuning these sizes in order to maintain the
best performance and energy characteristics.

Figure 1: Proposed Adaptive RRAM-VAC (AVAC) Block diagram

###  II-B Machine Learning models

The proposed AVAC model uses polynomial regression [15] and gradient ascent
[16]. The former provides a way to approximate a function with input as a
multidimensional vector, characteristic to the application and the current
Wait Buffer and batch sizes. We use this to approximate the expected
performance and energy gains and determine a cumulative reward as described in
Section III-C. We then use gradient ascent to iteratively update the Wait
Buffer and batch size pair, in order to optimize this reward function.

##  III Adaptive RRAM-VAC Architecture

This section gives a functional description of AVAC.

###  III-A Dynamic Buffer Size

Figure 1 presents a detailed block diagram of the proposed AVAC. As explained
in Section II-A, the controller fetches the read/write requests from the
processor and stores them to the Wait Buffer (for a write request) or the Read
Buffer (for a read request). The “locked” batches are written employing the
“Write Coalescing” technique. However, in this architecture, the Wait Buffer
is larger in size and we can dynamically switch off certain Write-Lines based
on the requirement. This allows us to change the effective Wait Buffer size
that is being used at any given time. The power-gating reduces leakage in
applications where a large size is not needed, since it shuts off the current
to these cells. On the other hand, for applications with very low data
locality, we can optimize performance by increasing the Wait Buffer size,
since that would better average the variability in write times.

Further, the whole Wait Buffer can be connected to the RRAM block via a wide
bus. We can dynamically tune the batch size by varying the number of words
written at a time. Higher variability ($\sigma$) of the distribution requires
a larger batch size. Moreover, the optimum batch size also depends on the Wait
Buffer size [9].

###  III-B Feature Extraction

The optimum Wait Buffer and batch sizes and the possible performance and
energy gains are dependent on the memory-trace features, as introduced in
Section II-A. These features represent the application memory access patterns.
They are extracted in the AVAC by the “Feature Extractor” as shown in Figure
1. The set of all the 8 features, with the current Wait Buffer size ($W$) and
batch size ($B$) forms a 10 dimensional feature vector. The 8 features
extracted are as follows:

  1. 1.

Read/Write ratio: Large number of reads requires a small batch size, so that
read requests do not have to wait for a long time for the batch to flush out
to the RRAM. If the read locality is high, then a small Wait Buffer can also
lead to performance gains (reading from the Wait Buffer is less expensive than
from the RRAM block).

  2. 2.

Read locality: As explained above, high read locality would benefit from a
small Wait Buffer. If the locality is low, the application would demand a
larger Wait Buffer.

  3. 3.

Write locality: Again, high write locality would benefit from a small Wait
Buffer just as the reads above.

  4. 4.

Mean Read burst size: For a series of small read bursts, the Wait Buffer will
have to wait frequently for the Read Buffer to clear out, thus not allowing it
to flush out its write requests so as to catch the next write instruction.

  5. 5.

Mean Write burst size: While the batch is being written to memory, the next
read request that cannot be processed inside the Wait Buffer is stored in the
Read Buffer and the processor is stalled, compromising performance.

  6. 6.

Mean Read repetition: The read locality only targets the variance in the read
request addresses. The peak of the distribution can be represented by the mean
of the repetition for each read address.

  7. 7.

Mean Write repetition: Similar to the case of read repetition, higher write
repetition would result in higher energy gains by accesses from the Wait
Buffer.

  8. 8.

Variation in bit-changes for writes: By this feature, we mean the number of
changes in bit written to a particular address (0 to 1 or 1 to 0). The Write
Coalescing strategy works best if the variability in writes can be averaged
out. However, for example, if the writes to addresses are of the form
0x00000000 to 0x0000000F, then the LSB will always have higher write times
than the other bits, thus reducing the gains of a higher batch size.

###  III-C Polynomial model and parameter optimization

The complete feature vector, calculated for a fixed number of memory accesses
in 10 dimensions, is given to two polynomial-fit based models: Performance
Gains (PG) and Energy Gains (EG). We empirically find 1000 to be the best
interval size ($S_{I}$), and propose to test with other and dynamic $S_{I}$
values as part of future work. Each model is an approximator that maps the 10
dimensional feature vector ($fv$) to the corresponding performance and energy
gains ($pg$ and $eg$). At training time, we generate multiple data-points
{$fv^{(j)}$, $pg^{(j)}$, $eg^{(j)}$}${}_{j=1}^{N}$ for different applications
with buffer size $\in[1,120]$ and batch size $\in[1,80]$. This training data
is then used to perform polynomial regression and generate model parameters
for PG and EG. The applications were chosen to cover a large space of feature
vectors.

Figure 2: Performance gains (a) actual, and model with degree - (b) 3 and
(c) 5. Energy gains (d) actual, and model with degree - (e) 3 and (f) 5.

At testing time, for every memory trace of last 1000 accesses at time $t_{i}$,
the trace feature vector is coupled with the current (at time $t_{i}$) buffer
size ($W_{i}$) and batch size ($B_{i}$) to form a vector of size 10 which is
sent to the two polynomial models that output $pg_{i}$ and $eg_{i}$. These are
then used to calculate the reward ($r_{i}$) as convex combination $\alpha\cdot
pg_{i}+\beta\cdot eg_{i}$ where the weights $\alpha$ and $\beta$
($\alpha+\beta=1$) can be changed based on user requirements targeting either
optimal performance or energy (experiments in this work use $\alpha$ = 0.1 and
$\beta$ = 0.9 to prioritize energy reduction). This whole pipeline is run
multiple times by changing buffer and batch sizes to achieve maximum reward
using gradient ascent. For the current model, we used learning rate as 0.01
with 0.9 momentum. This gives the ($W_{i+1}$,$B_{i+1}$) tuple which maximizes
the reward (keeping area minimum) and is used for the next interval till
$t_{i+1}$. Figure 2 shows actual performance and energy gains with polynomial
models of degree 3 and 5. With higher degree, outputs are closer to actual
values but require more model parameters (AVAC uses degree 5 models). Finally,
the Wait Buffer and batch sizes were fixed to 80 and 10 respectively for the
Static RRAM-VAC [9].

##  IV Experimental Setup

This section discusses the basic setup, energy and speed assumptions, with
biomedical applications and generic benchmarks. The simulations were performed
on MATLAB.

###  IV-A Energy and Speed Assumptions

For a programming voltage of 1V to 1.5V, programming time of a few tens of
nano-seconds can be achieved [5]. Hence, we have assumed a 50 ns worst-case
programming time at a programming voltage of 1V. 100 $\mu$A programming
current has been assumed for a high ratio of resistance between the High
Resistance State (HRS) and the Low Resistance State (LRS) and for several
years of memory lifetime [5]. We take a normal distribution of programming
time with the mean ($\mu$) at 25 ns and a variance ($\sigma$) of 5 ns [9]. The
AVAC model can be further extended to account for ageing and corresponding
variation in the distribution. As explained in [9], energy characterization is
done for every bit as an integral ($V\int{I\cdot dt}$) taking into account the
shift in the current ($I$) for every stochastic transition (HRS to LRS or
vice-versa). WT circuit switching detection time is taken to be 1 ns [9]. The
read energy is considered as 1 pJ per bit [17]. Scaling down CMOS technology
has led to increase in leakage power, primary concern in low-power circuits.
The leakage current (for 1V programming voltage) can go as high as 15nA per
bit cell (and even higher in some cases) in the current deep-submicron nodes
[18]. This leads to a leakage gain of 480nW per word-line of 32 bits
(switching them off dynamically when not needed) in the proposed approach.
Implementation of AVAC models described in Sections III-B and III-C on Artix-7
FPGA shows that it has 0.278% energy overhead compared to a 4GB RRAM, which is
negligible [19].

###  IV-B Applications and Benchmarks

Experiments were performed on different applications relevant to Edge devices
in the biomedical domain. These include Compressed Sensing (CS) for an
Electro-Cardiogram (ECG) signal, Feature Extraction (FE) and Decision Tree
(DT) in Epilepsy seizure detection algorithm, with Matrix Multiplication (MM)
and Convolution (Conv) as two kernels [20, 21] as used in [9]. DT_C is the DT
application post-processed with an L1 cache of 16 words. We also use Sysbench
CPU [22] and Apache [23] to further increase the diversity of applications.
All benchmarks traces were extracted on Raspberry-Pi 4 and used to fit the
polynomial models PG and EG.

##  V Experimental results

Figure 3: Energy and Performance comparison for different applications

Figure 3 compares the energy and performance gains for the Static and the
Adaptive RRAM-VAC with the reference case not using the RRAM-VAC. These gains
can be explained by comparing the model parameter optima, i.e the optimal
values of the tuple ($W$, $B$) for different applications, with that of the
Static RRAM-VAC - (80, 10). For the applications CS and FE, the parameter
optima ((80, 60) and (70, 50) respectively) were quite close to that of the
Static RRAM-VAC, giving only about 2% more gains in energy compared to the
Static case. The CS and FE have low locality of addresses, and a low
read/write ratio. Since the parameters for Static RRAM-VAC were decided based
on writes to random addresses [9] (implying a low locality and zero read/write
ratio) these memory traces are quite close to the assumed one in the Static
RRAM-VAC. Still, CS gains a little in performance owing to a larger batch size
(averaging the variability in write times). However, MM and Conv show little
dependence of the parameters on the gains, with their respective optima at
(10, 10) and (80, 80). This is due to the fact that both have balanced
read/write ratios. In MM, AVAC reduces leakage power by reducing the Wait
Buffer size as locality is low, since a larger Wait Buffer does not provide
significant advantage. On the other hand, Conv has high gains both in the
Static and Adaptive RRAM-VAC and benefits from a large Wait Buffer to reduce
energy of read and write accesses.

AVAC provides high gains in DT, DT_C and FE+DT, with their respective model
optima at - (30,30), (60,60) and (50,50). DT shows maximum improvement in
energy gains- 89% higher than the Static case. With otherwise low locality but
high address repetition, these applications perform better with a smaller Wait
Buffer. This can be explained by high read/write burst size and high address
repetition. Sysbench shows high gains with the model optimum at (30,30) due to
high read/write locality. On the other hand, Apache has similar optimum at
(70,50) as the Static case, due to low read/write locality. Both benefit with
a larger batch size, providing 3% higher performance gains compared to the
Static case.

Figure 4: Transient simulations for Static and Adaptive RRAM-VAC for HealthFog
application (a) Performance Gains and (b) Energy Gains

To demonstrate efficacy of AVAC, we further show the performance and energy
gains for a real-life Edge application called HealthFog [12] which provides
high accuracy healthcare services using ensemble deep learning. Figure 4 shows
the application running in 3 major stages: (T1) the program performs large
number of ECG read operations and shares data in real-time with sensors and
actuators; (T2) the program performs task scheduling and migration decisions
for minimum service-level-agreement violations [2]; (T3) the program utilizes
ensemble deep learning based methods to evaluate the data and generate results
like health analysis and automated prescription generation. Gains in static
and adaptive cases are same in T1 due to only-read operations. T2 has large
number of convolution operations giving high energy gains in both the Static
and Adaptive cases, compared to the reference. Further, T3 has many MM-like
operations and also bootstrapping processes similar to those in the DT,
leading to higher gains (29% performance and 19% energy). Also, Figure 4
highlights how the proposed ML-based model can adapt to shifts in memory
access patters to instantly enhance gains.

##  VI Conclusions

In this work, we proposed the Adaptive RRAM Variability-Aware Controller
(AVAC), which uses Machine Learning (ML) techniques to dynamically configure
the Wait Buffer and the batch sizes. This not only mitigates the device-to-
device variability in RRAMs, but also further optimizes performance and energy
dependent on the memory access patters. Gains were simulated for different
applications in the Edge/Fog environment, and compared to the Static RRAM-VAC
with fixed Wait Buffer and batch sizes. With the considered RRAM technology,
AVAC provides up to 94% gains in performance (up to 29% more than the Static
case) and up to 99% gains in energy (up to 19% higher than the Static case).
The model can dynamically tune operation parameters in complex and varied Edge
and Fog applications to maintain the best performance and energy at all times.
Other ML models, with dynamic interval sizing can be investigated as part of
future work.

## References

  * [1] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: Vision and challenges,” _IEEE Internet of Things Journal_ , vol. 3, no. 5, pp. 637–646, 2016.
  * [2] S. S. Gill, S. Tuli, M. Xu, I. Singh, K. V. Singh, D. Lindsay, S. Tuli, D. Smirnova, M. Singh, U. Jain, H. Pervaiz, B. Sehgal, S. S. Kaila, S. Misra, M. S. Aslanpour, H. Mehta, V. Stankovski, and P. Garraghan, “Transformative effects of IoT, Blockchain and Artificial Intelligence on Cloud Computing: Evolution, vision, trends and open challenges,” _Internet of Things_ , vol. 8, p. 100118, 2019.
  * [3] International Technology Roadmap for Semiconductors by Semiconductor Industry Association, 2011. [Online]. Available: http://www.itrs2.net/2011-itrs.html
  * [4] R. Braojos, D. Atienza, M. M. S. Aly, T. F. Wu, H.-S. P. Wong, S. Mitra, and G. Ansaloni, “Nano-engineered architectures for ultra-low power wireless body sensor nodes,” in _Proceedings of the Eleventh IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis_ , ser. CODES ’16. New York, NY, USA: ACM, 2016, pp. 23:1–23:10.
  * [5] E. Vianello, O. Thomas, M. Harrand, S. Onkaraiah, T. Cabout, B. Traoré, T. Diokh, H. Oucheikh, L. Perniola, G. Molas, P. Blaise, J. F. Nodin, E. Jalaguier, and B. De Salvo, “Back-end 3D integration of HfO2-based RRAMs for low-voltage advanced IC digital design,” in _Proceedings of 2013 International Conference on IC Design Technology (ICICDT)_ , May 2013, pp. 235–238.
  * [6] H.-S. P. Wong, H. Lee, S. Yu, Y. Chen, Y. Wu, P. Chen, B. Lee, F. T. Chen, and M. Tsai, “Metal–Oxide RRAM,” _Proceedings of the IEEE_ , vol. 100, no. 6, pp. 1951–1970, June 2012.
  * [7] S. Senni, L. Torres, G. Sassatelli, A. Gamatie, and B. Mussard, “Emerging Non-volatile Memory Technologies Exploration Flow for Processor Architecture,” in _2015 IEEE Computer Society Annual Symposium on VLSI_ , July 2015, pp. 460–460.
  * [8] W. Zhao, L. Torres, L. V. Cargnini, R. M. Brum, Y. Zhang, Y. Guillemenet, G. Sassatelli, Y. Lakys, J.-O. Klein, D. Etiemble, D. Ravelosona, and C. Chappert, “High Performance SoC Design Using Magnetic Logic and Memory,” in _VLSI-SoC: Advanced Research for Systems on Chip_ , S. Mir, C.-Y. Tsui, R. Reis, and O. C. S. Choy, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 10–33.
  * [9] S. Tuli, M. A. Rios, A. S. J. Levisse, and D. Atienza Alonso, “RRAM-VAC: A Variability-Aware Controller for RRAM-based Memory Architectures,” _Proceedings of the 25th Asia and South Pacific Design Automation Conference ASP-DAC_ , 2020.
  * [10] G. Sassine, C. Nail, L. Tillie, D. A. Robayo, A. Levisse, C. Cagli, K. E. Hajjam, J. Nodin, E. Vianello, M. Bernard, G. Molas, and E. Nowak, “Sub-pJ consumption and short latency time in RRAM arrays for high endurance applications,” in _2018 IEEE International Reliability Physics Symposium (IRPS)_ , March 2018, pp. P–MY.2–1–P–MY.2–5.
  * [11] M. Alayan, E. Muhr, A. Levisse, M. Bocquet, M. Moreau, E. Nowak, G. Molas, E. Vianello, and J. M. Portal, “Switching Event Detection and Self-Termination Programming Circuit for Energy Efficient ReRAM Memory Arrays,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 66, no. 5, pp. 748–752, May 2019.
  * [12] S. Tuli, N. Basumatary, S. S. Gill, M. Kahani, R. C. Arya, G. S. Wander, and R. Buyya, “HealthFog: An Ensemble Deep Learning based Smart Healthcare System for Automatic Diagnosis of Heart Diseases in Integrated IoT and Fog Computing Environments,” _Future Generation Computer Systems_ , 2019.
  * [13] S. Tuli, R. Mahmud, S. Tuli, and R. Buyya, “FogBus: A Blockchain-based Lightweight Framework for Edge and Fog Computing,” _Journal of Systems and Software_ , vol. 154, pp. 22 – 36, 2019.
  * [14] A. Agarwal, S. Hsu, S. Mathew, M. Anders, H. Kaul, F. Sheikh, and R. Krishnamurthy, “A 128x128b high-speed wide-and match-line content addressable memory in 32nm CMOS,” in _2011 Proceedings of the ESSCIRC (ESSCIRC)_ , Sep. 2011, pp. 83–86.
  * [15] D. C. Montgomery, E. A. Peck, and G. G. Vining, _Introduction to linear regression analysis_. John Wiley & Sons, 2012, vol. 821.
  * [16] S. Bubeck _et al._ , “Convex optimization: Algorithms and complexity,” _Foundations and Trends® in Machine Learning_ , vol. 8, no. 3-4, pp. 231–357, 2015.
  * [17] P. Jain, U. Arslan, M. Sekhar, B. C. Lin, L. Wei, T. Sahu, J. Alzate-vinasco, A. Vangapaty, M. Meterelliyoz, N. Strutt, A. B. Chen, P. Hentges, P. A. Quintero, C. Connor, O. Golonzka, K. Fischer, and F. Hamzaoglu, “13.2 A 3.6Mb 10.1Mb/mm2 Embedded Non-Volatile ReRAM Macro in 22nm FinFET Technology with Adaptive Forming/Set/Reset Schemes Yielding Down to 0.5V with Sensing Time of 5ns at 0.7V,” in _2019 IEEE International Solid- State Circuits Conference - (ISSCC)_ , Feb 2019, pp. 212–214.
  * [18] D. Bhattacharya, A. N. Bhoj, and N. K. Jha, “Design of Efficient Content Addressable Memories in High-Performance FinFET Technology,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 23, no. 5, pp. 963–967, May 2015.
  * [19] Y. Liu, Z. Wang, A. Lee, F. Su, C. Lo, Z. Yuan, C. Lin, Q. Wei, Y. Wang, Y. King, C. Lin, P. Khalili, K. Wang, M. Chang, and H. Yang, “4.7 A 65nm ReRAM-enabled nonvolatile processor with 6× reduction in restore time and 4× higher clock frequency using adaptive data retention and self-write-termination nonvolatile logic,” in _2016 IEEE International Solid-State Circuits Conference (ISSCC)_ , Jan 2016, pp. 84–86.
  * [20] A. Vasudevan, A. Anderson, and D. Gregg, “Parallel Multi Channel convolution using General Matrix Multiplication,” in _2017 IEEE 28th International Conference on Application-specific Systems, Architectures and Processors (ASAP)_ , July 2017, pp. 19–24.
  * [21] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “ImageNet Classification with Deep Convolutional Neural Networks,” in _Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 1_ , ser. NIPS’12. USA: Curran Associates Inc., 2012, pp. 1097–1105.
  * [22] A. Kopytov. (2004) SysBench: a system performance benchmark. [Online]. Available: http://sysbench. sourceforge. net/
  * [23] Apache HTTP server benchmarking tool. [Online]. Available: https://httpd.apache.org/docs/2.4/programs/ab.html