{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# CS579: Lecture 08  \n",
    "\n",
    "**Information Diffusion**\n",
    "\n",
    "*[Dr. Aron Culotta](http://cs.iit.edu/~culotta)*  \n",
    "*[Illinois Institute of Technology](http://iit.edu)*\n",
    "\n",
    "With some figures from [Networks and Markets: Reasoning about a highly connected world](http://www.cs.cornell.edu/home/kleinber/networks-book/), David Easley and Jon Kleinberg"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Another Milgram Experiment\n",
    "\n",
    "<img width=500 src=\"http://www.portlandpua.com/stylelife/Files/Preparing/Influence%20The%20Art%20of%20Persuasion%20by%20Robert%20Cialdini/4_Social_Proof/4_Social_Proof-3.jpg\">\n",
    "\n",
    "[Source](http://www.portlandpua.com/stylelife/Files/Preparing/Influence%20The%20Art%20of%20Persuasion%20by%20Robert%20Cialdini/4_Social_Proof/index.html)\n",
    "\n",
    "![up](up.png)\n",
    "\n",
    "[Milgram et al. \"Note on the drawing power of crowds of different size.\" Journal of personality and social psychology 13.2 (1969): 79.](http://www.communicationcache.com/uploads/1/0/8/8/10887248/note_on_the_drawing_power_of_crowds_of_different_size.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Purchasing Decisions\n",
    "![iphone](http://i2.cdn.turner.com/cnn/dam/assets/120920021010-iphone-5-lines-nyc-horizontal-gallery.jpg)\n",
    "\n",
    "![samsung](https://i.pinimg.com/736x/f0/fc/6c/f0fc6c54d1b7d0a92ba62dfa6a2e3aca--signage-design-booth-design.jpg)\n",
    "\n",
    "Sources: [1](http://vr-zone.com/articles/apple-files-more-requests-for-bans-of-samsung-android-devices-why/17252.html)\n",
    "[2](http://www.cnn.com/2012/09/19/tech/mobile/iphone-5-line-tips/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## How do others' decisions affect my own?\n",
    "\n",
    "- **Informational**: Actions of others provide additional information \n",
    "- **Direct Benefit**: I join FaceBook because it is more popular than MySpace\n",
    "\n",
    "\n",
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Information Cascade\n",
    "\n",
    "- Others' decisions dominate personal evidence\n",
    "\n",
    "<br><br><br>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Other Examples\n",
    "\n",
    "- News stories\n",
    "- Retweeting\n",
    "- Buying a product\n",
    "- [Ice Bucket Challenge](http://en.wikipedia.org/wiki/Ice_Bucket_Challenge)\n",
    "- [Viral Cat Videos](https://www.youtube.com/watch?v=J---aiyznGQ)\n",
    "\n",
    "<br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Ingredients for a cascade\n",
    "\n",
    "- Sequential decisions\n",
    "- People can observe decisions made previously by others.\n",
    "- Each person has some private information to help make the decision.\n",
    "- No person can observe the private infomation of others.\n",
    "- But, each person can observe the **actions** of others.\n",
    "<br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Urn Experiment\n",
    "\n",
    "- Does an urn contain more red marbles or more blue marbles?\n",
    "\n",
    "![urn](http://poetry.literaturelearning.org/files/images/Ode_to_a_Grecian_Urn.jpg)\n",
    "\n",
    "Two possibilities:\n",
    "  - 50%: urn has 2 red marbles, 1 blue\n",
    "  - 50%: urn has 1 red marble, 2 blue\n",
    "\n",
    "- Sequential decisions:\n",
    "  - Student picks a marble that **only he sees**.\n",
    "  - Student announces his guess (more blue or more red).\n",
    "  - Repeat with next student."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** First student **\n",
    "\n",
    "- Sees blue $\\rightarrow$ \n",
    "- Sees red $\\rightarrow$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** First student **\n",
    "\n",
    "- Sees blue $\\rightarrow$ guesses blue\n",
    "- Sees red $\\rightarrow$ guesses red"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** Second student **\n",
    "- Sees same as first student $\\rightarrow$ \n",
    "- Sees different color as first student $\\rightarrow$ \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** Second student **\n",
    "- Sees same as first student $\\rightarrow$ Guesses same color as first student\n",
    "- Sees different color as first student $\\rightarrow$ Tie; arbitrarily guess what second student saw\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** Third student **\n",
    "- If first two guessed opposite colors $\\rightarrow$\n",
    "- If first two guessed the same color $\\rightarrow$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** Third student **\n",
    "- If first two guessed opposite colors $\\rightarrow$ Guesses what third student sees\n",
    "- If first two guessed the same color $\\rightarrow$ Gueses majority color\n",
    "  - **Regardless of what third student sees**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** Fourth Student**\n",
    "- Let's assume first two students guessed the same color.\n",
    "- What impact does third student's guess have on fourth student?\n",
    "\n",
    "<br><br><br><br>\n",
    "\n",
    "  - **None!**\n",
    "- If two marbles of the same color are drawn first, all future guesses provide no information.\n",
    "- Decisions of others dominate personal information $\\rightarrow$ **Cascade**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Conclusions of Urn Experiment\n",
    "\n",
    "- Surprising cascades can occur even assuming rationality.\n",
    "- Cascades can lead to sub-optimal outcomes.\n",
    "- Cascades are fragile:\n",
    "  - What if student 100 shows the class a red marble?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Modeling decision making under uncertainty\n",
    "\n",
    "- What is the probability that the urn has two red marbles? Given:\n",
    "  - What marble I see\n",
    "  - Previous guesses\n",
    "- Need to model how new information affects this probability."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Axiom of probability: \n",
    "\n",
    "$$ P(A|B) = \\frac{P(A,B)}{P(B)}$$\n",
    "\n",
    "![venn](venn.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$$ P(A|B) = \\frac{P(A,B)}{P(B)}$$\n",
    "\n",
    "\n",
    "$$ P(B|A) = \\frac{P(A,B)}{P(A)}$$\n",
    "\n",
    "\n",
    "$$ P(A|B) P(B) = P(A,B) = P(B|A) P(A)$$\n",
    "divide by $P(B)$:\n",
    "\n",
    "$$ P(A|B) = \\frac{P(A) P(B|A)}{P(B)} \\bf{\\hbox{  Bayes Rule }}$$\n",
    "\n",
    "- $P(A)$: **prior** probability of $A$ (without any additional information)\n",
    "- $P(A|B)$: **posterior** probability of $A$ given $B$.\n",
    "- Effect of observing $B$: $P(A|B) - P(A)$\n",
    "  - Change in prior of $A$ after observing $B$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Using Bayes' Rule for Urn Experiment\n",
    "\n",
    "- Let $B$ = urn is majority blue\n",
    "- Let $R$ = urn is majority red.\n",
    "- Let $b_i$ = student $i$ draws a blue ball\n",
    "- Let $r_i$ = student $i$ draws a red ball\n",
    "\n",
    "\n",
    "- At start of experiment:\n",
    "  - $P(B)=$?\n",
    "  - $P(R)=$?\n",
    "  \n",
    "<br><br><br>\n",
    "\n",
    "  - $P(B)=.5$\n",
    "  - $P(R)=.5$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Probability of drawing a blue ball from a blue urn?\n",
    "\n",
    "- $P(b_i|B)$ = ?\n",
    "\n",
    "<br><br><br><br>\n",
    "\n",
    "- $P(b_i|B) = \\frac{2}{3}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** Student 1 draws a blue marble:**\n",
    "\n",
    "$$P(B|b_1)=?$$\n",
    "\n",
    "Use **Bayes Rule** $ P(A|B) = \\frac{P(A) P(B|A)}{P(B)} $\n",
    "\n",
    "$$\\begin{align}\n",
    "P(B|b_1)&=&\\frac{P(B)P(b_1|B)}{P(b_1)}\\\\\n",
    "&=&\\frac{\\frac{1}{2} * \\frac{2}{3}}{P(B)P(b_1|B) + P(R)P(b_1|R)}\\\\\n",
    "&=&\\frac{\\frac{1}{2} * \\frac{2}{3}}{\\frac{1}{2} * \\frac{2}{3} + \\frac{1}{2} * \\frac{1}{3}}\\\\\n",
    "&=&\\frac{\\frac{1}{2} * \\frac{2}{3}}{\\frac{1}{2}}\\\\\n",
    "&=&\\frac{2}{3}\n",
    "\\end{align}$$\n",
    "\n",
    "Thus, student guesses **blue**, since that is the most probable.\n",
    "  - $P(R|b_1) = \\frac{1}{3}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Student 3**\n",
    "- Assume student 2 guesses **blue**\n",
    "- Student 3 draws **red** marble\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "P(B|b_1, b_2, r_3) = ?\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "<br><br><br>\n",
    "$$\n",
    "\\begin{align}\n",
    "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)}\\\\\n",
    "&=& \\frac{\\frac{1}{2}(\\frac{2}{3}*\\frac{2}{3}*\\frac{1}{3})}{P(b_1, b_2, r_3)}\\\\\n",
    "&=& \\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)}\\\\\n",
    "&=&\\frac{\\frac{2}{27}}{\\frac{1}{9}}\\\\\n",
    "&=&\\frac{2}{3}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "- Student guesses **blue**\n",
    "- Most probably outcome unaffected by observing a red marble!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** Student *n* **\n",
    "\n",
    "- If number of blue and red guesses are the same:\n",
    "  - Guess color that $n$ sees\n",
    "- If number of blue and red guesses differ by 1:\n",
    "  - Guess color that $n$ sees\n",
    "  - (arbitrarily break tie)\n",
    "- If number of blue and red guesses differ by 2 or more:\n",
    "  - Guess the majority"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "![cascade](cascade.png)\n",
    "\n",
    "[Source](https://github.com/iit-cs579/main/blob/master/read/ek-19.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- What happened to **Wisdom of Crowds?**\n",
    "\n",
    "![wisdom](http://cdn2.hubspot.net/hub/25951/file-13554177-jpg/images/building_committee_-_surowiecki_book-resized-600.jpg?t=1410360126000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Network Effect\n",
    "\n",
    "![network](network.png)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}