Publish on 28th October 2019
Category: Birds
0

Algorithmic and Economic Aspects of Networks

Nicole Immorlica

Beliefs in Social Networks

Given that we influence each other’s beliefs,- will we agree or remain divided?- who has the most influence over our beliefs?- how quickly do we learn?- do we learn the truth?

Observational Learning

Key Idea: If your neighbor is doing better than you are, copy him.

Bayesian Updating Model

n agentsconnected in a social networkat eachtime t= 1, 2, …, each agent selects an action from a finite setpayoffsto actions are random and depend on the state of nature

Agent Goal

maximize sum of discounted payoffs∑t > 0δt∙πitwhereδ< 1is discount factor andπitis payoff to i at time t.

Example

Two actionsaction Ahas payoff 1action Bhas payoff 2 with probability p and 0 with probability (1-p)If p > ½, agents prefer B, else agents prefer A.

Example

Agents havebeliefsμi(pj)representing probability agent i assigns to event that p =pj.Multi-armed bandit…with observations.

Example

B: 0

B: 0

A: 1

B: 2

A: 1

B: 2

B: 0

B: 0

Center agent, Day 0:Pr[p=1/3] = 0, Pr[p=2/3] = 1Play action B, payoff 0

Center agent, Day 1:Pr[p=1/3] > 0, Pr[p=2/3] < 1Play action A, payoff 1

Center agent, Day 2:Now must take into account “echoes” for optimal update

B: 2

A: 1

A: 1

B: 0

A: 1

A: 1

B: 0

A: 1

Example

Ignoring echoes,Theorem [Bala and Goyal]: With prob. 1, all agents eventually play the same action.Proof: By strong law of large numbers, if B is played infinitely often, beliefs converge to correct probability.

Example

Note, all agents play same action, but- don’t necessarily have same beliefs- don’t necessarily pick “right” action ** unless someone is optimistic about B

Imitation and Social Influence

At time t, agent i has anopinionpi(t)in [0,1].Letp(t) = (p1(t), …,pn(t))be vector of opinions.Matrix Trepresents interactions:

T11T12T13

T21T22T23

T31T32T33

How much agent 2 believes agent 1

Rows sum to 1

Updating Beliefs

Update rule: p(t) = T ∙ p(t-1)

T11T12T13

T21T22T23

T31T32T33

p1(t-1)p2(t-1)p3(t-1)

T11p1(t-1)T12p1(t-1)T13p1(t-1)

T21p2(t-1)T22p2(t-1)T23p2(t-1)

T31p3(t-1)T32p3(t-1)T33p3(t-1)

Example

1/31/31/3

1/21/20

01/43/4

Example

2

1

3

1/3

1/3

1/3

1/2

1/2

1/4

3/4

Example

Suppose p(0) = (1, 0, 0). Thenp(1) = T p(0) = = (1/3, 1/2, 0)p(2) = T p(1) = (5/18, 5/12, 1/8)p(3) = T p(2) = (0.273, 0.347, 0.198)p(4) = T p(3) = (0.273, 0.310, 0.235)… p(∞) (0.2727, 0.2727, 0.2727)

1/31/31/3

1/21/20

01/43/4

100

Incorporating Media

Media is listened to by (some) agents, but not influenced by anyone.Represent media by agent i withTii= 1,Tij= 0 for j not equal to i. Media influences agents k for whichTki> 0.

Converging Beliefs

When does process have a limit?Note p(t) = T p(t-1) =T2p(t-2) = … =Ttp(0).Process converges whenTtconverges.Final influence weights are rows ofTt.

Example

01/21/2

100

010

t

2/52/51/5

2/52/51/5

2/52/51/5

Example

01/21/2

100

100

Does not converge!

Example

01/21/2

100

100

1/2

1/2

1

1

Aperiodic

Definition. T is aperiodic if the gcd of allcycle lengths is one (e.g., if T has a selfloop).

Convergence

T is aperiodic and strongly connectedT converges

(standard results inMarkov chain theory)

Everyone should trust themselves a little bit.

Can be relaxed, see book.

Consensus

For any aperiodic matrix T, any “closed” and strongly connected group reaches consensus.

Social Influence

We look for a unit vector s = (s1, …,sn) such thatp(∞) = s ∙ p(0)Then s would be the relative influences of agents in society as a whole.

Social Influence

Note p(0) & T p(0) have same limiting beliefs, sos ∙ p(0) = s ∙ (T p(0))And since this holds for every p, it must be thats T = s

Social Influence

The vector s is an eigenvector of T with eigenvalue one.If T is strongly connected, aperiodic, and has rows that sum to one, then s is unique.Another interpretation: s is the stationary distribution of the random walk.

Computing Social Influence

Sinces ∙ p(0) = p(∞) = T∞∙ p(0)it must be that each row of T converges to s.

Who’s Influential?

Note, since s is an eigenvector,si=Tjisj, so an agent has high influence if they are listened to by influential people.

PageRank

Compute influence vector on web graph and return pages in decreasing order of influence.- each page seeks advice from all outgoing links (equally)- add restart probabilities to make strongly connected- add initial distribution to bias walk

Time to Convergence

If it takes forever for beliefs to converge, then we may never observe the final state.

Time to Convergence

Two agents1. similar weightings (T11~T21) implies fast convergence2. different weightings (T11>>T21) implies slow convergence

Diagonal Decomposition

Want to explore how farTtis from T∞Rewrite T in its diagonal decomposition soT =u-1Λufor a matrix u and adiagonal matrixΛ.1. Compute eigenvectors of T2. Let u be matrix of eigenvectors3. LetΛbe matrix of eigenvalues

Exponentiation

NowTtbecomes:(u-1Λu) (u-1Λu) … (u-1Λu)=u-1ΛtuandΛtis diagonal matrix, so easy exponentiate.

Speed of Convergence

1 0

0T11–T12

1 0

0 (T11–T12)t

t

Since (T11- T12) < 1, (T11- T12)tconverges to zero.Speed of convergence is related to magnitute of 2ndeigenvalue,… and to how different weights are.

More Agents

Speed of convergence now relates to how much groups trust each other.

Finding the Truth

When do we converge to the correct belief?

Assume Truth Exists

There is aground truthμ.There aren agents(to make formal, study sequence of societies with n∞).Each agent has asignalpi(0)distributed with meanμand varianceσi2.

Wisdom

Definition. Networks arewiseif p(∞) converges toμwhen n is large enough.

Truth Can Be Found

By law of large numbers, averaging all beliefs with equal weights converges to truth.Sufficient: agents have equal influence.

Necessary Conditions

Necessary that- no agent has too much influence- no agent has too much relative influence- no agent has too much indirect influence

1-δ

1-δ

1-δ

1-δ

1-δ

1-δ

δ

δ

δ

δ

δ

δ

Sufficient Conditions

Sufficient that the society exhibits-balance: a smaller group of agents does not get infinitely more weight in from a larger group than it gives back-dispersion: each small group must give some minimum amount of weight to larger groups

Assignment:

Readings:Social and Economic Networks, Chapter 8PageRankpapersReaction to paperPresentation volunteer?

0

Embed

Upload

_ …