Lecture notes for COMS 6998 - Social Network Economics
Fall 2013, Columbia University
by A. Chaintreau

---

Part A.2 - Manipulation

Motivation

Many social interaction with opinions do not result in a single state representing the opinion that is now believed by all nodes, and when it does, there is no guarantee that this equilibrium is what our previous models predict. There are various reasons for that, and the first one that we study is the presence of nodes who interact without respecting fully the update rules that we have defined so far. We focus on two particular anomaly:

• assymetric influence (formarly defined below), in which only one node decides to take information exchanged into account, and
• a specific form of bias in which no matter how many steps have been, a node $i$ still remember its initial value $x_i(0)$ and treats this private information as a constant.

Like in the previous naive learning we studied, the node treats information received from its neighbors as if they constitute entirely new information to be treated as in the first round, except that after doing that, the node does not update the initial value to the current estimate. Extreme forms of influence (totally assymetric for a node) or bias leads to stubborness: nodes that affect the outcome of the system without revising their estimates at anytime.

Update model with influence and bias**

We know will consider different cases depending in which transitions (averaging, influence, others) are either be triggered by a pair

• Pairwise Averaging a symmetric exchange in which two nodes come simultaneously to an agreement: $x_i \leftarrow \frac{x_i+x_j}{2}$ and $x_j \leftarrow \frac{x_i+x_j}{2}$

• Pairwise Influence assymetric exchange in which one person modifies her state from a directed interaction (new information, forceful) $x_i \leftarrow (1-\theta_{i,j})\cdot x_i + \theta_{i,j} \cdot x_j$ where $\theta_{i,j}$ denotes how much $i$ trusts $j$ and hence adapts her own opinion after $j$'s statement

or it can alternatively be triggered a node.

• Node’s Cost Minimization is a local operation in which $x_i$ decides to update her opinion by first gathering information from her neighborhood and then choose a position that seems a best fit: $x_i \leftarrow \min_{y} \textrm{Cost}_i\left(y,(x_{j})_{j\in \mathcal{N}(i)},x_i\right)$ where $\mathcal{N}(i)$ denotes the set of nodes whose positions influences the choice of $i$. To focus on a simple model of convex cost, the function $\textrm{Cost}$ is typically a function that computes a weighted sum of the square of the distance between the new position $y$ and the other opinions in factor.

  We say the node is unbiased (or memoryless) if it takes the current best estimate $x_i(t)$ that it maintains as the last argument of the Cost. We say the node is biased if the last argument remains $x_i(0)$ at anytime.

The case in which all nodes simultaneously perform a cost minimization will be called synchronous, the cases where a single node is chosen at random to make a transition alone is called asynchronous.

Some immediate remarks on this model:

• Fair Iterated averaging, seen and analyzed before, is a synchronous nodal cost minimizing, where all nodes are unbiased and aims at minimizing the sum of square distance to all the nodes they listen including themselves (a weighted version can handle various level of trust).
• One can see that forms of skewed averaging in which a pairwise interaction between $(i,j)$ results in $x_i$ and $x_j$ updating their values but according to different coefficient is essentially equivalent in effect to choosing one or the other with different probability and value of $\theta$.
• One can model Stubborn nodes in the pairwise model (these are nodes that do not participate to symmetric transition, and are not influenced by anyone, although they can influence others) and in the nodal model (these simply means that the cost put all weights on staying close to initial value).
• Pairwise fair iterated averaging corresponds to a system evolving with no influence transition. Not only does this always converge as long as the graph denoting probability to meet is connected, but it brings two other benefits: Periodicity is not an issue anymore. This limit in this case, is always the exact average of all initial positions. It can be derived from a “mass conservation” argument: The total sum of $x_i$ among all $i$ remains constant at anytime.

---

Analysis of the model with nodal updates

We first consider results from two paper that study a Synchronous cost minimization where nodes display general bias and/or stubborness. In contrast with the iterated averaging we have studied, nodes in the limit do not necessarily come to an agreement. The first paper characterizes the evolution of the system and allows us to understand its limit in more explicit mathematical terms. The second paper characterizes the amount of disagreement, be it internal (towards initial opinion for biased nodes) or external (towards other nodes). It shows that the sum of this disagreement cost attained by the equilibrium of this system is never too far from what would be the minimum cost always present for all opinions.

Convergence and Limit expressed using Random Walks

J. Ghaderi and R. Srikant, “Opinion Dynamics in Social Networks: A Local Interaction Game with Stubborn Agents,” ACC ‘13: Proceedings of the American Control Conference, vol. cs.GT. 2013.

Summary of main contributions:

• Proves convergence and provide a formula relating the limit attained to the property of random walk on associated graphs.
• Provides several general upper bounds that estimates the convergence time in terms of eigenvalue of an associated transition matrix, paths and cuts in the graph.
• Show the relative tightness of these bounds on convergence time on various classes of graphs (complete, ring, uniform random graph, grid with distance based shortcuts).

Model: The paper assumes that the network of neighbors is undirected (or equivalently, symmetric) and that it is connected (and, hence, strongly connected).

Nodes initially have an opinion $x_i(0)$ based on their private information. The nodes that keep this opinion are refered to as partially stubborn whereas the nodes that never update their value are totally stubborn, others are unbiased.

If we assume that all users aim at minimizing the following individually perceived cost

$$\textrm{Cost}_i = K_i (x_i-x_i(0))^2 + \sum_{j\in N(i)} (x_i-x_j)^2\;,$$ then assuming neighbors and initial opinion is fixed, the node will follow the nodal update rule below: $$x_i \leftarrow \frac{1}{K_i + |N(i)| } \left(K_i x_{i}(0) + \sum_{j\in N(i)} x_{j}\right)$$

Analysis of convergence and limit:

• Convergence: If all nodes perform that rule simultaneously, this can be rewritten as $x(t+1) = A x(t) + B x(0)$ where
  $A_{i,j} = \frac{1}{K_i + |N(i)|}$ for $j\in N(i)$, and $A_{i,j}=0$ otherwise = 0, and $B=\textrm{Diag}(\left(\frac{K_i}{|N(i)|+K_i}\right)_{i})$
  This iteration can be shown by recursion to imply: $x(t)= A^tx(0)+\sum_{l=0}^{t-1} A^l B x(0)$. Except if $K_i=0$ for all $i$ (which comes back to cases we previously studied) $A$ is a substochastic matrix: its sum of coefficient on all rows are at most $1$, and, assuming at least one node $i$ is biased, i.e., $K_i>0$, one row sums to less than 1. This implies that $A^t\to 0$ as $t$ increases because its largest eigenvalue is less than $1$. We deduce

  $$x(\infty)= \sum_{t=0}^{\infty} A^t B x(0)=(I-A)^{-1}B x(0)$$

• Equilibrium is characterized in a simple form through the properties of a simple random walk. Let us first assume that all biased nodes (denoted by $S$) are stubborn (i.e., for any $i$, either $K_i=0$ or $K_i=\infty$), then we have (Lemma 3)

  $$x_i(\infty) = \sum_{j\in S} P[Z(\tau_S)=j \;|\; Z(0)=i ]\cdot x_j(0) \;,$$ where $Z(.)$ is a simple random walk which is in this formula initiated at node $i$, $\tau_S$ is the first time the random walk enters the set $S$.

• Extension to biased agents, also called partially stubborn (i.e., any $i$ such that $0<K_i<\infty$) can be analyzed as follows. From a given graph, replace any $i$ as above by two nodes: $i$ and $u_i$, where $i$ is an unbiased agent and $u_i$ a stubborn agent whose opinion is given by the initial opinion of agent $i$, $x_i(0)$. Define a new random walk $Z$ on this new graph by first assigning weight $1$ to every edge, and weight $K_i$ to edge $(i,u_i)$, then from any node, pick a random edge to follow according to its normalized weight. Then the formula above generalize to characterize the limit of opinion $x_i(\infty)$ in this system.

Proof of the equilibrium attained (Lemma 3):

• We draw the proof in the case where all biased nodes are stubborn. The proof relies on rewriting the evolution of the system as:

  $$x(t+1) = \tilde{A} x(t) + \tilde{B} x^{(S)}(0)$$ where $\tilde{A}$ is obtained from $A$ where all rows and columns associated with stubborn nodes are removed (it implies that these are only unbiased nodes), and $\tilde{B}_{i,j}$ where $i$ is unbiased and $j$ is stubborn is equal to $\frac{1}{|N(i)|}$ if $j\in N(i)$ and is zero otherwise.

• Interestingly, $\tilde{A}$ has the same eigenvalues as $A$ (because rows of $A$ equal to zero for stubborn nodes, and hence no eigenvector will put any weight on this coordinate). We hence deduce that the same equation evolution allows us to write:

  $$x(\infty)= \sum_{t\geq 0}{\tilde{A}^t} \tilde{B}x^{(S)}(0) = (I-\tilde{A})^{-1}\tilde{B} x^{(S)}(0)$$

• Finally, we observe that if we denote by $F_{i,j}=P[Z(\tau_S)=j|Z(0)=i]$, we have

  $$F_{i,j}=\tilde{B}_{i,j}+ \sum_{k\notin S} \tilde{A}_{i,k} F_{k,j}\;.$$ This observation comes from looking at one-step analysis of the random walk $Z$ starting in $Z(0)=i$. Let $k$ be the node $Z$ visits in the next step. We have $$P[Z(\tau_S)=j|Z(0)=i]=\sum_{k} P[Z(\tau_S)=j|Z(1)=k,Z(0)=i]\;.$$ First, $Z(1)=j$ with probability $\frac{1}{|N(i)|}$ if $i$ and $j$ are neighbors, and 0 otherwise, which is exactly $\tilde{B}_{i,j}$. Second, if $k\in S$ and $k\neq j$, then $Z(\tau_S)\neq j$ as the walk enters $S$ not in $j$. Finally, if $k\notin S$, we are back to the initial problem but starting in $k$ instead of $i$.
  This implies $F=(I-\tilde{A})^{-1}\tilde{B}$, hence $x=Fx^{(S)}(0)$

Studying the disagreement cost at equilibrium

D. Bindel, J. M. Kleinberg, and S. Oren, “How Bad is Forming Your Own Opinion?,” Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pp. 57–66, 2011.

Summary of contributions: * Show that when costs correspond to a sum on undirected edges, the equilibrium always incurs a total disagreement cost that is never more than $9/8$ of any other possible states. This result is tight on an elementary example. * Proves no general bound can be derived for the case of cost defined on directed edges (in which depending on the direction of disagreement, it is counted with a different weight), even if the degree remains small. However, directed graphs with unit weight that are Eulerian (each node has equal in and out degree) offers some appropriate bounds depending on their degree. * Shows that various graph modifications techniques to reduce disagreement in directed graphs leads to large computational complexity, and provide a few cases of single modifications that can be computed.

Model:

• Similar model as in work above with minor variations in the notations/assumptions:

  $$\textrm{Cost}_i = (x_i-x_i(0))^2 + \sum_{j\in N(i)} w_{i,j} (x_i-x_j)^2$$
  $$x_i= \frac{1}{1 + \sum_{j\in N(i)} w_{i,j} } \left(x_{i}(0) + \sum_{j\in N(i)}w_{i,j} x_{j}\right)$$

Let us consider a simple example first:

• Two nodes with opinion 0 and 1, which each of them values equally to the opinion of her neighbors are both connected to a third middle node which does not have (or do not value) her own opinion. If we denote their opinions by (x,y,z) it's like starting with (0,?,1) and finding an equilibrium, where the cost is hence
  • $(x-0)^2+(y-x)^2$, for the first node
  • $(y-x)^2+(z-y)^2$, for the middle node
  • $(z-y)^2+(1-z)^2$, for the last node

• It’s not too hard to see that $y$ should at any time remain 1/2 by symmetry,

  • $(x-0)^2+(\frac{1}{2}-x)^2$, for the first node
  • $(\frac{1}{2}-x)^2+(z-\frac{1}{2})^2$, for the middle node
  • $(z-\frac{1}{2})^2+(1-z)^2$, for the last node.

  In that case at equilibrum x=1/4 (since this node puts equal weight on her opinion 0 and the one of the middle node equal to 1/2). Similarly, z=3/4. This creates a cost $2 (\frac{1}{4})^2=\frac{1}{8}$ for all nodes, which sums to $\frac{3}{8}$. Intuitively, the marginal cost increase/decrease among all edges adjacent to a node should exactly compensate.

• Intuitively, if we interpret the sum of each term as a cost on edges (where we draw an edge between a node with an initial opinion and a virtual node that have this opinion), the total cost contains some edges multiple times. In particular, since the “middle” edges appear twice in the sum we could lower their cost for an equivalent increase on the peripheral edges that are only counting once. Intuively, this should improve the total cost. And it does: By minimizing $(x-0)^2+2(\frac{1}{2}-x)^2$ (obtained when derivative $2x+2\cdot (-2) \cdot (\frac{1}{2}-x)=6x-2$ is equal to zero for $x=1/3$) we obtain that assigning opinions $(1/3,1/2,2/3)$ would result overall in a total cost $2 ((1/3)^2+2(1/6)^2)=2 (1/9+1/18)= 2/6 = 1/3$. In other words, the cost of equilibrium which is $3/8$ is $9/8$ times larger.

The main contributions of this paper is to study that gap.

• The situation above is the worst case if the graph is undirected (THM1), the equilibrium always create a total cost that is at most $9/8$ larger than the optimal. This holds for general situation on weights, including stubborn nodes.
• The directed case is not as easy to bound. It’s simple to build a counter-example of a star where the equilibrium is arbitrarily bad in relative terms. This can also be done for bounded degree, and as soon as ratio of weights can be unbouded, so unit weight are only considered.
• For Eulerian directed graph (strongly connected, where indegree=outdegree for anynode) bounds can be given as function of degree (for regular graph), and as $O(d^2/\alpha^2)$ for max degree $d$ and edge-expansion $\alpha$.
• One potential area for improvement is “edge suggestion”, in which by artificially adding an edge to modify a node’s behavior the equilibrium of the whole society is improved. One can for instance show easily that if an undirected is reversed to become symmetrical, the resulting equilibrium is at most $(2\cdot 9/8)$ of the original optimal. Unfortunately, most of the related problem (adding the best set of edges, adding the best k edges (when k is part of the input), with/without constraints on nodes) are all NP hard. On the other hand, finding the best edge or the best weight for a given edge is easy.

The proof of the main prices of anarchy results for general undirected graphs is as follows.

• First, from symmetry $w_{i,j}=w_{j,i}$, we can deduce

$$\sum_{i,j>i} w_{i,j} (x_i-x_j)^2 = \sum_{i, j>i} w_{i,j} x_i(x_i-x_j) - \sum_{i, j>i} w_{i,j} x_j(x_i-x_j) \\ = \sum_{i, j>i} w_{i,j} x_i(x_i-x_j) + \sum_{i, j>i} w_{i,j} x_j(x_j-x_i) \\ = \sum_{i,j\neq i} w_{i,j} x_i(x_i-x_j) \\ = \sum_{i} x_i \left( \left(\sum_{j} w_{i,j}\right) x_i + \sum_{j\neq i} x_i (-w_{i,j}) x_j\right) \\ = x^T L x$$ where $L$ is a matrix $L_{i,j}=-w_{i,j}$ for $i\neq j$ and $L_{i,i}=\sum_{j} w_{i,j}$ (sometimes called the Laplacian matrix, generally defined by $\textrm{Degree}-\textrm{Adjacency}$ that has multiple properties related to the graph, in particular it is positive semidefinite matrix with only non-negative eigenvalues).

Hence, the total cost of the network can be written as $\textrm{Cost}(x)=2\cdot x^T L x + || x-x(0)||^2$. We can rewrite

$$\textrm{Cost}(x)=2\cdot x^T L x + (x-x(0))^T(x-x(0)) = x^T (2L+I) x - 2 x(0)^T x + x(0)^T x(0) \;.$$ this function is a quadratic form, and since $2L+I$ is positive definitive (i.e., its eigenvalues are all positive), the only minimizer of this cost satisfies $(2L+I)x^*=x(0)$ or, equivalently, $x^*=(2L+I)^{-1}x(O)$.

Note that any Nash equilibrium $\tilde{x}$ satisfies $(I+L)\tilde{x}=x(0)$. Indeed, we can write

$$\left((I+L)\tilde{x}\right)_i = (1+\sum_{j\neq i}w_{i,j}) \tilde{x}_i - \sum_{j\neq i} \tilde{x}_j$$ which is by definition of the best response seen above, equal to $x_i(0)$. This equality implies for the same reasons as above that $\tilde{x}=(I+L)^{-1}x(0)$.

Note that one can immediately use these two properties to show that the price of anarchy is upper bounded by $2$, but a better bound exists, that we now detail.

Given the form of $x^*$ and $\tilde{x}$, we have:

$$\textrm{Cost}(\tilde{x}) = \tilde{x}^T 2L \tilde{x} + ||\tilde{x}-x(0)||^2 = \tilde{x}^T 2L \tilde{x} + (\tilde{x}-x(0))^T(\tilde{x}-x(0)) = x(0)^T \left((I+L)^{-1}2L(I+L)^{-1} + ((I+L)^{-1}-I)^2\right) x(0) = x(0)^T M x(0)$$ where we call the (complicated) middle Matrix $M$.

Similarly

$$\textrm{Cost}(x^*) = x(0)^T \left((I+2L)^{-1}2L(I+2L)^{-1} + ((I+2L)^{-1}-I)^2\right) x(0) = x(0)^T N x(0)$$ where $N$ is the middle matrix.

As a consequence, since if we diagonalize $L$ in another base of vector that are orthogonal, the same base diagonalize $M$ and $N$ and the eigenvalues of $M$ and $N$ corresponds exactly to the function of the value in their respective form, hence

$$\lambda_i^M = \frac{1}{1+\lambda_i}2\lambda_i\frac{1}{1+\lambda_i}+\left(\frac{1}{1+\lambda_i}-1\right)^2 =\frac{2\lambda_i+\lambda_i^2}{(1+\lambda_i)^2}=\frac{\lambda_i(\lambda_i+2)}{(1+\lambda_i)^2}\;.$$ Similarly, we have
$$\lambda_i^N = \frac{1}{1+2\lambda_i}2\lambda_i\frac{1}{1+2\lambda_i}+\left(\frac{1}{1+2\lambda_i}-1\right)^2 = \frac{2\lambda_i+4\lambda_i^2}{(1+2\lambda_i)^2}=\frac{2\lambda_i}{1+2\lambda_i}$$ Hence $\lambda_i^M/\lambda_i^N = \frac{(\lambda_i+2)(1+2\lambda_i)}{2(1+\lambda_i)^2)}=\frac{\lambda_i^2+5/2 \lambda_i+1}{\lambda_i^2+2\lambda_i+1}$, this last function is seen to have a maximum equal to 9/8 when $\lambda_i=1$ which concludes the proof.

Analysis of the model with Pairwise Updates

The pairwise version of the above evolution is necessarily asynchronous and hence leads to larger effects of randomness.

• We generally consider the case where at any time one node $i$ is chosen with probability $1/n$ and condition on this event it meets another node $j$ with probability $\frac{1}{n}p_{i,j}$.
• Then we assume the conditional on $i$ meeting $j$, a symmetric interaction occurs with probability $\beta_{i,j}$ and an assymetric influence transition occurs with probability $\alpha_{i,j}$. Whenever $p_{i,j}\alpha_{i,j}>0$ we say this link is forceful.
• We called a directed edge $(i,j)$ active if $p_{i,j}(\beta_{i,j}+\alpha_{i,j})+p_{j,i}\beta_{i,j} >0$. Otherwise it indicates that at no time is $i$ updating its value by taking into account the value of $x_j$. In particular a node $i$ that has no outgoing active edge is by definition stubborn.

The main results in that pairwise model is to prove the convergence of the system to a limit that can be characterized by the evolution of an associated Markov Chain.

Two particular cases are studied depending on the topology of the networks

• Case 1: The set of edges active edges makes the graph strongly connected. This corresponds to a situation where each node, however biased or influential, is still influenced or averaging its opinion with some others and indirectly include anyone’s opinion in the sum. This case is also refered to as a “no man on an island” assumption. It also forbids that a stubborn is present.
• Case 2: At the other extreme of the spectrum we assume that all nodes are indirectly influenced by some stubborn nodes. In other words, not only do stubborn nodes exist, but their indirect effect through influence reaches anyone.

Case 1: no man on an island

For this particular case, one can show that the system always converge to a state in which all nodes agree. However, the value of this agreement is a random variable that depends on the system itself. The following paper establishes various bounds to study the effect of “influential” or “forceful” link.

D. Acemoglu, A. Ozdaglar, and A. ParandehGheibi, “Spread of (mis) information in social networks,” Games and Economic Behavior, vol. 70, no. 2, pp. 194–227, 2010.

When some agents disproportionally influence others (while still participating to the update of belief), how this leads to a consensus whose distribution may be influence by these agents. Under which conditions can this distortion be avoided.

• Model assumes possibility of a forceful interaction. As $i$ meets $j$, we have
  • with proba $\beta_{i,j}$, $x_i(k+1)=x_j(k+1)=\frac{x_i(k)+x_j(k)}{2}$
  • With proba $\alpha_{i,j}$, $x_i(k+1)=\varepsilon x_i(k)+(1-\varepsilon)x_j(k)$ and $x_j(k+1)=x_j(k)$
  • With proba $1-\alpha_{i,j}-\beta_{i,j}$, $x_i(k+1)=x_i(k)$ and $x_j(k+1)=x_j(k)$
• Assumptions: proba non-negative, sums to 1, wlog all edges have $\alpha_{i,j}+\beta_{i,j}>0$, the network is strongly connected.
• The evolution of the model can be seen as $x(k+1)=T(k)x(k)$ where $T(k)$ is a random (nxn) matrix and there exists a nonnegative matrix $\tilde{T}=E[T(k)]$ for all $k\geq 0$, which can be rewritten as $C+D$ where $$C=\frac{1}{n} \sum_{i,j} p_{i,j} ((1-\alpha_{i,j}-\beta_{i,j})I+(\alpha_{i,j}+\beta_{i,j})A^{i,j}) \;\textrm{and}\; D=\frac{1}{n} \sum_{i,j} p_{i,j}\alpha_{i,j} (J^{i,j}-A^{i,j})$$ $$\;\textrm{for}\; A^{i,j} = I - \frac{(e_i-e_j)(e_i-e_j)'}{2} \;\textrm{and}\; J^{i,j} = I - (1-\varepsilon)e_i(e_i-e_j)'$$ Note that $C$ denotes averaging interaction happening after gossip between nodes occur, while $D$ is a matrix capturing how much forceful agents bias this evolution.

The main contributions of the paper are:

• Convergence (THM1-2) of this dynamics to a state in which everyone is in the state state $\tilde{x}=\sum_j s_i x_i^0$, where $s_i$ is a nonnegative random vector that does not depend on the initial belief of agents and sums to 1. So as opposed We can show that $E[s_i]=\tilde{s}_i$ where $\tilde{s}_i$ is the weight of agent $i$ in the expected matrix $\tilde{T}$.

• Bias in the final outcome which may be estimated as $\sum_{i} (E[s_i] - \frac{1}{n}) x^0_i$ can be bounded (THM5-6) using the second largest eigenvalue of the matrix $C$

  $$\left|\left| E[s] - \frac{1}{n} e \right|\right|_2 \leq \frac{1}{1-\lambda_2(C)} \frac{\sum_{i,j} p_{i,j} \alpha_{i,j} }{n}$$ This implies in particular that if we consider a series of social network graph indexed by $n$ whose contact matrix $C_n$ satisfies $\inf_n 1-\lambda_2(C_n)>0$ (also known as an expander family), the first term remains a constant. In this case, if the total influence strength of all forceful agents grows smaller than $n$ as society expands, then the distribution of the outcome converges to the average of the initial beliefs.

• Another bound and properties of the bias can be obtained using the mean first passage time from state $i$ to state $j$ (defined as $m_{i,j}=E\left[\inf\{t\geq 0 \;|\; X_t=j\} \;|\; X_i=0\right]$) in a Markov Chain with transition given by the matrix $C$ (with stationary distribution denoted by $\pi$). In particular the excess of influence of agent $k$ is bounded as:

  $$\left|s_k-\frac{1}{n}\right| \leq \sum_{i,j} \frac{p_{i,j}\alpha_{i,j}}{2 n^2} |m_{i,k}-m_{j,k}| \leq \sum_{i,j} \frac{p_{i,j}\alpha_{i,j}}{2 n^2} (m_{i,j}+m_{j,i})$$ Note that the second inequality bounds the influence using the commute time from $i$ to $j$. This bound can be made more precise using the normalized cut value, we have: $$m_{i,j}+m_{j,i} \leq \frac{3n \log(n)}{\rho_{i,j}} \;\textrm{where}\; \rho_{i,j} = \min_{S\subseteq V} \left\{ \frac{\sum_{k\in S,l\notin S} \pi(i) C_{i,j}}{\pi(S) \pi(\bar{S})} \;|\; i\in S, j\notin S \right\}$$ This shows that if no good cut exists to separate the forceful agent from the one she influences, the mean commute time is probably small (of the order of $n\log(n)$) which shows that unless forceful links are very prominent (a fraction of the "interaction")

The core of the proof relies on a perturbation result from Markov Chain theory that involves the so-called fundamental matrix of the Markov Chain with transition matrix $C$ (defined as $Y=\sum_{k\geq 0} (C^k-C^{\infty})$, where $C^\infty$ has all rows equal to $\pi'$). Since the evolution of the Markov Chain is perturbed by $D$ (with sums along rows equal to $0$), we can deduce $||E[s]-\frac{1}{n}e||_2 \leq ||D Y||_2$$ which yields the result.

Case 2: All nodes under influence of stubborn

The analysis of this case generally focuses on the simpler case where all nodes with an outgoing influential or forceful edges are stubborn. This case is already complex to analyze as the system enters a persistent disagreement and fluctuation states where it converges only in distribution. This essentially means that the system becomes time-invariant, a property of its ergodicity. However, just like for the nodal update, one can again show that the expected opinion of a node is related to the behavior of a random walk.

D. Acemoglu, G. Como, F. Fagnani, and A. Ozdaglar, “Opinion fluctuations and disagreement in social networks,” Mathematics of Operations Research, vol. 38, no. 1, pp. 1–27, 2013.

Continuous opinion dynamics with a fixed set of stubborn agents. The main difference with the work above is that we do not assume any more that the active links formed a strongly connected graph. In particular, some agents may be influencing other without being influenced at all. These are stubborn and will not change their positions once they have adopted it initially.

Model

• Each node maintains an opinion x_i that fluctuates in continuous time $t$, according to the following evolution
  • node $i$ meets node $j$ according to a rate $r_{i,j}$ and when this happens it receives some influence from that node, updating his belief accordingly from $x_i(t^-)$ to $x_i(t)=(1-\theta_{i,j})x_i(t^-) + \theta_{i,j} x_j(t^-)$. A stubborn nodes is one that receives influence from no one (either because he does not meets or does not listen), we denote the set of stubborn nodes by $S$.
  • We define the rate transition matrix $Q_{i,j} = \theta_{i,j}r_{i,j}$ for $i\neq j$ and $Q_{i,i}=-\sum_{j\neq i} Q_{i,j}$ corresponding to a random walk between members of the population.
  • We assume that all nodes is connected to a stubborn nodes through a set of active links (those with $\theta_{i,j} r_{i,j}>0$). It’s equivalent to assume that the random walk with transition $Q$ eventually always hits a stubborn nodes.

Main contributions of the paper:

• A convergence result is obtained following results on iterated random functions (THM1). It is significantly more involved than previous result as (1) the convergence only applies to a process defined backward which means by considering the origin of time infinitely far away in the past(2) since the limit is not deterministic AND is not equal for all nodes, all results can only apply in distribution for process in continuous time. It prove that in such situation, although consensus is not obtained and people may vastly vary, at least the system reaches a steady state where the effect of time has no effect on any expected value.
• A characterization of the limit regime. Expectation and Cross products of two nodes' beliefs follow (THM3) the properties of the hitting times of the continuous time Markov Chain defined on nodes with transition rate $Q$ (that we denote by $V(t)$). $$E[x_i] = \sum_{j \in S} \gamma^i_{j} x_j \;\textrm{where}\; \gamma^i_j = P\left[V(\inf\{t\geq 0 | V(t) \in S\})=j\;|\;V(0)=i\right]$$ So the expected beliefe of $i$ is a linear combination of belief of stubborn agents, where the weight is given by the chance to hit from $i$ this particular agent first in a Markov Chain with rate transition $Q$.
• A sufficient condition for uniform expected belief which is relatively technical: After associating a discrete time Markov Chain to the rate $Q$, we consider its mixing time and the weight of the stubborn set in the associated probability distribution. If their products goes to zero then it can be shown that all agents have approximately the same expected belief. Note that this does not implies that they agree, or that their opinion may not continue to dynamically evolve strongly with time.

E. Yildiz, D. Acemoglu, A. Ozdaglar, A. Saberi, and A. Scaglione, “Binary Opinion Dynamics with Stubborn Agents,” ACM Transactions on Economics and Computation, 2013. (previously appeared as “Discrete opinion dynamics with stubborn agents,” SSRN 1744113, 2011).

Considers a special case of the model above: there are only two opinions {0,1}, and all influential transitions follow a complete trust (i.e., $\theta_{i,j}=1$ whenever this transition occurs).

The results of this paper are

• convergence in distribution of this process (THM1), identical to paper above. Expected opinion given by probability to hit a particular set with a given opinion (PROP1),
• A bound on the variance (which is in this case the product of two nodes being in state 1). Show that $$\sigma^2 \leq \frac{1}{N^2} \sum_{i \notin S} \gamma^i_1(1-\gamma^i_1)) (\textrm{centr}_i)^2$$ where $\sigma$ is the observed variance in steady state and $\textrm{centr}_i$ denotes the absorption probability at $i$ in a Markov Chain where $i$ is also a stubborn node, started from any other nodes uniformly: $\sum_{j\notin S} P\left[V(\inf\{t\geq 0 | V(t) \in S\cup\{i\}\})=i\;|\;V(0)=j\right]$
• A proof that optimal placement of the first stubborn agent for a position is given by a property related to the fundamental matrix of the Markov Chain before absorption.

Going further: More on study of disagreement

Most of the on going works deal with the nodal update model that is conceptually simple to relate to the notion of Best Response and Nash Equilibrium.

K. Bhawalkar, S. Gollapudi, and K. Munagala, “Coevolutionary opinion formation games,” presented at the STOC ‘13: Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, 2013.

Proposes more price of anarchy results for a similar model and considers a case where edges may be created/deleted by current agreement/disagreement.

F. Chierichetti, J. M. Kleinberg, and S. Oren, “On discrete preferences and coordination,” presented at the EC ‘13: Proceedings of the fourteenth ACM conference on Electronic commerce, 2013.

When opinion or choices are discrete, and the distance function comes from a preference ranking, how does a network of nodes lead to various efficiency.

Written with StackEdit.