# Winning the Social Media Influence Battle: Uncertainty-Aware Opinions to
Understand and Spread True Information via Competitive Influence Maximization

Qi Zhang  Department of Computer Science
Virginia Tech
Falls Church VA, USA
<EMAIL_ADDRESS>Lance M. Kaplan  US DEVCOM Army Research Laboratory
Adelphi MD, USA
<EMAIL_ADDRESS>Audun Jøsang  Department of Informatics
University of Oslo
Oslo, Norway
<EMAIL_ADDRESS>Dong Hyun Jeong  Department of Computer Science
University of the District of Columbia
Washington DC, USA
<EMAIL_ADDRESS>Feng Chen  Department of Computer Science
University of Texas at Dallas
Richardson TX, USA
<EMAIL_ADDRESS>Jin-Hee Cho  Department of Computer Science
Virginia Tech
Falls Church VA, USA
<EMAIL_ADDRESS>
###### Abstract

Competitive Influence Maximization (CIM) involves entities competing to
maximize influence in online social networks (OSNs). Current Deep
Reinforcement Learning (DRL) methods in CIM rely on simplistic binary opinion
models (i.e., an opinion is represented by either 0 or 1) and often overlook
the complexity of users’ behavioral characteristics and their prior knowledge.
We propose a novel DRL-based framework that enhances CIM analysis by
integrating Subjective Logic (SL) to accommodate uncertain opinions, users’
behaviors, and their preferences. This approach targets the mitigation of
false information by effectively propagating true information. By modeling two
competitive agents, one spreading true information and the other spreading
false information, we capture the strategic interplay essential to CIM. Our
framework utilizes an uncertainty-based opinion model (UOM) to assess the
impact on information quality in OSNs, emphasizing the importance of user
behavior alongside network topology in selecting influential seed nodes.
Extensive experiments demonstrate that our approach significantly outperforms
state-of-the-art methods, achieving faster and more influential results (i.e.,
outperforming over 20%) under realistic network conditions. Moreover, our
method shows robust performance in partially observable networks, effectively
doubling the performance when users are predisposed to disbelieve true
information.

###### Index Terms:

Competitive influence maximization, deep reinforcement learning, uncertainty,
opinion models, influence propagation

##  I Introduction

Online Social Networks (OSNs) are primary platforms for information exchange
and opinion formation. In situations where exclusive decisions are required,
such as service selection or voting, a competitive environment arises. This
sets the stage for a Competitive Influence Maximization (CIM) problem, where
political parties and corporations vie to sway these decisions. CIM involves
these entities strategically selecting key individuals, called seed nodes in a
network, within the network to act as opinion leaders and maximize the spread
of their influence throughout the network. This study tackles the CIM problem
in OSNs, focusing on two opposing parties: the true party disseminating true
information and the false party spreading false information.

Our work explores strategies for the true party to effectively counteract the
false party and curb the spread of false information, given its harmful
consequences, such as damaged reputations, financial losses, and manipulated
public opinion [9]. The aim is to enhance the propagation of true information
and mitigate the negative impacts of false information in the OSN.

Prior studies on CIM in OSNs [4, 6, 17, 22] typically represented user
opinions as fixed and binary, ignoring the complex, dynamic nature of
individual preferences and behaviors. They mainly leveraged the Linear
Threshold (LT) model and relied heavily on network topology, resulting in
inconsistent effectiveness across different network topologies [17]. This
explains the need for adaptable strategies to varying network structures and
evolving competitive dynamics. Reinforcement Learning (RL) emerges as a viable
approach, facilitating real-time data gathering and strategy optimization to
address the intricate requirements of CIM tasks.

We present a Deep RL (DRL)-based CIM framework to enhance the dissemination of
accurate information and counter false information. We aim to identify an
optimal set of seed users to maximize information spread, acknowledging that
user opinions are not simply binary but are formed and evolve over time. To
this end, we made the following key contribution in our work:

  1. 1.

Refining CIM Analysis with Uncertain Opinions in OSNs: Traditional CIM
research often reduces user opinions to binary states, inadequately reflecting
the dynamic shifts in user opinions within OSNs [2, 3, 6, 17]. We incorporate
Subjective Logic (SL) [10] into our CIM framework to accurately model the
uncertain and subjective nature of user beliefs. This approach provides a
deeper understanding of opinion evolution in OSNs, enhancing CIM analysis.

  2. 2.

Enhancing CIM with Dual DRL Agents: Previous CIM research utilizing DRL often
focused on a single influence strategy and simplified user opinions to binary
states, missing real-world complexities [6, 15, 17]. We present a dual-agent
DRL framework that models the dissemination of both true and false
information. This approach considers network structures and user behaviors,
providing a comprehensive method for selecting influential seed nodes and
deepening the strategic dynamics within CIM.

  3. 3.

Evaluating UOM’s Impact on OSN Information Quality: We explore the
effectiveness of the Uncertainty-aware Opinion Model (UOM) in enhancing
information quality within OSNs. Our findings reveal that UOM captures the
dynamics of false information, which often dominates before the truth emerges,
posing challenges in correcting established misconceptions. Implementing UOM
improved user engagement with content critically, reducing the spread and
impact of false information. Further, these results affirm the UOM’s potential
to enhance information veracity in OSNs.

  4. 4.

Exploring CIM Performance under Partial Observability with UOM: While the
impact of partially observable networks (PONs) on CIM has been recognized [18,
21], the influence of non-binary opinions modeled by specific opinion
frameworks like UOM on CIM’s observability remains underexplored. Our work
aims to delve into how partial observability impacts CIM performance using the
UOM framework with non-binary opinion models.

  5. 5.

Identifying Traits for Influential Seed Node Selection: Through simulations of
various scenarios with two parties employing different strategies, we identify
critical user behavioral traits and network characteristics that optimally
indicate influential seed nodes.

We specifically use the term false information instead of misinformation or
disinformation to maintain clarity. Misinformation refers to inaccurately
shared information without intent to deceive, stemming from misunderstanding
or ignorance. In contrast, disinformation is deliberately spread to mislead
others, characterized by malicious intent. The nuanced differences between
misinformation and disinformation, along with their separate impacts, fall
outside the purview of our research focus.

##  II Related Work

The Influence Maximization (IM) problem, initially conceptualized in Domingos
and Richardson [7] as an algorithmic challenge, involves maximizing influence
across OSNs by selecting optimal seed sets. Kempe et al. [13] further refined
it into a discrete stochastic optimization problem, enhancing its theoretical
framework. CIM extends the IM problem, featuring multiple entities competing
to maximize their influence, with various methodologies demonstrating
effectiveness in addressing CIM challenges.

###  II-A Propagation Models

Propagation models like Independent Cascade (IC) [14] and Linear Threshold
(LT) [8] are established frameworks for analyzing network influence [4, 20,
19, 22]. The IC model activates a node and attempts independent influence on
its neighbors, whereas the LT model activates a node if the cumulative
influence from neighbors surpasses a preset threshold.

Despite their wide acceptance, both models are limited in real-world scenarios
due to static probabilities and thresholds, which overlook individual response
variations to information. Our study enhances these models by integrating
diverse opinion dynamics, particularly evaluating their effectiveness against
the spread of false information.

###  II-B DRL-based CIM

Lin et al. [17] introduced STORM, a STrategy-Oriented ReinforceMent-Learning-
based framework for multi-round CIM within the competitive LT model [25],
marking the first use of RL in CIM. STORM employed RL to dynamically select IM
strategies based on evolving user opinions and competitor actions. Building on
this, Chung [6] developed a DRL-based CIM framework, enhancing strategic seed
selection across multiple rounds using Deep-Q Learning (DQN) and a spectral
community detection method to optimize seed choices and improve influence
spread. Furthermore, Ali et al. [2] extended DRL applications to CIM in
unknown network topologies, adapting STORM’s reward and action spaces with
additional network exploration actions.

However, the prior work in [6, 17] often assumed complete knowledge of network
topology, an unrealistic scenario in practical applications. Moreover, DRL
approaches in [2, 3] simplified opinion evolution with binary models. Our work
addresses these limitations by integrating detailed opinion dynamics and
accounting for uncertainties in opinions and network structure, thus
developing a more realistic CIM framework.

##  III Problem Statement

An OSN is modeled as an unweighted, undirected graph $G=(V,E)$, with $V$ as
users and $E$ as relationships. Within $G$, two parties, $\mathcal{T}$ for
true information and $\mathcal{F}$ for false information, aim to maximize
their influence. Their central decision makers (CDMs) select seed users
$\mathbf{S}^{\mathcal{T}}$ and $\mathbf{S}^{\mathcal{F}}$ to spread their
respective information types. DRL is employed to strategically select action
$\bm{A}$ to select seed nodes for maximizing influence. Each party’s node
selection process will follow the procedures and opinion models described in
Section IV.

To formally put, each party’s CDM seeks to optimize the objective of
maximizing their influence by:

$\displaystyle\arg\max_{\bm{S},\bm{A}}\;\;\mathcal{IF}(G,\bm{S},{\bm{uc}}),$
(1)

where ${\bm{uc}}$ represents the characteristics of users, detailed in Section
IV-C.

##  IV Proposed CIM Framework

###  IV-A SL-based Opinion Formulation

In an OSN, users adopt opinions modeled by Subjective Logic (SL),
accommodating multidimensional uncertainties [10, 11]. SL articulates a
binomial opinion $\omega=(b,d,u,a)$, incorporating belief ($b$), disbelief
($d$), uncertainty ($u$), and base rate ($a$), where $b+d+u=1$ and each
element is ranged within $[0,1]$ as a real number. Here, $b$ reflects
agreement with true information, $d$ captures disagreement with false
information (or disbelieving true information), $u$ represents uncertainty due
to insufficient evidence, and $a$ (and $1-a$) indicates the prior belief
favoring true information (i.e., belief) or false information (i.e.,
disbelief). A user’s opinion update adjusts these elements based on evidence
for or against belief and disbelief. An opinion $\omega$ is formulated by:

$\displaystyle
b=\frac{r}{r+s+W}~{},d=\frac{s}{r+s+W}~{},u=\frac{W}{r+s+W}~{},$ (2)

where $r$ and $s$ are the numbers of evidence to support $b$ and $d$,
respectively, and $W$ refers to the number of uncertain evidence that cannot
be judged as true or false, supporting neither $b$ nor $d$.

We denote user $i$’s opinion by $\omega_{i}=(b_{i},d_{i},u_{i},\bm{a}_{i})$.
Since users make decisions from the two choices, $b_{i}$ or $d_{i}$, they
interpret uncertainty based on their prior belief,
$\bm{a}_{i}=\\{a_{i},1-a_{i}\\}$ to support $b_{i}$ and $d_{i}$, respectively,
and $a_{i}+(1-a_{i})=1$. Users incorporate the projected belief or disbelief
and uncertainty to make decisions in practice. The projected belief $P(b_{i})$
and disbelief $P(d_{i})$ are obtained by:

$\displaystyle P(b_{i})=b_{i}+a_{i}\times
u_{i},\;P(d_{i})=d_{i}+(1-a_{i})\times u_{i},$ (3)

where $P(b_{i})+P(d_{i})=1$ and $a_{i}u_{i}+(1-a_{i})u_{i}=u_{i}$ with
$b_{i}+d_{i}+u_{i}=1$.

We consider two types of uncertainty in user $i$’s opinion [11]: vacuity and
dissonance. Vacuity refers to uncertainty caused by a lack of evidence.
Dissonance indicates uncertainty due to conflicting evidence. Vacuity
uncertainty mass in user $i$’s opinion, $\omega_{i}$, is measured by $u_{i}$.
Dissonance uncertainty mass is defined as:

$\displaystyle\bm{b}_{i}^{\mathrm{Diss}}={(b_{i}+d_{i})\cdot\mbox{Bal}(b_{i},d_{i})},$
(4)

where $\bm{b}_{i}(x)=\\{b_{i},d_{i}\\}$ and the relative mass balance between
belief masses, $b_{i}$ and $d_{i}$, is given by:

$\mbox{Bal}(b_{i},d_{i})=1-\frac{|b_{i}-d_{i}|}{b_{i}+d_{i}}.$ (5)

We incorporated uncertainty estimates, such as vacuity and dissonance, to
develop a UOM in Section IV-C.

###  IV-B User Types

We consider three types of users as follows:

  * •

True information propagators (TIPs) have their opinion initialized by
$\omega_{T}=(b,d,u,a)=(b\rightarrow 1,d\rightarrow 0,u\rightarrow 0,a=1)$.
This opinion implies TIPs have a strong belief in true information ($b$ is
close to 1), while they lack belief in false information ($d$ is close to 0).
TIPs selected as seed nodes will not change their opinions.

  * •

False information propagators (FIPs) have their opinion, initialized by
$\omega_{F}=(b,d,u,a)=(b\rightarrow 0,d\rightarrow 1,u\rightarrow 0,a=0)$.
This means FIPs have a strong belief in false information ($d$ is close to 1)
while having a lack of belief in true information ($b$ is close to 0). FIPs
selected as seed nodes will not change their opinions.

  * •

Legitimate users have a highly uncertain opinion, initialized by
$\omega_{L}=(b,d,u,a)=(b\rightarrow 0,d\rightarrow 0,u\rightarrow
1,{\bm{a}})$. The users’ prior beliefs are initialized based on uniform
distribution with $a_{i}=1-a_{i}=0.5$ and will be updated based on the
consensus operation in Eq. (8).

###  IV-C Opinion Models

Each user $i$’s behavior is characterized by the following main components:
opinion updating, sharing, and reading, denoted by a set of user behaviors,
$\bm{uc}_{i}$. In our objective function, described in Eq. (1), $\bm{uc}$
refers to a set of users about these behavioral components. To formally put,
$\bm{uc}$ is defined by:

$\displaystyle\bm{uc}=\\{\bm{uc}_{1},\ldots,\bm{uc}_{i},\ldots,\bm{uc}_{n}\\},$
(6)

where
$\bm{uc}_{i}=\\{\mathrm{updating}_{i},\mathrm{reading}_{i},\mathrm{sharing}_{i}\\}$.
Details about each behavioral component are shown below.

####  IV-C1 Opinion Updating

Recall that we choose SL as it offers the ability to formulate a subjective
opinion that can handle multiple types of uncertainty caused by different
causes (i.e., vacuity or dissonance). At time $t$, when user $i$ encounters
user $j$ and reads user $j$’s information (i.e., $\omega_{j}(t)$), user $i$
will update the opinion as $\omega_{i}\oplus\omega_{i\otimes j}=(b_{i}\oplus
b_{i\otimes j},d_{i}\oplus d_{i\otimes j},u_{i}\oplus u_{i\otimes
j},a_{i}\oplus a_{i\otimes j})$, and $\omega_{i\otimes j}$ indicates user
$j$’s opinion based on user $i$’s trust in user $j$. The $\omega_{i\otimes
j}=(b_{i\otimes j},d_{i\otimes j},u_{i\otimes j},a_{i\otimes j})$ is obtained
where each component of the opinion is estimated by:

$\displaystyle b_{i\otimes j}=c_{i}^{j}b_{j},~{}d_{i\otimes
j}=c_{i}^{j}d_{j},~{}$ (7) $\displaystyle u_{i\otimes
j}=1-c_{i}^{j}(1-u_{j}),~{}a_{i\otimes j}=a_{j},$

where $c_{i}^{j}$ is a discounting operator decided by different opinion
models (detailed below), representing user $i$’s trust in user $j$. Finally,
$\omega_{i}\oplus\omega_{i\otimes j}$ is obtained by:

$\displaystyle b_{i}\oplus b_{i\otimes
j}=\frac{b_{i}(1-c_{i}^{j}(1-u_{j}))+c_{i}^{j}b_{j}u_{i}}{\beta}~{},$ (8)
$\displaystyle d_{i}\oplus d_{i\otimes
j}=\frac{d_{i}(1-c_{i}^{j}(1-u_{j}))+c_{i}^{j}d_{j}u_{i}}{\beta}~{},$
$\displaystyle u_{i}\oplus u_{i\otimes
j}=\frac{u_{i}(1-c_{i}^{j}(1-u_{j}))}{\beta}~{},$ $\displaystyle a_{i}\oplus
a_{i\otimes
j}=\frac{(a_{i}-(a_{i}+a_{j})u_{i})(1-c_{i}^{j}(1-u_{j}))+a_{j}u_{i}}{\beta-
u_{i}(1-c_{i}^{j}(1-u_{j}))}~{},$
$\displaystyle\beta=1-c_{i}^{j}(1-u_{i})(1-u_{j})\neq 0,$

For simplicity, if uncertainty ($u$) is very low ($u\leq T_{u}$), we assume
$u=0$, halting further opinion updates by users.

We explore three opinion models (OMs) based on their types of trust, including
uncertainty-based trust, homophily (like-mindedness)-based trust, and no-
trust-based trust:

  * •

Uncertainty-based OM (UOM): This OM uses uncertainty (or certainty)-based
trust and calculates the uncertainty discounting operator $uc_{i}^{j}$ between
two users as $uc_{i}^{j}=(1-u_{i})(1-u_{j})$. To ensure non-zero uncertainty
for using the consensus operator in Eq. (8), a vacuity (uncertainty)
maximization technique [10] is employed, defining a vacuity-maximized opinion
for user $i$ as
$\ddot{\omega}_{i}=(\ddot{b}_{i},\ddot{d}_{i},\ddot{u}_{i},\bm{a}_{i})$. Here,
$\ddot{u}_{i}$ is the minimized projected belief and disbelief, adjusted by
$a_{i}$ and $(1-a_{i})$, with $\ddot{b}_{i}$ and $\ddot{d}_{i}$ calculated by
reducing $\ddot{u}_{i}$ from $P(b_{i})$ and $P(d_{i})$, respectively. When
$u_{i}<\xi$ (indicating low uncertainty or vacuity with sufficient evidence)
and dissonance (uncertainty caused by conflicting evidence)
$\bm{b}_{i}^{\mathrm{Diss}}>T_{d}$ remains high, uncertainty $\ddot{u}_{i}$ is
used to consider the effect of new information more dynamically. We set
$\xi=0.01$ and $T_{d}=0.6$ as thresholds to effectively maximize each party’s
influence based on our experimental analysis.

  * •

Homophily-based OM (HOM): Homophily, i.e., the tendency of like-minded
individuals to associate, significantly influences opinion updates [16]. The
homophily discounting operator $hc_{i}^{j}$ is determined using cosine
similarity [26] to measure the alignment between two users’ beliefs and
disbeliefs by:

$\displaystyle hc_{i}^{j}$ $\displaystyle=$
$\displaystyle\frac{b_{i}b_{j}+d_{i}d_{j}}{\sqrt{b_{i}^{2}+d_{i}^{2}}\sqrt{b_{j}^{2}+d_{j}^{2}}}.$
(9)

Utilizing cosine similarity evaluates the similarity in opinions by focusing
on belief and disbelief dimensions within an SL-based opinion model. This
sidesteps direct consideration of uncertainty since belief and disbelief imply
uncertainty due to $b+d+u=1$.

  * •

No-Trust-based OM (NOM): When we use neither UOM nor HOM, i.e., no trust
filter used, we name the opinion model ‘No-Trust-based OM’ and set
$nc_{i}^{j}=1$.

####  IV-C2 Opinion Reading

Following [5], we define a user’s reading behavior as a probability $P_{r}$,
indicating how often they read messages from neighbors. $P_{r}$ varies among 1
(multiple times per day), 0.5 (daily), 0.25 (weekly/monthly), and 0.1 (never)
to model different user engagement levels with the received content.

####  IV-C3 Opinion Sharing

Each user shares an opinion $\omega_{i}$ with friends $j$’s based on a sharing
probability $P_{s}$. Following the distribution from [5], $P_{s}$ varies to
reflect sharing frequency: 1 (always/mostly), 0.5 (half the time), 0.25
(sometimes), and 0.1 (never). Considering reading messages motivates updating
opinions [12], we assume a user will possibly share only if they read before.

###  IV-D Partially Observable Network

Following [21], we define a partially observable network within an undirected
graph $G=(V,E)$. $G^{\prime}$ = $(V,E^{\prime})$ represents the known portion
of the network, with $E^{\prime}\subset E$. Network visibility probability
$P_{nv}$ dictates the selection of $E^{\prime}$, influencing the visibility of
edges.

###  IV-E DRL-based Seed Set Selection Process

We utilize DRL to guide the decision-making process, optimizing strategy
selection for maximal influence spread within the network. We consider multi-
round influence propagation. Each round consists of two steps: the false party
(FP) selects one seed node and begins sharing assigned false information in
the first step. After that, the true party (TP) follows in the second step
with the assigned true information. An episode comprises a fixed number of
rounds, which equals the number of seed nodes. The design of states, actions,
and rewards of the DRL agent are described below.

####  IV-E1 States

At each step $t$, the state $s_{t}$ encompasses the network’s current
structure, defined as:

$s_{t}=\Bigg{\\{}\sum_{i,j\in\mathcal{U}_{i}}e_{i,j},\max_{i\in\mathcal{U}_{i}}\mathrm{deg}_{i}\Bigg{\\}},$
(10)

where $\sum_{i,j\in\mathcal{U}_{i}}e_{i,j}$ calculates the number of edges
among free nodes, and $\max_{i\in\mathcal{U}_{i}}\mathrm{deg}_{i}$ identifies
the highest degree among these nodes. We define free nodes as
$\\{j|u_{j}^{t}\geq 0.5\\}$, meaning user $j$ still has a high uncertainty
level and has yet to align with either party. Recall that $u_{j}^{t}$ refers
to the ‘vacuity’ (in Eq. (2)) of user $j$ at step $t$.

####  IV-E2 Actions

Action space at step $t$ is ${\bf
a}_{t}=\\{a_{t}^{AF},a_{t}^{BF},a_{t}^{SGF},a_{t}^{CF}\\}$. Actions focus on
the user’s behavioral or opinion traits and their network position:

  * •

Active First (AF, $a_{t}^{AU}$) prioritizes the most active user, determined
by the highest $P_{r}\times P_{s}$ in the network where $P_{r}$ and $P_{s}$
refer to a user’s reading and sharing probabilities.

  * •

Blocking First (BF, $a_{t}^{B}$) targets a user who is a neighbor of nodes
belonging to the opponent’s party and has the highest free degree (i.e., the
maximum number of free nodes connected to it). A user is considered to belong
to a party based on its expected belief or disbelief. User $i$ belongs to the
TP when $P(b_{i})>0.5$, or belongs to the FP if $P(d_{i})>0.5$.

  * •

SubGreedy First (SGF, $a_{t}^{SG}$) chooses a node with the maximum number of
neighboring nodes within $d$-hops [17, 6]. This aims to efficiently capture a
user’s network power in a local network. In this work, we choose $d=2$, which
balances efficiency and effectiveness based on our experimental investigation.

  * •

Centrality First (CF, $a_{t}^{CD}$) selects a user with the highest degree
centrality.

####  IV-E3 Rewards

The reward at step $t$ by each party, $\mathcal{T}$ and $\mathcal{F}$, is
estimated by:

$R^{\mathcal{T}}_{t}=n^{\mathcal{T}}_{t}-n^{\mathcal{T}}_{t-2},\;\;R^{\mathcal{F}}_{t}=n^{\mathcal{F}}_{t}-n^{\mathcal{F}}_{t-2}.$
(11)

The reward calculation for each party is based on the net change in the number
of users aligned with them from the previous round. Specifically, for the FP
which selects first, the reward at time $t=1$ is given by
$R^{\mathcal{F}}_{t}=n^{\mathcal{F}}_{t}-n^{\mathcal{F}}_{t-1}$. The TP starts
its calculation from $t=2$. The accumulated reward in one episode is:

$R_{T}=\sum_{t=T}^{\infty}\gamma^{t-T+1}R_{t},$ (12)

where $R_{t}$ is either $R^{\mathcal{T}}_{t}$ or $R^{\mathcal{F}}_{t}$ in Eq.
(11) and $\gamma$ is a discounting factor, we choose $\gamma=0.95$ in this
work.

Figure 1: CIM using Subjective Logic-based opinion model

Fig. 1 presents an overview of the CIM problem using Subjective Logic,
illustrated through an OSN case example. The figure employs a color gradient
to represent belief strength: lighter colors indicate less certainty, with
white denoting neutral users. Blue signifies users inclined toward true
information, with the darkest blue representing true information propagators.
Conversely, red indicates users leaning towards false information, with the
darkest red marking FIP identified by the FP.

##  V Experiment Setup

Experimental Setting: We employ Proximal Policy Optimization (PPO) [24] as a
DRL algorithm to select optimal seed nodes because PPO allows agents to update
multiple times with the same group of data with reduced computational
complexity. We assume six possible FPs using different strategies, including
the four strategies in the action space (i.e., AF, BF, CF, SGF), Random, and
DRL. ‘Random’ means randomly choosing a strategy out of the action space. We
train six distinct DRL agents for TP, given each FP, and then test with the
corresponding FP in Section VI. In reality, true information often counters
false narratives, so we give FIPs the first-mover advantage to select seed
nodes and propagate information first in each round using Breadth-First Search
for information spread. We initialize SL-based opinions for legitimate users
using the mapping rule in Eq. (2) with $(r,s,W)=(1,1,101)$, indicating high
uncertainty due to insufficient evidence. For TIPs, seed nodes’ opinions are
set to $(r,s,W)=(100,1,2)$, denoting strong confidence in their true
information. Conversely, FIPs have opinions initialized at
$(r,s,W)=(1,100,2)$, reflecting confidence in the false information.We use an
HPE Apollo 6500 system equipped with AMD EPYC 7742 chips, featuring a base
frequency of 2.25 GHz and a boost of up to 3.4 GHz for all experiments.

Datasets: We use the URV Email Network [23] for the current experimental
results. The dataset is the email communications at Universitat Rovira i
Virgili in Spain, an undirected graph with 1,133 nodes and 5,452 edges.

Metrics: The effectiveness of each party’s information maximization is
measured by the number of users holding the party’s beliefs, as determined by
Eq. (3). Users with $P_{i}(b_{i})\geq 0.5$ are classified as TP, indicating
TP’s influence, denoted by $n^{T}$. Algorithmic efficiency is assessed by the
simulation’s running time per episode.

Comparing Schemes: Unlike [4, 6, 17, 22], our approach employs a dynamic
opinion model, allowing user opinions to evolve through interactions using SL
[10]. To ensure a fair comparison with existing state-of-the-art (SOTA)
approaches, all models will operate under the same conditions. This includes
utilizing the same opinion models (HOM, UOM, or NOM), identical seed node
selection counts (i.e., $k=50$), and opinion updating mechanisms as detailed
in Section IV. Adapting these schemes to our settings might alter their
original performance, but this standardization is crucial for assessing their
performance in the more realistic scenarios addressed in our study. We
evaluate the performance of the following CIM algorithms:

  * •

DRIM-A implements a complete action set for seed node selection as detailed in
Section IV-E. ‘A’ represents the AF strategy.

  * •

DRIM-NA utilizes a subset of actions, specifically excluding AF where NA
represents No-AF, for seed node selection.

  * •

STORM is a SOTA approach in [17]. For a fair comparison, we apply our user
opinion model to STORM where we define free node ($\\{j|u_{j}^{t}\geq 0.5\\}$)
as the non-occupied node, which is different from the concept of free nodes
used in [17]. We also simplify STORM’s action space as max-weight and max-
degree are the same in an unweighted graph.

  * •

C-STORM [6] advances STORM by adding a preliminary step of identifying the
optimal community for seed selection detected by a community detection
algorithm, named it as C-STORM (i.e., community-based STORM). For a fair
comparison, we use our opinion model and the free nodes defined in our work.

##  VI Numerical Analysis & Results

We apply the trained model as the node selection agent when applying the DRL-
based strategy. Then, we let both parties pick 50 seeds and propagate in
turns. We assume TIP propagates twice after picking a seed while FIP does
once. We make this assumption because a mix of human judgment, diversity in
algorithm design, and public awareness play critical roles in the ongoing
battle against false information on OSNs, it is natural that true information
can gain more valid propagation in OSNs. All the experiment results have an
average of 20 runs.

###  VI-A Effect of Various Opinion Models

TABLE I: True Party (TP)’s Influence in $n^{\mathcal{T}}$ Under Various CIM Algorithms with Different OMs Scheme / OM |  Random |  AF |  BF |  SGF |  CF |  DRL
---|---|---|---|---|---|---
DRIM-A/UOM |  937.5 |  1008 |  894.3 |  951.4 |  937.3 |  890.8
DRIM-A/HOM |  150.5 |  61.5 |  576.3 |  57 |  227.6 |  142.9
DRIM-A/NOM |  474.9 |  89 |  561.3 |  60.2 |  65.1 |  102.2
DRIM-NA/UOM |  897.3 |  992.4 |  826.8 |  937.9 |  808.6 |  926.9
DRIM-NA/HOM |  232.6 |  48.2 |  672.2 |  109.3 |  62.9 |  53.6
DRIM-NA/NOM |  476.2 |  79.8 |  486.8 |  66.6 |  76.2 |  150.5
C-STORM/UOM |  659.7 |  704.2 |  1051.3 |  858.3 |  898 |  743
C-STORM/HOM |  238.3 |  618 |  679.7 |  149.8 |  64.2 |  58.7
C-STORM/NOM |  563.2 |  586.7 |  403.8 |  74.4 |  77.1 |  65.7
STORM/UOM |  722.3 |  652 |  1007.3 |  861 |  877 |  674.7
STORM/HOM |  373.7 |  659.2 |  779.3 |  62.4 |  62.1 |  68.6
STORM/NOM |  341 |  477.6 |  659.1 |  74.4 |  72.7 |  358.3

We compare the performance of four schemes against various-strategy FP under
three different opinion models: UOM, HOM, and NOM. As shown in Table I, the
first column marks the scheme names associated with the opinion models, and
the first row represents the node selection strategy applied by FP.
Performance is represented by the number of nodes $n^{\mathcal{T}}$ aligned
with TP $\mathcal{T}$. As shown in Table I, UOM always lets true information
gain the highest impact. This is because when user $i$ adopts UOM, user $i$
tends to accept new evidence when the $u_{i}$ is low. Thus, even with the
first-mover advantage of FP, true information can still be well spread through
the OSN.

The poor performance with HOM and NOM also shows that it is crucial to reach
out to the users with the correct information earlier rather than later. It
requires fast detection and quick response to combat False information.

###  VI-B Effect of DRL-based TP’s Influence Under Various Strategies Taken by
FP

Figure 2: TP’s influence under various CIM algorithms

(a) Varying # of information propagation (IP)

(b) Varying % of network observability

(c) Varying users’ prior belief

Figure 3: True party (TP)’s influence under various CIM algorithms when both
TP and False party (FP) use DRL for seed node selection

Fig. 2 presents the comparative performance analysis of the TP’s influence
under various CIM algorithms and UOM when the TP selects strategies to find
seed nodes using DRL. At the same time, the FP takes the fixed strategy to
select seed nodes under a fully observable network. It illustrates the
effectiveness of these four CIM algorithms under UOM when the FP chooses seed
nodes by a random strategy, one of four strategies in the action space, or
DRL-agent. Except for Blocking First (BF, $a_{t}^{B}$), when the FP applies
the other five strategies, DRIM-A and DRIM-NA outperform C-STORM and STORM.
The reason for lower performance under DRIM-A and DRIM-NA with the opponent
taking BF is that blocking can mitigate the impact of opponents but is not
effective in increasing its party’s influence. Therefore, our schemes are more
suitable for proactive opponents.

DRIM-A outperforms the DRIM-NA in most of the cases as the beneficial of
Active First (AF, $a_{t}^{AU}$) action. The gap is distinct, especially when
FP uses CF, a common and widely accepted strategy in IM. Hence, the user
behavior is worth considering in the CIM problem.

###  VI-C Sensitivity Analyses

This section discusses the sensitivity analyses of how the number of times
propagating true information or the percentage of network observability
affects the performance of the considered CIM algorithms that use UOM as an
opinion model.

####  VI-C1 Effect of Varying the Number of Information Propagation by TIPs

In Fig. 3(a), we examine the effect of increasing the number of information
propagation (IP) instances for the TP from 1 to 5 while the FP maintains a
fixed, single strategy. Naturally, all schemes demonstrate increased influence
with more IPs. Specifically, our schemes, DRIM-A and DRIM-NA, exhibit a
significant gain in influence when IP is increased from once to twice per
step, efficiently countering false information with minimal additional
resource investment. Beyond IP $>2$, the increase in influence plateaus, which
justifies setting the default IP value at 2 to optimize resource use while
maximizing influence.

####  VI-C2 Effect of Varying the Degree of Network Observability

As depicted in Fig. 3(b), DRIM-A and DRIM-NA maintain influence comparable to
C-STORM under conditions of partial network observability, impacting both the
TP and FP. This shared visibility condition means that any increase in network
transparency benefits FP’s performance as well. In contrast, STORM and C-STORM
show fluctuating performance improvements with greater network visibility,
indicating their lack of robustness against opponents who possess enhanced
information.

####  VI-C3 Effect of Varying the users’ prior belief

Prior belief represents the initial probability favoring belief acceptance. A
higher prior belief enhances TP’s influence, as demonstrated in Fig. 3(c).
Notably, even with low ($a<0.5$) or neutral ($a=0.5$) prior belief, DRIM-A and
DRIM-NA outperform C-STORM and STORM, indicating effectiveness even when
initial user beliefs do not favor true information. In summary, DRIM-A and
DRIM-NA are resource-efficient and robust in partially observable networks.
They effectively combat false information by maximizing the impact of true
information, even when users initially lean towards false information.

TABLE II: Simulation Running Time (RT) of the Considered CIM Algorithms Algo. |  DRIM-A |  DRIM-NA |  C-STORM |  STORM
---|---|---|---|---
RT (sec.) |  0.108 |  0.099 |  0.132 |  0.244

###  VI-D Running Time Analysis of CIM Algorithms

Our DRIM-A and DRIM-NA demonstrated superior running time as shown in Table
II. DRIM-NA is more efficient because of the smaller action space, but
sacrificing the performance as shown in Fig. 2.

##  VII Conclusions & Future Work

This work introduced a deep reinforcement learning (DRL)-based framework
enhanced with Subjective Logic (SL) to refine competitive influence
maximization (CIM) analysis by integrating uncertain opinions and user
preferences in Online Social Networks (OSNs). Unlike traditional CIM
approaches that rely on binary opinions (i.e., either 0 or 1), our model
incorporates a more nuanced Uncertainty-based Opinion Model (UOM), which
reflects a more realistic representation of user attitudes. Our proposed
schemes, DRIM-A and DRIM-NA, demonstrate superior efficiency and effectiveness
in countering false information by leveraging this model.

Our experimental results demonstrated that UOM significantly enhances the
dissemination of true information, even with less engaged users, a typical
scenario in combating false information. Further, recognizing user behavior
patterns and engagement levels is crucial when designing the action space for
the True Party, particularly as active users with high reading and sharing
frequency.

Future work aims to extend these experiments to larger and denser social
networks to evaluate the scalability of our framework. We will explore the
nuances of uncertainty further to develop more sophisticated and practical
solutions, contributing significantly to advancing CIM research.

## Acknowledgement

This work is partly supported by NSF under Grant Numbers 2107449, 2107450, and
2107451. The views and conclusions contained in this document are those of the
authors and should not be interpreted as representing the official policies,
expressed or implied, of the U.S. Government.

## References

  * [1]
  * Ali et al. [2020] K. Ali, C. Wang, M. Yeh, and Y. Chen. 2020.  Addressing Competitive Influence Maximization on Unknown Social Network with Deep Reinforcement Learning. In _2020 IEEE/ACM Intl. Conf. on Advances in Social Networks Analysis and Mining (ASONAM)_. 196–203.
  * Ali et al. [2021] K. Ali, C. Wang, M. Yeh, C. Li, and Y. Chen. 2021.  NEDRL-CIM:Network Embedding Meets Deep Reinforcement Learning to Tackle Competitive Influence Maximization on Evolving Social Networks. In _2021 IEEE 8th Intl. Conf. on Data Science and Advanced Analytics (DSAA)_. 1–9.
  * Bharathi et al. [2007] S. Bharathi, D. Kempe, and M. Salek. 2007.  Competitive Influence Maximization in Social Networks. In _Internet and Network Economics_. Springer Berlin Heidelberg, Berlin, Heidelberg, 306–311.
  * Cho et al. [2019] J.H. Cho, S. Rager, J. O’Donovan, S. Adali, and B. Horne. 2019.  Uncertainty-based False Information Propagation in Social Networks.  _ACM Transactions on Social Computing_ 2, 2 (2019), 1–34.
  * Chung [2019] T. Chung. 2019.  Deep Reinforcement Learning-based Approach to Tackle Competitive Influence Maximization. In _Proc. of MLG Workshop_.
  * Domingos and Richardson [2001] P. Domingos and M. Richardson. 2001.  Mining the Network Value of Customers. In _Proc. of the Seventh ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining_. 57–66.
  * Granovetter [1978] M. Granovetter. 1978.  Threshold Models of Collective Behavior.  _Amer. J. Sociology_ 83, 6 (1978), 1420–1443.
  * Guo et al. [2020] Z. Guo, J.H. Cho, R. Chen, S. Sengupta, M. Hong, and T. Mitra. 2020.  Online Social Deception and its Countermeasures: A Survey.  _IEEE Access_ 9 (2020), 1770–1806.
  * Jøsang [2016] A. Jøsang. 2016.  _Subjective Logic: A Formalism for Reasoning Under Uncertainty_.  Springer.
  * Jøsang et al. [2018] A. Jøsang, J.H. Cho, and F. Chen. 2018.  Uncertainty Characteristics of Subjective Opinions. In _21st FUSION_. 1998–2005.
  * Karnowski et al. [2018] V. Karnowski, L. Leonhard, and A. Kümpel. 2018.  Why Users Share the News: A Theory of Reasoned Action-based Study on the Antecedents of News-sharing Behavior.  _Communication Research Reports_ 35, 2 (2018), 91–100.
  * Kempe et al. [2003a] D. Kempe, J. Kleinberg, and É. Tardos. 2003a.  Maximizing the Spread of Influence through a Social Network. In _Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining_ (Washington, D.C.) _(KDD ’03)_. Association for Computing Machinery, New York, NY, USA, 137–146.
  * Kempe et al. [2003b] D. Kempe, J. Kleinberg, and É. Tardos. 2003b.  Maximizing the Spread of Influence Through a Social Network. In _Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining_. 137–146.
  * Li et al. [2020] J. Li, T. Cai, K. Deng, X. Wang, T. Sellis, and F. Xia. 2020.  Community-diversified Influence Maximization in Social Networks.  _Information Systems_ 92 (2020), 101522.
  * Li et al. [2013] L. Li, A. Scaglione, A. Swami, and Q. Zhao. 2013.  Consensus, Polarization and Clustering of Opinions in Social Networks.  _IEEE Journal on Selected Areas in Communications_ 31, 6 (2013), 1072–1083.
  * Lin et al. [2015] S. Lin, S. Lin, and M. Chen. 2015.  A Learning-Based Framework to Handle Multi-Round Multi-Party Influence Maximization on Social Networks. In _Proc. of the 21th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining_ (Sydney, NSW, Australia) _(KDD ’15)_. New York, NY, USA, 695–704.
  * Lin and Lui [2015] Y. Lin and J. Lui. 2015.  Analyzing Competitive Influence Maximization Problems with Partial Information: An Approximation Algorithmic Framework.  _Performance Evaluation_ 91 (2015), 187–204.
  * Liu et al. [2020] W. Liu, L. Chen, X. Chen, and B. Chen. 2020.  An Algorithm for Influence Maximization in Competitive Social Networks with Unwanted Users.  _Applied Intelligence_ 50, 2 (2020), 417–437.
  * Michael et al. [2021] K. Michael, L. Markus, R. Mario, and S. Markus. 2021.  Benders decomposition for competitive influence maximization in (social) networks.  _Omega_ 100 (2021), 102264.
  * Nasim et al. [2016] M. Nasim, R. Charbey, C. Prieur, and U. Brandes. 2016.  Investigating Link Inference in Partially Observable Networks: Friendship Ties and Interaction.  _IEEE Transactions on Computational Social Systems_ 3, 3 (2016), 113–119.
  * Pham et al. [2019] C. Pham, H. Duong, H. Hoang, and M. Thai. 2019.  Competitive Influence Maximization within Time and Budget Constraints in Online Social Networks: An Algorithmic Approach.  _Applied Sciences_ 9, 11 (2019).
  * Rossi and Ahmed [2015] R. Rossi and N. Ahmed. 2015.  The Network Data Repository with Interactive Graph Analytics and Visualization. In _Proc. of the AAAI Conf. on Artificial Intelligence_ , Vol. 29.
  * Schulman et al. [2017] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. 2017.  Proximal Policy Optimization Algorithms.  _arXiv preprint arXiv:1707.06347_ (2017).
  * Shakarian et al. [2015] P. Shakarian, A. Bhatnagar, A. Aleali, E. Shaabani, R. Guo, P. Shakarian, A. Bhatnagar, A. Aleali, E. Shaabani, and R. Guo. 2015.  The Independent Cascade and Linear Threshold Models.  _Diffusion in Social Networks_ (2015), 35–48.
  * Tan et al. [2005] P. Tan, M. Steinbach, and V. Kumar. 2005.  _Introduction to Data Mining (First Edition)_.  Boston, MA, USA.


# Promoting Fair Proposers, Fair Responders or Both? Cost-Efficient
Interference in the Spatial Ultimatum Game

Theodor Cimpeanu1, Cedric Perret2, and The Anh Han1,⋆

1 School of Computing, Engineering and Digital Technologies, Teesside
University, Middlesbrough, UK TS1 3BA
2 College of Life and Environmental Sciences, University of Exeter, Exeter, UK
EX4 4PY
⋆ Corresponding author: The Anh Han<EMAIL_ADDRESS>
## Abstract

Institutions and investors face the constant challenge of making accurate
decisions and predictions regarding how best they should distribute their
endowments. The problem of achieving an optimal outcome at minimal cost has
been extensively studied and resolved using several heuristics. However, these
works usually fail to address how an external party can target different types
of fair behaviour or do not take into account how limited information can
shape this complex interplay. Here, we consider the well-known Ultimatum game
in a spatial setting and propose a hierarchy of interference mechanisms based
on the amount of information available to an external decision-maker and
desired standards of fairness. Our analysis reveals that monitoring the
population at a macroscopic level requires more strict information gathering
in order to obtain an optimal outcome and that local observations can mediate
this requirement. Moreover, we identify the conditions which must be met for
an individual to be eligible for investment in order to avoid unnecessary
spending. We further explore the effects of varying mutation or behavioural
exploration rates on the choice of investment strategy and total accumulated
costs to the investor. Overall, our analysis provides new insights about
efficient heuristics for cost-efficient promotion of fairness in societies.
Finally, we discuss the differences between our findings and previous work
done on the PD and present our suggestions for promoting fairness as an
external decision-maker.

Keywords: Ultimatum game, interference, evolutionary game theory, complex
network.

##  1 Introduction

The problem of how collective behaviour, such as cooperation, coordination,
safety compliance and fairness among self-interested individuals, emerges in
evolving, dynamical systems has fascinated researchers from many disciplines,
ranging from Evolutionary Biology, Economics, Physics, Social Sciences and
Computer Science (Perc and Szolnoki,, 2010, Sigmund,, 2010, Airiau et al.,,
2014, Han,, 2013, Nowak,, 2006, West et al.,, 2007, Tuyls and Parsons,, 2007,
Maynard-Smith,, 1982, Han et al., 2020a, ). Several mechanisms that are
responsible for promoting the emergence of cooperation have been proposed,
including direct reciprocity (Trivers,, 1971, Sigmund,, 2010), kin selection
(Hamilton,, 1964) and network reciprocity (Ohtsuki et al.,, 2006) (for review,
see (Nowak,, 2012, West et al.,, 2007)). In these works, the evolution of
desired collective behaviour is typically shaped by the combined actions of
individuals within the systems.

On the other hand, external interference, where the advocating of certain
desired collective behaviour is carried out by an external decision maker (who
does not belong to the system), studies how this can be done in a cost-
effective way (Chen et al.,, 2015, Han and Tran-Thanh,, 2018, Han et al.,,
2018, Wang et al.,, 2019, Cimpeanu et al.,, 2019). These works aim to identify
a broad class of interference strategies, or heuristics, that exploit
available information such as global statistics (population behavioural
composition), as well as local information such as local behaviour profile and
diversity, and graph structures, for budget saving. This line of research is
useful to provide insights into the design of self-organised and distributed
Multi-Agent Systems (MAS), in order to ensure agents achieve a desired
collective state. For instance, one might consider a hybrid system consisting
of humans and intelligent machines, in which it is important to ensure a
cooperative and trustful relationship amongst each other (Paiva et al.,, 2018,
Santos et al.,, 2019, Andras et al.,, 2018). Another example is how
international agencies such as the European Union and United Nations might
advocate certain preferred political behaviours or resolve international
conflicts, given a limited budget (e.g. in terms of cost and military
resources) (Marton-Lafevre et al.,, 2007, Smidt,, 2020).

The literature on external interference in evolving, dynamical systems (or
populations) has so far focused on cooperation dilemmas, namely the Prisoner’s
Dilemma (PD) (Han and Tran-Thanh,, 2018, Han et al.,, 2018, Cimpeanu et al.,,
2019) and the Public Goods Game (PGG) (Sasaki et al.,, 2012, Chen and Perc,,
2014, Chen et al.,, 2015, Wang et al.,, 2019). In these games, the
interactions are symmetric and the players’ roles are equivalent. However,
many real-world and MAS interactions are asymmetric, where players may have
different baseline characteristics and/or play different roles in the
interactions (Tuyls et al.,, 2018, McAvoy and Hauert,, 2015, Ogbo et al.,,
2021). Examples include conflict resolution (Selten,, 1978, Smidt,, 2020),
technology adoption by firms (Ogbo et al.,, 2021), and multiparty resource
allocations (Chevaleyre et al.,, 2005, Lerat et al.,, 2013), where
participants might have different roles (e.g. proposers/dictators vs
responders) or bargaining power in the decision making process. In this
asymmetric setting, the external decision maker might need to take into
account the difference among players’ underlying characteristics, such as
their roles in the interactions, in order to optimise the cost and the level
of desired behaviour. In particular, we might ask, is it enough to target a
subset of the roles to already achieve a sufficiently good outcome, since
collecting information about all the roles might be (very) costly and time
consuming?

This paper contributes to advancing the state-of-the-art by studying cost-
efficient external interference in a spatial Ultimatum Game (UG), a popular
bargaining game for investigating fair decision making in many disciplines,
such as economics and AI/MAS research, (Güth et al.,, 1982, Fehr and Schmidt,,
1999, De Jong et al.,, 2008, Santos et al.,, 2019, de Melo et al.,, 2018, de
Jong and Tuyls,, 2011, Rauwolf and Bryson,, 2018). In a standard UG, players
have two different roles, proposer and receiver (or responder), with different
bargaining powers (See Methods in Section 3 for a detailed description of the
game). We consider the spatial version of the game (Page et al.,, 2000) where
players are distributed on a network in order to examine how to exploit the
roles’ asymmetry in both global and local interference strategies (Han et
al.,, 2018).

In general, a cost-efficient interference problem consists of solving a bi-
objective optimisation problem (Han and Tran-Thanh,, 2018, Wang et al.,,
2019), maximising the overall level of desired behaviours (in the long run)
while ensuring the total cost spent being within budget and/or minimal. The
key challenge is that, for evolving, dynamical systems such as those in the
above-mentioned examples, the system dynamics are shaped by various stochastic
and random effects, such as those resulting from behavioural updates and
mutation (behavioural exploration) (Traulsen et al.,, 2009, Rand et al.,
2013a, ). With behavioural updates, such as through social learning or
reproduction (Nowak,, 2006, Sigmund,, 2010), undesired behaviours might
resurface over time whenever interference was not sufficiently strong in the
past. Through mutation, these behaviours might do so even when they were
extinct. Hence, the external decision maker needs to take into consideration
that they will have to repeatedly interfere in the system, in order to sustain
the desired behaviour over time. Note however that, for simplicity, previous
works have either omitted mutation (Han and Tran-Thanh,, 2018, Wang et al.,,
2019), or assumed that it is infinitely small (for analytical treatment) (Han
and Tran-Thanh,, 2018). Mutation (behavioural exploration), where agents can
freely experiment with new behaviours, is usually non-negligible in real
populations and has been shown to play an important role in enabling
cooperation in the context of social dilemmas (Duong and Han,, 2019, Antal et
al.,, 2009, Traulsen et al.,, 2009, Han et al.,, 2012, Rand et al., 2013a, ).
Thus, the present work will also advance the state-of-the-art in this respect,
where we will closely examine how different regimes of mutation, or agents’
propensity for behavioural exploration, influence the manner in which external
interference should be carried out. Indeed, our results show that when
mutation is sufficiently high, in line with those observed in behavioural
experiments, optimal interference strategies can be significantly different.

The remainder of the paper is structured as follows. The next section reviews
most relevant literature. Section 3 then describes the models and methods in
detail. The paper proceeds with presenting the results and a final discussion.
We also include with this paper a Supplementary Information (SI) that includes
additional results to support the robustness of the paper findings.

##  2 Models and Methods

###  2.1 Ultimatum Game (UG)

Agents’ interaction is modelled using the one-shot Ultimatum Game (UG) (Nowak
et al.,, 2000, Page et al.,, 2000). In the UG, two players are offered a
chance to win a certain sum of money, normalised to 1, which they must divide
between each other. One player is elected proposer, and suggests how to split
the sum, while the other, the receiver (responder) can accept or reject the
deal. If the deal is rejected, neither player receives any part of the initial
sum. As in (Nowak et al.,, 2000, Page et al.,, 2000), we assume that a player
is equally likely to perform in one of the roles (proposer or receiver). A
player’s strategy is defined by a pair of parameters, $p$ and $q$. When acting
as proposer, the player offers the amount $p$, while in a receiver’s role, the
player rejects any offer smaller than $q$.

As we focus in this paper on the effect of having multiple roles on
interference decision making, we consider a baseline UG model where proposers
have two possible strategic offers, a low (L, with $p=l$) and a high (fair)
(H, with $p=h$) one, where $l<h\in[0,1]$. On the other hand, receivers have
two options, a low threshold (L, with $q=l$) and a high threshold (H, with
$q=h$). Thus, overall, there are four possible strategies HH, HL, LH and LL
(i.e. HL would denote proposing high and accepting any offers, etc.). Given
evidence from several behavioural experiments (Güth et al.,, 1982, Rand et
al., 2013a, ), in which people (almost) never offered more than half of the
sum in UG, we assume $h\leq 0.5$. Particularly, we set $h=0.5$ and $l=0.1$, as
shown in (Page et al.,, 2000). In this scenario, the strategy LL is
evolutionarily stable. We also confirm this result in our simulations, as
shown in Figure S1 in Supplementary Information (SI) and we note that this
result is true for several mutation rates.

The payoff matrix for the four strategies HH, HL, LH and LL reads (for row
player)

$\left(\begin{array}[]{cccc}1/2&1/2&(1-h)/2&(1-h)/2\\\
1/2&1/2&(1-h+l)/2&(1-h+l)/2\\\ h/2&(1+h-l)/2&0&(1-l)/2\\\
h/2&(1+h-l)/2&l/2&1/2\\\ \end{array}\right).$ (1)

###  2.2 Population structure and dynamics

We consider a population of agents or individuals on a square lattice of size
$Z=L\times L$ with periodic boundary conditions— a widely adopted population
structure in population dynamics and evolutionary games (Szabó and Fath,,
2007). We focus our analysis on the efficiency of various interference
strategies in spatial settings, adopting an agent-based model directly
comparable with the setup of recent lab experiments on cooperation (Rand et
al.,, 2014). We set $L=100$ for all our experiments, resulting in a population
size $Z=10^{4}$.

Initially each agent is designated as one of the four strategies (i.e. HH, HL,
LH, HH), with equal probability. At each time step or generation, each agent
plays the UG with its (four) immediate neighbours. The score for each agent is
the sum of the payoffs in these encounters. At the end of each generation an
agent $A$ with score $f_{A}$ chooses to copy the strategy of a randomly
selected neighbour agent $B$ with score $f_{B}$ with a probability given by
the Fermi rule (i.e. stochastic update) (Traulsen et al.,, 2006):

$(1+e^{(f_{A}-f_{B})/K})^{-1},$

where $K$ denotes the amplitude of noise in the imitation process (Szabó and
Fath,, 2007). Varying $K$ allows us to capture a wide range of update rules
and levels of stochasticity, including those used by humans, as measured in
lab experiments (Zisis et al.,, 2015, Rand et al., 2013b, ). In line with
previous works and lab experiments (Szabó and Fath,, 2007, Zisis et al.,,
2015, Rand et al., 2013a, ), we set $K=0.1$ in our simulations. With a given
probability $\mu$, this process is replaced instead by a randomly occurring
mutation. A mutation is equivalent to behavioural exploration, where the
individual makes a stochastic decision switch to one of the four available
strategies.

Although our analysis below will focus on the stochastic update rule (in order
to examine how stochasticity affects interference, as discussed above), we
will also provide results for deterministic update to have a clear comparison
with previous works (see e.g. (Han et al.,, 2018)). For the deterministic
update, an agent’s strategy is always changed to that of its highest scoring
neighbour (Nowak and May,, 1992, Szabó and Fath,, 2007). This is a way of
approximating the stochastic update rule where the stochastic effect is
infinitely small, i.e. $K\rightarrow 0$.

We simulate this evolutionary process until a stationary state or a cyclic
pattern is reached. Similarly to (Nowak and May,, 1992), all the simulations
in this work (described in next sections) converge quickly to such a state.
For the sake of a clear and fair comparison, all simulations are run for 500
generations. Moreover, for each simulation, the results are averaged over the
final 25 generations, in order to account for the fluctuations characteristic
of these stable states. Furthermore, to improve accuracy, for each set of
parameter values, the final results are obtained from averaging 30 independent
realisations. When shown in figures, the error bars represent the standard
error of the mean between replicates.

Note that in the special case of deterministic update (where we also do not
consider mutations), simulations can stop early when the proportion of fair
proposers reaches $100\%$. We note that when maximum fairness is not reached,
investment can still be ongoing beyond 500 generations and thus, the total
cost of interference is dependent on the chosen stopping point. However, our
results show that the average investment at the 500 generation mark is never
more than $0.2\%$ of the average total investment, for all types of
interference. Thus, this arbitrary number has a limited effect and should not
affect these results qualitatively.

###  2.3 Cost-Efficient Interference in Networks

We aim to study how one can efficiently interfere in a structured population
to achieve high levels of fairness while minimising the cost of interference.
Naturally, the level of fairness is measured by the fraction of fair offers in
the population (Rand et al., 2013a, ), which is the total of HH and HL
frequencies. An investment decision consists of a cost $\theta>0$ to the
external decision-making agent/investor, this value $\theta$ is added as
surplus to the payoff of each suitable candidate.

We examine and compare different approaches of interference to induce
fairness, based on ensuring fairness for either role or both, leading to
different desirable behaviours to be targeted

  * (i)

ensure all proposals are fair, thus investing in HH and HL (Target: HH, HL);

  * (ii)

ensure only fair offers are accepted, thus investing in HH and LH (Target: HH,
LH);

  * (iii)

ensure both (i) and (ii), i.e. investing in HH only (Target: HH).

Moreover, in line with previous works on network interference (Chen et al.,,
2015, Han and Tran-Thanh,, 2018, Cimpeanu et al.,, 2019), we will compare
global interference strategies where investments are triggered based on
network-wide information, and the local ones where investments are based on
local neighbourhood information.

In the population-based approach, a decision to invest in desirable behaviours
is based on the current composition of the population. We denote $x_{f}$ the
fraction of individuals in the population with a desirable behaviour, given a
targeting approach at hand, i.e. (i), (ii) or (iii) as defined above. Namely,
investment is made if $x_{f}$ is less or at most equal to a threshold $p_{f}$
(i.e. $x_{f}\leq p_{f}$), for $0\leq p_{f}\leq 1$. They do not invest
otherwise (i.e. $x_{f}>p_{f}$). The value $p_{f}$ describes how rare the
desirable behaviours should be to trigger external support. In the
neighbourhood-based approach, a decision to invest is based on the fraction
$x_{f}$ calculated at local level. Investment happens if the proportion of
neighbours of a focal individual with the desirable behaviours is less or at
most equal to a threshold $n_{f}$ (i.e. $x_{f}\leq n_{f}$), for $0\leq
n_{f}\leq 1$; otherwise, no investment is made.

##  3 Results

When choosing to invest in a population of individuals in an effort to ensure
some form of desirable outcome, an external decision maker must first consider
several factors before any decision is made. Among these, we consider and aim
to resolve the questions regarding what sort of behaviour they should invest
in, how large the individual endowment must be, but also what an investor can
do when information about the population or the environment is incomplete, or
even unknown. As such, we consider that the simplest form of information
gathering evaluates the overall population (in the form of some metric
measuring fairness on average), as opposed to fine-grained observations on
individual neighbourhoods. Likewise, we consider that ensuring all proposals
are fair (i.e. investing in HH or HL) is less demanding on an external
decision-maker than ensuring that only fair offers are accepted (i.e.
investing in HH and LH), which is, in turn, a simpler endeavour than for both
the former and latter to be strictly enforced (choosing to invest in HH only).
In this way, we can conceptualise a hierarchy of investment strategies, in
terms of complexity, some of which may simply be impossible for an investor to
follow, merely due to lack of information, funding, or a combination of the
two.

We consider that there exists a minimal level of fairness which the external
decision maker is aiming to enforce in regards to the population’s behaviour
(Han and Tran-Thanh,, 2018), and we study the least expensive investment
strategies for differing preferences of such an acceptable fairness.

Figure 1: Average fairness (left) and average cost of interference (right) as
a function of the individual endowment $\theta$ and the threshold $p_{f}$
(population-based, $\mu=0.01$, stochastic update). Each row represents a
different targeting scheme. The cost of interference is shown on a logarithmic
scale.

###  3.1 Population-based results

Firstly, we explore the simplest class of investment strategies, using a
macroscopic metric of the population, measuring average fairness in the whole
system (population). In Figure 1, we clearly observe the difference between
the three targets for investment. We would like to point out the higher levels
of fairness obtained using the HH targeting scheme, especially for a lower
threshold $p_{f}$. We also notice an increase in the threshold for investment
$p_{f}$ in order to achieve similar levels of fairness. When it comes to the
accumulated cost of interference, we see that HH is the most cost-effective
solution, due to the previously perceived lower threshold required to maintain
fairness.

Figure 2: Proportion of unfair proposers as a function of average cost of interference for different targeting scheme (population-based, $\mu=0.01$, stochastic update). The size and colour of the circles correspond to investment amount and threshold of investment, respectively. We note that the most desirable outcomes are closest to the origin. Table 1: Most cost-efficient scheme to reach a minimum fairness of proposals for different mutation rates (population-based, stochastic update). There exists no schemes which satisfy the higher minimum fairness requirements in the case of very high mutation rate, written as ‘–’ in the table. Mutation rate | Minimum fairness | Target | Threshold | $\theta$ | Cost
---|---|---|---|---|---
$10^{-4}$ | 75% | HH | 0.3 | 0.1 | 530
$10^{-4}$ | 90% | HH | 0.3 | 0.1 | 530
$10^{-4}$ | 99% | HH | 0.3 | 0.4 | 999
$10^{-2}$ | 75% | HH | 0.3 | 0.3 | 750
$10^{-2}$ | 90% | HH | 0.3 | 0.7 | 1747
$10^{-2}$ | 99% | HH | 1 | 0.1 | 487514
0.2 | 75% | HH | 0.6 | 0.2 | 358089
0.2 | 90% | – | – | – | –
0.2 | 99% | – | – | – | –

Figure 2 further exemplifies the finding that targeting HH is the optimal
scheme for population-based interference. Each row (portraying the different
targeting schemes), drifts further away from the cost-optimal bottom left. As
the threshold increases, so does the total cost, so the regions of high
fairness for a lower threshold observed in Figure 1 coincide with the maximal
savings (while still achieving desired levels of fairness).

Table 1 shows the most cost-efficient schemes for ensuring specific standards
of fairness when only a population-based approach is possible, under differing
rates of mutation ($\mu$). We observe a definitive bias towards the most
complex investment scheme (i.e. targeting HH players), which reiterates our
previous observation. We note that, in order to maintain a desired level of
fairness, an external decision maker must increase the threshold at which they
resume their investment, but also the individual endowment ($\theta$). It
becomes increasingly difficult to maintain standards of fairness when the
population is exposed to high degrees of behavioural exploration and this
naturally attracts an increase in total cost for the investor. We report
similar figures for other values of $\mu$ in Figures S2, S3, S4, in SI.

Moreover, we observe an increase in fairness for all schemes of interference,
across most values of individual endowment $\theta$, which bodes well when the
external decision maker possesses limited knowledge. If reducing cost is not
the main objective, fairness can be maintained using any targeting scheme
(i.e. any relevant observations made about the population), by increasing the
minimum threshold $p_{f}$.

When the external decision maker is limited to the macroscopic metrics
associated with population-based interference, interference is characterised
by its strictness. To elaborate, information gathering should be the main goal
for the investor, as ensuring that proposals and responses are simultaneously
fair (i.e. targeting HH) is the optimal outcome. In this way, the minimum
threshold can be kept low, reducing the accumulated cost.

Figure 3: Average fairness (left) and average cost of interference (right) as
a function of $\theta$ and threshold $n_{f}$ (neighbourhood-based, $\mu=0.01$,
stochastic update). Each row represents a different targeting scheme. The cost
of interference is on a logarithmic scale.

###  3.2 Neighbourhood-based interference

Previous works on the PD have shown that the greatest gains in cooperation
(while maintaining a minimal investment cost) require very detailed
observations of individual neighbourhoods, coupled with overly strict
investment schemes (Han and Tran-Thanh,, 2018, Cimpeanu et al.,, 2019, Han et
al.,, 2018). In order to decipher whether or not these findings hold for the
spatial ultimatum game, we study the outcome when an investor can perceive
fairness at the local level.

Figure 3 reports the relationship between gains in fairness and increases in
cost for an external investor, with diverse targets for receiving investments.
We observe that fairness is more easily achieved than in population based
interference, with only a very low investment required to sustain a majority
of fair proposals. Further investment increases the cost of interference, but
only slightly. If different thresholds result in fairness, Figure 3 shows that
a threshold of $25\%$ is the most cost-efficient. Similarly to population-
based interference, the external decision maker should invest only when a
large proportion of unfair individuals are present to limit the cost of
investment. Finally, there are no significant differences between targeting
schemes.

Similarly to our findings using a population-based approach, we observe that
the more prohibitive option, HH, is also the most cost-effective. On the other
hand, high fairness can be achieved in all three cases for the same values of
endowment. Ensuring that all proposals are fair (thus investing in HH and HL),
can lead to an increase in cost of interference, and a decrease in fairness
gains (relative to the other two interference strategies). While all
investment schemes evidently succeed in promoting the evolution of fairness,
only ensuring the equitable proposals is not as reliable as encouraging
discerning responses to offers or both. We note that this effect can only be
seen when the threshold for investment is very high (i.e. an investor only
invests in neighbourhoods with three or more fair proposers). As discussed
earlier, investing in neighbourhoods with at most one fair agent and not
investing otherwise, solves this dilemma.

Figure 4: Proportion of unfair proposers as a function of average cost of
interference for different targeting scheme (neighbourhood-based, $\mu=0.01$,
stochastic update). The size and colour of the circles correspond to
investment amount and threshold of investment, respectively. We note that the
most desirable outcomes are closest to the origin.

Markedly, it is not effective to invest in neighbourhoods with a high
percentage of fair proposals. These results point to a key observation, that
it is more important to invest in fair proposers when there are few of them in
a specific neighbourhood. In this sense, the lonely fair individuals require
aid in otherwise competitive, unjust entourages. This result can further be
seen in Figure 4. By being very selective with which neighbourhoods the
external investor chooses to invest in (i.e. only choosing very fair
neighbourhoods), they inadvertently produce a much higher final cost to their
own selves. An external decision-maker would then unwittingly keep investing
in fair proposals ad infinitum because fairness is eventually reached in the
ultimatum game, even when individual endowment is relatively low. It is clear,
therefore, that to reduce potential costs, only players in unfair groups
should be eligible for investment. Therefore, the defining characteristic of
neighbourhood-based interference is the low threshold for investment ($25\%$).

Table 2: Most cost-efficient scheme to reach a minimum fairness of proposals for different mutation rates (neighbourhood-based, stochastic update). There exists no schemes which satisfy the higher minimum fairness requirements in the case of very high mutation rates, written as ‘–’ in the table. Mutation rate | Minimum fairness | Target | Threshold | $\theta$ | Cost
---|---|---|---|---|---
$10^{-4}$ | 75% | HH | 0.25 | 0.1 | 1395
$10^{-4}$ | 90% | HH | 0.25 | 0.1 | 1395
$10^{-4}$ | 99% | HH | 0.25 | 0.1 | 1395
$10^{-2}$ | 75% | HH HL | 0.25 | 0.1 | 3794
$10^{-2}$ | 90% | HH LH | 0.25 | 0.1 | 4352
$10^{-2}$ | 99% | HH LH | 0.25 | 0.2 | 5957
0.2 | 75% | HH | 0.25 | 0.4 | 150777
0.2 | 90% | – | – | – | –
0.2 | 99% | – | – | – | –

By varying minimal fairness requirements and rates of mutation, we can gain
further insight into which investment strategies are the most robust and cost-
effective. Table 2 highlights some surprising findings. We see that
neighbourhood based interference can result in a higher total cost than the
optimal population-based interference schemes (see Table 1). Previous work has
shown that more specific and restrictive intervention schemes are more
effective in the PD (Han et al.,, 2018, Cimpeanu et al.,, 2019), but by being
able to target different roles in the Ultimatum game, these differences can be
mitigated. Furthermore, mutation rate serves as an equaliser between the
investment targets and we observe that less specific schemes (HH & HL and HH &
LH) are the most cost-efficient options. We note that the differences between
results are small enough that different runs could yield any outcome in the
case of high or intermediate mutation rates. The lack of significant
variability among the distinct targeting schemes contrasts strongly with the
findings on the PD (Han and Tran-Thanh,, 2018, Cimpeanu et al.,, 2019). We
report similar figures for other values of $\mu$ in Figures S5, S6, S7, in SI.

Figure 5: Typical runs showing the evolution of fairness and the associated
total cost of interference for various mutation rates ($\mu$) (neighbourhood-
based, stochastic update). Parameters: $\ n_{f}=0.25,\ \theta=0.1,\
Target=HH.$ The choice of parameter values was motivated by selecting the
optimal solutions in Table 2. Figure 6: Typical runs showing the evolution of
fairness and the associated total cost of interference for various mutation
rates ($\mu$) (neighbourhood-based, stochastic update). Parameters: $\
n_{f}=0.5,\ \theta=0.1,\ Target=HH.$ The choice of parameter values was
motivated by selecting the optimal solutions in Table 2.

###  3.3 Evolution of strategies over time

We make use of the optimal parameter values identified in Tables 1 and 2 to
explore the evolution of fairness over time for all the strategies in the
population, as well as any associated accumulated costs. Through this
analysis, we clarify some of the dynamics differentiating the different
decisions for investment, as well as the effects of varying mutation rates
upon the outcomes and the options available to investors.

The effects of mutation on the optimality of different interference schemes
can be seen in Figure 5. As the mutation rate ($\mu$) increases, the capacity
of maintaining a threshold of fairness decreases (as also seen in Table 2). An
external investor must increase their individual investment amount in order to
meet these new demands set out by the increased mutation rates, and by doing
so they can maintain fairness levels to a respectable standard.

Figure 7: Typical runs showing the evolution of fairness and the associated
total cost of interference for various mutation rates ($\mu$) (population-
based, stochastic update). Higher mutation rates leads to an increasing need
for interference over time. Parameters: $\ p_{f}=0.8,\ \theta=0.3,\
Target=HH.$ The choice of parameter values was motivated by selecting the
optimal solutions in Table 1.

To better highlight the sharp increases in the cost associated with the non-
optimal threshold (i.e. when it is greater than $25\%$) for neighbourhood-
based interference, we show such typical runs for varying mutation rates for
the $50\%$ threshold in Figure 6. When comparing Figures 5 and 6, we note the
relative differences in total accumulated costs attributed to the choice of
the threshold for investment $n_{f}$. We also note that increasing rates of
behavioural exploration (mutation) amplifies this discrepancy.

We show how less specific interference strategies, which require less
information gathering, can be effective in facilitating the evolution of
fairness, when local monitoring is possible (Figure 8). Promoting fair
proposals may often not be sufficient for low individual investment budgets
(which are also the optimal solution) — in such cases fairness does not
evolve. This occurs due to the inability of indiscriminate fair proposers to
protect themselves against unfair proposers. Investing in fair proposers, in
this case, artificially protects them against very competitive selection
pressures.

Figure 7 showcases how different mutation rates call for different approaches
to interference. As shown previously, optimal interference strategies vary
according to the mutation rate. We point out the three different cases in
which an investor might find themselves in. First, when few initial rounds of
investment are enough for the system to converge and stabilise to a desired
state. Second, an investor might be required to reinvest when the population
tends to revert back to its initial condition. Lastly, constant investment is
required to maintain a desired level of fairness, with the total cost
skyrocketing accordingly. To some extent, a fair population can better deal
with unfair invaders and this explains the need for a sufficiently high
initial investment when mutation rates increase.

Figure 8: Typical runs showing the evolution of fairness and the associated
total cost of interference for various targeting schemes (neighbourhood-based,
stochastic update). Parameters: $\ n_{f}=0.25,\ \theta=0.2,\ \mu=10^{-2}.$ The
choice of parameter values was motivated by selecting the optimal solutions in
Table 2.

Finally, behavioural exploration motivates the manner or strength (in terms of
individual endowment) of any initial efforts to moderate unfair behaviour.
Figures 5, 6 and 7 show that the increase in cost is linear and ever-growing
for high mutation-rates and gradually sharper at the beginning for lower
mutation, eventually plateauing when the population is exposed to little or no
behavioural exploration.

Table 3: Most cost-efficient population-based scheme (deterministic update) to reach a minimum fairness of proposals. Minimum fairness | Target | Threshold | $\theta$ | Cost
---|---|---|---|---
75% | HH | 0.5 | 0.5 | 1251
90% | HH | 0.6 | 0.9 | 2228
99% | HH | 0.9 | 1.1 | 5488
Table 4: Most cost-efficient neighbourhood-based scheme (deterministic update) to reach a minimum fairness of proposals. Minimum fairness | Target | Threshold | $\theta$ | Cost
---|---|---|---|---
75% | HH | 0.25 | 0.8 | 2146
90% | HH | 0.25 | 0.8 | 2146
99% | HH | 0.25 | 1 | 2513
Figure 9: Average fairness (left) and average cost of interference (right) as
a function of $\theta$ and threshold $n_{f}$ (neighbourhood-based,
deterministic update). Each row represents a different targeting scheme. The
cost of interference is on a logarithmic scale for clarity.

###  3.4 Deterministic update

The results and findings reported so far were based on the stochastic update
rule. We now take a step back and consider whether our findings would still
hold for the deterministic rule (see again Methods section). It is not only
for the sake of a direct comparison with a previous analysis reported in (Han
et al.,, 2018), where cost-efficient interference was studied for the spatial
PD in a deterministic setting (with no mutation). It would also allow us to
examine if the findings above would remain robust for the deterministic
update, a popular approximation for rare stochastic effect (or infinite
intensity of selection) that is regularly used in the literature (Szabó and
Fáth,, 2007). Tables 3 and 4 report results for the optimal interference
strategies, in population-based (for a full report, see Figure S8, in SI) and
neighbourhood-based schemes, respectively. We observe that for both schemes,
targeting HH is always the best option. This is the same as the stochastic
approach for population-based schemes but different from the neighbourhood-
based ones. However, for the latter ones, the optimal threshold $n_{f}=0.25$
remains the same as in the case of stochastic update, see also Figure 9. This
is in stark contrast with the PD results where $n_{f}=0.75$ was always the
optimal choice.

##  4 Discussion

In summary, this paper has advanced the state of the art of the literature on
external interference in dynamical systems, or populations of self-interested
individuals, in two main respects: i) we have addressed an asymmetric
interaction setting, in the form of the Ultimatum game, where players have
different roles in the interaction. We have shown that it is crucial to
consider the roles’ asymmetry to provide cost-efficient investment strategies.
This important analysis was not possible in previous works where symmetric
games were studied (Chen and Perc,, 2014, Han and Tran-Thanh,, 2018, Han et
al.,, 2018, Chen et al.,, 2015, Wang et al.,, 2019, Cimpeanu et al.,, 2019);
ii) we have incorporated realistic levels of mutation or behavioural
exploration in our analysis and have shown that they strongly affect the
manner in which interference should be carried out. Previous works have always
omitted mutation or assumed that it is infinitely small, thereby being unable
to address this important issue for real-world populations and applications.

We have identified several key features that are required for a cost-effective
interference scheme. On the one hand, population-based schemes are
characterised by the need of extensive information gathering about both roles,
as targeting HH always leads to the optimal strategy. On the other hand,
neighbourhood-based schemes are characterised by their flexibility, where the
optimal strategy always entails that investment is only made when there is at
most one player with the desirable behaviour in the neighbourhood (i.e. no
investment should be made when there is a half or larger fraction of such
behaviour the neighbourhood). Our findings stand out in stark contrast with
previous works on cooperation dilemmas, where both population and
neighbourhood-based schemes require a highly strict investment approach.

The ultimatum game has been widely studied, whether with theoretical models
(see (Debove et al.,, 2016) for a review) or behavioural experiments (see
(Güth and Kocher,, 2014) for a review). The main motivation arises from the
gap between theoretical predictions, in which rational individuals keep most
of the endowment and the responders accept any positive proposition however
small it may be, and experiments, in which individuals propose 40% to 50% of
their endowment (and often get punished if they propose less) (Güth et al.,,
1982). That said, previous works have investigated how fairness can evolve in
models of the ultimatum game, wherein several mechanisms promoting the
emergence of fairness have been identified. We note that we align our
definition of fairness with these previous works, where generous proposers are
deemed as fair, regardless of their behaviour when acting in the role of the
responder.

Among others, Nowak et al. have studied the evolution of fairness in the
Ultimatum game under indirect reciprocity (Nowak et al.,, 2000), i.e. when
players can observe others’ interactions and have information about the
reputations of others. We do not rely on reputation building mechanisms, as
the role of this mechanism can be limited in large groups, where one-shot
interactions between strangers are common. Page et al. and Sinatra et al. have
developed spatial models of the Ultimatum game, where interactions happen only
between neighbours (Page et al.,, 2000, Sinatra et al.,, 2009). It has been
shown that a spatial structure can promote the emergence of higher levels of
fairness, but an equal split between proposers and responders is yet to be
reached. The model developed in the present work has also considered a spatial
model because (i) it captures an essential feature of many real-world networks
of contacts (Barabasi,, 2014), and (ii) it allows us to explore the effects of
interference localised in particular neighbourhoods, which has been shown to
be more cost efficient (Han et al.,, 2018). Furthermore, Rand et al. have
shown that even if the population is well-mixed, fairness can result directly
from the effect of randomness due to mutation and stochastic strategy updates
(Rand et al., 2013b, ). Intuitively, the uncertainty in the responders’ choice
forces the proposers to offer a high proposal so as to avoid rejection. We
show that these stochastic factors also strongly influence the manner in which
external interference may be performed while maintaining cost-efficiency.
Moreover, the Ultimatum game has also been used to study how fairness can
emerge in a hybrid population of human-agent interactions (de Melo et al.,,
2018, Santos et al.,, 2019). These works, however, do not consider external
interference.

The problem of how to externally influence a system of multiple interacting
agents to achieve a certain desired behaviour has been of significant interest
in mechanism design, network theory and control theory literature. For
example, how to maximise influence in networks has been studied in (Wilder et
al.,, 2018, Bloembergen et al.,, 2014, Riehl and Cao,, 2016). Moreover,
Endriss et al. have investigated how to tax games so as incentivise certain
behaviours at system equilibrium (Endriss et al.,, 2011); while, Wooldridge
has presented potential ways to manipulate games in order to achieve desired
behaviours (Wooldridge,, 2012). These works, however, assume that the
decision-maker possesses full control of the agents within the systems. With
our approach, the decision-maker has little or no direct control on the
agents’ behaviour, so we can rely only on rewarding schemes and their effects
as ways of motivating the evolution of fairness. It is noteworthy that these
works do not focus on the cost efficiency problem, whereas cost optimisation
is one of our main goals.

Our future work will examine other asymmetric games with multiple roles, such
as the trust and anticipation games, where the bargaining nature is different
from the ultimatum game (Gut,, 2009, Han et al., 2020b, , Zisis et al.,, 2015,
Rauwolf and Bryson,, 2018), to see how this bargaining factor might affect the
way interference needs to be made. We are also interested in how different
network structures influence the interference strategies in asymmetric
interactions, which has been studied for symmetric games (Cimpeanu et al.,,
2019).

## Acknowledgements

T.C., C.P. and T.A.H. were supported by Future of Life Institute grant
RFP2-154. T.A.H. is also supported by a Leverhulme Research Fellowship
(RF-2020-603/9).

## References

  * Airiau et al., (2014) Airiau, S., Sen, S., and Villatoro, D. (2014).  Emergence of conventions through social learning.  Autonomous Agents and Multi-Agent Systems, 28(5):779–804.
  * Andras et al., (2018) Andras, P., Esterle, L., Guckert, M., Han, T. A., Lewis, P. R., Milanovic, K., Payne, T., Perret, C., Pitt, J., Powers, S. T., Urquhart, N., and Wells, S. (2018).  Trusting Intelligent Machines: Deepening Trust Within Socio-Technical Systems.  IEEE Technology and Society Magazine, 37(4):76–83.
  * Antal et al., (2009) Antal, T., Traulsen, A., Ohtsuki, H., Tarnita, C. E., and Nowak, M. A. (2009).  Mutation-selection equilibrium in games with multiple strategies.  Journal of theoretical biology, 258(4):614–622.
  * Barabasi, (2014) Barabasi, A.-L. (2014).  Linked-how Everything is Connected to Everything Else and what it Means F.  Perseus Books Group.
  * Bloembergen et al., (2014) Bloembergen, D., Sahraei, B. R., Bou-Ammar, H., Tuyls, K., and Weiss, G. (2014).  Influencing social networks: An optimal control study.  In ECAI, volume 14, pages 105–110.
  * Chen and Perc, (2014) Chen, X. and Perc, M. (2014).  Optimal distribution of incentives for public cooperation in heterogeneous interaction environments.  Frontiers in behavioral neuroscience, 8:248.
  * Chen et al., (2015) Chen, X., Sasaki, T., Brännström, Å., and Dieckmann, U. (2015).  First carrot, then stick: how the adaptive hybridization of incentives promotes cooperation.  Journal of the royal society interface, 12(102):20140935.
  * Chevaleyre et al., (2005) Chevaleyre, Y., Dunne, P. E., Endriss, U., Lang, J., Lemaitre, M., Maudet, N., Padget, J., Phelps, S., Rodrígues-Aguilar, J. A., and Sousa, P. (2005).  Issues in multiagent resource allocation.
  * Cimpeanu et al., (2019) Cimpeanu, T., Han, T. A., and Santos, F. C. (2019).  Exogenous rewards for promoting cooperation in scale-free networks.  In Artificial Life Conference Proceedings, pages 316–323. MIT Press.
  * de Jong and Tuyls, (2011) de Jong, S. and Tuyls, K. (2011).  Human-inspired computational fairness.  Autonomous Agents and Multi-Agent Systems, 22(1):103–126.
  * De Jong et al., (2008) De Jong, S., Uyttendaele, S., and Tuyls, K. (2008).  Learning to reach agreement in a continuous ultimatum game.  Journal of Artificial Intelligence Research, 33:551–574.
  * de Melo et al., (2018) de Melo, C. M., Marsella, S., and Gratch, J. (2018).  Social decisions and fairness change when people’s interests are represented by autonomous agents.  Autonomous Agents and Multi-Agent Systems, 32(1):163–187.
  * Debove et al., (2016) Debove, S., Baumard, N., and André, J. B. (2016).  Models of the evolution of fairness in the ultimatum game: A review and classification.  Evolution and Human Behavior, 37(3):245–254.
  * Duong and Han, (2019) Duong, M. H. and Han, T. A. (2019).  On equilibrium properties of the replicator–mutator equation in deterministic and random games.  Dynamic Games and Applications, pages 1–23.
  * Endriss et al., (2011) Endriss, U., Kraus, S., Lang, J., and Wooldridge, M. (2011).  Incentive engineering for boolean games.  IJCAI ’11, pages 2602–2607.
  * Fehr and Schmidt, (1999) Fehr, E. and Schmidt, K. M. (1999).  A theory of fairness, competition, and cooperation.  The quarterly journal of economics, 114(3):817–868.
  * Gut, (2009) Gut, A. (2009).  An Intermediate Course in Probability.  Springer Publishing Company, Incorporated, 2nd edition.
  * Güth and Kocher, (2014) Güth, W. and Kocher, M. G. (2014).  More than thirty years of ultimatum bargaining experiments: Motives, variations, and a survey of the recent literature.  Journal of Economic Behavior and Organization, 108:396–409.
  * Güth et al., (1982) Güth, W., Schmittberger, R., and Schwarze, B. (1982).  An experimental analysis of ultimatum bargaining.  Journal of economic behavior & organization, 3(4):367–388.
  * Hamilton, (1964) Hamilton, W. (1964).  The genetical evolution of social behaviour. i.  Journal of Theoretical Biology, 7(1):1 – 16.
  * Han, (2013) Han, T. A. (2013).  Intention Recognition, Commitments and Their Roles in the Evolution of Cooperation: From Artificial Intelligence Techniques to Evolutionary Game Theory Models, volume 9.  Springer SAPERE series.
  * Han et al., (2018) Han, T. A., Lynch, S., Tran-Thanh, L., and Santos, F. C. (2018).  Fostering cooperation in structured populations through local and global interference strategies.  In IJCAI-ECAI’2018, pages 289–295.
  * Han et al., (2012) Han, T. A., Pereira, L. M., and Santos, F. C. (2012).  The emergence of commitments and cooperation.  In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’2012), pages 559–566. ACM.
  * (24) Han, T. A., Pereira, L. M., Santos, F. C., and Lenaerts, T. (2020a).  To Regulate or Not: A Social Dynamics Analysis of an Idealised AI Race.  Journal of Artificial Intelligence Research, 69:881–921.
  * (25) Han, T. A., Perret, C., and Powers, S. T. (2020b).  When to (or not to) trust intelligent machines: Insights from an evolutionary game theory analysis of trust in repeated games.  arXiv e-prints, page arXiv:2007.11338.
  * Han and Tran-Thanh, (2018) Han, T. A. and Tran-Thanh, L. (2018).  Cost-effective external interference for promoting the evolution of cooperation.  Scientific reports, 8(1):1–9.
  * Lerat et al., (2013) Lerat, J.-S., Han, T. A., and Lenaerts, T. (2013).  Evolution of common-pool resources and social welfare in structured populations.  In IJCAI’2013, pages 2848–2854.
  * Marton-Lafevre et al., (2007) Marton-Lafevre, J. et al. (2007).  Peace parks: conservation and conflict resolution.  Mit Press.
  * Maynard-Smith, (1982) Maynard-Smith, J. (1982).  Evolution and the Theory of Games.  Cambridge University Press, Cambridge.
  * McAvoy and Hauert, (2015) McAvoy, A. and Hauert, C. (2015).  Asymmetric evolutionary games.  PLoS Comput Biol, 11(8):e1004349.
  * Nowak, (2006) Nowak, M. A. (2006).  Evolutionary Dynamics: Exploring the Equations of Life.  Harvard University Press, Cambridge, MA.
  * Nowak, (2012) Nowak, M. A. (2012).  Evolving cooperation.  Journal of Theoretical Biology, 299:1–8.
  * Nowak and May, (1992) Nowak, M. A. and May, R. M. (1992).  Evolutionary games and spatial chaos.  Nature, 359(6398):826–829.
  * Nowak et al., (2000) Nowak, M. A., Page, K. M., and Sigmund, K. (2000).  Fairness versus reason in the ultimatum game.  Science, 289(5485):1773–1775.
  * Ogbo et al., (2021) Ogbo, N. B., Elgarig, A., and Han, T. A. (2021).  Evolution of coordination in pairwise and multi-player interactions via prior commitments.  Adaptive Behavior (In Press).  Preprint arXiv:2009.11727.
  * Ohtsuki et al., (2006) Ohtsuki, H., Hauert, C., Lieberman, E., and Nowak, M. A. (2006).  A simple rule for the evolution of cooperation on graphs and social networks.  Nature, 441(7092):502–505.
  * Page et al., (2000) Page, K. M., Nowak, M. A., and Sigmund, K. (2000).  The spatial ultimatum game.  Proceedings of the Royal Society of London. Series B: Biological Sciences, 267(1458):2177–2182.
  * Paiva et al., (2018) Paiva, A., Santos, F. P., and Santos, F. C. (2018).  Engineering pro-sociality with autonomous agents.  In Thirty-second AAAI conference on artificial intelligence.
  * Perc and Szolnoki, (2010) Perc, M. and Szolnoki, A. (2010).  Coevolutionary games—a mini review.  BioSystems, 99(2):109–125.
  * Rand et al., (2014) Rand, D. G., Nowak, M. A., Fowler, J. H., and Christakis, N. A. (2014).  Static network structure can stabilize human cooperation.  Proc Natl Acad Sci USA, 111(48):17093–17098.
  * (41) Rand, D. G., Tarnita, C. E., Ohtsuki, H., and Nowak, M. A. (2013a).  Evolution of fairness in the one-shot anonymous ultimatum game.  Proceedings of the National Academy of Sciences, 110(7):2581–2586.
  * (42) Rand, D. G., Tarnita, C. E., Ohtsuki, H., and Nowak, M. A. (2013b).  Evolution of fairness in the one-shot anonymous ultimatum game.  Proc. Natl. Acad. Sci. USA, 110:2581–2586.
  * Rauwolf and Bryson, (2018) Rauwolf, P. and Bryson, J. J. (2018).  Expectations of fairness and trust co-evolve in environments of partial information.  Dynamic Games and Applications, 8(4):891–917.
  * Riehl and Cao, (2016) Riehl, J. R. and Cao, M. (2016).  Towards optimal control of evolutionary games on networks.  IEEE Transactions on Automatic Control, 62(1):458–462.
  * Santos et al., (2019) Santos, F. P., Pacheco, J. M., Paiva, A., and Santos, F. C. (2019).  Evolution of collective fairness in hybrid populations of humans and agents.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 6146–6153.
  * Sasaki et al., (2012) Sasaki, T., Brännström, Å., Dieckmann, U., and Sigmund, K. (2012).  The take-it-or-leave-it option allows small penalties to overcome social dilemmas.  Proceedings of the National Academy of Sciences, 109(4):1165–1169.
  * Selten, (1978) Selten, R. (1978).  A note on evolutionarily stable strategies in asymmetric animal conflicts.
  * Sigmund, (2010) Sigmund, K. (2010).  The Calculus of Selfishness.  Princeton University Press.
  * Sinatra et al., (2009) Sinatra, R., Iranzo, J., Gomez-Gardenes, J., Floria, L. M., Latora, V., and Moreno, Y. (2009).  The ultimatum game in complex networks.  Journal of Statistical Mechanics: Theory and Experiment, 2009(09):P09012.
  * Smidt, (2020) Smidt, H. M. (2020).  United nations peacekeeping locally: enabling conflict resolution, reducing communal violence.  Journal of Conflict Resolution, 64(2-3):344–372.
  * Szabó and Fath, (2007) Szabó, G. and Fath, G. (2007).  Evolutionary games on graphs.  Physics reports, 446(4-6):97–216.
  * Szabó and Fáth, (2007) Szabó, G. and Fáth, G. (2007).  Evolutionary games on graphs.  Phys Rep, 97-216(4-6).
  * Traulsen et al., (2009) Traulsen, A., Hauert, C., De Silva, H., Nowak, M. A., and Sigmund, K. (2009).  Exploration dynamics in evolutionary games.  Proceedings of the National Academy of Sciences, 106(3):709–712.
  * Traulsen et al., (2006) Traulsen, A., Nowak, M. A., and Pacheco, J. M. (2006).  Stochastic dynamics of invasion and fixation.  Phys Rev E, 74(1):011909.
  * Trivers, (1971) Trivers, R. L. (1971).  The evolution of reciprocal altruism.  Quaterly Review of Biology, 46:35–57.
  * Tuyls and Parsons, (2007) Tuyls, K. and Parsons, S. (2007).  What evolutionary game theory tells us about multiagent learning.  Artificial Intelligence, 171(7):406–416.
  * Tuyls et al., (2018) Tuyls, K., Perolat, J., Lanctot, M., Ostrovski, G., Savani, R., Leibo, J. Z., Ord, T., Graepel, T., and Legg, S. (2018).  Symmetric decomposition of asymmetric games.  Scientific Reports, 8(1):1–20.
  * Wang et al., (2019) Wang, S., Chen, X., and Szolnoki, A. (2019).  Exploring optimal institutional incentives for public cooperation.  Communications in Nonlinear Science and Numerical Simulation, 79:104914.
  * West et al., (2007) West, S., Griffin, A., and Gardner, A. (2007).  Evolutionary explanations for cooperation.  Current Biology, 17:R661–R672.
  * Wilder et al., (2018) Wilder, B., Immorlica, N., Rice, E., and Tambe, M. (2018).  Maximizing influence in an unknown social network.  In AAAI conference on Artificial Intelligence (AAAI-18).
  * Wooldridge, (2012) Wooldridge, M. (2012).  Bad equilibria (and what to do about them).  ECAI ’12, pages 6–11.
  * Zisis et al., (2015) Zisis, I., Guida, S. D., Han, T. A., Kirchsteiger, G., and Lenaerts, T. (2015).  Generosity motivated by acceptance - evolutionary analysis of an anticipation games.  Scientific reports, 5(18076).

##  5 Supplementary Information

Figure S1: Average frequencies of the four strategies HH, HL, LH and LL as a
function of mutation rate $\mu$ in absence of interference. Figure S2: Average
fairness as a function of the individual endowment $\theta$, the threshold
$p_{f}$ and the mutation rate $\mu$ (population-based, stochastic update).
Each row represents a different targeting scheme. Figure S3: Average cost of
interference as a function of the individual endowment $\theta$, the threshold
$p_{f}$ and the mutation rate $\mu$ (population-based, stochastic update).
Each row represents a different targeting scheme. The cost of interference is
shown on a logarithmic scale. Figure S4: Proportion of unfair proposers as a
function of average cost of interference for different targeting scheme and
mutation rate $\mu$ (population-based, stochastic update). The size and colour
of the circles correspond to investment amount and threshold of investment,
respectively. We note that the most desirable outcomes are closest to the
origin. Figure S5: Average fairness measured by the sum of frequencies of HH
and HL as a function of the individual endowment $\theta$, the threshold
$p_{f}$ and the mutation rate $\mu$ (neighbourhood-based, stochastic update).
Each row represents a different targeting scheme. Figure S6: Average cost of
interference as a function of the individual endowment $\theta$, the threshold
$p_{f}$ and the mutation rate $\mu$ (neighbourhood-based, stochastic update).
Each row represents a different targeting scheme. The cost of interference is
on a logarithmic scale for clarity. Figure S7: Proportion of unfair proposers
as a function of average cost of interference for different targeting scheme
and mutation rate $\mu$ (neighbourhood-based, stochastic update). The size and
colour of the circles correspond to investment amount and threshold of
investment, respectively. We note that the most desirable outcomes are closest
to the origin. Figure S8: Average fairness (left) and average cost of
interference (right) as a function of the individual endowment $\theta$ and
the threshold $p_{f}$ (population-based, $\mu=0.01$, deterministic update).
Each row represents a different targeting scheme. The cost of interference is
shown on a logarithmic scale.