CS579: Lecture 08¶

Information Diffusion

Dr. Aron Culotta
Illinois Institute of Technology

With some figures from Networks and Markets: Reasoning about a highly connected world, David Easley and Jon Kleinberg

Another Milgram Experiment¶

Source

Milgram et al. "Note on the drawing power of crowds of different size." Journal of personality and social psychology 13.2 (1969): 79.

Purchasing Decisions¶

Sources: 1 2

How do others' decisions affect my own?¶

• Informational: Actions of others provide additional information
• Direct Benefit: I join FaceBook because it is more popular than MySpace

Information Cascade¶

• Others' decisions dominate personal evidence

Other Examples¶

• News stories
• Retweeting
• Buying a product
• Ice Bucket Challenge
• Viral Cat Videos

Ingredients for a cascade¶

• Sequential decisions
• People can observe decisions made previously by others.
• Each person has some private information to help make the decision.
• No person can observe the private infomation of others.
• But, each person can observe the actions of others.

Urn Experiment¶

• Does an urn contain more red marbles or more blue marbles?

Two possibilities:

• 50%: urn has 2 red marbles, 1 blue

• 50%: urn has 1 red marble, 2 blue

• Sequential decisions:

  • Student picks a marble that only he sees.
  • Student announces his guess (more blue or more red).
  • Repeat with next student.

** First student **

• Sees blue $\rightarrow$
• Sees red $\rightarrow$

** First student **

• Sees blue $\rightarrow$ guesses blue
• Sees red $\rightarrow$ guesses red

** Second student **

• Sees same as first student $\rightarrow$
• Sees different color as first student $\rightarrow$

** Second student **

• Sees same as first student $\rightarrow$ Guesses same color as first student
• Sees different color as first student $\rightarrow$ Tie; arbitrarily guess what second student saw

** Third student **

• If first two guessed opposite colors $\rightarrow$
• If first two guessed the same color $\rightarrow$

** Third student **

• If first two guessed opposite colors $\rightarrow$ Guesses what third student sees
• If first two guessed the same color $\rightarrow$ Gueses majority color
  • Regardless of what third student sees

** Fourth Student**

• Let's assume first two students guessed the same color.
• What impact does third student's guess have on fourth student?

• None!
• If two marbles of the same color are drawn first, all future guesses provide no information.
• Decisions of others dominate personal information $\rightarrow$ Cascade

Conclusions of Urn Experiment¶

• Surprising cascades can occur even assuming rationality.
• Cascades can lead to sub-optimal outcomes.
• Cascades are fragile:
  • What if student 100 shows the class a red marble?

Modeling decision making under uncertainty¶

• What is the probability that the urn has two red marbles? Given:
  • What marble I see
  • Previous guesses
• Need to model how new information affects this probability.

Axiom of probability:

$$ P(A|B) = \frac{P(A,B)}{P(B)}$$

$$ P(A|B) = \frac{P(A,B)}{P(B)}$$$$ P(B|A) = \frac{P(A,B)}{P(A)}$$$$ P(A|B) P(B) = P(A,B) = P(B|A) P(A)$$

divide by $P(B)$:

$$ P(A|B) = \frac{P(A) P(B|A)}{P(B)} \bf{\hbox{ Bayes Rule }}$$

• $P(A)$: prior probability of $A$ (without any additional information)
• $P(A|B)$: posterior probability of $A$ given $B$.
• Effect of observing $B$: $P(A|B) - P(A)$
  • Change in prior of $A$ after observing $B$

Using Bayes' Rule for Urn Experiment¶

• Let $B$ = urn is majority blue

• Let $R$ = urn is majority red.

• Let $b_i$ = student $i$ draws a blue ball

• Let $r_i$ = student $i$ draws a red ball

• At start of experiment:

  • $P(B)=$?
  • $P(R)=$?

• $P(B)=.5$
• $P(R)=.5$

Probability of drawing a blue ball from a blue urn?

• $P(b_i|B)$ = ?

• $P(b_i|B) = \frac{2}{3}$

** Student 1 draws a blue marble:**

$$P(B|b_1)=?$$

Use Bayes Rule $ P(A|B) = \frac{P(A) P(B|A)}{P(B)} $

$$\begin{align} P(B|b_1)&=&\frac{P(B)P(b_1|B)}{P(b_1)}\\ &=&\frac{\frac{1}{2} * \frac{2}{3}}{P(B)P(b_1|B) + P(R)P(b_1|R)}\\ &=&\frac{\frac{1}{2} * \frac{2}{3}}{\frac{1}{2} * \frac{2}{3} + \frac{1}{2} * \frac{1}{3}}\\ &=&\frac{\frac{1}{2} * \frac{2}{3}}{\frac{1}{2}}\\ &=&\frac{2}{3} \end{align}$$

Thus, student guesses blue, since that is the most probable.

• $P(R|b_1) = \frac{1}{3}$

Student 3

• Assume student 2 guesses blue
• Student 3 draws red marble

$$ \begin{align} P(B|b_1, b_2, r_3) = ? \end{align} $$

$$ \begin{align} P(B|b_1, b_2, r_3) &=& \frac{P(B)P(b_1, b_2, r_3|B)}{P(b_1, b_2, r_3)}\\ &=& \frac{\frac{1}{2}(\frac{2}{3}*\frac{2}{3}*\frac{1}{3})}{P(b_1, b_2, r_3)}\\ &=& \frac{\frac{1}{2}(\frac{2}{3}*\frac{2}{3}*\frac{1}{3})}{P(B)P(b_1, b_2, r_3|B) + P(R)P(b_1, b_2, r_3|R)}\\ &=&\frac{\frac{2}{27}}{\frac{1}{9}}\\ &=&\frac{2}{3} \end{align} $$

• Student guesses blue
• Most probably outcome unaffected by observing a red marble!

** Student n **

• If number of blue and red guesses are the same:
  • Guess color that $n$ sees
• If number of blue and red guesses differ by 1:
  • Guess color that $n$ sees
  • (arbitrarily break tie)
• If number of blue and red guesses differ by 2 or more:
  • Guess the majority

Source

• What happened to Wisdom of Crowds?

Network Effect¶