Opinion dynamics, Projected dynamical systems, Utility maximization, Game theory, Multi-agent systems.

1 Introduction↩︎

Multi-agent modeling and study of opinion dynamics finds widespread applications in sociology, economics, and other fields. Many of the complex decision making problems that individuals, organizations, corporations and governments engage in often boil down to problems of allocating limited resources (such as time or money) among multiple options. In such scenarios, there is a strong interplay between agents’ self-interest, their heterogeneous resource constraints and social influences on the formation of opinions about resource allocation. To the best of our knowledge, currently there are no models and studies that explore such complex mechanisms behind opinion formation. Thus, in this paper, we seek to model and study such important phenomena.

Literature review↩︎

Classical models, including the French-DeGroot (FD), the Abelson, the Taylor, the Friedkin-Johnsen (FJ), the Hegselmann-Krause (HK), the Altafini, and the Deffuant-Weisbuch (DW) models form the foundation of opinion dynamics research [1]–[3] and have inspired numerous extensions and refinements. Many of these models studied single-topic discussions with scalar opinions. Extensions to vector-valued opinions (multi-topic scenarios) have also been explored [4]–[10]. Some notable works adopt a game-theoretic and utility-maximization approach to model opinion dynamics [11]–[15].

In many applications, opinions are naturally or forced to be constrained within a bounded space. Models for such scenarios also exist. For instance, [16] models opinions as unit vectors with varying orientations. References [5], [6], [17] restrict opinions to a real interval, which is particularly useful when opinions represent an agent’s sentiments. Another work [18] proposes a model where opinions are confined on the surface of a sphere.

The impact of limited or constrained resources on decision-making has been explored across various disciplines, including psychology, economics, and transportation. For a comprehensive overview, see [19], [20] and the references therein. Notably, [19] examines how financial constraints influence consumer behavior from four distinct angles: resource scarcity, choice restriction, social comparison, and environmental uncertainty. Motivated to study such effects, our recent works [21], [22] introduced a nonlinear opinion dynamics model with a resource penalty in the utility function, enforcing soft constraints to keep opinions bounded. The applicability of the FJ model to resource allocation problems is examined in [23]. A closely related work is [24], which introduces models (based on the DW and HK models) where opinions are confined to a probability simplex. Here, the opinions represent each agent’s proposal for allocating a fixed global budget across multiple projects.

Statement of contributions↩︎

1. To the best of our knowledge, this is the first work to model and study opinion dynamics for general resource allocation scenarios. Our model captures heterogeneous goals and hard resource constraints of the agents. Moreover, we adopt a projected dynamical systems framework to model opinion dynamics under constraints on opinions, which is also a first in the literature.

2. We employ a game-theoretic framework, where the proposed projected dynamics are derived from the unconstrained dynamics which in turn are derived from the agent’s utility function, assuming that each agent myopically seeks to maximize its utility.

3. Unlike our prior works [21], [22], which focused on a single-topic model with soft resource penalty, this paper considers multiple topics and enforces hard resource constraints. Our model allows for agents with heterogeneous budgets.

Notation↩︎

The sets of natural numbers, real numbers, non-negative real numbers and positive real numbers are denoted by \(\mathbb{N},\mathbb{R}\), \(\mathbb{R}_{\geq0}\) and \(\mathbb{R}_{>0}\), respectively. Given \(\mathbf{x}, \mathbf{y}\in \mathbb{R}^{n}\) and a diagonal matrix \(\mathbf{D} \in \mathbb{R}_{\geq 0}^{n\times n}\); \(\|\mathbf{x}\| :=\sqrt{\mathbf{x}^\top \mathbf{x}}\), \(\|\mathbf{x}\|_{\mathbf{D}}:= \sqrt{\mathbf{x}^\top \mathbf{D}\mathbf{x}}\) and \(\langle \mathbf{x},\mathbf{y}\rangle :=\mathbf{x}^\top \mathbf{y}\). For \(\mathbf{x}\in \mathbb{R}^p\), \(\mathsf{supp}(\mathbf{x})\) denotes its support, and \(\mathrm{diag}(x_{1},\ldots,x_p)\) denotes a diagonal matrix with \(\mathbf{x}\) as its main diagonal. Similarly, for \(\mathbf{D}_1, \dots, \mathbf{D}_n\in \mathbb{R}^{p \times p}\), \(\mathrm{blkdiag}(\mathbf{D}_1, \dots, \mathbf{D}_n)\) denotes a block diagonal matrix with \(\mathbf{D}_i\) as its diagonal blocks. For real matrices \(\mathbf{A}\), \(\mathbf{B}\); their Kronecker product is \(\mathbf{A} \otimes \mathbf{B}\) and \(\|\mathbf{A}\|\) denotes the induced matrix norm. Let \(\mathbf{0}\) denote a vector (of appropriate dimension) with all zero elements. For any \(a \in \mathbb{R}\), \(|a|\) denotes its absolute value. For any \(\mathbf{x}_{i} \in \mathbb{R}^{m}\), \(x_i^j\) denotes its \(j^{\text{th}}\) element.

For \(\mathcal{C}\subset \mathbb{R}^{n}\), \(\overline{\mathcal{C}}\) is its closure. The empty set is denoted by \(\varnothing\) . The projection of \(\mathbf{x}\in \mathbb{R}^{n}\) onto a closed, convex and non-empty set \(\mathcal{S}\subset \mathbb{R}^{n}\) is denoted by \(\mathcal{P}_{\mathcal{S}}(\mathbf{x}):=\mathop{\mathrm{argmin}}_{\mathbf{y}\in \mathcal{S}} \|\mathbf{y}- \mathbf{x}\|\). The tangent cone to a set \(\mathcal{X} \subset \mathbb{R}^{n}\) at a point \(\mathbf{x}\in \mathcal{X}\), \(T_{\mathcal{X}}(\mathbf{x}) :=\{ \mathbf{v}\in \mathbb{R}^{n}\,|\,\) \(\exists \{\mathbf{x}_{i}\}_{i \in \mathbb{N}} \in \mathcal{X}, \mathbf{x}_i \to \mathbf{x}\) and \(\exists \{t_{i}\}_{i \in \mathbb{N}}, t_i >0, t_i \to 0,\) such that \(\mathbf{v}= \lim_{i \to \infty}(\mathbf{x}_{i}- \mathbf{x})/t_i \}\).

2 Preliminaries↩︎

A Projected Dynamical System (PDS) is a special type of discontinuous dynamical system that restricts the state to a constraint set. In this work, we limit the definition of a PDS to closed, convex constraint sets and Euclidean projections. For a given closed, convex, non-empty set \(\mathcal{X} \subset \mathbb{R}^p\) and a vector field \(\mathbf{g}: \mathbb{R}^p \to \mathbb{R}^p\), we define the PDS as \[\dot{\mathbf{x}} = \Pi_{\mathcal{X}}(\mathbf{x},-\mathbf{g}(\mathbf{x})) :=\lim_{\delta \to 0^+} \frac{ \mathcal{P}_{\mathcal{X}}(\mathbf{x}- \delta \mathbf{g}(\mathbf{x}))-\mathbf{x}}{\delta} \,,\] which is equivalent to the following dynamics [25], \[\dot{\mathbf{x}} = \mathcal{P}_{T_{\mathcal{X}}(\mathbf{x})}(-\mathbf{g}(\mathbf{x})) \,. \label{eq:pds95def}\tag{1}\] In this paper, we use this representation of the PDS. Since the dynamics 1 is discontinuous, it is essential to first define an appropriate notion of a solution before proceeding with the analysis. Here, we consider solutions of 1 in the Carathéodory sense [26] i.e., absolutely continuous curves that satisfy 1 almost everywhere. It is well known that the equilibrium points of 1 are related to solutions of the following variational inequality (VI) problem [27].

Interestingly, the VI problem is closely connected to several fundamental mathematical frameworks, including nonlinear equations, optimization, complementarity problems, and fixed-point problems [27].

3 Modeling and Problem Setup↩︎

Consider a set \(\mathcal{V}:=\{1,\ldots,n\}\) of \(n\) agents that form opinions about allocation of their limited resources on \(m\) topics indexed by the set \(\mathcal{T}:=\{1,\ldots,m\}\). We aim to study the evolution of these opinions as the agents interact with each other over a social network. We start by defining a utility function for each agent that depends on their preferences and opinions on all topics and the social influence of their neighboring agents. Since the agents’ opinions are about allocation of limited resources among the topics in \(\mathcal{T}\), they constrain their opinions so that a budget constraint is always satisfied. We first derive the unconstrained opinion dynamics from the utility functions, assuming that each agent myopically seeks to maximize its utility. Then, using the unconstrained vector field, we define a projected dynamical system that keeps the opinions of all agents restricted by their budget constraints.

We denote the opinion of agent \(i \in \mathcal{V}\) on topic \(j \in \mathcal{T}\) at time \(t\) as \(z_{i}^{j}(t) \in \mathbb{R}\). We omit the time argument wherever there is no confusion. We let \(\mathbf{z}_{i}:=[z_{i}^{1},\ldots,z_{i}^{m}]^\top \in \mathbb{R}^{m}\) denote the stacked opinions of agent \(i\) on all topics. Similarly, \(\mathbf{z}:=[\mathbf{z}_{1}^\top,\ldots,\mathbf{z}_{n}^\top]^\top \in \mathbb{R}^{mn}\) is the stacked vector of opinions of all agents. The utility of agent \(i \in \mathcal{V}\) is \[\begin{align} U_{i}(\mathbf{z}) & :=- \frac{1}{2} \sum_{j \in \mathcal{T}}w_{i}^{j}\big(z_{i}^{j}- p_{i}^{j} \big)^{2} - \frac{1}{2} \sum_{j \in \mathcal{T}}\sum_{k \in \mathcal{V}}a_{ik}\big(z_{k}^{j}- z_{i}^{j} \big)^{2} \nonumber \\ &= -\frac{1}{2} || \mathbf{z}_{i}-\mathbf{p}_{i}||_{\mathbf{D}_{i}}^2 - \sum_{k \in \mathcal{V}}\frac{a_{ik}}{2} || \mathbf{z}_{k}-\mathbf{z}_{i}||^2. \label{eq:utility} \end{align}\tag{2}\] Here \(p_{i}^{j}\in \mathbb{R}\) is the internal preference of agent \(i \in \mathcal{V}\) on topic \(j \in \mathcal{T}\), while \(\mathbf{p}_{i}\in \mathbb{R}^{m}\) is the vector containing preferences \(p_{i}^{j}\)’s of agent \(i\) on all topics. The topic preference weight \(w_{i}^{j}\in \mathbb{R}_{> 0}\) is the importance that agent \(i \in \mathcal{V}\) attaches to its internal preference on topic \(j \in \mathcal{T}\) and \(\mathbf{D}_{i}:=\mathrm{diag}(w_{i}^{1},\ldots,w_{i}^{m}) \in \mathbb{R}^{m \times m}\). Finally, \(a_{ik}\) is the influence weight of agent \(k\)’s opinions on those of agent \(i\). Let \(\mathbf{A}\) be the matrix with its \((i, k)^{\text{th}}\) element as \(a_{ik}\). The inter-agent influence weights implicitly define a weighted social graph \(\mathsf{G}:=\big(\mathcal{V}, \mathcal{L}, \mathbf{A}\big)\), where \(\mathcal{V}\) (the set of agents) is the set of nodes, \(\mathcal{L}\subseteq \mathcal{V}\times \mathcal{V}\) is the set of undirected links and \(\mathbf{A}\) is the weighted adjacency matrix. Note that \(a_{ik}\neq 0\) if and only if \(\{i,k\} \in \mathcal{L}\). Notice that the self loop weights \(a_{ii}\), for any \(i \in \mathcal{V}\), do not affect the utility of the agents. We may assume them to be zero without loss of generality. The self influence of the agents is captured by the preference term in the utility function. In this paper, an agent’s opinions are restricted to a constraint set which we define next. The opinion constraint set for each agent \(i \in \mathcal{V}\) is given by \[\label{eq:constraint95set} \mathcal{K}_{i}:=\{\mathbf{z}_{i}\in \mathbb{R}^{m}\:\mid\: \mathbf{c}_{i}^\top \mathbf{z}_{i}\leq B_{i},\:\mathbf{z}_{i}\geq \mathbf{0}\},\tag{3}\] where \(\mathbf{c}_{i}\in \mathbb{R}^{m}_{>0}\) is a weighing parameter against \(i\)’s budget \(B_i\). Note that \(\mathcal{K}_{i}\) is a closed, bounded and convex polytope.

We assume the following throughout the paper.

1. (Undirected social network.) The graph \(\mathsf{G}=\big(\mathcal{V}, \mathcal{L}, \mathbf{A}\big)\) is undirected, i.e., \(\mathbf{A}=\mathbf{A}^\top\) and connected⁴. \(\bullet\)

2. (Model parameters’ signs.) \(p_{i}^{j}\in \mathbb{R}_{\geq 0}\), \(w_{i}^{j}\in \mathbb{R}_{> 0}\), \(a_{ik}\in \mathbb{R}\), \(\forall k \in \mathcal{V}\), \(B_{i}>0\) and \(\mathbf{c}_{i}> \mathbf{0}\), \(\forall i \in \mathcal{V}\), \(j \in \mathcal{T}\). \(\bullet\)

We discuss the justification for [asmp:param95sign] in the sequel. However, note here that the entries of \(\mathbf{A}\) are allowed to have negative values. The sign of \(a_{ik}\) denotes the type of influence relationship and its magnitude denotes the degree of influence. Using this idea, we define the following.

Some of our results in this paper are applicable to certain specific classes of inter-agent interactions. We list these specific classes in the following assumptions.

1. (No antagonistic relations.) For each agent \(i \in \mathcal{V}\), \(\mathcal{N}_{i}^{e}=\varnothing\). \(\bullet\)

1. (Very weak antagonistic relations.) For each agent \(i \in \mathcal{V}\), \(\min_{j \in \mathcal{T}}\;w_{i}^{j}> 2 \sum_{k \in\mathcal{N}_{i}^{e}}|a_{ik}|\). \(\bullet\)

1. (Weak antagonistic relations.) For each agent \(i \in \mathcal{V}\), \(\big(\min_{j \in \mathcal{T}} \:w_{i}^{j}+ \sum_{k \in \mathcal{V}\setminus \left\{i\right\}}a_{ik}\big) \geq 0.\) \(\bullet\)

Remark 4 justifies our standing assumption [asmp:param95sign] on all model parameters stated earlier. In the following, we first define the unconstrained multi-topic opinion dynamics and then use it to propose the projected opinion dynamics model.

Unconstrained Opinion Dynamics↩︎

Suppose that there are no budget constraints and opinions \(z_{i}^{j}\)’s are allowed to take any real values. We assume that at each infinitesimal time instant, each agent \(i \in \mathcal{V}\) revises its opinion on topic \(j \in \mathcal{T}\) by ascending along the gradient of its utility \(U_{i}\), given in 2 , with respect to its own opinion \(z_{i}^{j}\), while assuming that others do not change their opinions. Thus, for each \(i \in \mathcal{V}\), \[\begin{align} \label{eq:uncontrained95agent95dynamics} \dot{\mathbf{z}}_i = -\mathbf{D}_{i}(\mathbf{z}_{i}-\mathbf{p}_{i}) + \sum_{k \in \mathcal{V}}a_{ik}(\mathbf{z}_{k}-\mathbf{z}_{i}) =:-\mathbf{f}_{i}(\mathbf{z}_{i}, \mathbf{z}_{-i}). \end{align}\tag{4}\] The unconstrained dynamics of all agents can be written as \[\begin{align} \label{eq:uncontrained95dynamics} \dot{\mathbf{z}} = -\mathbf{D}(\mathbf{z}- \mathbf{p}) - (\mathbf{L}\otimes \mathbf{I}_{m})\mathbf{z}=:-\mathbf{f}(\mathbf{z}), \end{align}\tag{5}\] where \(\mathbf{z}_{-i}\in \mathbb{R}^{(n-1)m}\) denotes the opinions of all agents except \(i\), \(\mathbf{D}:=\mathrm{blkdiag}(\mathbf{D}_{1},\ldots,\mathbf{D}_{n}) \in \mathbb{R}^{mn \times mn}\), \(\mathbf{p}:= [\mathbf{p}_{1}^\top,\ldots,\mathbf{p}_{n}^\top]^\top \in \mathbb{R}^{mn}\) and \(\mathbf{L}\) is a symmetric matrix⁵ with elements \(l_{ii}=\sum_{k \in \mathcal{V}\setminus \left\{i\right\}}a_{ik}\) and \(l_{ij} = -a_{ij},\: \forall j\neq i\). We denote the Jacobian of the vector field \(\mathbf{f}(\mathbf{z})\) in 5 by, \[\begin{align} \mathbf{J}:=(\mathbf{D}+\mathbf{L}\otimes\mathbf{I}_{m}). \label{eq:jacobian95mat} \end{align}\tag{6}\]

The terms in the unconstrained dynamics 4 for each topic is similar to Taylor’s model [29] of opinion dynamics when antagonistic relations are absent in the network (i.e., when \(a_{ik}\geq 0\)). In the presence of antagonistic relations, the second term in 4 models the boomerang effect [30], where agents respond to neighbors’ influence by shifting their opinions in the opposite direction, leading to disagreement.

Since the unconstrained dynamics in 4 is obtained by performing gradient ascent on each agent \(i\)’s utility with respect to its opinion \(\mathbf{z}_{i}\), it can be interpreted in continuous time as the instantaneous better-response dynamics of agent \(i\) to its neighbors’ opinions. However, because each agent’s opinions are restricted by individual resource constraints given in 3 , the unconstrained dynamics 5 cannot, in general, ensure feasibility of the opinions at all times. So, we propose a projected version of the opinion update rule.

Projected Opinion Dynamics↩︎

In this work, our aim is to study the effect of limited resources of the agents on their opinion evolution. Hence, we propose a model where the opinions of each agent satisfy their resource constraints 3 at all times. More precisely, the projected dynamical system \[\label{eq:projected95dynamics95agent} \dot{\mathbf{z}}_i = \mathcal{P}_{T_{\mathcal{K}_{i}}(\mathbf{z}_{i})}(-\mathbf{f}_{i}(\mathbf{z}_{i}, \mathbf{z}_{-i})) \,,\tag{7}\] uses the unconstrained gradient ascent direction in 4 and restricts each agent’s opinion evolution within the feasible set perpetually. Again for the sake of convenience, we let \(\mathbf{z}_{-i}\in \mathcal{K}_{-i}:=\bigtimes_{l=1,l\neq i}^{n}\mathcal{K}_{l}\) denote the opinions of all agents except \(i\). The tangent cone \(T_{\mathcal{K}_{i}}(\mathbf{z}_{i})\) to the constraint set \(\mathcal{K}_{i}\) at \(\mathbf{z}_{i}\) is closed and convex because the constraint set \(\mathcal{K}_{i}\) in 3 is closed and convex [31]. Hence, the projection in 7 is unique [32] and consequently, 7 takes the form of a differential equation rather than a differential inclusion. Similarly, we can associate the following projected dynamical system with 5 \[\label{eq:projected95dynamics} \dot{\mathbf{z}} = \mathcal{P}_{T_{\mathcal{K}}(\mathbf{z})}(-\mathbf{f}(\mathbf{z})), \quad\text{where}\: \mathcal{K}:=\textstyle\bigtimes_{i=1}^{n}\mathcal{K}_{i}.\tag{8}\] Note that, the inter-agent opinion coupling in 7 comes through the social term in 2 and the inter-topic opinion coupling comes through the budget constraints given in 3 .

The equivalence between the agents’ dynamics in 7 and 8 can be established as follows. First, note that each agent \(i\)’s constraint set \(\mathcal{K}_{i}\) defined in 3 is closed and convex and therefore Clarke-regular [31]. Since \(\mathcal{K}= \textstyle\bigtimes_{i=1}^{n}\mathcal{K}_{i}\) by definition 8 and each \(\mathcal{K}_{i}\) is Clarke-regular, \(\mathcal{K}\) is Clarke-regular and hence, the tangent cone decomposes as \(T_{\mathcal{K}}(\mathbf{z})= \bigtimes_{i=1}^{n} T_{\mathcal{K}_{i}}(\mathbf{z}_{i}),\:\forall \mathbf{z}\in \mathcal{K}\) [31]. Second, the projection onto the tangent cone in both 7 and 8 is performed using the Euclidean norm. These two facts ensure that the two formulations describe the same opinion evolution.

For simplicity, we will refer to dynamics 7 and 8 by \(\mathrm{PDS}(\mathbf{f}_{i},\mathcal{K}_{i},\mathbf{z}_{-i})\) and \(\mathrm{PDS}(\mathbf{f},\mathcal{K})\) respectively. Finally, we denote the equilibrium points of \(\mathrm{PDS}(\mathbf{f},\mathcal{K})\) by \[\label{eq:eqpt} \mathcal{E}:=\{\mathbf{z}\in \mathcal{K}\:\mid\: \dot{\mathbf{z}}= \mathcal{P}_{T_{\mathcal{K}}(\mathbf{z})}(-\mathbf{f}(\mathbf{z})) = \mathbf{0}\}.\tag{9}\]

We now show that the projected dynamics 7 is also an instantaneous better response dynamics. Specifically, we demonstrate that the projected update direction of each agent \(i \in \mathcal{V}\) in 7 aligns with the unconstrained gradient ascent direction in 4 . The proof (which we omit) of this result is based on [27].

We are now ready to state the goals of this paper.

Objectives↩︎

For the proposed projected opinion dynamics 8 , our primary objective is to study how inter-agent social influence and inter-topic coupling, through agents’ budget constraints, shape opinion formation across different topics. We aim to analyze the long-term evolution of opinions, particularly the convergence and stability properties of the dynamics in 8 . We also aim to investigate the properties of Nash equilibria in the underlying opinion formation game.

4 Asymptotic Behavior of Opinions↩︎

In the following result, we first leverage the affine structure of the unconstrained vector field 5 to establish the existence and uniqueness of the Carathéodory solution to 8 .

Proof: To prove this claim, we first note the following for the vector field \(\mathbf{f}(\mathbf{z})\) defined in 5 , \(\|\mathbf{f}(\mathbf{z})\| \leq \alpha (1+\|\mathbf{z}\|) \:,\forall \mathbf{z}\in \mathcal{K}\) where \(\alpha := \max \{\|\mathbf{D}+(\mathbf{L}\otimes \mathbf{I}_{mn})\|,\| \mathbf{D}\mathbf{p}\| \}\). For any \(\mathbf{z}_1,\mathbf{z}_2 \in \mathcal{K}\), we have \(\left[\mathbf{f}(\mathbf{z}_2)- \mathbf{f}(\mathbf{z}_1)\right]^\top [\mathbf{z}_1-\mathbf{z}_2] \leq \alpha \|\mathbf{z}_1-\mathbf{z}_2\|^2.\) The claim now follows from [27]. \(\blacksquare\)

We now define the variational inequality associated with each agent’s dynamics 7 and establish a connection between the solutions of these VI’s and the single VI associated with 8 . We then relate the solution of this VI to the equilibrium points 9 of the projected dynamics 8 .

Proof: To prove this, observe that for any \(\mathbf{x},\mathbf{z}\in \mathcal{K}\) \[\langle \: \mathbf{f}(\mathbf{z}),\mathbf{x}-\mathbf{z}\ \rangle= \textstyle\sum_{i \in \mathcal{V}}\: \langle \: \mathbf{f}_{i}(\mathbf{z}_{i},\mathbf{z}_{-i}),\mathbf{x}_{i}-\mathbf{z}_{i}\ \rangle. \label{eq:relation95betn95varineq95proof951}\tag{10}\] Suppose \(\mathbf{z}^* \in \mathrm{SOL}(\mathbf{f},\mathcal{K})\). Using 10 , we have \[\textstyle\sum_{i \in \mathcal{V}}\,\, \langle \: \mathbf{f}_{i}(\mathbf{z}_{i}^*,\mathbf{z}_{-i}^*),\mathbf{x}_{i}-\mathbf{z}_{i}^*\ \rangle\geq 0, \: \forall \mathbf{x}\in \mathcal{K}. \label{eq:relation95betn95varineq95proof952}\tag{11}\] Let \(\mathbf{y}^{(i)}:= [\mathbf{z}_{1}^{*\top},\ldots,\mathbf{z}_{i-1}^{*\top},\mathbf{s}_{i}^\top,\mathbf{z}_{i+1}^{*\top},\ldots,\mathbf{z}_{n}^{*\top}]^\top \in \mathcal{K}\), \(\forall \mathbf{s}_i \in \mathcal{K}_{i}\) and \(\forall i \in \{ 1,\ldots,n \}\). With \(\mathbf{x}= \mathbf{y}^{(i)}\), 11 gives \[\begin{align} 0 & \leq \langle \mathbf{f}_{i}(\mathbf{z}_{i}^*,\mathbf{z}_{-i}^*),\mathbf{s}_i-\mathbf{z}_{i}^* \rangle + \textstyle\sum_{j \neq i} \langle \mathbf{f}_j(\mathbf{z}_{j}^*,\mathbf{z}_{-j}^*),\mathbf{z}_{j}^*-\mathbf{z}_{j}^* \rangle \\ & = \langle \mathbf{f}_{i}(\mathbf{z}_{i}^*,\mathbf{z}_{-i}^*),\mathbf{s}_i-\mathbf{z}_{i}^* \rangle, \quad \forall \mathbf{s}_i \in \mathcal{K}_{i}\,. \end{align}\] Hence, \(\mathbf{z}_{i}^* \in \mathrm{SOL}(\mathbf{f}_{i},\mathcal{K}_{i},\mathbf{z}_{-i}^*),\:\forall i \in \mathcal{V}\).

Next, suppose \(\mathbf{z}_{i}^* \in \mathrm{SOL}(\mathbf{f}_{i},\mathcal{K}_{i},\mathbf{z}_{-i}^*)\:, \forall i \in \mathcal{V}\). Then \(\forall i \in \mathcal{V}\), \(\langle \: \mathbf{f}_{i}(\mathbf{z}_{i}^*,\mathbf{z}_{-i}^*),\mathbf{x}_{i}-\mathbf{z}_{i}^*\ \rangle\geq 0,\: \forall \mathbf{x}_{i}\in \mathcal{K}_{i}.\) Then,  10 implies \[\begin{align} 0 \leq \textstyle\sum\limits_{i \in \mathcal{V}} \langle \: \mathbf{f}_{i}(\mathbf{z}_{i}^*,\mathbf{z}_{-i}^*),\mathbf{x}_{i}-\mathbf{z}_{i}^*\ \rangle= \langle \mathbf{f}(\mathbf{z}^*),\mathbf{x}-\mathbf{z}^* \rangle, \,\, \forall \mathbf{x}\in \mathcal{K}\,. \end{align}\] Hence, \(\mathbf{z}^*\in \mathrm{SOL}(\mathbf{f},\mathcal{K})\). The proof is now complete. \(\blacksquare\)

In the next result, we use a well known result from [27] to relate \(\mathcal{E}\), the equilibrium points of \(\mathrm{PDS}(\mathbf{f},\mathcal{K})\), and the solution set of \(\mathrm{VI}(\mathbf{f},\mathcal{K})\) and show that \(\mathcal{E}\) is not empty.

Proof: The claim that \(\mathcal{E}= \mathrm{SOL}(\mathbf{f},\mathcal{K})\) is a direct consequence of  [27]. Next, since \(\mathcal{K}_{i}\) is compact and convex, \(\mathcal{K}\) as defined in 8 is also compact and convex. Further, the vector field \(\mathbf{f}(\mathbf{z})\) is affine and hence continuous in \(\mathcal{K}\). Non-emptiness of \(\mathcal{E}= \mathrm{SOL}(\mathbf{f},\mathcal{K})\) now follows from [27]. \(\blacksquare\)

We can immediately show that any opinion trajectory converges to the set of equilibrium points, which we know is non-empty (due to Lemma 3). First, we define the function \[\begin{align} W(\mathbf{z}) & := \sum_{k \in \mathcal{V}}U_{k}(\mathbf{z}) + 0.5 \,\mathbf{z}^\top(\mathbf{L}\otimes \mathbf{I}_{m})\mathbf{z}\notag \\ & = - 0.5 \, \mathbf{z}^\top \mathbf{J}\mathbf{z}+ \mathbf{z}^\top \mathbf{D}\mathbf{p}- 0.5 \, \mathbf{p}^\top\mathbf{D}\mathbf{p}\,, \label{eq:potential95function} \end{align}\tag{12}\] which will be useful for showing convergence. Later, in Section 5, we show that this function can work as a potential function for the associated non-cooperative game.

Proof: Consider the Lyapunov-like function \(V(\mathbf{z}) :=-W(\mathbf{z})\), with \(W(\cdot)\) defined in 12 . Then, it can be verified that \(\nabla V(\mathbf{z})=\mathbf{f}(\mathbf{z})\). The time derivative of \(V(\mathbf{z})\) along the trajectories of 8 is \(\dot{V}(\mathbf{z}) = \mathbf{f}(\mathbf{z})^\top \mathcal{P}_{T_{\mathcal{K}}(\mathbf{z})}(-\mathbf{f}(\mathbf{z})) \leq 0\). This inequality can be proved using [27] and Cauchy-Bunyakovskii-Schwarz inequality. Now, let us define the set \(\mathcal{W}:=\{\mathbf{z}\in \mathcal{K}\;\mid \; \dot{V}(\mathbf{z})=0\}\). Using [27], we can again conclude that \(\dot{V}(\mathbf{z})=0\) if and only if \(\mathbf{f}(\mathbf{z})=\mathbf{0}\) or \(\mathcal{P}_{T_{\mathcal{K}}(\mathbf{z})}(-\mathbf{f}(\mathbf{z}))=\mathbf{0}\). Since \(\{\mathbf{z}\in \mathcal{K}\;\mid\; \mathbf{f}(\mathbf{z})= \mathbf{0}\} \subseteq \mathcal{E}\), we conclude that \(\mathcal{W}=\mathcal{E}\). Notice that the vector field \(\mathbf{f}(\mathbf{z})\) defined in 5 is affine. Hence, the variational inequality associated with the corresponding \(\mathrm{PDS}(\mathbf{f},\mathcal{K})\) is an Affine Variational Inequality. It is well known that the solution set of an Affine variational inequality is closed [33]. This, along with Lemma 3, implies that \(\mathcal{E}\) is closed. Thus, \(\overline{\mathcal{W}}=\mathcal{E}\). Finally, we apply the invariance principle for discontinuous dynamics [26] to ensure convergence of \(\mathbf{z}(t)\) to the largest invariant set in \(\overline{\mathcal{W}}\), which in our case is the equilibrium set \(\mathcal{E}\) itself. \(\blacksquare\)

In the remaining portion of this section, we leverage the properties of the Jacobian Matrix, \(\mathbf{J}\), of the unconstrained vector field \(\mathbf{f}(\mathbf{z})\) to comment more about the equilibrium set and the asymptotic behavior of the opinion trajectories. In fact, if \(\mathbf{J}\) is positive semi-definite, we can establish that \(\mathcal{E}\) is convex and show convergence of solutions of 8 to an equilibrium point in \(\mathcal{E}\). We formally state these results next.

Proof: To prove Claim [lem:global95monotone95attractivity95and95stability], notice that under the stated assumptions the vector field \(\mathbf{f}(\mathbf{z})\) defined in 5 is monotone on \(\mathcal{K}\). The claim now follows from [27].

Next, to prove Claim [lem:convexity95of95eqm95set], using the hypothesis, note that \(-W(\mathbf{z})\) is convex on \(\mathcal{K}\), since its Hessian \(\mathbf{J}\) is positive semi-definite in \(\mathcal{K}\). From [27], we know that the set \(\mathrm{SOL}(\mathbf{f},\mathcal{K})\) is equal to the set of solutions to the convex optimization problem \(\max_{\mathbf{z}\in \mathcal{K}} W(\mathbf{z})\). Hence, \(\mathrm{SOL}(\mathbf{f},\mathcal{K})\) is convex. The claim now follows from Lemma 3.

Finally, we show Claim [thm:convg95to95eqm95pt]. We know from Claim [lem:convexity95of95eqm95set] and [33] that \(\mathcal{E}\subseteq \mathcal{K}\) is convex and compact. This means for any given \(t \geq 0\), \(\mathop{\mathrm{argmin}}_{\mathbf{y}\in \mathcal{E}} \|\mathbf{z}(t)-\mathbf{y}\|\) is a singleton set. We now show that \(\mathbf{z}(t)\) converges to \(\mathbf{z}^*_{0}\). From Claim [lem:global95monotone95attractivity95and95stability], we know that \(\mathbf{z}^{*}_{0}\) is a global monotone attractor which means \(\|\mathbf{z}(t)-\mathbf{z}^*_0\|\) is non-increasing, \(\forall t \geq 0\). We also know that \(\mathbf{z}(t)\) is continuous, \(\forall t \geq 0\). All of the above observations imply that \(\mathop{\mathrm{argmin}}_{\mathbf{y}\in \mathcal{E}}\|\mathbf{z}(t)-\mathbf{y}\|=\mathbf{z}^*_0\:,\forall t \geq 0\). Additionally, from Theorem 7, we know that \(\mathbf{z}(t)\) converges to \(\mathcal{E}\), i.e., \(\min_{\mathbf{y}\in \mathcal{E}}\|\mathbf{z}(t)-\mathbf{y}\| \to 0\) as \(t \to \infty\). Hence, \(\|\mathbf{z}(t)-\mathbf{z}^*_0\|\to 0\) as \(t \to \infty\). The proof is now complete. \(\blacksquare\)

Note that Theorem 8 precludes the existence of periodic or oscillatory solutions for the dynamics 8 under the assumption that \(\mathbf{J}\) is positive semi-definite. To conclude this section, we provide a stricter result for networks with very weak antagonistic relations Assumption [asmp:WAR95WSI]. In such a scenario, the following result guarantees convergence of the solution \(\mathbf{z}(t)\) to a unique equilibrium point, starting from any initial condition \(\mathbf{z}(0) \in \mathcal{K}\).

Proof: We will show that under Assumption [asmp:WAR95WSI], \(\mathbf{f}(\mathbf{z})\) is strictly monotone⁶ on \(\mathcal{K}\). Firstly, note that the Jacobian matrix \(\mathbf{J}\) defined in 6 is symmetric. Thus, \(\mathbf{f}(\mathbf{z})\) is strictly monotone on \(\mathcal{K}\) if and only if \(\mathbf{J}\) has all positive eigenvalues. For any fixed \(i\in \mathcal{V}\) and \(j \in \mathcal{T}\), the center and radius of the corresponding Gerschgorin discs of \(\mathbf{J}\) are given by \(w_{i}^{j}+ \sum_{k \in \mathcal{V}\setminus \left\{i\right\}}a_{ik}\) and \(\sum_{k \in \mathcal{V}\setminus \left\{i\right\}}|a_{ik}|\), respectively. Using the Gerschgorin disc theorem, it can now be easily verified that the matrix \(\mathbf{J}\) is positive definite under Assumption [asmp:WAR95WSI]. The rest of the claim now follows from Lemma 3, [27] and [27].

\(\blacksquare\)

5 Opinion Formation Game↩︎

In this section, we delve deeper into the properties of the underlying opinion formation game. Recall that each agent \(i \in \mathcal{V}\) is interested in maximizing its utility \(U_i\) given in 2 , by suitably choosing its opinion \(\mathbf{z}_{i}\in \mathcal{K}_{i}\). This framework defines a strategic form game \(\mathcal{G}:=\langle \mathcal{V}, \left(\mathcal{K}_{i}\right)_{i \in \mathcal{V}}, \left(U_{i}\right)_{i \in \mathcal{V}}\rangle\) among the set of agents \(\mathcal{V}\), with the strategy of agent \(i \in \mathcal{V}\) being its opinion \(\mathbf{z}_{i}\in \mathcal{K}_{i}\) and its utility function being \(U_i\).

For this game, we are interested in presenting the properties of the Nash equilibria and relating it to the equilibrium set of the opinion dynamics. Note that, by definition, for a Nash equilibrium \(\mathbf{z}^*\) (if one exists), \(\mathbf{z}_{i}^*\) is agent \(i\)’s best response over all opinions \(\mathbf{z}_{i}\in \mathcal{K}_{i}\) to \(\mathbf{z}_{-i}^* \in \mathcal{K}_{-i}\), the Nash equilibrium opinions of all the other agents. The set of Nash equilibria of the game \(\mathcal{G}\) is \[\begin{align} \notag \mathcal{NE}& :=\{ \mathbf{z}^* \in \mathcal{K}\,\,|\,\, \forall i \in \mathcal{V}, \\ &\quad U_i(\mathbf{z}_{i}^*,\mathbf{z}_{-i}^*) \geq U_i(\mathbf{z}_{i},\mathbf{z}_{-i}^*), \forall \mathbf{z}_{i}\in \mathcal{K}_{i}\}\,. \label{eq:ne} \end{align}\tag{13}\]

We start by relating the equilibria of the opinion dynamics with the Nash equilibria of the opinion formation game.

Proof: Let \(\mathbf{z}^*=(\mathbf{z}_{i}^*,\mathbf{z}_{-i}^*) \in \mathcal{NE}\), the set of Nash equilibria. Then, by definition of Nash equilibrium, \(\mathbf{z}_{i}^* \in \mathop{\mathrm{argmax}}_{\mathbf{z}_{i}\in \mathcal{K}_{i}} U_{i}(\mathbf{z}_{i},\mathbf{z}_{-i}^*),\:\forall i \in \mathcal{V}\). Recall that the unconstrained dynamics 4 for each agent \(i\) is equal to gradient ascent of its utility \(U_i\) with respect to \(\mathbf{z}_{i}\) assuming \(\mathbf{z}_{-i}^*\) to be fixed; i.e., \(\nabla_{\mathbf{z}_{i}}U_i(\mathbf{z}_{i},\mathbf{z}_{-i}^*) = -\mathbf{f}_{i}(\mathbf{z}_{i},\mathbf{z}_{-i}^*)\). From [27], we can conclude that \(\mathbf{z}_{i}^* \in \mathrm{SOL}(\mathbf{f}_{i},\mathcal{K}_{i},\mathbf{z}_{-i}^*),\:\forall i \in \mathcal{V}\). Now, Lemmas 2 and 3 imply that \(\mathbf{z}^*\in \mathcal{E}\).

Next, observe that \(\forall i \in \mathcal{V}\), the Hessian of \(U_{i}(\mathbf{z}_{i},\mathbf{z}_{-i})\) in 2 with respect to \(\mathbf{z}_{i}\) is a diagonal matrix with its diagonal elements being equal to \(-(w_{i}^{j}+\sum_{k \in \mathcal{V}\setminus \left\{i\right\}}a_{ik})\). If Assumption [asmp:WAR] holds, then it is easy to see that this Hessian matrix is negative semidefinite \(\forall \mathbf{z}_{i}\in \mathcal{K}_{i}\). Hence, \(U_{i}(\cdot,\mathbf{z}_{-i})\) is concave on the set \(\mathcal{K}_{i}\), \(\forall i \in \mathcal{V}\). The rest of the claim can now be proved using similar arguments used in proof of [32] for concave functions. \(\blacksquare\)

We conclude this section by showing that the function \(W(\cdot)\) defined earlier in 12 is an exact potential function⁷ of the game \(\mathcal{G}\). This is also useful in showing that a Nash equilibrium always exists for the opinion formation game.

Proof: For any \(i \in \mathcal{V}\), it can be easily verified from 2 and 12 that \(\forall \mathbf{x}_i,\mathbf{y}_i \in \mathcal{K}_{i}\) and \(\forall \mathbf{z}_{-i}\in \mathcal{K}_{-i}\), \[W(\mathbf{x}_i,\mathbf{z}_{-i})-W(\mathbf{y}_i,\mathbf{z}_{-i}) = U_i(\mathbf{x}_i,\mathbf{z}_{-i})-U_i(\mathbf{y}_i,\mathbf{z}_{-i}).\] Thus, \(\mathcal{G}\) is an exact potential game with the potential function \(W(\mathbf{z})\). The existence of a Nash equilibrium is a consequence of the continuity of \(W\) and the compactness of the strategy set \(\mathcal{K}\), which implies that the potential function attains a maximum in the set \(\mathcal{K}\)  [34]. \(\blacksquare\)

It is important to note that in an exact potential game with a potential function \(W(\mathbf{z})\), \(\mathcal{NE}\) is not always equal to \(\mathop{\mathrm{argmax}}_{\mathbf{z}\in \mathcal{K}}W(\mathbf{z})\). In general \(\mathop{\mathrm{argmax}}_{\mathbf{z}\in \mathcal{K}}W(\mathbf{z}) \subseteq \mathcal{NE}\). The next result, which is a consequence of Theorems 8, 10, and 11 equates the two sets when the Jacobian \(\mathbf{J}\) is positive semi-definite. We skip a formal proof.

6 When there are no antagonistic relations↩︎

Here, we analyze the properties of the unique Nash equilibrium of the opinion formation game in the absence of antagonistic relations; i.e., when Assumption [asmp:no95antagonistic95relations] holds. Since Assumption [asmp:no95antagonistic95relations] is a special case of Assumptions [asmp:WAR95WSI] and [asmp:WAR], \(\mathcal{E}=\mathcal{NE}\) and the solution of 8 converges to the unique equilibrium point \(\mathbf{z}^* \in \mathcal{E}\) starting from any \(\mathbf{z}(0) \in \mathcal{K}\). By definition, we know that \(\mathbf{z}^*=(\mathbf{z}_{i}^*,\mathbf{z}_{-i}^*) \in \mathcal{NE}\) if and only if \(\mathbf{z}_{i}^* \in \mathop{\mathrm{argmax}}_{\mathbf{z}_{i}\in \mathcal{K}_{i}} U_{i}(\mathbf{z}_{i},\mathbf{z}_{-i}^*),\:\forall i \in \mathcal{V}\). For any agent \(i \in \mathcal{V}\), using 2 let us re-write the function \(U_i(\mathbf{z}_{i},\mathbf{z}_{-i}^*)\) as \[U_i(\mathbf{z}_{i},\mathbf{z}_{-i}^*) = -0.5 \left\|\mathbf{z}_{i}-\widetilde{\mathbf{p}}_{i}(\mathbf{z}_{-i}^*) \right\|_{\widetilde{\mathbf{D}}_{i}}^{2} - \Delta_{i}(\mathbf{z}_{-i}^*), \label{eq:utility95of95i95given95strategies95of95others}\tag{14}\] where \(\widetilde{\mathbf{D}}_{i}:=\big(\mathbf{D}_{i}+ \sum_{k \in \mathcal{V}\setminus \left\{i\right\}}a_{ik}\mathbf{I}_{m}\big) \in \mathbb{R}^{m \times m}_{\geq 0}\) is a positive diagonal matrix, \(\widetilde{\mathbf{p}}_{i}(\mathbf{z}_{-i}^*):=\widetilde{\mathbf{D}}_{i}^{-1}\big(\mathbf{D}_{i}\mathbf{p}_{i}+ \sum_{k \in \mathcal{V}\setminus \left\{i\right\}}a_{ik}\mathbf{z}_{k}^*\big) \in \mathbb{R}^{m}_{\geq 0}\) and \(2\Delta_{i}(\mathbf{z}_{-i}^*):= \mathbf{p}_{i}^\top\mathbf{D}_{i}\mathbf{p}_{i}+\sum_{k \in \mathcal{V}\setminus \left\{i\right\}}a_{ik}\mathbf{z}_{k}^{*\top}\mathbf{z}_{k}^*-\widetilde{\mathbf{p}}_{i}(\mathbf{z}_{-i}^*)^\top \widetilde{\mathbf{D}}_{i}\widetilde{\mathbf{p}}_{i}(\mathbf{z}_{-i}^*) \in \mathbb{R}\). Henceforth, we omit the arguments of \(\widetilde{\mathbf{p}}_{i}(\mathbf{z}_{-i}^*)\) and \(\Delta_i(\mathbf{z}_{-i}^*)\) for brevity.

Now, consider a particular agent \(i \in \mathcal{V}\). Note that \(\widetilde{\mathbf{p}}_{i}\) and \(\Delta_i\) are independent of \(i\)’s own opinion \(\mathbf{z}_{i}\) and depends solely on its neighbors’ opinions \(\mathbf{z}_{k}^*,\: k \in \mathcal{N}_{i}\). Hence, if \(\mathbf{z}_{-i}^* \in \mathcal{K}_{-i}\) denotes the Nash equilibrium opinions of other agents, then from the above discussion, we can see that the Nash equilibrium opinion \(\mathbf{z}_{i}^*\) of agent \(i\) is the unique solution to the quadratic program \(\min_{\mathbf{z}_{i}\in \mathcal{K}_{i}} 0.5 \left\|\mathbf{z}_{i}-\widetilde{\mathbf{p}}_{i}\right\|_{\widetilde{\mathbf{D}}_{i}}^{2}\). Thus, for each agent \(i \in \mathcal{V}\), its unique Nash equilibrium opinion vector \(\mathbf{z}_{i}^* \in \mathcal{K}_{i}\) is the weighted projection of the neighbor influenced preference vector \(\widetilde{\mathbf{p}}_{i}\) onto the compact, convex set \(\mathcal{K}_{i}\). Moreover, for any Nash equilibrium \(\mathbf{z}^* \in \mathcal{NE}\), we can partition the entire set of agents \(\mathcal{V}\) into two disjoint subsets, \[ \begin{align} \tag{15} & \mathcal{V}_{\mathrm{E}}(\mathbf{z}^*) :=\{i\in \mathcal{V}\mid \mathbf{c}_{i}^\top \mathbf{z}_{i}^* = B_i\}, \\ \tag{16} & \mathcal{V}_{\mathrm{DE}}(\mathbf{z}^*) :=\{i\in \mathcal{V}\mid \mathbf{c}_{i}^\top \mathbf{z}_{i}^* < B_i\}\,. \end{align} \tag{17}\] Here, \(\mathcal{V}_{\mathrm{E}}(\mathbf{z}^*)\) is the set of all agents who fully exhaust their resources at Nash equilibrium and \(\mathcal{V}_{\mathrm{DE}}(\mathbf{z}^*) = \mathcal{V}\setminus \mathcal{V}_{\mathrm{E}}(\mathbf{z}^*)\) is the set of agents who do not. Viewing each agent’s Nash equilibrium opinion \(\mathbf{z}_{i}^*\) as the solution to the projection problem provides insight into its properties by partitioning agents into the aforementioned sets \(\mathcal{V}_{\mathrm{E}}(\mathbf{z}^*)\) and \(\mathcal{V}_{\mathrm{DE}}(\mathbf{z}^*)\).

We first state the conditions that the Nash equilibrium opinions of agents in these sets must satisfy and then in the remark that follows, discuss the implications.

Proof: Under the stated assumptions, if \(\mathbf{z}^* \in \mathcal{NE}\), then by definition \(\widetilde{\mathbf{p}}_{i}\geq 0,\:\forall i \in \mathcal{V}\). Also, recall that \(\mathbf{z}_{i}^* = \mathop{\mathrm{argmin}}_{\mathbf{z}_{i}\in \mathcal{K}_{i}} 0.5 \left\|\mathbf{z}_{i}-\widetilde{\mathbf{p}}_{i}\right\|_{\widetilde{\mathbf{D}}_{i}}^{2},\:\forall i \in \mathcal{V}\). This means each \(\mathbf{z}_{i}^*\) is the unique weighted projection of \(\widetilde{\mathbf{p}}_{i}\) onto closed, convex set \(\mathcal{K}_{i}\). It is then easy to see that \(i \in \mathcal{V}_{\mathrm{DE}}(\mathbf{z}^*)\) if and only if \(\mathbf{c}_{i}^\top \widetilde{\mathbf{p}}_{i}< B_{i}\). Since \(\widetilde{\mathbf{p}}_{i}\geq \mathbf{0}\) it means that \(\widetilde{\mathbf{p}}_{i}\in \mathcal{K}_{i}\) and hence \(\mathbf{z}_{i}^*= \widetilde{\mathbf{p}}_{i}\). This proves the equality in 18 . Similarly, we can show that \(i \in \mathcal{V}_{\mathrm{E}}(\mathbf{z}^*)\) if and only if \(\mathbf{c}_{i}^\top \widetilde{\mathbf{p}}_{i}\geq B_{i}\). This means that \(\mathbf{z}_{i}^*\) is the solution to the projection problem only if \(\mathbf{c}_{i}^\top \mathbf{z}_{i}^* = B_i\). Hence, \(\mathbf{z}_{i}^* = \mathop{\mathrm{argmin}}_{ \{\mathbf{z}_{i}\mid \mathbf{z}_{i}\geq \mathbf{0},\; \mathbf{c}_{i}^\top \mathbf{z}_{i}= B_i\} } 0.5 \left\|\mathbf{z}_{i}-\widetilde{\mathbf{p}}_{i}\right\|_{\widetilde{\mathbf{D}}_{i}}^{2}\). From the KKT conditions for this (strict) convex program we have, \[ \tag{20} \begin{equation} \widetilde{\mathbf{D}}_{i}(\mathbf{z}_{i}^* - \widetilde{\mathbf{p}}_{i}) - \lambda^*\mathbf{c}_{i}- \boldsymbol{\mu}^* = \mathbf{0}\;, \tag{21} \end{equation} \begin{equation} \boldsymbol{\mu}^{*\top} \mathbf{z}_{i}^* = 0 \tag{22}, \boldsymbol{\mu}^* \geq \mathbf{0},\:\mathbf{z}_{i}^* \in \{\mathbf{z}_{i}| \mathbf{z}_{i}\geq \mathbf{0}, \mathbf{c}_{i}^\top \mathbf{z}_{i}= B_i\}. \end{equation} \tag{23}\] Then 19 follows from 23 . This completes the proof. \(\blacksquare\)

In light of Lemma 4, we see the importance of partitioning the agents into \(\mathcal{V}_{\mathrm{E}}(\mathbf{z}^*)\) and \(\mathcal{V}_{\mathrm{DE}}(\mathbf{z}^*)\). So, in the remaining portion of the section, we give sufficient conditions based solely on model parameters to determine if an agent either fully exhausts or does not exhaust its budget.

Proof: Under the stated assumptions and the definitions of \(\boldsymbol{\upsilon}_{i}\) and \(\widetilde{\mathbf{p}}_{i}\), it is clear that \(\widetilde{\mathbf{p}}_{i}\leq \boldsymbol{\upsilon}_{i}\). This follows because the equilibrium opinion profiles of neighboring agents, regardless of their exact values, satisfy \(\mathbf{z}_{l}^* \in \mathcal{K}_{l},\:\forall l \in \mathcal{N}_{i}\). The claim now follows from the proof of Lemma 4. \(\blacksquare\)

Note that \(\boldsymbol{\upsilon}_i\) depends on the importance weights \(w_{i}^{j}\), influence weights \(a_{ik}\), and the budgets of neighboring agents \(B_k\). So, if there exists an \(i \in \mathcal{V}\) with a large enough budget \(B_i\) such that \(\mathbf{c}_i^\top\boldsymbol{\upsilon}_i < B_i\), then by Lemma 5, the agent will not exhaust its budget at equilibrium.

Finally, we provide a sufficient condition, again based solely on model parameters, to guarantee that an agent exhausts its budget at the Nash equilibrium. Before proceeding, we state and prove this short result next.

Proof: Under Assumption [asmp:no95antagonistic95relations] it can be shown that \(\mathbf{J}\) is an invertible M-matrix. Hence, its inverse \(\mathbf{J}^{-1}\) is a non-negative matrix [1]. The claim now follows from Assumption [asmp:param95sign]. \(\blacksquare\)

Note that since \(\mathbf{J}\) is invertible, \(\mathbf{q}^*\) defined in Lemma 6 is in fact the unique equilibrium point of the unconstrained dynamics 5 . Additionally, let \(\mathbf{q}_{i}^*\) represent the \(i^{\text{th}}\) sub-vector of \(\mathbf{q}^*\), corresponding to the unconstrained equilibrium opinion vector of \(i \in \mathcal{V}\). We now present the final result.

Proof: First note that the vector field \(\mathbf{f}(\mathbf{z})\) defined in 5 can be written in terms of \(\mathbf{q}^*\) as \(\mathbf{f}(\mathbf{z})= \mathbf{J}(\mathbf{z}- \mathbf{q}^*)\). Hence \(\mathbf{f}_{i}(\mathbf{z}) = \mathbf{D}_{i}(\mathbf{z}_{i}- \mathbf{q}_{i}^*) - \sum_{k \in \mathcal{V}\setminus \left\{i\right\}}a_{ik}\left[\mathbf{q}_{i}^* - \mathbf{q}_{k}^* + \mathbf{z}_{k}- \mathbf{z}_{i}\right]\). Also note that from 3 , for any \(k \in \mathcal{V}\) we have \(0 \leq z_{k}^{j}\leq B_k/c_k^j,\:\forall j \in \mathcal{T}\). From Lemma 6 and the condition given in 24 , we can show that \(f_{i}^{j}(\mathbf{z})<0\). We are now ready to prove the claim via contradiction. Let \(\mathbf{z}^*\in \mathcal{E}\). From Lemmas 2 and 3, we have that \(\mathbf{z}_{i}^*\in \mathrm{SOL}(\mathbf{f}_{i},\mathcal{K}_{i},\mathbf{z}_{-i}^*)\), i.e., \(\langle \mathbf{f}_{i}(\mathbf{z}_{i}^{*},\mathbf{z}_{-i}^*), \mathbf{x}_{i} - \mathbf{z}_{i}^{*} \rangle \geq 0, \quad\forall \mathbf{x}_{i}\in \mathcal{K}_{i}\). Let the condition in 24 hold. Suppose \(\mathbf{c}_{i}^\top \mathbf{z}_{i}^* <B_i\). Choose \(s_i^j > (z_i^j)^*\) such that \(\mathbf{c}_{i}^\top \mathbf{x}_{i}= B_i\), where \(\mathbf{x}_{i}= [(z_{i}^{1})^{*},\ldots,(z_{i}^{j-1})^{*},s_{i}^{j},(z_{i}^{j+1})^{*},\ldots,(z_{i}^{m})^{*}]^\top \in \mathcal{K}_{i}\), with all values being exactly the same as those in \(\mathbf{z}_{i}^*\) except the \(j^{\text{th}}\) value, which is equal to \(s_i^j\). Clearly, \(\mathbf{x}_{i}\geq \mathbf{0}\) because such an \(s_i^j\) exists since \(\mathbf{c}_{i}^\top\mathbf{z}_{i}^* < B_i\). Thus, \(\mathbf{x}_{i}\in \mathcal{K}_{i}\). Now, using this \(\mathbf{x}_{i}\), evaluating the above inner product gives \(\langle \mathbf{f}_{i}(\mathbf{z}_{i}^{*},\mathbf{z}_{-i}^*), \mathbf{x}_{i} - \mathbf{z}_{i}^{*} \rangle = (s_i^j - (z_i^j)^*) f_i^j(\mathbf{z}^*) < 0\). This contradicts the fact that \(\mathbf{z}_{i}^*\in \mathrm{SOL}(\mathbf{f}_{i},\mathcal{K}_{i},\mathbf{z}_{-i}^*)\). \(\blacksquare\)

We now interpret the sufficient condition in the above result. Recall from the proof of Lemma 7 that for any agent \(i \in \mathcal{V}\), the upper bound on \(z_{i}^{j}\leq B_i/c_i^j,\:\forall j \in \mathcal{T}\) represents the maximum possible budget-constrained opinion that \(i\) can hold on topic \(j\). The condition in 24 states that if there exists a topic \(j \in \mathcal{T}\) for which the unconstrained equilibrium opinion \((q_{i}^j)^*\) is sufficiently larger than \(B_i/c_i^j\), then the agent will exhaust its resource budget at equilibrium.

7 Simulations↩︎

In this section, we present simulations to illustrate our analytical results⁸. We consider a group of four agents forming opinions on three topics according to 8 . For all simulations, we let \(\mathbf{c}_{i}= [1,1,1]^\top,~\forall i \in \mathcal{V}\) and \(a_{12}\!\approx\!1.24,~a_{13}\!\approx\!4.21,~a_{14}\!\approx\!1.57,~a_{23}\!\approx\!3.90,~a_{24}\!\approx\!5.14,~a_{34}\!\approx\!6.49\), and \(a_{ii}\!=\!0,~\forall i \in \mathcal{V}\). Thus, Assumption [asmp:no95antagonistic95relations] holds.

For the first set of simulations in Figure 1, the resource budget vector is \(\mathbf{r} \approx [100, 183.38, 325.99, 356.12]^\top\). Figure 1 (Left) shows that agent \(1\)’s opinions in all topics converge to the corresponding values of the unique equilibrium point \(\mathbf{z}^*\in \mathcal{E}= \mathop{\mathrm{argmax}}_{\mathbf{z}\in \mathcal{K}}W(\mathbf{z})\). Figure 1 (Right) shows that the error \(\|\mathbf{z}(t)-\mathbf{z}^*\|\) decreases monotonically to zero. This verifies the claims in Theorems 8, 9 and Corollary 1. The unconstrained equilibrium opinion vectors of all agents are: \(\mathbf{q}_{1}^*\!\approx\![216.45, 203.35, 422.27]^\top\), \(\mathbf{q}_{2}^*\!\approx\![146.76, 198.20, 207.26]^\top\), \(\mathbf{q}_{3}^*\!\approx\![170.87, 293.39, 311.20]^\top\), \(\mathbf{q}_{4}^*\!\approx\![160.35, 340.76, 305.09]^\top\). From these data, we can verify that \((q_1^3)^*\!\approx\!422.27\) is greater than the expression in square brackets in 24 , which is approximately equal to 391.45. Thus, the condition in 24 is satisfied. Figure 1 (Right) also shows that total allocation \(\mathbf{c}_1^\top\mathbf{z}_1(t)\) of agent \(1\) converges to its budget value, \(B_{1} =100\) and never exceeds it. Hence, \(1 \in \mathcal{V}_{\mathrm{E}}(\mathbf{z}^*)\). This verifies Lemma 7. The equilibrium opinions of agent \(2\) is \(\mathbf{z}_{2}^*\!\approx\![0, 103.41, 79.97]^\top\) and its neighbor influenced preference vector is \(\widetilde{\mathbf{p}}_{2} \approx [25.15, 143.56, 117.04]\). Thus, \(2 \in \mathcal{V}_{\mathrm{E}}(\mathbf{z}^*)\) because \(\mathbf{c}_{2}^\top\mathbf{z}_{2}^* \approx 183.38\). Also note that, \(2,3 \in \mathsf{supp}(\mathbf{z}_2^*) \subseteq \mathcal{T}\). The vector containing the values of \(\widetilde{w}_2^s\) defined in Lemma 4 is \(\widetilde{\mathbf{w}}_2\approx [14.48, 21.34, 22.89]^\top\). The vector containing the values of \(|(z_{2}^s)^* - \widetilde{p}_2^s|\) is \(\mathbf{d}_2 \approx [25.15, 39.96, 37.25]^\top\). The above data verifies 19 and its interpretation below Lemma 4. For the second set of simulations in Figure 2, \(\mathbf{r}\approx [100, 800, 325.99, 356.12]^\top\) is the resource budget vector containing \(B_i\)’s. Figure 2 (Left) shows agent \(2\)’s opinions’ evolution in all three topics. Figure 2 (Right) shows the evolution of total allocation \(\mathbf{c}_{2}^\top\mathbf{z}_{2}(t)\). Here, we see that the agent does not exhaust its budget at equilibrium; i.e., \(2 \in \mathcal{V}_{\mathrm{DE}}(\mathbf{z}^*)\). This is because \(\mathbf{c}_{2}^\top \boldsymbol{\upsilon}_{2} \approx 653.8 < 800\). This verifies the sufficient condition given in Lemma 5. The equilibrium opinion vector of second agent is \(\mathbf{z}_{2}^* \approx [25.15, 143.56, 117.04]\) and its neighbor influenced preference vector is \(\widetilde{\mathbf{p}}_{2} \approx [25.15, 143.56, 117.04]\). We observe that \(\mathbf{z}_{2}^*\approx \widetilde{\mathbf{p}}_{2}\). This verifies the implication in 18 of Lemma 4.

8 Conclusions↩︎

We introduced a novel opinion dynamics model within the projected dynamical systems framework, where agents allocate limited resources across multiple topics. We analyzed the model’s asymptotic properties, establishing convergence and stability of the equilibrium set. We analyzed the underlying opinion formation game, established that it is a potential game and characterized its Nash equilibria. Further, we related the Nash equilibria to the equilibria of the projected dynamics. Finally, we studied cases where agents exhaust (or do not exhaust) their budget in the absence of antagonistic relations. Potential future work directions include extension to directed signed social networks and exploration of more general utility functions.

References↩︎