# Differential Game Strategies for Social Networks with Self-Interested
Individuals

Hossein B. Jond  Department of Computer Science, VSB-Technical University of
Ostrava, Ostrava-Poruba, Czech Republic

###### Abstract

A social network population engages in collective actions as a direct result
of forming a particular opinion. The strategic interactions among the
individuals acting independently and selfishly naturally portray a
noncooperative game. Nash equilibrium allows for self-enforcing strategic
interactions between selfish and self-interested individuals. This paper
presents a differential game approach to the opinion formation problem in
social networks to investigate the evolution of opinions as a result of a Nash
equilibrium. The opinion of each individual is described by a differential
equation, which is the continuous-time Hegselmann-Krause model for opinion
dynamics with a time delay in input. The objective of each individual is to
seek optimal strategies for her own opinion evolution by minimizing an
individual cost function. Two differential game problems emerge, one for a
population that is not stubborn and another for a population that is stubborn.
The open-loop Nash equilibrium actions and their associated opinion
trajectories are derived for both differential games using Pontryagin’s
principle. Additionally, the receding horizon control scheme is used to
practice feedback strategies where the information flow is restricted by fixed
and complete social graphs as well as the second neighborhood concept. The
game strategies were executed on the well-known Zachary’s Karate Club social
network. The resulting opinion trajectories associated with the game
strategies showed consensus, polarization, and disagreement in final opinions.

Keywords: Game theory; Hegselmann-Krause model; opinion dynamics; receding
horizon; Zachary’s Karate Club

##  1 Introduction

Opinion formation is one of the salient features of social networks. Users of
a network engage through communication mediums and tools and fuse their
opinions with those of other users. However, little is known regarding the
strategies employed by network users. In recent decades, there has been
increasing research attention on opinion dynamics which is the study of the
evolution of public opinions [1, 2].

In many of the models proposed for modeling opinion dynamics, each social
network user holds a numerical opinion and fuses that opinion through repeated
averaging with her neighbors. Among those, the bounded confidence models of
opinion dynamics have attracted more attention [3, 4]. The bounded confidence
concept was incorporated into opinion dynamics by Hegselmann and Krause [4].
In the Hegselmann-Krause (HK) model, a finite number of agents fuse their
opinions only with those of others whose opinions do not differ more than
their confidence bound. The rationale behind the confidence bound concept is
that a user adopts the opinions of those she considers trustworthy. Several
works have studied the extensions of the HK model under various settings [5,
6, 7].

Game theory is a promising tool to model and analyze the strategic
interactions among users with self-interest, conflict, cooperation, and
competition traits in social groups from a mathematical point of view [8]. In
the context of a game, a user’s opinion does not just evolve through a
repeated averaging process. Instead, a user’s strategy for fusing opinions
with others is based on her personal optimization, which models the reward or
loss for each possible combination of strategic interactions between her and
her neighbors. Each user’s strategies must be the best outcome for her
optimization and meanwhile self-enforcing, taking other users’ strategies into
account. Nash equilibrium guarantees all users adopt a self-enforcing plan of
action to comply with. The social actors complying with the Nash equilibrium
move toward their neighbors’ opinions, but in general not sufficiently enough
to achieve the globally minimum social cost [9].

In the past two decades, game theory has been used to study opinion dynamics
in social networks. Static games [10, 11, 12, 13, 14] or evolutionary games
[15, 16, 17, 18] were used in early works and most of the current literature.
Nevertheless, only a few works have theoretically analyzed opinion dynamics
using differential games and mean-field games. These classes of games were
proven to provide mathematically rigorous models of opinion formation in
social networks [19, 20, 21].

Opinion dynamics in the context of differential or dynamics games were noticed
very recently. Opinion dynamics in a social network on graphs were treated
with a dynamic game in [22]. Feedback Nash equilibrium strategies for complete
and incomplete communication graphs were found analytically and numerically,
respectively. Competitive influence maximization in opinion dynamics using
dynamic games was studied in [23]. An efficient algorithm solves the game for
its open-loop equilibrium strategies. A differential game model of opinion
dynamics with an open-loop information structure was introduced in [24]. The
model was extended in [25] to investigate the opinion behavior of stubborn
agents in a social network in the presence of a troll.

In this paper, I use noncooperative differential games to model and analyze
the opinion dynamics of self-interested users in a social network. The opinion
fusion rules are according to the HK opinion dynamics model and are restricted
by a communication graph. In particular, I propose two differential game
problem extensions to the HK opinion dynamics. One is for a social network
that is not stubborn, and the other is for a network that is stubborn. In a
stubborn social network, each user is trying to minimize her disagreement with
her neighbors’ opinions and with her own initial opinion. Stubborn users in
social networks were the subject of extensive research [12, 26]. The explicit
game strategies of Nash equilibrium and their corresponding opinion
trajectories for both differential games were obtained analytically. Three
receding horizon implementations of the open-loop game strategies were
proposed to practice feedback strategies for the non-stubborn social network.

The main contributions of this paper in comparison with closely related works
in [24, 25] are fourfold. First, [24, 25] considered the single integrator
dynamics model for opinion evolution, whereas I utilize the HK opinion
dynamics model. Unlike the single integrator model, the HK model involves the
topological structure of the social network. Second, the cost functions in
[24, 25] involve minimizing disagreements in the network throughout the entire
opinion formation process. In this work, disagreements in the final opinion
are taken into account in the formulation of cost functions. The selection of
cost functions in this manner leads to more compact explicit expressions for
the Nash equilibrium and the opinion trajectories associated with it, which in
turn facilitates acknowledging the emergence of distributed information
fashion in the solution. Third, I consider an input time delay in the
formulation of the differential games. The confidence bound concept in the HK
opinion dynamics model is a matter of feedback strategies. Finally, I
introduced the receding horizon implementation of open-loop game strategies to
practice feedback strategies. Even though a model predictive control (MPC)
scheme was used in [27] to construct feedback control strategies for the HK
opinion formation model in an optimal control framework, the MPC
implementation required solving a sequence of open-loop optimality systems
discretized by an appropriate Runge–Kutta scheme and solved by a nonlinear
conjugate gradient method. The proposed receding horizon implementations use
the explicit solutions that were obtained for the open-loop differential game,
and therefore, the differential game is not solved repeatedly.

The paper is organized as follows. In Section 2, I present two differential
game models based on the HK opinion dynamics. In Section 3, I derive the open-
loop Nash equilibrium solution and the associated opinion trajectory with it
for both differential game problems. The receding horizon implementations of
the open-loop strategies were presented in Section 4. In Section 5, the
results from the previous sections are implemented on a real-world social
network to observe the evolution of individuals’ opinions when they are non-
stubborn and stubborn. Conclusions and future works are discussed in Section
6.

##  2 Differential Game Formulation of Opinion Dynamics

Consider a social network of $n$ agents indexed $1$ through $n$ on a
communication graph $\mathcal{G}(\mathcal{V},\mathcal{E})$. The set of
vertices $\mathcal{V}=\\{1,\cdots,n\\}$ corresponds to the set of agents. Each
edge $(i,j)\in\mathcal{E}$ represents a mutual opinion flow between node $i$
and node $j$. The set of neighbors of vertex $i$ is denoted by
$\mathcal{N}_{i}=\\{j\in\mathcal{V}:(i,j)\mbox{ or }(j,i)\in\mathcal{E},j\neq
i\\}$. I make the following assumption. The social graph $\mathcal{G}$ is
connected. The connectivity of $\mathcal{G}$ means at least one globally
reachable node (a root node of a spanning tree on the graph) and vice versa.
In other words, $\mathcal{N}_{i}\neq\emptyset$ or
$\lvert\mathcal{N}_{i}\rvert\neq 0$ for all $i\in\mathcal{V}$.

Let $x_{i}(t)\in\mathit{\mathbb{R}}$ be the opinion of agent $i$ at time
$t\in[0,t_{f}]$ where $t_{f}$ is a terminal time. In the HK model, the
evolution of $x_{i}(t)$ at each stage $k=0,1,\cdots$ is as follows

$x_{i}(k+1)=\frac{1}{\lvert\mathcal{N}_{i}\rvert}\sum_{j\in\mathcal{N}_{i}}x_{j}(k).$
(1)

In this model, each agent’s opinion at each stage is the average opinion of
her graph neighbors. The graph neighbors here are equivalent to the bounded
confidence concept in the original HK model. An agent with the confidence
bound $\epsilon_{i}>0$ takes only those agents $j$ into account whose opinions
differ from her own not bigger than her confidence bound. The set of such
agents $j$ is denoted by $N_{i}(t)=\\{j\in\mathcal{V}:\lvert
x_{i}(t)-x_{j}(t)\rvert\leq\epsilon_{i}\\}$ which in terms of a time-invariant
social graph $\mathcal{G}(\mathcal{V},\mathcal{E})$, is equivalent to the set
of the graph neighbors for agent $i$ as defined before, i.e.,
$\mathcal{N}_{i}$. Another interpretation for $\mathcal{N}_{i}$ could be the
set of agents whom a particular agent $i$ trusts to share and fuse opinion
[28].

Define $u_{i}(t)\in\mathit{\mathbb{R}}$ as agent $i$’s influence effort or
simply her control input at time $t\in[0,t_{f}]$. The HK model (1) with the
time-delayed control input in continuous time is given by

$
\dot{x}_{i}(t)=\frac{1}{\lvert\mathcal{N}_{i}\rvert}\sum_{j\in\mathcal{N}_{i}}x_{j}(t)-x_{i}(t)+b_{i}u_{i}(t-\tau),$
(2)

where $\tau>0$ is an input delay and $b_{i}$ is a nonzero constant.

The HK model applies to a non-stubborn social network whose population of
agents does not hold any prejudices. The process of opinion formation in a
rational, non-stubborn social network at the individual level can be subject
to each agent trying to minimize her disagreement with her graph neighbors
while, in the meantime, expending the least influence effort. An appropriate
cost function that characterizes such behavior or preferences in a social
network for agent $i\in\mathcal{V}$ to minimize is

$J_{i}=\frac{1}{\lvert\mathcal{N}_{i}\rvert}\sum_{j\in\mathcal{N}_{i}}\big{(}x_{i}(t_{f})-x_{j}(t_{f})\big{)}^{2}+\int_{0}^{t_{f}}r_{i}u_{i}^{2}(t-\tau)~{}\mathrm{dt},
$ (3)

where $r_{i}\in\mathit{\mathbb{R}}$ is a positive scalar ($r_{i}>0$). The cost
function in (3) has two terms. The first term averages the sum of
disagreements between the final opinions of each agent and her graph
neighbors. The second term is the weighted control or influence effort made
during the entire opinion formation process. In this work, I refer to the
optimization problem in (2) and (3) as the non-stubborn optimization of the
continuous-time HK opinion dynamics model.

Suppose that the agents of the social network are stubborn, meaning that they
take their prejudices into account in the process of opinion formation. The
initial opinions $x_{i0}$ are referred to as the agents’ prejudices. Agents
with prejudices (i.e., $x_{i0}\neq 0$) are stubborn. In the course of
optimization, stubborn agents are trying to minimize their disagreement with
their (graph) neighbors as well as their terminal time opinion deviation from
their initial opinion. The cost function for a stubborn agent
$i\in\mathcal{V}$ to minimize is

$\displaystyle\tilde{J}_{i}$
$\displaystyle=\omega_{i}\big{(}x_{i}(t_{f})-x_{i0}\big{)}^{2}+\frac{1-\omega_{i}}{\lvert\mathcal{N}_{i}\rvert}\sum_{j\in\mathcal{N}_{i}}\big{(}x_{i}(t_{f})-x_{j}(t_{f})\big{)}^{2}+\int_{0}^{t_{f}}r_{i}u_{i}^{2}(t-\tau)~{}\mathrm{dt},
$ (4)

where $0\leq\omega_{i}\leq 1$ is the stubbornness coefficient. A larger
$\omega_{i}$ indicates agent $i$’s stronger stubbornness to her prejudices.
Note that when $\omega_{i}=0$, (4) reduces to (3) while for $\omega_{i}=1$, it
means at the terminal time the agent only is trying to minimize her final
opinion deviation from her initial opinion. An agent with $\omega_{i}=1$ is
totally stubborn. I refer to the optimization problem in (2) and (4) as the
stubborn optimization of the continuous-time HK opinion dynamics model.

In the control community, both optimization problems that emerged in this work
are known as differential game problems [29]. In the context of a differential
game, each agent of the network is referred to as a player. In this context,
each player seeks the control $u_{i}(t)$ that minimizes her cost function
$J_{i}$ or $\tilde{J}_{i}$ with the given initial opinions, subject to the
continuous-time HK opinion evolution equation (2). In other words, the players
in the game seek to minimize their cost functions in order to find their
control or influence strategies $u_{i}(t)$ while their opinions evolve
according to the differential equation (2). The behavior of self-interested
players in the game of opinion formation is best reflected via noncooperative
game theory. Under the framework of noncooperative games, the players can not
make binding agreements, and therefore, the solution (i.e., the Nash
equilibrium) has to be self-enforcing, meaning that once it is agreed upon,
nobody has the incentive to deviate from [30]. Throughout the paper, I use the
words user, agent, player, and individual interchangeably.

##  3 Open-loop Nash Equilibrium

Nash equilibrium is the main solution concept in noncooperative game
scenarios. A Nash equilibrium is a strategy combination of all players in the
game with the property that no one can gain a lower cost by unilaterally
deviating from it. The open-loop Nash equilibrium is defined as a set of
admissible actions ($u_{1}^{*},\cdots,u_{n}^{*}$) if for all admissible
($u_{1},\cdots,u_{n}$) the inequalities
$J_{i}(u_{1}^{*},\cdots,u_{i-1}^{*},u_{i}^{*}\\\
,u_{i+1}^{*},\cdots,u_{n}^{*})\leq
J_{i}(u_{1}^{*},\cdots,u_{i-1}^{*},u_{i},u_{i+1}^{*},\cdots,u_{n}^{*})$ hold
for $i\in\\{1,\cdots,n\\}$ where $u_{i}\in\Gamma_{i}$ and $\Gamma_{i}$ is the
admissible strategy set for player $i$. The noncooperative differential game
and the unique Nash equilibrium associated with it are discussed in [29].

In the following subsections, I present the open-loop Nash equilibrium
solutions and the associated opinion trajectories with the equilibrium actions
for both of the previously introduced optimization problems. Before that, I
define the following vectors and matrices to restate the optimization problems
in a compact form. These matrix definitions are borrowed from the standard
literature on graph theory.

Define $A_{i}=[a_{ij}]$ where

$a_{ij}=\left\\{\begin{array}[]{ll}1&\text{if }(i,j)\in\mathcal{E}\text{ and
}i\neq j,\\\ 0&\text{if }(i,j)\notin\mathcal{E}\text{ and }i\neq j,\\\
0&\text{if }i=j,\end{array}\right.$

to be the adjacency matrix for each agent $i\in\mathcal{V}$. The degree matrix
is $D_{i}=\mathrm{diag}(0,\cdots,\lvert\mathcal{N}_{i}\rvert,\cdots,0)$ where
”$\mathrm{diag}{·}$” stands for diagonal matrix. The graph Laplacian matrix
for each agent $i$ is defined as

$L_{i}=D_{i}-A_{i}.$ (5)

The global adjacency, degree, and Laplacian matrices are $A=\sum_{i}A_{i}$,
$D=\sum_{i}D_{i}$, and $L=\sum_{i}L_{i}$. All the aforementioned matrices are
symmetric. Additionally, let
$W_{i}=\mathrm{diag}(0,\cdots,\omega_{i},\cdots,0)$ and $W=\sum_{i}W_{i}$.
Define vectors $x(t)=[x_{1}(t),\cdots,x_{n}(t)]^{\top}$,
$B_{i}=[0,\cdots,b_{i},\cdots,0]^{\top}$, and matrix $\Lambda=D^{-1}A-I$.

###  3.1 Non-stubborn social network

The non-stubborn optimization in (2) and (3) is restated in compact form as
follows

$\displaystyle\quad\min_{u_{i}}~{}J_{i}(u_{i}(t-\tau))=\frac{1}{\lvert\mathcal{N}_{i}\rvert}x^{\top}(t_{f})L_{i}x(t_{f})+\int_{0}^{t_{f}}r_{i}u_{i}^{2}(t-\tau)~{}\mathrm{dt},\quad
i=1,\ldots,n,$ (6) $\displaystyle{s.t.}$ $\displaystyle\quad\dot{x}(t)=\Lambda
x(t)+\sum_{i=1}^{n}B_{i}u_{i}(t-\tau),\quad x(0)=x_{0},$

The presence of the Laplacian $L_{i}$ in the cost function above is due to its
sum-of-squares property (see [31]).

$
x^{\top}(t_{f})L_{i}x(t_{f})=\sum_{j\in\mathcal{N}_{i}}\big{(}x_{i}(t_{f})-x_{j}(t_{f})\big{)}^{2}.$

######  Theorem 1.

The unique Nash equilibrium actions and the associated opinion trajectory with
these equilibrium actions for opinion formation in a non-stubborn social
network as the noncooperative differential game in (6) are given by

$\displaystyle
u_{i}(t)=-\frac{1}{r_{i}\lvert\mathcal{N}_{i}\rvert}\hat{B}_{i}^{\top}\mathrm{e}^{(t_{f}-t)\Lambda^{\top}}\hat{L}_{i}H^{-1}(t_{f}-\tau)\mathrm{e}^{(t_{f}-2\tau)\Lambda}x(\tau),$
(7) $\displaystyle
x(t+\tau)=\Big{(}\mathrm{e}^{t\Lambda}-\mathrm{e}^{\tau\Lambda}\Psi(t)\Delta
H^{-1}(t_{f}-\tau)\mathrm{e}^{(t_{f}-2\tau)\Lambda}\Big{)}x(\tau),$ (8)

where

$\displaystyle H(t_{f}-\tau)=I+\Psi(t_{f}-\tau)\Delta,$ (9)
$\displaystyle\Psi(t)=[\Psi_{1}(t),\cdots,\Psi_{n}(t)],$ (10)
$\displaystyle\Delta=[\frac{1}{\lvert\mathcal{N}_{1}\rvert}\hat{L}_{1},\cdots,\frac{1}{\lvert\mathcal{N}_{n}\rvert}\hat{L}_{n}]^{\top},$
(11)
$\displaystyle\Psi_{i}(t,0)=\int_{0}^{t}\mathrm{e}^{(t-s)\Lambda}S_{i}\mathrm{e}^{(t-s)\Lambda^{\top}}~{}\mathrm{ds},$
(12) $\displaystyle
S_{i}=\frac{1}{r_{i}}\hat{B}_{i}\hat{B}_{i}^{\top},\quad\hat{B}_{i}=\mathrm{e}^{-\tau\Lambda}B_{i},\quad\hat{L}_{i}=\mathrm{e}^{\tau\Lambda^{\top}}L_{i}\mathrm{e}^{\tau\Lambda}.$
(13)

###### Proof.

Before proceeding with applying the necessary optimality conditions, one
should address the input delay. A common approach to dealing with the input-
delayed linear dynamical system in (6) is to apply an integral transformation
to obtain a delay-free linear dynamical system [32]. Below, I convert the
input-delayed differential game in (6) to a delay-free differential game
problem.

The cost function in (6) can be decomposed by

$\displaystyle J_{i}(u_{i}(t))$
$\displaystyle=\frac{1}{\lvert\mathcal{N}_{i}\rvert}x^{\top}(t_{f})L_{i}x(t_{f})+\int_{0}^{\tau}r_{i}u_{i}^{2}(t)~{}\mathrm{dt}+\int_{0}^{t_{f}-\tau}r_{i}u_{i}^{2}(t)~{}\mathrm{dt},
$ (14)

The middle integral term on the right-hand side in (14) is a constant since
the control does not take place for $t\in[0,\tau[$. Therefore, the
minimization of $J_{i}$ is equivalent to the minimization of

$J_{i}(u_{i}(t))=\frac{1}{\lvert\mathcal{N}_{i}\rvert}x^{\top}(t_{f})L_{i}x(t_{f})+\int_{0}^{t_{f}-\tau}r_{i}u_{i}^{2}(t)~{}\mathrm{dt}.
$ (15)

The solution of the linear system in (6) at $t+\tau$ is given by

$\displaystyle x(t+\tau)$
$\displaystyle=\mathrm{e}^{(t+\tau)\Lambda}x_{0}+\int_{0}^{t+\tau}\mathrm{e}^{(t+\tau-s)\Lambda}\sum_{i=1}^{n}B_{i}u_{i}(s-\tau)~{}\mathrm{ds}$
$\displaystyle=\mathrm{e}^{\tau\Lambda}\Big{(}\mathrm{e}^{t\Lambda}x_{0}+\int_{0}^{t}\mathrm{e}^{(t-s)\Lambda}\sum_{i=1}^{n}B_{i}u_{i}(s-\tau)~{}\mathrm{ds}+\int_{t}^{t+\tau}\mathrm{e}^{(t-s)\Lambda}\sum_{i=1}^{n}B_{i}u_{i}(s-\tau)~{}\mathrm{ds}\Big{)}.$
(16)

The first and second terms inside the outer bracket pair on the right-hand
side in (3.1) denote the solution of the linear system in (6) at $t$.
Therefore, (3.1) can be rewritten as

$\displaystyle x(t+\tau)$
$\displaystyle=\mathrm{e}^{\tau\Lambda}\left(x(t)+\int_{t}^{t+\tau}\mathrm{e}^{(t-s)\Lambda}\sum_{i=1}^{n}B_{i}u_{i}(s-\tau)~{}\mathrm{ds}\right)$
$\displaystyle=\mathrm{e}^{\tau\Lambda}\left(x(t)+\int_{t-\tau}^{t}\mathrm{e}^{(t-s-\tau)\Lambda}\sum_{i=1}^{n}B_{i}u_{i}(s)~{}\mathrm{ds}\right)$
$\displaystyle=\mathrm{e}^{\tau\Lambda}y(t),$ (17)

where $y(t)$ is a delay-free transformation. By letting $t=0$ and
$t=t_{f}-\tau$, we obtain $\mathrm{e}^{-\tau\Lambda}x(\tau)=y(0)$ and
$x(t_{f})=\mathrm{e}^{\tau\Lambda}y(t_{f}-\tau)$, respectively. By
substituting (3.1) into the cost function in (6), I have

$\displaystyle J_{i}(u_{i}(t))$
$\displaystyle=\frac{1}{\lvert\mathcal{N}_{i}\rvert}\big{(}\mathrm{e}^{\tau\Lambda}y(t_{f}-\tau)\big{)}^{\top}L_{i}\big{(}\mathrm{e}^{\tau\Lambda}y(t_{f}-\tau)\big{)}+\int_{0}^{t_{f}-\tau}r_{i}u_{i}^{2}(t)~{}\mathrm{dt}$
$\displaystyle=\frac{1}{\lvert\mathcal{N}_{i}\rvert}y^{\top}(t_{f}-\tau)\big{(}\mathrm{e}^{\tau\Lambda^{\top}}L_{i}\mathrm{e}^{\tau\Lambda}\big{)}y(t_{f}-\tau)+\int_{0}^{t_{f}-\tau}r_{i}u_{i}^{2}(t)~{}\mathrm{dt}.
$ (18)

The time derivative of (3.1) is given by

$\displaystyle\mathrm{e}^{\tau\Lambda}\dot{y}(t)=\dot{x}(t+\tau)=\Lambda
x(t+\tau)+\sum_{i=1}^{n}B_{i}u_{i}(t),$

or equivalently,

$\displaystyle\dot{y}(t)=\mathrm{e}^{-\tau\Lambda}\Lambda
x(t+\tau)+\sum_{i=1}^{n}\mathrm{e}^{-\tau\Lambda}B_{i}u_{i}(t).$ (19)

Substituting $x(t+\tau)=\mathrm{e}^{\tau\Lambda}y(t)$ into (19) finally yields
the delay-free dynamics

$\displaystyle\dot{y}(t)$
$\displaystyle=\mathrm{e}^{-\tau\Lambda}\Lambda\mathrm{e}^{\tau\Lambda}y(t)+\sum_{i=1}^{n}\mathrm{e}^{-\tau\Lambda}B_{i}u_{i}(t).$
(20)

Note that if matrices $A_{0}$ and $B_{0}$ commute, i.e.,
$A_{0}B_{0}=B_{0}A_{0}$, then
$B_{0}\mathrm{e}^{A_{0}}=\mathrm{e}^{A_{0}}B_{0}$ and
$\mathrm{e}^{A_{0}}\mathrm{e}^{B_{0}}=\mathrm{e}^{A_{0}+B_{0}}$ (see Fact
11.14.2. in [33]). Thereby, (20) is simplified as

$\displaystyle\dot{y}(t)$ $\displaystyle=\Lambda
y(t)+\sum_{i=1}^{n}\mathrm{e}^{-\tau\Lambda}B_{i}u_{i}(t).$ (21)

Using the new state dynamics (21), cost function (3.1) and matrix notations in
(13), the new optimization problem becomes

$\displaystyle\quad\min_{u_{i}}~{}J_{i}(u_{i}(t))=\frac{1}{\lvert\mathcal{N}_{i}\rvert}y^{\top}(t_{f}-\tau)\hat{L}_{i}y(t_{f}-\tau)+\int_{0}^{t_{f}-\tau}r_{i}u_{i}^{2}(t)~{}\mathrm{dt},\quad
i=1,\ldots,n,$ (22) $\displaystyle{s.t.}$
$\displaystyle\quad\dot{y}(t)=\Lambda
y(t)+\sum_{i=1}^{n}\hat{B}_{i}u_{i}(t),\quad
y(0)=\mathrm{e}^{-\tau\Lambda}x(\tau).$

Now, I apply the conditions obtained from Pontryagin’s principle to the delay-
free optimization (22).

Define the Hamiltonian

$\mathcal{H}_{i}=r_{i}u_{i}^{2}(t)+\lambda_{i}^{\top}(t)\Big{(}\Lambda
y(t)+\sum_{i=1}^{n}\hat{B}_{i}u_{i}(t)\Big{)},$ (23)

where $\lambda_{i}(t)$ is a co-state vector. According to Pontryagin’s
principle, the necessary conditions for optimality are
$\frac{\partial\mathcal{H}_{i}}{\partial u_{i}}=0$ and
$\dot{\lambda}_{i}(t)=-\frac{\partial\mathcal{H}_{i}}{\partial y}$. Applying
the necessary conditions on the Hamiltonian yield

$\displaystyle u_{i}(t)=-\frac{1}{r_{i}}\hat{B}_{i}^{\top}\lambda_{i}(t),$
(24) $\displaystyle\dot{\lambda}_{i}(t)=-\Lambda^{\top}\lambda_{i}(t),$ (25)

with the terminal condition

$\lambda_{i}(t_{f})=\frac{1}{\lvert\mathcal{N}_{i}\rvert}\hat{L}_{i}y(t_{f}-\tau).$
(26)

The solution of (25) is uniquely determined by

$\lambda_{i}(t)=\mathrm{e}^{(t_{f}-t)\Lambda^{\top}}\lambda_{i}(t_{f}).$ (27)

Substituting this solution into (24) yields

$u_{i}(t)=-\frac{1}{r_{i}}\hat{B}_{i}^{\top}\mathrm{e}^{(t_{f}-t)\Lambda^{\top}}\lambda_{i}(t_{f}).$
(28)

Substituting (24) into the opinion dynamics in (6) and then using (28), I get

$\displaystyle\dot{y}(t)$ $\displaystyle=\Lambda
y(t)-\sum_{i=1}^{n}S_{i}\lambda_{i}(t)$ $\displaystyle=\Lambda
y(t)-\sum_{i=1}^{n}S_{i}\mathrm{e}^{(t_{f}-t)\Lambda^{\top}}\lambda_{i}(t_{f}).$
(29)

The solution of (3.1) at $t$ is given by

$y(t)=\mathrm{e}^{t\Lambda}y(0)-\sum_{i=1}^{n}\Psi_{i}(t)\lambda_{i}(t_{f}),$
(30)

where $\Psi_{i}(t)$ is defined in (12).

Let
$\lambda(t_{f})=[\lambda_{1}^{\top}(t_{f}),\cdots,\lambda_{n}^{\top}(t_{f})]^{\top}$.
Using notation (10), solution (30) becomes

$y(t)=\mathrm{e}^{t\Lambda}y(0)-\Psi(t)\lambda(t_{f}).$ (31)

Stacking (26) for $i=1,\cdots,n$ yields

$\lambda(t_{f})=\Delta y(t_{f}-\tau)$ (32)

with $\Delta$ defined in (11). Substituting $\lambda(t_{f})$ from (32) then
into (31) at $t_{f}-\tau$ yields

$\displaystyle
y(t_{f}-\tau)=\mathrm{e}^{(t_{f}-\tau)\Lambda}y(0)-\Psi(t_{f}-\tau)\Delta
y(t_{f}-\tau),$

which can be rewritten as

$\displaystyle\big{(}I+\Psi(t_{f}-\tau)\Delta\big{)}y(t_{f}-\tau)=\mathrm{e}^{(t_{f}-\tau)\Lambda}y(0).$
(33)

Using the notation $H(t_{f}-\tau)$ in (9), the compact form of (33) is

$\displaystyle
y(t_{f}-\tau)=H^{-1}(t_{f}-\tau)\mathrm{e}^{(t_{f}-\tau)\Lambda}y(0).$ (34)

If the game has a unique open-loop Nash equilibrium, then (33) is satisfied
for any arbitrary $y(0)$ and $y(t_{f}-\tau)$. Equivalently, if matrix
$H^{-1}(t_{f}-\tau)$ has an inverse for any arbitrary $y(t_{f}-\tau)$, the
unique equilibrium actions exist and could be calculated for all
$t\in[0,t_{f}-\tau]$. By substituting (34) into (26) and re-substituting (26)
in (24), I obtain (7).

Substituting $\lambda(t_{f})$ from (32) into (31) and then re-submitting
$y(t_{f}-\tau)$ from (34), I have

$\displaystyle y(t)$
$\displaystyle=\mathrm{e}^{t\Lambda}y(0)-\Psi(t)\lambda(t_{f})$
$\displaystyle=\mathrm{e}^{t\Lambda}y(0)-\Psi(t)\Delta y(t_{f}-\tau)$
$\displaystyle=\mathrm{e}^{t\Lambda}y(0)-\Psi(t)\Delta
H^{-1}(t_{f}-\tau)\mathrm{e}^{(t_{f}-\tau)\Lambda}y(0).$ (35)

Substituting $y(t)=\mathrm{e}^{-\tau\Lambda}x(t+\tau)$ and
$y(0)=\mathrm{e}^{-\tau\Lambda}x(\tau)$ into (3.1) and after simplifications,
the state trajectory for opinions in (8) appears. This concludes the proof. ∎

######  Remark 1.

For a delay-free optimization problem (6), i.e., $\tau=0$, matrices
$\hat{L}_{i}$ and $\hat{B}_{i}$ in the equilibrium actions (7) reduce to
$L_{i}$ and $B_{i}$, respectively. From the definition of the Laplacian matrix
$L_{i}$ in (5), it can be easily figured out that all nonzero elements of
$L_{i}$ are only in the $i$th row and column. Moreover, the nonzero elements
of the $i$th row and column are at the indices $j\in\mathcal{N}_{i}$. Based on
this structure, it can be deduced that the matrix product
$L_{i}H^{-1}(t_{f})\mathrm{e}^{t_{f}\Lambda}x_{0}$ only requires the initial
$x_{0}$ entries for $\forall j\in\mathcal{N}_{i}$ in $x_{0}$. Thus, I can draw
the conclusion that the equilibrium actions (7) are distributed in the sense
that each agent only uses local information of her own and her graph neighbors
without using any global information of the communication graph.

###  3.2 Stubborn social network

The stubborn optimization in (2) and (4) in compact form is

$\displaystyle\quad\min_{u_{i}}~{}\tilde{J}_{i}(x_{0},u_{i}(t-\tau))=$
$\displaystyle\big{(}x(t_{f})-x_{0}\big{)}^{\top}W_{i}\big{(}x(t_{f})-x_{0}\big{)}+\frac{1-\omega_{i}}{\lvert\mathcal{N}_{i}\rvert}x^{\top}(t_{f})L_{i}x(t_{f})+\int_{0}^{t_{f}}r_{i}u_{i}^{2}(t-\tau)~{}\mathrm{dt},\quad
i=1,\ldots,n,$ (36) $\displaystyle{s.t.}$
$\displaystyle\quad\dot{x}(t)=\Lambda
x(t)+\sum_{i=1}^{n}B_{i}u_{i}(t-\tau),\quad x(0)=x_{0}.$

######  Theorem 2.

The unique Nash equilibrium actions and the associated opinion trajectory with
these equilibrium actions for opinion formation in a stubborn social network
as the noncooperative differential game in (3.2) are given by (37) and (38),
respectively, shown at the bottom of the next page.

$\displaystyle u$
${}_{i}(t)=-\frac{1}{r_{i}}\hat{B}_{i}^{\top}\mathrm{e}^{(t_{f}-t)\Lambda^{\top}}\Big{[}\big{(}\hat{W}_{i}+\frac{1-\omega_{i}}{\lvert\mathcal{N}_{i}\rvert}\hat{L}_{i}\big{)}\hat{H}^{-1}(t_{f}-\tau)\big{(}\mathrm{e}^{(t_{f}-2\tau)\Lambda}x(\tau)+\Psi(t_{f}-\tau)\Omega
x_{0}\big{)}-\tilde{W}_{i}x_{0}\Big{]},$ (37) $\displaystyle x$
$\displaystyle(t+\tau)=\mathrm{e}^{t\Lambda}x(\tau)-\mathrm{e}^{\tau\Lambda}\Psi(t)\Big{[}\big{(}\hat{\Delta}+\Gamma\big{)}\hat{H}^{-1}(t_{f}-\tau)\Big{(}\mathrm{e}^{(t_{f}-2\tau)\Lambda}x(\tau)+\Psi(t_{f}-\tau)\Omega
x_{0}\Big{)}-\Omega x_{0}\Big{]},$ (38)

where

$\displaystyle\tilde{H}(t_{f}-\tau)=I+\Psi(t_{f}-\tau)\big{(}\hat{\Delta}+\Gamma\big{)},$
(39) $\displaystyle\Omega=[\tilde{W}_{1},\cdots,\tilde{W}_{n}]^{\top},$ (40)
$\displaystyle\Gamma=[\hat{W}_{1},\cdots,\hat{W}_{n}]^{\top},$ (41)
$\displaystyle\tilde{\Delta}=[\frac{1-\omega_{1}}{\lvert\mathcal{N}_{1}\rvert}\hat{L}_{1},\cdots,\frac{1-\omega_{n}}{\lvert\mathcal{N}_{n}\rvert}\hat{L}_{n}]^{\top},$
(42)
$\displaystyle\hat{W}_{i}=\mathrm{e}^{\tau\Lambda^{\top}}W_{i}\mathrm{e}^{\tau\Lambda},\quad\tilde{W}_{i}=2\mathrm{e}^{\tau\Lambda^{\top}}W_{i}.$
(43)

###### Proof.

Substituting the transformation
$x(t_{f})=\mathrm{e}^{\tau\Lambda}y(t_{f}-\tau)$ into the cost function in
(3.2), I have

$\displaystyle\tilde{J}_{i}(x_{0},u_{i}(t))$
$\displaystyle=\big{(}\mathrm{e}^{\tau\Lambda}y(t_{f}-\tau)-x_{0}\big{)}^{\top}W_{i}\big{(}\mathrm{e}^{\tau\Lambda}y(t_{f}-\tau)-x_{0}\big{)}$
$\displaystyle+\frac{1-\omega_{i}}{\lvert\mathcal{N}_{i}\rvert}y^{\top}(t_{f}-\tau)\hat{L}_{i}y(t_{f}-\tau)+\int_{0}^{t_{f}-\tau}r_{i}u_{i}^{2}(t)~{}\mathrm{dt}$
$\displaystyle=y^{\top}(t_{f}-\tau)\mathrm{e}^{\tau\Lambda^{\top}}W_{i}\mathrm{e}^{\tau\Lambda}y(t_{f}-\tau)-2y^{\top}(t_{f}-\tau)\mathrm{e}^{\tau\Lambda^{\top}}W_{i}x_{0}+x_{0}^{\top}W_{i}x_{0}$
$\displaystyle+\frac{1-\omega_{i}}{\lvert\mathcal{N}_{i}\rvert}y^{\top}(t_{f}-\tau)\hat{L}_{i}y(t_{f}-\tau)+\int_{0}^{t_{f}-\tau}r_{i}u_{i}^{2}(t)~{}\mathrm{dt}$
(44)

Here, $x_{0}^{\top}W_{i}x_{0}$ is a constant. Then, (3.2) is equivalent to

$\displaystyle\tilde{J}_{i}(x_{0},u_{i}(t))$
$\displaystyle=y^{\top}(t_{f}-\tau)\hat{W}_{i}y(t_{f}-\tau)-y^{\top}(t_{f}-\tau)\tilde{W}x_{0}$
$\displaystyle+\frac{1-\omega_{i}}{\lvert\mathcal{N}_{i}\rvert}y^{\top}(t_{f}-\tau)\hat{L}_{i}y(t_{f}-\tau)+\int_{0}^{t_{f}-\tau}r_{i}u_{i}^{2}(t)~{}\mathrm{dt},$
(45)

where $\hat{W}_{i}$ and $\tilde{W}_{i}$ are defined in (43). Therefore, the
delay-free optimization becomes

$\displaystyle\min_{u_{i}}~{}\tilde{J}_{i}(x_{0},u_{i}(t))=y^{\top}(t_{f}-\tau)\hat{W}_{i}y(t_{f}-\tau)-y^{\top}(t_{f}-\tau)\tilde{W}_{i}x_{0}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad+\frac{1-\omega_{i}}{\lvert\mathcal{N}_{i}\rvert}y^{\top}(t_{f}-\tau)\hat{L}_{i}y(t_{f}-\tau)+\int_{0}^{t_{f}-\tau}r_{i}u_{i}^{2}(t)~{}\mathrm{dt},\quad
i=1,\ldots,n,$ (46) $\displaystyle{s.t.}$
$\displaystyle\quad\dot{y}(t)=\Lambda
y(t)+\sum_{i=1}^{n}\hat{B}_{i}u_{i}(t),\quad
y(0)=\mathrm{e}^{-\tau\Lambda}x(\tau).$

Defining the Hamiltonian in (23) and applying the necessary conditions for
optimality yield (24) and (25) with the terminal condition

$\lambda_{i}(t_{f})=(\hat{W}_{i}+\frac{1-\omega_{i}}{\lvert\mathcal{N}_{i}\rvert}\hat{L}_{i})y(t_{f}-\tau)-\tilde{W}_{i}x_{0}.$
(47)

Stacking (47) for $i=1,\cdots,n$ yields

$\lambda(t_{f})=\big{(}\tilde{\Delta}+\Gamma\big{)}y(t_{f}-\tau)-\Omega x_{0}$
(48)

with $\Omega$, $\Gamma$, and $\hat{\Delta}$ given in (40-42), respectively.

Substituting $\lambda(t_{f})$ from (48) then into (31) at $t_{f}-\tau$ yields

$\displaystyle y(t_{f}-\tau)$
$\displaystyle=\mathrm{e}^{(t_{f}-\tau)\Lambda}y(0)-\Psi(t_{f}-\tau)\big{(}\tilde{\Delta}+\Gamma\big{)}y(t_{f}-\tau)+\Psi(t_{f}-\tau)\Omega
x_{0},$

which can be rewritten as

$\displaystyle\Big{(}I+\Psi(t_{f}-\tau)\big{(}$
$\displaystyle\tilde{\Delta}+\Gamma\big{)}\Big{)}y(t_{f}-\tau)=\mathrm{e}^{(t_{f}-\tau)\Lambda}y(0)+\Psi(t_{f}-\tau)\Omega
x_{0}.$ (49)

Using the notation $\hat{H}(t_{f}-\tau)$ in (39), the compact form of (49) is

$\displaystyle
y(t_{f}-\tau)=\hat{H}^{-1}(t_{f}-\tau)\Big{(}\mathrm{e}^{(t_{f}-\tau)\Lambda}y(0)+\Psi(t_{f}-\tau)\Omega
x_{0}\Big{)}.$ (50)

The game has a unique open-loop Nash equilibrium if matrix
$\hat{H}(t_{f}-\tau)$ is nonsingular. By substituting (50) into (47) and re-
substituting (47) into (27) and then into (24), I obtain (37). Substituting
$y(t_{f}-\tau)$ from (50) into (48), then re-submitting (48) into (31), and
using $y(t)=\mathrm{e}^{-\tau\Lambda}x(t+\tau)$ and
$y(0)=\mathrm{e}^{-\tau\Lambda}x(\tau)$, I get (38). The proof is complete. ∎

######  Remark 2.

Equilibrium actions (37) could be judged similarly to Remark 1.

######  Remark 3.

If $\omega_{i}=0$ for all $i=1,\cdots,n$, then the matrices $W_{i}$,
$\hat{W}_{i}$, $\tilde{W}_{i}$ for all $i=1,\cdots,n$, $\Omega$, and $\Gamma$
will be zero matrices and therefore, the results of Theorem 2, i.e., (37) and
(38) will reduces to the results of Theorem 1, i.e., (7) and (8),
respectively.

##  4 Receding Horizon Implementation of Game Strategies

The differential games proposed in Section 2 are offline optimizations of
opinion formation in social networks with self-interested individuals. At the
beginning of the game, the individuals determine their strategies and act
accordingly over the entire time interval. The open-loop Nash equilibrium
strategies in (7) and (37) depend on information only from the beginning of
the game. However, players in the game of opinion formation naturally have a
tendency to base their decisions on the current information in the network, so
feedback strategies rather than open-loop strategies are in demand. Feedback
information differential games are problematic due to the solvability issues
of the coupled partial differential equations they convert to [34].

In this work, I use the receding horizon control scheme to practice feedback
strategies. In this control scheme, also known as model predictive control
(MPC) [35] at the beginning, the optimization problem is solved to determine
the open-loop Nash equilibrium strategies over the fixed time horizon, and
then the first input is applied. At the next time step, the time horizon of
the previously solved optimization is shifted one step forward, taking into
account the current information of the network, a new optimization forms,
which is then solved, and the first input is applied. This process is repeated
at every future time step.

Before proposing a receding horizon implementation of open-loop Nash
strategies in (7) and (37), I define
$P_{i}(t_{f},t)=\frac{1}{\lvert\mathcal{N}_{i}\rvert}\mathrm{e}^{(t_{f}-t)\Lambda^{\top}}\hat{L}_{i}H^{-1}(t_{f}-\tau)$
and rewrite (7) as

$\displaystyle
u_{i}(t)=-\frac{1}{r_{i}}\hat{B}_{i}^{\top}P_{i}(t_{f},t)\mathrm{e}^{(t_{f}-2\tau)\Lambda}x(\tau).$
(51)

To rewrite the opinion trajectory $x(t+\tau)$ associated with the equilibrium
actions in (51) in terms of $P_{i}$, I revisit (30), shown at the bottom of
the next page,

$\displaystyle y(t)$
$\displaystyle=\mathrm{e}^{t\Lambda}y(0)-\sum_{i=1}^{n}\Psi_{i}(t,0)\lambda_{i}(t_{f})=\mathrm{e}^{t\Lambda}y(0)-\sum_{i=1}^{n}\int_{0}^{t}\mathrm{e}^{(t-s)\Lambda}S_{i}\mathrm{e}^{(t-s)\Lambda^{\top}}\lambda_{i}(t_{f})~{}\mathrm{ds}$
$\displaystyle=\mathrm{e}^{t\Lambda}y(0)-\sum_{i=1}^{n}\int_{0}^{t}\mathrm{e}^{(t-s)\Lambda}S_{i}\mathrm{e}^{(t-s)\Lambda^{\top}}\frac{1}{\lvert\mathcal{N}_{i}\rvert}\hat{L}_{i}y(t_{f}-\tau)~{}\mathrm{ds}$
$\displaystyle=\mathrm{e}^{t\Lambda}y(0)-\sum_{i=1}^{n}\int_{0}^{t}\mathrm{e}^{(t-s)\Lambda}S_{i}\mathrm{e}^{(t-s)\Lambda^{\top}}\frac{1}{\lvert\mathcal{N}_{i}\rvert}\hat{L}_{i}H^{-1}(t_{f}-\tau)\mathrm{e}^{(t_{f}-\tau)\Lambda}y(0)~{}\mathrm{ds}$
$\displaystyle=\Big{(}\mathrm{e}^{t\Lambda}-\sum_{i=1}^{n}\int_{0}^{t}\mathrm{e}^{(t-s)\Lambda}S_{i}P_{i}(t,s)~{}\mathrm{ds}~{}\mathrm{e}^{(t_{f}-\tau)\Lambda}\Big{)}y(0),$
(52)

where
$P_{i}(t,s)=\frac{1}{\lvert\mathcal{N}_{i}\rvert}\mathrm{e}^{(t-s)\Lambda^{\top}}\hat{L}_{i}H^{-1}(t_{f}-\tau)$.
Substituting $y(t)=\mathrm{e}^{-\tau\Lambda}x(t+\tau)$ and
$y(0)=\mathrm{e}^{-\tau\Lambda}x(\tau)$ into (52), I have

$\displaystyle
x(t+\tau)=\Big{(}\mathrm{e}^{t\Lambda}-\mathrm{e}^{\tau\Lambda}\sum_{i=1}^{n}\int_{0}^{t}\mathrm{e}^{(t-s)\Lambda}S_{i}P_{i}(t,s)~{}\mathrm{ds}~{}\mathrm{e}^{(t_{f}-2\tau)\Lambda}\Big{)}x(\tau).$
(53)

At each time instant $t$, assuming that the delay-free vector
$\bar{x}_{0}=x(t)$ or delayed vector $\bar{x}_{0}(\tau)=x(t+\tau)$ is
available, the receding horizon cost function for non-stubborn optimization is
as follows

$\displaystyle\min_{u_{i}}~{}J_{i}(x(t)$
$\displaystyle,u_{i}(t-\tau))=\frac{1}{\lvert\mathcal{N}_{i}\rvert}x^{\top}(t+t_{f})L_{i}x(t+t_{f})+\int_{t}^{t+t_{f}}r_{i}u_{i}^{2}(t-\tau)~{}\mathrm{dt},\quad
i=1,\ldots,n.$ (54)

Following [36], the receding horizon Nash equilibrium actions $\bar{u}_{i}(t)$
and their associated opinion trajectory $\bar{x}(t+\tau)$ are defined as

$\displaystyle\bar{u}_{i}(t)=-\frac{1}{r_{i}}\hat{B}_{i}^{\top}P_{i}(t_{f},0)\mathrm{e}^{(t_{f}-2\tau)\Lambda}\bar{x}_{0}(\tau),$
(55)
$\displaystyle\bar{x}(t+\tau)=\Big{(}\mathrm{e}^{t\Lambda}-\mathrm{e}^{\tau\Lambda}\sum_{i=1}^{n}\int_{0}^{t}\mathrm{e}^{(t-s)\Lambda}S_{i}P_{i}(t,0)~{}\mathrm{ds}~{}\mathrm{e}^{(t_{f}-2\tau)\Lambda}\Big{)}\bar{x}_{0}(\tau).$
(56)

In the following subsections, I present three implementations of the receding
horizon scheme.

###  4.1 Fixed Social Graph

First, I assume that each individual in the social network takes only the
opinions of her immediate neighbors on a fixed social graph into account when
determining the set of individuals whose opinions differ from her own not
bigger than her confidence bound. So that the social graph stays connected, I
assume that each agent chooses a confidence bound so that at least one
neighbor’s opinion doesn’t differ by more than her confidence bound. The
proposed receding horizon implementation of Nash equilibrium strategies on a
fixed social graph is presented in Algorithm 1. Instead of applying only the
first input at time $t$, the receding horizon implementation is applied over
the interval $[t,t+\sigma[$ (where $\tau<\sigma<t_{f}$) to accommodate the
delay.

Algorithm 1 Receding horizon implementation of Nash equilibrium strategies on
a fixed social graph over any interval $[t,t+\sigma[$ ($\tau<\sigma<t_{f}$)

1:for $i=1,\cdots,n$ do

2: for $\forall j\in\mathcal{N}_{i}$ do

3: if $\lvert x_{i}(t)-x_{j}(t)\rvert\leq\epsilon_{i}$ then

4: $\mathcal{N}_{i}^{tmp}\Leftarrow{\text{add}~{}}j$

5: end if

6: end for

7: ${\text{form
matrices}~{}}D_{i},A_{i},L_{i}{\text{~{}using}~{}}\mathcal{N}_{i}^{tmp}$

8:end for

9:${\text{form matrix}~{}}\Lambda$

10:for $i=1,\cdots,n$ do

11: ${\text{form
matrices}~{}}\hat{L}_{i},\hat{B}_{i},S_{i},\Phi_{i}(t_{f}-\tau)$

12:end for

13:${\text{form matrices}~{}}\Phi(t_{f}-\tau),\Delta,H(t_{f}-\tau)$

14:${\text{for time interval}~{}[t,t+\tau[:~{}}$

15:for $i=1,\cdots,n$ do

16: $\bar{u}_{i}(s)\Leftarrow 0,s\in[t,t+\tau[$

17:end for

18:$x(s)\Leftarrow\mathrm{e}^{(t+s)\Lambda}\bar{x}_{0},s\in[t,t+\tau[$

19:$\bar{x}_{0}(\tau)\Leftarrow\mathrm{e}^{\tau\Lambda}\bar{x}_{0}$

20:${\text{for time interval}~{}[t+\tau,t+\sigma[:~{}}$

21:for $i=1,\cdots,n$ do

22: $\bar{u}_{i}(s)\Leftarrow{\text{use the right side in}~{}}(\ref{eq:Nash-
nonstub-rh}),s\in[t+\tau,t+\sigma[$

23:end for

24:$\bar{x}(s+\tau)\Leftarrow{\text{use the right side in}~{}}(\ref{eq:Nash-
nonstub-tr-rh}),s\in[t+\tau,t+\sigma[$

###  4.2 Complete Social Graph

Here, I assume that the social graph is complete and that each agent $i$
determines the set of her neighbors by examining the opinion values of all
individuals in the network. The proposed receding horizon implementation of
Nash equilibrium strategies on a complete social graph is presented in
Algorithm 2. The complete social graph scenario could also be considered
equivalent to a time-varying social graph in the sense that, at each receding
horizon implementation, the social graph’s topology varies to capture the
time-varying interaction network.

Algorithm 2 Receding horizon implementation of Nash equilibrium strategies on
a complete social graph over any interval $[t,t+\sigma[$ ($\tau<\sigma<t_{f}$)

1:for $i=1,\cdots,n$ do

2: for $j=1,\cdots,n$ do

3: if $i\neq j$ then

4: if $\lvert x_{i}(t)-x_{j}(t)\rvert\leq\epsilon_{i}$ then

5: $\mathcal{N}_{i}\Leftarrow{\text{add}~{}}j$

6: end if

7: end if

8: end for

9: ${\text{form matrices}~{}}D_{i},A_{i},L_{i}$

10:end for

11:go to line 9 in Algorithm 1

###  4.3 Second Neighborhood in Social Graph

In graph theory, the second neighborhood refers to all the nodes that are
exactly two edges away from a given node in a graph [37]. In the context of a
social graph where an edge pairs two friends, the second neighborhood concept
is equivalent to friends-of-friends. The second neighborhood concept is a
useful tool from graph theory that helps model the structure and connectivity
of social networks beyond direct connections between individuals. In the third
receding horizon implementation in Algorithm 3, each agent, besides her
immediate graph neighbors, also takes the agents in her second neighborhood
into account.

Algorithm 3 Receding horizon implementation of Nash equilibrium strategies
based on the second neighborhood over any interval $[t,t+\sigma[$
($\tau<\sigma<t_{f}$)

1:for $i=1,\cdots,n$ do

2: for $\forall j\in\mathcal{N}_{i}$ do

3: if $\lvert x_{i}(t)-x_{j}(t)\rvert\leq\epsilon_{i}$ then

4: $\mathcal{N}_{i}^{tmp}\Leftarrow{\text{add}~{}}j$

5: end if

6: for $\forall k\in\mathcal{N}_{j}$ do

7: if $\lvert x_{i}(t)-x_{k}(t)\rvert\leq\epsilon_{i}$ then

8: $\mathcal{N}_{i}^{tmp}\Leftarrow{\text{add}~{}}k$

9: end if

10: end for

11: end for

12: ${\text{form
matrices}~{}}D_{i},A_{i},L_{i}{~{}\text{using}~{}}\mathcal{N}_{i}^{tmp}$

13:end for

14:go to line 9 in Algorithm 1

In all receding horizon implementations of game strategies in Algorithm 1\- 3,
I assume that at each execution time, each agent $i$ adopts a confidence bound
value $\epsilon_{i}$ that guarantees a non-empty set $\mathcal{N}_{i}$, so the
connectivity of the social graph is always preserved. Note that the receding
horizon implementations above accommodate social networks with a heterogeneous
population of users with different confidence bounds. I should also mention
that the receding horizon implementation for a stubborn network is a more
challenging task that is left for future work.

##  5 Simulations

In this section, I apply the theoretical results to the well-known social
network of Zachary’s Karate Club [38]. With its underlying social graph given
in Fig. 1, Zachary’s Karate Club network, created by Wayne Zachary in 1977, is
a social network between the members of a karate club at a US university. This
network has 34 nodes and 78 edges, where the nodes and edges represent the
club members and their mutual friendships.

Figure 1: Zachary’s Karate Club network.

The continuous-time HK model in (2) or its compact equation in (6) can be used
to illustrate the formation of a particular opinion over time. The time
interval is chosen $t_{f}=10$ and the users’ opinions are initially uniformly
spaced on the interval $[-1,1)$, i.e.,
$x_{0}=\\{-1,-0.94,\cdots,0.92,0.98\\}$. The evolution of club members’
opinions prior to any optimization (i.e., $u_{i}(t)=0$) under the receding
horizon scheme in Algorithm 1 is shown in Fig. 2. As it is seen, the club
members’ opinions reach a consensus about the average opinion in the network.
In the first sub-figure from the left, all individuals have adopted the
confidence bound value $\epsilon_{i}=1.2$. Running Algorithm 1 multiple times
showed that for a lower value than $\epsilon_{i}=1.2$ on a fixed social graph
using the initial opinion vector above, the set of neighbors $\mathcal{N}_{i}$
for some individuals becomes empty and their opinions cannot be calculated.
The next two sub-figures depict the opinion trajectories for the situation
when the confidence bound value is increased to $\epsilon_{i}=1.5$ and
$\epsilon_{i}=2$, respectively, where the effect on opinions is insignificant.

Figure 2: Opinion trajectories associated with the HK model for Zachary’s
network prior to optimization.

For self-interested members of Zachary’s Karate Club social network, whose
underlying opinion dynamics is the HK model, the open-loop game strategies in
Theorem 1 and Theorem 2 can be used to illustrate their opinion formation. Let
$b_{i}=1$. For the stubborn and totally stubborn ($\omega_{i}=1~{}\forall
i\in\mathcal{V}$) Zachary’s network, the opinion trajectories as a result of
optimization (3.2) are shown in Fig. 3. As captured in (4), the prejudices of
the stubborn members influence the formation of their final opinions. It can
be observed that there is disagreement among the final opinions in the
(totally) stubborn network. A large enough $r_{i}~{}\forall i\in\mathcal{V}$
can force a consensus, as the individuals in the stubborn network will try to
minimize their influence effort rather than their disagreement with others and
their prejudices. The rationale behind this is that with a large enough
$r_{i}$, the corresponding optimization boils down to the minimization of the
influence effort term.

Figure 3: Opinion trajectories associated with the game strategies for the
stubborn and totally stubborn Zachary’s network.

Consider the non-stubborn Zachary’s network with a fixed graph, illustrated in
Fig. 1. The resulting opinion trajectories from the receding horizon
implementation in Algorithm 1 are shown in Fig. 4. Interestingly, for a delay-
free network, the final opinions form two clusters, while introducing a small
delay $\tau=0.4$ reduces the clusters to one, and for a slightly bigger delay
$\tau=0.6$, a consensus is reached.

Figure 4: Opinion trajectories associated with the game strategies for non-
stubborn Zachary’s network on a fixed graph.

For the non-stubborn Zachary’s network on a complete graph, the resulting
opinion trajectories from the receding horizon implementation in Algorithm 2
are shown in Fig. 5. Although in a delay-free network, short-term clusters of
opinions appear, the final opinions reach a consensus. In the presence of a
delay, the consensus is realized smoothly.

Figure 5: Opinion trajectories associated with the game strategies for non-
stubborn Zachary’s network on a complete graph.

Finally, for the non-stubborn Zachary’s network with a fixed graph and using
the second neighborhood concept in graphs, the resulting opinion trajectories
from the receding horizon implementation in Algorithm 3 are shown in Fig. 6. I
should note that multiple visits to the graph nodes are allowed at each
execution of Algorithm 3. For a delay-free network, the final opinions
polarize, while in a delayed network they reach a consensus. In the delay-free
non-stubborn networks in Fig.4-6, the confidence bound values are the lowest
for which the network stays connected and the corresponding trajectories could
be calculated. These values were experienced with multiple runs of their
corresponding algorithms.

Figure 6: Opinion trajectories associated with the game strategies for non-
stubborn Zachary’s network using the second neighborhood concept.

##  6 Conclusions

In this paper, differential games were utilized to formulate opinion formation
in non-stubborn and stubborn social networks, where the game’s dynamics is the
continuous-time Hegselmann-Krause model with a time delay in input. The
explicit expressions for open-loop Nash equilibrium strategies and their
associated opinion trajectories for both the non-stubborn and stubborn
populations were found. Furthermore, feedback strategies were practiced for
non-stubborn social networks through receding horizon implementations of open-
loop game strategies. The receding horizon implementations of game strategies,
depending on how big the confidence bounds and time delay are, show consensus,
polarization, or clustering of opinions in the network. The receding horizon
scheme for a stubborn network can be addressed in new work. A future direction
of research could be analyzing the opinion dynamics in social networks on
directed or signed graphs.

## Acknowledgment

This work was supported by SGS, VŠB - Technical University of Ostrava, Czech
Republic, under grant No. SP2023/012 “Parallel processing of Big Data IX”.

## References

  * [1] Haiming Liang and Cong-Cong Li and Yucheng Dong and Yanping Jiang.  The fusion process of interval opinions based on the dynamic bounded confidence.  Information Fusion, 29:112-119, 2016.
  * [2] Noah E. Friedkin.  The Problem of Social Control and Coordination of Complex Systems in Sociology: A Look at the Community Cleavage Problem.  IEEE Control Systems Magazine, 35(3):40-51, 2015.
  * [3] Jan Christian Dittmer.  Consensus formation under bounded confidence.  Nonlinear Analysis: Theory, Methods & Applications, 47(7):4615-4621, 2001.
  * [4] Rainer Hegselmann and Ulrich Krause.  Opinion Dynamics and Bounded Confidence Models, Analysis and Simulation.  Journal of Artificial Societies and Social Simulation, 5(3):1-2, 2002\.
  * [5] Chen, Ge and Su, Wei and Ding, Songyuan and Hong, Yiguang.  Heterogeneous Hegselmann–Krause Dynamics With Environment and Communication Noise.  IEEE Transactions on Automatic Control, 65(8):3409-3424, 2020.
  * [6] Jan Lorenz.  Heterogeneous bounds of confidence: Meet, discuss and find consensus!.  Complexity, 15(4):43-52, 2010.
  * [7] Francesco Vasca and Carmela Bernardo and Raffaele Iervolino.  Practical consensus in bounded confidence opinion dynamics.  Automatica, 129:109683, 2021.
  * [8] M.J. Osborne.  An Introduction to Game Theory.  Oxford University Press, 2009.
  * [9] David Bindel and Jon Kleinberg and Sigal Oren.  How bad is forming your own opinion?.  Games and Economic Behavior,92:248-265, 2015.
  * [10] Bhawalkar, Kshipra and Gollapudi, Sreenivas and Munagala, Kamesh.  Coevolutionary Opinion Formation Games.  Association for Computing Machinery, New York, NY, USA, 2013.
  * [11] Grabisch, Michel and Mandel, Antoine and Rusinowska, Agnieszka and Tanimura, Emily.  Strategic Influence in Social Networks.  Mathematics of Operations Research,43(1):29-50, 2018.
  * [12] Javad Ghaderi and R. Srikant.  Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate.  Automatica, 50(12):3209-3215, 2014.
  * [13] Diodato Ferraioli and Paul W. Goldberg and Carmine Ventre.  Decentralized dynamics for finite opinion games.  Theoretical Computer Science, 648:96-115, 2016.
  * [14] Etesami, Seyed Rasoul and Başar, Tamer.  Game-Theoretic Analysis of the Hegselmann-Krause Model for Opinion Dynamics in Finite Dimensions.  IEEE Transactions on Automatic Control, 60(7):1886-1897, 2015\.
  * [15] Di Mare, Alessandro and Latora, Vito.  Opinion Formation Models Based on Game Theory.  International Journal of Modern Physics C, 18(09):1377-1395, 2007.
  * [16] Fei Ding and Yun Liu and Bo Shen and Xia-Meng Si.  An evolutionary game theory model of binary opinion formation.  Physica A: Statistical Mechanics and its Applications, 389(8):1745-1752, 2010\.
  * [17] Changwei Huang and Yongzhao Hou and Wenchen Han.  Coevolution of consensus and cooperation in evolutionary Hegselmann–Krause dilemma with the cooperation cost.  Chaos, Solitons & Fractals, 168:113215, 2023. 2009\.
  * [18] Wan, Pengfei and Wang, Xiaoming and Min, Geyong and Wang, Liang and Lin, Yaguang and Yu, Wangyang and Wu, Xiaojun.  Optimal Control for Positive and Negative Information Diffusion Based on Game Theory in Online Social Networks.  IEEE Transactions on Network Science and Engineering, 10(1):426-440, 2023.
  * [19] Bauso, D. and Tembine, H. and Başar, T.  Opinion Dynamics in Social Networks through Mean-Field Games.  SIAM Journal on Control and Optimization, 54(6):3225-3257, 2016.
  * [20] Banez, Reginald A. and Gao, Hao and Li, Lixin and Yang, Chungang and Han, Zhu and Poor, H. Vincent.  Modeling and Analysis of Opinion Dynamics in Social Networks Using Multiple-Population Mean Field Games.  IEEE Transactions on Signal and Information Processing over Networks, 8:301-316, 2022.
  * [21] Bingchang Wang and Yong Liang.  Robust mean field social control problems with applications in analysis of opinion dynamics.  International Journal of Control, 95:3309 - 3325, 2020.
  * [22] Jiang, Hui and Mazalov, Vladimir and Gao, Hongwei and Wang, Chen.  Opinion Dynamics Control in a Social Network with a Communication Structure.  Dynamic Games and Applications, 13:412–434, 2021.
  * [23] Seyed Rasoul Etesami.  Open-Loop Equilibrium Strategies for Dynamic Influence Maximization Game Over Social Networks.  IEEE Control Systems Letters, 6:1496-1500, 2021\.
  * [24] Muhammad Umar B. Niazi and A. Bülent Özgüler.  A Differential Game Model of Opinion Dynamics: Accord and Discord as Nash Equilibria.  Dynamic Games and Applications, 11:137-160, 2021\.
  * [25] Aykut Yildiz and Arif Bülent Özgüler.  Opinion dynamics of stubborn agents under the presence of a troll as differential game.  Turkish J. Electr. Eng. Comput. Sci., 29(7):3259–3269, 2021.
  * [26] Ye Tian and Long Wang.  Opinion dynamics in social networks with stubborn agents: An issue-based perspective.  Automatica, 96:213-223, 2018\.
  * [27] Wongkaew, Suttida and Caponigro, Marco and Borzì, Alfio.  On the control through leadership of the Hegselmann–Krause opinion formation model.  Mathematical Models and Methods in Applied Sciences, 25(03):565-585, 2015\.
  * [28] Babakhanbak, Saghar and Kavousi, Kaveh and Farokhi, Fardad.  Application of a time delay neural network for predicting positive and negative links in social networks.  Turkish Journal of Electrical Engineering & Computer Sciences, 24: 2825-2837, 2016.
  * [29] J. Engwerda.  LQ Dynamic Optimization and Differential Games.  Wiley, 2005.
  * [30] E. van Damme.  Refinements of the Nash Equilibrium Concept.  Lecture Notes in Computer Science, 1983.
  * [31] Jond, Hossein Barghi and Vasif, Nabiyev.  On the finite horizon Nash equilibrium solution in the differential game approach to formation control.  Journal of Systems Engineering and Electronics, 30(6): 1233-1242, 2019.
  * [32] Zhou, Yusheng and Wang, Zaihua.  Optimal Feedback Control for Linear Systems with Input Delays Revisited.  Journal of Optimization Theory and Applications, 163: 977–984, 2014.
  * [33] D.S. Bernstein.  Matrix Mathematics: Theory, Facts, and Formulas (Second Edition).  Princeton University Press, 2009.
  * [34] L. C. EVANS and P. E. SOUGANIDIS.  Differential Games and Representation Formulas for Solutions of Hamilton-Jacobi-Isaacs Equations.  Indiana University Mathematics Journal, 33(5): 773–797, 1984.
  * [35] W.H. Kwon and S.H. Han.  Receding Horizon Control: Model Predictive Control for State Models, Springer London, 2005.
  * [36] Gu, Dongbing.  A Differential Game Approach to Formation Control.  IEEE Transactions on Control Systems Technology, 16(1):85-93, 2008.
  * [37] Bouya, Farid.  Some Results on Seymour’s Second-Neighborhood Conjecture and on Decompositions of Graphs.  PhD thesis, Louisiana State University, 2020.
  * [38] Wayne W. Zachary.  An Information Flow Model for Conflict and Fission in Small Groups.  Journal of Anthropological Research, 33(4):452–473, 1977.