Increasing Peer Pressure on any Connected Graph Leads to Consensus
Justin Semonsen Christopher Griffin Anna Squicciarini Sarah Rajtmajer




[JS E-mail:]js2118@math.rutgers.edu
Department of Mathematics, 
Rutgers University, 
Piscataway, NJ 08854


[CG E-mail:]griffinch@ieee.org

Mathematics Department, 
United States Naval Academy, 
Annapolis, MD 21666

[AS E-mail:]asquicciarini@ist.psu.edu

College of Info. Sci. and Tech., 
Penn State University, 
University Park, PA 16802

[SR E-mail: ]sarah.rajtmajer@qs-2.com

Quantitative Scientific Solutions, 
Arlington, VA 22203



In this paper, we study a model of opinion dynamics in a social network in the presence increasing interpersonal influence, i.e., increasing peer pressure. Each agent in the social network has a distinct social stress function given by a weighted sum of internal and external behavioral pressures. We assume a weighted average update rule and prove conditions under which a connected group of agents converge to a fixed opinion distribution, and under which conditions the group reaches consensus. We show that the update rule is a gradient descent and explain its transient and asymptotic convergence properties. Through simulation, we study the rate of convergence on a scale-free network and then validate the assumption of increasing peer pressure in a simple empirical model.


89.65.-s,02.10.Ox,02.50.Le
 
Increasing Peer Pressure on any Connected Graph Leads to Consensus
    Sarah Rajtmajer
    December 30, 2023 - preprint
==================================================================





§ INTRODUCTION

Beginning with DeGroot <cit.>, opinion models have been studied extensively (see e.g.,  <cit.>). In these models, opinion is a dynamic state variable whose evolution in some compact subset of ℝ^n is governed by an autonomous dynamical system. Using this formalism, opinion models have been unified with flocking models (see e.g., <cit.>) in <cit.>. Most recent work on opinion dynamics (and their unification with flocking models) considers the interaction of agents on a graph structure <cit.>. When considered on a lattice, these models are share characteristics to continuous variations of Ising models <cit.>.

Recent work <cit.> considers the evolution of opinion on a social network in which agents are resistant to change because of an innate belief. In particular, <cit.> use a variant of the model in <cit.> and study this problem from a game-theoretic perspective by considering the price of anarchy on the opinion formation process on a connected graph. The existence of innate beliefs, which are hidden but affect (publicly) presented opinion, is supported in recent empirical work by Stephens-Davidowitz et al. <cit.>. While the work in <cit.> introduces the concept of the stubborn agent, it does not consider the effect of situationally variant peer-pressure on agents' opinions, though statically weighted user connections are considered. Peer pressure in social networks is well-documented. Adoption of trends <cit.>, purchasing behaviors <cit.>, beliefs and cultural norms <cit.>, privacy behaviors <cit.>, bullying <cit.>, and health behaviors <cit.> have all been linked to peer influence. 

In this paper, we 
consider the problem of opinion dynamics on a social network of agents with innate beliefs in which peer-pressure is a dynamically changing quantity, independent of the opinions themselves. This has the mathematical effect of transforming the formerly autonomous dynamical system into a non-autonomous dynamical system. 

 Our notion of persuasion and peer-pressure affecting these dynamics  is related to the psychology literature on belief formation and social influence. In  particular,  we draw inspiration from studies on periodicity in human behavior, and social influence theories <cit.>. We follow Friedkin's foundational theory that strong ties are more likely to affect users' opinions and result in persuasion or social influence. Underpinning our model is also the notion  of mimicking. Brewer and more recently Van Bareen <cit.> suggest that mimicking is used when individuals feel out of  a group and therefore will alter their behavior (to a point <cit.>) to be more socially accepted.

The resulting   model also accounts for agents with relatively varying resistance to changing their innate beliefs. We use a recent result from functional analysis on the composition of (distinct) contraction mappings along with the Sherman-Morrison formula to show:


  * Under increasing peer-pressure, the dynamical system converges.

  * If peer-pressure increases in an unbounded way, consensus emerges a weighted average of the innate beliefs of the individuals.

  * The opinion update process converges to a gradient descent, with linear convergence rate

  * The hypothesis of increasing peer-pressure can be supported with a live data set. 

Work herein is complementary to (e.g.) <cit.> in that we consider a dynamic (increasing) peer-pressure coefficient with variable weights on initial belief. Additionally, we analyze the convergence rate of the dynamical system to the fixed point, while <cit.> focus on the model from a game-theoretic perspective. 


The remainder of this paper is organized as follows: In Section <ref> we present the basic model. In Section <ref> we prove convergence of the model and that increasing peer pressure leads to consensus in any connected graph. We discuss the convergence rate in Section <ref> by showing the dynamical system is, effectively, gradient descent. We briefly relate our work to the cost of anarchy work from <cit.> in Section <ref>. In Section <ref>, we validate the hypothesis of increasing peer pressure by fitting our model to a live data set. Conclusions and future directions are presented in Section <ref>. 



§ PROBLEM STATEMENT AND MODEL

We model a network of agents, representing individuals in a social network in which each user communicates with her friends/associates, but not necessarily the entire network. Assume that the agents' network is represented by a simple graph G = (V,E) where vertexes V are agents and edges E are the social connections (communications) between them. It is clear that disconnected sections of the graph are independent, so we assume that G is connected. For the remainder of the paper, let V = {1, 2 , … n}, so E is a subset of the two-element subsets of V.
The state of Agent i at time k is a continuous value x_i^(k)∈ [0,1] that represents disclosed opinion on a bivalent topic (e.g., “I support gun control” or “I like classical music”). Each agent has a constant preference x^+_i∈ [0,1] representing her inherent position on the topic. This may differ from the opinion disclosed to the public. The value x^+_i represents inherent agent bias. Further, Agent i is assigned a non-negative vertex weight s_i and positive edge weights w_ij respectively for (i, j) ∈ E. The weight s_i, termed stubbornness <cit.>, models the tendency of Agent i to maintain her (private) position x^+_i in public. The edge weights w_ij represent friendship affinity.  The set of all disclosed opinions is denoted by the vector 𝐱^(k) while the set of constant private preferences is 𝐱^+. For the remainder of this paper, we refer to publicly disclosed opinions simply as opinions.

Agent i's state is updated by minimizing its social stress: 

    J_i(x_i^(k),𝐱^(k-1), k) = s_i(x_i^(k) - x_i^+)^2
    
    + ρ^(k)∑_j = 1^n w_ij(x_i^(k) - x_j^(k-1))^2

Here ρ^(k) is the peer-pressure coefficient. In the sequel, we assume ρ^(k) is an increasing function of k. As noted in <cit.>, under these assumptions, the first order necessary conditions are sufficient for minimizing J_i(x_i^(k),𝐱^(k-1), k). 






The optimal state for Agent i at time k is then:

    x_i^(k) = s_ix_i^+ + ρ^(k)∑_j = 1^n w_ijx_j^(k-1)/s_i + ρ^(k)d_i,

where d_i = ∑_j = 1^n w_ij is the weighted degree of vertex i. The implied update rule is simply a generalization of the DeGroot model variation found in <cit.> and generalizes the model in <cit.> by including the stubbornness coefficient and an increasing peer-pressure term.

Let 𝐀 be the n × n weighted adjacency matrix of G. In addition, let 𝐃 be the n × n matrix with d_i on the diagonal and let 𝐒 be the n × n matrix with s_i on the diagonal. Using these terms, the recurrence in Eq. (<ref>) can be written as: 

𝐱^(k) = (𝐒 + ρ^(k)𝐃)^-1(𝐒𝐱^+ + ρ^(k)𝐀𝐱^(k-1))



We say that the agents converge to consensus 𝐱̅ if there is some N so that for all n > N, ‖𝐱̅ - 𝐱^(n)‖ < ϵ for some small ϵ > 0. This represents meaningful compromise on the issue under consideration. 



§ CONVERGENCE
 
In this section, we consider the update rule in Eq. (<ref>) as a sequence of contraction mappings each with its own fixed point. We then show that all these fixed points converge to a weighted average. The result rests on a variation of the contraction mapping theorem from <cit.>. 

 If 𝐋 = 𝐃-𝐀 is the weighted graph Laplacian, then 𝐋 has an eigenvalue 0 with multiplicity 1 and a corresponding eigenvector 1 where 1 is the vector of all 1's. 



For any ρ^(k) > 0, 𝐒 + ρ^(k)𝐋 is invertible. 



By definition, the graph Laplacian is a positive semidefinite symmetric matrix. In addition, the only eigenvector with eigenvalue 0 is the vector of all 1s, written 1.

Since 𝐒 is symmetric and s_i≥ 0, 𝐒 + ρ^(k)𝐋 is positive semidefinite as well. Choose 𝐱∈ℝ^n such that 𝐱^T(𝐒 + ρ^(k)𝐋)𝐱 = 0. Then 𝐱^T(𝐒 + ρ^(k)𝐋)𝐱 = 𝐱^T𝐒𝐱 + ρ^(k)𝐱^T𝐋𝐱.  Since 𝐒 and 𝐋 are positive semidefinite and ρ^(k) > 0, this implies that 𝐱^T𝐒𝐱 = 𝐱^T𝐋𝐱 = 0.

Since 𝐋 is symmetric, by the spectral theorem it has is an orthonormal basis of eigenvectors { b_1, … b_n} with associated eigenvectors {λ_1, …λ_n}. Because 𝐋 is positive semidefinite λ_i≥ 0, that 𝐱^T𝐋𝐱 = ∑_i = 1^nλ_i (𝐱^T b_i)^2. And, because 𝐱^T𝐋𝐱 = 0, if λ_i≠ 0, 𝐱^T b_i = 0.

It follows that x is an eigenvector of 𝐋 with eigenvalue 0; that is, 𝐱 = c 1 for some constant c, and therefore 𝐱^T𝐒𝐱 = c^2∑_i=1^n s_i. Since s_i≥ 0 and not all s_i are zero, we must have c = 0, so 𝐱 =  0. Following, 𝐒 + ρ^(k)𝐋 is positive definite, and therefore invertible.





Define:

F_k(𝐱) = (𝐒 + ρ^(k)𝐃)^-1(𝐒𝐱^+ + ρ^(k)𝐀𝐱)

and let:

    G_k = F_k∘ F_k-1∘⋯∘ F_1

Then 𝐱^(k) = F_k(𝐱^(k-1)) and  𝐱^(k) = G_k(𝐱^(0)). That is, iterating these F_k captures the evolution of 𝐱^(k). We show that for each k, F_k is a contraction and therefore has a fixed point by the Banach Fixed Point Theorem <cit.>. We use this result in the proof of Theorem <ref>. 


For all k, F_k is a contraction map with fixed point given by 𝐱^(k) = (𝐒 + ρ^(k)𝐋)^-1𝐒x^+.



Let 𝐁 be the (n+1) × (n+1) matrix given by adding a row and column to ρ^(k)(𝐒 + ρ^(k)𝐃)^-1𝐀 as follows: 

𝐁 = [[ ρ^(k)(𝐒 + ρ^(k)𝐃)^-1𝐀     (𝐒 + ρ^(k)𝐃)^-1𝐒1;                     0                     1 ]]


The rows of 𝐁 sum to 1. To see this, replace x^+ and x_i^(k-1) in Eq. (<ref>) with 1. Thus 𝐁 is a stochastic matrix for a Markov process with a single absorbing state. Since G is connected and not all s_i are equal to 0, a transition exists from each state to the steady state; thus from any starting state, convergence to the steady state is guaranteed. This means that lim_i →∞(ρ^(k)(𝐒 + ρ^(k)𝐃)^-1𝐀)^i = 0, so 𝐀 is a convergent matrix. Equivalently, if ‖·‖ denotes the matrix operator norm, then, ‖ρ^(k)(𝐒 + ρ^(k)𝐃)^-1𝐀‖ < 1. Therefore for any 𝐱,𝐲∈ [0,1]^n:

    ‖ F_k(𝐱) - F_k( y) ‖
       = ‖ (𝐒 + ρ^(k)𝐃)^-1ρ^(k)𝐀(𝐱 -  y) ‖
       ≤‖ (𝐒 + ρ^(k)𝐃)^-1ρ^(k)𝐀‖‖𝐱 -  y‖

That is, F_k is a contraction map on a compact set, so by the Banach fixed-point theorem, it has a unique fixed point 𝐱^(k). 

Let 𝐱^(k) be that fixed point. Then 𝐱^(k) = F_k(𝐱^(k)). Rearranging the terms yields, 

(𝐒 + ρ^(k)𝐃)𝐱^(k) - ρ^(k)𝐀𝐱^(k)  = (𝐒 + ρ^(k)𝐋) 𝐱^(k) = 𝐒𝐱^+.

Therefore:

    𝐱^(k) = (𝐒 + ρ^(k)𝐋)^-1𝐒𝐱^+.

This completes the proof.


The following lemma will allow us to consider the matrices (𝐒 + ρ^(k)𝐋)^-1 for k ∈{1,2,…} in GL_n(ℝ) (the Lie group of invertible n× n real matrices) as perturbations.  This enables effective approximations of asymptotic behaviors.

Let { b_1… b_n} an orthonormal basis of ℝ^n. Also let 𝐌: ℝ^n→ℝ^n be an invertible symmetric linear transformation (invertible square matrix) and { u_1, … u_n} be a set of unit vectors such that for a small constant δ, 𝐌^-1 b_1 = λ b_1 + O(δ) u_1 and 𝐌^-1 b_j = O(δ) u_j for j ≠ 1.

Then if ‖ v‖ = 1, and s ∈ℝ, then unless (𝐌 + s v v^T) is not invertible, there exists a set of unit vectors { u_1', … u_n'} such that (𝐌 + s v v^T)^-1 b_1 = λ/1 + sλ ( v^T b_1)^2 b_1 + O(δ) u_1' and (𝐌 + s v v^T)^-1 b_j = O(δ) u_j' for j ≠ 1.

Before proceeding to the proof of this result, based on the Sherman-Morrison formula, we note that we will establish an instance of the necessary conditions of this lemma in Theorem <ref>. Thus the lemma is not vacuous. 

Since { b_1… b_n} is an orthonormal basis, v = ∑_i=1^n a_i b_i where a_i =  v^T b_i. This means that 𝐌^-1 v =  ∑_i=1^n a_i𝐌^-1( b_i) = λ a_1 b_1 + O(δ)∑_i=1^n a_i u_i. By Cauchy-Schwartz, | a_i|≤‖ v‖‖ b_i‖ = 1, so by the triangle inequality, ‖∑_i=1^n a_i u_i‖≤ n. Then letting u = ∑_i=1^n a_i u_i/n, we have that 𝐌^-1 v = λ a_1 b_1 + O(δ) u, where ‖ u‖≤ 1.

By the Sherman-Morrison formula, 

(𝐌 + svv^T)^-1 = 𝐌^-1 - s𝐌^-1vv^T𝐌^-1/1 + sv^T𝐌^-1v. 

Using this, and choosing each u_i' to be an appropriate rescaling of the O(δ) terms yields:


    (𝐌 + s v v^T)^-1( b_1) = 𝐌^-1 b_1 - s𝐌^-1 v v^T𝐌^-1 b_1/1 + s v^TM^-1 v = 
    λ b_1 + O(δ) u_1 - s v^T(λ b_1 + O(δ) u_1)/1 + s v^T(λ a_1 b_1 + O(δ) u)(λ a_1 b_1 + O(δ) u)
    
    = λ b_1 + O(δ) u_1 - sλ a_1 + O(δ)/1 + sλ a_1^2 + O(δ)(λ a_1 b_1 + O(δ) u)
    
    = λ/1 + sλ ( v^T b_1)^2 b_1 + O(δ) u_1'

Furthermore, for j ≠ 1:

    (𝐌 + s v v^T)^-1( b_j) = 𝐌^-1 b_j - s𝐌^-1 v v^T𝐌^-1 b_j/1 + s v^T𝐌^-1 v = 
     O(δ) u_j - s v^T(O(δ) u_1)/1 + s v^T(λ a_1 b_1 + O(δ) u)(λ a_1 b_1 + O(δ) u)
    
    = O(δ) u_j'

This completes the proof.


The results stated give insight into the motion of fixed points as ρ^(k) increases. We now show that the  fixed point given by Eq. (<ref>) converge to the average of the agents' initial preferences, weighted by the stubbornness of each agent. We then use that result to prove the dynamics converge to this point when ρ^(k)→∞. 




If lim_k →∞ρ^(k) = ∞, then:

lim_k →∞𝐱^(k) = ∑_i = 1^n s_ix_i^+/∑_i = 1^n s_i1.
 



Since G is a graph, the Laplacian 𝐋 is a positive semidefinite symmetric matrix, and therefore has an orthonormal basis of eigenvectors { b_1, … b_n} with real eigenvalues {λ_1, …λ_n}. Since G is connected, only a single eigenvalue λ_1 = 0 and the associated unit eigenvector is b_1 = 1/√(n) 1.

Since every vector is an eigenvector of the identity matrix I, { b_1, … b_n} are an orthonormal basis of eigenvectors for I + ρ^(k)𝐋 with eigenvalues {1, 1 + ρ^(k)λ_2, … 1 + ρ^(k)λ_n}. But then ( I + ρ^(k)𝐋)^-1 has the same basis of eigenvectors, with eigenvalues {1, 1/1 + ρ^(k)λ_2, …1/1 + ρ^(k)λ_n}.

As ρ^(k)→∞, 1/1 + ρ^(k)λ_j→ 0 for each j ≠ 1. In particular, for any  δ > 0, for sufficiently large ρ^(k),  I+ ρ^(k)𝐋 satisfies the conditions of Lemma <ref> with λ = 1.

Let I + ρ^(k)𝐋 = 𝐌_0. Then, for each l up to n, let 𝐌_l = (𝐌_l-1 + (s_l - 1) e_l e_l^T) where e_l is the lth vector of the standard basis. Since e_l e_l^T is the zero matrix with a one in the lth place on the diagonal, ∑_l=1^n (s_l - 1) e_i e_i^T = 𝐒- I and therefore 𝐌_n = ( I + ρ^(k)𝐋) + ∑_l=1^n (s_l - 1) e_l e_l^T = 𝐒 + ρ^(k)𝐋.

By iterating Lemma <ref> with s = s_l - 1 and v =  e_l, we have that for each l there is a λ_l such that 𝐌_l^-1 b_1 = λ_l b_1 + O(δ) u_1^(l) and 𝐌_l^-1 b_j = O(δ) u_j^(l) for j ≠ 1.

Since e_l^T b_1 = 1/√(n), Lemma <ref> gives the recurrence: 
    λ_l = λ_l-1/1+ λ_l-1s_i -1/n


Solving this recurrence with λ_0 = 1 yields:  

𝐌_l^-1b_1 = n/n + ∑_k=1^l (s_k - 1) b_1 + O(δ)u_1^(l)


Since ∑_k=1^n (s_k - 1) = tr(𝐒) - n, it is clear that

𝐌_n^-1b_1 = n/tr(𝐒) b_1 + O(δ)u_1^(n).

Therefore, for u = ∑_i=1^n b_1^T𝐒𝐱^+ u_i^(n):

    𝐱^(k)   = n/tr(𝐒) b_1^T𝐒𝐱^+ b_1 + O(δ) ∑_i=1^n b_1^T𝐒𝐱^+ u_i^(n)
       =  1^T𝐒𝐱^+/tr(𝐒) 1 + O(δ)  u
       = ∑_i=1^n s_ix_i^+/∑_i=1^n s_i 1 + O(δ)  u


Since δ→ 0 as ρ^(k)→∞, if lim_k →∞ρ^(k) = ∞, then:

lim_k →∞ 𝐱^(k) = ∑_i=1^n s_ix_i^+/∑_i=1^n s_i1.

This completes the proof.


Since peer pressure increases in each step, no single F_k is sufficient to model the process of convergence. We use the following result from <cit.>
 Let {f_n} be a sequence of analytic contractions in a domain D with f_n(D) ⊆ E ⊆ D_0 ⊆ D for all n. Then F_n = f_n ∘ f_n-1∘⋯∘ f_1 converges uniformly in D_0 and locally uniformly in D to a constant function F(z) = c ∈ E. Furthermore, the fixed points of f_n converge to the constant c. 


The following corollary is now immediate from Lemmas <ref> and <ref>:

From Eq. (<ref>), let G_k= F_k∘ G_k-1 = F_k∘ F_k-1∘…∘ F_1 for each k ≥ 0. Then G = lim_k →∞ G_k is a constant function and (functional) convergence is uniform. 


We now have the following theorem, which follows immediately from Corollary <ref> and Theorem <ref>:
 If ρ^(k)→∞, then:

lim_k →∞ 𝐱^(k) = ∑_i = 1^n s_ix_i^+/∑_i = 1^n s_i1.




This means that in the case of increasing and unbounded peer pressure, all the agents' opinions always converge to consensus. In addition, the value of this consensus is the average of their preferences weighted by their stubbornness. This is irrespective of the weighting of the edges in the network, so long as the network is connected.

We illustrate opinion consensus on a simple graph with 15 vertices in Fig. <ref>. The vertices are organized into three connected cliques. Each clique was initialized with a distinct range of opinions in [0,1]. Initial stubbornness was set randomly and is shown by relative vertex size.

The opinion trajectories for this example are shown in Fig. <ref>.


In the case of increasing but bounded peer pressure, we have:

lim_k →∞ ρ^(k) ≤ρ^*

Further, this limit always exists by monotone convergence. Intuitively, this means the influence of others is limited, and that personal preferences will always slightly skew the opinions of others. Again, this is consistent with social influence theories on bounded peer pressure and trade-offs with comfort level <cit.>.


Suppose ρ^(k) is increasing and bounded and that:

lim_k →∞ ρ^(k) = ρ^*,

then 

lim_k →∞ 𝐱^(k) = (𝐒 + ρ^*𝐋)^-1𝐒𝐱^+.



Since ρ^(k) is increasing and bounded, it converges to a finite number ρ^* by monotone convergence. From Lemma <ref>, (𝐒 + ρ^* 𝐋) is defined and invertible. Since matrix inversion is continuous in GL_n(ℝ), by Theorem <ref>:

    lim_k →∞𝐱^(k)   = lim_k →∞𝐱^(k)
       = lim_k →∞(𝐒 + ρ^(k)𝐋)^-1𝐒𝐱^+
       = (𝐒 + lim_k →∞ρ^(k)𝐋)^-1𝐒𝐱^+
       = (𝐒 + ρ^* 𝐋)^-1𝐒𝐱^+

 
The above theorem tells us that if peer pressure is increasing and bounded, the agents' opinions converge to a fixed distribution, which may not be a consensus, but is easily computable from the initial preferences. In this case, the shape of the network is important for determining the limit distribution, as the edge weights factor into the Laplacian. This result is similar to the convergence point given in <cit.> where stubbornness coefficients are not presented and peer pressure is constant.



§ CONVERGENCE RATE

We analyze the convergence rate of the algorithm and obtain a secondary result on efficiency. Define the utility of these convergent points to be the sum of the stress of the agents when the state 𝐱 is constant. Formally:

    U^(k) (𝐱)    = ∑_i J_i(x_i, 𝐱, k)
       = ∑_i =1^n s_i(x_i - x_i^+)^2 +  ρ^k(∑_i,j w_ij(x_i-x_j)^2)
       = (𝐱 - 𝐱^+)^T𝐒(𝐱 - 𝐱^+) + 2ρ^k𝐱^T𝐋𝐱
       = 𝐱^T(𝐒 + 2ρ^k𝐋)𝐱 - 2𝐱^T𝐒𝐱^+ + (𝐱^+)^T𝐒𝐱^+

Define the limiting utility U(𝐱) as:

    U(𝐱) = lim_k →∞1/ρ^(k)U^(k)(𝐱)

The following lemma is immediately clear from the construction of the functions J_i, the fact that U^(k) is a strictly convex function and U is the limit of these strictly convex functions:
 The global utility function U(𝐱) is convex. Furthermore, the fact that (i) U^(k) is smooth on its entire domain and (ii) U^(k)(𝐱)/ρ^(k) converges uniformly to U(𝐱), implies that U(𝐱) is both differentiable and its derivative can be computed as the limit of the derivatives of 
U^(k)(𝐱)/ρ^(k).



Using the global utility function, we can analyze the convergence rate of the update rule. From Eq. (<ref>), we can compute:

    Δ x_i^(k-1) = x_i^(k) - x_i^(k-1) = 
    s_i(x_i^+ - x_i^(k-1)) + ∑_j=1^n (x_j^(k-1) -x_i^(k-1))/s_i + ρ^(k)∑_j=1^n w_ij

Let:

    α_i^(k) = 1/s_i + ρ^(k)∑_j=1^n w_ij

and define 𝐇^(k) = 12diag(α_1^(k),…,α_n^(k)). Computing the gradient of U^(k) yields:

    Δ𝐱 = -𝐇^(k)∇ U^(k)(𝐱_i^(k-1))

We conclude the update rule, Eq. (<ref>) can be written:

    𝐱^(k) = 𝐱^(k-1) - 𝐇^(k)∇ U^(k)(𝐱^k-1)

Necessarily, 𝐇^(k) is always positive definite and therefore - 𝐇^(k)∇ U^(k)(𝐱^k-1) is always a descent direction for U^(k). Moreover, (∇ U_k)^T ∇ U > 0 and consequently - 𝐇^(k)∇ U^(k)(𝐱^k-1) is a descent direction for U(𝐱). Thus, the update rule is a descent algorithm, which explains the initial fast convergence toward the average (see Fig. <ref>).  When the descent direction converges to a Newton step, a descent algorithm can be shown to converge superlinearly  <cit.>. However, these steps do not converge to Newton steps. As ρ^(k) grows large, α_i^(k)→ 0 and U_k/ρ^(k)→ U and consequently for large k:

1/ρ^(k)𝐇^(k)∇U^(k)(𝐱^k-1) ≈ϵ∇U(𝐱^k-1)

for ϵ∼ 1/ρ^(k). Thus, the update rule approaches a simple gradient descent. We show that a consequence of this is a linear convergence rate. 


Let:

𝐱^*= ∑_i=1^n s_ix_i^+/∑_i=1^n s_i1

and define:

𝐲^(k) = 𝐱^(k) - 𝐱^*.

From Eq. (<ref>) we compute:

    ‖𝐱^(k+1) - 𝐱^*‖/‖𝐱^(k) - 𝐱^*‖ = 
    ‖𝐲^(k) - 𝐇^(k+1)∇ U^(k+1)(𝐱^(k))‖/‖𝐲^(k-1) - 𝐇^(k)∇ U^(k)(𝐱^(k-1))‖

Assuming ρ^(k)→∞ as k →∞, and expanding the gradient using Eq. (<ref>) we obtain:


    lim_k →∞‖𝐱^(k+1) - 𝐱^*‖/‖𝐱^(k) - 𝐱^*‖  = lim_k →∞1ρ^(k)/1ρ^(k)‖𝐲^(k) - 𝐇^(k+1)([𝐒 + 2ρ^(k+1)𝐋]𝐱^(k) - 2𝐒𝐱^+)‖/‖𝐲^(k-1) - 𝐇^(k)([𝐒 + 2ρ^(k)𝐋]𝐱^(k-1) - 2𝐒𝐱^+)‖ =
    lim_k →∞‖𝐲^(k)/ρ^(k) - 𝐇^(k+1)([𝐒/ρ^(k) + 2ρ^(k+1)ρ^(k)𝐋]𝐱^(k) - 2𝐒𝐱^+/ρ^(k))‖/‖𝐲^(k-1)/ρ^(k) - 𝐇^(k)([𝐒/ρ^(k) + 2𝐋]𝐱^(k-1) - 2𝐒𝐱^+/ρ^(k))‖ = 
    lim_k →∞2ρ^(k+1)ρ^(k)‖𝐇^(k+1)𝐋𝐱^(k)‖/2‖𝐇^(k)𝐋𝐱^(k-1)‖


As ρ^(k)→∞, we see that:

𝐇^(k) →1/2ρ^(k)𝐃^-1,

where 𝐃 is the diagonal weighted degree matrix. Then:

    lim_k →∞2ρ^(k+1)ρ^(k)‖𝐇^(k+1)𝐋𝐱^(k)‖/2‖𝐇^(k)𝐋𝐱^(k-1)‖ = 
    ρ^(k+1)/ρ^(k)1ρ^(k+1)‖𝐃^-1𝐋𝐱^(k)‖/1ρ^(k)‖𝐃^-1𝐋𝐱^(k-1)‖ = 1

Thus we have shown:
 The convergence rate of the update rule given in Eq. (<ref>) is linear. In particular: 

    lim_k →∞‖𝐱^(k+1) - 𝐱^*‖/‖𝐱^(k) - 𝐱^*‖ = 1,



We illustrate the slow convergence on a larger example with 500 vertices organized into a scale-free graph using the Barabási-Albert <cit.> graph construction algorithm. The graph and snapshots of opinion evolution are shown in Fig. <ref>.

We show the opinion trajectories for the 500 vertex scale-free network in Fig. <ref>(a) and illustrate Eq. (<ref>) in Fig. <ref>(b).

Notice the ratio ‖𝐱^(k+1) - 𝐱^*‖/‖𝐱^(k) - 𝐱^*‖ approaches 1 as expected.




§ COST OF ANARCHY

<cit.> observe that simultaneous minimization of Eq. (<ref>) is a game-theoretic problem and compare the total social utility in a centralized solution to a decentralized solution (Nash equilibrium); i.e., they compute a price of anarchy <cit.>. To analyze the price of anarchy of this system, we cannot use the utility function in Eq. (<ref>), as the U^(k)(lim_k →∞𝐱^(k)) → 0 when ρ^(k)→∞. Instead, we use a total utility function U_T(𝐱) = lim_k→∞ U^(k)(𝐱) to compute the cost of anarchy:

 The convergent point lim_k →∞𝐱^(k) minimizes total utility if and only if lim_k →∞ρ^k = ∞.


If ρ^(k) converges to a finite number ρ^*, then the total utility is

    U_T(x) = 𝐱^T(𝐒 + 2ρ^*𝐋)𝐱 - 2𝐱^T𝐒𝐱^+ + (𝐱^+)^T𝐒𝐱^+

Note that this is identical to the work in <cit.>, except with edge weights multiplied by ρ^*. We note that lim_k →∞𝐱^(k) is the Nash Equilibrium used in <cit.>. From the work in <cit.> we may conclude the convergent point is not optimal for finite ρ^*.

If lim_k →∞ρ^k = ∞, then if 𝐱≠ c1 for some constant c, then 𝐱^T𝐋𝐱 > 0, so U^(k)(𝐱) grows without bound. However, for any k, we have that U^(k)(c1) = ∑_i=1^n s_i(c - x_i^+)^2, so U_T(c1) = ∑_i=1^n s_i(c - x_i^+)^2. By first order necessary conditions of optimality:
 
    ∑_i=1^n s_ix_i^+/∑_i=1^n s_i1
 
 minimizes U(𝐱), and thus lim_k →∞𝐱^(k) is optimal.

This gives the following trivial corollary, which is consistent with the work in <cit.>.
 The cost of anarchy is 1 if and only if lim_k →∞ρ^(k) = ∞. 



§ EMPIRICAL ANALYSIS
 
The hypothesis of increasing peer pressure in social settings underlies this work. We attempt to (in)validate the hypothesis that peer-pressure does increase in real-world systems, by using data from the well-known Social Evolution Experiment <cit.>. The experiment tracked the everyday life of approximately 80 students in an undergraduate dormitory over 6 months using mobile phones and surveys, in order to mine spatio-temporal behavioral patterns and the co-evolution of individual behaviors and social network structure.

The dataset includes proximity, location, and call logs, collected through a mobile application. Also included are sociometric survey data for relationships,  political opinions, recent smoking behavior, attitudes towards exercise and fitness, attitudes towards diet, attitudes towards academic performance, current confidence and anxiety level, and musical tastes. 

The derived social network graph (shown Fig. <ref>) represents each student as a node; an edge is present between two nodes if either student noted any level of interaction during the surveys. Edge weights were derived based on the level of interaction recorded between the students in the surveys, as well as the number of surveys in which the interaction appeared. 

We note that this graph is not scale-free, as is typical of social networks. This may be a result of the size of the network, collection bias or simply representative of this social network. As a consequence, it is dense.

Political opinion was modeled on a [0,1] scale, with lower numbers representing Republican preferences and higher numbers representing Democratic preferences. Individual scores were assigned based on reported political party, preferred candidate and likelihood of voting (prior to the election), as well as who they voted for and their approval rating of Barack Obama (after the election). Appendix <ref> contains the code used to set these preferences. Each month's survey was examined individually to put together a monthly time line of each person's political views. The results of the first survey were used as proxy for their inherent personal preference, prior to peer influence.

Finally, individual stubbornness/lack of susceptibility to peer pressure was approximated using reported interest in politics on the first survey administered, as well as stated likelihood of voting. These survey questions were independent of those used in determining political preferences. Appendix <ref> contains the code used to set stubbornness.

Given a list of ρ^(k), students' preferences were simulated by aligning each iteration of play to one day in the survey period. The simulated preferences were compared to the surveyed preferences at each month, and the distances between the vectors were summed to get a single score for each list of ρ^(k). 

This function of ρ^(k) was minimized with fminsearch in Matlab and the best-fit peer pressure values were found to be increasing, with a best fit line ρ^(k) = 1.06*k - 11.96 and r^2 = .9886 (see Fig. <ref>).

The inferred increasing in peer pressure is consistent with the underlying hypothesis of the paper, under the assumption that the process of repeated opinion averaging with stubbornness is a valid model of human behavior. We discuss this further in Section <ref>.



§ CONCLUSION

In this paper we study an opinion formation model under the presence of increasing peer pressure. As in earlier work, we consider agents whose opinion is affected by unchanging innate beliefs. In this paper, the relative strength of these innate beliefs may vary from agent to agent. We show that in the case of unbounded peer-pressure, opinion consensus to a weighted average of innate beliefs is ensured. We also consider the case when peer-pressure is increasing, but bounded. Simulation suggests a numerically slow convergence, which is explained by showing the system dynamics converge to gradient descent applied to a certain convex function. Using this observation we show that that convergence is linear. We evaluate our hypothesis that peer-pressure increases in real world closed systems by fitting our model to a live data set. 

We note that that the assumption of a non-constant (and increasing) peer-pressure coefficient can help mitigate the fast initial convergence of this class of models. It is rare in the real-world to see dramatic opinion shifts over extremely short time scales. Such dramatic shifts are consistent with a gradient descent. However, by varying peer-pressure, the gradient descent can be controlled, leading to more consistency with real-world phenomena as illustrated. 


In future work, the limitation that the network is undirected and symmetric should be removed to account for asymmetric social influence. In addition, the network is assumed to remain static during the convergence process, with connections independent of the agents' opinions. Sufficiently different opinions could cause enough stress between agents so as to cause them to reduce influence or even sever the tie between them. A dynamic network model as in <cit.> could accommodate this kind of network update. Finally, it would be interesting to study corresponding control problems, in which we are given a 𝐱̅, the desired convergence point and we can control a subset of agents reporting values (x_i^(k)), stubbornness (s_i) or initial value (x_i^+) to determine conditions under which opinion steering is possible. This problem becomes more interesting if the other agents attempt to determine whether certain agents are intentionally attempting to manipulate the opinion value 𝐱^(k). Of equal interest is the transient control problem in which 𝐱^(k) is steered through a set X ⊂ℝ^n under the assumption that external factors will prevent convergence in the long-run.



§ ACKNOWLEDGEMENT

All authors were supported in part by the Army Research Office, under Grant W911NF-13-1-0271. A portion of CG's work was supported by the National Science Foundation under grant number CMMI-1463482. A portion of AS's work was supported by the National Science foundation under grant number 1453080.



§ INITIAL CONDITION CODE

The Matlab code below sets the initial preferences (𝐱^+) in this experiment.
InferPrefs.m



§ STUBBORNNESS SETTING CODE

The Matlab code below set the stubbornness coefficients (𝐬) in this experiment.
PoliticalStubbornness.m

apsrev4-1


